【Scheme】ForthをSchemeで実装してみた。

はい。今度はScheme（処理系はGaucheを使用）でForthを実装してみました。

プログラムは5つの部分に分かれていて、
１）スタック管理
２）標準入力からプログラムを読むリーダ
３）ForthプログラムをSchemeプログラムに変換するトランスレータ
４）ワードが登録される辞書
５）実行制御
という構成になっています。

とりあえず、各部分の説明をしていきます。

１）スタック管理

;;; スタック管理

(define *data-stack* '())

(define (push val)
  (set! *data-stack* (cons val *data-stack*)))

(define (pop)
  (cond
   ((null? *data-stack*)
    (raise "Stack UnderFlow."))
   (else 
    (let ((val (car *data-stack*)))
      (set! *data-stack* (cdr *data-stack*))
      val))))

スタック管理は面倒くさくないグローバル変数を使ったものにしました。
関数もPUSHとPOPのみです。POPにはスタックアンダーフローがでたら例外が投げられるようになっています。

２）標準入力からプログラムを読むリーダ

;;; 標準入力から読み込み、トークンに分割する。

(define (trim str)
  (begin
    (set! str (regexp-replace #/^\s+/ str ""))
    (set! str (regexp-replace #/\s+$/ str ""))
    str))

;; シンボルに使えない文字を変換する
(define (def-word-translate str)
  (begin
    (set! str (regexp-replace-all #/\;/ str "edef"))
    (set! str (regexp-replace-all #/\:/ str "sdef"))
    (set! str (regexp-replace-all #/\./ str "dot"))
    (set! str (regexp-replace-all #/\.([a-zA-Z])/ str "dot\\1"))
    (set! str (regexp-replace-all #/\s+/ str " "))
    str))

;; 半角スペースで分割
(define (tokenizer str)
  (token->symbol (string-split (def-word-translate str) " ")))

;; トークンをシンボルと数値のリストにする
(define (token->symbol tokens)
  (cond
   ((null? tokens) '())
   ((rxmatch #/[0-9\.]+/ (car tokens))
    (cons (string->number (car tokens))
   (token->symbol (cdr tokens))))
   (else
    (cons (string->symbol (car tokens))
   (token->symbol (cdr tokens))))))

;; 標準入力からプログラムを読み取り、トークンにして返す
(define (reader)
  (let ((line (read-line)))
    (cond
     ((eof-object? line) '())
     ((string=? "" (trim line))
      (reader))
     (else
      (tokenizer (trim line))))))

基本的には標準入力から入ってきた文字列をトークンに分割するだけなのですが、「；」や「．」がSchemeでは特別な意味を持っているので、変換してからトークンに分割しています。

３）ForthプログラムをSchemeプログラムに変換するトランスレータ

;;; ForthプログラムをSchemeに変換する
(define *program* '())

(define (translate-token token)
  (cond
   ((number? token)
    (list 'push token))
   ((search-dict token)
    (list (get-dict token)))
   (else
    (raise (format #f "Undefined [~A]." token)))))

(define (define-word tokens)
  (cond
   ((null? tokens)
    (raise "Syntax Error: [;] is missing."))
   ((eq? 'edef (car tokens)) '())
   (else
    (cons (translate-token (car tokens))
   (define-word (cdr tokens))))))

(define (translate tokens define-flag)
  (cond
   ((null? tokens) '())
   ((and define-flag)
    (if (eq? (car tokens) 'edef)
 (translate (cdr tokens) #f)
 (translate (cdr tokens) #t)))
   ((eq? (car tokens) 'sdef)
    (add-dict (cadr tokens) 
       (append '(lambda ()) (define-word (cddr tokens))))
    (translate (cdr tokens) #t))
   (else
    (cons (translate-token (car tokens))
   (translate (cdr tokens) #f)))))

トランスレータは今はこれだけです。これに「ループ処理」や「ローカル変数」などを実装するともっと長くなりそうです。
ワード定義もここでやっていて、
(append '(lambda ()) '(define-word ...))
とやれば、手軽にワードを生成することができますね。

４）ワードが登録される辞書

;;; 辞書用プログラム
(define *dictionaly* (make-hash-table 'equal?))

;; 辞書初期化
(define (init-dict)
  (begin
    (hash-table-put! *dictionaly* '+ 
       (lambda () (push (+ (pop) (pop)))))
    (hash-table-put! *dictionaly* '- 
       (lambda () (let ((a (pop))) (push (- (pop) a)))))
    (hash-table-put! *dictionaly* '* 
       (lambda () (let ((a (pop))) (push (* (pop) a)))))
    (hash-table-put! *dictionaly* '/ 
       (lambda () (let ((a (pop))) (push (/ (pop) a)))))
    (hash-table-put! *dictionaly* 'mod 
       (lambda () (let ((a (pop))) (push (mod (pop) a)))))
    (hash-table-put! *dictionaly* 'dot 
       (lambda () (print (pop))))
    (hash-table-put! *dictionaly* 'dots
       (lambda () (print (reverse *data-stack*))))
    (hash-table-put! *dictionaly* 'exit
       (lambda () (exit)))
    ))

;; 辞書に追加
(define (add-dict key val)
  (hash-table-put! *dictionaly* key val))

;; 辞書検索
(define (search-dict key)
  (hash-table-exists? *dictionaly* key))

;; 辞書から取得
(define (get-dict key)
  (if (search-dict key)
      (hash-table-get *dictionaly* key)
      (raise (format #f "Undefined [~A]" key))))

ワード辞書もグローバル変数としました。辞書からワードを取得するとき、ワードが存在しなければ例外が投げられます。
ワードは「init-dict」関数に追加していけば使える組み込みワードが増えます。今は四則演算と表示くらいしかないですがｗ

５）実行制御

;;; Forthエントリポイント

;; 処理系初期化
(define (init-forth)
  (begin
    (load "./dictionaly")
    (load "./reader")
    (load "./stack")
    (load "./translate")
    (init-dict)))

;; ForthプログラムをSchemeに変換した結果を実行する
(define (exec-forth prog ret)
  (cond
   ((null? prog) ret)
   (else
    (exec-forth (cdr prog)
  (eval (car prog) (interaction-environment))))))


(init-forth)
(let loop ()
  (display "> ")
  (flush)
  (display (exec-forth (translate (reader) #f) #f))
  (newline)
  (loop))

これは特に説明することもないです。
処理系の初期化関数とトランスレートしたForthプログラムの実行くらいです。
トランスレートしたプログラムはただevalしてるだけですね。

こんな感じです。

【Forth】JavaScriptでForthっぽいの作ってみた。

ちょっと前から、簡単な言語構造をしているプログラミング言語を他の言語で実装することにはまっています。
今回挑戦したのはForth言語です。
今回はJavascriptで作ったので、整数も浮動小数点数も同じ1つのスタックで処理できます。つまり、「1.2 2 + sqrt」とか書くことが可能です。
この言語の特徴は「スタック志向」と「逆ポーランド記法（後置記法）」につきます。他の言語で言う「関数」は「ワード」といいます。ワードは辞書に登録されています。
と、突然言われても良くわからないのと思うので、早速サンプルプログラムをいくつか列挙して解説していきたいと思います。
Forthは（というより後置記法がですが）偶然にも日本語の並びにとても似ているので日本語で説明するのが実は簡単です。

04-21追記：個別サイトを作ってみました。JS Forth

●インタプリタデモ
１．下の入力欄にプログラムを入力して、エンターキーを押します。
２．自動的に計算結果が入力欄の下にたまります。
※このページをリロードすると定義したワードが消えてしまいますので注意してください。




●20000円を3人で割り勘にする
　→　20000 3 /mod floor . .
解説：
上のプログラムは以下の通り処理が進みます。
１）20000をスタックに積む。3をスタックに積む。(20000 3)
２）スタックから2つ値を取り出して、除算をし、剰余をスタックに積む。商をスタックに積む。(/mod)
３）スタックからひとつ取り出して小数点以下を切り捨てる。(floor)
４）スタックから1つ取り出して表示する。(.)
５）スタックから1つ取り出して表示する。(.)
ね、簡単でしょ？
日本語で説明するときは、「20000円と3万円で割り算して商と余りを出す。商の小数点以下を切り捨てて結果を出す」といったところでしょうか。

●割り勘ワード定義
上のプログラムをワード（関数）にしてみます。
　→　: warikan ( n1 n2 -- n n ) /mod floor ;
解説：
１）「：（以下コロン）」はワード定義が始まるときに書きます。コロンがないとForthインタプリタは解釈モードとして動作し、結果を出そうとします。それをやめさせるにはこのコロンが必要です。コロンが見つかったときインタプリタは「コンパイルモード」になってプログラムがワード定義だとわかり、結果を出すのではなく定義されたワードを辞書に登録します。
２）「warikan」はワード名です。
３）「(」～「)」はコメントです。この場合のコメント「( n1 n2 -- n n )」はスタックから2つ取り出し、処理結果を2つ積む。という内容のコメントです。
４）「/mod floor」はwarikanワードのプログラム本体でこれらに引数の記述は必要なく、ワードの中でスタックからポップする処理やプッシュ処理が記述されているので「引数を本当に」とりません。
５）「；」はコロン定義の終了マークです。

Forth言語のプログラムは以上のような感じです。

●組み込みワード
今のところ組み込みワードは以下の通りです。
注意としては、制御構造ワードは「コンパイルモード」でしか使用できないところでしょうか。
詳しいワードの説明は「GForthマニュアル」がいいと思います。

・算術演算(整数・小数の区別なし)
+　1+　-　1-　*　/　mod　/mod　negate　abs　min　max

・ビット演算
and　or　xor　invert　lshift　rshift　2*　2/

・比較演算
<　<=　<>　=　>　>=　0<　0<=　0<>　0>　0>=

・算術関数
floor　round　**　sqrt　exp　log　cos　sin　tan　acos　asin　atan　atan2　pi

・制御構造
if　else　then　endif　begin　agein　repeat　while　until　?do　loop　+loop　-loop　unloop　leave　exit　recurse

・スタック操作
drop　nip　dup　over　tuck　swap　rot　-rot　pick　clearstacks

・表示
.　.s