A micro-manual for LISP Implemented in Groovy
元ネタは Nurullah Akkaya 氏の A micro-manual for LISP Implemented in C
その元ネタは Lisp の始祖である John McCarthy 氏の A micro-manual for LISP - not the whole truth*1
LISP による実装は 50 行ぐらい、C による実装は 380行ぐらいある。
この差は言語によるもの以外に LISP の実装は EVAL 関数だけを定義しているが C の実装は入出力まで実装しているため。
他の言語でも実装されていて Scala では Suzuki Hisao 氏の http://www.oki-osk.jp/esc/scala-lisp/ を見つけた。
本家の LISP 版のように EVAL のみ実装し、以下のテストが通るところを目指す*2。
import static Lisp.* lisp { shell -> assert A == shell << [QUOTE, A] assert [A, B, C] == shell << [QUOTE, [A, B, C]] assert A == shell << [CAR, [QUOTE, [A, B, C]]] assert [B, C] == shell << [CDR, [QUOTE, [A, B, C]]] assert [A, B, C] == shell << [CONS, [QUOTE, A], [QUOTE, [B, C]]] assert true == shell << [EQUAL, [CAR, [QUOTE, [A, B]]], [QUOTE, A]] assert [] == shell << [EQUAL, [CDR, [CDR, [QUOTE, [A, B]]]], [QUOTE, A]] assert true == shell << [ATOM, [QUOTE, A]] assert B == shell << [COND, [[ATOM, [QUOTE, A]], [QUOTE, B]], [[QUOTE, T], [QUOTE, C]]] assert [A, D] == shell << [[LAMBDA, [X, Y], [CONS, [CAR, X], Y]], [QUOTE, [A, B]], [CDR, [QUOTE, [C, D]]]] assert true == shell << [LABEL, FF, [LAMBDA, [X, Y], [CONS, [CAR, X], Y]]] assert [A, D] == shell << [FF, [QUOTE, [A, B]], [CDR, [QUOTE, [C, D]]]] assert true == shell << [LABEL, XX, [QUOTE, [A, B]]] assert A == shell << [CAR, XX] }
REPL を実装しないのは Groovy で引用符なしで実現する方法を思いついたため。
A とか QUOTE など存在しないものはプロパティではと判定されることを利用してみた。
XXXBuilder は同じように invokeMethod を利用しているがそれのプロパティバージョン。
groovy:000> A ERROR groovy.lang.MissingPropertyException: No such property: A for class: groovysh_evaluate at groovysh_evaluate.run (groovysh_evaluate:2) ...
ドキュメントの最初に S式の説明がある。
空でないリストがリストでそれ以外はアトムである ということらしい。
この辺りは Scheme *3 と違っている*4のでややこしいのだが、Groovy も Java も知らない人にとっては == は同値比較なのか同一比較なのか混乱するだろうと思えばお互い様かもしれない。
ちなみに Groovy は昔は === で同一比較を行っていたらしい*5。
試してみると is 使えといわれた。Groovy はたまに例外でアドバイスしてくれるけどこのあたりはどうなっているのだろう*6。
groovy:000> 1 === 1 ERROR org.codehaus.groovy.control.MultipleCompilationErrorsException: startup failed: groovysh_evaluate: 2: Operators === and !== are not supported. Use this.is(that) instead @ line 2, column 1. 1 === 1 ^
以下、実装
class Lisp { static shell() { new Shell() } static def lisp(Closure block) { lisp(shell(), block) } static def lisp(Shell shell, Closure block) { block.resolveStrategy = Closure.DELEGATE_ONLY block.delegate = new GroovyObjectSupport() { def getProperty(String name) { name } } block(shell) } static class Shell { def env = [:].withDefault { it } def leftShift(sexp) { println sexp eval(sexp, env) } def isList(sexp) { sexp in List && sexp != [] } def isAtom(sexp) { !isList(sexp) } def eval(sexp, Map env) { if (isAtom(sexp)) { env[sexp] } else if (isAtom(sexp.head())) { def (name, arg1, arg2) = sexp if (name == "QUOTE") arg1 else if (name == "CAR") eval(arg1, env).head() else if (name == "CDR") eval(arg1, env).tail() else if (name == "CONS") [eval(arg1, env), *eval(arg2, env)] else if (name == "EQUAL") eval(arg1, env) == eval(arg2, env) ?: [] else if (name == "ATOM") eval(arg1, env).with { it == [] || !(it in List) } ?: [] else if (name == "COND") sexp.tail().find { eval(it.head() ,env) == true }.with { eval(it.tail().head(), env) } else if (name == "LABEL") { if (arg2.head() == "LAMBDA") env[arg1] = arg2 else env[arg1] = eval(arg2, env) true } else { def value = [env[name], *sexp.tail()] if (isList(value) && isList(value.head()) && value.head().head() == "LAMBDA") eval(value, env) else value.collect { eval(it, env) } } } else if (sexp.head().head() == "LAMBDA") { def (_, params, body) = sexp.head() def evlis = sexp.tail().collect { eval(it, env) } eval(body, env + [params, evlis].transpose()*.asType(MapEntry)) } } } }
env を Map に変えたり、LABEL のあたりが本家と違う気がするが大体同じだと思う。
getProperty で捕捉できるのはプロパティと判断されるものだけなので例えば以下のものは捕捉できない。
