この記事は，関数型プログラミングが可能な言語を網羅しようとしている拙作記事『カリー化チートシート』や『不動点コンビネータを用いた無名再帰関数の実行まとめ』に関連して試したScheme処理系に関する記録，および，各記事の宣伝です（正直）．ですので，すみません，Juliaほとんどありません．タグ付けしないのもどうかなあと…．
Juliaとfemtolisp
上記の記事で，次のターゲット（？）は『Julia』かなと調べたところ，フロントエンド（パーサ）に独自開発の小さなSchemeインタプリタ『femtolisp』を使用しているだけでなく，Julia起動時に--lispオプションを付けると普通にREPLが起動するということを知りました．下記はその実行例．
$ julia --lisp
; _
; |_ _ _ |_ _ | . _ _
; | (-||||_(_)|__|_)|_)
;-------------------|----------------------------------------------------------
> (define fix (lambda (f) (f (lambda (x) ((fix f) x)))))
#fn("7000r1|c0|q141;" [#fn("6000r1e0~31|41;" [fix])])
> (((fix (lambda (f) (lambda (x) (lambda (r) (if (< x 1) r ((f (- x 1)) (* x r))))))) 5) 1)
120
> (exit)
$
Juliaの実行例もついでに（酷）．
$ julia
_
_ _ _(_)_ | Documentation: https://docs.julialang.org
(_) | (_) (_) |
_ _ _| |_ __ _ | Type "?" for help, "]?" for Pkg help.
| | | | | | |/ _` | |
| | |_| | | | (_| | | Version 1.0.5 (2019-09-09)
_/ |\__'_|_|_|\__'_| | Official https://julialang.org/ release
|__/ |
julia> fix(f) = f(x -> fix(f)(x))
fix (generic function with 1 method)
julia> fix(f -> x -> r -> x < 1 ? r : f(x-1)(x*r))(5)(1)
120
julia> exit()
femtolispは，それ単体で開発が進められているようです（GitHubリポジトリ）．
tiny版femtolisp
GitHubリポジトリの中の『tiny』ディレクトリを見ると，更に小さいSchemeインタプリタのC言語ソースコードがパブリックドメインとして公開されていました．3種類ほどありましたが，整数のみ対応で末尾再帰最適化を含むコード（lisp.c）が最も安定しており，Debian系OSだけでなく，Cygwinでもエラーなくgccコンパイルが通り，問題なく稼働しました．femtolispのREADME.mdを見る限り，末尾再帰最適化の有用性を示すためのプロトタイプとして作成されたようです．
$ ls
lisp.c system.lsp
$ uname -a
CYGWIN_NT-10.0 XXXXXXXXXX 3.1.6(0.340/5/3) 2020-07-09 08:20 x86_64 Cygwin
$ cc --version
cc (GCC) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ cc -o lisp lisp.c
$ ./lisp
Welcome to femtoLisp ----------------------------------------------------------
> (define fix (lambda (f) (f (lambda (x) ((fix f) x)))))
(lambda (f) (f (lambda (x) ((fix f) x))))
> (((fix (lambda (f) (lambda (x) (lambda (r) (if (< x 1) r ((f (- x 1)) (* x r))))))) 5) 1)
120
>（Ctrl-Dで終了）
$
lisp.cのコードは1038行で，コメントを除くと確実に1000行を切るという小ささ．ただし（他の処理系実装と同様に）defineを含む多くの基本構文・関数は，起動時に読み込むsystem.lspにて，それ自身のマクロ定義や関数定義で別途記述されています．ビルトイン構文・関数の予約語は次の通り．
static char *builtin_names[] =
{ "quote", "cond", "if", "and", "or", "while", "lambda", "macro", "label",
"progn", "eq", "atom", "cons", "car", "cdr", "read", "eval", "print",
"set", "not", "load", "symbolp", "numberp", "+", "-", "*", "/", "<",
"prog1", "apply", "rplaca", "rplacd", "boundp" };
どちらかというと昔ながらのLISP予約語構成となっており，真偽値も#tではなくt，#fではなくnil（空リスト）といった感じです．lambda式の手続き本体はひとつのみです．ただ，静的スコープ，第一級オブジェクトのlambda式（自己評価型）など，Schemeで特に意識されている仕組みは揃っていました．
次は，初期化ファイルであるsystem.lspを読み込まずにtiny版femtolispを起動し，ビルトイン構文のsetとlambdaのみを用いて関数定義した例です．なお，setは，quote（'）された名前に値を割り当てる構文です．
$ ./lisp
Welcome to femtoLisp ----------------------------------------------------------
> define
eval: error: variable define has no value
> (set 'fix (lambda (f) (f (lambda (x) ((fix f) x)))))
(lambda (f) (f (lambda (x) ((fix f) x))))
> (((fix (lambda (f) (lambda (x) (lambda (r) (if (< x 1) r ((f (- x 1)) (* x r))))))) 5) 1)
120
マクロ定義もビルトイン構文であるmacroで可能ですので，値割り当てだけであれば，次のようにdefineが定義可能です（system.lspにあるlistの関数定義とsetqのマクロ定義をぱくっただけですが…）．
> (set 'list (lambda x x))
(lambda x x)
> (set 'define (macro (name val) (list set (list quote name) val)))
(macro (name val) (list set (list quote name) val))
> (define fix (lambda (f) (f (lambda (x) ((fix f) x)))))
(lambda (f) (f (lambda (x) ((fix f) x))))
> (define factr (lambda (f) (lambda (x) (lambda (r) (if (< x 1) r ((f (- x 1)) (* x r)))))))
(lambda (f) (lambda (x) (lambda (r) (if (< x 1) r ((f (- x 1)) (* x r))))))
> (((fix factr) 5) 1)
120
macroはマクロ定義のための構文で，指定した引数をどのように展開するかをリスト構造で示しています．
tiny版femtolispの改造
さしあたり，とっとと#tと#fが利用できるようにしています．せっかくの（？）パブリックドメインなのと，system.lspはもちろんlisp.cもとても読みやすいコードなので，割とさくさくいけます．
@@ -195,8 +203,8 @@
curheap = fromspace;
lim = curheap+heapsize-sizeof(cons_t);
- NIL = symbol("nil"); setc(NIL, NIL);
- T = symbol("t"); setc(T, T);
+ NIL = symbol("#f"); setc(NIL, NIL);
+ T = symbol("#t"); setc(T, T);
LAMBDA = symbol("lambda");
MACRO = symbol("macro");
LABEL = symbol("label");
@@ -1024,7 +1032,8 @@
なお，こういう場合はたいがい機能拡張するものなのですが，既にfemtolispという上位フルセット処理系があることから，lisp.cもsystem.lspも機能縮小を基本としています．Scheme対応していないPaaSやSaaSでこっそりScheme処理系を仕込めるようになるまで．
system.lspは昔ながらのLISP予約語定義も多いので，ゼロから定義するか，必要なものだけをC言語プログラム本体に組み込んだ方が良いかもしれません．Julia同様，自作ソフトに入力解析器として組み込むためにカスタマイズしたり，簡単なラムダ計算を試す（Scheme記述例はこちら）ために使用したり（また宣伝）．
なお，UNIX環境での対話型利用は（他のScheme処理系同様）rlwrapやEmacs連動が便利です．
改造進捗（2020-08-06）
既に何言語かわからなくなってる…というほどでもないけど，互換性がなくなっちゃってるんだよなあ．ちなみに，fltrとはfemtolisp tiny reduced versionの略である！（ダサい）
$ cat Tarai.fltr
(// Tarai
(>> (x y z)
(?+ ((le? x y) y)
(#t (Tarai (Tarai (sub x 1) y z)
(Tarai (sub y 1) z x)
(Tarai (sub z 1) x y))))))
(display (Tarai 14 7 0))
(newline)
$ time ./fltr init.fltr Tarai.fltr
14
real 3m49.193s
user 3m49.192s
sys 0m0.000s
$ cat Tarai.scm
(define Tarai
(lambda (x y z)
(cond ((<= x y) y)
(else (Tarai (Tarai (- x 1) y z)
(Tarai (- y 1) z x)
(Tarai (- z 1) x y))))))
(display (Tarai 14 7 0))
(newline)
$ time gosh Tarai.scm
14
real 0m18.569s
user 0m18.472s
sys 0m0.008s
改造進捗（2020-08-16）
予約語の記号化はやめました．文法記号としての括弧の連なりの圧に負けた…．
とりあえず，tnil→#t#fだけでなく，述語関数の?付けやelseの導入，defunとsetqの削除，(exit)による終了，eval結果の出力の抑制など，順次Scheme寄りの記法にしています．異なるところと言えば，defineによる手続き定義はlambda式の名前付けのみにしたことでしょうか（ただの趣味＆手抜き）．
$ fltr
fltr> (define f (lambda (x) (lambda (y) (lambda (z) (* (- x y) z)))))
#t
fltr> (f 10)
(lambda (y) (lambda (z) (* (- x y) z)) (x . 10))
fltr> ((f 10) 20)
(lambda (z) (* (- x y) z) (y . 20) (x . 10))
fltr> (((f 10) 20) 30)
-300
fltr> (define small (lambda (n) (filter (lambda (x) (< x (car n))) (cdr n))))
#t
fltr> (define large (lambda (n) (filter (lambda (x) (>= x (car n))) (cdr n))))
#t
fltr> (define qsort (lambda (n)
(cond ((null? n) '())
(else (append (qsort (small n))
(list (car n))
(qsort (large n)))))))
#t
fltr> (qsort '(8 4 2 1 9 2 7 3))
(1 2 2 3 4 7 8 9)
fltr> (exit)
$
扱う値が相変わらず整数のみですが，実数はconsセルで実装できないかなあとか考えていたりいなかったり．
改造進捗（2020-08-21）
fltrから更にforkしました（えっ）．lamlisとは，lambda and listの略である！（ダサいを通り越して呆れ）．
static char *builtin_names[] = {
// special forms
"if", "quote", "lambda",
// functions
"eq", "atom", "set", "cons", "car", "cdr"
};
はい，いわゆる純LISPというやつですね．数値も扱えなくなりました．純粋にラムダ計算とリスト処理を楽しむためのものという感じ．なお，lambda式を含む値はquoteしたアトムにしか束縛できなくてdefineじゃないよなあということで，オリジナル名称のsetに戻しました．述語もeqとatomだけになったのであえて?を付ける理由がなくなったというか．
(set 'null (lambda (L) (eq L '())))
(set 'append
(lambda (L1 L2)
(if (null L1)
L2
(cons (car L1)
(append (cdr L1) L2)))))
(set 'fold
(lambda (f n L)
(if (null L)
n
(fold f
(f (car L) n)
(cdr L)))))
(set 'reverse
(lambda (L)
(fold (lambda (x y) (cons x y))
'() L)))
(set 'list (lambda x x))
(set 'map
(lambda (f L)
(if (null L)
'()
(append (list (f (car L)))
(map f (cdr L))))))
; (map reverse '((a b c) (1 2 3) (hello nice to meet you)))
; => ((c b a) (3 2 1) (you meet to nice hello))
(set 'filter
(lambda (p L)
(if (null L)
'()
(if (p (car L))
(cons (car L) (filter p (cdr L)))
(filter p (cdr L))))))
(set 'assq
(lambda (L k)
(if (null L)
'()
(if (eq (car (car L)) k)
(car (cdr (car L)))
(assq (cdr L) k)))))
; (set 'db
; '((Sato (Engl 95) (Math 59) (Chem 72))
; (Suzuki (Japn 82) (Chem 91) (Expr 79))
; (Naito (Math 68) (Japn 77) (Engl 87))))
;
; (filter (lambda (x) x) (map (lambda (x) (assq (cdr x) 'Engl)) db))
; => (95 87)
備考
各リポジトリ
-
lamlis:https://github.com/ytaki0801/Samples/tree/master/Scheme/implementations/lamlis -
fltr：https://github.com/ytaki0801/Samples/tree/master/Scheme/implementations/fltr
参考文献
- Gauche - A Scheme Implementation：『Schemeで書くかCで書くか』
変更履歴
- 2020-10-21：リポジトリ位置の変更に伴いリンク等を修正
- 2020-08-21：改造進捗追記
- 2020-08-16：改造進捗追記，備考に改造ソースコード公開場所追加
- 2020-08-06：改造進捗追記
- 2020-08-05：初版公開