インスタントPL/0コンパイラ

再会

1980年代のこと、貧乏学生だった私は水道橋の書店、書泉グランデに入りびたりで立ち読みしてました。bitのバックナンバーです。毎日のように立ち読みに来るので店員さんに呆れられてたみたいです。bitの7人の執筆者たちで書かれた記事を読むのが楽しかったのです。でも、当時は貧乏学生ですから生活費を節約するのにbit誌は買わず終いでした。ところが最近になって電子書籍でbitが復刻されました。あの頃立ち読みした記事ってどんな話だっけ？また読み直しています。その中でも印象に残っていたのは「インスタント・コンパイラ」の記事でした。LispでサラサラとPascalコンパイラを作っちゃったんだよなぁ。改めて読み直してみると再発見がありました。そして、自分でも作れそうでした。自作のEasy-ISLisp用にインスタント・コンパイラを作ってみました。

bit誌　1987年6月号より引用

PL/0の言語仕様

私のおぼろげな記憶ですとPascalコンパイラを作っちゃったという内容だと思っていたのですが、PL/0でした。教育用にPascalを簡単化したものです。記事中でBNFの説明をしています。ネット検索でみつけたBNFは次のようになっていました。

program = block "." .

block = [ "const" ident "=" number {"," ident "=" number} ";"]
        [ "var" ident {"," ident} ";"]
        { "procedure" ident ";" block ";" } statement .
statement = [ ident ":=" expression | "call" ident |
            "begin" statement {";" statement } "end" |
            "if" condition "then" statement |
            "while" condition "do" statement ].
condition = "odd" expression |
            expression ("="|"#"|"<"|"<="|">"|">=") expression .
expression = [ "+"|"-"] term { ("+"|"-") term}.
term = factor {("*"|"/") factor}.
factor = ident | number | "(" expression ")".

例題

記事では最小公約数を求めるPL/0のコードをLispのS式で表したものが題材として使われていました。自分流にやりやすいように少し改編を加えました。次のコードです。

(program gcd
     (const (x = 10)(y = 45))
     (var z)
     (procedure gcd1 
         (var a b)
         (a := x) (b := y)
         (while (a /= b) do
            (if (a < b) then (b := (b - a)) else (a := (a - b))))
         (z := a))
     ((call gcd1)
      (write z))))

下記はbit誌に掲載されたオリジナルなコードです。（bit1987年6月より引用）

if構文をif　then　elseに変更させてもらいました。オリジナルのコードですと副作用によりうまく計算できませんでした。
begin~endはオリジナルと同様に ((statement1) ... (statementn))のようにカッコで括ることとしています。
定数宣言部、変数宣言部はカッコで括らずに独立させています。

パターンマッチが大活躍

自作のEasy-ISLispにはパターンマッチマクロをライブラリとして用意してあります。これは最近はやりのElixirという言語にインスパイアされて作ったものです。Prologユニフィケーション風のパターンマッチングを可能にしています。PL/0の仕様は前方参照なので素直に最初から順次読み込んでいくだけで済みます。

代入文の右辺は中置記法を可能にしてります。これは数式処理の第一人者であった下地貞夫先生のコードを先生の許可を得てライブラリとして公開しているものです。このライブラリを使って := による代入文がでてきたら右辺を中置記法に変換しています。

(defpattern comp
    (((program _x :rest _y)) `(defmodule ,_x ,@(comp-block _y))))

(defpattern comp-block 
    ((empty) nil)
    ((((const :rest _x) :rest _r)) (append (comp-const _x) (comp-block _r)))
    ((((var :rest _x) :rest _r)) (append (comp-var _x) (comp-block _r)))
    ((((procedure _x :rest _y) _r)) (cons (comp-procedure _x (car _y)) (comp-block _r)))
    ((_x) (comp-statement _x)))
    

(defpattern comp-const
    ((empty) nil)
    ((((_x = _y) :rest _r)) (cons `(defconstant ,_x ,_y) (comp-const _r))))

(defpattern comp-var
    ((empty) nil)
    (((_x :rest _r)) (cons `(defglobal ,_x nil) (comp-var _r))))

(defun comp-procedure (name body)
    `(defun ,name nil ,(comp-body body)))

(defpattern comp-body
     ((empty) nil)
     ((((var :rest _x) :rest _r)) `(let ,(let-var _x) ,@(comp-body _r)))
     ((((const :rest _x) :rest _r)) `(let ,(let-const _x) ,@(comp-body)))
     ((_x) (comp-statement _x)))

(defpattern comp-statement
    ((empty) nil)
    ((((_x := _y) :rest _r)) (cons `(setq ,_x ,(infix->prefix _y)) (comp-statement _r)))
    ((((while _x do _y) :rest _r)) (cons `(while ,(infix->prefix _x) ,@(comp-statement (list _y)))
                                                (comp-statement _r)))
    ((((if _x then _y else _z) :rest _r)) (cons `(if ,(infix->prefix _x) 
                                                           ,@(comp-statement (list _y))
                                                           ,@(comp-statement (list _z)))
                                               (comp-statement _r)))
    ((((call _x) :rest _r)) (cons `(,_x) (comp-statement _r)))
    ((((write _x) :rest _r)) (cons `(format (standard-output) "~A",_x) (comp-statement _r)))
    ((_x) (error "syntax-error" _x)))


(defun let-var (x)
    (if (null x)
        nil
        (cons (list (car x) nil)
              (let-var (cdr x)))))

(defun let-const (x)
    (if (null x)
        nil
        (cons (list (elt (car x 0)) (elt (car x) 2))
              (let-const (cdr x)))))

変換されるLispコード

上記の例をコンパイルしますと次のようなコードに変換されます。defmoduleというのはEasy-ISlispにおけるISLispの拡張構文です。モジュールを生成することとなっています。

program構文内における変数、定数宣言部は大域なものとしてdefglobal　defconstantに変換しています。procedure内の変数、定数宣言部はLispのlet構文に変換しています。

(DEFMODULE GCD
           (DEFCONSTANT X 10)
           (DEFCONSTANT Y 45)
           (DEFGLOBAL Z NIL)
           (DEFUN GCD1
                  NIL
                  (LET ((A NIL) (B NIL))
                       (SETQ A X)
                       (SETQ B Y)
                       (WHILE (/= A B) (IF (< A B) (SETQ B (- B A)) (SETQ A (- A B))))
                       (SETQ Z A)))
           (GCD1)
           (FORMAT (STANDARD-OUTPUT) "~A" Z))

スープは冷めないうちに

コンパイラ作成といいますと分厚い専門書を読んで理解しないと作れないようなイメージがあります。本格的なものを作ろうとすると膨大な時間と労力を必要とすることでしょう。飽きっぽい私なんぞは、そんなことをしているうちに興味が薄れてしまうかもしれません。ところがLispで作ればほんの数時間です。行数も100行以内。とりあえず作れてしまいます。形になるとうれしいものです。そしたら構文エラーチェック、意味論のチェックなどと新たな目標が生じます。こんな経験のためにLispはとても役に立ちます。

わがLispは永遠に不滅です。

1970年代前半はLispがふんだんに使える環境はあまりなかったと聞きます。泣く泣くFortranで数式処理や定理証明を書いたものだよと先駆者が書いている記事を読んだことがあります。bit誌の記事にもLispは大量のメモリを食うのでつい最近まで迫害の日々だったよ、という話がでてきます。当時は大型機と言えども非力でした。タイムシェアリングも出始めの頃だったと思います。Lispは当時の研究者にとって憧れの的だったようです。

今や21世紀もおよそ四半世紀が過ぎLispは普通のパソコン上で余裕で動作するようになりました。コンピューターパワーの増大はElixirのようなモダンな言語を許容するようになりました。1970年代のマシンではLispでさえリソース大食いと言われたのです。現代の計算機パワーを大食いするモダンな言語は到底許容されなかったでしょう。今やそうしたモダンな言語が楽々パソコン上で走るようになりました。さて、それではLispはもう不要なのでしょうか？いえいえ、上述のような事例ではLispはその良さを今でも存分に発揮します。モダンな言語はその内部の複雑な仕組みをベールに包んでしまいました。内部がどうなっているのかは一般のプログラマには想像がつきません。一方、Lispはモロ出しです。教育的な分野においてLispはまだまだこれからも力を発揮することでしょう。

ソースコード

Easy-ISLispはISLispスタンダード互換のインタプリタ・コンパイラです。OSSとして公表しています。exampleフォルダーに本記事のソースコードを置いてあります。