1958 - McCarthy 的 LISP（遞迴與符號計算的語言）#

(DEFUN FACT (N) (COND ((EQ N 0) 1) (T (TIMES N (FACT (SUB1 N))))))

(+ 1 2)              ; 程式（求值後 = 3）
'(+ 1 2)             ; 資料（串列 (+ 1 2)）

# 用 Python 實現一個微型 LISP（eval/apply 循環）
def tokenize(s):
    """詞法：切成記號"""
    return s.replace('(', ' ( ').replace(')', ' ) ').split()

def parse(tokens):
    """語法：建 S-運算式樹"""
    if len(tokens) == 0:
        raise SyntaxError("unexpected EOF")
    tok = tokens.pop(0)
    if tok == '(':
        lst = []
        while tokens[0] != ')':
            lst.append(parse(tokens))
        tokens.pop(0)   # 吃掉 ')'
        return lst
    elif tok == ')':
        raise SyntaxError("unexpected )")
    else:
        return atom(tok)

def atom(tok):
    """數字或符號"""
    try:
        return int(tok)
    except ValueError:
        try:
            return float(tok)
        except ValueError:
            return Symbol(tok)

class Symbol(str):
    pass

# 環境：變數與函數
import operator as op
def standard_env():
    env = {
        '+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv,
        '>': op.gt, '<': op.lt, '>=': op.ge, '<=': op.le,
        '=': op.eq,
        'car': lambda x: x[0],
        'cdr': lambda x: x[1:],
        'cons': lambda x, y: [x] + y,
        'atom': lambda x: isinstance(x, Symbol),
        'len': len,
    }
    return env

global_env = standard_env()

def evaluate(x, env=global_env):
    """eval/apply 循環（LISP 的心臟）"""
    if isinstance(x, Symbol):
        return env[x]              # 變數查表
    elif isinstance(x, (int, float)):
        return x                    # 常數
    elif x[0] == 'if':
        (_, test, conseq, alt) = x
        return evaluate(conseq if evaluate(test, env) else alt, env)
    elif x[0] == 'lambda':
        (_, params, body) = x
        def closure(*args, _params=params, _body=body, _env=env):
            local = dict(zip(_params, args))
            local.update(_env)
            return evaluate(_body, local)
        return closure
    elif x[0] == 'quote':
        return x[1]                 # 引號：不求值
    elif x[0] == 'define':
        (_, name, exp) = x
        env[name] = evaluate(exp, env)
    else:
        proc = evaluate(x[0], env)
        args = [evaluate(arg, env) for arg in x[1:]]
        return proc(*args)          # apply

# 測試：微型 LISP
print("微型 LISP（eval/apply 循環）：")
print(f"  (+ 1 2) = {evaluate(parse(tokenize('(+ 1 2)')))}")
print(f"  (* 3 (+ 2 4)) = {evaluate(parse(tokenize('(* 3 (+ 2 4))')))}")
print(f"  (car (cons 1 2)) = {evaluate(parse(tokenize('(car (cons 1 (quote (2))))')))}")
print(f"  (cons 1 (cons 2 nil)) = {evaluate(parse(tokenize('(cons 1 (cons 2 (quote ())))')))}")

# 定義遞迴函數：階乘
program = """
(define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))))
(fact 5)
"""
tokens = tokenize(program)
result = None
while tokens:
    result = evaluate(parse(tokens))
print(f"\n遞迴階乘：(fact 5) = {result}")

# 垃圾回收的概念示範（Python 自帶 GC）
import gc
print("\n垃圾回收（McCarthy 1959 的發明）：")
class Node:
    def __init__(self, name):
        self.name = name
        self.ref = None
    def __repr__(self):
        return f"Node({self.name})"

# 創建一個循環引用（GC 的難題）
a = Node("a"); b = Node("b")
a.ref = b; b.ref = a   # 循環引用
del a, b               # 刪除外部引用
collected = gc.collect()   # GC 應回收循環垃圾
print(f"  循環引用 + 外部刪除 → gc.collect() 回收 {collected} 個物件")
print("  → 標記-清除法可以處理循環引用（引用計數不能）")
print("  → Python、Java、Go 的 GC 都是 McCarthy 思想的後代")

微型 LISP（eval/apply 循環）：
  (+ 1 2) = 3
  (* 3 (+ 2 4)) = 18
  (car (cons 1 2)) = 1
  (cons 1 (cons 2 nil)) = [1, 2]

遞迴階乘：(fact 5) = 120

垃圾回收（McCarthy 1959 的發明）：
  循環引用 + 外部刪除 → gc.collect() 回收 2 個物件
  → 標記-清除法可以處理循環引用（引用計數不能）
  → Python、Java、Go 的 GC 都是 McCarthy 思想的後代