Think Stitch
PRINCIPIA  最近の更新


LispKit Lisp 4 - Read-Compile-Execute-and-Print, without Loop

C で書いた SECD 機械にコンパイラを組み込んで,入力された式を自力でコンパイルし実行できるようにします. これで Gauche から独立して LispKit Lisp だけで Lisp のプログラムを実行できるようになります.

関数 rd, wr の追加

入力ができるように rd 関数を追加します.ついでに wr も追加しましょう. はじめに Scheme 上の SECD 機械でテストをしてから C へ移ることにします.

まず SECD 機械に命令を追加します.Scheme の場合はシンボル,C の場合は整数にします.

(define RD 'RD)
(define WR 'WR)
;;; or
(define RD 24)
(define WR 25)

vm のディスパッチに RD, WR のためのブランチを追加します. 見てのとおり,RD は入力した式をスタックに積むだけ,WR はスタックのトップにある値を表示するだけです.

(define (vm s e c d)
  (match c
    ......
    (('RD . c)
     (vm (cons (read) s) e c d))
    (('WR . c)
     (format #t "~S\n" (car s))
     (vm s e c d))
    ......))

Read-Compile-Execute-Print プログラム

次に,入力された式をコンパイルして実行するコードを用意して,SECD 機械で実行できるようにコンパイルします.SECD 機械上で実行時にコンパイルするわけですから,コンパイラのコードをまるまる含めます.

ここでは式を1つ評価したらそれで終わりとします.ループも末尾呼び出し最適化もないのでとりあえずこうしました. REPL ならぬ REP,コンパイルが入るので RCEP でしょうか.

(compile
 '(letrec
      ((compile
        (lambda (e)
          (comp e '() '())))
       ......)
    (exec (compile (rd)))))

コンパイルされたコードを実行する関数 exec は次のようになっています. コンパイルされたコード(exec 関数の引数)を,引数をとらない lambda 式の本体とみなし,空の環境と合わせてクロージャを作り,空の引数リストに適用する(AP 命令)ことで実行します.いちばん面白いところです.

((eq (car e) 'exec)
 (cons LDC
       (cons '()
             (cons LDC
                   (cons '()
                         (comp (car (cdr e)) n
                               (cons CONS
                                     (cons AP c))))))))

Scheme による SECD 機械で実行して確認することができます.

(vm '() '() c '())

C による SECD 機械の拡張

Scheme のときと同じように拡張します.まず命令を追加します.

enum VM_INST {
  LD,   LDC,  LDF,  AP,   RTN,  DUM,  RAP,  SEL,  JOIN,  SOR,  NON,
  CAR,  CDR,  CONS, ATOM, EQ,  SYMBOLP,  INTEGERP,  LESS,
  ADD,  SUB,  MUL,  DIV,  REM,
  RD, WR
};

命令の処理を vm に追加します.

void vm(void)
{
    while (1) {
      ......
      switch (fixnum_value(car(C))) {
      ......
      case RD:
      {
          S = cons(read_sexpr(stdin), S);
          C = cdr(C);
      }
      break;

      case WR:
      {
         ptr_t p = car(S);
         write_sexpr(p);
         printf("\n");
         C = cdr(C);
      }
      break;
 ....

これで LispKit Lisp が自立します.コンパイルした Read-Compile-Execute-Print プログラムをファイルに書いて SECD 機械で実行すると,以下のように入力した式を評価できます.

$ ./secd rep.secd 
(letrec ((rev (lambda (x)
                (if (atom x)
                    (quote ())
                    (app (rev (cdr x))
                         (cons (car x) (quote ()))))))
         (app (lambda (x y)
                (if (atom x)
                    y
                    (app (rev (cdr (rev x)))
                         (cons (car (rev x)) y))))))
  (rev (quote (0 1 2 3 4 5 6 7))))
(7 6 5 4 3 2 1 0)

あとはいろいろ(?)追加・整備すれば Common Lisp や Scheme になるでしょう(^^).

2015/03/24
© 2013,2014,2015 PRINCIPIA Limited