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

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 "match").但是,当使用字符串作为键assq不再足够时,使用eq?比较过程,而不是assoc必须使用该equal?过程,这使用过程,由于它递归地比较结构,因此成本更高.上述实现实际上足够便宜,通常可以用作在解释器中建模关联数组和环境的方法,即使它肯定不是随机访问.

编辑:正如你所问,在溪流上:

该计划标准支持一双很漂亮的,一个是调用的函数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
)

很明显,承诺确实仅被评估一次,并且当再次强制时,它产生与第一次评估时相同的值.

这是流中通常使用的,或概念性的"无限列表".在这种情况下,列表的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))))

你的计划编译器或解释现在翻译的每一次出现(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(lambda(xy)(+ 1 xy))零(零)将生成一个完全填充一个的流.纤维流本身是递归定义的.给出前两个元素,其余的元素来自两个恰好是fibs的流和fibs本身的stream-cdr.