[plt-scheme] Y Combinator Exercise

In the monograph on reduction semantics [Felleisen & Flatt], we had 
some sample calculations using the Y combinator along the lines of what 
John points out. Use reductions to show ((Y mk-!) 2) is 2. Then show 
them that the fixpoint equation helps. Reprove the first one and wow it 
all gets easier. Then show them that you need a calculus (=) and that 
reductions (->) are no longer enough for this. Puzzle: can you design a 
cbv Y-like combinator that doesn't use 'backwards' reductions. -- 
Matthias


On Nov 16, 2005, at 5:02 AM, Paulo Jorge Matos wrote:

> Hi all,
>
> Although some nice things about Scheme are not taught in our
> Programming Fundamentals Course I've written some 'harder/research'
> exercises to introduce them to some nice concepts which I make
> available online during the semester. I've already sone some for
> call/cc, the use of very basic operations to define some scheme
> implementation code, webpages and I'd like to write something about
> the Y Combinator but I'm missing ideas for an exercise where they
> could apply the concept of Y Combinator. It should not be too easy but
> also not too hard since this should be for them to grasp by themselves
> this concept. First I though about giving them an introduction to the
> Y combinator and then to ask them to solve the problem of the Towers
> of Hanoi for 8 discs for example by writing recursive definitions
> using the Y combinator.
>
> But I would like to know if someone has any other suggestion.
>
> Thanks a lot,
> --
> Paulo Jorge Matos - pocm at sat inesc-id pt
> Web: http://sat.inesc-id.pt/~pocm
> Computer and Software Engineering
> INESC-ID - SAT Group
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme