Go to Qiita Advent Calendar 2024 Top
LoginSignup
6
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@saka1029(saka1029)

JuliaによるLispの実装

Posted at

#はじめに

数カ月前から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とします。

#実装した型

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

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

6
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
5

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?