Graduate Program KB

SICP

Chapter 1.1

  • Lisp (LISt Processing) was invented in the 1950s which uses recursive logical expressions as its computation model
  • Lisp is not efficient but great as an educational tool
  • Fundamentally, there are two elements: Data and Procedures

Compound expressions (combinations)

  • Expressed as a list containing an operator on the left, followed by an arbitrary amount of operands 
    (+ 137 349)
486
  • Combinations can also be nested, it can become messy though. So, a concept called 'pretty-printing' is used to improve readability 
    (+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
58

    (+ (* 3
	    (+ (* 2 4)
   	       (+ 3 5)))
   (+ (- 10 7)
      6))
58

Variables

  • Use keyword define, can be used in evaluating expressions 
    (define x 3)
(* x 5)
15

Compound procedures

  • Procedures can also be defined, similar to assigning functions to variables in JavaScript

    • <name> Symbol associated with procedure definition
    • <formal parameters> Name of arguments passed to the body
    • <body> Expression to evaluate procedure, formal parameters are within scope
    (define (<name> <formal parameters>) <body>)

(define (square x) (* x x))
(square 5)
25

Substitution model

  • Compound procedures are applied to arguments by evaluating the body where each formal parameter is replaced by the corresponding arguments

    (define (sum-of-squares x y) (+ (square x) (square y)))

Evaluate (sum-of-squares 5 6).
First, retrieve the body of sum-of-squares.
Second, replace formal parameter by their corresponding argument.

(+ (square x) (square y)) ----> (+ (square 5) (square 6))

Then, using the definition of square which is (* x x) to evaluate the expression.

(+ (* 5 5) (* 6 6)) ----> (+ 25 36) ----> 51

  • There are two methods to evaluate expressions:

    • Applicative-order evaluation Evaluate the arguments then apply (This is what the interpreter uses)
    • Normal-order evaluation Fully expand then reduce

  • Both methods yield the same result, but normal-order evaluation generally computes redundant expressions

Conditional expressions

  • The cond keyword is a special form (don't conform to general evaluation rule)
    • Consists of paranthesised pairs of expressions called clauses
    • In each clause, <p> is a predicate and <e> is an expression
    • The expression only evaluates if the predicate is true
    (cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

(define (abs x)
    (cond ((> x 0) x)
    	  ((= x 0) 0)
    	  ((< x 0) (- x))))
  • else is a special form which returns a default value if all previous predicate fail 
    (define (abs x)
    (cond ((< x 0) (- x))
    	  (else x)))
  • if is a special form that can be used in cases with two scenarios 
    (if <predicate> <consequent> <alternative>)

(define (abs x)
    (if (< x 0) 
        (- x)
    	x))
  • Predicate compounds:
    • Evaluation is stopped if the left subexpressions return false early, with the exception of not
    • and and or are special forms, not is an ordinary procedure
    (and <e1> ... <en>)
(or <e1> ... <en>)
(not <e>)