Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-17T17:49:31.070Z
Answers.Text: Now that I've seen your writeup, are you saying that the lab activity is, itself, to create `fib` and `fac`?
Answers.UserDisplayName: Ben I.
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-17T17:57:00.877Z
Answers.Text: 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.
Answers.UserDisplayName: Guy Coder
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-17T01:02:44.040Z
Answers.LastActivityDate: 2017-12-17T17:46:37.307Z
Answers.LastEditDate: 2017-12-17T17:46:37.307Z
Answers.UserDisplayName: Guy Coder
Body: <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>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-04T21:34:16.797Z
Comments.Text: An example that seems to work is here: http://www.viksit.com/tags/clojure/practical-applications-y-combinator-clojure/
Comments.UserDisplayName: Buffy
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-14T20:48:19.977Z
Comments.Text: Does this help: RosettaCode Y-Combinator [Scheme](https://rosettacode.org/wiki/Y_combinator#Scheme) ? If so I can make it an answer.
Comments.UserDisplayName: Guy Coder
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-16T21:06:33.523Z
Comments.Text: @GuyCoder It certainly helps.
Comments.UserDisplayName: Ben I.
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-16T21:11:52.487Z
Comments.Text: @Buffy The memoization example there is amazing. I'm still trying to make sense of it.
Comments.UserDisplayName: Ben I.
Tags: <labs><lambda-expressions>
Title: A lab activity for the Y-Combinator
ThreadText: # 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**: @username_2 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](http://rosettacode.org/wiki/Rosetta_Code). 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](https://en.wikipedia.org/wiki/Scheme_(programming_language)), an example simple enough to use in a classroom and the [Lambda Calculus](https://en.wikipedia.org/wiki/Lambda_calculus) [Y-combinator](https://en.wikipedia.org/wiki/Fixed-point_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"](http://cs.fit.edu/~ryan/library/functional_programming/gjm.lambook88.pdf)
  
  Note: While the link is nice if you really do use the book often then please [purchase](https://rads.stackoverflow.com/amzn/click/0486478831) 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.  
  
  ---
  
  