DrRacket:取消对and的所有使用，或不将其转换为嵌套的ifs

Question

因此，我目前正在学习如何编程，我们从DrRacket开始。本周的任务包括使用模式匹配和将表达式工作/转换为s-表达式，反之亦然。我能够以某种令人满意的方式完成大部分任务，但最后这个任务让我很困惑，我甚至不知道该如何开始。到目前为止，我的任务是编写“核心语言”，最后一个函数应该将"extended“(有和，或者，不是)转换为嵌套的ifs (”核心语言“只使用if)。

关于如何通过模式匹配实现这一点，您有什么建议吗？我已经给出了签名和测试，这样就可以清楚地知道这个函数应该做什么。

; S-Expression -> S-Expression
; Desugars all uses of and, or, not and cond into (potentially nested) ifs.
(check-expect (desugar '(and #true #false)) '(if #true (if #false #true #false) #false))

谢谢你的帮助！

Answer 1

诀窍在于想一想，如果你只有and和or，那么像if这样的东西需要变成什么样的东西。

not实在太简单了，所以我不会说。

and相当容易，分为三种情况(因此，模式匹配将对您有所帮助)。

如果

• (and)为真，则true;
• (and x)为真，因此，如果x为真，而(and y ...)为真，则相当于x为真。

所以唯一有趣的案子是最后一个。那你是怎么表达那个案子的？有点像(if x (and y ...) #f)，对吧？

如果您想获得传统的Lisp/Scheme语义，or会更有趣，也更难。

如果您想要的是一个简单的or，它返回一个布尔值，那么它很简单：

• (or) is false;
• (or x)与x;
• (or x y ...)相同，如果x为真，或者(or y ...)为真，这意味着它是(if x #t (or y ...)).

这很好，但这不是Scheme或Lisp传统上所做的事情。对于Scheme或Lisp，规则是(斜体的不同)：

如果

• (or)是false;
• (or x)，则x;
• (or x y ...)是x的值，否则就是(or y ...).

的值。

注意最后一条规则是不同的。将最后一个规则转化为(if x x (or y ...))是很有诱惑力的。为什么这是不正确的？正确的展开是什么(提示:它包括let或等效的lambda)？

因此，现在需要理解的最后一件重要的事情是，将复杂的语言转化为简单语言的东西必须递归地工作:如果您得到一个类似于(a ...)的表单，您需要决定：

如果

• 是你知道如何处理的一件特殊事情(比如if)，那么您将有一套规则来告诉您需要进一步检查表单的哪些部分(对于if，答案是“全部”)；
• is a是一种我们知道如何变成更简单(“扩展”为更简单的事物)的东西，在这种情况下，可以将其扩展为更简单的东西，然后再查看更简单的事物；如果
• 是您不知道的东西，在这种情况下，您只需计算它以生成一个函数，处理其他表单，然后将该函数应用于其他表单；
• 则没有其他选项。