ElixirでLisp1.5を作ったお話

#三つ子の魂百まで
昭和58年だったと思います。まだ20代前半の頃でした。中西正和先生のLispの本を買いました。まるで理解できませんでした（苦笑）。当時の版はM式で書かれていました。わからないながらもLispと付き合っていたら楽しくて、あれから30年以上経った今もLispに対する興味は尽きません。Elixirのモダンな機能を活かして初期LispであるLISP1.5相当をElixirで書いてみました。懐かしさもあってM式も扱えるようにしてあります。

#トークンナイズとパース
ElixirのString.splitを使うと楽ができます。Lispでのデリミタはスペースです。スペースでsplitをかければトークンに分解できます。カッコもデリミタです。これはreplaceをつかってスペースを入れるように変換しておいてから、splitをかければ分解できます。この方法でトークンナイズは手抜きをしています。

String.split("(+ 1 2)")
["(+", "1", "2)"]

"(" を　" ( " に変換しておけば・・・

String.split(" ( + 1 2 ) ")
["(", "+", "1", "2", ")"]

トークンに分解してしまったら、リストに変換していくだけです。再帰構造をしているLispのプログラムのパースは再帰構造になります。

#インタプリタ
lisp1.5プログラマーズ・マニュアルにできるだけ忠実にElixirに翻訳しています。パターンマッチングを活用しています。

#M式の不思議
Lisp1.5のマニュアルはM式で記述されていました。現在、Lispで主流のS式を見慣れている人にとっては違和感があることでしょう。まったくLispに馴染みのない人にとってはLispって昔はけっこうまともだったんですね、という感想を持つようです。

Lisp 1.5 in Elixir M-expression in sequential
? cons[A;B]
(A . B)
? length[(A B C)]
3

起動時のオプションによりS式もOKにしてあります。

Lisp 1.5 in Elixir S-expression
S? (cons 'A 'B)
(A . B)
S? (length '(A B C))
3
S?

#並列処理
折角、Elixirで作っているのですから、Elixirならではの技を入れたいところです。並列処理をいれてあります。1970年代から1980年代にかけて大阪大学で研究されていたEVLISというLispマシンにヒントを得て、Elixirのspawnにより並列実行させています。evalをまるごとspawnで起動しています。再帰関数について再帰する場合もspawnを使ってしまうと非効率です。各並列動作の中での再帰は普通に逐次処理をしています。

(foo (bar 1)(bar 2)(bar 3))

という関数呼び出しがある場合、(bar 1), (bar 2), (bar 3) を並列に実行しています。フィボナッチ数の素朴再帰定義のような場合に効率がよくなります。

フィボナッチ数の素朴な再帰定義で計測すると以下のように高速になっていました。

fib[n] = [lessp[n;2]->n;
          T->plus[fib[sub1[n]];fib[difference[n;2]]]]

逐次処理の場合

mix elxlisp seq
Lisp 1.5 in Elixir in sequential
? load["test.meta"]
T
? time[fib[30]]
"time: 3413831 micro second"
"-------------"

832040
? quit[]
"goodbye"

並列処理の場合

mix elxlisp para
Lisp 1.5 in Elixir in parallel
? load["test.meta"]
T
? time[fib[30]]
"time: 2111035 micro second"
"-------------"
832040
?

#コンパイラ
ちゃんとしたコンパイラを作ろうとするとかなり手間暇がかかるのですけど、Elixirの動的コンパイルの機能を使って簡単に済ませました。Lispコードを等価なElixirのコードに変換する方式です。次のように変換されます。

S式モード

(defun foo (x)
  (plus x x))

(defun bar (x)
  (cond ((eq x 1) 1)
        (t 2)))

(defun tarai (x y z)
  (cond ((eqlessp x y) y)
        (t (tarai (tarai (sub1 x) y z)
                  (tarai (sub1 y) z x)
                  (tarai (sub1 z) x y)))))

変換されたElixirコード
見易くするためにformatしてあります。

defmodule Elxfunc do
  def is_compiled(x) do
    Enum.member?([:foo, :bar, :tarai], x)
  end

  def primitive([:foo, x]) do
    foo(x)
  end

  def primitive([:bar, x]) do
    bar(x)
  end

  def primitive([:tarai, x, y, z]) do
    tarai(x, y, z)
  end

  def foo(x) do
    x + x
  end

  def bar(x) do
    cond do
      x == 1 -> 1
      true -> 2
    end
  end

  def tarai(x, y, z) do
    cond do
      x <= y -> y
      true -> tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
    end
  end
end

予め空のElxfuncモジュールを定義しておきます。これを動的に上書きコンパイルします。Codeモジュールのcompile_stringを利用しています。

#コンパイラでの並列処理
これはまだ実装できていません。上記のtarai(12,6,0)程度の場合ですとプロセス生成のコストの方が高くつきます。人間がコンパイルオプションを与えて並列処理のコードを生成するのかどうか、を指定したらいいのか、と思いつつまだ手付かずです。

#Elixirで実装出来なかったこと
Lispは最初のPure-Lispだったころは関数型プログラミングであったと思います。しかし、Lisp1.5においては既にsetqのような参照透明性を壊すものが持ち込まれています。また、リストの破壊的な操作であるnconcのようなものも取り込まれています。Elixirは関数型プログラミング言語でありデータはイミュータブルです。nconcは実装できませんでした。

putprop、getによる属性リストも1.5で取り込まれています。インタプリタにおいては引数に属性リスト用のデータを持たせています。しかし、コンパイラでは大域変数を持たせることができず、対応できていません。

#Elixirに未来を託して
古いLISP1.5の実装を通して当時のマッカーシー博士の思考を辿ったような気分でした。1.5で既にsetqやprogのようなものが導入されています。当時の希少な計算機リソースにおける妥協だったのだろうと思います。λ計算理論をベースにしたLispはその後、実用を目指し、理論からは離れていくこととなります。

面白いことにElixirは古いPureなLispと似ています。Elixirは関数型言語でありイミュータブルです。破壊的なデータ操作を持ちません。Elixirは豊富なライブラリを持ち実用指向でありながら、初期のLispに通ずる理論的なところが多いのは関数型プログラミング言語だからでしょう。マッカーシー博士はElixirみたいなのを創りたかったのではないかなぁ。LISP2は未完に終わりましたがElixirとよく似ています。

いよいよ並列の時代に入りました。Elixirは並列の時代の牽引役であると私は思っています。奇妙なことにその並列の時代の最先端をいくElixirが古いLispと似ています。面白いものです。

#ソース
GitHubにおいてあります。
https://github.com/sasagawa888/Elxlisp