JuliaによるLispの実装

#はじめに

数カ月前からJuliaをはじめた初心者です。新しい言語を学ぶときは、その言語を使ってLispを実装することにしています。C、C++、Delphi、Awk、C#、Javaはそれで勉強しました。Juliaについても同じやり方をしてみました。
ソースは[saka1029/JuLisp: A simple Lisp by Julia](https://github.com/saka1029/JuLisp)にあります。テストコードを除くと約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](https://ja.wikipedia.org/wiki/%E7%B4%94LISP)とします。Schemeと同様に関数名と変数名の名前空間は単一とします(1-Lisp)。スコープもSchemeと同様にレキシカルスコープとします。実装する関数はeq、null、atom、car、cdr、cons、listとし、特殊形式はquote、if、define、lambdaとします。


#実装した型

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/78427/f523d47f-b0c6-7269-a7bc-e401e463dead.png)

##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
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`を見つけて、対応する値を返します。実際の定義はこうなります。

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

```julia
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`します。実際の定義はこうなります。

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

#Envの初期化

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

```julia
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`関数を定義して実行しています。

```Lisp
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のいいところだと思います。