# [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
*