Образец соответствия выражений - PullRequest
Новая
       22

Образец соответствия выражений

0 голосов
/ 11 января 2020

Надеюсь, вы мне немного поможете. Для домашней работы я должен написать функцию, которая проверяет, соответствует ли выражение определенному определению структуры, используя сопоставление с образцом.

Это определения: 

(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]   
))

Причина, по которой я делаю это таким образом, заключается в том, что я должен проверить, относится ли выражение к структуре, и я также должен убедиться, что элементы этой структуры - не что иное, как числа, как второй тест провалился бы тогда. Но почему-то мой путь не работает, так как тест для EXPRESSION-1 и EXPRESSION-2 уже провалился, и я не могу понять, почему ...

Я оставил четыре нижние строки, как они были в начало, потому что я хочу сосредоточиться на строке для добавления, поскольку я ожидаю, что это будет простое повторение строки для «добавления?». Как бы вы поступили, чтобы получить это право? Кроме того, вы бы порекомендовали передать эту проверку для чисел как элементов структуры в отдельную функцию?

Приветствия!

Редактировать: Теперь, как я и думал, я понял это прямо, я Борьба со следующей задачей, в которой я верю, должна работать почти так же, как предложил Атхарва Шукла ниже. Задача состоит в том, чтобы перевести выражение в s-выражение, например, из (make-add (make-literal 1) (make-literal 2)) в '(+ 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))]
[...]
[...]
))

1 Ответ

1 голос
/ 12 января 2020

Имена полей, указанные в шаблоне, будут связаны в соответствующих пунктах. Так что нет необходимости в предикатах. 

(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 для любого значения.

Та же RHS для пунктов 2-5 может быть обобщена следующим образом: 

(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]))

Однако я предпочитаю первую версию больше, потому что она отражает определение Выражение .

Редактировать 01.12.20:

Это будет похоже на предыдущий пример, но мы создадим список, как мы go. 

(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")]))

Подробнее о Quote, Quasiquote и Unquote можно узнать здесь .

...