scala - 如何在Scala中打印递归值？

问题描述

我正在用 Scala 编写 Lisp。

sealed trait Val

final case class Atom(name: String) extends Val

final case object Null extends Val

final class Cons(a: Val, d: => Val) extends Val {
  override def toString(): String = "Cons(" + a.toString() + "," + d.toString() + ")"
}

如何正确打印递归Vals？例子：

lazy val lst:Val = new Cons(Atom("a"), {lst})
lst.toString()

我希望它的结果是#1=Cons(Atom("a"), #1).

标签： scalafunctional-programminglisp

我有实现循环符号的经验，但是在 C 中。

首先，方法不止一种。

您必须退后一步考虑：对象是否总是要使用 ? 打印成文本toString？也就是说，您不打算拥有 I/O 流，以及一种将对象打印到流而不是将它们转换为字符串的方法吗？

如果您计划拥有 I/O 流，那么您可以使它们足够通用，以便可以实现字符串输出流，这可以作为将对象转换为字符串的基础。

在实现循环符号时，可以以各种方式做事。关键问题是你不想在所有东西上都贴上数字标签，不管它是否需要，因为那样看起来很难看。例如：

#1=(#2=(a b) #3=(c d) e) ;; no circularity or substructure sharing!

但是在您的打印机发现最方便开始发射一个对象的时候，它必须知道：发射一个标签，还是不发射一个标签？

要考虑的另一点是循环符号很昂贵。这就是 ANSI Lisp 指定*print-circle*启用它的特殊变量的原因，默认情况下它是关闭的。实现这样的开关可能是个好主意。

循环表示法的一个主要问题是，如果您的 Lisp 方言有一个对象系统，程序员可以通过该对象系统创建具有自定义打印方法的新类类型，那么即使遍历这些自定义打印方法，循环表示法也必须工作。这很重要，因为在没有自定义方法的情况下，您的打印机可以在递归时轻松地将任意上下文对象传递给它自己。该对象可以指示循环符号已打开（无需继续检查动态变量，它可以保存标签等的哈希表）。如果打印机调用自定义打印方法，该方法可以回调打印机，则无法传递良好的内部上下文：它不是 API 的一部分。

无论如何，一个有效的简单算法是首先遍历要打印的对象并构建其所有“符合圆圈条件”的组成对象的哈希表。例如，fixnum 整数或内部符号不是；不要将它们添加到哈希中。在散列（我假设这里是 Lisp 样式的散列）中，您可以nil在对象首次引入时将其关联。如果看到对象的副本，则nil翻转到t。当然，任何时候你发现访问的对象已经在散列中，你不会递归它。那将打败整个练习。构建哈希后，您可以在打印时引用它。当要打印一个“符合圆圈条件的”对象时，您首先在散列中查找它。如果哈希有一个t，那么你替换它t使用标签计数器的值，发出标签计数器值#<counter>=所在的文本<counter>，然后打印对象。计数器递增。如果哈希将对象与整数相关联，则意味着您之前#<counter>=已经为该对象打印了符号。这只是对该对象的引用：所以只需 print#<that integer>#来表示该对象，就完成了。

这是基本的想法。如果您决定使用 consing 点实现平面列表表示法，您将需要以下逻辑。例如，考虑循环列表#1=(a b c . #1#)。如果打印机没有注意到循环，它只会(a b c a b c a b c ...永远打印，或者直到达到配置的列表长度限制。它只是循环直到cdr迭代器碰到一个原子。在循环模式下，打印机在渲染平面列表时，必须观察cdr迭代器是否在循环哈希中命中。如果是这样，那么它必须打印 consing 点和符号，关闭括号并终止循环。这种#=情况可以发生在这个位置：(a b c . #1=(d e . #1#))。一个积极的哈希命中基本上被视为一个终止原子。

scala - 如何在Scala中打印递归值？

问题描述

解决方案

推荐阅读