HN 日本語サマリー

← 一覧へ戻る
プログラミング

Lithp.py (~2008)

Lithp.py (~2008) (fogus.me)

8 pointsby wglb1 コメント

要約

「Lithp.py」は、ジョン・マッカーシーによるオリジナルのLispインタープリタをPythonで実装したものです。このプロジェクトは、Lispの初期の設計者の思想を垣間見ることができる、教育的な目的も兼ねた詳細なドキュメント付きのコードを提供しています。Python 2.6.1以降で動作し、主要なLisp関数やREPLを備えています。

全文翻訳

lithp.py

Lithp - John McCarthyのオリジナルのLispインタプリタ。

詳細にドキュメント化されたLithpのコードはGithubで見つけることができます。

Lispインタプリタを書くだけでは十分ではありませんでした――私は学んだことをあなたと共有したかったのです。このソースコードを読むことは、John McCarthy、Steve Russell、Timothy P. Hart、Mike Levin、そしておまけとして私自身の思考プロセスを垣間見ることができます。以下のソースファイルが閲覧可能です:

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 = "."

Lithpクラスはインタプリタのドライバーです。以下の処理を行います:

class Lithp(Lisp):
  1. グローバル環境を初期化する
  2. コマンドライン引数を解析し、適切に行動する
  3. 基本的なLisp関数を初期化する
  4. 入力を読み取る
  5. 評価する
  6. 出力する
  7. 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)) # will print something like "option -a not recognized"
        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 こちら
  • (Hart 1963) AIM-57: MACRO Definitions for LISP by Timothy P. Hart