Register

# 5.2. Tying The Knot¶

## 5.2.1. Implementing Recursion Efficiently¶

We next consider how to implement recursive functions in SLang2. In the lambda calculus and SLang1, all functions are anonymous and cannot call themselves. We could use a fixed-point combinator, like the $Y$ combinator.

let
Y = fn (h) => (fn (x) => (h (x x)) fn (x) => (h (x x)))
f = fn (g) => fn (n) => if (n === 0) then 1 else (n * (g (n - 1)))
in
((Y f) 5)
end


What is the problem with this approach?

In SLang2, we can take advantage of references and the assignment statement to implement recursion in an efficient way with a technique called "tying the knot."

To get a sense of how this technique works, ask yourself what is the value of the following program?

let
dummyClosure = fn (n) => (n + 1)
in
let
f = fn (n) => if (n===0) then 1 else (n * (dummyClosure (n - 1)))
in
(f 5)
end
end


How can we modify this program to turn the function f above into the (recursive) function that we know under the name factorial so that the value of the program above is 120?

Hint: add a single assignment statement, but which one? and where? Answer these questions and you will see why this technique is called "tying the knot".

## 5.2.2. Practice TTK¶

This problem will help you get comfortable with the TTK technique. To earn credit for it, you must complete this randomized problem correctly three times in a row.

When you provide your answer, remember to include the full denoted values, for example [ "Num", 0 ] and not just 0.