パーサーコンビネータで作るインタープリタ

ふと、パーサーコンビネータでパーサーを作ると、それをそのままインタープリタとして走らせられるんじゃないか、ということを思い付きました。

普通はファイルやネットワークの入力ポートを

(parse p input-port)

のようにして渡すことで (p はパーサー関数)、パースが行われます。

ここに (current-input-port) を渡してやれば、キー入力を受け取って解析してくれるインタープリタが即出来上がるんじゃないか、という思惑です。

が、実際やってみたところ、ちょっと上手くいきませんでした。

parse 関数の中でポートが遅延リスト (ストリーム) 化されるんですが、どうもそこで eof-object を受け取るまで入力を待ち続ける仕様であるために、パースが終了できないみたいです。

キーボードで eof-object を入力する方法があれば、あるいは、パースに成功したらその時点で入力を待つのを止められれば良いと思うんですが、ちょっとやり方が分かりませんでした。

ということで、単純に read-line で入力を受け取る方式でやってみました:

(require "parser.ss")

(define (prompt)
  (printf "~%>>> ")
  (flush-output (current-output-port))
  (read-line))

(define (repl p)
  (let loop ((input (prompt)))
    (printf "~s~%" (parse p input))
    (loop (prompt))))

これに、中置記法の四則演算をするパーサー (arith.ss) を与えてみると:

> (repl (dynamic-require "arith.ss" 'arith))
>>> 1 + 2
3

>>> 1 + 2 * 3
7

>>> (1 + 2) * 3
9

\(^o^)/

実にあっけないですが、パーサー自体が元々評価器としての機能を持っていたためにこういうことが可能なわけです。

ただし read-line を使っているため、1行で完結する式しか受け取れないのが欠点ですね。ちょっと工夫してみました:

(define (append-lines x y)
  (cond ((not x) y)
        ((not y) x)
        (else (string-append x (string #\newline) y))))

(define (read-input)
  (let loop ((input #f))
    (cond ((char-ready?)
           (loop (append-lines input (read-line))))
          ((and input (> (string-length input) 0))
           input)
          (else
           (sleep 0.5)
           (read-input)))))

read-line の所を read-input に置き換えると、Emacs だと CTRL-j で改行しながら入力できるようになります。

環境というものを持たないので本格的なプログラミング言語は動かせなさそうなのが問題かなと思いますが、解決可能かどうか考え中です。