はじめに

数カ月前からJuliaをはじめた初心者です。新しい言語を学ぶときは、その言語を使ってLispを実装することにしています。C、C++、Delphi、Awk、C#、Javaはそれで勉強しました。Juliaについても同じやり方をしてみました。
ソースはsaka1029/JuLisp: A simple Lisp by Juliaにあります。テストコードを除くと約300行程度です。

環境

開発環境は以下のとおりです。IDEは特に使っていません。

Windwos10
Julia1.3
Vim

プロジェクトはgenerateコマンドで作成します。

d:\IdeaProjects$ julia -q           (Juliaを起動し、`]`を押してパッケージモードに入る)
(v1.3) pkg> generate JuLisp         (パッケージのひな形を作成する)
Generating project A:
    JuLisp\Project.toml
    JuLisp/src/JuLisp.jl

(v1.3) pkg>                         (^Dを押してJuliaを抜ける)

生成されたJuLisp.jlに実装コードを記述しました。
テストコードはプロジェクトディレクトリの下にtestディレクトリを作成し、その下のruntests.jlに記述します。
テストはjuliaコマンドのパッケージモードのtestコマンドで実行できます。

d:\IdeaProjects\JuLisp$ julia -q --project    (Juliaコマンドを実行して`]`でパッケージモードに張ります)
(JuLisp) pkg> test                            (testコマンドでテストを実行します)
   Testing JuLisp
 Resolving package versions...
Test Summary: | Pass  Total
LispSymbol    |    3      3
Test Summary: | Pass  Total
NIL           |    4      4
Test Summary: | Pass  Total
T             |    4      4
Test Summary: | Pass  Total
LispSymbol    |    4      4
Test Summary: | Pass  Total
Pair          |   14     14
Test Summary: | Pass  Total
env           |    5      5
Test Summary: | Pass  Total
evaluate      |    6      6
Test Summary: | Pass  Total
Closure       |    5      5
Test Summary: | Pass  Total
repl          |    1      1
Test Summary: | Pass  Total
append        |    1      1
   Testing JuLisp tests passed

(JuLisp) pkg>

実装するLispの概要

単純化したいので基本的に純LISPとします。Schemeと同様に関数名と変数名の名前空間は単一とします(1-Lisp)。スコープもSchemeと同様にレキシカルスコープとします。実装する関数はeq、null、atom、car、cdr、cons、listとし、特殊形式はquote、if、define、lambdaとします。

実装した型

実装した型は以下の７つです。

Object

すべてのLispオブジェクトを表す抽象型です。Union型を使うこともできますが、ここではabstract typeとして実装します。

Sym

Lispシンボルの型です。JuliaのSymbolを要素として持つstructとして実装します。

Pair

データのペアを表す型です。値を書き換える関数（rplacaなど）は実装しないのでimmutableなstructとします。

Env

変数束縛を保持する型です。実際にはbindメンバに連想リスト((var₀ . val₀) (var₁ . val₁) ...)を持たせます。immutableなPairを使っているので値を更新することはできません。

Applicable

組み込み関数や特殊形式を実現する型です。applyメンバはこれらをJuliaで実装した関数を保持します。

Clausure

ユーザ定義関数を実現するクロージャの型です。以下の要素を持ちます。

parms 引数パラメータ名のリストです。
body 関数の本体です。
env クロージャとして定義された時点での環境です。レキシカルスコープを実現するために必要となります。
apply クロージャの本体を実行するときに呼び出される関数です。この関数は実引数を順に評価してparmsにバインドした後、bodyで定義された本体を呼び出します。

LispReader

文字列のストリームをLispの式に変換するための型です。inメンバは入力するストリームです。chメンバは1文字先読みするためのバッファです。

readの実装

先に述べたLispReaderを使ってストリームからLispの式を取り出すBase.read(r::LispReader)を実装します。

printの実装

テストやデバッグを考えるとJuliaのprint関数で簡単にLispの式を表示できると便利です。

Julia> c = Pair(Sym(:a), Sym(:b))
Julia> print(c)
(a . b)

そこで、Base.show(io::IO, s::Sym)やBase.show(io::IO, p::Pair)という形で実装します。

evalの実装

Envを使ってLispオブジェクトを評価するevaluate(s::Sym, e::Env)やevaluate(p::Pair, e::Env)を実装します。
evaluate(s::Sym, e::Env)はeが持っている連想リストの中からシンボルsを見つけて、対応する値を返します。実際の定義はこうなります。

evaluate(s::Sym, e::Env) = get(e, s)

get(e::Env, s::Sym)の定義はこうです。

function find(env::Env, variable::Sym)
    bind = env.bind
    while bind != NIL
        if variable == bind.car.car
            return bind.car
        end
        bind = bind.cdr
    end
    error("Variable $variable not found")
end

get(env::Env, var) = find(env, var).cdr

evaluate(p::Pair, e::Env)はpの先頭要素をevaluateして、その結果にpの残りの要素(引数)をapplyします。実際の定義はこうなります。

function evaluate(p::Pair, e::Env)
    a = evaluate(p.car, e)
    a.apply(a, p.cdr, e)
end

Envの初期化

組み込み関数や特殊形式を組み込んだ形のEnvを作る関数は以下のとおりです。

function defaultEnv()
    e = env()
    define(e, NIL, NIL)
    define(e, T, T)
    define(e, symbol("atom"), procedure(a -> predicate(atom(a.car))))
    define(e, symbol("null"), procedure(a -> predicate(null(a.car))))
    define(e, symbol("eq"), procedure(a -> predicate(a.car == a.cdr.car)))
    define(e, symbol("car"), procedure(a -> a.car.car))
    define(e, symbol("cdr"), procedure(a -> a.car.cdr))
    define(e, symbol("cons"), procedure(a -> Pair(a.car, a.cdr.car)))
    define(e, symbol("list"), procedure(a -> a))
    define(e, QUOTE, special((s, a, e) -> a.car))
    define(e, symbol("lambda"), special((s, a, e) -> closure(a.car, a.cdr, e)))
    define(e, symbol("define"), special((s, a, e) -> define(e, a.car, evaluate(a.cdr.car, e))))
    define(e, symbol("if"), special(lispIf))
    return e
end

REPL(Read Eval Print Loop)

REPLはrepl()関数として実装しました。以下はその実行例です。append関数を定義して実行しています。

d:\IdeaProjects\JuLisp$ julia -q --project
julia> using JuLisp

julia> repl()

JuLisp> (define append (lambda (a b) (if (null a) b (cons (car a) (append (cdr a) b)))))
Closure{(a b), ((if (null a) b (cons (car a) (append (cdr a) b))))}
JuLisp> (append '(a b c d e) '(f g h i j))
(a b c d e f g h i j)
JuLisp> quit
Base.TTY(Base.Libc.WindowsRawSocket(0x0000000000000284) open, 0 bytes waiting)

julia>

quitで終了します。エラー処理を何もしていないので、実行中にエラーがあると終了します。

最後に

はじめての言語なので実装に1カ月ほどかかってしまいましたが、何とかREPLまでたどり着くことができました。最近はJavaのようなオブジェクト指向言語ばかり使っているせいか、必要なAPIを探すのに苦労しました。
Javaならば必要とする機能を持っていそうなクラスをパッケージ名とクラス名で見当をつけて、そのメソッドを探せば必要なメソッドのAPIにたどり着くのですが、Juliaの場合、型名で検索しても、その型を操作するメソッドは見つからなかったりします。例えばStringのヘルプは以下のようになっています。

help?> String
search: String string StringIndexError Cstring Cwstring bitstring SubString

  String(v::AbstractVector{UInt8})

  Create a new String object from a byte vector v containing UTF-8 encoded characters.
  If v is Vector{UInt8} it will be truncated to zero length and future modification of
  v cannot affect the contents of the resulting string. To avoid truncation use
  String(copy(v)).

  When possible, the memory of v will be used without copying when the String object
  is created. This is guaranteed to be the case for byte vectors returned by take! on
  a writable IOBuffer and by calls to read(io, nb). This allows zero-copy conversion
  of I/O data to strings. In other cases, Vector{UInt8} data may be copied, but v is
  truncated anyway to guarantee consistent behavior.

  ────────────────────────────────────────────────────────────────────────────────────

  String(s::AbstractString)

  Convert a string to a contiguous byte array representation encoded as UTF-8 bytes.
  This representation is often appropriate for passing strings to C.

julia>

文字列の連結やsubstringはどうすればいいの？となってしまいます。
しかし、クラスという概念を持ち込まずにCLOSのようにジェネリック関数のみで実現しているので、Javaのオブジェクト型とプリミティブ型の区別がない点がJuliaのいいところだと思います。