2014/08/29

Lispの仕様書, リファレンスマニュアル

(LISP 1.5 PRIMER (BY (CLARK WEISSMAN)) (1967)
http://www.softwarepreservation.org/projects/LISP/book/Weismann_LISP1.5_Primer_1967.pdf

LISP 1.5 Programmer's Manual 2nd ed, 15th printing (1985)
http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf

Mac Lisp Reference Manual (1974.08.04)
http://www.softwarepreservation.org/projects/LISP/MIT/Moon-MACLISP_Reference_Manual-Apr_08_1974.pdf

Franz Lisp Manual (1983)

Lisp Machine Manual 6th ed (Zeta Lisp) (1984.06)
http://common-lisp.net/project/bknr/static/lmman/frontpage.html

Common Lisp HyperSpec
http://www.lispworks.com/documentation/HyperSpec/Front/index.htm

R5RS〜R7RS, SRFI
http://scheme-reports.org/

R4RS(Revised 4 Report on the Algorithmic Language Scheme) (1991)
http://people.csail.mit.edu/jaffer/r4rs_toc.html

R5RS(Revised 5 Report on the Algorithmic Language Scheme) (1998)
http://www.schemers.org/Documents/Standards/R5RS/

R6RS(Revised 6 Report on the Algorithmic Language Scheme) (2007)
http://www.r6rs.org/

R7RS(Revised 7 Report on the Algorithmic Language Scheme) (2013)
http://trac.sacrideo.us/wg/wiki/R7RSHomePage

その他, LispといえばEmacs Lisp, Clojure, Arcなど.

#'(function)とfuncall (Common Lisp)

 Lisp-1を使う私にとって, Common Lispの最大の謎は, funcallと#'です. Lisp-2の名前空間の仕組みさえわかってしまえば, あとはGauche(Scheme)とほとんど同じというのが, Common Lispへの私の勝手な印象です(間違っているかもしれませんが..).
 Schemeから入ると, この辺がよくわからなくなります.

 #'の正しい呼び方は, "function"です. #'は, その見た目のとおり, functionマクロのリーダマクロでした. functionは, レキシカルクロージャを生成するためのものみたいですね. (Common Lispにおけるlambdaのあれこれ(ありえるえりあ))
 しかし, 普通にlambdaと書くだけではクロージャを作らないのかというと, そういうわけでもないようです. 現代におけるCommon Lispのlambdaは, #'(lambda ...)を表すマクロなので, lambdaと書けば, #'(lambda ...)と書いたのと同じだということです. Common Lispで普段使われるlambdaは, 普通のクロージャになるのでしょうか.

 関数呼び出しの最左の式(要素?)は, ラムダ抽象か, 関数を束縛した変数である必要があります.

((lambda (x y z ...)) B C ...) ; => ○
((x y z ...) B C ...)          ; (x y z ...)がlambda式でない何か=> ×
(A B C ...)                    ; この時, Aは特殊形式 => ○
(A B C ...)                    ; 関数の名前空間にAの値(関数)が束縛されている => ○
(A B C ...)                    ; 関数の名前空間にAの値(関数)が束縛されていない => ×
 上記の○と×は, 文法的かつ変数の束縛している内容について考えた場合, 正しい記述か間違っているかという意味です. Schemeでは上から二番目の(x y z...)も問題ないのですが, Common LispではNG. Common Lispでは,  funcallは, この時(or こういった書き方をしたい時)に, 呼ばれる関数のようです. また, 最下段のケースでも, 変数の名前空間でのAに関数が束縛されている時も, funcallが使えます.

 これで, なぜfuncallをするのかという謎と, #'の使い所の謎が解けました. lambda抽象に対する#'は不要で, defunで定義した関数について, クロージャを作りたいときに, #'fなどと書けば良いことになります. funcallは, クロージャが渡された時, applyするために使うものとなります.

 funcallが必要になるのは, Lisp-2の名前空間が原因のようで, 例えば, (A B C ...)のような関数適用があった時に, 関数の名前空間におけるAが表す値(関数)と変数の名前空間におけるAが表す値(関数/クロージャを1stクラスオブジェクトとして扱えるため)を区別するためにあるようですね.

2014/08/23

Haskell風のリスト内包記法をClojureで

Clojureのリスト内包記法は, forですが, この記法は少し読みにくいように感じます.

例えば, Haskellなら
[(x, y) | x <- [1..10], y <- [2..11], odd (x * y)]
と書けるところをClojureは,
(for [x (range 1 11), y (range 2 12), :when (odd? (* x y))] [x y])
と書きます.

 どのあたりが気に入らないのかというと, 真っ先に目につくのが:whenです. Haskellは注釈なしに条件を付加しています. whenのような注釈は, Haskellに必要ありません.

 :when以外にも気に入らないところがあります. generatorです. Haskellは, 例のx<-[1..10]というかなり直感的な表記ですが, Clojureは, rangeと束縛する変数を併置するという書き方で, かなり形式張った印象があります. Clojureでも, x <- [(exp1)..(exp2)]のようにかければいいかなと思いました. 一番理想的なのは, e ∈ [1..10]ですが.

 このような注釈が必要になるのは, 動的型付け言語であるClojureでは仕方がないのかもしれないです. Haskellの場合, odd (x * y)の式は, 構文を読み込んだ後の型推論のフェーズで, 式がboolを返す式であることを認識します. 一方で, Clojureは, 構文を読んだ時点で任意の関数fが, 例えば, (f (* x y))と書かれているとして, それが条件を表すとは認識できない(というか, 決定できない)と思ったのですが...

Haskell Report 98のリスト内包記法 によれば, 次のように定義されます.
[e | True ]     = [e]
[e | q    ]     = [ e | q, True ]
[e | b, Q ]     = if b then [  e | Q ] else []
[e | p <- l, Q ]= let ok p = [  e | Q ]
                      ok _ = []
                      in concatMap ok l
[e | let decls, Q ] = let decls in [  e | Q ]
 Haskellの内包記法は, letとfilter, generatorが使えます. letは, リスト内包記法内で一時的に束縛される変数を定義する式です.<-で記述される式は, generatorと呼ばれます. generatorから生成された変数列にかけるのがfilterです. 3行目のbがfilterに相当します.

 Haskellのリスト内包記法の定義をよく見ると, 型注釈から, 式をフィルターの条件式かどうかを判定しているわけではなく, 構文的に条件式だと見ているようです. つまり, 処理系から見て, リスト内包記法の構文を読む時, :whenの注釈は必要ないのかもしれません.

 :whenは, 意味的に必要なのではなくて, 分かりやすさのために存在していると見た方がよさそうです.

 Clojureのリスト内包記法がこのような表記になっている原因は, この記法のイメージの根底にあるが, for-each構文だからでしょう. 構文の名前もforと書かれています. Pythonのリスト内包記法もforが使われていました. 一方で, Haskellの記法は, 数学で用いられる集合の内包的記法を忠実に文法に落とし込んだ印象があります.

 いずれにせよ, 上記のような特徴からClojureのリスト内包記法は直感的ではないと思いました.

 というわけで, Haskell風のリスト内包記法の構文をClojureでも使えるようにします. ここで重要なのは, すべてHaskell化するのではないということです. S式は残します. 例えば, こんな感じ.
[(x, y) | x <- (range 1 11), y <- (range 2 12), (odd? (* x y))] 
 S式でコードが書けないのは, 本末転倒です. 最初からHaskellを使えばいいだけなので.

 次のようなマクロを作りました.
user=> (lc [x | x <- (range 10), (odd? x)])
(1 3 5 7 9)
user=> (lc [[x,y] | x <- (range 10), (odd? x), let y = (* x 3)])
([1 3] [3 9] [5 15] [7 21] [9 27])
 lcはHaskell風の内包記法をとり, Clojureのforへ変換します. 表記が違うだけで, 機能的にはforそのものです.
 以下がソースコード. core.matchマクロを使っているので, 使用の際には, project.cljやleinのprofileにmatchマクロを追加する必要があります.

(use '[clojure.core.match :only (match)])

(defn throw-exception [message]
  #((throw (Exception. (str message %)))))

(defn malformed-let-in-lc [s-exp]
  ((throw-exception "malformed let in list comprehension : ") s-exp))

(defn malformed-generator-in-lc [s-exp]
  ((throw-exception "malformed generator in list comprehension : ") s-exp))

(defn malformed-lc [s-exp]
  ((throw-exception "malformed list comprehension : ") s-exp))

(defn lc-tail->for [tail-exps converted]
  (let [top (first tail-exps)]
    (cond
     (empty? tail-exps) converted
     ;; let
     (= top 'let)
      (match tail-exps
             ['let var-name '= exp & rest-of-tail]
             (lc-tail->for
              rest-of-tail
              (concat converted [:let [var-name exp]]))
             a (malformed-let-in-lc a))
     ;; generator
     (and (symbol? top) (= '<- (second tail-exps)))
      (match tail-exps
             [var-name '<- generator & rest-of-tail]
             (lc-tail->for
              rest-of-tail
              (concat converted [var-name generator]))
             a (malformed-generator-in-lc a))
     ;; filter
     (list? top)
      (lc-tail->for
       (vec (rest tail-exps))
       (concat converted [:when top]))
     :else
      (malformed-lc tail-exps))))

(defmacro lc [exp]
  (match exp
         [an-element '| & list-comprehension-tail]
         `(for ~(vec (lc-tail->for list-comprehension-tail []))
            ~an-element)
         a (malformed-lc a)))
 例えば, ラマヌジャン数も求まります. (以下のS式のexpは別途用意が必要)
user=> (lc [[left [x,y,z,w]] | x <- (range 1 20),
                               y <- (range 1 20),
                               z <- (range 1 20),
                               w <- (range 1 20),
                               let left = (+ (exp x 3) (exp y 3)),
                               let right = (+ (exp z 3) (exp w 3)),
                               (= left right) (not= x y) (not= y z)
                               (not= z w) (not= x z) (not= x w) (not= y w)])
([1729 [1 12 9 10]] [1729 [1 12 10 9]] [4104 [2 16 9 15]] [4104 [2 16 15 9]] [1729 [9 10 1 12]] [1729 [9 10 12 1]] [4104 [9 15 2 16]] [4104 [9 15 16 2]] [1729 [10 9 1 12]] [1729 [10 9 12 1]] [1729 [12 1 9 10]] [1729 [12 1 10 9]] [4104 [15 9 2 16]] [4104 [15 9 16 2]] [4104 [16 2 9 15]] [4104 [16 2 15 9]])

 元のClojureのforよりは見やすくなったと信じています. 特に空白を表すカンマが適当なところで, 区切りを明確に表現して丁度いい感じになりました. しかし, lcが邪魔ですね.

 リードマクロで#[x| ...]のように記述できれば理想的なのですが, Clojureにはリードマクロを自由に追加することはできません. (追記, 2014/10/06 :  Clojureのリーダマクロ 最近のversionでは追加されたようです.) Clojure本体のコードを弄ることで, リードマクロを拡張することはできるようなのですが, それは少しやりすぎな感じがします.

2014/08/18

syntax-rulesの書き方のコツのようなもの(Scheme)

 Scheme(R5RS)のマクロであるsyntax-rulesは, Lispの伝統的なマクロとは書き方や雰囲気も全く違います. 伝統的なマクロがないSchemeは, どこか言語として(Lispとして), 物足りない感じがしました.  しかし, そんな私も最近は, 折にふれて, ちょっとした作業でsyntax-rulesマクロを使うようにしたところ, Hygenicマクロへの抵抗感が薄れてきました. 使い慣れたついでの, Hygenicマクロの書き方のコツのようなもののメモです.

再帰的な関数の書き方

 どこで読んだのか覚えていないのですが, 関数型言語でプログラムを書くコツは,if(cond)式について, 特殊なケースから順に書いていくことだそうです.
 例えば,  フィボナッチ数を計算する関数は, 再帰呼び出しを用いて書く場合,
(define (fib n)
    ... ...
という形で最初に関数名と引数の数とその値の型について考えます. ここでは, nは整数(integer)です.
 次に, 特殊なケースについて, n = 0の時と, n = 1について考えます.
(define (fib n)
  (cond
    ((= n 0) 1)
    ((= n 1) 1)
    ... ...
それぞれ以上のように書けることは, 明らかです. 関数型言語を覚えたての頃は, 任意のnのケースについて考えるのが大変なのですが, フィボナッチ数はその性質から, fib(n - 1)とfib(n - 2)の和だということを考えると, 残りのプログラムが書けて, 
(define (fib n)
  (cond
    ((= n 0) 1)
    ((= n 1) 1)
    (else (fib (- n 1)) (fib (- n 2)))))
という感じで, プログラムを書いていきます.
 これだと, nに負の値を与えられた場合が問題になるので, throw-exceptionに継続をバインドして, 次のように書いてもいいかもしれません.
(define (fib n)
  (cond
    ((< 0 n) (throw-exception "wrong argument"))
    ((= n 0) 1)
    ((= n 1) 1)
    (else (fib (- n 1)) (fib (- n 2)))))
 これは, 普段プログラミングを行うときに自然にやっていることですが, 関数型言語風の書き方を始めたばかりの頃は, 再帰呼び出しでの書き方が分からず, 混乱した時に, このアドバイスに従い, 整理して, 書いていました. この方法論は, かなり(私には)有用で, 大抵のケースで, このアドバイスが応用できました.
 上記は数値の例ですが, 例えば, リスト処理や文字列の処理でも同じような考え方でコードを書いたのを覚えています.

syntax-rulesマクロの書き方

 この方法論は, syntax-rulesマクロを書くときにも応用できます. マクロの引数が1つ与えられている場合について考えるのです.
 次のようなフォームを反転させるマクロを実装してみます. 例えば, (1 2 3 4 5 6)が与えられるとそれを反転した(6 5 4 3 2 1)が, S式として展開されるようなマクロです. 実用性はさておき, syntax-rulesの柔軟性を調べるためには十分だと思います.
 実行結果は次のようになります.
gosh> (macro-list-reverse (1 2 3 4 5 6))
*** ERROR: invalid application: (6 5 4 3 2 1)
Stack Trace:
_______________________________________
gosh> (macro-list-reverse (1 2 3 4 5 +))
15
 これは, Schemeにおけるreverse関数をパターンマッチにより実装するのとさほど変わりません. ところで, 一般に, reverse関数は, cons関数と再帰呼び出しのために, 2つ引数をとります.  (reverse (1 2 3) ()) → (reverse (2 3) (1)) → (reverse (3) (2 1)) → (reverse () (3 2 1)) というふうに末尾再帰を繰り返すので, 2つの引数を想定します.
(define-syntax macro-list-reverse
  (syntax-rules ()
    ((_ () ())
     ... ...
 次に特殊なケースについて考えます. 1つ目の引数が空リストの場合です. 2つ目の引数には, 反転されたリストが入っているので, そのリストを返せばよく,
(define-syntax macro-list-reverse
  (syntax-rules ()
    ((_ () ())
     ())
    ((_ () (xs ...))
     (xs ...))
     ... ...
と書けます. (xs ...)は, 何らかのリストを意味しています. これがそのまま, 展開した結果として返されます.
最後に, 一般的なケースについて考えると, 左の先頭を右の先頭へ移す処理なので, (x xs ...)と分解して, 左の(ys ...)に(x ys ...)と加えて, 次のように書けます.
(define-syntax macro-list-reverse
  (syntax-rules ()
    ((_ () ())
     ())
    ((_ () (xs ...))
     (xs ...))
    ((_ (x) (xs ...))
     (x xs ...))
    ((_ (x xs ...) (ys ...))
     (macro-list-reverse (xs ...) (x ys ...)))))
 これで, 与えられた要素が反転するマクロができますが, 初期値の空リストが冗長なので, パターンマッチでそのケースについて追加します.
(define-syntax macro-list-reverse
  (syntax-rules ()
    ((_ (xs ...))
     (macro-list-reverse (xs ...) ()))
    ((_ () ())
     ())
    ((_ () (xs ...))
     (xs ...))
    ((_ (x) (xs ...))
     (x xs ...))
    ((_ (x xs ...) (ys ...))
     (macro-list-reverse (xs ...) (x ys ...)))))
 というわけで, 最初のmacro-list-reverseが完成します.

 パターンマッチが分岐の役割を果たし, 再帰的展開が普通の関数における再帰呼び出しに相当するため, Schemeにおける関数と遜色ない程度の計算力を持ったマクロがかけるようです.

2014/08/08

shift/reset(限定継続)をSchemeのメタ循環インタプリタに実装

 Schemeのメタ循環インタプリタに, shift/reset(限定継続)の機能を付け加えよう. という話です.
最初からすべてを実装するのは大変なので, 3つのversionを作ります.Schemeの処理系はGaucheを想定しています.
  • interp1 : 普通のSchemeで作成した(Schemeのsubsetを解釈する)メタ循環インタプリタ
  • interp2 : カリー化されたSchemeのメタ循環インタプリタ
  • interp3 : Abstrcting Control(論文)のSemanticsに基づいたインタプリタ

shift/resetの評価器

 次の一連の式は, shift/resetを実行可能な評価関数の定義です. 論文(Abstracting Control)のセクション1, Extended Continuation-Passing Styleの後半部分に登場する評価器(evaluator)です.
 一番先頭の行は, 評価器(インタプリタ)の型で, 式と環境, 継続とメタ継続(限定継続)を引数にとり, 計算結果を返すものです. 上から順に変数, 組み込み関数(オペレータ)の適用, 関数適用, ラムダ抽象, if(条件分岐), call/cc, shift, resetを表します.
 基本的に, ラムダ計算にcall/cc, shift/reset, ifと定数/プリミティブ関数を拡張したプログラムになります.

Eval :: Exp -> Env -> Cont -> MCont -> Ans
Eval[x]ρκγ      = κ (ρ[x]) γ
Eval[π E]ρκγ    = Eval[E] ρ (λνγ'. κ (π ν) γ') γ
Eval[E1 E2]ρκγ   = Eval[E1] ρ (λfγ'. Eval[E2] ρ (λaγ". f a κ γ") γ') γ
Eval[λx. E]ρκγ  = κ (λνκ'γ'. Eval[E] ρ[x := ν] κ' γ') γ
Eval[E1 → E2 | E3]ρκγ
                = Eval[E1] ρ (λbγ'. b → Eval[E2]ρκγ' | Eval[E3]ρκγ') γ
Eval[εk. E]ρκγ  = Eval[E] ρ[k := (λνκ'γ'. κ ν γ')] κ γ
Eval[ξk. E]ρκγ  = Eval[E] ρ[k := (λνκ'γ'. κ ν (λw. κ' w γ'))] (λxγ". γ" x) γ
Eval[{E}]ρκγ    = Eval[E] ρ (λxγ'. γ' x) (λν.κνγ)
 ρ[x] は, 環境ρから変数xに相当する値を返す処理を意味しています.
 E1→E2|E3は, Schemeにおける (if E1 E2 E3)を表します.
 ρ[x:=ν]は, 環境ρ中のxをνに置き換えることの表現です.

 Eval[x]ρκγ = ...は例えば, 評価関数が式x(変数)と, 環境ρ, 継続κ, メタ継続γを引数として受け取った時, 右側の式を返すという風に読みます.

 全体的に限定継続付きの継続渡しスタイルになっていて, ある評価ステップで計算しきれなかった計算(=残りの計算)は, 次以降のステップで継続として記述されます. 定数/変数項やラムダ抽象のステップでは, これ以上計算できないので, 継続にその式(定数やラムダ抽象など)を関数適用します. それ以外のステップは, 基本的に残りの計算を継続で表現して, 式(プログラム)の解釈を進めます.

 最終的な目標

 次のような実装を実現することです.
gosh> (interp3 '(reset (+ 1 (shift (c) (c 10)))))
11
gosh> (interp3 '(reset (+ 1 (shift (c) (c (c 10))))))
12
gosh> (interp3 '(reset (+ 1 (shift (c) 10))))
10
 一番目の実行では, 限定継続が1回実行されて11を返しますが, 二回目は, 2回実行されて12を返します. 最後の実行では, 残りの計算が切り捨てられて10を返しています.


interp1(メタ循環インタプリタの実装)

 interp1では, 簡単なラムダ抽象とその関数適用, ifによる分岐, プリミティブの演算の実行が可能な処理系を作成します.

 文法は以下のようなものを受け付けます.
exp := const | var | (exp exp ...) | (lambda (var ...) exp) | (if exp exp exp)

interp1の実装は次のようになります.

 環境(変数を表すシンボルとその値のペアからなるリスト)から変数名を探し, それに該当する値を返すのがlookup関数, extend*は, 環境を拡張する関数でインタプリタでは共に定番の補助関数となっています. initial-envは, プリミティブの演算(関数)が含まれている環境. eval1がインタプリタ. interp1は例外の機構を付け加えたインタプリタです(interp2以降では, もう少し複雑な使われ方をします).
 サンプルプログラムとして, 階乗を計算するプログラムとフィボナッチ数を計算するプログラムを作成しました. ループは不動点コンビネータで記述します.
 評価関数は, schemeのmatchマクロの都合上, 最初に(lambda, ifなどの)スペシャルフォームを持ってきて, 次に関数適用, 定数/変数といった順に並べる必要がありました.
 ラムダ抽象を評価した結果の値は, レキシカルクロージャ(ラムダ抽象と環境のペア)です.
 エラーが発生するポイントとしては, 探している変数が見つからないlookup関数(8行目), 間違った関数適用の形式(46行目), 想定されていないプログラムのフォーマット(54行目)などがあります. このようなケースでは, continuationを使って, 脱出します.

 実行結果は, こんな感じです.
gosh> (interp1 factorial-p)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
gosh> (interp1 fib-p)
144
gosh> (interp1 '((lambda (x y) (+ x (* y y))) 7 12))
151

interp2(カリー化)

 基本的に動作(計算結果, 機能など)については, interp1とほぼ同じですが, 内部的に式をカリー化したインタプリタを作成します. interp2では, プログラムとなる式を受け取ると, 内部的にカリー化して, カリー化された式を受け付けるインタプリタによりプログラムを計算します.
 また, これに伴い, プリミティブの関数もカリー化します.
 カリー化が必要なのは, 冒頭の説明にあるshift/resetの評価器がカリー化されたλ式をターゲットプログラムとしているからです.

 interp2の動作とinterp1の動作の違いは, 例えば, 次のプログラムを解釈できるか否かだと言えます.

gosh> (interp2 '((lambda (x) (x 2)) (+ 4)))
6
gosh> (interp1 '((lambda (x) (x 2)) (+ 4)))
4"# error :: malformed lambda"

 interp1では, +関数のカリー化に失敗しています(ラムダ抽象で包み込む必要があります)が, interp2では, その必要がありません (Haskell likeなスタイルになっているようにも見えます).

interp2の実装は以下のとおり.

 実行結果は,前述のケース以外では, interp1と同じです.
 プリミティブ関数をカリー化するcurryマクロとそれに関連するcurry*, curry-primitives-2などのマクロが登場しています. これは, プリミティブの関数fを, (lambda (x) (lambda (y) (f x y)))と書き直すことで, カリー化するマクロです. カリー化されたことで, eval2インタプリタでは, 関数適用が必ず関数と引数のペアになりました(今までは, 関数と引数の割合は一対多でした).
 curry-s-expは, 普通のS式を引数にとって, カリー化されたS式を返します.


interp3(素朴なshift/resetの実装)

 interp2まで完成すると, いよいよ, shift/resetが実装できるようになります. shift/resetの評価器は, 継続渡しスタイルで記述されます.
 この素朴な実装のメリットは, 上記の評価器をそのまま書けば, shift/resetの実装として正しく動いてくれるところです. ただし, matchマクロにあうように, スペシャルフォームから順に実装する必要があります.

ターゲット言語の文法は, 機能を追加したので, 次のようになります.
exp := const | var | (exp exp ...) | (lambda (var ...) exp) | (if exp exp exp)
             | (call/cc (var) exp) | (shift (var) exp) | (reset exp)

interp3の実装はこのようになります.


 normal2->cps2は, 2引数をとるプリミティブの関数を限定継続付きの継続渡しスタイルへ変換するマクロです. add-transform-cps-2で, その処理をすべてのプリミティブ関数に実行します.
 eval3では, インタプリタ上の例外処理をきれいに扱うため, factory関数を作り, eval3をその関数が生成するクロージャとすることで, 評価器の定義をそのまま記述できるようにしました. 基本的に書き方は, 冒頭で書いた定義と(順番が違う以外は, )ほぼ同じです.
 カリー化するプログラム(curry-s-exp)も, 文法の拡張部分について, 修正をほどこします.
 eval3へ最初に渡す継続は, (λx m. x)で, xに式全体の計算結果が渡されるので, それを返すようにします.
 サンプルプログラムとして, factorial-pでcall/ccとshift/resetを使ったものを作成しました.

 interp3の実行結果は次のようになるはずです.
gosh> (interp3 normal-p)
3628801
gosh> (interp3 shift-exception-p)
101
gosh> (interp3 call/cc-exception-p)
"call/cc exception"
 normal-pでは, 例外を返さない範囲内の引数が与えられたので, 普通にfactorialを計算します. shift-exception-pでは, factorial関数に50より上の値が渡されたので限定継続を使って, resetの外側へ脱出しています. 負の値を渡した場合は, 継続によってcall/ccの外へジャンプします.

 紛らわしいのですが, call/ccは, 継続を束縛した変数cを呼び出すことで例外のように式の外側へジャンプしますが, shift/resetは, 限定継続を束縛した変数cを呼び出さないことで式(reset)の外側へ脱出します.

 以上で, メタ循環インタプリタに限定継続(と継続)の機能を実装することができるようになりました.

 この投稿では, 素朴な(お試しの)実装について書きましたが, 本格的な言語に実用的な実装するには, Stackなどによる実装にする必要があります(遅いです).