純LISP (JunLISP)

一応の完成(2013/06/27)
ソースファイル(新定義版(純LISP)Version 2.1.1 lisp13.js)(txt)
ソースファイル(整理版(少なLISP)Version 1.3.1 lisp8.js)(txt)(実装)
ソースファイル(プロトタイプ lisp3.js)(txt)
※ 新定義版(lisp13.js)について
    チューリング完全の再現(LISPコードによるeval実現)をしやすいように仕様を大幅変更した
    それにともないlisp8.jsは『純LISP』改め『少なLISP』という名称に変更した
※ プロトタイプ(lisp3.js)と整理版(lisp8.js)の違いについて
    いくつかの関数名の変更と、関数をひとまとめにした
    またLISPコード解析の方法を丸ごと変更した(複数行への分割記述・コメント行(;)に対応)

マイオリジナルevalコード(lisp14.txt) (2013/06/26 Version 1.2.0)
このテキストファイルの中身を丸ごと全部、下のテキストエリアにコピペして実行すれば試せます
このevalはこのページで公開中の純LISPの仕様を再現するよう作られています
(ファイル最後に書いてあるテストコードがとても重いので注意が必要です)

マイオリジナルevalコード やや軽(lisp15.txt) (2013/06/26 Version 2.2.0)
上記のlisp14.txtのエラートラップを全て削除し、不要コードを整理したものです
lisp14.txtのものよりはやや軽めの動作(実行が2倍程度速い)。ただしエラートラップが全くないため
引数や名前など間違ったLISPコードをevalやその他の関数に与えるとどのような挙動をするか全くの不明です

eval上でeval?

lisp15.txtの内容をテキストエリアにコピペして実行したあとで
以下のようなコードを入力して実行することで eval上にevalを実現できます(チューリング完全なので可能なのです!)
(全処理に100倍以上の時間がかかるので注意、処理が倍以上に重いlisp14.txtではテストしないほうが無難です)

(program (quote (

;;この位置にlisp15.txtの内容を丸々コピペ

)) (quote NIL))

◆参考 (lisp15.txtでテスト)
私のネットブック(CPU1.66GHz, メモリ1GB, Windows7 Starter SP1)でブラウザOpera(12.15)上で実行した結果
 lisp15.txtの内容をテキストエリアにコピペして実行 … 数秒程度
 上記実行後 program関数にlisp15.txtの内容を渡して実行 … 5~6分

;この純LISPの仕様上の関係で下記のコードでもevalの動作になります(笑)
(label f-eval (lambda (e a) ((cons (quote LAMBDA) (cons (quote ()) (cons (cons e a) ()))))))
(f-eval (quote CONS) (quote ((quote A) (quote (B C)))))

LISPコード入力



実行結果


開発デバッグ用出力


説明(特殊形式)

名前引数説明
COND(値 値)* (値 値)* … 引数の各リストを順次評価していく(リストは1つ以上必要)
引数のリストの先頭の値がNIL以外なら対になる値をCONDの戻り値として返す
引数のリストの先頭の値がNILなら次の引数のリストを評価する
(COND ((QUOTE A) (QUOTE B)) ((QUOTE T) (QUOTE C))) ; B
(COND ((QUOTE NIL) (QUOTE B)) ((QUOTE T) (QUOTE C))) ; C
LAMBDA(シンボル* シンボル* …)* 値*
又は、
(シンボル* シンボル* … . シンボル*)* 値*
又は、
シンボル* 値*
又は、
NIL* 値*
ユーザ関数を設定する
第一引数にユーザ関数の仮引数を定義する
仮引数にはシンボルを並べたリストまたはシンボルで定義する
第一引数にNILまたは空リストを指定すると引数をとらない関数を作れる
第二引数にユーザ関数呼び出し時に評価する値(実行時評価部)を渡す
このリストを評価するとこのリストがそのまま返る。
このリストが評価すべきリストの先頭要素にあると関数として実行される
ユーザ関数は実行時に変数スコープを形成する
(動的スコープを採用しているので
ユーザ関数内で未定義の変数が使用されている場合には
ユーザ関数呼び出し元の変数スコープでその変数が定義してあればその値を使用する)
(LAMBDA (X Y) (CONS (CONS X X) (CONS Y Y)))
((LAMBDA (X Y) (CONS (CONS X X) (CONS Y Y))) (QUOTE A) (QUOTE B)) ; ((A . A) B . B)
(LAMBDA () (QUOTE A))
((LAMBDA () (QUOTE A))) ; A
((LAMBDA (X Y . Z) Z) (QUOTE A) (QUOTE B) (QUOTE C) (QUOTE D)) ; (C D)
((LAMBDA X X) (QUOTE A) (QUOTE B)) ; (A B)
LABEL
又は、
DEFINE
シンボル* 値第一引数のシンボルに第二引数の値を設定する(変数設定)
第一引数のシンボルに次の予約キーワードは指定できない
 T NIL COND LAMBDA LABEL QUOTE DFINE
 CONS CAR CDR EQ ATOM
LABELの戻り値は変数に設定した値となる
LABELは実行時点の変数スコープに変数を設定する
(ユーザ関数の実行時評価部でLABELを使うとユーザ関数内でのみ有効な変数となる)
(LABEL A (QUOTE B)) ; B
(CONS A A) ; (B . B)
(LABEL F (LAMBDA (X Y) (CONS X Y))) ; (LAMBDA (X Y) (CONS X Y))
(F (QUOTE A) (QUOTE B)) ; (A . B)
(DEFINE A (QUOTE C)) ; C (LABELの代わりにDEFINEを使う例)
(CONS A A) ; (C . C) [LABELと同じ動作]
QUOTE値*QUOTEは戻り値として引数を評価せずにそのまま返す
(シングルクオート[']を使った略記表現に対応)
(QUOTE A) ; A
(QUOTE (A . B)) ; (A . B)
(QUOTE (A B)) ; (A B)
(QUOTE (A B C . D)) ; (A B C . D)
'A ; (QUOTE A) に同じ
'(A B C) ; (QUOTE (A B C)) に同じ
'''X ; (QUOTE (QUOTE (QUOTE X))) に同じ
値:シンボルもしくはリスト
シンボル: Atomic Symbol のこと。アトムとも言う
*:*マークは関数・特殊形式の処理時に評価しない部分を表す(*マークが無い引数は全て評価される)
評価:シンボルならLABELで設定された値を返す。リストならリストの先頭を関数または特殊形式、リストの後方を引数として処理する

説明(システム関数)

名前引数説明
CONS値 値2つの引数でリストを作る(CONS (QUOTE A) (QUOTE B)) ; (A . B)
(CONS (QUOTE A) (QUOTE NIL)) ; (A)
(CONS (QUOTE A) (QUOTE (B))) ; (A B)
(CONS (QUOTE A) (QUOTE (B C))) ; (A B C)
CARリストリストの先頭を取り出す
引数にシンボルを渡すとエラー
(CAR (QUOTE (A . B))) ; A
(CAR (QUOTE (A B C))) ; A
(CAR (QUOTE ())) ; ()
(CAR (CONS (QUOTE A) (QUOTE B))) ; A
CDRリストリストの後方を取り出す
引数にシンボルを渡すとエラー
(CDR (QUOTE (A B C))) ; (B C)
(CDR (QUOTE ())) ; ()
EQシンボル シンボル2つの引数が同じシンボルならT
それ以外はNIL
シンボル以外を引数に渡すとエラー
(EQ (QUOTE A) (QUOTE A)) ; T
(EQ (QUOTE A) (QUOTE B)) ; NIL
(EQ (QUOTE (A . B)) (QUOTE (A . B))) ; エラー
ATOM引数がリストならNIL
それ以外はT
(ATOM (QUOTE A)) ; T
(ATOM (QUOTE (A B))) ; NIL
(ATOM (CONS (QUOTE A) (QUOTE B))) ; NIL
値:シンボルもしくはリスト
シンボル: Atomic Symbol のこと。アトムとも言う
*:*マークは評価しない部分を表す(*マークが無い引数は全て評価される)
評価:シンボルならLABELで設定された値を返す。リストならリストの先頭を関数または特殊形式、リストの後方を引数として処理する

参考にした文献

[1] LISP - Wikipedia
http://ja.wikipedia.org/wiki/LISP

[2] 純LISP - Wikipedia
http://ja.wikipedia.org/wiki/%E7%B4%94LISP

[3] RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE (Part I)
http://www-formal.stanford.edu/jmc/recursive.html

[4] Revised(5) Report on the Algorithmic Language Scheme - Table of Contents
http://people.csail.mit.edu/jaffer/r5rsj_toc.html

[5] Common Lisp the Language, 2nd Edition
http://www.cs.cmu.edu/Groups/AI/html/cltl/cltl2.html


その他

この下にscriptタグによりlispコードを記述してありいくつかのLAMBDA関数を定義してある。ページ読み込み完了時に自動的に実行される
定義されている関数 not list last progn car/cdrの単純合成関数群(caar cdar cddr など)
詳細はこのページのHTMLソースを参照されたし