処理系間で共通にできるeval APIのサブセット

小ネタ。処理系毎にevalやそれに与えられる環境の機能性が微妙に違うので共通APIを考える会。

eval APIの移植性

LispSchemeと言えばeval。JavaScriptや他の言語でもAPIとして存在するが、Lispではその場でS式を組み立てて使えるのでそれなりに利便性が高い。ただ、意外と移植性が低く、

  • R6RS / R7RS標準には環境を操作する手続きが無い 。多くのSchemeでは eval 手続きに与える環境をfirst class objectとして扱い、それなりの数の操作APIを用意していることが多いが、これらが標準に含まれない。このため、任意のバインディングを環境に取り込むためには、事前にライブラリにしておく必要がある。
  • そもそも環境を指定できない処理系がある 。Gambit等。

独自の環境操作手続きとしては、例えば Chez Schemeset-top-level-value! が有り、yuniではGuile( module-define! https://github.com/okuoku/yuni/blob/96fa6edd7c0b2b6c97597c60ccf1a3314b73ace1/lib-runtime/selfboot/guile/selfboot-entry.sps#L142 ) やRacket( namespace-set-variable-value! https://github.com/okuoku/yuni/blob/96fa6edd7c0b2b6c97597c60ccf1a3314b73ace1/lib-runtime/selfboot/racket/selfboot-entry.rkt#L212 )で同じAPIを実装している。

更に、これらの手続きはマクロも操作できることが多い。例えば、MIT/GNU Schemeには environment-define-macro があり、任意の環境に対してマクロを導入できる。

... 大抵の処理系でこれらの環境操作手続きが使えるならyuniで互換層を提供しても良いかもしれないが、Gambitのように、そもそも eval が環境を取らない処理系ではどうしようもないため最大公約数を探す方向とした。

(eval expr [env]) procedure

The first parameter is a datum representing an expression. The eval procedure evaluates this expression in the global interaction environment and returns the result. If present, the second parameter is ignored (it is provided for compatibility with R5RS).

環境を取らないevalで環境をエミュレートする

実はすっごく難しく考えていて、これ実装できないんじゃないかと思っていたが、実は超簡単だった。 普通に環境を let に見立て、これを lambda に変換すれば良い。

よくある even? odd? の例を考えると、

(define (odd? i)
  (if (= i 0)
    #f
    (even? (- i 1))))

(define (even? i)
  (if (= i 0)
    #t
    (odd? (- i 1))))

eval して、できた手続き odd?even? を取り出したいとする。例えば、R7RSでは (scheme repl) ライブラリに interaction-environment 環境が規定されているのでそれを使って、

(import (scheme base)
        (scheme write)
        (scheme eval)
        (scheme repl))

(define env (interaction-environment)) ;; envはREPL環境を指す

;; REPL環境を破壊的に更新する
(eval '(begin
         (define (xodd? i)
          (if (= i 0)
            #f
            (xeven? (- i 1))))
         (define (xeven? i)
           (if (= i 0)
             #t
             (xodd? (- i 1)))))
      env) 

;; 更新したREPL環境からxeven?とxodd?を取り出して使う
(let ((xeven? (eval 'xeven? env))
      (xodd? (eval 'xodd? env)))
  (display (list (xeven? 2) (xodd? 2))) (newline))

と書ける。しかし、 eval の引数に環境を取らないSchemeではこの方法は取れない( eval 間で環境が共有される保証が無いため)。代わりに、大抵のSchemeには define シーケンスと同等の効果を持つ letrec* 構文があるため、これに変換して、

;; このevalは作られた odd? even? の手続きを返す
(eval '(letrec* ((odd? (lambda (i) (if (= i 0)
                                     #f
                                     (even? (- i 1)))))
                 (even? (lambda (i) (if (= i 0)
                                      #t
                                      (odd? (- i 1))))))
         (list odd? even?)))

のようにできる。つまり、 letrec* で束縛したものを、リストかベクタに纏めて、そのオブジェクトを受け取れば良い。

この定義された odd?even? を使った式を eval したいときは、単に lambda に変換して、 eval からは一旦クロージャを受け取ることで実装できる。

(let ((proc (eval (lambda (odd? even?) ;; odd? と even? を束縛するためのクロージャを返す
                    ;; ココの内容は上の例と同じ
                    (display (list (even? 2) (odd? 2))) (newline)))))
  ;; 実際に呼び出す
  (proc xodd? xeven?))

この方法は環境に構文を導入することはできない という欠点は有るものの、環境を取らないevalで環境を取るevalと同様に手続きの定義や使用を行うことができる。

APIの実装

今回、この制約に従う evallighteval と呼ぶことにしてyuniのライブラリに導入した。lightevalはyuniがサポートしている処理系全てについて、環境付きのevalをエミュレートするためのツールを提供する。

eval プリミティブ

yuniでは、基盤となるScheme語彙として (yuni scheme) をライブラリとして定義している。ライブラリとしては この環境のみを eval の環境として保証し 、唯一の移植性のある eval 手続きとして提供する。R6RS/R7RSでは、このevalは以下のように定義できる:

(define (eval/yuni frm)
  (eval frm (environment '(yuni scheme))))

Gambitのように eval が環境を取らない処理系では、単に (define eval/yuni eval) し、実行環境に (yuni scheme) の語彙が揃っていることは別の手段で保証する。

この eval/yuni が唯一の移植性プリミティブとなる。(lightevalライブラリ自体は環境の表現にハッシュテーブルを使用するため、ハッシュテーブルも実装されている必要があるが。。)

環境オブジェクトとadd-globals!

環境オブジェクトとしてはハッシュテーブルを直接使用する。というわけで、 make-symbol-hashtable したものがそのまま環境オブジェクトとして使用される。

add-globals! は環境にグローバル変数define するための手続きで、シンボル名と eval したいコードの連想リストを受けとり、その内容を letrec* に開いた上で eval/yuni して結果を環境に格納する。

(define (lighteval-env-add-globals! env alist)
  (let ((names (map car alist))
        (code (map (lambda (p)
                     (let ((name (car p))
                           (obj (cdr p)))
                       (list name obj)))
                   alist)))
    ;; lighteval-bind(後述) 手続きが、環境の内容を展開した上でeval/yuniを行う
    (let ((out (lighteval-bind env `(letrec* ,code (list ,@names)))))
      (for-each (lambda (name obj)
                  (lighteval-env-set! env name obj))
                names
                out))))

bind

環境内のシンボルを使用したコードをevalするには、bind手続きを使う。bind手続きは、環境を lambda に開いて eval/yuni し、更にevalが返したクロージャapply した結果を返す。

(define (lighteval-bind env frm)
  (let-values (((k v) (hashtable-entries env)))
              (let* ((names (vector->list k))
                     (objs (vector->list v))
                     (proc (eval/yuni `(lambda ,names ,frm))))
                (apply proc objs))))

... 名前が良くない気がする。

何の役に立つのか?

lightevalでは、全ての変数定義を明示的な add-globals! 手続き、または、環境を表現するハッシュテーブルのアクセスを通して行う必要がある。このような eval が何故必要かというと、 define-macro のexpanderをyuni上に実現するために必要になる。。

s7やBiwaSchemeのようなdefine-macroを使用した処理系で、パフォーマンスのため事前にマクロを展開した状態でyuniライブラリを提供したいという気持ちがある。この展開処理自体もyuniのプログラムとして書いてしまいたい。

yuniにはScheme-on-Schemeに実装されたVMがライブラリとして有る( https://mjt.hatenadiary.com/entry/20170525/p1 )ので、それを使えば eval をエミュレートすること自体は可能だが、それだとあんまりなので互換性を考慮した eval ラッパーAPIを用意し、処理系を生かす形でexpanderを実装したかった。

他の応用としてはREPLの実装が考えられるが、実用的なREPLを実装するためには例外の処理もどうにかポータブルに記述できるようにする必要があり、なかなか難易度が高い。