Lisp / Scheme: A Functional Language

Syntax:
Atom ::= Symbol | Number
Expression ::= Atom | ( Expression* )

Evaluation:
Number => itself
Symbol => its current binding
(OrdinaryFunction Arguments) => 
    Evaluate each of the arguments
    Apply OrdinaryFunction
(quote Expression) => Expression (unevaluated)
'Expression => Same as (quote Expression)
(SpecialForm Arguments) => Depends.

Interpreter loop:
Prompt top[#]=> User types expression
  Interpreter evaluates expression
  Types value := <Value of expression>
Note: Expression oriented language. 
Every expression has a value.

Comments -- semicolon to end of line.

Basic evaluation

   value := 1
   top[1]=> (+ 23 76) 
   value := 99
   top[2]=> (+ (* 7 2) (- 9 5))
   value := 18
   top[3]=> (set! I 7)  ; set! is a special form. 
   value := 7
   top[4]=>(+ I 2)
   value := 9

Quote suppresses evaluation

   top[5] => (quote (a b c))
   value := (a b c)
   top[6] => (quote (+ I 7)) 
   value := (+ I 7)
   top[7] => '(+ I 7)
   value := (+ I 7)

Basic list functions: car, cdr, cons
   (car '(a b c)) => a
   (cdr '(a b c)) => (b c)
   (cons 'a '(b c)) => (a b c)
   (car '((a b) (c d) e)) => (a b)
   (cdr '((a b) (c d) e)) => ((c d) e)
   (cdr '(a)) => ()  ; null list
   (car '()) => error
   (cadr '(a b c)) => b
   (cddar '((a b c) d e)) => (c)
   (list 'a '(b c) I) => (a (b c) 7)

Basic boolean functions
  (equal? '(a b) '(a b)) => #t
  (equal? '(a b) '(c d)) => #f
  (null? '()) => #t
  (null? '(b c)) => #f
  (symbol? 'a) => #t
  (symbol? '(a)) => #f
  (list? '(b)) => #t
  (list? 7) => #f

Binding atoms
  (define PI 3.14159) => PI ; Permanent definition. Only used at top level.
  (set! E 2.718) => 2.718   ; Side effect. Looked down on in functional 
                            ; languages

Defining functions
  (define (add3  X) (+ X 3)) => foo
  (add3 7) => 10.

Conditionals
  (define (absolute N) (if (> N 0) N (- N))) => absolute
  (absolute -3) => 3

 
(cond (--Condition-- 
       --Expression--
       --Expression--
      )
     (--Condition--
      --Expression--
      --Expression--
     )
    ...
    (--Condition--
     --Expression--
     --Expression--
    )

  (define (absolute N) 
     (cond ((> N 0) 
            N) 
           (#t (- N))))


Recursion

Numerical recursion

   (define (sumToN N)
      (if (= N 0) 
          0
          (+ N (sumToN (- N 1)))))

   (define (power X N)
      (cond ((= N 0) 1)
            (#t (* X (power X (- N 1))))))

   (define (fibonacci N)
       (cond ((= N 1) 1)
             ((= N 2) 1)
             (#t (+ (fibonacci (- N 1)) (fibonacci (- N 2))))))

; creates list of first N Fibonacci numbers in  backward order.
; Note: It is often easiest in Lisp to create lists in backward order.

   (define (fibNums N)
     (cond ((= N 1) '(1))
           ((= N 2) '(1 1))
           (#t
            (let ((L (fibNums (- N 1))))
              (cons (+ (car L) (cadr L)) L)))))




Cdr-Recursion
   (define (mem1 X L)
     (cond ((null? L) #f)
           ((equal? X (car L)) #t)
           (#t (mem1 X (cdr L)))))  

   (define (myLength L)
       (cond ((null? L) 0)
             (#t (+ 1 (myLength (cdr L))))))

   (define (addLists L M)
     (cond ((null? L) '())
           ((null? M) '())
           (#t (cons (+ (car L) (car M)) (addLists (cdr L) (cdr M))))))

   (define (myAppend L M)
      (cond ((null? L) M)
            (#t (cons (car L) (myAppend (cdr L) M)))))

; inserts NEW into L before the first occurrence of OLD non-destructively

(define (insertBefore NEW OLD L) 
  (cond ((null? L) '())
        ((equal? (car L) OLD)
         (cons NEW L))
        (#t
         (cons (car L) (insertBefore NEW OLD (cdr L))))))

(set!  '(x y z)) => (x y z)
(insertBefore 'a 'y L) => (x a y z)

L => (x y z)

; Top level superroutine with a recursive helper

(define (myReverse L)
   (myReverse1 L '()))

; (myReverse1 L M) returns the list with L reversed followed by M.

(define (myReverse1 L M)
   (cond ((null? L) M)
         (#t (myReverse1 (cdr L) (cons (car L) M)))))

(myReverse1 '(c d) '(a)) => (d c a))
(myReverse '(a b c)) => (c b a)


Car recursion

   (define (firstAtom L)
     (cond ((list? L) 
            (firstAtom (car L)))
           (#t L)))

   (firstAtom '(a b c)) => a
   (firstAtom '(((b) c) d)) => b

Car-Cdr recursion

(define (flatten L)
  (cond ((null? L) L)
        ((not (list? L))
         (list L))
        (#t 
         (append (flatten (car L)) (flatten (cdr L))))))

(flatten '((a b) (c) (d e f)))

(define (addNumbersIn L)
  (cond ((null? L) 0)
        ((number? L) L)
        ((list? L) 
         (+ (addNumbersIn (car L)) (addNumbersIn (cdr L))))
        (#t 0)))      

(addNumbersIn '((A 1) 5 ((2 (8)) C))) => 16

Local variables
 (let ((variable binding) (variable binding) ... (variable binding)) 
      body)

Variables are local, and initialized to bindings which are evaluated in
outer context.

 (let* ((variable binding) (variable binding) ... (variable binding)) 
      body)

Variables are initialized to bindings which are evaluated sequentially.


(set! I 3)
(set! J 8)
(let ((J (+ I 2)) (I (* J 5))) 
    (list I J)) 

=> (40 5)

(let* ((J (+ I 2)) (I (* J 5))) 
    (list I J)) 
=> (25 5)