lisp 中的自定义“+”（求和）函数

Question

我正在阅读 Paul Graham 的 Lisp 之根，他声称任何 lisp 功能都可以通过这 7 个基本函数的组合来构建：quote、atom、eq、cond、cons、car、cdr。

问题：Lisp 方言真的完全基于这些函数吗？我们如何使用上述 7 个原始函数定义 'sum' 或 'plus' 函数？例如我们自己的 (+ 1 2) 函数

注意：我完全是 Lisp 的新手，但我也开始对这门语言感到非常兴奋。本题目的纯属真心兴趣

Answer 1

作者参考了 1960 年图灵奖获得者和 Lisp 发明者 John McCarthy 写的一篇非常著名的论文 “Recursive Functions of Symbolic Expressions and Their Computation by Machine”，他在文中将 Lisp 的语义定义为一种新的计算形式主义，等同于图灵机。

在论文中（以及 Lisp 1.5 Manual）McCarthy 描述了该语言的解释器，仅使用 Graham 提到的七个原始函数即可完全编写。

该语言主要用于符号计算，论文中介绍的解释器仅涉及这些计算，不求助于数字或不同于原子和对的其他数据类型。

正如 Graham 在 Root of Lisp 第 11 页的注释中所说，“可以在 McCarthy 1960 年的 Lisp 中使用例如n 个原子的列表，表示数字 n”，因此执行求和相当于附加两个列表。

当然，这种做法效率很低：它只是为了显示与其他计算形式的等价性，而在实际中 interpreters/compilers 整数像往常一样表示，并具有通常的运算符。

Answer 2

据我所知，还有一种方法可以使用列表嵌套级别来执行此操作（不太记得，在哪里）。从 () 开始为零，(()) == 1 等等。然后你可以简单地定义 inc 为 list 和 dec 为 car:

CL-USER> (defun zero? (x) (eq () x))
ZERO?

CL-USER> (zero? nil)
T

CL-USER> (zero? 1)
NIL

CL-USER> (defparameter *zero* ())
*ZERO*

CL-USER> (defun inc (x) (list x))
INC

CL-USER> (defun dec (x) (car x))
DEC

CL-USER> (defun plus (x y)
           (if (zero? y) x (plus (inc x) (dec y))))
PLUS

CL-USER> (plus *zero* (inc (inc *zero*)))
((NIL))

CL-USER> (defparameter *one* (inc *zero*))
*ONE*

CL-USER> (defparameter *two* (inc *one*))
*TWO*

CL-USER> (defparameter *three* (inc *two*))
*THREE*

CL-USER> (plus *two* *three*)
(((((NIL)))))

CL-USER> (equal *two* (dec (dec (dec (plus *two* *three*)))))
T

Answer 3

TL; DR: 不。现代 lisp 系统比第一个 lisp 有更多的原语，每个新的原语数据类型都需要一个新的原语。

第一个 Lisp 没有数字，但它是图灵完备的。这意味着它可以进行任何其他语言可能进行的任何计算，但这并不意味着这样做是可行的。数字并不难模仿，但计算速度很慢。今天有谣言说慢算术可以追溯到 Lisp 1.5 之前。

当我制作我的第一个 lisp 解释器时，我不太关心数字。这并不是口译员真正有趣的方面。然而，我确实以 fibonacci 为例，这就是它的样子：

;; This is NOT Common Lisp code. It's Zozotez
(setq + (lambda (x y)
  (if x (cons (car x) 
              (+ (cdr x) y))
      y)))

(setq - (lambda (z w)
  (if w (- (cdr z) 
           (cdr w)) 
      z)))

(setq fibonacci
  (lambda (n a1 a2)
    (if n
        (fibonacci (- n '(1))
                   a2 
                   (+ a2 a1)) 
        a1)))

(fibonacci '(1 1 1 1 1 1 1 1 1) () '(1))
; ==> (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1)

没有数字！（1 在我的语言中是一个符号，所以它需要被引用，否则它将像变量一样被评估）

作为替代数字系统，我已经实现了一个位置系统，非常类似于我们如何使用相同规则为 adding/multiplying 等编写数字。也许比长度为 n 的 lits 快一点，但制作起来更复杂。

如果 Lisp 有闭包，你可以使用教堂数字。使用与 lambda 演算相同的方法，您可以只用闭包计算任何东西。你只需要一个原语，lambda。（同样，不是最容易使用的）

lisp 中的自定义“+”（求和）函数

Custom '+' (sum) function in lisp

lisp

common-lisp