オレオレ Lisp 案

※この記事は頻繁に更新される可能性があります。
(ここの仕様通りのオレオレ Lisp は着々と実装が進んでおります。いずれ進捗状況も報告できればと。)

オレオレ Lisp を実装するにあたって、特徴的な仕様を書き留めていく忘備録です。
最終的には Lisp だけで、リアルタイム3Dゲームが実装出来る事が目標です。
当面の目標はセルフホスティング出来る最小の実装を作る事です。
セルフホストは Lisp コードをバイトコードへコンパイルし、バイトコードを C のソースにトランスレートする事で実現します。

なぜバイトコードか？

Lisp は全ての関数が何らかの値を返す事になっているが、whileやifやcond(C のswitch文に近い)も例外ではない。
whileの戻り値は常にnil(JavaScript のnullに近い)を返す為、戻り値を使う事はほぼ無いと言えるが、逆にifやcondに関しては戻り値を使う事は多い。
これに関しては C の 3 項演算子を使ったり(これはかなり汚いコードになる…)、GNU 拡張を使ったり(こっちは綺麗なコードになるが常に使えるとは限らない)すれば何とかなるが、クロージャーの実装を行う場合は非常に込み入った C のコードを出力しなければならず、そんなコードを作成するのはとても大変だ。
しかし、バイトコードへ出力、というかスタックマシーンで動かすコードに変換すれば、ifやcondはスタック操作とgoto(またはgoto-if)に変換出来る為、C89 でも単純なコードに変換する事が出来る。
更にバイトコードを高速にインタープリターで実行する事も可能になる。
クロージャーについては…まだ実装を詰められてないので、また後日。

なぜ Lisp か？

単純に好きだからというのがあるが、それは置いといて、マリオ64の制作(ツール)に Common Lisp が使われたとか、(自分も知らない)昔はグラフィックス関連に LISPマシン(Symbolics) が使われてたりとか、ゲームのコード自体に Lisp が使われてたりしてたけど、ゲームを全て Lisp で実装している家庭用ゲーム機向けのゲームは多分無いだろうという事で、それが可能な Lisp を実装したいと思ったから。

名前 (仮)

CELLISP (C の代わりになる Emacs Lisp ライクな Lisp)

マクロ

当然 Lisp なので、マクロは実装される。Lisp のマクロは強力なので、以下の機能はマクロで実装する事が出来て、言語仕様(コンパイラ)に含める必要が無い。

• ジェネレータ (or コルーチン)
• Async/Await
• パターンマッチ
• (明示的な)末尾呼び出しの最適化
• (明示的な)遅延評価

新しいプログラミングパラダイムが出てきたとしても、大体はマクロで対応出来るはず。
最近のトレンドとしては(安全な？)並行処理とかだけど、ゲームプログラミングにも並行・並列処理が必須なので、何らかのマクロでの対応を追加したい。

ちなみに、ゲームプログラミングにおいてはコルーチンはとても役に立つ。コルーチンはフル活用したいと思う。

静的コード解析

マクロにも通ずる事だが、Lisp はコードの形式が非常に単純なので、コードを解析する事がとても簡単だ。
なので、静的コード解析を充実出来ればと思っている。

静的コード解析が役に立つ例としては、配列にアクセスする際のインデックスがサイズをオーバーする可能性がある、とか。
C や C++ の場合はこれによって範囲外アクセスが発生し、最悪セキュリティホールになり得る。
そうならないように、事前に範囲チェックを追加する(Lisp 等はデフォルト範囲チェックされる)が、結局異常な値が来たら正常に処理を続行出来ないので、人間がデバッグする必要がある。
しかし、静的コード解析が出来れば、アクセスを遡って問題が発生しそうな箇所を自動的に割り出す事が出来るだろう。

型

基本的に静的型だけど、リストの実装には C# の dynamic (または TypeScript の any)の様に動的型を使えるようにする。

(apply func '(1 "a" 3.0))

Lisp はこのようなコードを頻繁に実行するので、リストを静的型で実装する事は困難…

型はdefrecordで定義する。(C のstructとほぼ一緒)

(defrecord point2d
  x 0 ;; x は型推論で int
  y) ;; エラー (初期値が必要)

(defrecord cons
  car:any nil
  cdr:any nil)

any型の伝搬を防ぐ為に any to any の代入を禁止する。

(setcar c0 (car c1)) ;; エラー

(letq a 1 ;; ok
      b (car co) ;; エラー
      b:int (car co)) ;; ok

(defun test (a)
  (typecase a
    (float "a float")
    (int "a int")
    ...))

(test (car co)) ;; エラー
(test (int (car co))) ;; ok

リストを使ったコードが冗長になりそうなので、実装後に要検討。
(setcar c0 (car c1))のようなコードはマクロを実装する上で頻発する気がするので、リスト to リストならば特別にエラーにならないようにする必要があるだろう。

コロン

package:func ← Common Lisp のこれを拡張して…
obj:attr と書けるようにする。(C や Java 等のドットと同じ)

• obj:attr → (attr obj)
• array:2 → (2 array) → (aref array 2)
• htbl:"a" → ("a" htbl) → (gethash "a" htbl)
• (defun f (a:int) ...) → (defun f ((int a)) ...)

これで括弧だらけになるのを防げる。
Lisp 一般の関数評価部分を拡張して (2 obj) ("a" obj) と整数などもメソッドとして実行出来るようにする。
コロンはa:b → (b a) とするだけの単なるリーダマクロ。
これでarray:2やhtbl:"a"が実現できる。

ちなみに、Lisp でオブジェクトを使うと以下の右側のように書く必要がある。

• obj.method(arg) → (method obj arg)
• obj.attr → (attr obj)

メソッド呼び出しの方は全然良いとして、アトリビュート(メンバ変数)にアクセスする括弧がかなり鬱陶しい…例えば

func(o.a, o.b + o.c[2]) → (func (a o) (+ (b o) (aref (c o) 2)))

Lisp を嫌いにならないでください…コロンを使えば

(func (a o) (+ (b o) (aref (c o) 2))) → (func o:a (+ o:b o:c:2))

と、少なくとも括弧地獄にはなっていない。(コロンは左結合)
そうなると、Lisp の全てを括弧で表現するというメタファーからは逸脱してしまってると思われるかもしれないが、既に Common Lisp でpackage:funcと使っている以上問題無いと言い張る。

破綻が無いか更に検討が必要。

カリー化

(obj:method 1 2)は((method obj) 1 2)と展開されるが、methodは以下の様に定義されている。

(defun method (self:class param1:int param2:int):int
  ...)

methodは(method obj 1 2)と呼び出す事が可能だが、obj:methodを使えばオブジェクトに紐付いてる事が明確なのでなるべくそのように書きたい。
その場合に(method obj)が返すものがmethodをカリー化した関数だ。
そうすると((method obj) 1 2)が(method obj 1 2)と同じ意味になる。

タプル

配列とレコードとタプルは使い方や見た目が同じものとする。
[1 "a" 1.0]は中身が型が違う値が入っているのでタプルと言い、インラインでdefrecordされている。(C++ のテンプレートで実装されているタプルと似ている)
もちろん静的型なので"a"の場所に2を代入する事は出来ない。
[0 1 2]は全て型が一緒なので配列と言う。
(make-vector LENGTH INIT)は配列を作成するが、INITで初期化される際に単一の型に固定される。
defrecordされたレコードやタプルでも添え字アクセスが可能。
[1 "a" 1.0]:1は"a"を返す。
(cons "car" "cdr"):1は"cdr"を返す。

defun

(defun hoge (a:int b:string) ...)

これは

(defun hoge ((int a) (string b)) ...)

と展開されて、(int a) はキャスト関数で a が int ライク(float など)でないとエラーになり、float が渡されたら int にして返す。

要するに引数リストには関数を書く事が出来て、

(defun hoge (a:int (<= 0 b:int)) ...)
;; ↓
(defun hoge ((int a) (<= 0 (int b))) ...)
;; or
(defun natural-num (n:int) (if (<= 0 n) n (throw 'wrong-type-argment ...)
(defun hoge (a:int b:natural-num) ...)

と、アサートを書く事が出来る。

戻り値の型をどこに書くか要検討。

戻り値の型はパースすれば、推論して確定する事が可能なので(確定出来ない場合は、戻り値の型が曖昧という事でエラーになる)、明示的には書かないという事になりそう。
TypeScript は戻り値の型を省略可能だが、例えばifのthen節とelse節の戻り値の型が違えば、コンパイルエラーになる。
結局、戻り値の型を書こうが書くまいが、コンパイラは型の推論は必須になる。

関数をコーディングしている時に、先に戻り値を確定しておきたい時がある。
その場合の為にdeclare-functionを使う。これは C で言う関数プロトタイプでもある。
(declare-function は、Emacs でも使われている)

(declare-function func (a:int b:int) int)
(defun func (a:int b:int)
  )

戻り値の書き方候補(多分これで決まり)

(defun add (a:int b:int &optional (c 0) (d:float 0)):int
  (+ a b))
↓
(defun add (int ((int a) (int b) &optional (c 0) ((float d) 0)))
  (+ a b))

(defun 関数名 (戻り値の型 ((型 引数名1) (型 引数名2) ...))
  ...)

:リーダーマクロ展開後は引数リスト(ラムダリストとも言う)がかなり括弧だらけにはなるが、これを直接見る(扱う)人はマクロを書く人ぐらいなので、問題は無い。引数リストをパースする標準的な関数を用意してそれを必ず使ってもらえば良い。

(defun func (a b) ...) ;; 型指定無し引数リスト
(defun func (int (a b)) ...) ;; 戻り値の型のみ有る引数リスト
(defun func (a &optional (b 0)) ...) ;; デフォルト引数有り(戻り値と引数の型無し)

一見、戻り値の型指定とデフォルト引数の指定が 2 つ目にコンスセルが来ている所が似ているが、デフォルト引数は&optionalの後に書かないといけないので、混同せずに正しくパース出来る。

letq

setqの構文は

(setq a 0
      b 1)

とシンプルに記述出来るが、letは括弧が多過ぎる。
なので、以下のように記述出来るようにする。

(defun fib (n)
  (let ((a 0)
        (b 1))
    (dotimes (_ n)
      (cl-psetq a b
                b (+ a b)))
    a))
;; ↓
(defun fib (n)
  (letq a 0
        b 1) ;; a や b は型推論されている (a b 共に int)
  (dotimes (_ n)
    (psetq a b
           b (+ a b)))
  a)

他の言語(例えば JavaScript)は、関数の先頭などでlet等を使ってローカル変数を定義する事が普通なので、letqの書き方は自然な書き方になる。(既存の Lisp 使ってる人は気持ち悪いかもしれないが…)
a 0に至るまでの括弧の数が 3 から 1 へ大幅に減っていて、慣れれば読み易いし、setqと一貫性があって覚え易い。

ちなみに何処に定義されるかというと、defunが持ってる暗黙の(block ...)内にローカル変数が定義される。
暗黙のブロックは他にもwhileが持っていたりする。(Common Lisp のdoが暗黙のブロックを持ってるのと同じ)

改めてブロックを作成して、そのブロック内にローカル変数を定義するには、以下のようにする。

(defun fib (n)
  (letq a 0
        b 1)
  (block
   (letq n (* n 2))
   (dotimes (_ n)
     (psetq a b
            b (+ a b))))
  a)

亜種にpsetqと対になるpletqがある。letとlet*の関係も不満があったので、これで一貫した定義に出来る。

;; a => 1, b => 2 とする
(letq a b
      b (+ a b))
a ;; => 2
b ;; => 4

;; a => 1, b => 2 とする
(pletq a b
       b (+ a b))
a ;; => 2
b ;; => 3

ローカル変数の定義はこれでいいとして、fletやlabelsで定義していたローカルの関数は、Scheme のように単にdefunをネストする事で対応する。

(defun factorial (x)
  (cl-labels ((fact-iter (a product)
                         (if (= a 0)
                             product
                           (fact-iter (- a 1) (* product a)))))
    (fact-iter x 1)))
;; ↓
(defun factorial (x)
  (defun fact-iter (a product)
    (if (= a 0)
        product
      (fact-iter (- a 1) (* product a))))
  (fact-iter x 1))

これで、a productに至るまでの括弧が 2 つ削減されている。

ちなみに、Emacs Lisp の場合はdefunは最終的にfsetが呼ばれるが、このfsetがローカルかグローバルかの判別を追加すればいいはず。
setqは最初からそのような実装になっていて、ローカルの場合は「レキシカル環境(lexical environment)」に保存される。

モジュール

最終的にはモジュールは .dll や .so の共有ライブラリになる。
可能な限り C と ABI 互換にしたい。
C では .h に書かれている関数プロトタイプのような情報も共有ライブラリ自体に含めたい。
要するに .dll さえ有ればコンパイルが出来るようにしたい。

C との連携

OS とのインターフェースは C の API を呼び出す事になるが、それらの情報は全て C のヘッダーファイルに書かれている。
これをパースする必要があるが、それは Clang を使う事にする。
まだ試したことはないが、ヘッダーに書かれている情報は全て取得出来ると仮定する。

Lisp と C を連携する時に幾つか問題がある。
1 つは #define や enum 等のバイナリには含まれないが有益な情報だろう。
Lisp でそのような情報を書く術を見た事が無い。
defconstを使えば定数を定義出来るが、これはバイナリに含まれてしまう。
大量の enum が定義されていた場合にバイナリに無駄が生じるので、enum に相当するものを定義する。

(declare-enum MONSTER
              MON_ZAKO 0
              MON_BOSS 1)

declare は Lisp でバイナリに含まれない情報を表すっぽい雰囲気があるので、declare-enumとする。

もう一つはポインターだろう。

(declare-record FILE)
(declare-function fopen (path:char* mode:char*) FILE*)

(defrecord User
  name:char* nullptr
  file:FILE* nullptr)

と、型名の最後が*で終わってたらポインタとみなして、ポインタ型を認めるしかない。
しかし、C# の unsafe の様に、簡単に使えないようにはしたい。

C-Expression

curly-infix-expressions とも言う。既に Common Lisp のリーダーマクロで実装されていて、同じものを実装予定。
マクロで実装されるので言語仕様ではないが、最初から有れば便利だろう。
S 式で複雑な数式を書くのはつらい…。特にゲームは複雑な数式を書く事が多いので、この機能はやむを得ない。

(letq a {1 + 2 + 3 * (4 + 5)}
      b {a ** b})