Review: Mantras -- Part 1

1. Every expression* has a value.
2. To find the value of a combination,
   • Find the values of all of the subexpressions, in any order
   • Apply the value of the first to the values of the rest
3. The value of a lambda expression is a procedure.

*: Except for errors, infinite loops, and the define special form.

Four Kinds of Expressions

Primitive Expressions (no parens)

Constants

numerals, quoted strings, booleans #t and #f, ...

Variables

names for values. Names can be built-in ("primitives"), defined, or the parameters of a procedure (only "lexically within the procedure body")

Compound Expressions (in parens)

Special forms

and, begin, case, cond, define, do, if, lambda, let, let*, letrec, or, quasiquote, quote, set!

Combinations

"Function call" or "procedure application"

Predefined Procedures

• There are lots of them; see the manual.
• Predefined doesn't mean primitive!
• We won't tell you what's really primitive. It varies.
• We introduce new ones all the time, without prior warning.

Conditional Expressions

(if predicate consequent alternative)

(cond clause1 clause2 ...)

where a clause is (predicate consequent ...) or (else consequent ...)

(and e1 e2 ...)

(or e1 e2 ...)

Examples (Blackboard)

(define x 10)

(if (= x 10) 1 2)

(define absolute-value
  (lambda (x) (if (negative? x) (- x) x)))

(define (absolute-value x)
  ;; shorthand version of define
  (cond ((zero? x) 0)
        ((negative? x) (- x))
        (else x))

Substitution Model

Remember Mantra 2: To find the value of a combination,

• Find the values of all of the subexpressions, in any order
• Apply the value of the first to the values of the rest

"Apply" (for now) means "substitute the values of the arguments for the corresponding parameters in the body of the procedure being called."

Examples (Blackboard)

(absolute-value (+ x 3))

((lambda (a) (* a a)) (+ 2 3))

(define (simplify n)
  ;; Assuming 0 <= n <= 17 then 0 <= result < 9
  (if (>= n 9)
      (- n 9)
      n))

(define (cast-nines n)
  ;; If n is a non-negative integer, then 0 <= result < 9
  (if (< n 9)
      n
      (simplify (+ (remainder n 10)
                   (cast-nines (quotient n 10))))))

(define (test a b)
  (= (simplify (+ (cast-nines a)
                  (cast-nines b)))
     (cast-nines (+ a b))))

One More Special Form

(let ((name1 expression1)
      (name2 expression2)
      ...)
  body)

Temporarily (only inside of body) gives the name name1 to the value of expression1, the name name2 to the value of expression2, etc., and returns the value of body

One Last Example

(define (cast-nines n)
  (define (loop answer-so-far left-to-do)
    (if (zero? left-to-do)
        answer-so-far
        (let ((next (+ answer-so-far
                       (remainder left-to-do 10))))
          (loop (simplify next)
                (quotient left-to-do 10)))))
  (loop 0 n))