1

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

如何编写一个 lambda 表达式，递归地评估原始表达式中的项目（原子？）并确定它们是常量还是项？如果是术语，则需要再次递归评估以确定该术语列表中每个项目的类型。

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

我显然需要一个基本案例来确定一旦我到达表达式最深处的最后一个单个原子。然后递归地“备份”工作，根据规则以适当的形式构建表达式。

来自 Java / C++ 背景，我很难理解如何在 Scheme 中从语法上做到这一点。

4

2 回答 2

4

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

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

为了解决这样的问题，我们需要准确地指定输入的形状。本质上，我们想要描述一种数据类型。我们会说我们的输入将是“字符串表达式”。让我们str-exprs简称他们。然后让我们定义什么是str-expr.

Astr-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-exprs 的程序几乎肯定会遵循这种形式：

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

这一切甚至都没有做任何实际工作：我们可以完全弄清楚这部分，因为这就是数据的形状告诉我们的。填写 '...' 的其余部分以使这一切顺利进行实际上并不算太糟糕，尤其是当我们还考虑我们已经编写的测试用例时。（代码）

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

于 2013-01-31T00:43:07.480 回答
1

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

然后，指定输出形式。实际上，您上面的文字对此有些模糊：我想我知道您的输出形式是什么样的，但我并不完全确定。

接下来，编写一组测试。这些应该基于您输入术语的结构；从最简单的开始，然后从那里向上工作。

一旦你有一套好的测试，实现这个功能应该很简单。如果您遇到困难，我很乐意提供帮助！

于 2013-01-30T23:28:30.593 回答