scheme処理系を実装中です。

Kobe University Advent Calendar 2016の22日目の記事です。
そして私はB3のniyarinです。


本編に関係ないネタ

本編が少し雑なので、xmas treeを出力するスクリプトをてきとーにschemeで書きました

(define decorate #f)
(let ((pos-seed 1)
      (shape-seed 1))
  (set! decorate
    (lambda (leaves)
      (for-each 
        (lambda (_) 
          (set! pos-seed (modulo (+ (* pos-seed 3) 7) 26))
          (set! shape-seed (modulo (+ shape-seed 1) 3))
          (if (< pos-seed (string-length leaves))
            (string-set! leaves pos-seed
                         (list-ref '(#\@ #\? #\$) shape-seed)))) 
        (make-list 3))
      leaves)))


(define tree-data 
    (let loop1 ((width '( 0 2 6 10 ))(updates '(1 1 2 2 ) ))
      (if (null? width) 
        '()
        (append 
          (let loop2 ((w (min 1 (car width))))
            (if (> w (car width))
              '()
              (cons 
                (string-append
                  (substring "                             " 0 (- 13 w))
                  (decorate (substring "*********************" 0 (+ (* w 2) 1))))
                (loop2 (+ w (car updates) )))))
          (loop1 (cdr width)(cdr updates))))))

(define tree-pot
  (let ((space "          ")
        (edge  "|     |")
        (bottom "-------"))
    (append
      (map (lambda (_)
             (string-append space edge))
           (make-list 2 ))
      (list (string-append space bottom)))))


(for-each 
  (lambda (x) (display x)(newline))
  (append tree-data tree-pot))


結果

             *
            *?*
           *****
            *?*
          *******
        *?*********
            ***
          *?*****
        **********$
      *?*************
    **********$@**?****
          |     |
          |     |
          -------

ネタおしまい。

scheme処理系を実装している話

・未完成です。
・上のxmas tree scriptも動きません
ページ
今回は、中でどんな処理をしているのか雑に説明します。

処理系の概要

・r7rsを目指す。
JavaScriptで実装。
VM

終わったこと

・末尾呼び出し最適化
・末尾呼び出しでなくても最適化する
・syntax-rules
・第一級継続
・dynamic-wind
・多値

コンパイル手順

α変換&マクロ展開&syntax展開 → cps conversion → closure conversion & lambda lifting →VMコード生成

α変換

名前の衝突は後の処理で厄介になりそうなのでリネームします。

(lambda (a)(lambda (a) (+ a 1))) -> (lambda (a) (lambda (a_2) (+ a_2 1)))

cps conversion

継続を陽に表すようなコードに変換します。
私の処理系では、これを第一級継続、末尾呼び出し最適化に使用しているので割と大事な処理だったりします。

(+ (+ a b)(+ c d))
->
  (+ a b (lambda (r1) 
           (+ c d (lambda (r2) (+ r1 r2 ret)))))


closure conversionとlambda lifting

自由変数を削除する変換です

lambda liftingはlambda式のparameterを拡張する変換です

(let ((a 1))
  ((lambda (b c) (+ a b c )) 2 3))
->
(let ((a 1))
  ((lambda (b c a)(+ a b c )) 2 3 a ))


closure conversionは、closureを手続きと自由変数の値のペアで表現するという変換です。

末尾呼び出し最適化

すべての手続き呼び出しで、call stackを必要としないコードに変換することで実現しました。
具体的には、cps conversionで戻りアドレスを不要にして、 closure conversionで外の自由変数を削除するという方針です。

おしまい