Chapter 2

SICP Workshop Workshops

Started by Muhammad Haggag January 01, 2007 07:33 AM

40 comments, last by SamLowry 16 years, 9 months ago

1,865

April 10, 2007 07:37 PM

Quote:Original post by Muhammad Haggag
Quote:Original post by SamLowry
Both look ok to me (maybe you should curry your functions, but that's a detail), but you can simplify a bit.

Am I correct in assuming that your simplifications assume the functions are curried?

The "simplifications" I made make use of currying yes. The 'mul' example you quoted consists of two steps: the first step uses a rule (\xy.expr y) == (\x.expr) if expr does not contain y, the second step uses (\x.\y.body) == (\xy.body). In lambda-calculus and other languages supporting currying, this is indeed a simplification. In Scheme, I'm not so sure.

Quote:
Quote:
mul = \a b.\s z.a (b s) z
===
mul = \a b.\s.a (b s)
===
mul = \a b s.a (b s)

For some reason, I couldn't translate this to Scheme correctly. Can you give me a hand?

For my first attempt, I cheated a little bit and defined 2 macros which helped me with the currying.

(define-syntax curry  (syntax-rules ()    ((_ (x y . xs) . body)     (lambda (x)       (curry (y . xs) . body)))    ((_ (x) . body)     (lambda (x) . body)))); (call f x y); becomes; ((f x) y)(define-syntax call  (syntax-rules ()    ((_ func x y . xs)     (call (func x) y . xs))    ((_ func x)     (func x))))(define zero  (curry (s z)         z))(define succ  (curry (n s z)         (s (call n s z))))(define add  (curry (a b s z)         (call a s (call b s z))))(define mul  (curry (a b s)         (a (b s))))

Without the use of macros, it becomes

(define zero  (lambda (s)    (lambda (z)      z)))(define succ  (lambda (n)    (lambda (s)      (lambda (z)        (s ((n s) z))))))(define add  (lambda (a)    (lambda (b)      (lambda (s)        (lambda (z)          ((a s) ((b s) z)))))))(define mul  (lambda (a)    (lambda (b)      (lambda (s)        (a (b s))))))

SamLowry

1,865

April 12, 2007 08:45 AM

Regarding your solutions (Muhammad Haggag), they look fine, I didn't check them thoroughly. I very much dislike practicing the lambda calculus in Scheme, as you're doing two things simultaneously: learning to work in the lambda calculus, and writing it down in a very clumsy syntax. The latter part annoys the hell out of me.

Since the lambda calculus is very interesting to work with, I'd rather first make a small evaluator which can automatically curry functions, provides different evaluation orders (normal-order evaluation being the most important since you might need it to avoid infinite recursion) and the possibility to "recognize" values such as true, false and church numerals. Implementing recursion, data structures, etc. would be interesting exercises (going too far would be useless, as you would create the necessary abstractions to emulate something Scheme-like, and you're better off working directly with Scheme at that point).

Muhammad Haggag

1,358

Author

April 16, 2007 01:41 PM

Thanks for the explanations. I have some questions about the empty list in Scheme. What's the difference between () and (list ())?
Is the former the 'nil' element, while the latter is the empty list?

Also, I don't understand this interpreter output:

>(list 1 2 3 ())(1 2 3 ())

Shouldn't it echo (1 2 3)? It seems that (list 1 2 3 ()) is equivalent to (cons 1 (cons 2 (cons 3 (cons () ())))) rather than (cons 1 (cons 2 (cons 3 ()))).

Which brings me to this:

>(list 1 2 3 () 4 5)(1 2 3 () 4 5)

If a nil element can be found mid-list, how does it differentiate between the end-of-list marker and the one in the middle? I thought null? worked by examining the car and comparing it against (), but that's obviously not the case?

Muhammad Haggag

1,358

Author

April 16, 2007 02:04 PM

One more thing: nil doesn't seem to be defined, although the book uses it in the examples. Should I define it on my own or what? (i.e. (define nil ()) or something)

Rebooted

612

April 16, 2007 05:25 PM

Quote:Original post by Muhammad Haggag
I have some questions about the empty list in Scheme. What's the difference between () and (list ())?

The first is the empty list, the second is a list containing the empty list.

Quote:
Also, I don't understand this interpreter output:
>(list 1 2 3 ())(1 2 3 ())

This gives you a list containing 1, 2, 3 and the empty list.

Quote:
Which brings me to this:
>(list 1 2 3 () 4 5)(1 2 3 () 4 5)
If a nil element can be found mid-list, how does it differentiate between the end-of-list marker and the one in the middle?

Scheme-style lists don't work like C-style arrays.

A list is either:

the empty list, ()

a cons cell consisting of two paired values

Lists longer than two elements are created by nesting another cons cell as the second paired value. We know when a list ends because the second element of the most deeply nested cons cell is not another cons cell. If () appears somewhere in the list other than the end, it just means the value at that point is the empty list - it is not a terminator.

I hope that made sense.. I found that quite tricky to explain.

SamLowry

1,865

April 16, 2007 06:29 PM

Quote:Original post by Rebooted
Lists longer than two elements are created by nesting another cons cell as the second paired value.

I'm not sure I agree on this one. A list of 2 elements is made by using 2 cons cells, not one (I'm assuming "longer than" means >, not >=).

(list? (cons 1 2))> #f

I'm maybe just being picky at terminology, but I'd rather be pedantic than having people confused over this.

SamLowry

1,865

April 16, 2007 06:37 PM

Quote:Original post by Muhammad Haggag
Which brings me to this:
>(list 1 2 3 () 4 5)(1 2 3 () 4 5)
If a nil element can be found mid-list, how does it differentiate between the end-of-list marker and the one in the middle? I thought null? worked by examining the car and comparing it against (), but that's obviously not the case?

null? does not work on the car, as only cons cells have cars and null? works on any object (numbers, strings, ...).

(define (null? x)  (eq? x ()))

Your (1 2 3 () 4 5) example isn't a problem: the fourth element () is placed in the car of the fourth cons cell. The structure of the list looks like this:

[1, #] -> [2, #] -> [3, #] -> [(), #] -> [4, #] -> [5, #] -> ()

with # being a pointer whose destination is specified by the following ->.

You just need to differentiate between a cons cell containing () in its car, and just plain (). In order to be an end-of-list marker, the () must appear in the cdr of a cons cell, not the car. Everything in a car position is an element of the list.

Since this is important, one last example:

(define (show x)  (cond ((pair? x)         (display "CONS( car:")         (display (car x))         (display ", cdr:")         (display (cdr x))         (display " )"))        (else         (display x)))  (newline))(define (list? x)  (show x)  (or (null? x)      (and (pair? x)           (list? (cdr x)))))> (list? '(1 2 3 () 4 5))CONS( car:1, cdr:(2 3 () 4 5) )CONS( car:2, cdr:(3 () 4 5) )CONS( car:3, cdr:(() 4 5) )CONS( car:(), cdr:(4 5) )CONS( car:4, cdr:(5) )CONS( car:5, cdr:() )()#t

Rebooted

612

April 17, 2007 01:42 AM

Quote:Original post by SamLowry
Quote:Original post by Rebooted
Lists longer than two elements are created by nesting another cons cell as the second paired value.

I'm not sure I agree on this one. A list of 2 elements is made by using 2 cons cells, not one (I'm assuming "longer than" means >, not >=).

Right. The second paired element should always be another list: () if the list is finished, or a cons cell.

It's worth pointing this example out too:

> (list? (cons 1 (cons 2 ())))#t> (list? (cons 1 (cons 2 3)))#f

Muhammad Haggag

1,358

Author

April 18, 2007 05:34 AM

I see. Thanks a lot for the clarifications and examples.

Muhammad Haggag

1,358

Author

May 08, 2007 10:37 AM

For some reason, I'm not happy with my solutions to 2.27 and 2.28. They work well, but I have a nagging feeling that they're inelegant, or that there's an alternative way:

Quote:Exercise 2.27. Modify your reverse procedure of exercise 2.18 to produce a deep-reverse procedure that takes a list as argument and returns as its value the list with its elements reversed and with all sublists deep-reversed as well. For example,

>(define x (list (list 1 2) (list 3 4)))
>x
((1 2) (3 4))

>(reverse x)
((3 4) (1 2))

>(deep-reverse x)
((4 3) (2 1))

My solution:

(define (deep-reverse items)  (define (iter in out)    (if (null? in)        out        (let ((head (car in)) (tail (cdr in)))          (if (list? head)              (iter tail (cons (deep-reverse head) out))              (iter tail (cons head out))))))  (iter items ()))

Quote:Exercise 2.28. Write a procedure fringe that takes as argument a tree (represented as a list) and returns a list whose elements are all the leaves of the tree arranged in left-to-right order. For example,

>(define x (list (list 1 2) (list 3 4)))

>(fringe x)
(1 2 3 4)

>(fringe (list x x))
(1 2 3 4 1 2 3 4)

My solution:

(define (fringe tree)  (if (null? tree)      ()      (if (not (list? tree))          (list tree)          (append (fringe (car tree)) (fringe (cdr tree))))))

What do you think?

Chapter 2

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Chapter 2

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines