アロンゾ・
チャーチ
ジョン・
マッカーシー
スティーブ・
ラッセル
ガイ・
スティール
ジェラルド・
ジェイ・サスマン
Peter Norvig / 青木靖 訳
前のエッセイでは、90行のPythonコードでシンプルなLispインタプリタを書く方法を示した(lis.py)。このエッセイでは、3倍込み入っているが、より完全なlispy.pyを実装しよう。それぞれの節で1つの機能追加を扱っている。
Lispyへの新しいデータ型の追加は3つの部分からなる。データの内部表現、それを扱う手続き、読み書きのためのシンタックスだ。ここでは4つの型を追加する(入力ポート以外はPythonのネイティブ表現をそのまま使う)。
class Symbol(str): pass
def Sym(s, symbol_table={}):
"シンボルテーブルで文字列 s に対するユニークなシンボルの登録と取得を行う。"
if s not in symbol_table: symbol_table[s] = Symbol(s)
return symbol_table[s]
_quote, _if, _set, _define, _lambda, _begin, _definemacro, = map(Sym,
"quote if set! define lambda begin define-macro".split())
_quasiquote, _unquote, _unquotesplicing = map(Sym,
"quasiquote unquote unquote-splicing".split())
残りの部分もすぐに説明する。 文字列の追加によってトークン切り分けが複雑になる。文字列の中にはスペースが現れ得るので、もはやスペースをトークンの区切りに使うわけにはいかない。代わりに、入力を分割してトークンにするために複雑な正規表現を使う。Schemeではセミコロンから行末までがコメントになる。我々はこれをトークンとした上で無視することにする。それからまた、新しく6種類のトークン #t #f ' ` , ,@ のサポートを追加する。
トークン #t と #f は、それぞれTrueとFalseのリテラルだ。シングルクォーテーションマークは続く式をクォートする。構文 'exp は (quote exp) と書くのとまったく等価である。バッククォーテーションマーク ` はSchemeでは準クォートと呼ばれており、' と似ているが、準クォート式の中では ,exp は exp そのものではなく exp の値を挿入することを意味し、,@exp は exp をリストと解して各要素を挿入することを意味する。
前のバージョンのLispyでは、すべての入力は文字列から読み込まれた。今回のバージョンでは、ポート(ファイルオブジェクト、あるいはストリームとも呼ばれる)を導入し、そこから読むことにする。これによって read-eval-print ループ (repl) がずっと便利になる。入力式が1行に納まると前提するのでなく、式が完成するまでトークンを読んでいくことができ、複数行にまたがっても問題ない。さらにPythonの対話ループがするように、エラーを捕まえて表示させることにする。以下が InPort (input port) クラスだ。
class InPort(object):
"入力ポート。文字列行を保持する。"
tokenizer = r'''\s*(,@|[('`,)]|"(?:[\\].|[^\\"])*"|;.*|[^\s('"`,;)]*)(.*)'''
def __init__(self, file):
self.file = file; self.line = ''
def next_token(self):
"次のトークンを返す。必要なら行バッファに新しいテキストを読み込む。"
while True:
if self.line == '': self.line = self.file.readline()
if self.line == '': return eof_object
token, self.line = re.match(InPort.tokenizer, self.line).groups()
if token != '' and not token.startswith(';'):
return token
read 関数の基本的な設計(と動くコード)は、 Darius Baconの示唆によるものだ(彼は他の何か所かの改善にも貢献している)。
eof_object = Symbol('#<eof-object>') # メモ: uninterned; 読めない
def readchar(inport):
"入力ポートから次の文字を読み込む。"
if inport.line != '':
ch, inport.line = inport.line[0], inport.line[1:]
return ch
else:
return inport.file.read(1) or eof_object
def read(inport):
"入力ポートからScheme式を読み込む。"
def read_ahead(token):
if '(' == token:
L = []
while True:
token = inport.next_token()
if token == ')': return L
else: L.append(read_ahead(token))
elif ')' == token: raise SyntaxError('unexpected )')
elif token in quotes: return [quotes[token], read(inport)]
elif token is eof_object: raise SyntaxError('unexpected EOF in list')
else: return atom(token)
# body of read:
token1 = inport.next_token()
return eof_object if token1 is eof_object else read_ahead(token1)
quotes = {"'":_quote, "`":_quasiquote, ",":_unquote, ",@":_unquotesplicing}
def atom(token):
'数は数にし、#t と #f は論理型に、"..."は文字列に、それ以外はシンボルにする。'
if token == '#t': return True
elif token == '#f': return False
elif token[0] == '"': return token[1:-1].decode('string_escape')
try: return int(token)
except ValueError:
try: return float(token)
except ValueError:
try: return complex(token.replace('i', 'j', 1))
except ValueError:
return Sym(token)
def to_string(x):
"PythonオブジェクトをLispの読める文字列に戻す。"
if x is True: return "#t"
elif x is False: return "#f"
elif isa(x, Symbol): return x
elif isa(x, str): return '"%s"' % x.encode('string_escape').replace('"',r'\"')
elif isa(x, list): return '('+' '.join(map(to_string, x))+')'
elif isa(x, complex): return str(x).replace('j', 'i')
else: return str(x)
def load(filename):
"ファイルのすべての式を評価する。"
repl(None, InPort(open(filename)), None)
def repl(prompt='lispy> ', inport=InPort(sys.stdin), out=sys.stdout):
"read-eval-print-loopのプロンプト。"
sys.stderr.write("Lispy version 2.0\n")
while True:
try:
if prompt: sys.stderr.write(prompt)
x = parse(inport)
if x is eof_object: return
val = eval(x)
if val is not None and out: print >> out, to_string(val)
except Exception as e:
print '%s: %s' % (type(e).__name__, e)
read-eval-print-loop がいかに改善されているか見てみよう。
>>> repl()
Lispy version 2.0
lispy> (define (cube x)
(* x (* x x))) ; input spans multiple lines
lispy> (cube 10)
1000
lispy> (cube 1) (cube 2) (cube 3) ; multiple inputs per line
1
lispy> 8
lispy> 27
lispy> (/ 3 0) ; error recovery
ZeroDivisionError: integer division or modulo by zero
lispy> (if 1 2 3 4 5) ; syntax error recovery
SyntaxError: (if 1 2 3 4 5): wrong length
lispy> (defun (f x)
(set! 3 x)) ;; early syntax error detection
SyntaxError: (set! 3 x): can set! only a symbol
lispy>
我々はまた、マクロ定義のための機能も追加する。これは define-macro 特殊形式 (標準のSchemeとは若干異なっている)によってユーザが使うことのできるもので、以下の and 形式のような派生式と呼ばれるものを内部的に定義するのにも使える。マクロ定義が使えるのは、ファイルのトップレベルか、対話セッション中、もしくはトップレベルにある begin 形式の中である。
以下は let と and のマクロ定義で、バッククォート、アンクォート、アンクォートスプライシングの構文の使い方も示している。
def let(*args):
args = list(args)
x = cons(_let, args)
require(x, len(args)>1)
bindings, body = args[0], args[1:]
require(x, all(isa(b, list) and len(b)==2 and isa(b[0], Symbol)
for b in bindings), "illegal binding list")
vars, vals = zip(*bindings)
return [[_lambda, list(vars)]+body] + list(vals)
_append, _cons, _let = map(Sym("append cons let".split))
macro_table = {_let:let} ## More macros can go here
eval(parse("""(begin
(define-macro and (lambda args
(if (null? args) #t
(if (= (length args) 1) (car args)
`(if ,(car args) (and ,@(cdr args)) #f)))))
;; 追加のマクロをここに
)"""))
Schemeには while も for ループもなく、繰り返しはもっぱら再帰による。これによって言語がシンプルになるが、潜在的な問題もある。個々の再帰呼出しでコールスタックが増大するなら、再帰の深さが制限され、したがってループできる回数が制限されることになる。実装によっては、この制限は繰り返しが数百回までという小ささになる。あらゆる再帰に対しコールスタックを大きくするのではなく、必要な場合に限るよう eval を書き換えることで、この制限は引き上げることができる。
v を 1、twice を手続き (lambda (y) (* 2 y)) として、式(if (> v 0) (begin 1 (begin 2 (f (- v 1))))) の評価を行うことを考えてみよう。lis.pyのバージョンの eval では、矢印を eval の再帰呼出しとして、実行の経過が以下のようになる。
⇒ eval(x=(if (> v 0) (begin 1 (begin 2 (twice (- v 1))))), env={'v':1})
⇒ eval(x=(begin 1 (begin 2 (twice (- v 1)))), env={'v':1})
⇒ eval(x=(begin 2 (twice (- v 1)))), env={'v':1})
⇒ eval(x=(twice (- v 1)))), env={'v':1})
⇒ eval(x=(* 2 y), env={'y':0})
⇐ 0
しかしこの再帰呼出しは必要ないことに注意してほしい。再帰呼出しの戻り値を呼び元がすぐに返しているなら、再帰する代わりに元の eval(x, env) の呼び出しの x の値 (場合によっては env も) を変更することで済ませることができる。古い x の値が必要ない場合にはいつでもそうすることができる。すると呼出しの経過は以下のようになる。
⇒ eval(x=(if (> v 0) (begin 1 (begin 2 (twice (- v 1))))), env={'v':1})
x = (begin 1 (begin 2 (twice (- v 1))))
x = (begin 2 (twice (- v 1))))
x = (twice (- v 1))))
x = (* 2 y); env = {'y':0}
⇐ 0
以下はこのような動作をする eval の実装だ。本体を while True ループでくるんでおり、ほとんどの部分の実装は変わっていない。しかし3箇所で変数 x (評価される式)を更新している。 if と begin とユーザ定義手続きの手続き呼び出しのところだ(手続き呼び出しの場合には、 x を手続きの本体に置き換えるだけでなく、env を手続きの引数のバインディングを持つ新しい環境へと更新する)。
def eval(x, env=global_env):
"環境の中で式を評価する"
while True:
if isa(x, Symbol): # 変数参照
return env.find(x)[x]
elif not isa(x, list): # 定数リテラル
return x
elif x[0] is _quote: # (quote exp)
(_, exp) = x
return exp
elif x[0] is _if: # (if test conseq alt)
(_, test, conseq, alt) = x
x = (conseq if eval(test, env) else alt)
elif x[0] is _set: # (set! var exp)
(_, var, exp) = x
env.find(var)[var] = eval(exp, env)
return None
elif x[0] is _define: # (define var exp)
(_, var, exp) = x
env[var] = eval(exp, env)
return None
elif x[0] is _lambda: # (lambda (var*) exp)
(_, vars, exp) = x
return Procedure(vars, exp, env)
elif x[0] is _begin: # (begin exp+)
for exp in x[1:-1]:
eval(exp, env)
x = x[-1]
else: # (proc exp*)
exps = [eval(exp, env) for exp in x]
proc = exps.pop(0)
if isa(proc, Procedure):
x = proc.exp
env = Env(proc.parms, exps, proc.env)
else:
return proc(*exps)
この実装により、メモリを使い果たすことなくいくらでも深く再帰する手続きを書けるようになる。しかしそれを機能させるためには、手続きを若干作り変える必要があるかもしれない。以下に挙げた、0 から n: までの整数を加え合わせる関数の2つの実装を考えてほしい。
(define (sum-to n)
(if (= n 0)
0
(+ n (sum-to (- n 1)))))
(define (sum2 n acc)
(if (= n 0)
acc
(sum2 (- n 1) (+ n acc))))
最初の方が分かりやすいが、(sum-to 1000) を計算させると、エラー"RuntimeError: maximum recursion depth exceeded"が出ることになる。2番目の方では、sum2 の再帰呼出しは関数本体の最後にあるので、最初の100万個の整数の和を (sum2 1000000 0) で安全に計算して答え 500000500000 を得ることができる。2番目の引数 acc はそれまでに計算した値を累積していることに注意してほしい。このスタイルの累積方法を身につければ、いくらでも深い再帰ができるようになる。
lispy> (call/cc (lambda (throw)
(+ 5 (* 10 (call/cc (lambda (escape) (* 100 (escape 3))))))))
35
lispy> (call/cc (lambda (throw)
(+ 5 (* 10 (call/cc (lambda (escape) (* 100 (throw 3))))))))
3
最初の例では、 (escape 3) の評価でSchemeは現在の継続を中止して、包含されている call/cc の呼出しの戻り値として3を返す。結果は(+ 5 (* 10 3))、つまり35となる。
2番目の例では (throw 3) は2レベル上まで戻って、トップレベルに値3を返すことになる。一般に call/cc は1つの引数 proc を取り、これは1引数の手続きでなければならない。 ここでは throw と名付けた手続きを作り、それを引数として proc を呼び出す。throw が呼ばれるとき、引数は call/cc の呼出し全体の値である。throw が呼ばれない場合には proc で計算される値を返す。以下が実装だ。
def callcc(proc):
"現在の継続とともにprocを呼び出す。脱出のみ。"
ball = RuntimeWarning("Sorry, can't continue this continuation any longer.")
def throw(retval): ball.retval = retval; raise ball
try:
return proc(throw)
except RuntimeWarning as w:
if w is ball: return ball.retval
else: raise w
この実装により手続きからの非局所的な脱出ができるようになる。ただしこれは本当のSchemeの call/cc が持つ力すべてを実装してはいない。本当のSchemeでは継続は値を返すためだけでなく、継続を保存しておいてそれを何度も呼び出し、そのたびに同じ場所に戻ることができる。
標準のSchemeの手続き list は (list 1 2)、(list 1 2 3) のように、任意個の引数に対して呼び出すことができる。Schemeではユーザもこのような手続きを構文 (lambda args body) を使って定義することができる。ここでargs は手続き呼び出しで渡される引数リストにバインドされる仮引数を表す1つのシンボルで、body は手続きの本体である。実装は parms がリストではなくシンボルであることをチェックする小さな修正を Env.__init__ に入れるだけだ。
class Env(dict):
"環境: ペア{'var':val}のdictで、外部環境(outer)を持つ。"
def __init__(self, parms=(), args=(), outer=None):
# 仮引数のリストを対応する引数に、あるいは1つの仮引数を引数のリストにバインドする。
self.outer = outer
if isa(parms, Symbol):
self.update({parms:list(args)})
else:
if len(args) != len(parms):
raise TypeError('expected %s, given %s, '
% (to_string(parms), to_string(args)))
self.update(zip(parms,args))
def find(self, var):
"var が現れる一番内側のEnvを見つける。"
if var in self: return self
elif self.outer is None: raise LookupError(var)
else: return self.outer.find(var)
parms がシンボルなら、それを引数のリストにバインドする。そうでない場合はそれぞれの仮引数を対応する引数にバインドする。本当のSchemeではさらに (lambda (arg1 arg2 . rest) ...) という構文も使うことができる。我々はドットペアのないPythonのリストを使っているため、これはできない。
(define f (lambda (x) (set! 3 x))) (define g (lambda (3) (if (x = 0)))) (define h (lambda (x) (if (x = 0) 1 2 3)))
最初のバージョンのLispyでは、これらの定義を評価させても文句は言わなかった。しかし定義された関数を呼び出すや否や実行時エラーが起きた。一般にエラーは可能な限り早く通知すべきなので、新しいバージョンのLispyでは、呼び出されるまで待つのではなく、関数が定義された時点で適切なエラーメッセージを出すことにしよう。
これは手続き parse を改良することで実現する。最初のバージョンのLispyでは、parse は read で実装されていた。言い換えると、任意の式がプログラムとして受け入れられていた。新しいバージョンでは、それぞれの式の正しさを定義される時点でチェックする。チェックするのは、それぞれの特殊形式が正しい数の引数を持つことと、set! と define がシンボルに対して使われていることだ。ここではまた、マクロと(2)節で定義した準クォートの展開も行う。さらに下記のテーブルに書いたような若干寛容な書き方を許容することにする。左側の式は最初のバージョンのLispyでは不正だったが、新しいバージョンでは右側の対応する式と解釈して受け入れることにする。
| 拡張された記法 | 式 | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
(begin)| None
| (if test conseq) | (if test conseq None)
| (define (f arg...) body...) | (define f (lambda (arg...) body...)
| (lambda (arg...) e1 e2...) | (lambda (arg...) (begin e1 e2...))
| `exp | (quasiquote exp) expand , and
,@ within exp
| (macro-name arg...) | expansion of (macro-name arg...)
| |
以下が parse の定義だ。
def parse(inport):
"プログラムを構文解析する。読み込み、展開/エラーチェックを行う。"
# 後方互換性のため、文字列を渡されたときはInPortに変換する。
if isinstance(inport, str): inport = InPort(StringIO.StringIO(inport))
return expand(read(inport), toplevel=True)
以下が expand の定義だ。expand が eval の2倍の長さになっているのは奇妙に思えるかもしれない。しかし expand は実際より難しい仕事をしているのだ。コードのそれぞれの部分が正しいか確認するために eval がすることのほとんどすべてを行うのに加え、不正なコードには意味のあるエラーメッセージを出したり、拡張された記法を正しい基本形に変えたりする必要があるのだ。
def expand(x, toplevel=False):
"x のツリーを辿って最適化/修正をし、SyntaxErrorを送出する。"
require(x, x!=[]) # () => Error
if not isa(x, list): # constant => unchanged
return x
elif x[0] is _quote: # (quote exp)
require(x, len(x)==2)
return x
elif x[0] is _if:
if len(x)==3: x = x + [None] # (if t c) => (if t c None)
require(x, len(x)==4)
return map(expand, x)
elif x[0] is _set:
require(x, len(x)==3);
var = x[1] # (set! non-var exp) => Error
require(x, isa(var, Symbol), "can set! only a symbol")
return [_set, var, expand(x[2])]
elif x[0] is _define or x[0] is _definemacro:
require(x, len(x)>=3)
_def, v, body = x[0], x[1], x[2:]
if isa(v, list) and v: # (define (f args) body)
f, args = v[0], v[1:] # => (define f (lambda (args) body))
return expand([_def, f, [_lambda, args]+body])
else:
require(x, len(x)==3) # (define non-var/list exp) => Error
require(x, isa(v, Symbol), "can define only a symbol")
exp = expand(x[2])
if _def is _definemacro:
require(x, toplevel, "define-macro only allowed at top level")
proc = eval(exp)
require(x, callable(proc), "macro must be a procedure")
macro_table[v] = proc # (define-macro v proc)
return None # => None; v:proc を macro_table に追加
return [_define, v, exp]
elif x[0] is _begin:
if len(x)==1: return None # (begin) => None
else: return [expand(xi, toplevel) for xi in x]
elif x[0] is _lambda: # (lambda (x) e1 e2)
require(x, len(x)>=3) # => (lambda (x) (begin e1 e2))
vars, body = x[1], x[2:]
require(x, (isa(vars, list) and all(isa(v, Symbol) for v in vars))
or isa(vars, Symbol), "illegal lambda argument list")
exp = body[0] if len(body) == 1 else [_begin] + body
return [_lambda, vars, expand(exp)]
elif x[0] is _quasiquote: # `x => expand_quasiquote(x)
require(x, len(x)==2)
return expand_quasiquote(x[1])
elif isa(x[0], Symbol) and x[0] in macro_table:
return expand(macro_table[x[0]](*x[1:]), toplevel) # (m arg...)
else: # => m がマクロならマクロ展開
return map(expand, x) # (f arg...) => それぞれを展開
def require(x, predicate, msg="wrong length"):
"predicate が偽の場合構文エラーを通知する。"
if not predicate: raise SyntaxError(to_string(x)+': '+msg)
def expand_quasiquote(x):
"""準クォートの展開 `x => 'x; `,x => x; `(,@x y) => (append x y) """
if not is_pair(x):
return [_quote, x]
require(x, x[0] is not _unquotesplicing, "can't splice here")
if x[0] is _unquote:
require(x, len(x)==2)
return x[1]
elif is_pair(x[0]) and x[0][0] is _unquotesplicing:
require(x[0], len(x[0])==2)
return [_append, x[0][1], expand_quasiquote(x[1:])]
else:
return [_cons, expand_quasiquote(x[0]), expand_quasiquote(x[1:])]
ここでは add_globals を拡張してSchemeのプリミティブな手続きをもう少し追加し、トータルで75個にする。まだ欠けているものが80くらいあるが、必要であればここで追加することができる。
def is_pair(x): return x != [] and isa(x, list)
def add_globals(self):
"Scheme標準の手続きの一部を追加する"
import math, cmath, operator as op
self.update(vars(math))
self.update(vars(cmath))
self.update({
'+':op.add, '-':op.sub, '*':op.mul, '/':op.div, 'not':op.not_,
'>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq,
'equal?':op.eq, 'eq?':op.is_, 'length':len, 'cons':lambda x,y:[x]+list(y),
'car':lambda x:x[0], 'cdr':lambda x:x[1:], 'append':op.add,
'list':lambda *x:list(x), 'list?': lambda x:isa(x,list),
'null?':lambda x:x==[], 'symbol?':lambda x: isa(x, Symbol),
'boolean?':lambda x: isa(x, bool), 'pair?':is_pair,
'port?': lambda x:isa(x,file), 'apply':lambda proc,l: proc(*l),
'eval':lambda x: eval(expand(x)), 'load':lambda fn: load(fn), 'call/cc':callcc,
'open-input-file':open,'close-input-port':lambda p: p.file.close(),
'open-output-file':lambda f:open(f,'w'), 'close-output-port':lambda p: p.close(),
'eof-object?':lambda x:x is eof_object, 'read-char':readchar,
'read':read, 'write':lambda x,port=sys.stdout:port.write(to_string(x)),
'display':lambda x,port=sys.stdout:port.write(x if isa(x,str) else to_string(x))})
return self
isa = isinstance
global_env = add_globals(Env())
bash$ python lispytest.py
python lispytest.py
(quote (testing 1 (2.0) -3.14e159)) => (testing 1 (2.0) -3.14e+159)
(+ 2 2) => 4
(+ (* 2 100) (* 1 10)) => 210
(if (> 6 5) (+ 1 1) (+ 2 2)) => 2
(if (< 6 5) (+ 1 1) (+ 2 2)) => 4
(define x 3) => None
x => 3
(+ x x) => 6
(begin (define x 1) (set! x (+ x 1)) (+ x 1)) => 3
((lambda (x) (+ x x)) 5) => 10
(define twice (lambda (x) (* 2 x))) => None
(twice 5) => 10
(define compose (lambda (f g) (lambda (x) (f (g x))))) => None
((compose list twice) 5) => (10)
(define repeat (lambda (f) (compose f f))) => None
((repeat twice) 5) => 20
((repeat (repeat twice)) 5) => 80
(define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1)))))) => None
(fact 3) => 6
(fact 50) => 30414093201713378043612608166064768844377641568960512000000000000
(define abs (lambda (n) ((if (> n 0) + -) 0 n))) => None
(list (abs -3) (abs 0) (abs 3)) => (3 0 3)
(define combine (lambda (f)
(lambda (x y)
(if (null? x) (quote ())
(f (list (car x) (car y))
((combine f) (cdr x) (cdr y))))))) => None
(define zip (combine cons)) => None
(zip (list 1 2 3 4) (list 5 6 7 8)) => ((1 5) (2 6) (3 7) (4 8))
(define riff-shuffle (lambda (deck) (begin
(define take (lambda (n seq) (if (<= n 0) (quote ()) (cons (car seq) (take (- n 1) (cdr seq))))))
(define drop (lambda (n seq) (if (<= n 0) seq (drop (- n 1) (cdr seq)))))
(define mid (lambda (seq) (/ (length seq) 2)))
((combine append) (take (mid deck) deck) (drop (mid deck) deck))))) => None
(riff-shuffle (list 1 2 3 4 5 6 7 8)) => (1 5 2 6 3 7 4 8)
((repeat riff-shuffle) (list 1 2 3 4 5 6 7 8)) => (1 3 5 7 2 4 6 8)
(riff-shuffle (riff-shuffle (riff-shuffle (list 1 2 3 4 5 6 7 8)))) => (1 2 3 4 5 6 7 8)
********************************************* lis.py: 0 out of 29 tests fail.
(quote (testing 1 (2.0) -3.14e159)) => (testing 1 (2.0) -3.14e+159)
(+ 2 2) => 4
(+ (* 2 100) (* 1 10)) => 210
(if (> 6 5) (+ 1 1) (+ 2 2)) => 2
(if (< 6 5) (+ 1 1) (+ 2 2)) => 4
(define x 3) => None
x => 3
(+ x x) => 6
(begin (define x 1) (set! x (+ x 1)) (+ x 1)) => 3
((lambda (x) (+ x x)) 5) => 10
(define twice (lambda (x) (* 2 x))) => None
(twice 5) => 10
(define compose (lambda (f g) (lambda (x) (f (g x))))) => None
((compose list twice) 5) => (10)
(define repeat (lambda (f) (compose f f))) => None
((repeat twice) 5) => 20
((repeat (repeat twice)) 5) => 80
(define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1)))))) => None
(fact 3) => 6
(fact 50) => 30414093201713378043612608166064768844377641568960512000000000000
(define abs (lambda (n) ((if (> n 0) + -) 0 n))) => None
(list (abs -3) (abs 0) (abs 3)) => (3 0 3)
(define combine (lambda (f)
(lambda (x y)
(if (null? x) (quote ())
(f (list (car x) (car y))
((combine f) (cdr x) (cdr y))))))) => None
(define zip (combine cons)) => None
(zip (list 1 2 3 4) (list 5 6 7 8)) => ((1 5) (2 6) (3 7) (4 8))
(define riff-shuffle (lambda (deck) (begin
(define take (lambda (n seq) (if (<= n 0) (quote ()) (cons (car seq) (take (- n 1) (cdr seq))))))
(define drop (lambda (n seq) (if (<= n 0) seq (drop (- n 1) (cdr seq)))))
(define mid (lambda (seq) (/ (length seq) 2)))
((combine append) (take (mid deck) deck) (drop (mid deck) deck))))) => None
(riff-shuffle (list 1 2 3 4 5 6 7 8)) => (1 5 2 6 3 7 4 8)
((repeat riff-shuffle) (list 1 2 3 4 5 6 7 8)) => (1 3 5 7 2 4 6 8)
(riff-shuffle (riff-shuffle (riff-shuffle (list 1 2 3 4 5 6 7 8)))) => (1 2 3 4 5 6 7 8)
() =raises=> SyntaxError (): wrong length
(set! x) =raises=> SyntaxError (set! x): wrong length
(define 3 4) =raises=> SyntaxError (define 3 4): can define only a symbol
(quote 1 2) =raises=> SyntaxError (quote 1 2): wrong length
(if 1 2 3 4) =raises=> SyntaxError (if 1 2 3 4): wrong length
(lambda 3 3) =raises=> SyntaxError (lambda 3 3): illegal lambda argument list
(lambda (x)) =raises=> SyntaxError (lambda (x)): wrong length
(if (= 1 2) (define-macro a 'a)
(define-macro a 'b)) =raises=> SyntaxError (define-macro a (quote a)): define-macro only allowed at top level
(define (twice x) (* 2 x)) => None
(twice 2) => 4
(twice 2 2) =raises=> TypeError expected (x), given (2 2),
(define lyst (lambda items items)) => None
(lyst 1 2 3 (+ 2 2)) => (1 2 3 4)
(if 1 2) => 2
(if (= 3 4) 2) => None
(define ((account bal) amt) (set! bal (+ bal amt)) bal) => None
(define a1 (account 100)) => None
(a1 0) => 100
(a1 10) => 110
(a1 10) => 120
(define (newton guess function derivative epsilon)
(define guess2 (- guess (/ (function guess) (derivative guess))))
(if (< (abs (- guess guess2)) epsilon) guess2
(newton guess2 function derivative epsilon))) => None
(define (square-root a)
(newton 1 (lambda (x) (- (* x x) a)) (lambda (x) (* 2 x)) 1e-8)) => None
(> (square-root 200.) 14.14213) => #t
(< (square-root 200.) 14.14215) => #t
(= (square-root 200.) (sqrt 200.)) => #t
(define (sum-squares-range start end)
(define (sumsq-acc start end acc)
(if (> start end) acc (sumsq-acc (+ start 1) end (+ (* start start) acc))))
(sumsq-acc start end 0)) => None
(sum-squares-range 1 3000) => 9004500500
(call/cc (lambda (throw) (+ 5 (* 10 (throw 1))))) ;; throw => 1
(call/cc (lambda (throw) (+ 5 (* 10 1)))) ;; do not throw => 15
(call/cc (lambda (throw)
(+ 5 (* 10 (call/cc (lambda (escape) (* 100 (escape 3)))))))) ; 1 level => 35
(call/cc (lambda (throw)
(+ 5 (* 10 (call/cc (lambda (escape) (* 100 (throw 3)))))))) ; 2 levels => 3
(call/cc (lambda (throw)
(+ 5 (* 10 (call/cc (lambda (escape) (* 100 1))))))) ; 0 levels => 1005
(* 1i 1i) => (-1+0i)
(sqrt -1) => 1i
(let ((a 1) (b 2)) (+ a b)) => 3
(let ((a 1) (b 2 3)) (+ a b)) =raises=> SyntaxError (let ((a 1) (b 2 3)) (+ a b)): illegal binding list
(and 1 2 3) => 3
(and (> 2 1) 2 3) => 3
(and) => #t
(and (> 2 1) (> 2 3)) => #f
(define-macro unless (lambda args `(if (not ,(car args)) (begin ,@(cdr args))))) ; test ` => None
(unless (= 2 (+ 1 1)) (display 2) 3 4) => None
2
(unless (= 4 (+ 1 1)) (display 2) (display "\n") 3 4) => 4
(quote x) => x
(quote (1 2 three)) => (1 2 three)
'x => x
'(one 2 3) => (one 2 3)
(define L (list 1 2 3)) => None
`(testing ,@L testing) => (testing 1 2 3 testing)
`(testing ,L testing) => (testing (1 2 3) testing)
`,@L =raises=> SyntaxError (unquote-splicing L): can't splice here
'(1 ;test comments '
;skip this line
2 ; more ; comments ; ) )
3) ; final comment => (1 2 3)
********************************************* lispy.py: 0 out of 81 tests fail.
|
アロンゾ・ チャーチ |
ジョン・ マッカーシー |
スティーブ・ ラッセル |
ガイ・ スティール |
ジェラルド・ ジェイ・サスマン |
|---|---|---|---|---|
|
|
|
|
|
アロンゾ・チャーチは1932年にラムダ計算を定義した。ラムダ計算がプログラミング言語の基礎として使えることをジョン・マッカーシーが1958年末に提案し、1959年にスティーブ・ラッセルが最初のLispインタプリタをIBM 704のアセンブラで書いた。1975年にジェラルド・ジェイ・サスマンとガイ・スティールがLispの方言であるSchemeを作った。
(メモ 手続き/関数を導入するときに lambda を使うのは変に思うかもしれない。この記法はアロンゾ・チャーチにまで遡る。1930年に彼は「ハット」記号を使い始め、2乗関数を"ŷ . y × y"のように書いた。しかし植字工が面倒なのでハットを引数の左に移して大文字のラムダに変え、"Λy . y × y"のようにした。その後大文字のラムダは小文字に変わり、数学書では"λy . y × y"、Lispでは (lambda (y) (* y y)) と書かれるようになった。私だったら fun か ^ を使っていたと思う。
| home rss |