4

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

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

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

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

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

在更远的范围内，还有时间在一个无限的字母表上实现所有可能单词的集合。我正在考虑通过允许的最大单词大小来限制集合。再说一次，这是一个好习惯还是我应该转而选择流？我觉得流会是一种更好的方法，但我还没有学会它们，所以我真的不知道使用它们的含义。

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

4

1 回答 1

7

简单的区别是符号的比较非常便宜。可以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)返回的代码是所谓的“承诺”，它延迟了该承诺中答案的计算，但承诺在评估时结果将与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 是对列表其余部分的承诺，它在检索时被强制执行，否则它将变成非终止计算，例如，通常我们定义：

(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 编译器或解释器现在将为任意 x 和 y翻译每次出现的(stream-cons x y)to 。(cons x (delay 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) 会生成一个完全用一个填充的流。fibs 流本身是递归定义的。前两个元素是给定的，其余的是从恰好是 fibs 的两个流和 fibs 本身的 stream-cdr 计算的。

于 2010-06-27T17:57:21.710 回答