これは言語処理系を作るというチャレンジのために作ったLispインタプリタである。
- 字句解析はflex(lex)
- 構文解析はBison(yacc)
- 意味解析はC言語 で作られている。
$ make
$ ./MyLisp
John McCarthy(Wiki)が開発したプログラミング言語であり、Lispの名前の由来であるlist processorの通り、プログラムとデータの両方をリストとして記述することができる強力な言語である。
アトム
アトムには以下のものがある
- 記号
- 数
- t
- nil
記号はx, atomなど、普通に文字を書いたもので、あらゆる文字を扱うことができる。
使うことのできない文字は正規表現で[ \t\r\n().#]これらの文字である。
数は1, 2, 1.0, 0,1などである。
数字で始まっても数として扱えないもの(123ab等)は記号として扱われる。
tは真偽値のtrueを表す特殊なアトムで、nilは空のリストや何もないことを表す特殊なアトムである。
リスト
リストは(で始まり)で終わる記法で表すことができる。
ドットペアは(X . Y)のように表され、carがX, cdrがYとなる。
ドットペアの特殊な形がリストで、ドットペアがネストし、cdrを辿り続けた時にもっとも深い位置にあるドットペアのcdrがnilだった場合、リストとなる。
例: (1 . (2 . (3 . nil)))
この例は(1 2 3)と同じ意味を持ち、同じリストとして扱われる。
空のリストは()と表すことができ、これはアトムであるnilと同じ意味を持つ。
プログラムは(+ 1 2 3)のように一つ目に関数、それ以降に引数列の形のリスト構造をインタプリタに食わせることで評価させて実行することができる。
(atom X)
Xがatomであればt、そうでなければnilを返す
(atom 1)
# -> t
(atom 1.1)
# -> t
(atom (quote a))
# -> t
(atom nil)
# -> t
(atom (quote (1 2)))
# -> nil
(car X)
cons(X)のcarを返す
(car (quote (1 2 3)))
# -> 1
(cdr X)
cons(X)のcdrを返す
(cdr (quote (1 2 3)))
# -> (2 3)
(cons X Y)
XとYをそれぞれconsのcarとcdrにして返す
(cons (quote (1 2 3)) (quote (4 5 6)))
# -> ((1 2 3) 4 5 6)
(eq X Y)
XとYが同値であればt、そうでなければnilを返す
(eq 1 1)
# -> t
(eq 1.1 1.1)
# -> t
(eq (quote a) (quote a))
# -> t
(eq (quote (1 2)) (quote (1 2)))
# -> t
(eq 1 2)
# -> nil
(eq (quote (1 2)) (quote (1 3)))
# -> nil
(eval X)
MyLispの処理系と同じようにXを評価する
(eval 1)
# -> 1
(eval (quote ((lambda (x y) (+ x y)) 1 2)))
# -> 3
(numberp X)
Xがnumberであればt、そうでなければnilを返す
(numberp 1)
# -> t
(numberp 1.1)
# -> t
(numberp nil)
# -> nil
(numberp (quote a))
# -> nil
(print X)
Xを標準出力に書き出し、それ自体を返す
(print 1)
# 1
# -> 1
(print (quote a))
# a
# -> a
(+ X1 X2 X3 ... Xn)
X1, X2, X3, ... Xnを順次足し合わせて返す
値はC言語のdoubleの計算精度、範囲である
(+ 1 2 3)
# -> 6
(- X1 X2 X3 ... Xn)
X1からX2, X3, ... Xnを順次引いて返す
値はC言語のdoubleの計算精度、範囲である
(- 1 2 3)
# -> -4
(* X1 X2 X3 ... Xn)
X1, X2, X3, ... Xnを順次掛けて合わせて返す
値はC言語のdoubleの計算精度、範囲である
(* 1 2 3)
# -> 6
(/ X1 X2 X3 ... Xn)
X1からX2, X3, ... Xnを順次割って返す
値はC言語のdoubleの計算精度、範囲である
(/ 1 2 3)
# -> 0.166667 = 1 / 6
未実装
モジュロ演算を順次実行する関数になる予定
(cond (X1 Y11 Y12 ... Y1n) ... (Xn Yn1 Yn2 ... Ynn))
x1 ... Xnがtと評価されるまで引数を順に確認し、
tと評価されたリストのYn1, Yn2 ... Ynnを評価し、最終の評価値を返す
(cond ((eq 1 2) (print 1)) ((eq 2 2) (print 2)) (t (print 3)))
# 2
# -> 2
(cond ((eq 1 2) (print 1)) ((eq 2 3) (print 2)) (t (print 3)))
# 3
# -> 3
(define X Y)
Xで指定されたatomにYをバインドする
(define x 1)
# -> x
# x = 1
(define x (quote (1 2 3)))
# -> x
# x = (1 2 3)
(quote X)
Xを評価せずにそのまま返す
(quote a)
# -> a
(quote (1 2 3))
# -> (1 2 3)
lambdaを関数として扱うことができる
nlambdaで特殊形の関数を扱うことができ、引数が評価されない可変長引数のlambdaを定義できる
((lambda (x y) (+ x y)) 1 2)
# -> 3
((nlambda (x) (+ (car x) (car (cdr x)))) 1 2)
# -> 3
lambdaをatomにバインドして関数として呼び出すこともできる
(define func (quote (lambda (x y) (+ x y))))
# -> func
# func = (lambda (x y) (+ x y))
(func 1 2)
# -> 3
Railroad Diagram Generatorをお借りしてBNFから図形を生成
Program ::= SExpression+
SExpression ::= (Atom | DottedPair | List)
List ::= "(" SExpression* ")"
DottedPair ::= "(" SExpression "." SExpression ")"
Atom ::= (ATOMIC_SYMBOL | INTEGER | REAL)
ATOMIC_SYMBOL ::= "[^ \t\r\n().#]"*
INTEGER ::= "-"? "[0-9]"+
REAL ::= "-"? "[0-9]"+ "." "[0-9]"+
Program ::= SExpression+
SExpression ::= (Atom | DottedPair | List)
List ::= "(" SExpression* ")"
DottedPair ::= "(" SExpression "." SExpression ")"
Atom ::= (ATOMIC_SYMBOL | INTEGER | REAL)
ATOMIC_SYMBOL ::= "[^ \t\r\n().#]"*
INTEGER ::= "-"? "[0-9]"+
REAL ::= "-"? "[0-9]"+ "." "[0-9]"+