表达式的模式匹配

Question

我希望你能帮我一点忙。对于家庭作业，我应该编写一个函数，它使用模式匹配来检查表达式是否与特定的结构定义相对应。

以下是定义：

(define-struct literal (value))
(define-struct addition (lhs rhs))
(define-struct subtraction (lhs rhs))
(define-struct multiplication (lhs rhs))
(define-struct division (lhs rhs))

我的代码开始如下：

; An Expression is one of:
; - (make-literal Number)
; - (make-addition Expression Expression)
; - (make-subtraction Expression Expression)
; - (make-multiplication Expression Expression)
; - (make-division Expression Expression)
; interp. abstract syntax tree of arithmetic expressions

(define EXPRESSION-1 (make-literal 42))

(define EXPRESSION-2
  (make-addition (make-literal 4) (make-multiplication (make-literal 5) (make-literal 8))))

(define EXPRESSION-3
  (make-division (make-subtraction (make-literal 11) (make-literal 7)) (make-literal 2)))


; Any -> Boolean
; checks whether e is an Expression
(check-expect (expression? EXPRESSION-1) #true)
(check-expect (expression? EXPRESSION-2) #true)
(check-expect (expression? (make-literal "42")) #false)
(define (expression? e)
  (match e
    [(and (literal?) (number? literal-value)) #true]
    [(and (addition?) (number? addition-lhs) (addition-rhs)) #true]
    [substraction? #true]
    [multiplication? #true]
    [division? #true]
    [... #false]   
))

我这样做的原因是因为我必须检查表达式是否属于结构，而且我还必须确保该结构的元素只有数字，因为第二次测试将失败。但不知何故，我的方法不起作用，因为表达式-1和表达式-2的测试已经失败，我无法保持头脑清醒，为什么……

我把下面的四行留在了开头，因为我想把重点放在加法这一行上，因为我希望这只是“加法？”这一行的简单重复。你将如何继续做好这件事？此外，您是否建议将此数字检查作为结构的元素外包到单独的函数中？

干杯!

编辑:现在就像我想的那样，我正在努力完成下一个任务，我相信它的工作方式必须与Atharva Shukla下面建议的几乎相同。任务是将表达式转换为s表达式，例如，也使用模式匹配从(make- an (make-literal 1) (make-literal 2)) to '(+ 1 2)。

; Expression -> S-Expression
; converts an expression into the corresponding S-Expression
(check-expect (expr->sexpr EXPRESSION-1) '42)
(check-expect (expr->sexpr EXPRESSION-2) '(+ 4 (* 5 8)))
(check-expect (expr->sexpr EXPRESSION 3) '(/ (- 11 7) 2))
(check-expect (expr->sexpr (make-addition (make-literal 1) (make-literal 2)) 
'(+ 1 2))
(define (expr->sexpr e)
(match e
[(literal value) 'value]
[(addition lhs rhs) '(+ (addition lhs) (addition rhs))]
[(subtraction lhs rhs) '(- (subtraction lhs) (subtraction rhs))]
[...]
[...]
))

Answer 1

模式中指定的字段名称将在其各自的子句中进行绑定。所以不需要谓词。

(define (expression? e)
  (match e
    [(literal v) (number? v)]
    [(addition l r) (and (expression? l) (expression? r))]
    [(subtraction l r) (and (expression? l) (expression? r))]
    [(multiplication l r) (and (expression? l) (expression? r))]
    [(division l r) (and (expression? l) (expression? r))]
    [_ #false]))

最后一个子句是一个通配符，即计算RHS的任意值。

条例草案第2至5条的相同RHS可抽象为：

(define (expression? e)
  (match e
    [(literal v) (number? v)]
    [(or (addition l r) (subtraction l r)
         (multiplication l r) (division l r))
     (and (expression? l) (expression? r))]
    [_ #false]))

然而，我更喜欢第一个版本，因为它反映了表达式的定义。

编辑12/1/20:

它将类似于前面的示例，但我们会边走边构建列表。

(check-expect (compile-expression EXPRESSION-1) 42)
(check-expect (compile-expression EXPRESSION-2) `(+ 4 (* 5 8)))
(check-expect (compile-expression EXPRESSION-3) `(/ (- 11 7) 2))

(define (compile-expression e)
  (match e
    [(literal v) v]
    [(addition l r) (list '+ (compile-expression l) (compile-expression r))]
    [(subtraction l r) (list '- (compile-expression l) (compile-expression r))]
    [(multiplication l r) (list '* (compile-expression l) (compile-expression r))]
    [(division l r) (list '/ (compile-expression l) (compile-expression r))]
    [_ (error "Not an Expression")]))

我更喜欢这个版本，因为它允许您轻松创建更复杂的结构：

(define (compile-expression e)
  (match e
    [(literal v) v]
    [(addition l r) `(+ ,(compile-expression l) ,(compile-expression r))]
    [(subtraction l r) `(- ,(compile-expression l) ,(compile-expression r))]
    [(multiplication l r) `(* ,(compile-expression l) ,(compile-expression r))]
    [(division l r) `(/ ,(compile-expression l) ,(compile-expression r))]
    [_ (error "Not an Expression")]))

您可以了解有关报价、准报价和取消报价here的更多信息。