lisp - 澄清玻璃市格言， "LISP programmers know the value of everything and the cost of nothing."

Question

我一直在思考玻璃市的格言，

LISP programmers know the value of everything and the cost of nothing.

我可以找到一些提示和简短的解释，但不是对这句话的真正含义的清晰、有见地的解释，尤其是对于 Lisp 程序员而言。

请您解释一下 Perlis 的格言，可能先用简单的单词，CS 初学者可以理解的东西，然后再通过描述格言所隐含的相关结构、操作或情况，可能带有代码或伪代码示例来解释更多技术方面？

Answer 1

与许多 his epigrams 一样这至少部分是为了让您思考，而不是真正意味着任何真正具体的东西。

然而，理解他在这里的意思是相当简单的。引述分为两部分。

A LISP programmer knows the value of everything ...

这是指 Lisp 与许多编程语言不同，它是一种表达式语言。这意味着在 Lisp 中只有一种东西:表达式，它有一个值(或者在最近的 Lisp 中，有一些值)。因此，例如，在 CL 中，我可以说:

(let ((y (setq z 3))) ...)

因为 (setq ...) 是一个表达式，其值是它分配的最后一个值。同样我可以说

(setq y (let (...) ...))

因为 (let (...) ...) 是一个表达式，其值(或多个值)是其主体中最后一个形式的值(或多个值)，或者 nil 如果没有表单。

所以 Lisp 程序员知道一切的值(value)，因为在 Lisp 中，一切都是具有值(value)的表达式。

将此与 C 语言进行对比。在 C 语言中，有些表达式有值，有些语句没有。所以我不能在 C 中说:

int x = if (...) ... else ...;

因为 if (...) ... else ... 是 C 中的一个语句，而不是一个表达式。相反，我必须使用特殊的条件表达式:

int x = ...? ... : ...;

等等。

(但是，我可以说 int x = y = 4;:赋值是 C 中的一个表达式。)

许多语言也是如此(例如Python有同样的东西)。

我承认我不理解为什么这些语言会做出这种区分:我想除了使语言的语法和语义更加繁琐之外，肯定还有其他原因。

... but the cost of nothing.

引用的这一部分指的是 Lisp 中的各种操作具有时间(可能还有空间)复杂性——即成本——这不是常数。这本质上是因为 Lisp 中最独特和重要的复合数据结构(从来不是唯一的)是由 conses 组成的单链表，并且获取这样一个列表的第 n 个元素需要时间与 *n$ 成正比。

新手 Lisp 程序员，或者只是 Lisp 程序员，他们没有认真思考，因此最终编写的代码非常慢，而且扩展性非常差。例如考虑这个:

(defun terrible-sum-list (list)
  (let ((sum 0))
    (dotimes (i (length list) sum)
      (incf sum (nth i list)))))

这是列表长度的二次方，因为它重复遍历列表以获取第 n 个元素。但如果列表是一个数组，这将是一个非常合理的方法。相反，在 Lisp 中你想写这样的东西(我故意这样写，就好像很多 CL 不存在一样:这不是惯用的 CL 代码!):

(defun sum-list (list)
  (let ((sum 0))
    (mapc (lambda (e)
            (incf sum e))
          list)
    sum))

或者如果你想要真正原始(但使用 CL 的名字来表示原始性):

(defun caveman-sum-list (list)
  (let ((sum 0)
        (tail list))
    (tagbody
     loop
     (if (null tail)
         (go end))
     (setq sum (+ sum (first list))
           tail (rest tail))
     (go loop)
     end)
    sum))

Lisp 在编程语言中是，或者至少是不同寻常的，因为它提供的操作和数据结构的理解成本并非微不足道。将 Lisp 与 Fortran 等进行比较，尤其是与当时的 Fortran 进行比较。

当然，这句话实际上只适用于非常小或简单的程序，因为大型和复杂的程序也开始具有可能不明显的复杂性，导致这句话的另一个版本:

Fortran programmers know the values of a few things and the costs of a few very small things

(这并不是要对 Fortran 程序员无礼:我一直是 Fortran 程序员。)