Scala による小さな Lisp

2009.12.10 - 2009.12.15 (鈴)

1. 簡単な S 式パーサ
2. 文字列表現への変換
3. アトムと基本５関数だけの eval 関数
4. 条件式と関数適用を追加した eval 関数
5. 仕上げ

はじめに

本稿では，小さな Lisp の実装をとおして，最初の入門の次の段階としての Scala を学んで行きます。 Java 1.5.0 上の Scala 2.7.7 を使いますが，コードは Scala 2.8.0.r20121 でもひととおり確認しています。 Lisp の仕様と評価のアルゴリズムは基本的に下記にしたがいます。

John McCarthy: A Micro-Manual for Lisp - Not the Whole Truth,
ACM SIGPLAN Notices, Vol. 13, No. 8, August 1978, pp.215-216

これは 30 年以上昔の古典的な文献です。 Lisp としての基本は現代と同じですが，静的スコープなどのモダンな特徴はありません。昔をなつかしんでではなく，プログラムを 100 行程度にまとめられるような手頃なお手本を求めて ACM の電子図書館から探し出しました。 Scala を学習するのではなく，近代的な Lisp の小さな実装を望む場合は，例えば，より野心的:-) な L² Lisp を御覧ください。

1. 簡単な S 式パーサ

Scala は，Symbol クラスと，いわゆる cons セルから構成される List[+T] クラスを標準で備えていますから，Lisp の S 式を自然に表現できます。ただし，improper list (cdr が cons セルでも nil でもないリスト) を表せない点は妥協します。

abstract class List[+T] の + は List が covariant (共変) であることを示します。もしも型 T が型 S の派生クラスならば，自動的に List[T] は List[S] の派生クラスになります。したがって自動的に List[Any] は，すべての List の基底クラスになります。また List[Nothing] 型のシングルトン・オブジェクトである Nil は，すべての List のインスタンスになります。なぜなら Any はすべてのクラスの基底クラスであり，Nothing はすべてのクラスからの派生クラスだからです。

Scala は，便利なパーサ構築ライブラリを標準で備えています。これを使って S 式のパーサ，つまり構文解析器を簡単に書くことができます。下記の SExprParsers クラスはその一例です。

import scala.util.parsing.combinator._
import java.io.{FileReader, InputStreamReader}

class SExprParsers extends JavaTokenParsers {
  lazy val list: Parser[List[Any]] = "(" ~> rep(expr) <~ ")"
  lazy val quot: Parser[List[Any]] = ("'" ~> expr) ^^ (List('quote, _))
  lazy val expr: Parser[Any] = {
    list | quot |
    stringLiteral ^^ (s => s.substring(1, s.length() - 1)) |
    """[a-zA-Z_0-9\+\-\*\<]+""".r ^^
    (s => try {s.toLong} catch {case ex: NumberFormatException => Symbol(s)})
  }
}

object Lisp {
  def main(args: Array[String]) {
    val reader = if (args(0) == "-") new InputStreamReader(System.in)
                 else new FileReader(args(0))
    val parsers = new SExprParsers
    val exp = parsers.parseAll(parsers.expr, reader).get
    println(exp)
  }
}

SExprParsers の基底としている scala.util.parsing.combinator.JavaTokenParsers トレイトの継承元をさかのぼると scala.util.parsing.combinator.Parsers につきあたります。このトレイトの中で，~>，<~，^^，|，rep などのメソッドをもつ抽象クラス Parser[+T] が定義されています。

Scala では，任意の１引数メソッド呼出し x.f(y) を，二項演算子の式 x f y のように書くことができます。むしろ Scala の二項演算子は１引数メソッドの別の呼び方にすぎないと言うのが正確です。二項演算子としての優先順位は，言語に組込みのルールとして，メソッド名の先頭１文字で自動的に決定されます (ただし代入演算子は特別ルールによりつねに最下位にされます)。 ~>，<~，^^，| などのメソッドは，普通は，二項演算子として扱います。

演算子 ~> は，左辺を解析結果から捨てます。演算子 <~ は，右辺を解析結果から捨てます。したがって "(" ~> rep(expr) <~ ")" は，左丸括弧と rep(expr) と右丸括弧からなる列を受理して，rep(expr) の解析結果だけを返します。これは 0 回以上の式 (expression)の繰り返し (repetition) です。 expr の解析結果の型が Any ですから，rep(expr) の解析結果の型は List[Any] になります。 S 式のリストを表現するために Scala の List[Any] を使うならば，この解析結果をそのまま利用できます。このようにして lazy val list は Lisp のリストのパーサとなります。

(1 2 3) ⇒ List(1, 2, 3)

まゆげ演算子 ^^ は，左辺の解析結果を，右辺の関数に適用して，その戻り値を全体の解析結果とします。 ("'" ~> expr) ^^ (List('quote, _)) は，シングルクォートに続く式の解析結果を，右辺の関数に適用します。暗黙の仮引数 _ をもつ匿名関数 (List('quote, _)) は Symbol インスタンス 'quote と実引数値からなるリストを戻り値とします。このようにして lazy val quot は Lisp のクォート式のパーサになります。

'(1, 2, 3) ⇒ List('quote, List(1, 2, 3))

演算子 | は，ここでは左辺と右辺の選択を表します。まず左辺を試し，失敗したら右辺を試します。 stringLiteral (string literal, 文字列リテラル) はトレイト JavaTokenParsers で定義されています。 stringLiteral にマッチして得られた文字列は両端にダブルクォートが付いているので，まゆげ演算子右辺の匿名関数がそれを Java の String#substring メソッドでそぎ落とします。

"abc" ⇒ 両端のダブルクォートをそぎ落とした abc の３文字からなる文字列

正規表現で場合分けされた「英数字といくつかの記号からなる長さ１以上の列」に対しては，まず十進整数かどうか s.toLong メソッドを適用してみます。失敗して java.lang.NumberFormatException が投げられたときはシンボルと見なし， Symbol(s) で Symbol インスタンスにします。

123 ⇒ Long 値 123
123x ⇒ Symbol("123x")

この方法はシンボルとして 1+ のようなものを可能にするためです。一般的なプログラミング言語の識別子のようにシンボルを英字ではじまる英数字などと限定してよい場合， try - catch を使うのではなく，最初に場合分けするのが簡単でしょう。試しに書いてみてください。

このようにして lazy val expr は Lisp の S 式のパーサになります。

フィールド宣言に lazy val を使っているのは，相互に参照しあう構造を作為なしに自然に構築するためです。インスタンス構築時にはフィールドへの参照が確定するだけで，実際の値は，必要になったときはじめて，そしてその１回だけ評価されますから，フィールド間の相互参照的な構造を効率よく構築できます。 lazy val を def にかえても動作しますが，そうすると，無引数メソッドとして複数回評価され得ることになります。実験してみてください。

まゆげ演算子とは下記文献の Index p.713 で ^^ が result conversion, or "eyebrows" と説明されていることによります。

Martin Odersky, Lex Spoon, and Bill Venners: "Programming in Scala", 2008, ISBN 978-0-9815316-0-1

この本の表紙には石の階段があしらわれています。 scala とはイタリア語やラテン語で階段やはしごを意味する女性名詞です。わたしたち日本人がそのような性別で Scala を擬人化することを世界が期待しているかどうかは不明ですが ;-)，この石段本の表紙が Scala にふさわしいということは言えます。

シングルトン・オブジェクト Lisp に，このプログラムの main メソッドを置きます。これはコマンド行引数としてファイル名を一つとり，その内容を expr で解析し，結果を表示します。ただし，ファイル名が "-" ならば，(Unix の diff コマンドなどと同じく) 標準入力を対象とします。プログラムの使用例を示します。

$ scalac TinyLisp.scala
$ echo "(cons a (cons b '(x y z)))" | scala Lisp -
List('cons, 'a, List('cons, 'b, List('quote, List('x, 'y, 'z))))
$

main メソッドの定義では等号 = を使っていませんが， Scala でメソッド定義に等号を使わないことは，その戻り値の型を Unit，つまり「戻り値無し」と宣言したのと同じです。言い換えれば，等号を使って def main(args: Array[String]): Unit = {…} と書いたのと同じです。

2. 文字列表現への変換

S 式を構文解析して，Scala のデータ構造に変換するところまで出来ました。しかし，それを表示したとき，Scala のデータ構造の toString 結果のままでは S 式らしくありません。 S 式としての文字列の表現 (representation) を返す repr(e: Any): String を定義してみます。

object Lisp {
  def repr(e: Any): String = e match {
    case Nil => "nil"
    case List('quote, x) => "'" + repr(x)
    case (x: ::[_]) => "(" + x.map(repr).mkString(" ") + ")"
    case (x: String) => "\"" + x + "\""
    case (x: Symbol) => x.name
    case _ => e.toString
  }

  def main(args: Array[String]) {
    val reader = if (args(0) == "-") new InputStreamReader(System.in)
                 else new FileReader(args(0))
    val parsers = new SExprParsers
    val exp = parsers.parseAll(parsers.expr, reader).get
    println(repr(exp))
  }
}

ここで repr(e) の場合分けに現れている ::[_] は cons セルを表すクラスです。まゆげ ^^ がメソッド名であるように :: もれっきとしたクラス名です。型引数がワイルドカード _ ですから，任意の :: インスタンス，つまり，Nil でないあらゆる List インスタンスにマッチします。

Nil かどうか最初に場合分けをしていますから，::[_] と Nil の共通の抽象基底クラスである List[_] を ::[_] のかわりに使うこともできます。また，原理的には，::[_] のかわりに ::[Any] を使うこともできます。実際にそうするとどうなるか，ぜひ実験してみてください。

リストへの .map(repr) は，リストの各要素に repr を適用し，その戻り値をそれぞれ要素とする新しいリストを作ります。 .mkString(" ") はリストの各要素の toString による文字列を，あいだに " " をさしはさんで連結し，戻り値とします。

$ scalac TinyLisp.scala
$ echo "(cons a (cons b '(x y z)))" | scala Lisp -
(cons a (cons b '(x y z)))
$

case List('quote, x) => "'" + repr(x) の行を省くと，上記の例で '(x y z) ではなく (quote (x y z)) と表示されます。

3. アトムと基本５関数だけの eval 関数

ここまでで下ごしらえが済みましたから，いよいよ McCarthy の文献をもとに eval 関数に取りかかります。まず，さしあたり，アトムと基本５関数 (とクォート) だけを扱う eval 関数を書いてみます。

eval 関数は，第１引数として評価対象の S 式を，第２引数として評価時の環境 (environment) となる連想リスト (association list) を取ります。ここで連想リストとは，本来，シンボルとその変数値のペアからなるリストのことでした。

'((a . 212) (b . 611))

ここでは Scala らしく，Symbol と Any のタプルからなる List，つまり List[(Symbol, Any)] として連想リストを構成することにします。

List(('a, 212), ('b, 611))

簡潔さのために，type 宣言で List[(Symbol, Any)] に AList という別名を与えます。

object Lisp {
  type AList = List[(Symbol, Any)]      // Association List

  def eval(e: Any, a: AList): Any = e match {
    case car::cdr => car match {
      case 'quote =>
        val fst::Nil = cdr; fst

      case 'car =>
        val hd::tl = ev1arg(cdr, a); hd
      case 'cdr =>
        val hd::tl = ev1arg(cdr, a); tl
      case 'atom =>
        convBoolean(! ev1arg(cdr, a).isInstanceOf[::[_]])

      case 'cons =>
        val (x: Any, y: List[_]) = ev2args(cdr, a); x::y
      case 'eq =>
        convBoolean(ev2args(cdr, a) match {
          case (r: List[_], s: List[_]) => r eq s
          case (x, y) => x == y
        })
    }
    case 'nil => Nil
    case 't => 't
    case (variableName: Symbol) => fetch(variableName, a)
    case _ => e
  }

  def convBoolean(e: Boolean) = if (e) 't else Nil
  def fetch(s: Symbol, a: AList) = (a find (_._1 eq s)).get._2

  def ev1arg(e: List[Any], a: AList): Any = {
    val fst::Nil = e
    eval(fst, a)
  }

  def ev2args(e: List[Any], a: AList): (Any, Any) = {
    val fst::snd::Nil = e
    val x = eval(fst, a)
    val y = eval(snd, a)
    (x, y)
  }

クラス :: は case class ですから，match 式のパターンに使うことができます。 case car::cdr => によって， cons セルの car 部と cdr 部をそれぞれ変数 car と cdr に分解して参照できます。この書き方はプログラムを (恐ろしいほど!!) 簡潔にします。

このコードでは car, cdr のほか，hd (head), tl (tail) や fst (first), snd (second) といった変数名も使っています。ただし snd はリストの第２要素，つまり Lisp でいう cadr (cdr の car) にあたる部分を表すのに使っています。

評価対象が car::cdr パターンにマッチするとき，先頭要素 car を，quote または基本５関数 car, cdr, atom, cons, eq のどれかと合致するシンボルとして場合分けします。基本５関数ならば，cdr の各要素に (ev1arg メソッドまたは ev2args メソッドで) eval メソッドを適用してから操作をします。

評価対象がアトムの場合，nil シンボルならば空リスト Nil を， t シンボルならば t シンボル自身を評価結果とします。それ以外のシンボルならば，連想リスト a からそのシンボルに対応する変数値を (fetch メソッドで) 取り出します。シンボルでないとき，そのまま値を返します。数や文字列がこれに該当します。

fetch の定義本体にある a find (_._1 eq s) は，a find ((x: (Symbol, Any)) => x._1 eq s) の略記法です (ただし，x はほかで使われていない適当な名前とします)。 find は，左辺のリストの各要素を先頭から順に右辺の関数に適用して，true が得られた最初の要素を結果の値とします (正確にはそれを Some でくるんだ Option 値を返します)。左辺の型から，その要素の型が推論できますから，右辺の仮引数に型宣言は不要です。 a find ((x) => x._1 eq s) とできます。仮引数は１回しか出現していませんから，さらに簡略化して a find (_._1 eq s) とできます。 _1 はタプルの第１要素をとりだします。 eq は参照型の値に対して，同じ参照かどうか調べます。Java の == と同じです。

main メソッドでは，テスト用に a が 212， b が 611 となるダミーの環境を手作りして，eval メソッドに渡すことにします。

  def main(args: Array[String]) {
    val reader = if (args(0) == "-") new InputStreamReader(System.in)
                 else new FileReader(args(0))
    val parsers = new SExprParsers
    val exp = parsers.parseAll(parsers.expr, reader).get
    println(repr(exp))
    val env = List(('a, 212), ('b, 611)) // for example
    println(repr(eval(exp, env)))
  }
}

実行例です。

$ scalac TinyLisp.scala
$ echo "(cons a (cons b '(x y z)))" | scala Lisp -
(cons a (cons b '(x y z)))
(212 611 x y z)
$

4. 条件式と関数適用を追加した eval 関数

式が条件式 (conditional expression) (cond (p₁ e₁) … (p_n e_n)) かどうかは，式の car が 'cond シンボルかどうかで切り分けます。 evcond メソッドに cdr と連想リスト a を渡して評価します。

もしも伝統を無視してよければ， conditional expression は，条件式ではなく，条件付き式 と直訳すべきでしょう。通俗的には，おおむね例外なく「条件式」は condition (条件) の意味で使われています。 conditional expression の意味での「条件式」は，普通一般の用語としては，ほぼ死語です。本稿では，伝統を尊重して，あえて死語の意味で「条件式」を使っています。注意してください……といっても，ここでしか言及していませんから特に気にすることはありません。忘れてください >_<

式の car が quote にも基本５関数にも cond にも該当しないシンボルならば，その式を，シンボルの名前の ユーザ定義関数 (user-defined function) の適用と見なします。アトムの場合分けの中でシンボルに対する変数値を取り出したのと同じように，連想リストから値を (fetch メソッドで) 取り出します。そして，取り出した値と実引数並びから新しいリスト fun::cdr を構築し，eval することで関数適用を行います。

つまり，この Lisp では，変数に対する名前空間と，ユーザ定義関数に対する名前空間は同一です。いわゆる Lisp-1 です。

式の car がリストであるような場合は二つあります。LAMBDA 式の適用と LABEL 式の適用です。どちらもある種の関数適用です。 car の car 部である caar が 'lambda と 'label のどちらのシンボルかで場合分けします。

LAMBDA 式の適用 ((lambda (v₁ … v_n) body) e₁ … e_n) は次のように評価します。仮引数並び (v₁ … v_n) を取り出し，asInstanceOf を使って List[Symbol] にキャストします。実引数並び (e₁ … e_n) に該当する cdr に map (eval(_, a)) を適用し，各要素を評価したリスト evlis を得ます。 List[Symbol] 型の仮引数並び paramSymbols と，評価済み実引数の並び evlis を zip して，連想リスト a の頭に ::: 演算子で連結します。

List('x, 'y, 'z) zip List(1, 2, 3)
  ⇒  List(('x,1), ('y,2), ('z,3))  // zip の例

List(('x,1), ('y,2), ('z,3)) ::: List(('a,212), ('b,611))
  ⇒ List(('x,1), ('y,2), ('z,3), ('a,212), ('b,611))  // ::: の例

こうして作った連想リスト env は，仮引数のシンボルから実引数の値へのマッピングをもった新しい環境です。この環境のもとで LAMBDA 式の本体である body を eval(body, env) で評価します。

  def eval(e: Any, a: AList): Any = e match {
    case car::cdr => car match {
      [quote と基本５関数の場合分けを省略]

      case 'cond => evcond(cdr, a)
      case (functionName: Symbol) =>
        val fun = fetch(functionName, a); eval(fun::cdr, a)

      case caar::cdar => caar match {
        case 'lambda => {
          val params::body::Nil = cdar
          val paramSymbols = params.asInstanceOf[List[Symbol]]
          val evlis = cdr map (eval(_, a))
          val env = (paramSymbols zip evlis) ::: a
          eval(body, env)
        }
        case 'label => {
          val fun::lambdaExp::Nil = cdar
          val exp = lambdaExp::cdr
          val funSymbol = fun.asInstanceOf[Symbol]
          val env = (funSymbol, car) :: a
          eval(exp, env)
        }
      }
    }
    [アトムの場合分けを省略]
  }

LABEL 式の適用 ((label f (lambda (v₁ … v_n) body)) e₁ … e_n) とは，シンボル f の値が LABEL 式 (label f (lambda (v₁ … v_n) body)) であるような環境での，LAMBDA 式の適用 ((lambda (v₁ … v_n) body) e₁ … e_n) と同じです。上記の実装は，この定義をそのまま素直に実行しています。

ここでシンボルの値となるラベル式の中にシンボル自身が含まれていることに注意してください。循環的な構造になっています。これにより LABEL 式で再帰的な関数を定義できます。

evcond の定義を示します。

  def evcond(e: List[Any], a: AList): Any = {
    val hd::tl = e
    val condition::body::Nil = hd
    if (eval(condition, a) == Nil)
      evcond(tl, a)
    else
      eval(body, a)
  }

main メソッドでは，空の環境，つまり Nil を eval に渡します。

  def main(args: Array[String]) {
    val reader = if (args(0) == "-") new InputStreamReader(System.in)
                 else new FileReader(args(0))
    val parsers = new SExprParsers
    val exp = parsers.parseAll(parsers.expr, reader).get
    println(repr(exp))
    println(repr(eval(exp, Nil)))
  }

実行例です。

$ scalac TinyLisp.scala
$ cat find-first.l
((label find-first
        (lambda (x)
          (cond ((atom x) x)
                (t (find-first (car x))))))
 '((a b) c))
$ scala Lisp find-first.l
((label find-first (lambda (x) (cond ((atom x) x) (t (find-first (car x)))))) '(
(a b) c))
a
$

ここではアトムが見つかるまで再帰的にリストの car を取り出し続ける関数を LABEL 式で定義し，リスト ((a b) c) に適用しています。期待どおり，結果として a が得られています。

5. 仕上げ

仕上げとして，このプログラムが何もので何を参考にしたのかコメントとして書きます。 package 宣言を追加して，全体を esc.tinylisp パッケージに置きます。いくつかの整数演算 (+, -, *, <) を追加します。

このパッケージ名は便宜的なものです。正式には，Java のライブラリ・システムと破綻なく統合できるように jp.co.oki… のようなパッケージにします。追加の整数演算は，組込み関数の拡張方法を示すサンプルと考えてください。

最後ですから全リストを示します。

// A Tiny Lisp Interpreter in Scala 2.7.7 - 2.8.0 by (鈴) H21.12/11

// Cf. J. McCarthy: A Micro-Manual for Lisp - Not the Whole Truth,
//     ACM SIGPLAN Notices, Vol. 13, No. 8, August 1978, pp.215-216

package esc.tinylisp

import scala.util.parsing.combinator._
import java.io.{FileReader, InputStreamReader}

class SExprParsers extends JavaTokenParsers {
  lazy val list: Parser[List[Any]] = "(" ~> rep(expr) <~ ")"
  lazy val quot: Parser[List[Any]] = ("'" ~> expr) ^^ (List('quote, _))
  lazy val expr: Parser[Any] = {
    list | quot |
    stringLiteral ^^ (s => s.substring(1, s.length() - 1)) |
    """[a-zA-Z_0-9\+\-\*\<]+""".r ^^
    (s => try {s.toLong} catch {case ex: NumberFormatException => Symbol(s)})
  }
}

object Lisp {
  type AList = List[(Symbol, Any)]      // Association List

  val MINUS_SYMBOL = Symbol("-")        //  '- causes a syntax error.
  val STAR_SYMBOL = Symbol("*")         // So does '*

  def eval(e: Any, a: AList): Any = e match {
    case car::cdr => car match {
      case 'quote =>
        val fst::Nil = cdr; fst

      case 'car =>
        val hd::tl = ev1arg(cdr, a); hd
      case 'cdr =>
        val hd::tl = ev1arg(cdr, a); tl
      case 'atom =>
        convBoolean(! ev1arg(cdr, a).isInstanceOf[::[_]])

      case 'cons =>
        val (x: Any, y: List[_]) = ev2args(cdr, a); x::y
      case 'eq =>
        convBoolean(ev2args(cdr, a) match {
          case (r: List[_], s: List[_]) => r eq s
          case (x, y) => x == y
        })

      case '+ =>
        val (r: Long, s: Long) = ev2args(cdr, a); r + s
      case MINUS_SYMBOL =>
        val (r: Long, s: Long) = ev2args(cdr, a); r - s
      case STAR_SYMBOL =>
        val (r: Long, s: Long) = ev2args(cdr, a); r * s
      case '< =>
        val (r: Long, s: Long) = ev2args(cdr, a); convBoolean(r < s)

      case 'cond => evcond(cdr, a)
      case (functionName: Symbol) =>
        val fun = fetch(functionName, a); eval(fun::cdr, a)

      case caar::cdar => caar match {
        case 'lambda => {
          val params::body::Nil = cdar
          val paramSymbols = params.asInstanceOf[List[Symbol]]
          val evlis = cdr map (eval(_, a))
          val env = (paramSymbols zip evlis) ::: a
          eval(body, env)
        }
        case 'label => {
          val fun::lambdaExp::Nil = cdar
          val exp = lambdaExp::cdr
          val funSymbol = fun.asInstanceOf[Symbol]
          val env = (funSymbol, car) :: a
          eval(exp, env)
        }
      }
    }
    case 'nil => Nil
    case 't => 't
    case (variableName: Symbol) => fetch(variableName, a)
    case _ => e
  }

  def convBoolean(e: Boolean) = if (e) 't else Nil
  def fetch(s: Symbol, a: AList) = (a find (_._1 eq s)).get._2

  def ev1arg(e: List[Any], a: AList): Any = {
    val fst::Nil = e
    eval(fst, a)
  }

  def ev2args(e: List[Any], a: AList): (Any, Any) = {
    val fst::snd::Nil = e
    val x = eval(fst, a)
    val y = eval(snd, a)
    (x, y)
  }

  def evcond(e: List[Any], a: AList): Any = {
    val hd::tl = e
    val condition::body::Nil = hd
    if (eval(condition, a) == Nil)
      evcond(tl, a)
    else
      eval(body, a)
  }

  def repr(e: Any): String = e match {
    case Nil => "nil"
    case List('quote, x) => "'" + repr(x)
    case (x: ::[_]) => "(" + x.map(repr).mkString(" ") + ")"
    case (x: String) => "\"" + x + "\""
    case (x: Symbol) => x.name
    case _ => e.toString
  }

  def main(args: Array[String]) {
    val reader = if (args(0) == "-") new InputStreamReader(System.in)
                 else new FileReader(args(0))
    val parsers = new SExprParsers
    val exp = parsers.parseAll(parsers.expr, reader).get
    println(repr(exp))
    println(repr(eval(exp, Nil)))
  }
}

下記は MacBook Pro 15" (2GHz Core Duo, 2GB DDR2, Mac OS X 10.5.8, Java 1.5.0_22) 上の scala 2.7.7 による実行結果です。

$ scalac TinyLisp.scala
$ cat tak.l
((label tak
        (lambda (x y z)
          (cond ((< y x)
                 (tak (tak (- x 1) y z)
                      (tak (- y 1) z x)
                      (tak (- z 1) x y)))
                (t z))))
 18 12 6)
$ time scala esc.tinylisp.Lisp tak.l
((label tak (lambda (x y z) (cond ((< y x) (tak (tak (- x 1) y z) (tak (- y 1) z
 x) (tak (- z 1) x y))) (t z)))) 18 12 6)
7

real	0m0.946s
user	0m0.805s
sys	0m0.094s
$

tinylisp-211211.zip: TinyLisp.scala, find-first.l, tak.l: md5: cf5e67e6bc90de7b633fb88a4b148067

おわりに

コメント，空行込みで 125 行の Scala プログラムとして， tak 関数を評価できるだけの完成度の Lisp インタープリタを作成しました。 Lisp インタープリタの製作という，ある程度複雑な，ある意味おなじみの課題の Scala による解答例を読むことで，読者は Scala とはどんな言語なのか，より実感をもてたと思います。

といいますか，製作者である自分自身，そう実感しました。;-)

エラー処理や対話的セッションなどの実装や言語仕様の改良は読者への課題とします。

本稿で全く触れていない Scala の特徴として，並列処理プログラミングの容易さがあります。 evlis 値の計算，つまり実引数並びに対する eval 関数の map 演算が，従来，Lisp 処理系で並列化可能な箇所として考えられてきたそうです。今，Scala を使えば，そういった並列処理の実験を昔の基準からは考えられないほど簡単に行えるはずです。もちろん，どれをどこまで並列化すべきかは自明なことではないでしょう。どんなものになるか，Scala に慣れてきたら考えてみてください。

ちなみに McCarthy の文献では，evlis は再帰的な演算を行う LABEL 式でした。

   ((LABEL
     EVLIS
     (LAMBDA (U A)
             (COND ((NULL U) NIL)
                   (T (CONS (EVAL (CAR U) A)
                            (EVLIS (CDR U)
                                     A))))))
    (CDR E) 
    A)

この LABEL 式の適用を Scala に翻訳するとこうなります。ただし，上記で (CDR E) の戻り値にあたる値を変数 cdr がもっているとします。

  evlis(cdr, a)
  ……
  def evlis(args: List[Any], a: AList): List[Any] = args match {
    case Nil => Nil
    case hd::tl => eval(hd, a) :: evlis(tl, a)
  }

しかし，これは結局，下記の式と同じです。本処理系では，この式の結果の値を List[Any] 型の変数 evlis にセットしています。

  cdr map (eval(_, a))

先頭へ