Archive for the ‘SICP’ Category

Section 2.4 – Multiple representations for Abstract Data

January 17, 2009

1) Tagged data – Attach-tag simply tags the data, type-tag returns the type of the data, and contents returns the contents of the data, they are defined very similar to pair (cons car cdr). The problem with this approach is you cannot add new data-types easily, and there is clashing of names.

2) In data-directed programming, we install a package for every type of data, for eg rectangular complex numbers, we define procedures to give us the real part, imaginary part, magnitude, and angle. We also have procedures called make-from-real-imag, and make-from-mag-angle, that take in two numbers, cons them (for mag-angle, they compute 1st no. cos 2nd no, and 1st no sin 2no no) and then attach the tag rectangular before them. These procedures are then inserted using get and put in the table.

3) apply-generic is a general procedure, that takes in an operation and arguments. (think of it as taking in a real-part operation and a complex number) It then finds the appropriate procedure from the table that would apply to this kind of data, and if the procedure exists, applies it, else returns an error. Now real-part z is defined as (apply-generic ‘real-part z) and similarly for all other procedures.

4) In tagged data, we had intelligent operations, which acted according to data. We can also have intelligent data, which acts according to operations. This is called message-passing. Here make-from-real-imag x y returns a procedure, that when passed realpart, returns x, when passed imagpart, returns y, and so on. We never actually physically construct something as a complex number (I mean we never construct data, a complex number is now a procedure) Now (apply-generic op arg) is defined as (arg op). This is quite a non-intuitive technique.

Advertisements

Exercise 2.82

January 10, 2009

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op ‘type-tags)))
      (if proc
          (proc (map contents args))
          (try-coercion op . args)))))
(define (try-coercion op . args)
  (let ((n (length args)))
    (define (iter count)
      (if (= count n)
          (error “No proc defined for type-tags”)
          (let ((convert-to (stream-ref count args)))
              (let ((current-type (type-tags convert-to)))
                (if (convert-all args current-type)
                    (apply (get op (repeat n ‘current-type)) (convert-all args current-type))
                    (iter (+ 1 count)))))))
    (iter 0))) 

(define (convert-all args current-type)
  (if (null? args)
      ‘()
      (cons ((get-coercion (type-tags (car args)) current-type) (car args)) (convert-all (cdr args) current-type))))

Eval Apply Example

January 10, 2009

The particular problem I would like to look at is

Its the evaluation of

eval quote (((lambda(x) (lambda(y) (+ x y))) applied to 3) applied to 4) in some global environment which I will call e0. 

What we have is a procedure of one argument x which produces as its value a procedure of one argument y which adds x to y. We are applying the procedure of one argument x to 3 so that x should become 3, and the result of that will be a procedure of one argument y, which we will then apply to 4.

To do this we need a global environment,which I’ll call e0, and it will have definitions of +, *, -, /, car, cdr, cons, eq? and everything else. Something the machine is born with.

What does it mean to do this evaluation? First, we will go through all the special forms, this is not a number, this is not a symbol, its not a quoted expression, its not a thing that begins with lambda, its not a thing that begins with cond, therefore its an application of an operator to operands, its a combination.  The combination has an operator and operands.

We transform this to apply of (eval of (quote ((lambda(x) (lambda(y) (+ x y))) 3) in the environment, also e0, (Note here I have evaluated the operator) with the arguments being the result of (evlist the list containing 4 ine0).  e0 is the quoted expression for the data structure which will be the environment goes there. (What this basically does is, when you get a combination, evaluate the operator, evaluate the operand and apply the operator to operand. The evaluation of operands or arguments is done in steps, through evlist. If you see the body of evlist its just the consing of the evaluation of each argument.)

To do this, I have to do first and the second. Lets do the second first. This is first part followed by, the evlist turns into cons of eval of 4 in e0, followed by evlist ‘() in e0.

This is apply of eval of …. eval of 4 is 4, it meets the number criterion, evlist of empty list is the empty list, so what I get is the list 4 (4).

Lets look at the next intersting thing, what do I do to evaluate that expression? Evaluating this is nothing but an application of the operator applied to this operands,its that combination. So its just apply of eval of the operator, and evlist of the operands.

Note that next thing will be a special case because its a lambda expression, why weren’t those earlier things considered lambda expressions, because they were lambda expressions applied to some arguments (operators applied to operands), now its just pure operator that we have settled down to.

Eval of a lambda expression produces a procedure object. (Think of this as an abstract procedure object, with the two circles, and the 2nd circle pointing to the environment.) This abstract object we denote by closure, and environment e0 gets captured in it. Now we have to apply that procedure to the arguments.

However, that procedure is not primitive, its got the tag closure. Therefore, we have to do a bind. A new environment is made, which has as its parent environment, e0, and we’ll call this e1, and x is bound to 3 in e1.

So what our expression transforms into is the eval of the body of the procedure, in the environment e1. Apply (eval (lambda(y) (+ x y) e1) (4)).

I know how to evaluate a lambda. That means I apply the abstract procedure closure (x) (+ x y) with e1 captured in it. Apply that to 4.

That’s easy. That means I have to make a new environment which points to the environment pointed by the procedure, and which binds y to 4. This environment we will call e2. 

Our expression then is evaluate the body in e2. i.e. (eval (+ x y) e2)

But this is an application, therefore it becomes, apply of eval of + in e2, (apply (eval + e2) (evlist ‘(x y) e2)

That is (apply some primitive operator + to the result of evaluating x and y in e2), which is (apply some primitive operator + to 3 and 4) which gives me a 7 magically (since we don’t know +)

See one important ingredient – what’s being passed around, and who owns what and what his job is. eval produces procedure and arguments for apply. Some things eval can do by itself, those are little self things that are not interesting. Eval also evaluates all arguments one after the other, that’s not very interesting. Apply can do certain things by itself, such as +, not very interesting.But if apply can’t apply a procedure, it produces an expression, and an environment, for eval. The procedure and arguments wrap up the state of a computation, and so do expressions and environment.

eval-apply-example-board-1

eval-apply-example-board-2

eval-apply-example-env-diagram

eval-apply-example-board-3

eval-apply-loop

Memoization

January 3, 2009

I am not confident I would have got this myself. Its an amazing program. Took some time to analyze too that its a working program.

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))


 
The memoized version of the same procedure is

(define memo-fib
  (memoize (lambda (n)
             (cond ((= n 0) 0)
                   ((= n 1) 1)
                   (else (+ (memo-fib (- n 1))
                            (memo-fib (- n 2))))))))


 
where the memoizer is defined as

(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
        (or previously-computed-result
            (let ((result (f x)))
              (insert! x result table)
              result))))))

Sets as Binary Trees

January 2, 2009


(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set) 
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

SICP Exercise 3.21

January 2, 2009


(define (print-queue queue)
  (define (print-list sequence-ptr)
    (if (null? sequence-ptr)
        '()
        (begin
          (display (car sequence-ptr))
          (print-list (cdr sequence-ptr)))))
  (print-list (front-ptr queue)))