ごみ集めのないLISP
2020年5月 第17回関西Lispユーザ会
@zick_minoh
頭の悪い
Ring Lisp
これの話をします
ここでの「ごみ集めのないLISP」とは
線形論理を応用したごみ集めを必要としないLISP
みんな大好き線形論理
ここでの「ごみ集めのないLISP」とは
線形論理を応用したごみ集めを必要としないLISP
必要か知らんけど面倒なのでごみ集めのないLISP
頭の悪い処理系
自作LISP処理系の神話
あいまいな主張
目標
ごみ集めを書かずに
LISP処理系を作れるか検証する
実は後付の目標
前提
つまり頑張らない
コンスセルの割り当て
使用済み
空き領域
head
Heap
左から右へ
コンスセルの割り当て（実装）
uint8_t* alloc_head;
void* alloc() {
void* ret = reinterpret_cast<void*>(alloc_head);
alloc_head += kWordSize;
return ret;
}
kWordSize == 16
終端問題
終端まできたら割り当てができなくなる！
使用済み
空き領域
head
右端で止まる
メモリが一杯になったら
www.nichinoken.co.jp
わがままな要望
シカクいメモリをマルくする
new!
すでに空き領域は
残っていないが
終端がないので
どこまでも
割り当て可能
無限メモリーの幻想
シカクいメモリをマルくする（実装）
void* alloc() {
if (alloc_head >= cons_area_end) {
alloc_head = cons_area_begin;
}
void* ret = reinterpret_cast<void*>(alloc_head);
alloc_head += kWordSize;
return ret;
}
右端に行くと左端に戻る
コンスセルの上書き (1/3)
X = (cons 1 nil) ; => (1)
1
これは自明
コンスセルの上書き (2/3)
X = (cons 1 nil) ; => (1)
Y = (cons (something 2) X)) ; => (2 1)
1
2
すでにヒープが一杯に
コンスセルの上書き (3/3)
X = (cons 1 nil) ; => (1)
Y = (cons (something 2) X)) ; => (2 1)
Z = (cons 3 Y) ; => (3 2 1) ???
1
2
2
3
上書きされた
上書きは問題なのか (1/2)
2
3
X
Z
Y
問題のある変数とない変数
変数 | 想定 | 実際 |
X | (1 . nil) | (3 . Y) |
Y | (2 . X) | (2 . Z) |
Z | (3 . Y) | (3 . Y) |
上書きは問題なのか (2/2)
2
3
X
Z
Y
プログラマが悪い
ポインタの先が上書きされたか判断する (1/2)
未割当
第0世代
0周目
世代別GCの世代とは違う
第0世代
第1世代
1周目
ポインタの先が上書きされたか判断する (2/2)
第0世代
第1世代
1周目
X(第0世代)
Z(第1世代)
Y (第0世代)
ポインタを触るときに判断
ポインタの先が上書きされたか判断する（実装1/2）
int generation;
uintptr_t makeCons(uintptr_t car, uintptr_t cdr) {
Cons* cons = reinterpret_cast<Cons*>(alloc());
cons->car = car;
cons->cdr = cdr;
uintptr_t ret = reinterpret_cast<uintptr_t>(cons);
ret |= (generation << 1);
return ret;
}
0
G
G
G
A
A
A
A
A
A
A
A
…...
アドレス（下位4bitは省略）
世代
コンスは16bytes
ポインタの先が上書きされたか判断する（実装2/2）
int gen(uintptr_t obj) {
return static_cast<int>((obj & (kWordSize - 1)) >> 1);
}
int current_gen(uintptr_t obj) {
void* head = reinterpret_cast<void*>(alloc_head);
if (ptr(obj) >= alloc_head)
return (generation - 1) & ((kWordSize - 1) >> 1);
return generation;
}
0
G
G
G
A
A
A
A
A
A
A
A
…...
世代
アドレス（下位4bitは省略）
genとcurrent_genを比較
ここまでの考察
無理やりな考察
ここまでで何ができるか (1/2)
> (cdr '(a b c))
(b c)
> (cons 1 (cons 2 (cons 3 ())))
(1 2 3)
> (defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))
fact
> (fact 10)
3628800
突然のLISP
ここまでで何ができるか (2/2)
> (defun gen (n) (lambda (m) (setq n (+ n m))))
gen
> (setq x (gen 100))
expr
> (x 10)
110
> (x 90)
200
普通に動く
ここまでで何ができないか (1/2)
> (defun sum (n) (if (eq n 0) 0 (+ (sum (- n 1)) n)))
sum
> (sum 10)
55
> (sum 100)
... generation: 1
<stale value: 7fb340d00890>
上書きされてエラー
ここまでで何ができないか (2/2)
> (sum 50)
<error: sum has no value>
> (cdr '(a b c))
<error: cdr has no value>
くだらない
前提（再掲）
環境破壊
環境保全
組み込み関数
（上書き不可）
実はいらないけど便利
環境保全（実装）
void* alloc() {
if (alloc_head >= cons_area_end) {
alloc_head = saved_area_end;
generation = (generation + 1) & ((kWordSize - 1) >> 1);
}
void* ret = reinterpret_cast<void*>(alloc_head);
alloc_head += kWordSize;
return ret;
}
保護領域の直後に戻る
きちんと動く再帰関数を書く
主に頭が悪い
局所環境・一時データの上書き
(defun sum (n)
(if (eq n 0)
0
(+ (sum (- n 1))
n)))
再帰してるうちにnのことを忘れてしまう
(※) 環境は連想リストのリストで表現する
局所環境
一時データ
1回の関数呼出で
使うデータ
（フレーム）
過去を振り返ったらだめ
大域環境・関数本体の上書き
(defun sum (n acc)
(if (eq n 0)
acc
(sum (- n 1) (+ acc n))))
再帰してるうちにsumが壊れてしまう
(※) 関数・クロージャはリストで表現する
局所環境
一時データ
関数本体
大域環境（一部）
昔に作ったものは壊れる
一度しか作られない
毎回作るフレーム
評価規則の拡張
(setq f '(lambda (x) (cons x x))) ; => ...
(f 3) ; => (3 . 3)
((copy f) 3) ; => (3 . 3)
; (eval `(,(copy-tree f) 3)) ; CL version
実のところEVALと同じ
これなら動く総和関数
(setq sum
'(lambda (fn n acc)
(if (eq n 0)
acc
(fn (copy fn) (- n 1) (+ acc n)))))
; (sum sum 100 0) => 5050
環境
一時データ
関数本体
壊れる前に作り直す
毎回作るフレーム
再帰関数の書き方
末尾再帰は実質反復
末尾再帰で書けない関数
証明は読者の演習課題
アッカーマン関数: 普通の定義（動かない）
(defun ack (m n)
(if (eq m 0)
(+ n 1)
(if (eq n 0)
(ack (- m 1) 1)
(ack (- m 1) (ack m (- n 1))))))
読みやすくしただけ
アッカーマン関数: スタックを使う（動かない）
(defun ack (m n s)
(if (eq m 0)
(if (eq s nil)
(+ n 1)
(ack (car s) (+ n 1) (cdr s)))
(if (eq n 0)
(ack (- m 1) 1 s)
(ack m (- n 1) (cons (- m 1) s)))))
外側のackを後で呼ぶ
アッカーマン関数: 自己複製（動く）
(setq ack '(lambda (fn m n s)
(if (eq m 0)
(if (eq s nil)
(+ n 1)
(fn (copy fn) (car s) (+ n 1) (copy (cdr s))))
(if (eq n 0)
(fn (copy fn) (- m 1) 1 (copy s))
(fn (copy fn) m (- n 1)
(cons (- m 1) (copy s)))))))
スタックもコピー
真・再帰関数の書き方
複製したら死なない
よりLISPらしいプログラムを書く
個人の感想
アッカーマン関数: 継続渡し（動かない）
(defun ack (m n k)
(if (eq m 0)
(k (+ n 1))
(if (eq n 0)
(ack (- m 1) 1 k)
(ack m (- n 1) (lambda (n) (ack (- m 1) n k))))))
; (ack 1 2 (lambda (x) x))
継続のk
アッカーマン関数: 継続渡し＋複製（大飯食らい）
(setq ack '(lambda (fn m n k)
(if (eq m 0)
(k (+ n 1))
(if (eq n 0)
(fn (copy fn) (- m 1) 1 (copy k))
(fn (copy fn) m (- n 1)
(list 'lambda '(n)
(list (copy fn) (list 'quote (copy fn))
(- m 1) 'n (list 'quote (copy k)))))))))
複製と継続と私
アッカーマン関数: 継続渡し＋複製＋最適化
(setq ack '(lambda (fn m n k)
(if (eq m 0)
(k (+ n 1) fn)
(if (eq n 0)
(fn (copy fn) (- m 1) 1 (copy k))
(fn (copy fn) m (- n 1)
(list 'lambda '(n f)
(list 'f 'f (- m 1) 'n
(list 'quote (copy k)))))))))
関数を注入
自作LISP処理系の神話（再掲）
「たくさん」とは
必要なメモリの量を求める
フレームを考える
必要な関数本体の数
(setq sum
'(lambda (fn n acc)
(if (eq n 0)
acc
(fn (copy fn) (- n 1) (+ acc n)))))
呼び出された関数
渡された関数
複製された関数
3つの関数が同時に生存する必要がある
ひどい無駄
同一の関数の使用
(setq sum
'(lambda (fn n acc)
(if (eq n 0)
acc
((lambda (f) (f f (- n 1) (+ acc n)))
(copy fn)))))
2つの関数が同時に生存できればよい
まともになった
関数呼び出しに必要なメモリ量
つまり2倍
一般的なプログラムを書くための考察
見覚えのある条件
一般的なプログラムを書くための考察
これって copying GC なのでは？
知ってた
目標（再掲）
ごみ集めを書かずに
LISP処理系を作れるか検証する
検証した
結論
ごみ集めを書かずに
LISP処理系を作ると
LISPでごみ集めを書くことになる
ごみのような結論
付録
超循環評価器 (1/4)
EVALをかいてエバる
超循環評価器 (2/4)
(setq reval
'(lambda
(self-eval? cont appexpr search-bind rmbind update-env rapply
update-stack reval exp env stack)
(if (self-eval? exp)
(cont (copy self-eval?) (copy cont) (copy appexpr)
(copy search-bind) (copy rmbind) (copy update-env)
(copy rapply) (copy update-stack) (copy reval) (copy exp)
(copy stack))
;;; 中略
(if (eq (car exp) 'if)
(reval (copy ...) (copy (cadr exp)) (copy env)
(cons 'if
(cons (copy (cddr exp))
(copy (cons env stack)))))
;;; 後略
関数を引数で引き回す
超循環評価器 (3/4)
(reval self-eval? cont appexpr search-bind rmbind update-env
rapply update-stack reval
'((lambda()
(defun f(n acc)
(if (eq n 0)
acc
(f (- n 1) (+ n acc))))
(f 100 0)))
;;; 略
)
ごみを気にしない
なんと普通のLISPが書ける
超循環評価器 (4/4)
LISPでメモリ管理
（関連分野）Linear Lisp
比較するのが失礼
（関連分野）Cheney on the M.T.A.
比較するのが無礼