方案，何时使用符号而不是字符串？

Question

我提前为我的英语水平表示歉意；我会尽力避免语法错误等。

两周前，我决定更新我对Scheme（及其启示）的知识，同时实现我手上得到的一些数学材料，特别是我注册的自动机理论和计算课程中的常规语言。

到目前为止，我一直将字母表表示为符号列表而不是

1. 字符列表，因为我想要具有可变大小的字母。
2. 字符串列表，因为我有点觉得那不优雅。

我缺乏经验，想知道您对这个特定选择的看法。符号是为某种特定类型的任务保留的吗？我是否滥用了它们？对此的任何评论都非常感谢，因为我正在寻求指导。

更进一步，还有时间在字母表上实现所有可能单词的集合，这是无限的。我正在考虑通过允许的最大字数来限制集合。再说一次，这是一个很好的做法还是我应该去流媒体？我觉得流将是一种更好的方法，但我还没有学习它们，所以我真的不知道使用它们的含义。

无论如何，欢迎任何建议或评论。我真的很感谢您花时间阅读我的疑虑。祝你周末愉快！

Answer 1

简单的区别在于符号的比较成本非常低。可以使用 eq? 来比较两个符号是否相同。这是因为在编译时，编译器本质上会用数字枚举所有符号，因此您只是比较整数，这是一种非常便宜的机器操作。

这意味着两个符号是相同的当且仅当它们由相同的字符组成。无法辨别代码中具有相同字符的两个符号，它们是常量，它们是相同的对象，就像 3 和 3 一样。

然而，两个字符串很可能是驻留在内存不同位置的不同对象，并且要比较它们需要分别比较每个字符是否匹配。

因此符号应该并且经常用于此目的，例如，考虑：

(assq 'symb  '((foo 1 2 3) (bar symb) (symb "match")))

这返回列表 (symb "match") 这与比较一样便宜：

(assq 4  '((0 1 2 3) (1 symb) (4 "match")))

它返回列表 (4 "匹配”）。但是，当使用字符串作为键时，assq 不再足够，它使用 eq? 过程进行比较，而必须使用 assoc，它使用equal? 过程，由于它递归地比较结构，所以成本要高得多。上面的实现实际上足够便宜，可以经常用作在解释器中对关联数组和环境进行建模的方法，即使它肯定不是随机访问。

编辑：正如您所问，在流上：

Scheme 标准支持一对很好的函数，一个是名为 force 的函数，另一个是名为 的特殊形式延迟。实际上

(delay (+ 1 2 3))

，或任何其他代码代替 (+ 1 2 3) 返回的是所谓的“承诺”，它延迟了该承诺中答案的计算，但承诺结果将是当评估到我们到达的 6 时是相同的。这可能看起来毫无用处，但假设结果取决于某个可以更改的变量：

(define x 4) ; x is bound to 4.
(let ((promise (delay (+ 2 x)))) ; evaluating the expression now would result into 6, but we delay it.
  (set! x 5) ; we change the value of x.
  (display (force promise)) ; displays 7
  (set! x 6) ; change it again
  (force promise) ; ALSO displays 7, not 8
)

很明显，承诺确实只评估一次，并且当再次强制时，它会产生与第一次评估时相同的值。

这是流或概念性“无限列表”中通常使用的内容。在这种情况下，列表的 cdr 是对列表其余部分的承诺，在检索列表时强制执行，否则它将变成一个不间断的计算，例如，通常我们定义：

(define (stream-cdr x) (force (cdr x))) ; it forces that promise to evaluate it.
; and optionally
(define stream-car car) ; same

因为这个无法评估其参数，它需要是一种特殊的形式：

(define-syntax stream-cons
  (syntax-rules ()
    ((stream-cons x y)
     (cons x (delay y))))

您的Scheme编译器或解释器现在会将每次出现的(stream-cons xy)转换为(cons x (delay y))任意任意的 x 和 y。

因此，作为一个简单的例子，现在我们的评估被延迟到我们需要它为止，我们可以创建一个无限的零列表：

(define zero-stream (stream-cons 0 zero-streams))

一个由自身组成的列表，如果我们没有使用流，它肯定永远不会终止，无用的，但它展示了这个想法。我们可以一遍又一遍地使用 stream-cdr ，而不会到达空列表，我们只是再次得到相同的“无限 0 列表”。

一个更实际的例子是所有斐波那契数的列表，这有点复杂：

(define fibs 
  (stream-cons 0 (stream-cons 1
    (stream-map + fibs (stream-cdr fibs))))

Stream-map 是法线贴图的类似物，它的定义非常复杂，但我相信你可以查找它，它会生成流本身。因此 `(stream-map (lambda (xy) (+ 1 xy)) Zeroes Zeroes) 将生成一个完全充满 1 的流。 fibs 流本身是递归定义的。前两个元素是给定的，其余元素是根据两个流计算的，这两个流恰好是 fibs 和 fibs 本身的流 cdr。