Drake's Weblog

3 minute read

Peter Norvig 在他的個人網站上頭,寫了一篇 (How to Write a (Lisp) Interpreter (in Python))(註), 他寫了約莫 100 行的 python script 來小小模擬一個簡化版的 Lisp Interpreter,看了不禁拍案叫絕。 下頭這個表格截取自他的網頁,指出他這 100 行的程式碼,所實作的 syntax 只有 9 個(註)。

  • var, variable reference

    A symbol is interpreted as a variable name; its value is the variable’s value.
    Example: x

  • number, constant literal

    A number evaluates to itself.
    Examples: 12 or -3.45e+6

  • (quote exp), quotation

    Return the exp literally; do not evaluate it.
    Example: (quote (a b c)) ⇒ (a b c)

  • (if test conseq alt), conditional

    Evaluate test; if true, evaluate and return conseq; otherwise evaluate and return alt.
    Example: (if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2

  • (set! var exp), assignment

    Evaluate exp and assign that value to var, which must have been previously defined (with a define or as a parameter to an enclosing procedure).
    Example: (set! x2 (* x x))

  • (define var exp), definition

    Define a new variable in the innermost environment and give it the value of evaluating the expression exp.
    Examples: (define r 3) or (define square (lambda (x) (* x x))).

  • (lambda (var…) exp), procedure

    Create a procedure with parameter(s) named var… and the expression as the body.
    Example: (lambda (r) (* 3.141592653 (* r r)))

  • (begin exp…), sequencing

    Evaluate each of the expressions in left-to-right order, and return the final value.
    Example: (begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4

  • (proc exp…), procedure call

    If proc is anything other than one of the symbols if, set!, define, lambda, begin, or quote then it is treated as a procedure. It is evaluated using the same rules defined here. All the expressions are evaluated as well, and then the procedure is called with the list of expressions as arguments.
    Example: (square 12) ⇒ 144

整個 interpreter 的核心:evaluator 只有如下的數行而已,實在很巧妙。

    def eval(x, env=global_env):
        "Evaluate an expression in an environment."
        if isa(x, Symbol):             # variable reference
            return env.find(x)[x]
        elif not isa(x, list):         # constant literal
            return x                
        elif x[0] == 'quote':          # (quote exp)
            (_, exp) = x 
            return exp 
        elif x[0] == 'if':             # (if test conseq alt)
            (_, test, conseq, alt) = x 
            return eval((conseq if eval(test, env) else alt), env)
        elif x[0] == 'set!':           # (set! var exp)
            (_, var, exp) = x 
            env.find(var)[var] = eval(exp, env)
        elif x[0] == 'define':         # (define var exp)
            (_, var, exp) = x 
            env[var] = eval(exp, env)
        elif x[0] == 'lambda':         # (lambda (var*) exp)
            (_, vars, exp) = x 
            return lambda *args: eval(exp, Env(vars, args, env))
        elif x[0] == 'begin':          # (begin exp*)
            for exp in x[1:]:
                val = eval(exp, env)
            return val 
        else:                          # (proc exp*)
            exps = [eval(exp, env) for exp in x]
            proc = exps.pop(0)
            return proc(*exps)


  • 下載程式碼
  • 執行 python lis.py。
  • 呼叫 repl() 這個函式,進入 pseudo Lisp interactive shell。
  • 一一試試下頭的 lisp expression。
    >>> repl()
    lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
    lis.py> (area 3)
    lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
    lis.py> (fact 10)
    lis.py> (fact 100)
    lis.py> (area (fact 10))
    lis.py> (define first car)
    lis.py> (define rest cdr)
    lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))
    lis.py> (count 0 (list 0 1 2 3 0 0))
    lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))

連文章的標題都搞了一堆括號,可惜無法拿來執行 XD。 其實還有 +, -, *, / 算術運算子; not, >, <, >=, <=, =, equal?, eq? 邏輯運算子; length, car, cdr, cons, append, list, list?, null 這幾個 list 運算子。

comments powered by Disqus

Recent posts



You're looking at Drake's words or statements. All opinions are my own.