Zenn
😴

Zig で Lisp を書いてみた

2024/12/23に公開
lisp
Zig
tech

Overview

クロスマート・テック Advent Calendar 2024 23日目の記事です🎅

Zig 学習の第二弾として、比較的実装が容易で、言語学習に良いとされている Lisp インタプリタを書いてみようと思います。その性質上、Lisp には多くの方言（私は Common Lisp が好きで、処理系は SBCL を使います）がありますが、今日広く使われる Lisp には以下のようなものがあります

今回は、Zig の学習ですので Lisp の一部の機能だけを持つ小さな実装となります🫎

Lisp を書いていると、昨今のモダンなインタプリタ （例えば Python や JavaScript など）は全て構文糖衣された Lisp に見えてくるものです。また、思考は言語に依存しており、Lisp を書くことで、思考は Lisp となり、やがては世界の全てを理解するに至るのです。それでは Zig と共に Lisp の世界へ行ってみましょう

Source Code

ご自由にどうぞ

https://github.com/keix/tiny-lisp

Tested Environment

Tested with Zig 0.14.0 on Gentoo Linux, Kernel 6.6.32

Specification

「FizzBuzz が動作する」事が要件です🐤

(define i 1)
(while (<= i 100)
    (cond 
        (and (= (mod i 3) 0) (= (mod i 5) 0)) (print "FizzBuzz")
        (= (mod i 3) 0)                       (print "Fizz")
        (= (mod i 5) 0)                       (print "Buzz")
        #t                                    (print i))
    (set! i (+ i 1)))

基本的なデータ型とリスト:

  • Atom: 数値、シンボル、文字列、真偽値
  • List: Atomまたは他のListを要素として持つリスト

パーサ:

  • 入力文字列をパースし、抽象構文木（AST）を構築
  • 数値、文字列、シンボル、リストのパース
  • 真偽値リテラル(#t, #f)のパース
  • エラーハンドリング（構文エラー、括弧の不一致など）
  • ファイルからの Lisp コードの読み込み

組み込み関数:

  • 算術演算（+, -, *, /, mod）
  • 比較演算（=, <=, >=）
  • 論理演算（and）
  • 条件分岐（if, cond）
  • 変数定義と代入（define, set!）
  • ループ（while）
  • 出力（print)

環境とスコープ:

  • 変数の管理と名前解決をサポートする環境（Environment）
  • レキシカルスコープ（関数の引数、ローカル変数）

エラーハンドリング:

  • パースエラーと評価エラーをハンドリング
  • エラーメッセージの生成と表示

TODO:

  • マクロ
  • クロージャ/ラムダ式
  • ガベージコレクション
  • REPL

Implementation

この小さな処理系は以下の様に動作します

パース:

メインプログラムがパーサーにソースコードを渡して処理を開始し、パーサーは入力を解析する事でASTを構築します

入力の種類に応じて2つの処理パスに分岐：

  • アトムの処理：数値、シンボル、文字列などの基本要素を解析
  • リストの処理：括弧で囲まれた式を解析し、要素を順次追加

例として、以下の単純なLispプログラムから生成したASTは次の様なものです

(* (+ 1 2) (- 3 4))

LispValue.List(
    [
        LispValue.Atom(Symbol("*")),
        LispValue.List(
            [
                LispValue.Atom(Symbol("+")),
                LispValue.Atom(Number(1)),
                LispValue.Atom(Number(2))
            ]
        ),
        LispValue.List(
            [
                LispValue.Atom(Symbol("-")),
                LispValue.Atom(Number(3)),
                LispValue.Atom(Number(4))
            ]
        )
    ]
)

評価:

メインプログラムが評価器にASTと環境を渡して実行し、評価器は入力の種類に応じて処理パスに分岐：

  • アトムの評価：シンボルの場合は環境から値を取得
  • リストの評価：組み込み関数を実行し、各引数を順次評価

評価結果を返却

クリーンアップ:

メインプログラムがASTのメモリ解放を開始
再帰的にデータ構造を辿りながら、確保したメモリを解放

  • アトムの場合：必要に応じて文字列などを解放
  • リストの場合：各要素を解放後、リスト自体を解放

すべてのメモリリソースが適切に解放されたことを確認

Getting Started

以下コマンドでソースコードをダウンロード出来ます

git clone git@github.com:keix/tiny-lisp.git
cd tiny-lisp

以下コマンドでコンパイルして実行します

zig build
./zig-out/bin/lisp script/fizzbuzz.lisp

Special Thanks

I would like to express my deepest gratitude to:

Discussion