# Chapter 003: Recursion Trap
# Status: Timeline 1975.6.21
# Location: MIT AI Lab
>>> Timeline Jump Complete
>>> Current Location: MIT AI Lab, 1975
>>> Mission: Debug infinite recursion in LISP interpreter
>>> Warning: Stack overflow may corrupt the entire system
>>> Status: Connecting to local memory...
这次的场景完全不同了。
我发现自己坐在一台PDP-10终端机前，周围是MIT人工智能实验室标志性的白色墙壁。空气中弥漫着一股特殊的气味——电路板、咖啡和披萨的混合物。
显示器上正在运行着一个LISP解释器：
(defun eval (expr env)
(cond
((atom expr)
(cond ((numberp expr) expr)
((symbolp expr) (lookup expr env))
(t nil)))
((eq (car expr) 'quote) (cadr expr))
((eq (car expr) 'lambda) expr)
((eq (car expr) 'cond) (evcond (cdr expr) env))
(t (apply (eval (car expr) env)
(evlist (cdr expr) env)))))
"又一个栈溢出。"一个声音从背后传来，"这已经是今天第七次了。"
我转过身，看到了一个留着长发的年轻人。Guy Steele！这位传奇人物后来成为了Scheme语言的创始人之一。
"让我看看。"我说着，调出了更多代码：
(defun apply (fn args)
(cond
((atom fn)
(cond ((eq fn 'car) (car (car args)))
((eq fn 'cdr) (cdr (car args)))
((eq fn 'cons) (cons (car args)
(car (cdr args))))
((eq fn 'eq) (eq (car args)
(car (cdr args))))
((eq fn 'atom) (atom (car args)))
(t (apply (lookup fn env) args))))
((eq (car fn) 'lambda)
(eval (caddr fn)
(bind (cadr fn) args env)))))
问题出在递归调用上。在那个年代，尾递归优化还没有被广泛应用，这导致了严重的栈溢出问题。
"看这个测试用例。"Guy指着屏幕说：
(defun factorial (n)
(cond ((zerop n) 1)
(t (* n (factorial (- n 1))))))
(factorial 5000)
;; Stack overflow error
我明白了。这是LISP早期最严重的问题之一：递归函数无法处理大量的嵌套调用。这个问题如果不解决，将严重限制LISP在人工智能领域的应用。
"我们需要一个新的求值策略。"我说，"让我试试这个。"
我开始修改解释器的核心代码：
(defun eval (expr env)
(let ((stack nil)
(result nil))
(loop
(cond
((null expr)
(if (null stack)
(return result)
(destructuring-bind (prev-expr prev-env)
(pop stack)
(setq expr prev-expr
env prev-env))))
((atom expr)
(setq result
(cond ((numberp expr) expr)
((symbolp expr) (lookup expr env))
(t nil)))
(setq expr nil))
((eq (car expr) 'quote)
(setq result (cadr expr))
(setq expr nil))
((eq (car expr) 'lambda)
(setq result expr)
(setq expr nil))
(t (push (list (cdr expr) env) stack)
(setq expr (car expr)))))))
"这是一个迭代式的求值器，"我解释道，"它使用显式的栈来模拟递归，这样就不会受到系统栈大小的限制。"
Guy的眼睛亮了起来："让我们测试一下。"
(factorial 5000)
;; => 很大的数字...
它工作了！不仅如此，新的求值器还能处理更复杂的情况：
(defun deep-recursion (n)
(cond ((zerop n) 'done)
(t (deep-recursion (- n 1)))))
(deep-recursion 1000000)
;; => 'done
"这太棒了！"Guy兴奋地说，"这意味着我们可以处理任意深度的递归了。"
我点点头。这个改进不仅解决了当前的问题，还为后来的函数式编程语言提供了重要的技术基础。
正当我准备解释更多细节时，一个新的想法突然闪现：
(defun optimize-tail-call (expr)
(if (and (consp expr)
(eq (car expr) 'return))
`(go ,expr)
expr))
"等等，"我说，"我们还可以加入尾调用优化..."
但熟悉的眩晕感又来了。时间线正在转换。
>>> Mission Completed
>>> Timeline Stable
>>> Bug Fixed: Stack Overflow in LISP Interpreter
>>> Historical Impact: Significant
>>> Note: Tail Call Optimization Concept Introduced
>>> Preparing for next jump...
在视野完全模糊之前，我看到Guy正在快速记录些什么。也许这就是Scheme语言采用尾递归优化的起源。
每次穿越都在提醒我：编程语言的进化史，就是一个不断解决问题的过程。而有些看似简单的改进，却能影响整个计算机科学的发展方向。
# End of Chapter 003
# Next Timeline Loading...
梦远书城已将原网页转码以便移动设备浏览
本站仅提供资源搜索服务，不存放任何实质内容。如有侵权内容请联系搜狗，源资源删除后本站的链接将自动失效。
推荐阅读