Blog

2015.12.5

Scala初心者の新卒が頑張ってLispを作ってみた

この記事はCyberAgentエンジニアAdvent Calendar5日目の記事です。

こんにちは! サイバーエジェントアドテクスタジオ新卒の志村です!!
7月にScala初心者のままScalaを採用しているAMoAdに配属されたのでScala歴5ヶ月くらいです。
Scala歴5ヶ月くらいだと初級者になるのかもしれませんがScalaばかり書いてる訳ではないのでまだScalaは全然書けません。
簡単な言語くらいしか書かないのでScalaが複雑すぎて全然覚えられません(´・ω:;.:…

ということでアドベントカレンダーにかこつけてScalaの勉強をしたいと思います！

学んでいくにはやはり手を動かすのが一番なんですかね (@@;?
何か作ってみます。何を作るのが良いんでしょう。Scalaといえば…チューリング完全(?)な言語らしいですね。
チューリング完全といえばリスプですよね。リスプを作ってみたいと思いますo(((^^)))o

今回作るリスプを何のひねりもなくscalalispと呼ぶことにします。

AST

まずはASTを作ってみます。ASTは代数的データ型で作るのが一番ですね。Scalaで代数的データ型を作るには

  sealed trait ast

1	sealed trait ast

で始めるらしいです。 sealedは同一ファイルから以外の継承を禁止する修飾子らしいです。

そこからASTのデータ型を定義していきます。文字列があると面倒そうなので nil, t, コンスセル、自然数、シンボルくらいでいいですかね。試行錯誤してみたらこうなりました

package scalalisp

object Ast {
  sealed trait Ast
  final case class LNil() extends Ast
  final case class LT() extends Ast
  final case class LCons(car: Ast, cdr: Ast) extends Ast
  final case class LInt(i: Int) extends Ast
  final case class LSymbol(s: String) extends Ast
}

package scalalisp

object Ast {

sealed trait Ast

final case class LNil() extends Ast

final case class LT() extends Ast

final case class LCons(car: Ast, cdr: Ast) extends Ast

final case class LInt(i: Int) extends Ast

final case class LSymbol(s: String) extends Ast

}

あんまりMLの代数的データ型に似てませんがこれでちゃんと定義出来てるらしいです。不思議…

case classは classを便利にしたやつらしい(?)です。MLのレコードみたく扱えるみたいですね。

パーサ

ところでparserの読みは「パーザ」がイギリス読み、「パーサ」がアメリカ読みですよ（ドヤァ）

リスプの文法は簡単なので手書きでもいいのですがパーサコンビネータが標準ライブラリにあるらしいので折角ですし使ってみます(^o^)。

正式な記法をよく分かってないのですが、 "org.scala-lang.modules" %% "scala-parser-combinators" % "1.0.4"を使います。

package scalalisp

import util.parsing.combinator._

package scalalisp

import util.parsing.combinator._

から始まります。ワイルドカードインポートが邪悪ですがScalaだとよくやるんですか(・_・)？

ちょっとずつ定義していきます。まず簡単そうな nilと tから。

lazy val lnil = "nil" ^^ {_ => Ast.LNil()}
lazy val lt = "t" ^^ {_ => Ast.LT()}

1 2	lazy val lnil = "nil" ^^ {_ => Ast.LNil()} lazy val lt = "t" ^^ {_ => Ast.LT()}

簡単でした。まゆげみたいなので変換関数を指定しますo(^^)o。次は自然数とシンボルです。

  lazy val lint = """\d+""".r ^^ {n => Ast.LInt(n.toInt)}
  lazy val lsymbol = """[^\s()'0-9]+""".r ^^ {s => Ast.LSymbol(s)}

1 2	lazy val lint = """\d+""".r ^^ {n => Ast.LInt(n.toInt)} lazy val lsymbol = """[^\s()'0-9]+""".r ^^ {s => Ast.LSymbol(s)}

正規表現も簡単に使えるんですね。

リスト、シンボル、そしてクォートは相互に再帰するのでまとめて書いちゃいますね。

  lazy val expr  =  lnil | lt | llist | lint | lsymbol | lquote 
  lazy val llist:Parser[Ast.Ast] = "(" ~> rep(expr) <~ ")" ^^ {
    l => l.foldRight(Ast.LNil():Ast.Ast) ((e, acc)=> Ast.LCons(e, acc))
  }
  lazy val lquote: Parser[Ast.Ast] = "'" ~> expr ^^ {
    e => Ast.LCons(Ast.LSymbol("quote"), Ast.LCons(e, Ast.LNil()))
  }

lazy val llist:Parser[Ast.Ast] = "(" ~> rep(expr) <~ ")" ^^ {

l => l.foldRight(Ast.LNil():Ast.Ast) ((e, acc)=> Ast.LCons(e, acc))

}

lazy val lquote: Parser[Ast.Ast] = "'" ~> expr ^^ {

e => Ast.LCons(Ast.LSymbol("quote"), Ast.LCons(e, Ast.LNil()))

}

再帰するパーサには型を書かないといけないってScalaさんに怒られました(>_<)。
パースした結果は Parser型になるんですね。

ということでparser.scalaはこうなりました。

package scalalisp

import util.parsing.combinator._

object Parser extends RegexParsers {

  lazy val expr  =  lnil | lt | llist | lint | lsymbol | lquote 
  lazy val llist:Parser[Ast.Ast] = "(" ~> rep(expr) <~ ")" ^^ {
    l => l.foldRight(Ast.LNil():Ast.Ast) ((e, acc)=> Ast.LCons(e, acc))
  }
  lazy val lnil = "nil" ^^ {_ => Ast.LNil()}
  lazy val lt = "t" ^^ {_ => Ast.LT()}
  lazy val lint = """\d+""".r ^^ {
    n => Ast.LInt(n.toInt)}
  lazy val lsymbol = """[^\s()'0-9]+""".r ^^ {s => Ast.LSymbol(s.mkString)}

  lazy val lquote: Parser[Ast.Ast] = "'" ~> expr ^^ {
    e => Ast.LCons(Ast.LSymbol("quote"), Ast.LCons(e, Ast.LNil()))
  }
}

package scalalisp

import util.parsing.combinator._

object Parser extends RegexParsers {

lazy val llist:Parser[Ast.Ast] = "(" ~> rep(expr) <~ ")" ^^ {

l => l.foldRight(Ast.LNil():Ast.Ast) ((e, acc)=> Ast.LCons(e, acc))

}

lazy val lnil = "nil" ^^ {_ => Ast.LNil()}

lazy val lt = "t" ^^ {_ => Ast.LT()}

lazy val lint = """\d+""".r ^^ {

n => Ast.LInt(n.toInt)}

lazy val lsymbol = """[^\s()'0-9]+""".r ^^ {s => Ast.LSymbol(s.mkString)}

lazy val lquote: Parser[Ast.Ast] = "'" ~> expr ^^ {

e => Ast.LCons(Ast.LSymbol("quote"), Ast.LCons(e, Ast.LNil()))

}

これだけでリスプのパーサが書けるなんでScalaすごいですね。

ちょっと遊んでみます

scala> Parser.parseAll(Parser.expr, "1")
res2: scalalisp.Parser.ParseResult[scalalisp.Ast.Ast] = [1.2] parsed: LInt(1)

scala> Parser.parseAll(Parser.expr, "1").get
res3: scalalisp.Ast.Ast = LInt(1)

scala> Parser.parseAll(Parser.expr, "(1 2 3)").get
res4: scalalisp.Ast.Ast = LCons(LInt(1),LCons(LInt(2),LCons(LInt(3),LNil())))

scala> Parser.parseAll(Parser.expr, "(+ - +)").get
res5: scalalisp.Ast.Ast = LCons(LSymbol(+),LCons(LSymbol(-),LCons(LSymbol(+),LNil())))

scala> Parser.parseAll(Parser.expr, "'+").get
res6: scalalisp.Ast.Ast = LCons(LSymbol(quote),LCons(LSymbol(+),LNil()))

scala> Parser.parseAll(Parser.expr, "()").get
res7: scalalisp.Ast.Ast = LNil()

scala> Parser.parseAll(Parser.expr, "t").get
res8: scalalisp.Ast.Ast = LT()

scala> Parser.parseAll(Parser.expr, "nil").get
res9: scalalisp.Ast.Ast = LNil()

scala> Parser.parseAll(Parser.expr, "1")

res2: scalalisp.Parser.ParseResult[scalalisp.Ast.Ast] = [1.2] parsed: LInt(1)

scala> Parser.parseAll(Parser.expr, "1").get

res3: scalalisp.Ast.Ast = LInt(1)

scala> Parser.parseAll(Parser.expr, "(1 2 3)").get

res4: scalalisp.Ast.Ast = LCons(LInt(1),LCons(LInt(2),LCons(LInt(3),LNil())))

scala> Parser.parseAll(Parser.expr, "(+ - +)").get

res5: scalalisp.Ast.Ast = LCons(LSymbol(+),LCons(LSymbol(-),LCons(LSymbol(+),LNil())))

scala> Parser.parseAll(Parser.expr, "'+").get

res6: scalalisp.Ast.Ast = LCons(LSymbol(quote),LCons(LSymbol(+),LNil()))

scala> Parser.parseAll(Parser.expr, "()").get

res7: scalalisp.Ast.Ast = LNil()

scala> Parser.parseAll(Parser.expr, "t").get

res8: scalalisp.Ast.Ast = LT()

scala> Parser.parseAll(Parser.expr, "nil").get

res9: scalalisp.Ast.Ast = LNil()

ちゃんと動いてるみたいですね。地味に ()も LNil()になってくれてます。foldRightの基底条件ですね〜♪

内部表現

さっきまではASTでした。今度は実行時の表現を作りたいと思います。

さっきと同じように sealed traitから始めます。

sealed trait Expr

1	sealed trait Expr

どんどん定義していきます

sealed trait Nil extends Expr
sealed trait T_ extends Expr

1 2	sealed trait Nil extends Expr sealed trait T_ extends Expr

コンスセルはこうなるらしいです。

sealed trait ConsCell[+H <: Expr, +T <: Expr] extends Expr

1	sealed trait ConsCell[+H <: Expr, +T <: Expr] extends Expr

Hと Tの前に付いてる +は「いい感じにサブタイプ関係を推し量ってくれる」記号らしいです。すみませんよくわかってません><勉強不足ですみません((>_<))。
でも Cons[Nil, Nil]とかはM式に似てて親しみが持てますね。

次は自然数ですね

sealed trait Zero extends Expr
sealed trait Succ[N <: Expr] extends Expr

1 2	sealed trait Zero extends Expr sealed trait Succ[N <: Expr] extends Expr

自然数はチャーチ数で表すんですね♪

Succ[Succ[Zero]]

1	Succ[Succ[Zero]]

因みにこういうことらしいです。

  type _0 = Zero
  type _1 = Succ[_0]
  type _2 = Succ[_1]
  type _3 = Succ[_2]
  type _4 = Succ[_3]
  type _5 = Succ[_4]
  type _6 = Succ[_5]
  type _7 = Succ[_6]
  type _8 = Succ[_7]
  type _9 = Succ[_8]
  type _10 = Succ[_9]
  type _11 = Succ[_10]
  type _12 = Succ[_11]
  type _13 = Succ[_12]
  type _14 = Succ[_13]
  type _15 = Succ[_14]

type _0 = Zero

type _1 = Succ[_0]

type _2 = Succ[_1]

type _3 = Succ[_2]

type _4 = Succ[_3]

type _5 = Succ[_4]

type _6 = Succ[_5]

type _7 = Succ[_6]

type _8 = Succ[_7]

type _9 = Succ[_8]

type _10 = Succ[_9]

type _11 = Succ[_10]

type _12 = Succ[_11]

type _13 = Succ[_12]

type _14 = Succ[_13]

type _15 = Succ[_14]

次にシンボルです。シンボルは任意の形をしていますがどう表すのか分からなかったので事前に定義したものだけ許すことにしました。

sealed trait Symbol[S <: Sym] extends Expr

sealed trait Sym
sealed trait SCar extends Sym
sealed trait SCdr extends Sym
sealed trait SCons extends Sym
sealed trait SAppend extends Sym
sealed trait SPlus extends Sym
sealed trait SMinus extends Sym
sealed trait SMult extends Sym
sealed trait SEval extends Sym
sealed trait SQuote extends Sym
sealed trait SIf extends Sym

sealed trait Symbol[S <: Sym] extends Expr

sealed trait Sym

sealed trait SCar extends Sym

sealed trait SCdr extends Sym

sealed trait SCons extends Sym

sealed trait SAppend extends Sym

sealed trait SPlus extends Sym

sealed trait SMinus extends Sym

sealed trait SMult extends Sym

sealed trait SEval extends Sym

sealed trait SQuote extends Sym

sealed trait SIf extends Sym

詳しい方上手いやり方を教えて下さい><。

ASTから実行時の表現への変換はそんなに大したことなさそうなので最後にやることにします。

関数を定義する

足し算とか

まずは足し算からやってみます。チャーチ数の足し算は

0 + n = 
S(m) + n = m + S(n)

1 2	0 + n = S(m) + n = m + S(n)

ですね。今回は少し変形した

n + 0 = n
n + S(m) = S(n + m)

1 2	n + 0 = n n + S(m) = S(n + m)

を使います。

まずは足し算トレイトの定義から。

trait Plus[N <: Expr, M <: Expr] {type Out <: Expr}

1	trait Plus[N <: Expr, M <: Expr] {type Out <: Expr}

Nと Mを受け取って結果を Outに入れる、と。なんだかPrologみたいですね。
じゃあ実装をしていきます。まずは最初の n + 0 = nから。

object Plus {
  implicit def zero[N <: Expr]: Plus[N, Zero] { type Out = N } =
    new Plus[N, Zero] {type Out = N}
}

object Plus {

implicit def zero[N <: Expr]: Plus[N, Zero] { type Out = N } =

new Plus[N, Zero] {type Out = N}

}

そのままですね。ところでトレイトとオブジェクトの名前が被ってますが「インプリシットはコンパニオンオブジェクトからも探される」(?????)らしいので被ってていいそうです。というか同じじゃないといけない(?)。

因みに : Plus[N, Zero] { type Out = N } = new Plus[N, Zero] {type Out = N}と2回も同じことを書いてるのは : Plus[N, Zero] { type Out = N }側は計算結果、 new Plus[N, Zero] {type Out = N}側が計算結果が存在することの証明らしいです。
値は証明!ユニフィケーション!

次に再帰節です。再帰ってどうやるんだって気になりますがここでもインプリシットを使うそうです。

object Plus {
  implicit def zero[N <: Expr]: Plus[N, Zero] { type Out = N } =
    new Plus[N, Zero] {type Out = N}
  implicit def succ[N <: Expr, M <: Expr](implicit plus: Plus[N, M]): Plus[N, Succ[M]] { type Out = Succ[plus.Out] } =
    new Plus[N, Succ[M]] {type Out = Succ[plus.Out]}
}

object Plus {

implicit def zero[N <: Expr]: Plus[N, Zero] { type Out = N } =

new Plus[N, Zero] {type Out = N}

implicit def succ[N <: Expr, M <: Expr](implicit plus: Plus[N, M]): Plus[N, Succ[M]] { type Out = Succ[plus.Out] } =

new Plus[N, Succ[M]] {type Out = Succ[plus.Out]}

}

「 Plus[N, M]が存在する時に Plus[N, Succ[M]]は定義出来て、その結果は Succ[plus.Out]になる」と読めばなんとなく分かりそうです。やっぱりPrologっぽいですね。

plus(N,zero, N).
plus(N, s(M), s(O)):-
  plus(N, M, O).

plus(N,zero, N).

plus(N, s(M), s(O)):-

plus(N, M, O).

と対応とれますね。

一旦様子を見ます。

// 0 + 2 == 2
scala> implicitly[Plus[Zero, Succ[Succ[Zero]]]{type Out = Succ[Succ[Zero]]}]
res2: scalalisp.Plus[scalalisp.Zero,scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]]{type Out = scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]} = scalalisp.Plus$$anon$2@1d9c4d5

// 1 + 2 == 2
scala> implicitly[Plus[Succ[Zero], Succ[Succ[Zero]]]{type Out = Succ[Succ[Zero]]}]
<console>:14: error: could not find implicit value for parameter e: scalalisp.Plus[scalalisp.Succ[scalalisp.Zero],scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]]{type Out = scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]}
       implicitly[Plus[Succ[Zero], Succ[Succ[Zero]]]{type Out = Succ[Succ[Zero]]}]
                 ^

// 1 + 2 == 3
scala> implicitly[Plus[Succ[Zero], Succ[Succ[Zero]]]{type Out = Succ[Succ[Succ[Zero]]]}]
res4: scalalisp.Plus[scalalisp.Succ[scalalisp.Zero],scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]]{type Out = scalalisp.Succ[scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]]} = scalalisp.Plus$$anon$2@74a20f13

// 0 + 2 == 2

scala> implicitly[Plus[Zero, Succ[Succ[Zero]]]{type Out = Succ[Succ[Zero]]}]

res2: scalalisp.Plus[scalalisp.Zero,scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]]{type Out = scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]} = scalalisp.Plus$$anon$2@1d9c4d5

// 1 + 2 == 2

scala> implicitly[Plus[Succ[Zero], Succ[Succ[Zero]]]{type Out = Succ[Succ[Zero]]}]

<console>:14: error: could not find implicit value for parameter e: scalalisp.Plus[scalalisp.Succ[scalalisp.Zero],scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]]{type Out = scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]}

implicitly[Plus[Succ[Zero], Succ[Succ[Zero]]]{type Out = Succ[Succ[Zero]]}]

// 1 + 2 == 3

scala> implicitly[Plus[Succ[Zero], Succ[Succ[Zero]]]{type Out = Succ[Succ[Succ[Zero]]]}]

res4: scalalisp.Plus[scalalisp.Succ[scalalisp.Zero],scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]]{type Out = scalalisp.Succ[scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]]]} = scalalisp.Plus$$anon$2@74a20f13

計算と期待する結果が合っている時には値が返ってきて、間違ってる時にはエラーが出てます。assert成功ですね。

じゃあ、次はかけ算もやってみましょう。チャーチ数のかけ算は次のように定義できます。

n * 0 = 0
n * S(m) = n + n * m

1 2	n * 0 = 0 n * S(m) = n + n * m

n +を関数と思えば足し算とまったく同じ構造をしてますね。ということで実装もほとんど同じです。

object Mult {
  implicit def zero[N <: Expr]: Mult[N, Zero] { type Out = Zero } =
    new Mult[N, Zero] {type Out = Zero}
  implicit def succ[N <: Expr, M <: Expr, R <: Expr](implicit mult: Mult[N, M] { type Out = R }, plus: Plus[N, R]): Mult[N, Succ[M]] { type Out = plus.Out } =
    new Mult[N, Succ[M]] {type Out = plus.Out}
}

object Mult {

implicit def zero[N <: Expr]: Mult[N, Zero] { type Out = Zero } =

new Mult[N, Zero] {type Out = Zero}

implicit def succ[N <: Expr, M <: Expr, R <: Expr](implicit mult: Mult[N, M] { type Out = R }, plus: Plus[N, R]): Mult[N, Succ[M]] { type Out = plus.Out } =

new Mult[N, Succ[M]] {type Out = plus.Out}

}

自然数の扱いはこの辺までにして次はリストを扱ってみましょう。

リスト操作

リスト(コンスセル)操作の関数基本は自然数と同じです。

ベースとなるトレイトを用意して

trait Car[C <: Expr] {type Out <: Expr}

1	trait Car[C <: Expr] {type Out <: Expr}

実装を書きます。

object Car {
  implicit def car[H <: Expr, T <: Expr]: Car[ConsCell[H, T]] {type Out = H} =
    new Car[ConsCell[H, T]] {type Out = H}
}

object Car {

implicit def car[H <: Expr, T <: Expr]: Car[ConsCell[H, T]] {type Out = H} =

new Car[ConsCell[H, T]] {type Out = H}

}

簡単ですね。同じようにしてcdrも定義出来ます。

一応consも作ります。

trait Cons[Car <: Expr, Cdr <: Expr] {type Out <: Expr}

object Cons {
  implicit def cons[Car <: Expr, Cdr <: Expr]: Cons[Car, Cdr]{type Out = ConsCell[Car, Cdr]} =
    new Cons[Car, Cdr]{type Out = ConsCell[Car, Cdr]}
}

trait Cons[Car <: Expr, Cdr <: Expr] {type Out <: Expr}

object Cons {

implicit def cons[Car <: Expr, Cdr <: Expr]: Cons[Car, Cdr]{type Out = ConsCell[Car, Cdr]} =

new Cons[Car, Cdr]{type Out = ConsCell[Car, Cdr]}

}

余談ですが関数のコンスとデータ型のコンスが混らないようにデータ型の方をコンスセルにしました。

次はappendです。appendはどのように表されるでしょうか。一旦Prologで考えてみましょう。

append([], L2, L2).
append([H | T], L2, [H | Out]):-
    append(T, L2, Out).

append([], L2, L2).

append([H | T], L2, [H | Out]):-

append(T, L2, Out).

こうなりますね。これをそのままScalaに書き下します。

trait Append[L1 <: Expr, L2 <: Expr]{type Out <: Expr}

object Append {
  implicit def appendNil[L1 <: Nil, L2 <: Expr]: Append[L1, L2] {type Out = L2} = new Append[L1, L2] {type Out = L2}

  implicit def appendList[L1Car <: Expr, L1Cdr <: Expr, L2 <: Expr]
    (implicit append_ : Append[L1Cdr, L2]): Append[ConsCell[L1Car, L1Cdr], L2] {type Out = ConsCell[L1Car, append_.Out]} =
    new Append[ConsCell[L1Car, L1Cdr], L2] {type Out = ConsCell[L1Car, append_.Out]}

}

trait Append[L1 <: Expr, L2 <: Expr]{type Out <: Expr}

object Append {

implicit def appendNil[L1 <: Nil, L2 <: Expr]: Append[L1, L2] {type Out = L2} = new Append[L1, L2] {type Out = L2}

implicit def appendList[L1Car <: Expr, L1Cdr <: Expr, L2 <: Expr]

(implicit append_ : Append[L1Cdr, L2]): Append[ConsCell[L1Car, L1Cdr], L2] {type Out = ConsCell[L1Car, append_.Out]} =

new Append[ConsCell[L1Car, L1Cdr], L2] {type Out = ConsCell[L1Car, append_.Out]}

}

prologのbody部分を implicitにすれば良いみたいですね。だんだん慣れてきました。これも少し試してみましょう。

// (append (0) (1 2)) == (1 2 3)
scala> implicitly[Append[ConsCell[Zero, Nil], ConsCell[Succ[Zero], ConsCell[Succ[Succ[Zero]], Nil]]]{ type Out = ConsCell[Zero, ConsCell[Succ[Zero], ConsCell[Succ[Succ[Zero]], Nil]]]}]
res5: scalalisp.Append[scalalisp.ConsCell[scalalisp.Zero,scalalisp.Nil],scalalisp.ConsCell[scalalisp.Succ[scalalisp.Zero],scalalisp.ConsCell[scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]],scalalisp.Nil]]]{type Out = scalalisp.ConsCell[scalalisp.Zero,scalalisp.ConsCell[scalalisp.Succ[scalalisp.Zero],scalalisp.ConsCell[scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]],scalalisp.Nil]]]} = scalalisp.Append$$anon$5@72f34934

// (append (0) (1 2)) == (1 2 3)

scala> implicitly[Append[ConsCell[Zero, Nil], ConsCell[Succ[Zero], ConsCell[Succ[Succ[Zero]], Nil]]]{ type Out = ConsCell[Zero, ConsCell[Succ[Zero], ConsCell[Succ[Succ[Zero]], Nil]]]}]

res5: scalalisp.Append[scalalisp.ConsCell[scalalisp.Zero,scalalisp.Nil],scalalisp.ConsCell[scalalisp.Succ[scalalisp.Zero],scalalisp.ConsCell[scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]],scalalisp.Nil]]]{type Out = scalalisp.ConsCell[scalalisp.Zero,scalalisp.ConsCell[scalalisp.Succ[scalalisp.Zero],scalalisp.ConsCell[scalalisp.Succ[scalalisp.Succ[scalalisp.Zero]],scalalisp.Nil]]]} = scalalisp.Append$$anon$5@72f34934

よしよし。

もう少し複雑なことをやってみましょう。

// (car (cons 0 nil)) == 0
scala> implicitly[Car[Cons[Zero, Nil]]{type Out = Zero}]
<console>:14: error: could not find implicit value for parameter e: scalalisp.Car[scalalisp.Cons[scalalisp.Zero,scalalisp.Nil]]{type Out = scalalisp.Zero}
       implicitly[Car[Cons[Zero, Nil]]{type Out = Zero}]
                 ^

// (car (cons 0 nil)) == 0

scala> implicitly[Car[Cons[Zero, Nil]]{type Out = Zero}]

<console>:14: error: could not find implicit value for parameter e: scalalisp.Car[scalalisp.Cons[scalalisp.Zero,scalalisp.Nil]]{type Out = scalalisp.Zero}

implicitly[Car[Cons[Zero, Nil]]{type Out = Zero}]

あれ？合ってる筈なのにエラーが出ます。

これは Consの定義を思い出してみると分かります。

trait Cons[Car <: Expr, Cdr <: Expr] {type Out <: Expr}

object Cons {
  implicit def cons[Car <: Expr, Cdr <: Expr]: Cons[Car, Cdr]{type Out = ConsCell[Car, Cdr]} =
    new Cons[Car, Cdr]{type Out = ConsCell[Car, Cdr]}
}

trait Cons[Car <: Expr, Cdr <: Expr] {type Out <: Expr}

object Cons {

implicit def cons[Car <: Expr, Cdr <: Expr]: Cons[Car, Cdr]{type Out = ConsCell[Car, Cdr]} =

new Cons[Car, Cdr]{type Out = ConsCell[Car, Cdr]}

}

Consの型は Consなんですね。なので Carには渡せません。さて……どうしましょうか。

ここでお気付きの方もいるかもしれませんが今まで定義してきたのは「実行時表現を操作する何か」であって実行時表現ではないのです。
M式に似てるので勘違いしやすいのですがscalalispの一部でない。 Car[E]であって ConsCell[Symbol[SCar], ConsCell[E, Nil]]でない。
じゃあどうすればいいかというとS式のインタプリタを書くのです。

eval

S式のインタプリタのことを evalっていいますね。
evalのインターフェースは単純です。

trait Eval[E <: Expr] {
  type Out <: Expr
}

trait Eval[E <: Expr] {

type Out <: Expr

}

S式を受け取って評価した値を返す。

で、これの実装ですがprologで書くとこうなります。

eval(zero, zero).
eval(s(n), s(n)).
...
eval([quote, E], E).
eval([car, E], O):-
    eval(E, E_),
    car(E_, O).
...

eval(zero, zero).

eval(s(n), s(n)).

...

eval([quote, E], E).

eval([car, E], O):-

eval(E, E_),

car(E_, O).

...

アトム、スペシャルフォーム、及び提供したい関数全てに対してホーン節を定義してあげる訳です。

ちょっと億劫ですがやっていきましょう。

まずは便利のためにリスト型を用意します。

object Eval {
  type List1[E<:Expr] = ConsCell[E, Nil]
  type List2[E1<:Expr, E2<:Expr] = ConsCell[E1, List1[E2]]
  type List3[E1<:Expr, E2<:Expr, E3<:Expr] = ConsCell[E1, List2[E2, E3]]
  type List4[E1<:Expr, E2<:Expr, E3<:Expr, E4 <: Expr] = ConsCell[E1, List3[E2, E3, E4]]
  ...

object Eval {

type List1[E<:Expr] = ConsCell[E, Nil]

type List2[E1<:Expr, E2<:Expr] = ConsCell[E1, List1[E2]]

type List3[E1<:Expr, E2<:Expr, E3<:Expr] = ConsCell[E1, List2[E2, E3]]

type List4[E1<:Expr, E2<:Expr, E3<:Expr, E4 <: Expr] = ConsCell[E1, List3[E2, E3, E4]]

...

アトム

アトムは簡単です。

  implicit def zero: Eval[Zero] {type Out = Zero} = new Eval[Zero] {type Out = Zero}
  implicit def succ[E <: Expr]: Eval[Succ[E]] {type Out = Succ[E]} = new Eval[Succ[E]] {type Out = Succ[E]}
  implicit def nil: Eval[Nil] {type Out = Nil} = new Eval[Nil] {type Out = Nil}
  implicit def t: Eval[T_] {type Out = T_} = new Eval[T_] {type Out = T_}

  //TODO evaluate to bound value
  implicit def symbol[S <: Sym]: Eval[Symbol[S]] {type Out = Symbol[S]} = new Eval[Symbol[S]] {type Out = Symbol[S]}

implicit def zero: Eval[Zero] {type Out = Zero} = new Eval[Zero] {type Out = Zero}

implicit def succ[E <: Expr]: Eval[Succ[E]] {type Out = Succ[E]} = new Eval[Succ[E]] {type Out = Succ[E]}

implicit def nil: Eval[Nil] {type Out = Nil} = new Eval[Nil] {type Out = Nil}

implicit def t: Eval[T_] {type Out = T_} = new Eval[T_] {type Out = T_}

//TODO evaluate to bound value

implicit def symbol[S <: Sym]: Eval[Symbol[S]] {type Out = Symbol[S]} = new Eval[Symbol[S]] {type Out = Symbol[S]}

本来ならシンボルはそれが束縛されている値へと評価されるのですが今回値の束縛を用意していないので自身へと評価することにしました。
未束縛でエラーにならないちょっと気持ち悪いですかね。しかしShenのようにそういう評価規則を持つ処理系もあるので大丈夫でしょう。

関数

全部やるとキリがないのでいくつか。carはこうなります。上に挙げたprologそのままですね。

  implicit def car[E <: Expr, EOut <: Expr,  CarOut <: Expr]
    (implicit
      e : Eval[E]{type Out = EOut},
      car : Car[EOut]{type Out = CarOut}
    ) : Eval[List2[Symbol[SCar], E]] {type Out = CarOut} =
    new Eval[List2[Symbol[SCar], E]] {type Out = CarOut}

implicit def car[E <: Expr, EOut <: Expr, CarOut <: Expr]

(implicit

e : Eval[E]{type Out = EOut},

car : Car[EOut]{type Out = CarOut}

) : Eval[List2[Symbol[SCar], E]] {type Out = CarOut} =

new Eval[List2[Symbol[SCar], E]] {type Out = CarOut}

他の関数も同様に定義しますが、例としてappendも出しておきましょう。

  implicit def append[L1 <: Expr, L2 <: Expr, L1Out <: Expr, L2Out<: Expr, AppendOut <: Expr]
    (implicit
      l1 : Eval[L1]{type Out = L1Out},
      l2 : Eval[L2]{type Out = L2Out},
      append : Append[L1Out, L2Out]{type Out = AppendOut}
    ) : Eval[List3[Symbol[SAppend], L1, L2]] {type Out = AppendOut} =
    new Eval[List3[Symbol[SAppend], L1, L2]] {type Out = AppendOut}

implicit def append[L1 <: Expr, L2 <: Expr, L1Out <: Expr, L2Out<: Expr, AppendOut <: Expr]

(implicit

l1 : Eval[L1]{type Out = L1Out},

l2 : Eval[L2]{type Out = L2Out},

append : Append[L1Out, L2Out]{type Out = AppendOut}

) : Eval[List3[Symbol[SAppend], L1, L2]] {type Out = AppendOut} =

new Eval[List3[Symbol[SAppend], L1, L2]] {type Out = AppendOut}

prologではこうなります。

eval([append, L1, L2], AppendOut):-
    eval(L1, L1Out),
    eval(L2, L2Out),
    append(L1Out, L2Out, AppendOut).

eval([append, L1, L2], AppendOut):-

eval(L1, L1Out),

eval(L2, L2Out),

append(L1Out, L2Out, AppendOut).

そのまんま東ですね。

eval自身を定義することも勿論可能です。

  implicit def eval[E <: Expr, EOut <: Expr,  EvalOut <: Expr]
    (implicit
      e : Eval[E]{type Out = EOut},
      eval_ : Eval[EOut]{type Out = EvalOut}
    ) : Eval[List2[Symbol[SEval], E]] {type Out = EvalOut} =
    new Eval[List2[Symbol[SEval], E]] {type Out = EvalOut}

implicit def eval[E <: Expr, EOut <: Expr, EvalOut <: Expr]

(implicit

e : Eval[E]{type Out = EOut},

eval_ : Eval[EOut]{type Out = EvalOut}

) : Eval[List2[Symbol[SEval], E]] {type Out = EvalOut} =

new Eval[List2[Symbol[SEval], E]] {type Out = EvalOut}

スペシャルフォーム

今回、スペシャルフォームは quoteと ifを提供することにします。

quoteは簡単ですね。

  implicit def quote[E <: Expr]: Eval[List2[Symbol[SQuote], E]] {type Out = E} =
    new Eval[List2[Symbol[SQuote], E]] {type Out = E}

1 2	implicit def quote[E <: Expr]: Eval[List2[Symbol[SQuote], E]] {type Out = E} = new Eval[List2[Symbol[SQuote], E]] {type Out = E}

評価せずに返してあげればよいです。

問題はifです。Scalaだと複雑なので一旦prologで説明します。(なんかカットが必要な気がしますが説明と関係ないので省きます。)

eval([if,Cond, _, Else], ElseOut):-
    eval(Cond, nil),
    eval(Else, ElseOut).
eval([if, Cond, Then, _], ThenOut):-
    eval(Cond, _),
    eval(Then, ThenOut).

eval([if,Cond, _, Else], ElseOut):-

eval(Cond, nil),

eval(Else, ElseOut).

eval([if, Cond, Then, _], ThenOut):-

eval(Cond, _),

eval(Then, ThenOut).

これでnilとそうでない場合の分岐をしているのですが構造は同じですよね？違いは Condを評価した結果を nilとユニフィケーションしているか。

ところでCondの評価値がnilなのに2つ目の節に入った場合、 _で受けているのでユニフィケーションに失敗せずにそのまま Thenが返ってきてしまいますよね。
Prologの場合は 最初に書いたホーン節から 成功するまで試すので問題ありません。しかしScalaのimplicitにはそういう規則がありません。

どうにかしてimplicitの解決に優先順位を与えないといけませんね。そこで継承を使います。implicitは先に自身のimplicitを捜して次に親のimplicitを捜すらしい(?)のでそこで優先順位をつけます。ということで Evalに少し変更が必要です。

trait EvalLowerPriority{ 
  type List1[E<:Expr] = ConsCell[E, Nil]
  type List2[E1<:Expr, E2<:Expr] = ConsCell[E1, List1[E2]]
  type List3[E1<:Expr, E2<:Expr, E3<:Expr] = ConsCell[E1, List2[E2, E3]]
  type List4[E1<:Expr, E2<:Expr, E3<:Expr, E4 <: Expr] = ConsCell[E1, List3[E2, E3, E4]]
  implicit def ifT[Cond <: Expr, CondOut <:Expr, Then <: Expr, ThenOut <:Expr, Else <: Expr]
    (implicit
      cond : Eval[Cond]{type Out = CondOut},
      then_ : Eval[Then]{type Out = ThenOut})
      : Eval[List4[Symbol[SIf], Cond, Then, Else]] {type Out =  ThenOut} =
    new Eval[List4[Symbol[SIf], Cond, Then, Else]] {type Out =  ThenOut}

}

object Eval extends EvalLowerPriority {
....

  implicit def ifNil[Cond <: Expr, Then <: Expr, Else <: Expr, ElseOut <:Expr]
    (implicit
      cond : Eval[Cond]{type Out = Nil},
      else_ : Eval[Else]{type Out = ElseOut}
    ) : Eval[List4[Symbol[SIf], Cond, Then, Else]] {type Out = ElseOut} =
    new Eval[List4[Symbol[SIf], Cond, Then, Else]] {type Out = ElseOut}

....
}

trait EvalLowerPriority{

type List1[E<:Expr] = ConsCell[E, Nil]

type List2[E1<:Expr, E2<:Expr] = ConsCell[E1, List1[E2]]

type List3[E1<:Expr, E2<:Expr, E3<:Expr] = ConsCell[E1, List2[E2, E3]]

type List4[E1<:Expr, E2<:Expr, E3<:Expr, E4 <: Expr] = ConsCell[E1, List3[E2, E3, E4]]

implicit def ifT[Cond <: Expr, CondOut <:Expr, Then <: Expr, ThenOut <:Expr, Else <: Expr]

(implicit

cond : Eval[Cond]{type Out = CondOut},

then_ : Eval[Then]{type Out = ThenOut})

: Eval[List4[Symbol[SIf], Cond, Then, Else]] {type Out = ThenOut} =

new Eval[List4[Symbol[SIf], Cond, Then, Else]] {type Out = ThenOut}

}

object Eval extends EvalLowerPriority {

....

implicit def ifNil[Cond <: Expr, Then <: Expr, Else <: Expr, ElseOut <:Expr]

(implicit

cond : Eval[Cond]{type Out = Nil},

else_ : Eval[Else]{type Out = ElseOut}

) : Eval[List4[Symbol[SIf], Cond, Then, Else]] {type Out = ElseOut} =

new Eval[List4[Symbol[SIf], Cond, Then, Else]] {type Out = ElseOut}

....

}

優先度の低いホーン節用のトレイトを作ってあげて Evalでそいつを継承します。これで ifを実装出来ました

プリティプリンタ

最後の返り値はやっぱりS式の方が見易いので一瞬evalから離れて文字列化をやります。

  trait ToString[E <: Expr] {def apply(): String}
  object ToString {
    def apply[E <: Expr](implicit toString :ToString[E]): String = toString()
  }

trait ToString[E <: Expr] {def apply(): String}

object ToString {

def apply[E <: Expr](implicit toString :ToString[E]): String = toString()

}

を用意してまたimplicitに解決させます。今までと違うのは最後は文字列で欲しいので applyを使っているところですね。

nil/t

やっていきます。 tと nil

  implicit def toStringNil = new ToString[Nil]{
    def apply() = "()"
  }
  implicit def toStringT_ = new ToString[T_]{
    def apply() = "t"
  }

implicit def toStringNil = new ToString[Nil]{

def apply() = "()"

}

implicit def toStringT_ = new ToString[T_]{

def apply() = "t"

}

リスト/コンスセル

次は少々技巧的ですがリスト/コンスセル

  implicit def toStringList[E<:Expr](implicit toStringList : ToStringList[E]): ToString[E] = new ToString[E] {
    def apply() = s"(${toStringList()}"
  }

  trait ToStringList[E <: Expr] {def apply(): String}
  object ToStringList {
    def apply[E<:Expr](implicit toStringList: ToStringList[E]):String = toStringList()
  }

  implicit def toStringList1[E<:Expr](implicit toString1: ToString[E])
      :ToStringList[ConsCell[E, Nil]] = new ToStringList[ConsCell[E, Nil]] {
    def apply() = s"${toString1()})"
  }

  implicit def toStringListN[E<:Expr, E1 <: Expr, E2 <: Expr ](implicit toString1: ToString[E], toStringList: ToStringList[ConsCell[E1, E2]])
      :ToStringList[ConsCell[E, ConsCell[E1, E2]]] = new ToStringList[ConsCell[E, ConsCell[E1, E2]]] {
    def apply() = s"${toString1()} ${toStringList()}"
  }

  implicit def toStringListCons[E1 <: Expr, E2 <: Expr ](
    implicit toStringCar: ToString[E1],
    toStringCdr: ToString[E2]): ToStringList[ConsCell[E1, E2]] = new ToStringList[ConsCell[E1, E2]]{
    def apply() = s"${toStringCar()} . ${toStringCdr()})"
  }

implicit def toStringList[E<:Expr](implicit toStringList : ToStringList[E]): ToString[E] = new ToString[E] {

def apply() = s"(${toStringList()}"

}

trait ToStringList[E <: Expr] {def apply(): String}

object ToStringList {

def apply[E<:Expr](implicit toStringList: ToStringList[E]):String = toStringList()

}

implicit def toStringList1[E<:Expr](implicit toString1: ToString[E])

:ToStringList[ConsCell[E, Nil]] = new ToStringList[ConsCell[E, Nil]] {

def apply() = s"${toString1()})"

}

implicit def toStringListN[E<:Expr, E1 <: Expr, E2 <: Expr ](implicit toString1: ToString[E], toStringList: ToStringList[ConsCell[E1, E2]])

:ToStringList[ConsCell[E, ConsCell[E1, E2]]] = new ToStringList[ConsCell[E, ConsCell[E1, E2]]] {

def apply() = s"${toString1()} ${toStringList()}"

}

implicit def toStringListCons[E1 <: Expr, E2 <: Expr ](

implicit toStringCar: ToString[E1],

toStringCdr: ToString[E2]): ToStringList[ConsCell[E1, E2]] = new ToStringList[ConsCell[E1, E2]]{

def apply() = s"${toStringCar()} . ${toStringCdr()})"

}

リストの開始のコンスセルで "(s"を、リストの中では要素をスペース区切で、リストの最後のコンスセルで "e)"または ". e)"を返します。 toStringListNと toStringConsがコンフリクトしそうな気がしますが何故か通ります。返り値のユニフィケーションしてないから?よく分かってません。

自然数

自然数は一旦数値に変換してから toStringを呼んでやります。

  implicit def toStringInt[N <:Expr](implicit toInt: ToInt[N]):ToString[N] = new ToString[N] {
    def apply() = ToInt[N].toString
  }

  trait ToInt[E <: Expr] {def apply(): Int}
  object ToInt {
    def apply[E <: Expr](implicit toInt: ToInt[E]): Int = toInt()
  }

  implicit def toInt0:ToInt[Zero] = new ToInt[Zero] {
    def apply() = 0
  }


  implicit def toIntSucc[N <: Expr](implicit toInt: ToInt[N]):ToInt[Succ[N]] = new ToInt[Succ[N]] {
    def apply() = 1 + toInt()
  }

implicit def toStringInt[N <:Expr](implicit toInt: ToInt[N]):ToString[N] = new ToString[N] {

def apply() = ToInt[N].toString

}

trait ToInt[E <: Expr] {def apply(): Int}

object ToInt {

def apply[E <: Expr](implicit toInt: ToInt[E]): Int = toInt()

}

implicit def toInt0:ToInt[Zero] = new ToInt[Zero] {

def apply() = 0

}

implicit def toIntSucc[N <: Expr](implicit toInt: ToInt[N]):ToInt[Succ[N]] = new ToInt[Succ[N]] {

def apply() = 1 + toInt()

}

シンボル

シンボルは個別で対応するしかありません。まあ、今回は高々有限個です。

  implicit def toStringSym[E <: Expr](implicit toStringSym: ToStringSymbol[E]): ToString[E] = new ToString[E] {
    def apply() = toStringSym()
  }

  trait ToStringSymbol[E <: Expr] {def apply(): String}

  object ToStringSymbol {
    def apply[E <: Expr](implicit toStringSymbol: ToStringSymbol[E]) = toStringSymbol()
  }

  implicit def toStringCar: ToStringSymbol[Symbol[SCar]] = new ToStringSymbol[Symbol[SCar]] {
    def apply() = "car"
  }
  ...

implicit def toStringSym[E <: Expr](implicit toStringSym: ToStringSymbol[E]): ToString[E] = new ToString[E] {

def apply() = toStringSym()

}

trait ToStringSymbol[E <: Expr] {def apply(): String}

object ToStringSymbol {

def apply[E <: Expr](implicit toStringSymbol: ToStringSymbol[E]) = toStringSymbol()

}

implicit def toStringCar: ToStringSymbol[Symbol[SCar]] = new ToStringSymbol[Symbol[SCar]] {

def apply() = "car"

}

...

評価機

ToStringが出来たので評価機を作ります。 EvalToString。まあ、 Evalして ToStringするだけです。

  trait EvalToString[E <: Expr] {def apply(): String}

  object EvalToString {
    def apply[E <: Expr](
      implicit evalToString: EvalToString[E]): String = evalToString()
  }
  implicit def evalToString[E <:Expr, EvalOut <: Expr](
    implicit
      eval : Eval[E]{ type Out = EvalOut},
    toString_ : Expr.ToString[EvalOut]
  ): EvalToString[E] = new EvalToString[E]{def apply() = toString_()}

trait EvalToString[E <: Expr] {def apply(): String}

object EvalToString {

def apply[E <: Expr](

implicit evalToString: EvalToString[E]): String = evalToString()

}

implicit def evalToString[E <:Expr, EvalOut <: Expr](

implicit

eval : Eval[E]{ type Out = EvalOut},

toString_ : Expr.ToString[EvalOut]

): EvalToString[E] = new EvalToString[E]{def apply() = toString_()}

貫通

さて、部品が揃いました。あとはS式をパースして型に落として EvalToStringを呼ぶだけですね。コンパイル時にパース関数を走らせるためにマクロを使います。

マクロを使うにはリフレクションライブラリが必要みたいです。 "org.scala-lang" % "scala-reflect" % scalaVersion.value

さて、実行器はそんなに対したことないので一気にソースを載せてしまいます。

package scalalisp

import scala.reflect.macros.blackbox.Context
import scala.language.experimental.macros

object Lisp {
  def run(expr: String): String = macro run_impl
  def run_impl(c: Context)(expr: c.Expr[String]): c.Tree = {
    import c.universe._
    val Literal(Constant(s_expr: String)) = expr.tree
    val ast = Parser.parseAll(Parser.expr, s_expr).get
    val t = toT(c)(ast)
    q"Eval.EvalToString[$t]"
  }

  def toT(c: Context)(e: Ast.Ast): c.Tree = {
    import c.universe._
    import Ast._
    e match {
      case LNil() => tq"Nil"
      case LT() => tq"T_"
      case LCons(car, cdr) => tq"ConsCell[${toT(c)(car)},${toT(c)(cdr)}]"
      case LInt(0) => tq"Zero"
      case LInt(i) => tq"Succ[${toT(c)(LInt(i-1))}]"
      case LSymbol("car") => tq"Symbol[SCar]"
      case LSymbol("cdr") => tq"Symbol[SCdr]"
      case LSymbol("cons") => tq"Symbol[SCons]"
      case LSymbol("append") => tq"Symbol[SAppend]"
      case LSymbol("+") => tq"Symbol[SPlus]"
      case LSymbol("-") => tq"Symbol[SMinus]"
      case LSymbol("*") => tq"Symbol[SMult]"
      case LSymbol("eval") => tq"Symbol[SEval]"
      case LSymbol("quote") => tq"Symbol[SQuote]"
      case LSymbol("if") => tq"Symbol[SIf]"
      //TODO handle error
      case LSymbol(_) => tq"Nil"
    }
  }

}

package scalalisp

import scala.reflect.macros.blackbox.Context

import scala.language.experimental.macros

object Lisp {

def run(expr: String): String = macro run_impl

def run_impl(c: Context)(expr: c.Expr[String]): c.Tree = {

import c.universe._

val Literal(Constant(s_expr: String)) = expr.tree

val ast = Parser.parseAll(Parser.expr, s_expr).get

val t = toT(c)(ast)

q"Eval.EvalToString[$t]"

}

def toT(c: Context)(e: Ast.Ast): c.Tree = {

import c.universe._

import Ast._

e match {

case LNil() => tq"Nil"

case LT() => tq"T_"

case LCons(car, cdr) => tq"ConsCell[${toT(c)(car)},${toT(c)(cdr)}]"

case LInt(0) => tq"Zero"

case LInt(i) => tq"Succ[${toT(c)(LInt(i-1))}]"

case LSymbol("car") => tq"Symbol[SCar]"

case LSymbol("cdr") => tq"Symbol[SCdr]"

case LSymbol("cons") => tq"Symbol[SCons]"

case LSymbol("append") => tq"Symbol[SAppend]"

case LSymbol("+") => tq"Symbol[SPlus]"

case LSymbol("-") => tq"Symbol[SMinus]"

case LSymbol("*") => tq"Symbol[SMult]"

case LSymbol("eval") => tq"Symbol[SEval]"

case LSymbol("quote") => tq"Symbol[SQuote]"

case LSymbol("if") => tq"Symbol[SIf]"

//TODO handle error

case LSymbol(_) => tq"Nil"

}

run_implでは文字列リテラルのASTから文字列を抜き出して、パースしてASTにして、型に変換して、それを EvalToStringに食わせる形のASTに変換するだけですね

toTではASTを実行時表現にそのまま翻訳します。型なのでquasi quoteが qではなく tqになってますね。

事前に用意してなかったシンボルを nilにするという邪悪なことをしていますがまあ目を瞑って下さい。

それでは遊んでみましょう。

scala> Lisp.run("1")
res0: String = 1

scala> Lisp.run("'(1 2 3)")

res1: String = (1 2 3)

scala> Lisp.run("1")
res2: String = 1

scala> Lisp.run("(+ 1 2)")
res3: String = 3

scala> Lisp.run("(cons (+ 1 2) nil)")
res4: String = (3)

scala> Lisp.run("(cdr (cons (+ 1 2) nil))")
res5: String = ()

scala> Lisp.run("(car (cons (+ 1 2) nil))")
res6: String = 3

scala> Lisp.run("(append '(+ 1 2) '(3))")
res8: String = (+ 1 2 3)

scala> Lisp.run("(eval (append '(+ 1) '(3)))")
res9: String = 4

scala> Lisp.run("1")

res0: String = 1

scala> Lisp.run("'(1 2 3)")

res1: String = (1 2 3)

scala> Lisp.run("1")

res2: String = 1

scala> Lisp.run("(+ 1 2)")

res3: String = 3

scala> Lisp.run("(cons (+ 1 2) nil)")

res4: String = (3)

scala> Lisp.run("(cdr (cons (+ 1 2) nil))")

res5: String = ()

scala> Lisp.run("(car (cons (+ 1 2) nil))")

res6: String = 3

scala> Lisp.run("(append '(+ 1 2) '(3))")

res8: String = (+ 1 2 3)

scala> Lisp.run("(eval (append '(+ 1) '(3)))")

res9: String = 4

やりましたね! Lispが動いてます。

今回のソースコードはこちらに置いておきます。遊びで作ったので色々雑ですが興味のある方は全体を眺めてみて下さい。

最後に

飛ばし飛ばしでしたが型レベルLispはいかがでしたでしょうか。

心残りなのはチューリング完全に出来なかったことですね。Lispをチューリング完全にする場合、純LISP的アプローチだと (define name value)相当のラベル機能を付けますが、環境を持てない今回では厳しいので見送り。
次はlambdaを実装してしまうものですが、それも中々というかラベル以上に難しいでしょう。クロージャの実装が必要になります。
ド・ブラン・インデックスを使って実装してしまった方もいるようですが、traitをfatにしてtypeを持たせてやるやり方が好みでなかったのでやめました。
一応計画としては文法的にはlambdaをサポート、実行時表現にSKIコンビネータを入れてコンパイラでラムダ計算からSKIコンビネータへの項書き換えをするのが今回の実装に一番適してるかなと思ったのですが中々大変なので間に合いませんでした。
実行時表現にSKIコンビネータを突っ込むだけでもやれば良かった。

ということでκeen(@blackenedgold)がお送りしました！！

Author

fukuhara