CMPUT 325 Schedule and Outcomes
4. Week 2 - Jan 13

## 4.1 Topics

• Techniques for functional programming.
• use lambda and application to compute once and reuse many, introduce the `let` expression.
• pass previously computed information down the recursion with an accumulator
• pass computed results up the recursion, possibly adjusting at the final stage
• define recursors inside the function so don't have to pass down base data
• tail recursion is efficient, the jit compiler does all kinds of other optimizations
• how to restructure to get tail recursion
• prefix computation
• evaluation strategies for functional expressions
• special forms are lazy, how does `if` work?

## 4.2 Flipped Work - Assignment 1

The task this week is to work on Assignment 1. Submission details will be on the eClass site.

Note: you can use the full scheme/racket language for this assignment instead of being limited to restricted scheme.

Arithmetic expressions can naturally be written as lists using infix form, where each expression is either an atom (a number or a variable name), or a three-element list of the form `(l-exp op r-exp)`. These kinds of nested lists can be used to represent an expression tree.

Here is a BNF grammar for that describes all the syntactically correct expression trees: code/Week02/expression-grammar.txt

 `    ``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:` `    `` ` `    ``     ::= NUMBER | ` `    ``                    IDENTIFIER |` `    ``                    "("  ")" |` `    ``                    "("  OPERATOR  ")"`

Note that the grammar allows expressions like ((((1)))) and ( (1) + 2 ), but not 1 + 2 (it needs surrounding parentheses).

Normally you would have to parse a sentence in the grammar to build the expression tree, but they are already in list form for scheme, so no parsing necessary. Except you need to put spaces between the parts of the expression. `'(1 +2)` is the 2 element list `(1 2)`, and `(1+3)` is the 1 element list `(1+3)`.

To evaulate an expression tree means to recursively traverse the expression tree in the order: evaluate the left, evaluate the right, combine with the operation. At a leaf the value is the value of the atom at the leaf.

Here is a simple program that evaluates an expression tree that only contains numbers at the leaves.

code/Week02/expression-eval.rkt

 `    ``#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))`

Part 1: Using a symbol table to define variable values Modify `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:
`(exp-eval '((x + 1) + (x * y)) '( (x 2) (y 3) ))` is `9`
Also enable your new `exp-eval` to handle the operations of subtraction, `-`, and division `/`.

You can test if something is a list using the `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.

You should not assume that all the symbols in the expression tree are defined. In the case that a symbol is not defined, just leave it alone, and evaluate as much of the expression as possible. For example ``` (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))) ```

Part 2: Equality Under Commutativity

Implement the predicate `(equal-commute? E1 E2)` that tests whether the two expressions are equivalent under rearrangement due to commutativity of addition and multiplication.

For example, `(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.

Think of commutativity as being able to pivot the expression tree at internal vertices at operations that commute, such as `+` and `*`. But of course division and subtraction do not commute, so pivoting is not a good idea.

As part of your solution, give an estimate of the time-complexity of the `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.

## 4.3 Sample Solutions to Assignment 1

code/Week02/assig1-soln.rkt

 `    ``#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)))` `    `` `

## 4.4 Formative Quiz

For the purpose of this quiz, you can use full scheme/racket as for the assignment.

Implement the function `(exp-translate E)` that takes an infix expression `E` as above and produces the scheme/racket expression that can be directly evaluated.

For example:
```(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) ```

Challenge: Implement the function `(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) `

## 4.5 Sample Answers to Quiz

code/Week02/exp-translate.rkt

 `    ``#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`

code/Week02/exp-vars.rkt

 `    ``#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