In the 1980s, most universities used an imperative language, e.g., BASIC, as the medium of instruction for CS 101. Then MIT and other universities began using LISP or Scheme. What first programming language should be taught was a topic of great debate, when one would usually hear the following cited:

	History
	Lisp, AI and govt. funding, AI Winter speed problems: Lisp Machines, Symbolics, James Gosling, Guy Steele, Common Lisp, Emacs, Richard Stallman interpreter vs, compilers

Discussions, examples... Some Scheme examples:

(* 3 4)
(* 4 (+ 3 2))
(- 6 7)

The following program demonstrates a the use of a function that does not evaluate its arguments, first.

(define (when-non-zero val expr)
  (if (= 0 val)
    1
    expr ) )

(when-non-zero 0 (/ 1 0))

Discussion of order of evaluation, ordinary functions and special forms.

Consider the evaluation of expressions in a language without if-statement special forms, i.e., consider the following program under the situation that if statements use applicative-order instead of Scheme's normal order (i.e., delayed evaluation for if-statements then and else arguments)

(define (even? x)
  (if (zero? x)
      #t
      (odd? (- x 1))))

(define (odd? x)
  (if (zero? x)
      #f
      (even? (- x 1))))

show how applicative order -- infinite recursion normal order evaluation -- short circuits

applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed. Delaying evaluation of procedure arguments until the last possible moment (e.g., until they are required by a primitive operation) is called lazy evaluation.

strict: all arguments eval'd before body of procedure begins executing.

non-strict: body of procedure begins executing (evaluating) before arguments. (Delayed evaluation or non-strict cons-pairs can be used in forming streams)

Here are examples demonstrating special form (macros) evaluation vs. standard evaluation order.

(cond ((C1 E1)
       (C2 E2)
        ...
       (else En) )

(if (< 3 4)
    0
    (* 10 10) )

Consider the following recursive Scheme function.

define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

Using the substitution model of evaluation, we can see this by rewriting.

(factorial 5)
(* 5 (factorial 4))
...
(* 5 (* 4 (* 3 (* 2 1))))
...
(* 5 24)
120

But what if we adopt strict evaluation model?

Linear Recursion; Tail Recursion; Tree Recursion Relationship between tail recursion and iteration. Modern Scheme compilers internally trivially convert tail recursive functions into iteration.

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter prod count max)
  (if (> count max)
    product
    (fact-iter (* count prod)
               (+ count 1)
               max)))

;; NOTE this is not scheme, but representation of what a scheme compiler
;; might possibly generate for intermediate code statements suitable for
;; execution by Schemes internal VM.
;;

(define (fact-iter prod count max)
  (code-sequence
    (:= tmp1 (> count max))
    (branch-if-true tmp1 'label1)
    (return product)

(label 'label1)
    (:= tmp2 (* count prod))
    (:= tmp3 (+ count 1))
    (return (call-function 'fact-iter (tmp2 tmp3 max))
   )
)

- Mention Continuation (advanced concept) and Closure (advanced concept) make the transformation to iteration generalizable to any tail-recursive call. - [if time/ interest could discuss CPS-continuation passing style]

Continuations - like a goto, terminating evaluation - tail recursion explained in terms of continuations - "goto with variable bindings"

;; Defining a "verbose if" expression.
;; - requires two literal keywords, "then" and "else"
;; - doesn't eval args, just passes onto the built-in "if"
;;
(define-syntax verbif
  (syntax-rules (then else)
    ((_ tst then t else e) (if tst t e))))

> (verbif (< 1 2) then 55 else (display 22))
55
> (verbif (> 1 2) then 55 else (display 22))
22
> (verbif (> 1 2) 55 44)
STDIN::206: verbif: bad syntax in: (verbif (> 1 2) 55 44)


;; Redefining with a parenthesized syntax
(define-syntax verbif
  (syntax-rules (then else)
    ((_ tst (then t) (else e)) (if tst t e))))


> (verbif (< 1 2) (then 'foo) (else 'bar))
foo
>


(define-syntax switch
  (syntax-rules (case)
    ((_ value) #f)
    ((_ value (case v e) cases ...) (if (= value v)
                                        e
                                        (switch value cases ...)))))


> (switch 4)
#f
> (switch 4 (case 4 44))
44
> (switch 4 (case 1 11) (case 2 22) (case 3 33) (case 4 44))
44
> (switch 5 (case 1 11) (case 2 22) (case 3 33) (case 4 44))
#f