<p>One site that I find helpful for basic examples of coding task written in a multitude of programming languages is <a href="http://rosettacode.org/wiki/Rosetta_Code" rel="nofollow noreferrer">RosettaCode</a>. While it is not always a win when going there, I still keep it high on the list of sites to check when looking for teaching examples or code that demonstrates something.</p>

<p>In this case the combination of the programming language <a href="https://en.wikipedia.org/wiki/Scheme_(programming_language)" rel="nofollow noreferrer">Scheme</a>, an example simple enough to use in a classroom and the <a href="https://en.wikipedia.org/wiki/Lambda_calculus" rel="nofollow noreferrer">Lambda Calculus</a> <a href="https://en.wikipedia.org/wiki/Fixed-point_combinator" rel="nofollow noreferrer">Y-combinator</a> are satisfied by this example:</p>

<blockquote>
  <p>Define the stateless Y combinator and use it to compute factorials and
  Fibonacci numbers from other stateless functions or lambda
  expressions.</p>
</blockquote>

<pre><code>(define Y
  (lambda (h)
    ((lambda (x) (x x))
     (lambda (g)
       (h (lambda args (apply (g g) args)))))))
 
;; head-recursive factorial
(define fac
  (Y
    (lambda (f)
      (lambda (x)
        (if (&lt; x 2)
            1
            (* x (f (- x 1))))))))
 
;; tail-recursive factorial
(define (fac2 n)
  (letrec ((tail-fac 
             (Y (lambda (f)
                  (lambda (n acc)
                    (if (zero? n)
                        acc
                        (f (- n 1) (* n acc))))))))
    (tail-fac n 1)))
 
(define fib
  (Y
    (lambda (f)
      (lambda (x)
        (if (&lt; x 2)
            x
            (+ (f (- x 1)) (f (- x 2))))))))
 
(display (fac 6))
(newline)
 
(display (fib 6))
(newline)
</code></pre>

<p>output</p>

<pre><code>720
8
</code></pre>

<p>Bonus answer:</p>

<p>When others want to learn more about Lambda Calculus the first reference I always give is <a href="http://cs.fit.edu/~ryan/library/functional_programming/gjm.lambook88.pdf" rel="nofollow noreferrer">"An Introduction to Functional Programming Through lambda Calculus"</a></p>

<p>Note: While the link is nice if you really do use the book often then please <a href="https://rads.stackoverflow.com/amzn/click/0486478831" rel="nofollow noreferrer">purchase</a> the book.</p>

CC BY-SA 3.0
2017-12-17T17:49:31.070Z
Now that I've seen your writeup, are you saying that the lab activity is, itself, to create `fib` and `fac`?
Ben I.
CC BY-SA 3.0
2017-12-17T17:57:00.877Z
Yes. The activity would be first to create the Y combinator, then to verify that it works one could write `fib` and/or `fac`. I also find that reading the book noted is a gentler way to learning what is going on and why. While I don't know your end goal with Lambda Calculus. If I were teaching a class on it I would keep one of the goals being to understand [System F](https://en.wikipedia.org/wiki/System_F) which is the basis for a lot of functional languages and language research.
Guy Coder
CC BY-SA 3.0
2017-12-17T01:02:44.040Z
2017-12-17T17:46:37.307Z
2017-12-17T17:46:37.307Z
Guy Coder
<p>We are about to study the y-combinator as a culmination of lambda calculus, and I would like a shortish lab activity that is related to this idea.  We are currently working in Scheme, though I don't consider that to be important at this stage.  What I want (and what I lack) is something interesting that students can <em>do</em> with the concept of a lambda expression that takes itself and then acts recursively.</p>

CC BY-SA 3.0
2017-12-04T21:34:16.797Z
An example that seems to work is here: http://www.viksit.com/tags/clojure/practical-applications-y-combinator-clojure/
Buffy
CC BY-SA 3.0
2017-12-14T20:48:19.977Z
Does this help: RosettaCode Y-Combinator [Scheme](https://rosettacode.org/wiki/Y_combinator#Scheme) ? If so I can make it an answer.
Guy Coder
CC BY-SA 3.0
2017-12-16T21:06:33.523Z
@GuyCoder It certainly helps.
Ben I.
CC BY-SA 3.0
2017-12-16T21:11:52.487Z
@Buffy The memoization example there is amazing. I'm still trying to make sense of it.
Ben I.
<labs><lambda-expressions>
A lab activity for the Y-Combinator
# A lab activity for the Y-Combinator

(Asked by: username_0 on 2017-12-04)

We are about to study the y-combinator as a culmination of lambda calculus, and I would like a shortish lab activity that is related to this idea. We are currently working in Scheme, though I don't consider that to be important at this stage. What I want (and what I lack) is something interesting that students can *do* with the concept of a lambda expression that takes itself and then acts recursively.

**Tags:** labs, lambda-expressions

> **Comments:**
> **username_1**: An example that seems to work is here: http://www.viksit.com/tags/clojure/practical-applications-y-combinator-clojure/  
> **username_2**: Does this help: RosettaCode Y-Combinator [Scheme](https://rosettacode.org/wiki/Y_combinator#Scheme) ? If so I can make it an answer.  
> **username_0**: @GuyCoder It certainly helps.  
> **username_0**: @username_1 The memoization example there is amazing. I'm still trying to make sense of it.  

---

## 1 answers

### Answer by username_2 on 2017-12-17. Score: 4

One site that I find helpful for basic examples of coding task written in a multitude of programming languages is RosettaCode. While it is not always a win when going there, I still keep it high on the list of sites to check when looking for teaching examples or code that demonstrates something.
In this case the combination of the programming language Scheme, an example simple enough to use in a classroom and the Lambda Calculus Y-combinator are satisfied by this example:

Define the stateless Y combinator and use it to compute factorials and
  Fibonacci numbers from other stateless functions or lambda
  expressions.

(define Y
  (lambda (h)
    ((lambda (x) (x x))
     (lambda (g)
       (h (lambda args (apply (g g) args)))))))
 
;; head-recursive factorial
(define fac
  (Y
    (lambda (f)
      (lambda (x)
        (if (< x 2)
            1
            (* x (f (- x 1))))))))
 
;; tail-recursive factorial
(define (fac2 n)
  (letrec ((tail-fac 
             (Y (lambda (f)
                  (lambda (n acc)
                    (if (zero? n)
                        acc
                        (f (- n 1) (* n acc))))))))
    (tail-fac n 1)))
 
(define fib
  (Y
    (lambda (f)
      (lambda (x)
        (if (< x 2)
            x
            (+ (f (- x 1)) (f (- x 2))))))))
 
(display (fac 6))
(newline)
 
(display (fib 6))
(newline)

output
720
8

Bonus answer:
When others want to learn more about Lambda Calculus the first reference I always give is "An Introduction to Functional Programming Through lambda Calculus"
Note: While the link is nice if you really do use the book often then please purchase the book.

> **Comments:**
> **username_0**: Now that I've seen your writeup, are you saying that the lab activity is, itself, to create `fib` and `fac`?  
> **username_2**: Yes. The activity would be first to create the Y combinator, then to verify that it works one could write `fib` and/or `fac`. I also find that reading the book noted is a gentler way to learning what is going on and why. While I don't know your end goal with Lambda Calculus. If I were teaching a class on it I would keep one of the goals being to understand [System F](https://en.wikipedia.org/wiki/System_F) which is the basis for a lot of functional languages and language research.  

---

