Archive for the ‘lisp’ Category

Finding Primes In SICP

November 2nd 2010

I was reading SICP over lunch and found this lovely footnote on probabilistic methods for deciding if a number is prime. (it is #47)

Numbers that fool the Fermat test are called Carmichael numbers, and little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601. In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a “correct” algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering.

Posted by tom under lisp & SICP | No Comments »

Creating Something (In fact everything) out of nothing, Twice

October 25th 2010

I am reading through SICP with some of the guys in work and got to a bit that fascinated me and reminded me of my previous life as a mathematician.

The basic data structure in Scheme is the cons cell, essentially representing a ordered pair. So

> (cons 2 3)
(2 . 3)

creates the pair (2 . 3)

Lets call that a, 

> (define a (cons 2 3))

There are 2 other functions that act on these cons cells, car returns the first, cdr returns the second

> (car a)
2

> (cdr a)
3

You can build lists by chaining these cons cells and unpick the contents by using car and cdr

> (define b (cons 3 a))
> b
(3 2 . 3)

> (car b)
3

> (cdr b)
(2 . 3)

> (cdr (cdr b))
3

The interesting bit is at p91 of the book where it breaks down the distinction between procedures and data

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "arg no 0 or 1" m))))
  dispatch)

So here cons is a function of x and y as you would expect. The trick is that its return value is a function (internally called dispatch) of one argument that returns x if passed 0 and y if passed 1, otherwise it throws an error.

Now car and cdr can be defined

(define (car z) (z 0))

(define (cdr z) (z 1))

So car takes z as an argument and tries to apply z to 0, while cdr applys it to 1. While car and cdr will accept any function as an argument it makes sense if z is the cons of something as before.

As an example

(car (cons 1 2))

car will pass 0 to (cons 1 2)
(cons 1 2) returns 1,
similarly

(cdr (cons 1 2))

returns 2 as cdr will pass 1 to (cons 1 2)

This is not how the interpreter actually works, just the introduction to the idea of code as data (as code etc) in Lisp. This is the feature that sets it aside from other languages, in particular code is not parsed, jut loaded up as it is a valid data structure itself and allows for the powerful macro systems usually seen in Lisps.

Now for twice, it reminded me of some Set Theory, in particular forming the Natual Numbers in terms of sets.

We define 0 to be the empty set
.

Then we can define 1 to be

(this has 1 element – we say has cardinality 1)

Then 2 is

Notice this has cardinality 2 and is formed as the set containing all the previous numbers.

So we have all positive whole numbers. You can then define arithmetic and number theory in terms of these sets.

See this site for a nice introduction to set theory (it also begins by defining ordered pairs)

Loving SICP, got to do some Induction for the first time in ages last night!

Posted by tom under lisp & SICP | 1 Comment »