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

Question

我提前为我的原始英语道歉；我会尽量避免语法错误等。

两周前，我决定更新我对 Scheme(及其启示)的知识，同时实现我在手上获得的一些数学 Material ，特别是我注册的自动机理论和计算类(class)中的正则语言。

到目前为止，我一直将字母表示为 符号列表 代替

字符列表，因为我想要可变大小的字母。

字符串列表，因为我有点觉得那不优雅。

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

在更远的范围内，还有时间在一个字母表上实现所有可能单词的集合，这是无限的。我想通过允许的最大字数来限制集合。同样，这是一个好习惯还是我应该去流？我觉得流将是更好的方法，但我还没有学习它们，所以我真的不知道使用它们的含义。

无论如何，欢迎任何建议或评论。我非常感谢您花时间阅读我的疑虑。周末愉快!

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 "match") .但是，当使用字符串作为键时 assq不再足够，它使用 eq?比较程序，而不是 assoc必须使用，它使用 equal?过程，因为它递归地比较结构，所以成本要高得多。上面的实现实际上足够便宜，经常被用作在解释器中对关联数组和环境进行建模的一种方式，即使它肯定不是随机访问。

编辑:正如你所问，在流上:

Scheme 标准支持一对不错的函数，一个是名为 force 的函数。 ，另一种是一种特殊形式，称为 delay .有效什么

(delay (+ 1 2 3))

或任何其他代码代替 (+ 1 2 3)返回是一个所谓的“ promise ”，它延迟了该 promise 中答案的计算，但 promise 在评估为 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
)

很明显，promise 确实只被评估了一次，当再次强制时，它产生与第一次评估时相同的值。

这是流或概念性“无限列表”中通常使用的内容。在这种情况下，列表的 cdr 是对列表其余部分的 promise ，它在检索时被强制执行，否则它将变成非终止计算，例如，通常我们定义:

(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 x y) 的每一次出现。至 (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 (x y) (+ 1 x y)) zeroes zeroes) 将生成一个完全充满一个的流。 fibs 流本身是递归定义的。前两个元素是给定的，其余元素是从两个恰好是 fibs 的流和 fibs 本身的 stream-cdr 计算出来的。