CODEWITHSUNDEEP
evalracketarithmetic-expressions
newbie
newbie

Reputation: 123

racket: (evaluate t lst)

I implemented a function that takes an arithmetic expression and returns the value:

; an arithmetic expression (t) is one of the following:
; - a number
; - a list of the form '(a operator b) where a and b are arithmetic expressions
; arithmetic expression -> number

; computes the value of the arithmetic expression

(define (eval t)
  (cond
    [(number? t) t]
    [else ((cond
            [(equal? (second t) '+) +]
            [(equal? (second t) '-) -]
            [(equal? (second t) '*) *]
            [(equal? (second t) '/) /])
           (eval (first t)) (eval (third t)))]))

It works perfectly, but obviously it can't take constants. So what I'm trying to do is to extend the program such that it works for something like:

(eval '(1 + (3 * x)) (make-const 'x 3)                     -> 10
(eval '((3 - x) * y) ((make-const 'x 1) (make-const 'y 2)) -> 4
(eval '(1 + (y * x)) (make-const 'x 3)                     -> "error"

My idea was to define a struct:

(define struct const (symbol number))


(define (eval. t x)
  (cond
    [(number? t) t]
    [(symbol?  t) ???]
    [else ((cond
            [(equal? (second t) '+) +]
            [(equal? (second t) '-) -]
            [(equal? (second t) '*) *]
            [(equal? (second t) '/) /])
           (eval. (first t) lst) (eval. (third t) lst))]))

Can anyone tell me if I am headed in the right direction and maybe give me a hint? It would be much appreciated!

Upvotes: 0

Views: 88

Answers (1)

Sorawee Porncharoenwase
Sorawee Porncharoenwase

Reputation: 6502

First, note that your examples are slightly wrong:

(eval '(1 + (3 * x)) (make-const 'x 3)
; you need a closing parenthesis

(eval '((3 - x) * y) ((make-const 'x 1) (make-const 'y 2))
; same as above. also, ((make-const 'x 1) (make-const 'y 2)) doesn't make
; sense. Do you mean (list (make-const 'x 1) (make-const 'y 2))

Anyway, there are two ways to do this.

The first way is to make eval has two phases: the first phase is to substitute all variables first. If things go well, you would get an expression with no identifier back. The second step is to call your first version of eval (where I will refer to as eval-helper).

; eval :: expr, listof const -> number
(define (eval t vars)
  (eval-helper (subst-all t vars)))

Indeed, the difficult part is to get subst-all correct. To simplify things, you might want to write a function named subst which substitutes only one identifier at a time. This could be done by a recursion over the expression and replace a symbol with a number if the symbol matches. Then subst-all could use subst as a helper function.

(With this way, how would you know if there is an unbound identifier?)

The second way is to follow your code template:

(define struct const (symbol number))

(define (eval t env)
  (cond
    [(number? t) t]
    [(symbol?  t) ???]
    [else ((cond
            [(equal? (second t) '+) +]
            [(equal? (second t) '-) -]
            [(equal? (second t) '*) *]
            [(equal? (second t) '/) /])
           (eval (first t) env) (eval (third t) env))]))

Canonically, the second argument of this function (such as (list (make-const 'x 1) (make-const 'y 2))) is known as environment. When you see a symbol, you just lookup on the environment and return the value that associates with the symbol that you are looking up.

; lookup :: symbol, listof const -> number
(define (lookup sym env)
  (cond
   [(empty? env) ???]
   [else (if (equal? sym (const-symbol (first env)))
             ??? ; you want to return the value!
             ??? ; recursively call lookup on the rest of the environment
             )]))

(With this way, how would you know if there is an unbound identifier?)

See also:

Upvotes: 2

Related Questions