Explore Posterous

Color Scheme

Color Scheme

A Very Small Victory, and a Small Thought on Learning

Last weekend I sat down at my Scheme interpreter and attempted to write a simple function that would raise a given integer by a given power.  It's not rocket science, but I had a damned hard time with it.  Firstly, I was not at all familiar with the Scheme dialect.  Secondly, my skills at recursion had vanished without a trace.  I instinctively knew what I needed to do, but couldn't quite formulate it.  A little embarrassing, I have to say.

When recurring on a list of atoms, lat, ask two questions about it: (null? lat) and else.  When recurring on a number, n, ask two questions about it: (zero? n) and else.  When recurring on a list of S-expressions, l, ask three questions about it: (null? l), (atom? (car l)), and else.

(define raise
  (lambda (x n)
    (cond
      ((zero? n) 1)
      (else (* x (raise x (- n 1)))))))

Finished the First Two Chapters of The Little Schemer

I just wrapped up the first two chapters of The Little Schemer, working on the examples in my head and then running them through the PLT Scheme environment as well.  Both approaches have their place - the first helps you build the mental pathways necessary for this sort of problem solving, the second allows you to implement and alter the experiments so that you can make sure that you understand exactly what is going on.  

   
(define member?       
  (lambda (a lat)    
    (cond        
      ((null? lat) #f)        
      (else (or (eq? (car lat) a) (member? a (cdr lat)))))))  

Wanting to be sure that I understood the 'cond' statement properly, I altered the function like so to verify that it would still return the same results:

(define member?
  (lambda (a lat)
    (cond
      ((null? lat) #f)
      ((eq? (car lat) a) #t)
      (else (member? a (cdr lat))))))

Setting Short Term Goals

I'm one of those people that needs to set goals.  It's a way of harnessing the power of a large body of water, and focusing it down to a controlled stream.  I have too many curiosities to be left to roam without inner guidance!

Structure and Interpretation of Computer Programs at YouTube

Here goes a great series of class available at YouTube. It is a Berkley course based on the great book Structure and Interpretation of Computer Programs.
I came in greate time, since I'm studying Clojure.
 
By the way, don't forget to check the other 19 classes on the right bar of this youtube video.
 

The Marketing Mix

this one busted me up a bit today

;exercise 2.20 - return numbers of same parity, arbitrary number of arguments 
(define (same-parity . x) 
  (define (parity y) 
   (modulo y 2)) 
  (define (same-parity-recur x) 
   (cond ((null? (cdr x)) 
      x) 
      ((= (parity (car x)) 
        (parity (car (cdr x)))) 
      (cons (car x) (same-parity-recur (cdr x)))) 
      (else 
      (same-parity-recur (cons (car x) (cdr (cdr x))))))) 
   (same-parity-recur x)) 

although the ". x" takes a variable number of arguments and turns it into a list, it does not mean that you can pass in a list and have it do the right thing. and as far as i can tell, you can't decompose a list into atoms (since a function can't return more than one atom).
 
so therefore i have my hacky wrapper around what i think is a reasonably clever implementation of this, which results in:

(same-parity 1 2 3 4 5 6 7) 
(1 3 5 7) 
 
(same-parity 2 3 4 5 6 7) 
(2 4 6)

anyone have better suggestions? i probably [hopefully] just have a few gaps in my knowledge of scheme right now...

Applicative Order Y Combinator

;                          Stumbling towards Y
;
; The applicative-order Y combinator is a function that allows one
; to create a recursive function without using define.
; This may seem strange. Usually a recursive function has to call
; itself, and thus relies on itself having been defined.
;
; Regardless, here we will stumble towards the implementation of the
; Y combinator (in Scheme).
;
; This was largely influenced by material in "The Little Schemer".
; http://www.ccs.neu.edu/home/matthias/BTLS/
;
; I wrote this because I needed the excersise of arriving at Y on my
; own terms.
;
; Mark Bolusmjak, 2009
; Disclaimer: This document and code are without warrenty.



; Let's start with the Factorial function as our example.
(define fact
  (lambda (n)
    (cond
      ((= 0 n) 1)
      (else (* n (fact (- n 1)))))))

; Since we can't use define, let's strip that off.
; For the recursive call, let's just put in a placeholder
; to see how things look. We'll call the placeholder "myself".
(lambda (n)
  (cond
    ((= 0 n) 1)
    (else (* n (myself (- n 1))))))

; Ok, we need a way for the function to call itself via "myself".
; How will we get a handle on that if we can't use define?
; Maybe something can pass it in for us. Let's hope so and
; keep going.
(lambda (myself)
  (lambda (n)
    (cond
      ((= 0 n) 1)
      (else (* n (myself (- n 1)))))))

; That looks a lot like our original define-ed factorial function.
; Let's replace "myself" with fact and take a look (below).
;
; From the outside, it looks like something that makes the factorial
; function.
; Strangely, this function that creates the factorial function,
; relies on the function "fact" to be supplied to itself.
; Where will that come from?
; Doesn't that bring us back to square one?
(lambda (fact)
  (lambda (n)
    (cond
      ((= 0 n) 1)
      (else (* n (fact (- n 1)))))))

; Well, here we have a function that builds the factorial function.
; That seems nearly as useful as a factorial function. Maybe we
; could pass that to itself and call on it when we need it.
;
; First we need to pass that whole (lambda (fact) ... ) to itself.
; It's pretty easy to pass a function to itself if we have it
; defined.
; e.g. (f f)
; What about an anonymous function?
; No problem, just write a helper function that takes any function
; and applies it to itself.
(lambda (f) (f f))

; Ok, let's throw that in and take a look.
; We'll pass (lambda (fact) ... ) to itself via this helper.
((lambda (f) (f f))
 (lambda (fact)
   (lambda (n)
     (cond
       ((= 0 n) 1)
       (else (* n (fact (- n 1))))))))

; What happens if we try this out?
(((lambda (f) (f f))
  (lambda (fact)
    (lambda (n)
      (cond
        ((= 0 n) 1)
        (else (* n (fact (- n 1)))))))) 0)

; Hey it works for 0, but not for anything else.
; What's going on?
;
; With 0, (= 0 n) is true, and we get 1 back.
;
; If we try any other number we get a complaint that * is expecting a
; numbervas it's 2nd argument, but is getting a procedure. Huh?
; We got a bit ahead of ourselves.
; Recall, fact is not the factorial funtion anymore. It now *builds*
; the factorial function. We can't just pass it a number.
; As the fact builder function, it expects a function as an argument
; before it returns the actual function we want.
;
; This may be getting strange, but let's try to make a useful
; function out of fact by calling (fact fact). At least (fact fact)
; will work for the next step into our recursive function.
((lambda (f) (f f))
  (lambda (fact)
    (lambda (n)
      (cond
        ((= 0 n) 1)
        (else (* n ((fact fact) (- n 1))))))))

; Hmm ... recursion works by "always working for the next step",
; which we seem to have just covered. So could it work for all the
; "next steps"?
; Let's try to call that with a value other than 0.
(((lambda (f) (f f))
  (lambda (fact)
    (lambda (n)
      (cond
        ((= 0 n) 1)
        (else (* n ((fact fact) (- n 1)))))))) 5)

; Wow! That actually worked.
; Take a breather and think about this for a second. We just
; implemented a recursive function without using define.
; Pretty cool, but it's kind of messy.
;
; We have something that kind of looks like our original factorial
; definition in there. Let's try to refactor that out and see what
; we're left with.
;
; Our original fact function didn't have anything looking like a
; (fact fact) in it, so let's try to fix that first.
;
; As the next step, we'll pull out the (fact fact) and give it a
; name.
; What should we call it?
; fact is kind of like factorial builder at this point, so
; (fact fact) is more like the factorial function.
; Hmm ... let's just call (fact fact) fact2, see how things look and
; go from there.
;
; We're going to be clever and instead of simply passing (fact fact)
; in as fact2, we're going to wrap it up as a closure to prevent
; (fact fact) from getting evaluated before it gets passed in. Cool?
; We'll pass in (lambda (x) ((fact fact) x)) instead.
((lambda (f) (f f))
 (lambda (fact)
   ((lambda (fact2)
      (lambda (n)
        (cond
          ((= 0 n) 1)
          (else (* n (fact2 (- n 1)))))))(lambda (x) ((fact fact) x)))))

; If we try this out, we see it still works.
(((lambda (f) (f f))
  (lambda (fact)
    ((lambda (fact2)
       (lambda (n)
         (cond
           ((= 0 n) 1)
           (else (* n (fact2 (- n 1)))))))(lambda (x) ((fact fact) x))))) 12)

; Taking a closer look, we see that (lambda (fact2) ... ) looks
; exactly like our original (lambda (fact) ... ).
; Let's simply rename fact to y, and fact2 to fact to make this
; clear.
((lambda (f) (f f))
 (lambda (y)
   ((lambda (fact)
      (lambda (n)
        (cond
          ((= 0 n) 1)
          (else (* n (fact (- n 1)))))))(lambda (x) ((y y) x)))))

; Let's pull out (lambda (fact) ... ) and pass it in as a parameter
; r (for recursive function).
((lambda (r)
   ((lambda (f) (f f))
    (lambda (y)
      (r (lambda (x) ((y y) x))))))
 (lambda (fact)
   (lambda (n)
     (cond
       ((= 0 n) 1)
       (else (* n (fact (- n 1))))))))

; Still works! Try it.
(((lambda (r)
    ((lambda (f) (f f))
     (lambda (y)
       (r (lambda (x) ((y y) x))))))
  (lambda (fact)
    (lambda (n)
      (cond
        ((= 0 n) 1)
        (else (* n (fact (- n 1)))))))) 4)

; Now we've isolated the scaffolding we've built to allow the
; creation of a recursive function without define.
;
; Finally, we've lived long enough without define, and that thing we
; built seems pretty useful.
; Let's use define and call it Y.
(define Y
  (lambda (r)
    ((lambda (f) (f f))
     (lambda (y)
       (r (lambda (x) ((y y) x)))))))

; That's it. We've built the applicative-order Y combinator.

; Try it with another recursive function. Here it is with the
; Fibonacci number generator, taking a value of 8 as a parameter.
((Y
  (lambda (fib)
    (lambda (n)
      (cond 
        ((< n 2) n)
        (else (+ (fib (- n 1)) (fib (- n 2)))))))) 8)

Fried noodles

well, specifically one: mine. not far beyond my last post, i encountered this piece of brain melter, in which we define zero in terms of a procedure and the positive integers from that:

 (define zero (lambda (f) (lambda (x) x)))
 (define (add-1 n)
   (lambda (f) (lambda (x) (f ((n f) x)))))
 

substitution helps to figure it out:

 (add-1 zero)
 (add-1 (lambda (g) (lambda (y) y)))
 (lambda (f) (lambda (x) (f (((lambda (g) (lambda (y) y)) f) x))))
 (lambda (f) (lambda (x) (f x)))
 

therefore, we can now define one, two, and plus in this manner (plus is hard, i will admit that i didn't get it right on my own)

 (define one (lambda (f) (lambda (x) (f x))))
 (define two (lambda (f) (lambda (x) (f (f x)))))
 (define plus (m n) (lambda (f) (lambda (x) ((m f) ((n f) x)))))
 

fascinating stuff, i'm off to read more.

Mind blowing

(define (cons x y) 
 (define (dispatch m) 
  (cond ((= m 0) x) 
     ((= m 1) y) 
     (else (error "Argument not 0 or 1 -- CONS" m)))) 
 dispatch) 
 
(define (car z) (z 0)) 
 
(define (cdr z) (z 1)) 

or even more crazy:

(define (cons x y) 
 (lambda (m) (m x y))) 
 
(define (car z) 
 (z (lambda (p q) p))) 
 
(define (cdr z) 
 (z (lambda (p q) q))) 

i've always been quick to criticize theory. i guess what i needed was
to find some theory that i found fascinating and enlightening.