読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

Lisp-1でlambdaを使ったlet, let*, 関数内関数定義の実装メモ

SchemeみたいなレキシカルスコープのLisp-1処理系を作るときの話です。

lambda(Lexical Closure)とset!を実装できれば、マクロ又は処理系に変形させることでlet, named-let, let*, 関数内関数定義を実装することができます。

let

let式は、lambdaの即適用に単純に書き換えることができます。

(let ((a 1) (b 2))
  (+ a b))
((lambda (a b) (+ a b))  1 2)

ちなみにletのローカル変数定義(上記だと((a 1) (b 2)))からmap carで変数名、map cadrで値が集まります。

let*

次のようなlet*式について考えます

(let* ((a 123) (b a))  b)

この式は(bを経由して)aの値123を返すことを期待します。しかしこれを上記letのように変形してしまうと

((lambda (a b) b) 123 a)

lambdaの引数(123 a)のうち、aが参照しているのは目的のaではありません。まだ定義されていないか、外側の環境で定義されているかです。

これはlambdaの入れ子に変形することで解決できます。ローカル変数定義の順番で、前が外、後が内の入れ子です。

((lambda (a)
  ((lambda (b) b) a))
 123)

関数内関数定義

次のような関数について考えます

(define (foo)
  (define (a) (b))
  (define (b) (a))
  (a))

Schemeのように

  1. a, bの定義は関数fooの中のみで有効
  2. a, bは無限に相互再帰する

であってほしいとします。

1から、ローカル変数aとして(lambda () (b))を、bとして(lambda () (a))を定義すべきです。

しかし、letでもlet*でもうまくいきません。

まずletですが、a, b両方とも、お互いを指すことができません。次のように変形されるからです。

((lambda (a b) (a))  (lambda () (b))  (lambda () (a)))

a内のb、b内のaはどちらも未定義か外の環境のものを指します。

またlet*では、bはaを指せますがaはbを指せません。次のように変形されるからです。

((lambda (a)
   ((lambda (b) (a)) (lambda () (a))))
 (lambda () (b)))

少しわかりづらいですが、ローカル関数bの定義(2行目)ではうまくaを参照できています。しかしローカル関数aの定義(3行目)では未定義か外の環境のものを参照してしまっています。

解決策は、一度適当な値で初期化してから、改めてset!します。

この例の場合は次のように変形します。

((lambda (a b)
   (set! a (lambda () (b)))
   (set! b (lambda () (a)))
   (a)
   ) '() '())

まずa, bを'()で初期化し、それから両方が参照できるlambda本体で改めてset!しています。こうすることで相互再帰が可能になります。

ただし、このやり方でうまくいくのは関数の相互適用で、値の相互参照はまずいことになる可能性もあります。次の式を上記のように変形してみてください。

(define (foo)
  (define a b)
  (define b 123)
  a)

(foo)が返すのはbの123ではなく、'()です。

この問題を解決する方法もあるかもしれません(参考:Scheme:内部defineの評価順)が、かなりややこしそうです。関数内では関数以外のdefineを禁止したほうが良いかもしれません。

ちなみにletrecはこの考え方です。

雑感

相変わらず、何度目かのLisp-1処理系を書いています。

それでlet, let*, 関数内関数定義を書いていたんですが、初めて実装したときにletやletrecを何故分ける必要が、とちょっと混乱したのを思い出したので整理してみました。

広告を非表示にする