如何创建一个Scheme定义来解析复合S表达式并将其转换为范式

Question

给定一个形式为：(* 3 (+ x y))的表达式，我如何计算该表达式，以便将其放入(+ (* 3 x) (* 3 y))形式？(注意:在一般情况下，3是任何常量，"x“或"y”可以是单变量的术语或其他s表达式(例如(+ 2 x))。

如何编写递归计算项(原子？)的lambda表达式？并确定它们是常量还是项？在术语的情况下，然后需要再次递归地评估它，以确定该术语列表中的每个项目的类型。

同样，对我来说，问题的症结是定义的递归“内核”。

我显然需要一个基本情况，一旦我到达表达式最深部分的最后一个单原子，它就会确定。然后递归地“备份”，根据规则以适当的形式构建表达式。

来自Java / C++背景的我在理解如何在方案中从语法上做到这一点上有很大的困难。

Answer 1

让我们从最初的问题快速绕道到一些稍微相关的问题。假设您得到了以下内容:您想要编写一个求值器，它接受诸如(* 3 "hello")之类的“字符串构建”表达式，并将其“求值”为"hellohellohello“。我们想要做的其他例子包括

(+ "rock" (+ (* 5 "p") "aper"))     ==> "rockpppppaper"
(* 3 (+ "scis" "sors"))             ==> "scissorsscissorsscissors"

要解决这样的问题，我们需要准确地指定输入的形状。本质上，我们希望描述一种数据类型。我们会说我们的输入将是“string-expression”。让我们简称它们为str-exprs。那么让我们来定义一下作为一个str-expr意味着什么。

str-expr可以是：

1. <string>
2. (+ <str-expr> <str-expr>)
3. (* <number> <str-expr>)

通过这种表示法，我们试图说明str-exprs都适合这三种形状中的一种。

一旦我们对数据的形状有了一个很好的了解，我们就有了一个更好的指南来编写处理str-exprs的函数:它们必须对这三种备选方案进行案例分析！

;; A str-expr is either:
;;      a plain string, or
;;     (+ str-expr str-expr), or
;;     (* number str-expr)

;; We want to write a definition to "evaluate" such string-expressions.

;; evaluate: str-expr -> string
(define (evaluate expr)
  (cond
    [(string? expr)
     ...]
    [(eq? (first expr) '+)
     ...]
    [(eq? (first expr) '*)
     ...]))

其中的“...”是我们要填写的内容。

实际上，我们知道如何更多地填充“...”：我们知道在第二和第三种情况下，内部部分本身就是str-exprs。这些都是可能发生重复的主要点:由于我们的数据是用自身来描述的，所以处理它们的程序可能也需要引用它们自己。简而言之，处理str-expr的程序几乎肯定会遵循这样的形式：

(define (evaluate expr)
  (cond
    [(string? expr)
     ... expr 
     ...]
    [(eq? (first expr) '+)
     ... (evaluate (second expr))
     ... (evaluate (third expr))
     ...]
    [(eq? (first expr) '*)
     ... (second expr) 
     ... (evaluate (third expr))
     ...]))

这一切都不需要做任何真正的工作:我们可以弄清楚这一部分，纯粹是因为这是数据的形状告诉我们的。填入“...”的其余部分以使所有内容都正常工作实际上并不是太糟糕，特别是当我们还考虑到我们已经编写的测试用例时。(Code)

正是这种标准的数据分析/案例分析是你问题的核心，这也是HTDP等课程广泛涵盖的内容。这不是Scheme或球拍特定的:您可以在Java中执行相同类型的数据分析，并且在许多其他地方也可以看到相同类型的方法。在Java中，用于案例分析的低层机制可能会有所不同，可能是使用动态分派，但核心思想都是相同的。您需要描述数据。一旦有了数据定义，就可以使用它来帮助您勾勒出处理该数据所需的代码外观。使用测试用例来三角化如何填充草图。

Answer 2

你需要分解你的问题。首先，我将遵循HtDP (www.htdp.org)方法。你的输入是什么？你能准确地指定它们吗？在这种情况下，这些输入将是自引用的。

然后，指定输出表单。事实上，您上面的文本在这一点上有点模糊:我想我知道您的输出表单是什么样子的，但我不完全确定。

接下来，编写一组测试。这些应该基于你的输入词的结构；从最简单的开始，从那里往上往上。

一旦你有了一组很好的测试，实现这个函数就应该非常简单。如果你被卡住了，我很乐意帮你！