let
expression. if
work? (l-exp op r-exp)
. These kinds of nested lists can be used to represent an expression tree. Grammar for expressions of Assignment 1 |
|
Tokens: In the rules below tokens are either named (UPPER case) or in " " |
|
OPERATOR = any one of + - * / |
|
NUMBER = a token that satifies the number? predicate, that is |
any proper racket number |
|
IDENTIFIER = any token that begins with A-Z or a-z |
|
DELIMITERS = the ( and ) parentheses |
|
Rules: |
|
<expression> ::= NUMBER | |
IDENTIFIER | |
"(" <expression> ")" | |
"(" <expression> OPERATOR <expression> ")" |
'(1 +2)
is the 2 element list (1 2)
, and (1+3)
is the 1 element list (1+3)
. #lang racket |
|
; apply op to left and right arguments, assume they are numbers |
; this can be tested with the number? predicate |
(define (op-eval op larg rarg) |
(cond |
[ (equal? op '+) (+ larg rarg) ] |
[ (equal? op '*) (* larg rarg) ] |
)) |
|
; evaluate an infix expression tree, assuming that all the leaves |
; are numbers. |
(define (exp-eval ex) |
(cond |
; atoms are themselves |
[ (not (list? ex)) ex ] |
|
; single element lists are the value of their first element |
[ (null? (rest ex)) (exp-eval (first ex)) ] |
|
; triples require evaluation of left and right, followed by operation |
[ else (op-eval (second ex) (exp-eval (first ex)) (exp-eval (third ex))) ] |
)) |
|
(exp-eval 1) |
(exp-eval '1) |
(exp-eval '(1)) |
(exp-eval '(1 + 2)) |
(exp-eval '(3 * 4)) |
(exp-eval '( (1 + 2) * (3 + 4) )) |
;will not work: (exp-eval '(1 + x)) |
exp-eval
to take a additional argument that is a symbol table that maps symbols to their numeric values. The symbol table is a list of pairs of the form (symbol value)
. For example: Also enable your new(exp-eval '((x + 1) + (x * y)) '( (x 2) (y 3) ))
is9
exp-eval
to handle the operations of subtraction, -
, and division /
. list?
predicate, or is a number using the number?
predicate. So you can deduce if something is a symbol. The findf
function is handy for symbol table lookups. (exp-eval '(42 + (1 + x)) '() ) is '(42 + (1 + x))
(exp-eval '((2 + 40) + (1 + x)) '() ) is '(42 + (1 + x))
(exp-eval '((2 + (3 * 40)) * (x * ( (1 + 3) * y))) '() ) is '(122 * (x * (4 * y)))
(exp-eval '((2 + (3 * 40)) * (x * ( (1 + 3) * y))) '( (x 1) ) ) is
'(122 * (1 * (4 * y)))
(equal-commute? E1 E2)
that tests whether the two expressions are equivalent under rearrangement due to commutativity of addition and multiplication. (1 + x)
and (x + 1)
are commutatively equal, as are ((1 + x) * (y + 2))
and ((y + 2) * (x + 1))
. But ((1 + x) * (y + 2))
and ( (y + (y * x)) + (2 + (2 * x)) )
are not. +
and *
. But of course division and subtraction do not commute, so pivoting is not a good idea. equal-commute?
predicate. It will certainly be a function of the depth and density of the expression tree. Provide some best and worst case examples. #lang racket |
|
; Define some useful predicates on expressions we will use for both parts |
(define (is-exp-leaf? E) |
(not (list? E)) ) |
|
(define (is-exp-nested? E) |
(and (list? E) (null? (rest E)) ) ) |
|
(define (is-exp-binary? E) |
(and (list? E) (= 3 (length E)))) |
|
(define (is-cummutative? op) |
(or (equal? '+ op) (equal? '* op)) ) |
|
; Part 1 |
; evaluate op on larg, rarg. If larg and rarg are not numbers |
; the return the infix expression (larg op rarg), otherwise return the |
; value of ((eval op) larg rarg) |
; |
; op - quoted binary operation (like '+ '/), not a procedure (like + /) |
; larg, rarg - left and right arguments, numbers or expressions |
; |
; Note: if you want to have your own version of an operation, like say |
; / which on 1/0 yields 'NaN (Not a Number), then you can add a dispatch |
; cond to the else below. You could also explicitly enumerate the possible |
; operations and then generate an error when they are missing. |
|
(define (op-eval op larg rarg) |
(cond |
|
[ (or (not (number? larg)) (not (number? rarg))) |
(list larg op rarg) ] |
|
[ else ((eval op) larg rarg) ] |
)) |
|
; if s is in symbol table symtab, return the value of s, otherwise return |
; the default-value. |
; The symbol table is a list of (name value) pairs |
; that associates the symbol name with value. |
|
; If there are multiple |
; occurrences of name, then the value associated with the first one is used. |
|
(define (lookup-sym s default-value sym-tab) |
(let ( |
[ r (findf (lambda (p) (equal? s (first p))) sym-tab) ] |
) |
(if (not r) default-value (second r)) |
)) |
|
|
; evaluate expression E in the context of the symbol table sym-tab |
(define (exp-eval E sym-tab) |
|
(cond |
; the leaves are numbers or symbols. If a symbol, get it value from sym-tab, |
; otherwise just return the symbol. |
[ (is-exp-leaf? E) (if (number? E) E (lookup-sym E E sym-tab)) ] |
|
; single element lists are the value of their first element, so drill down |
[ (is-exp-nested? E) (exp-eval (first E) sym-tab) ] |
|
; binary operations are applied to the evaluations of their arguments |
[ (is-exp-binary? E) (op-eval (second E) |
(exp-eval (first E) sym-tab) |
(exp-eval (third E) sym-tab)) ] |
|
[ else (error (format "Bad expression ~a" E)) ] |
)) |
|
; tests |
(define sym-1 '( (x 3) (y 4) (z 42))) |
(define t 42) ; add t to the environment |
|
(define (run-tests) |
(map displayln |
(list |
(exp-eval 1 sym-1) |
(exp-eval '1 sym-1) |
(exp-eval '(1) sym-1) |
(exp-eval '(1 + 2) sym-1) |
(exp-eval '(3 * 4) sym-1) |
(exp-eval '( (1 + 2) * (3 + 4) ) sym-1) |
|
(exp-eval 'x sym-1) |
(exp-eval '(1 + x) sym-1) |
|
|
(exp-eval '(t + (1 + x)) sym-1) |
(exp-eval '( (1 + x ) / (1 + x) ) '() ) |
(exp-eval '( (1 * ( 2 * (3 + x) ) ) ) '() ) |
)) |
#t ; returns true if all the tests ran. |
) |
|
|
; Part 2 |
|
|
|
(define (equal-commute? E1 E2) |
(cond |
[ (and (is-exp-leaf? E1) (is-exp-leaf? E2)) (equal? E1 E2) ] |
|
[ (and (is-exp-nested? E1) (is-exp-nested? E2) ) |
(equal-commute? (first E1) (first E2) ) ] |
|
[ (and (is-exp-binary? E1) (is-exp-binary? E2) |
(equal? (second E1) (second E2) ) ) |
(let ( |
; left and right hand args of E1 and E2 |
[ op (second E1) ] ; op is same for both expressions |
[ lh-E1 (first E1) ] |
[ rh-E1 (third E1) ] |
[ lh-E2 (first E2) ] |
[ rh-E2 (third E2) ] |
) |
(if (is-cummutative? op) |
; commutative so try both orders |
(or |
(and (equal-commute? lh-E1 lh-E2) (equal-commute? rh-E1 rh-E2)) |
(and (equal-commute? lh-E1 rh-E2) (equal-commute? rh-E1 lh-E2)) ) |
; not commutative so must match |
(and (equal-commute? lh-E1 lh-E2) (equal-commute? rh-E1 rh-E2)) |
) |
) ] |
[ else #f ] |
)) |
|
(equal-commute? '5 '4) |
(equal-commute? '5 '5) |
(equal-commute? 'x '5) |
(equal-commute? 'x 'x) |
(equal-commute? '(5) '5) |
(equal-commute? '(5) '(5)) |
(equal-commute? '(1 + x) '(x + 1)) |
(equal-commute? '(1 + x) '(1 + x)) |
(equal-commute? '(1 * x) '(x * 1)) |
(equal-commute? '(1 * x) '(1 * x)) |
(equal-commute? '(1 + x) '(x * 1)) |
(equal-commute? '(1 + x) '(1 * x)) |
|
(equal-commute? '(1 - x) '(x - 1)) |
(equal-commute? '(1 - x) '(1 - x)) |
(equal-commute? '(1 / x) '(x / 1)) |
(equal-commute? '(1 / x) '(1 / x)) |
|
(equal-commute? '((1 + x) * (y + 2)) '((y + 2) * (x + 1))) |
|
(exp-translate E)
that takes an infix expression E
as above and produces the scheme/racket expression that can be directly evaluated. (exp-translate '(1 + 2)) is '(+ 1 2)
(exp-translate '(3 * 4)) is '(* 3 4)
(exp-translate '((1 + 2) * (3 + 4))) is '(* (+ 1 2) (+ 3 4))
(exp-translate 'x) is 'x
(exp-translate '(1 + x)) is '(+ 1 x)
(exp-vars E)
which takes an infix expression E
and returns a list of all the variables in E
. Each variable should appear only once in the result. For example (exp-vars '(x + ( (z / y) * ( x + y) ))) is '(y z x)
#lang racket |
|
; transform an infix expression tree E into an quoted s-expression that |
; when eval'd evaulates to the value of the expression tree E. For example |
; (exp-translate '( (1 + x) * (3 + (4 / 5)) )) is |
; '(* (+ 1 x) (+ 3 (/ 4 5))) |
|
|
(define (exp-translate ex) |
(cond |
; atoms are themselves |
[ (not (list? ex)) ex ] |
; single element lists are the value of their first element, so |
; drill down |
[ (null? (rest ex)) (exp-translate (first ex)) ] |
|
; binary expressions just need to be rewritten in prefix form |
[ else (list (second ex) |
(exp-translate (first ex)) |
(exp-translate (third ex))) ] |
)) |
|
|
(define (etest E) |
(let [ (T (exp-translate E) ) ] |
(fprintf (current-output-port) |
;"~a => ~s evals to " |
"(exp-translate ~v) is ~v\n" |
E T) |
|
;(displayln (eval T)) |
)) |
|
(define (testseq) |
|
;(etest '1) |
;(etest '(1)) |
(etest '(1 + 2)) |
(etest '(3 * 4)) |
(etest '( (1 + 2) * (3 + 4) )) |
; these next one should fail unless x is defined |
(define x 42) |
(etest 'x) |
(etest '(1 + x)) |
) |
|
(testseq |
#lang racket |
|
; returns true if v is a variable (not a number) not in vars |
(define (is-new-var? v vars) |
(and (not (number? v)) (not (member v vars)))) |
|
; extracts out a list of all the variables in E. Each variable appears |
; exactly once in the result list |
(define (exp-vars E) |
|
; given an current expression Ec, and a list vars of variables seen |
; so far, add and new variables of Ec |
(define (exp-vars-r Ec vars) |
|
(cond |
; atoms are themselves, so if not seen already, add a non-number |
; to the list of variables |
[ (not (list? Ec)) |
(if (is-new-var? Ec vars) (cons Ec vars) vars) ] |
|
; single element lists are the value of their first element, so |
; get variables in the expression given by the first element. |
[ (null? (rest Ec)) (exp-vars-r (first Ec) vars) ] |
|
; binary expressions, update the variables with the ones on the |
; left, and then update those with the ones on the right. Note |
; the threading of vars through the recursion. |
[ else (exp-vars-r (third Ec) (exp-vars-r (first Ec) vars) ) ] |
|
)) |
|
(exp-vars-r E '()) |
|
4. Week 2 - Jan 13 CMPUT 325 Schedule / Version 2.31 2014-04-04 |