# [plt-scheme] Y Combinator Exercise

 From: Matthias Felleisen (matthias at ccs.neu.edu) Date: Wed Nov 16 15:59:43 EST 2005 Previous message: [plt-scheme] Y Combinator Exercise Next message: [plt-scheme] Y Combinator Exercise Messages sorted by: [date] [thread] [subject] [author]

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
> _________________________________________________