The Rest Period and Pong   2 comments

Wow, haven’t posted in a while, but rest assured, I’ve been pretty busy! I’ve had a bunch of tests and exams recently in school, so I’ve had less time to work on things digital, but I’ve still managed to accomplish a fair bit.

I’m still working through SICP, I’m working on the part about data structures for sets.
I have done a total rewrite of my NCurses PONG Clone, and present to you the result:

Coxswain is winning!

I’ve got AI, a scoreboard and a few other things which I’m currently working on, check out the code at github

Posted 11/06/2010 by Emmanuel Jacyna in General Life

Tagged with , , , ,

pyafg – new features!   Leave a comment

If you’ve been watching my pyafg github repo of late, you will have noticed that I’ve been very busy hacking on pyafg in the last few weeks, and have managed to add a heap of cool new features.

What’s New

  • Added a graphical transform editor
  • Added a gradient coloring system
  • Added more features!
  • Added some more fractals
  • Fixed many bugs
  • Made the pygame interface cleaner
  • You can now save images in the pygame interface
  • Added gradient demo

The transform editor was written using tkinter, and so for that reason it is neither pretty nor quick (for some reason tkinter does not support drawing directly to a canvas, you have to make objects on the canvas), but it does the job well, and I’ve managed to create quite a few neat looking fractals with it. In the future I hope to make a gtk or qt interface, but until then, it should do the job.

pyafg's tkinter transform editor

I’ll need to tidy up and standardize the command line arguments to pyafg, because I’ve added a lot more options. Here is an example of gradient coloring.

Here is a shot of the gradient for the above image.

Posted 22/05/2010 by Emmanuel Jacyna in pyafg

Tagged with , , , ,

SICP – Section 2.3.1-2.3.2   Leave a comment

This section introduces the idea of “symbolic data”, and demonstrates how we can abstract our code with it. I found it to be really enjoyable, the questions were very challenging at the end. I notice I seem to say that I find each section enjoyable, and I do! I cannot recommend this book enough, not only for the knowledge and ideas you gain from it, but for the fun you’ll have solving the problems.

;;Exercise 2.53

As usual, just a check to make sure we understand how to manipulate symbolic data.
>(list '(a b c))
(a b c)
>(list (list 'george))
((george))
>(cdr '((x1 x2) (y1 y2)))
(y1 y2)
>(cadr '((x1 x2) (y1 y2)))
y1
>(pair? (car '(a short list)))
#f
>(memq 'red '((red shoes) (blue socks)))
#f
>(memq 'red '(red shoes blue socks))
(red shoes blue socks)

;;Exercise 2.54

A fairly straightforward implementation of the recursive description they gave.

(define (my-equal? a b)
  (cond ((and (eq? a '()) (eq? b '())) true)
        ((and (symbol? a) (symbol? b))
         (eq? a b))
        ((and (pair? a) (pair? b))
         (and (my-equal? (car a) (car b))
              (my-equal? (cdr a) (cdr b))))
        (else false)))

;;Exercise 2.55

The first challenging question. Had me stumped for a while, even when I typed the code in at my interpreter I didn’t get it, however, if you notice the footnote no. 34, it explains that the interpreter replaces each use of ' with a quote. So ''abracadabra is '(quote abracadabra), and the car of that list is the symbol quote!

;;Exercise 2.56

We’ve been introduced to the differentiation program, a very nice example of abstraction. The key to this exercise is pretty much to copy what happens for the other rules, just supplying different selectors and constructors, and a bit more code in the deriv function. I’m a bit of a rebel ;) I chose to use the ‘^ symbol instead of ‘**, as ‘^ seems more intuitive to me :)

Here are the selectors, predicate, and constructors:

;;'(^ b a)
(define (exponentiation? x)
  (and (pair? x) (eq? (car x) '^)))

(define (base x)
  (cadr x))

(define (exponent x)
  (caddr x))

(define (make-exponentiation base exponent)
  (cond ((and (number? base) (number? exponent))
         (expt base exponent))
        ((=number? exponent 0) 1)
        ((=number? exponent 1) base)
        (else (list '^ base exponent))))

And here is the modified deriv function:

(define (deriv expr var)
  (cond ((number? expr) 0)
        ((variable? expr)
         (if (same-variable? expr var) 1 0))
        ((exponentiation? expr) ;;EXPONENTIATION RULE
         (make-product
           (make-product (exponent expr)
                         (make-exponentiation (base expr)
                                              (- (exponent expr) 1)))
           (deriv (base expr) var)))
        ((sum? expr)
         (make-sum (deriv (addend expr) var)
                   (deriv (augend expr) var)))
        ((product? expr)
         (make-sum
           (make-product (multiplier expr)
                         (deriv (multiplicand expr) var))
           (make-product (deriv (multiplier expr) var)
                         (multiplicand expr))))
        (else
         (error "unknown expression type -- DERIV" expr))))

And a test,
>(deriv '(^ x 4) 'x)
(* 4 (^ x 3))

;;Exercise 2.57

I had some initial difficulties with this question, I understood what I was attempting to do in the selectors, but the constructors were a little trickier. With the selectors, the only interesting bit is in the augend selector. When we get the augend, we must remember if there is a list, we need to return it as the sum of the rest of the items in the list, not a a list of two or more numbers. eg. (augend ‘(+ 1 2 3)) is (+ 2 3) not (2 3).

(define (addend s) (cadr s))

(define (augend s)
  (let ((aug (cddr s)))
    (if (eq? (cdr aug) '())
        (car aug)
        (make-sum (car aug)
                  (cdr aug)))))

The constructor also held me up for a little while, as I had a bit of a hiccup in my code.
I was not combining the augend a2 into the list (‘+ a1 a2) correctly. This is best shown with some code…
>(make-sum x (2 (* 5 y)))
(+ x (2 (* 5 y)))

As you can see, instead of combining the 2 at the same level as x, it is a separate list, (2 (* 5 y)) which the program does not know how to parse. It should of course be (+ x 2 (* 5 y)). How do we combine the lists? Using append! Here is the constructor then:

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (append (list '+ a1) a2))))

Note that we can leave all the simplification code in, it will still work even in the new format. The changes to product are almost exactly the same as the changes to sum, I feel as though there’s an underlying abstraction somewhere ;)

Here’s the full code, including the product as well as sum, remember that this is all available on my sicp github repo.

;;(+ x y z)
(define (addend s) (cadr s))

(define (augend s)
  (let ((aug (cddr s)))
    (if (eq? (cdr aug) '())
        (car aug)
        (make-sum (car aug)
                  (cdr aug)))))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (append (list '+ a1) a2))))

;;'(* x y z)
(define (multiplier p) (cadr p))

(define (multiplicand p)
  (let ((mult (cddr p)))
    (if (eq? (cdr mult) '())
        (car mult)
        (make-product (car mult)
                      (cdr mult)))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (append (list '* m1) m2))))

;;Exercise 2.58
;;Part A

Things are getting interesting, we are now getting out of the safe world of polish notation, and into the rather complex one of parsing infix expressions. However, part a is very easy to implement, it simply requires swapping the parsing of the operator and the first operand, the change is exactly the same for multiplication.

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

(define (addend s) (car s))

(define (augend s) (caddr s))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

;;Part B

Part b is simply put, a beast of a question. It most certainly is quite a difficult problem, but it’s definitely possible! In fact, I suggest you stop reading now, so that you can have the same exhiliration that I got upon solving it! We are now required to parse infix expressions with any or no parenthization. I mulled over this one for a couple days, and spent more than a few nights writing attempts to solve it in my note book. I finally hit epiphany at badminton on Thursday (6/5/10) night.

Before we do anything, we should state what we are attempting to accomplish with our code. This is a bit trickier than it sounds, so let’s go through a couple examples and see if we can find anything interesting.

(x * (6 + y) + 5) is equivalent to
((x * (6 + y)) + 5) (note the extra parenthesis before x)

So one thing we need to do is replace parentheses to make it easier to parse.

(x * (6 + y) + 5)
can be reduced like so:

addend: x * (6 + y)
      multiplier: x
      multiplicand: (6 + y)
                 addend: 6
                 augend: y
augend:

This looks like a job for recursion to me, and it also looks like we’ll need to worry about putting sums in the right place before the products. For example, if we tried to grab the multiplicand of (3 * 6 + 5) we would obtain 6 + 5 instead of 6.

We can come up with a simple recursive definition for this:

If the augend of expr is a sum, then the augend of expr is the sum of everything after the sum operator in expr (y + 3* z). If the augend of expr is a product, then the augend of expr is the product of everything after the product operator in expr. If the augend of expr is a single variable then the augend of expr is the first item after the sum operator. Finally if the augend of expr is a single number, then the augend of expr is the first item after the sum operator.

So we can see that there are four rules to apply here which will eventually filter down to the base case of the single variable or number. So, the first thing we will implement is the definition of a sum and product. An expression is a sum if it has the ‘+ operator in it, and an expression is a product if it has only the ‘* operator in it. This gives us the proper operator precedence. The in? predicate here tells whether a given symbol is in a list.

(define (sum? x)
  (and (pair? x) (in? '+ x)))

(define (product? x)
  (and (pair? x) (not (in? '+ x)) (in? '* x)))

Now that we have our definitions of what constitutes a sum, we need to give the definitions of addend and augend. The addend is everything before the first ‘+ operator, but we also need to process the addend (remember the recursive definition) to correctly resolve operator precedence in it. We will do this with the recursive process stated above as a procedure named process-expr which I will leave unspecified. Remember that black box abstraction, and wishful thinking are very important. Anyway, here’s the definition of addend and augend, split-on is a function which gives a cons where the car is everything before the symbol, and the cdr is everything after the symbol.

>(split-on '+ (1* x + 2 * y))
((1 * x) 2 y)

(define (addend s)
  (process-expr (car (split-on '+ s))))

(define (augend s)
  (process-expr (cdr (split-on '+ s))))

Now it’s almost all in place, there’s one more definition left, how do we construct a sum? This is very easy, and stays the same as what we implemented for part A, (list a1 '+ a2).

Now, to implement the process-expr procedure. Since we have already defined all the selectors and constructors, this will be very easy.

(define (process-expr expr)
  (cond ((if (= (length expr) 1) (variable? (car expr)) false) (car expr))
        ((if (= (length expr) 1) (number? (car expr)) false) (car expr))
        ((sum? expr) (make-sum (addend expr)
                               (augend expr)))
        ((product? expr) (make-product (multiplier expr)
                                       (multiplicand expr))))))

This is a beautiful example of mutual recursion, and the great thing is, that it works! I first wrote this while waiting to play at badminton, and when I tranferred it from paper, it worked first try, with just a couple hiccups. One of those hiccups was the parsing of a parenthized expression such as (3 * (5 + 4)). The augend of this expression is ((5 + 4)), which is (list (list 5 + 4)). When process-expr encounters this, it checks if it is a variable, but while the length of (list (list 5 ‘+ 4)) is 1, it will not satisfy either the variable? or the number? predicate. It will then check if it is a sum, but there is no ‘+ in (list (list 5 + 4)), and it will also check if it is a product, but it won’t satisfy that either, so the cond expression will return #void! This is a bit of a bug, but it is fairly easy to fix. Let’s think of a parenthized-expression as another type of expression. It must satisfy these requirements to be considered parethized:

  • Must have a length of 1
  • Must not be a variable
  • Must not be a number
  • It’s car must be either a sum or a product

This is readily expressed as a procedure.

(define (parenthized-expression? expr)
  (and (not (variable? expr))
       (not (number? expr))
       (= (length expr) 1)
       (or (sum? (car expr))
           (product? (car expr)))))

;;Selector
(define (deparenthize expr) (car expr))

Now, we just need to add a rule for handling parenthized-expressions to process-expr. This is accomplished by adding a let expression, which will bind expr correctly:

(define (process-expr expr)
  (let ((expr (if (parenthized-expression? expr) (deparenthize expr) expr)))
    (cond ((if (= (length expr) 1) (variable? (car expr)) false) (car expr))
          ((if (= (length expr) 1) (number? (car expr)) false) (car expr))
          ((sum? expr) (make-sum (addend expr)
                                 (augend expr)))
          ((product? expr) (make-product (multiplier expr)
                                         (multiplicand expr))))))

We’re done! We have now created a fairly useful symbolic differentiator, which can handle (almost) arbitrary expressions. There is nothing as exhilirating as solving a really tough problem, and this can definitely be ranked as one of them! Here is all the code, and remember, this code is on my sicp github repo.

Happy Hacking!

;;Split an expr on symb
(define (split-on symb expr)
  (define (iter r l)
    (cond ((eq? l '()) r)
          ((eq? symb (car l)) (cons r (cdr l)))
          (else (iter (append r (list (car l))) (cdr l)))))
  (iter '() expr))

;;Is symb in expr?
(define (in? symb expr)
  (cond ((eq? expr '()) false)
        ((eq? symb (car expr)) true)
        (else (in? symb (cdr expr)))))

;; representing algebraic expressions
(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (=number? exp num)
  (and (number? exp) (= exp num)))

;;Is expr a parenthized expression? eg. ((1 + 2))
(define (parenthized-expression? expr)
  (and (not (variable? expr))
       (not (number? expr))
       (= (length expr) 1)
       (or (sum? (car expr))
           (product? (car expr)))))

(define (process-expr expr)
  (let ((expr (if (parenthized-expression? expr) (deparenthize expr) expr)))
    (cond ((if (= (length expr) 1) (variable? (car expr)) false) (car expr))
          ((if (= (length expr) 1) (number? (car expr)) false) (car expr))
          ((sum? expr) (make-sum (addend expr)
                                 (augend expr)))
          ((product? expr) (make-product (multiplier expr)
                                         (multiplicand expr))))))

(define (deparenthize expr) (car expr))

;;'(+ x y)
(define (sum? x)
  (and (pair? x) (in? '+ x)))

(define (addend s)
  (process-expr (car (split-on '+ s))))

(define (augend s)
  (process-expr (cdr (split-on '+ s))))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

;;'(* x y)
(define (product? x)
  (and (pair? x) (not (in? '+ x)) (in? '* x)))

(define (multiplier p)
  (process-expr (car (split-on '* p))))

(define (multiplicand p)
  (process-expr (cdr (split-on '* p))))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))

(define (deriv expr var)
  (cond ((number? expr) 0)
        ((variable? expr)
         (if (same-variable? expr var) 1 0))
        ((sum? expr)
         (make-sum (deriv (addend expr) var)
                   (deriv (augend expr) var)))
        ((product? expr)
         (make-sum
           (make-product (multiplier expr)
                         (deriv (multiplicand expr) var))
           (make-product (deriv (multiplier expr) var)
                         (multiplicand expr))))
        (else
         (error "unknown expression type -- DERIV" expr))))

>(deriv '(x + 3 * (x + y + 2)) 'x)
4

Posted 09/05/2010 by Emmanuel Jacyna in SICP

Tagged with , , , , , ,

IFS for the TI-89 Titanium   Leave a comment

Being bored this morning, I decided to implement the ifs algorithm on my TI-89 graphics calculator. It was not particularly difficult, and after 23 lines of TI-BASIC, I had this image on my screen.

Yes, rather low res, I know...

The program takes a n*7 matrix, like this

Where a, b, c, and d are the elements of a 2*2 transformation matrix, e and f are elements of an offset vector, and p is the probability of the rule occuring. Note that it runs extremely slowly, I waited about ten minutes for the picture shown to be generated. I’ve added it to the repo though; in case anyone else is also bored ;)

Prgm
rand()->a
rand()->b
0->i
1000000->iters
100->s
While ic
rand()->l
While pc
r[c,7]+p->p
EndWhile
r[c,1]*a+r[c,2]*b+r[c,5]->t
r[c,3]*a+r[c,4]*b+r[c,6]->b
t->a
If i>s
PtOn a,b
1+i->i
EndWhile
EndPrgm

Posted 30/04/2010 by Emmanuel Jacyna in Humor

Tagged with , , , ,

SICP – Section 2.2.4   Leave a comment

This section is a powerful demonstration of abstraction, using a “picture language”. For this section I used the sicp package from the PLaneT repository in DrScheme. Normally, I just use mzscheme and vim, but apparently you need DrScheme open to use that particular (graphical) package. Anyway, I found it pretty enjoyable, and even made some fractals with it.

;;Exercise 2.44

They could have made this one a little tougher ;)
Telling us to flip the arguments to right-split took any challenge out of it…

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))

;;Exercise 2.45

We follow the usual patter of making abstractions.

(define (split op1 op2)
  (define (rec painter n)
    (if (= n 0)
        painter
        (let ((smaller (rec painter (- n 1))))
          (op1 painter (op2 smaller smaller)))))
  rec)

(define up-split (split below beside))
(define right-split (split beside below))

;;Exercise 2.46

Not much to it, I used a list, but a cons would do fine too, however, I decided on list, because perhaps we’ll want to add a z coordinate for 3D vectors.

(define (make-myvect x y)
  (list x y))
(define (xcor-myvect vect)
  (car vect))
(define (ycor-myvect vect)
  (cadr vect))

(define (add-myvect a b)
  (make-myvect (+ (xcor-myvect a) (xcor-myvect b))
             (+ (ycor-myvect a) (ycor-myvect b))))

(define (sub-myvect a b)
  (make-myvect (- (xcor-myvect a) (xcor-myvect b))
             (- (ycor-myvect a) (ycor-myvect b))))

(define (scale-myvect s v)
  (make-myvect (* s (xcor-myvect v))
             (* s (ycor-myvect v))))

;;Exercise 2.47

First definition

(define (make-myframe origin edge1 edge2)
  (list origin edge1 edge2))

(define (origin-myframe f) (car f))

(define (edge1-myframe f) (cadr f))

(define (edge2-myframe f) (caddr f))

Second definition

(define (make-myframe origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

(define (origin-myframe f) (car f))

(define (edge1-myframe f) (cadr f))

(define (edge2-myframe f) (cddr f))

;;Exercise 2.48

(define (make-mysegment start end) (cons start end))

(define (start-mysegment seg) (car seg))

(define (end-mysegment seg) (cdr seg))

;;Exercise 2.49


;;a.  The painter that draws the outline of the designated frame.
(define outline (segments->painter (list
  (make-segment (make-vect 0 0)
                (make-vect 0 1))
  (make-segment (make-vect 0 0)
                (make-vect 1 0))
  (make-segment (make-vect .99 0)
                (make-vect .99 1))
  (make-segment (make-vect 0 .99)
                (make-vect 1 .99)))))

;;b.  The painter that draws an ``X'' by connecting opposite corners of the frame.
(define X (segments->painter (list
  (make-segment (make-vect 0 0)
                (make-vect 1 1))
  (make-segment (make-vect 1 0)
                (make-vect 0 1)))))

;;c.  The painter that draws a diamond shape by connecting the midpoints of the sides of the frame.
(define diamond (segments->painter (list
  (make-segment (make-vect 0 .5)
                (make-vect .5 0))
  (make-segment (make-vect .5 0)
                (make-vect 1 .5))
  (make-segment (make-vect 1 .5)
                (make-vect .5 1))
  (make-segment (make-vect .5 1)
                (make-vect 0 .5)))))

;;d.  The wave painter.
(define wave (segments->painter (list
  (make-segment (make-vect 0 .84) (make-vect .13 .6))
  (make-segment (make-vect .13 .6) (make-vect .3 .66))
  (make-segment (make-vect .3 .66) (make-vect .4 .66))
  (make-segment (make-vect .4 .66) (make-vect .36 .84))
  (make-segment (make-vect .36 .84) (make-vect .4 1))
  (make-segment (make-vect .6 1) (make-vect .64 .84))
  (make-segment (make-vect .64 .84) (make-vect .6 .66))
  (make-segment (make-vect .6 .66) (make-vect .71 .66))
  (make-segment (make-vect .71 .66) (make-vect 1 .34))
  (make-segment (make-vect 1 .16) (make-vect .6 .44))
  (make-segment (make-vect .6 .44) (make-vect .74 0))
  (make-segment (make-vect .6 0) (make-vect .5 .3))
  (make-segment (make-vect .5 .3) (make-vect .4 0))
  (make-segment (make-vect .24 0) (make-vect .34 .5))
  (make-segment (make-vect .34 .5) (make-vect .3 .6))
  (make-segment (make-vect .3 .6) (make-vect .14 .4))
  (make-segment (make-vect .14 .4) (make-vect 0 .64)))))

;;Exercise 2.50
The key to figuring these out is to draw a diagram of the unit square, draw the original picture, and then draw the rotated one, and note the coordinates of the origin, edge1, and edge2.

(define (myflip-horiz painter)
  ((transform-painter (make-vect 1 0)
                      (make-vect 0 0)
                      (make-vect 1 1)) painter))

(define (rotate-90 painter)
  ((transform-painter (make-vect 1 0)
                     (make-vect 1 1)
                     (make-vect 0 0)) painter))

(define (rotate-180 painter)
  ((transform-painter (make-vect 1 1)
                      (make-vect 0 1)
                      (make-vect 1 0)) painter))

(define (rotate-270 painter)
  ((transform-painter (make-vect 0 1)
                      (make-vect 0 0)
                      (make-vect 1 1)) painter))

;;Exercise 2.51

(define (my-below painter1 painter2)
  (let ((split-point (make-vect 0 .5)))
    (let ((paint-top
           ((transform-painter split-point
                               (make-vect 1 .5)
                               (make-vect 0 1)) painter1))
          (paint-bottom
           ((transform-painter (make-vect 0 0)
                               (make-vect 1 0)
                               split-point) painter2)))
      (lambda (frame)
        (paint-top frame)
        (paint-bottom frame)))))

(define (my-below2 painter1 painter2)
  (rotate-90 (beside (rotate-270 painter1) (rotate-270 painter2))))

Okay, this has been a pretty boring article… lack of pictures, &c. However, I do have a couple pictures of some nice fractals that I generated with some functions I wrote in this picture language.

The sierpinski painter generates a sierpinski triangle with n iterations using an MRCM (Multiple Reduction Copy Machine) process. This is based on the idea from the book, Computational Beauty of Nature.

(define (sierpinski painter n)
  (if (= n 0)
      painter
            (let ((top ((transform-painter (make-vect .25 0)
                      (make-vect .75 0)
                      (make-vect .25 1))
                      painter)))
        (sierpinski (below (beside painter painter) top) (- n 1))))) 

And here it is generating it with the einstein painter.

There’s also another neat fractal, which is defined as

(define (crystal painter n)
  (if (= n 0)
      painter
            (let ((top ((transform-painter (make-vect .25 0)
                      (make-vect .75 0)
                      (make-vect .25 1))
                      painter)))
        (crystal (below (beside (rotate-90 painter)
                                   (rotate-270 painter))
                           top)
                    (- n 1))))) 

And looks like

As you can see, it’s pretty easy to define MRCM fractals using this picture language.

Posted 24/04/2010 by Emmanuel Jacyna in Code, Scheme, SICP

Tagged with , , , ,

SICP – Section 2.2.3   Leave a comment

This section had just enough challenging problems, along with just enough hints to guide me along, to make it quite fun. I did this section about two weeks ago, but, due to school starting, and some other things in my life, it’s taken a bit longer to put it up. Also, I’ve put up my solutions in a github repo for people to check out, critique, and possibly correct. Anyway, without further ado, here are my solutions.

;;Exercise 2.34

The horner-eval exercise was fairly straightforward, you just have to remember that
(...(anx + an-1) x + ... + a1) x + a0
is equivalent to
a0 + x (a1 + x( ... an-1 + x (an))...)


(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
                (+ this-coeff (* x higher-terms)))
              0
              coefficient-sequence))

;;Exercise 2.35

I felt a bit sneaky with my solution for this, my map was pretty much an identity function, it had no affect on the end result…

(define (count-leaves t)
  (accumulate (lambda (x y) (+ (if (not (pair? x)) 1 (count-leaves x)) y))
              0
              (map (lambda (x) x) t)))

;;Exercise 2.36

I had to define a couple auxiliary functions for this one, car-tree and cdr-tree take the car and cdr of the lists in a list… that is,
> (car-tree ((1 2 3) (2 3 4) (3 4 5)))
> (1 2 3)

(define (car-tree t)
  (map (lambda (l) (car l)) t))
(define (cdr-tree t)
  (map (lambda (l) (cdr l)) t))

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      '()
      (cons (accumulate op init  (map (lambda (l) (car l)) seqs))
            (accumulate-n op init (map (lambda (l) (cdr l)) seqs)))))

;;Exercise 2.37
I haven’t done much matrix and vector math, so some of my definitions may be incorrect, however, I’m pretty sure they work like they’re meant to. I’m also pretty impressed with the way these functions work so nicely. I also added a bit of error/dimensions checking, so you can’t multiply a 2×3 by a 1×4 matrix, etc.

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

(define (element r c)
  (accumulate + 0 (accumulate-n * 1 (list r c))))

(define (matrix-*-vector m v)
  (map (lambda (r) (element r v)) m))

(define (dimensions m)
  (cons (length m) (length (car m))))

(define (transpose mat)
  (accumulate-n (lambda (x y) (cons x y)) '() mat))

(define (matrix-*-matrix m n)
  (if (not (= (cdr (dimensions m)) (car (dimensions n))))
      (error "Dimension mismatch")
      (let ((cols (transpose n)))
      (map (lambda (row)
             (map (lambda (col)
                    (element col row))
                  cols))
           m))))

;;Exercise 2.38

> (fold-right / 1 (list 1 2 3))
> 3/2
> (fold-left / 1 (list 1 2 3))
> 1/6

As we can see, we get different answers, the property is fairly obvious, op must have the associative property.

;;Exercise 2.39

(define (right-reverse sequence)
  (fold-right (lambda (x y) (append y (list x))) '() sequence))

(define (left-reverse sequence)
  (fold-left (lambda (x y) (append (list y) x)) '() sequence))

Just have to flip the order in either one.

;;Exercise 2.40

(define (unique-pairs n)
  (filter (lambda (i) (not (eqv? i '())))
          (flatmap (lambda (i)
                   (map (lambda (j) (if (< j i) (list i j) '()))
                        (enumerate-interval 1 (- n 1))))
                   (enumerate-interval 1 n))))

(define (prime-sum-pairs n)
  (map make-pair-sum
       (filter prime-sum? (unique-pairs n))))

This does indeed greatly simplify the definition of prime-sum-pairs, from 8 to 3 lines.

;;Exercise 2.41

I found this one a little a little tricky, but after studying the chapter again, I got it. The key is the nested mapping, and the use of flatmap, also note the abstraction in in-order?

(define (triples n)
  (flatmap (lambda (i)
             (flatmap (lambda (j)
                    (map (lambda (k)
                           (list i j k))
                         (enumerate-interval 1 n)))
                  (enumerate-interval 1 n)))
            (enumerate-interval 1 n)))

(define (in-order? cmp l)
  (cmp (car l) (cadr l) (caddr l)))

(define (gt? l)
  (in-order? > l))

(define (ordered-triples n)
  (filter gt? (triples n)))

(define (sum-to? triple s)
  (= (in-order? + triple) s))

(define (ordered-triples-which-sum-to-s n s)
  (filter (lambda (t) (sum-to? t s)) (ordered-triples n)))

;;Exercise 2.42

I haven’t completed this one yet, I think I have the general idea, but there are some issues with my implementation.

Posted 24/04/2010 by Emmanuel Jacyna in Code, Scheme, SICP

Tagged with , ,

Using python generators   Leave a comment

I just made a generator in python.

Wow. Just, Wow.

Generators are really awesome.
I’ve been having a couple issues with my IFS algorithm, because it’s not quite as fast as I would like, and I can’t seem to do everything I want just by passing callback functions. Here’s the original algorithm:

def run_IFS(iters, skip, rules, draw_method, speak_method=None, interval = 10000):
    """Calculate the points in an iterated fractal system, drawing them with draw_method,
    and announcing results with speak_method every interval iterations."""
    probs = [r[PROB_I] for r in rules]
    rules = [r[RULE_I] for r in rules]

    x = random_float()
    y = random_float()

    while i < iters + skip
        chosen = choose_rule(probs)
        x, y = calculate_transform(x, y, rules[chosen])
        if i > skip:
            draw_method(x, y, chosen)
        #Announce the results
        if not speak_method: pass
        elif i%interval == 0:
            speak_method(x, y, i)
        i += 1

This isn’t bad code, and it’s not particularly difficult to use. I know, because it was very easy for me to add a tkinter interface in less than ten minutes. However, when I wanted to write a function to calculate the best size settings for a fractal, I found it to be rather messy:


def old_calculate_best_settings(rules, scale, iters = 10000, skip = 100):
    """Return a tuple of width and height and x_off and y_off settings
((w,h),(x_off, y_off))"""
    #note, I know this is ugly, I don't know how else to do it though
    global h_x, h_y, l_x, l_y
    h_x = h_y = l_x = l_y = 0

    def draw_method(x, y, chosen):
        global h_x, h_y, l_x, l_y
        if x*scale > h_x: h_x = x*scale
        elif x*scale < l_x: l_x = x*scale
        if y*scale > h_y: h_y = y*scale
        elif y*scale < l_y: l_y = y*scale

    run_IFS(iters, skip, rules, draw_method)
    width = int(abs(l_x)+abs(h_x))
    height = int(abs(l_y)+abs(h_y))
    x_off = int(abs(l_x))
    y_off = int(abs(l_y))

    return ((width, height), (x_off, y_off))

Yes, that’s right.

    Global Variables


Because of an interesting feature in python, it’s not possible for draw_method to change the values of h_x (and friends) without resorting to globals. This is because you can access variables from outside scope, but assigning to them makes a new local variable with the same name, which is not really what we want (thanks to bob2 from #python on freenode.net for the explanation). Of course, I could have made these variables classes, and then called some __set__ method to change their values. Purge your mind friend. The very fact that we’re thinking of such roundabout, convoluted methods is a sure sign that something is not being done right.

Enter generators

Python, of course, has a nice solution to this problem. We can see that this function is basically iterating and producing points. A possible solution would be to store the points in a list, and then iterate over these to see what the low/high points are. This is halfway there, however, when we’re talking millions of points, memory quickly becomes an issue (at least on my 486 :). Instead, we can use a generator, which behaves like a list, and makes for more “pythonic” code. Here’s a simple example:


def generate_x():
    i = 0
    while i < 10:
        print i
        yield i
        i += 1

for x in generate_x():
    print x

When you run that code (or on codepad) you can see that the prints are interleaved in the generator and the for loop, demonstrating how it works.
To change a function to a generator, we just rearrange the function a bit and make it yield rather than return the points.
Here’s the run_IFS function as a generator:


def IFS_generator(iters, skip, rules):

    probs = [r[PROB_I] for r in rules]
    rules = [r[RULE_I] for r in rules]

    x = random_float()
    y = random_float()
    i = 0

    while i < iters + skip:         chosen = choose_rule(probs)         x, y, = calculate_transform(x, y, rules[chosen])         if i > skip:
            yield (x, y, chosen)
        i += 1

That’s a lot simpler, isn’t it? We can now modify the calculate_best_settings function to use the generator:


def calculate_best_settings(rules, scale, iters = 10000, skip = 100):
    """Return a tuple of width and height and x_off and y_off settings
((w,h),(x_off, y_off))"""
    h_x = l_x = h_y = l_y = 0

    for points in IFS_generator(iters, skip, rules):
        x, y, _ = points
        if (x*scale) > h_x: h_x = x*scale
        elif (x*scale) < l_x: l_x = x*scale         if (y*scale) > h_y: h_y = y*scale
        if (y*scale) < l_y: l_y = y*scale

    width = int(abs(l_x)+abs(h_x))
    height = int(abs(l_y)+abs(h_y))
    x_off = int(abs(l_x))
    y_off = int(abs(l_y))

    return ((width, height), (x_off, y_off))

See how this is now nice, pythonic code? No more messing with global variables and callbacks. Of course, there’s also a nice speed bonus in getting rid of those callbacks.

After timing both functions, I got these results:
Old:
[4.5442321300506592, 4.4281911849975586, 4.3002359867095947] min: 4.30023598671
New:
[5.3141071796417236, 4.0443418025970459, 3.9916889667510986] min: 3.99168896675

This is a pretty significant speed up for such a small change! Note that the calculate_best_settings function only runs ~10000 iterations. When you generate a fractal with 1000000 iterations this difference becomes even greater. The code gets a boost once we’re rid of draw_method and speak_method. Of course, the next step would be to implement this function as a C extension.

Further reading:
Pep 255 – Simple Generators

Posted 19/04/2010 by Emmanuel Jacyna in Code, Python

Tagged with , , ,