CODEWITHSUNDEEP
data-structurespattern-matchingracket
Illmatic
Illmatic

Reputation: 1

Pattern Matching of expressions

I hope you can help me a little. For a homework I am supposed to code a function, that checks if an expression corresponds to a certain structure definition using pattern matching.

These are the definitions:

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

My code starts as follows:

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

The reason I am doing it this way is because I have to check if the expression is of the sctructure and I also have to make sure that the elements of that structure are nothing but numbers as the second test would fail then. But somehow my way doesn't work as the test for the EXPRESSION-1 and EXPRESSION-2 already fail and I cannot get my head straigth, why...

I left the four lower lines as they were in the beginning, because I want to focus on the line for addition as I expect it would be a simple repetition of the line for 'addition?'. How would you proceed to get that right? Also, would you recommend to outsource this check for the numbers as elements of the structure into a seperate funtion?

Cheers!

Edit: Now just as I thought I got it straight, I am struggling with the next task where I beleive it must work almost the same way as Atharva Shukla suggested below. The task is to translate the expression into an s-expression, so e.g from (make-addition (make-literal 1) (make-literal 2)) to '(+ 1 2) also using pattern matching.

; 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))]
[...]
[...]
))

Upvotes: 0

Views: 106

Answers (1)

Atharva Shukla
Atharva Shukla

Reputation: 2137

The field names specified in the pattern will be bound in their respective clauses. So no need for predicates. 

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

The last clause is a wildcard i.e. evaluated the RHS for any value.

The same RHS for clauses 2-5 could be abstracted as follows:

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

However I prefer the first version more because it mirrors the Expression definition.

Edit 12/1/20:

It would be similar to the previous example but we construct the list as we 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")]))

I prefer this version because it allows you to create more complex structures easily:

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

You can learn more about Quote, Quasiquote, and Unquote here.

Upvotes: 1

Related Questions