Lithp.py (~2008)

lithp.py # Lithp - ジョン・マッカーシーによるオリジナルのLispインタープリタ。Lithpの非常に詳細にドキュメント化されたコードはGithubで見つけることができます。Lispインタープリタを書くだけでは十分ではありませんでした -- 私は学んだことを皆さんと共有したいとも思いました。このソースコードを読むことで、ジョン・マッカーシー、スティーブ・ラッセル、ティモシー・P・ハート、マイク・レヴィン、そしておまけとして私自身の思想を垣間見ることができます。以下のソースファイルが閲覧可能です: atom.py env.py error.py fun.py interface.py lisp.py lithp.py (このファイル) number.py reader.py seq.py core.lisp Lithpインタープリタは動作するためにPython 2.6.1+を必要とします。コメント、エラー報告、逸話などをLithp Githubプロジェクトページにお願いします。 import pdb import getopt, sys, io from env import Environment from fun import Function from atom import TRUE from atom import FALSE from lisp import Lisp from reader import Reader from error import Error from fun import Lambda from fun import Closure NAME = "Lithp" VERSION = "v1.1" WWW = "http://fogus.me/fun/lithp/" PROMPT = "lithp" DEPTH_MARK = "." # Lithperクラスはインタープリタのドライバです。以下のことを行います: class Lithp(Lisp): # グローバル環境を初期化する # コマンドライン引数をパースし、適切に処理する # 基本的なLisp関数を初期化する # 入力を読み込む # 評価する # 出力する # #4に戻ってループする def __init__( self): iostreams=(sys.stdin, sys.stdout, sys.stderr) (self.stdin, self.stdout, self.stderr) = iostreams self.debug = False self.verbose = True self.core = True self.closures = True self.rdr = Reader() self.environment = Environment() self.init() # def init(self): # コア関数を定義 self.environment.set("eq", Function(self.eq)) self.environment.set("quote", Function(self.quote)) self.environment.set("car", Function(self.car)) self.environment.set("cdr", Function(self.cdr)) self.environment.set("cons", Function(self.cons)) self.environment.set("atom", Function(self.atom)) self.environment.set("cond", Function(self.cond)) # ユーティリティ関数を定義 self.environment.set("print", Function( self.println)) # スペシャルフォーム self.environment.set("lambda", Function(self.lambda_)) self.environment.set("label", Function(self.label)) # コアシンボルを定義 self.environment.set("t", TRUE) # 空のリストは一つだけであり、nilと名付けられている self.environment.set("nil", FALSE) # メタ要素を定義 self.environment.set("__lithp__", self) self.environment.set("__global__", self.environment) # def usage(self): self.print_banner() print print NAME.lower(), " <options> [lithp files]\n" # def print_banner(self): print "The", NAME, "programming shell", VERSION print " by Fogus,", WWW print " Type :help for more information" print # def print_help(self): print "Help for Lithp v", VERSION print " Type :help for more information" print " Type :env to see the bindings in the current environment" print " Type :load followed by one or more filenames to load source files" print " Type :quit to exit the interpreter" # def push(self, env=None): if env: self.environment = self.environment.push(env) else: self.environment = self.environment.push() # def pop(self): self.environment = self.environment.pop() # def repl(self): while True: # CLIPSからのS式解析アプローチを拝借 source = self.get_complete_command() # REPLディレクティブをチェック if source in [":quit"]: break elif source in [":help"]: self.print_help() elif source.startswith(":load"): files = source.split(" ")[1:] self.process_files(files) elif source in [":env"]: print(self.environment) else: self.process(source) # ソースはS式ごとに処理されます。 def process(self, source): sexpr = self.rdr.get_sexpr(source) while sexpr: result = None try: result = self.eval(sexpr) except Error as err: print(err) if self.verbose: self.stdout.write(" %s\n" % result) sexpr = self.rdr.get_sexpr() # 私の人生の中で、クロージャと動的スコープは共存できないと常に聞いていました。思考実験として、なぜそうなるのかを視覚化できます。つまり、クロージャは変数の文脈的なバインディングをキャプチャする一方で、動的スコープでのルックアップは動的スタック上で発生します。これは、変数が一意である限り、その変数をクローズできるかもしれませんが、他の誰かが同じ名前の変数を定義し、クローズされた変数をルックアップしようとした途端、動的スタック上の最も上位のバインディングに解決されてしまうことを意味します。これは、同じ名前の変数がポップされる前にルックアップが発生することを前提としています。これは概念的には理解しやすいものの、実際に何が起こるかを見てみたかったのです -- そして、それはあまりきれいなものではありませんでした。 def lambda_(self, env, args): if self.environment != env.get("__global__") and self.closures: return Closure(env, args[0], args[1:]) else: return Lambda(args[0], args[1:]) # 評価をフォームに委譲します。 def eval(self, sexpr): try: return sexpr.eval(self.environment) except ValueError as err: print(err) return FALSE # 完全なコマンドは、完全なS式として定義されます。簡単に言えば、これは任意の原子またはバランスの取れた括弧のセットを持つ任意のリストです。 def get_complete_command(self, line="", depth=0): if line != "": line = line + " " if self.environment.level != 0: prompt = PROMPT + " %i%s " % (self.environment.level, DEPTH_MARK * (depth+1)) else: if depth == 0: prompt = PROMPT + "> " else: prompt = PROMPT + "%s " % (DEPTH_MARK * (depth+1)) line = line + self.read_line(prompt) # 括弧のバランスを取るために使用 balance = 0 for ch in line: if ch == "(": # これは完璧ではないが、今のところこれで十分 balance = balance + 1 elif ch == ")": # 右括弧が多すぎるのは問題 balance = balance - 1 if balance > 0: # バランスの取れた括弧はゼロを返す return self.get_complete_command( line, depth+1) elif balance < 0: raise ValueError("Invalid paren pattern") else: return line # def read_line( self, prompt) : if prompt and self.verbose: self.stdout.write("%s" % prompt) self.stdout.flush() line = self.stdin.readline() if(len(line) == 0): return "EOF" if line[-1] == "\n": line = line[:-1] return line # Lithpはリーダーの配管を使ってファイルを処理します。 def process_files(self, files): self.verbose = False for filename in files: infile = open( filename, 'r') self.stdin = infile source = self.get_complete_command() while(source not in ["EOF"]): self.process(source) source = self.get_complete_command() infile.close() self.stdin = sys.stdin self.verbose = True if __name__ == '__main__': lithp = Lithp() try: opts, files = getopt.getopt(sys.argv[1:], "hd", ["help", "debug", "no-core", "no-closures"]) except getopt.GetoptError as err: # ヘルプ情報を表示して終了: print(str( err)) # 「オプション -a は認識されません」のようなメッセージが出力される lithp.usage() sys.exit(1) for opt,arg in opts: if opt in ("--help", "-h"): lithp.usage() sys.exit(0) elif opt in ("--debug", "-d"): lithp.verbose = True elif opt in ("--no-core"): lithp.core = False elif opt in ("--no-closures"): lithp.closures = False else: print("unknown option " + opt) # コアLisp関数を処理する (該当する場合) if lithp.core: lithp.process_files(["../core.lisp"]) if len(files) > 0: lithp.process_files(files) lithp.print_banner() lithp.repl() # 参考文献 # (McCarthy 1979) History of Lisp by John MaCarthy # (McCarthy 1960) Recursive functions of symbolic expressions and their computation by machine, part I by John McCarthy # (Church 1941) The Calculi of Lambda-Conversion by Alonzo Church # (Baker 1993) Equal Rights for Functional Objects or, The More Things Change, The More They Are the Same by Henry Baker # (Kleene 1952) Introduction of Meta-Mathematics by Stephen Kleene # (McCarthy 1962) LISP 1.5 Programmer's Manual by John McCarthy, Daniel Edwards, Timothy Hart, and Michael Levin # (IBM 1955) IBM 704 Manual of Operation here # (Hart 1963) AIM-57: MACRO Definitions for LISP by Timothy P. Hart