lambdaway :: Y

lambdaway :: Y_en2

6 | list | login |load

| |

;;{toggle} 
{toggle2}

_h2 florilège | [[recursion|?view=divine_recursion]]

{{block}
_h2 introduction

{center « {b To understand recursion, you must understand recursion.} »}

_p In this paper we will explore {b recursion, 2 fixed-point combinators & IIFEs}.

_p Let's start from the beginning.

_p Words are essential in a programming language. Coding is a matter of playing with words, building structures made of words, called {b data structures}, and the first of them are {b pairs}. A pair is defined as an ordered set of two words. This is how, in lambdatalk, we create a pair, bind it to a word - its name - acces to its elements and test if a word is a pair or not.

{pre
'{def HW {P.new hello world}} -> {def HW {P.new hello world}}

'{P.left {HW}}    -> {P.left {HW}}
'{P.right {HW}}   -> {P.right {HW}}

'{P.pair? {HW}}   -> {P.pair? {HW}}
'{P.pair? nil}    -> {P.pair? nil}  // nil or any word
}

_p Pairs are powerful tools to build more complex structures, for instance {b lists}. A list is a pair whose left term is a word and the right term is a pair or any terminal word, chosen to be {b nil} for historical reasons.

{pre
'{def HBNW
 {P.new hello
  {P.new brave
   {P.new new
    {P.new world 
           nil}}}}}
-> {def HBNW
 {P.new hello
  {P.new brave
   {P.new new
    {P.new world nil}}}}}
}

_p {i Recursion occurs when a thing is defined in terms of itself}. Obviously, such a list, a pair made of words and pairs which are sub-lists, is a first example of {b recursive data structure}.

_p Because a list is first of all a pair we can acces its terms

{pre
'{P.left {HBNW}} -> {P.left {HBNW}}
'{P.left {P.right {HBNW}}} -> {P.left {P.right {HBNW}}}
'{P.left {P.right {P.right {HBNW}}}} -> {P.left {P.right {P.right {HBNW}}}}
'{P.left {P.right {P.right {P.right {HBNW}}}}} -> {P.left {P.right {P.right {P.right {HBNW}}}}}
'{P.left {P.right {P.right {P.right {P.right {HBNW}}}}}} -> {P.left {P.right {P.right {P.right {P.right {HBNW}}}}}}
}

_p At each step the rest of the list decreases until the last term, {b nil}. Testing each sub-list

{pre
'{P.pair? {HBNW}} -> {P.pair? {HBNW}}
'{P.pair? {P.right {HBNW}}} -> {P.pair? {P.right {HBNW}}}
'{P.pair? {P.right {P.right {HBNW}}}} -> {P.pair? {P.right {P.right {HBNW}}}}
'{P.pair? {P.right {P.right {P.right {HBNW}}}}} -> {P.pair? {P.right {P.right {P.right {HBNW}}}}}
'{P.pair? {P.right {P.right {P.right {P.right {HBNW}}}}}} -> {P.pair? {P.right {P.right {P.right {P.right {HBNW}}}}}}
}

_p reveals a {b recursive process} which can be summarized in a function

{pre
'{def DISP 
 {lambda {:list}
  {if {P.pair? :list}           // if it's a pair
   then {P.left :list}          // then display left term
        {DISP {P.right :list}}  // do it on right term
   else                         // else stop
}}}
-> {def DISP 
 {lambda {:list}
  {if {P.pair? :list}
   then {P.left :list}
        {DISP {P.right :list}}
   else 
}}}

'{DISP {HBNW}}
-> {DISP {HBNW}}
}

_p We notice that the {b DISP} function {b calls itself}, in its body. We just have built our first {b recursive function} displaying a recursive data structure.

_p Recursion is a great tool used everywhere in programming languages. Any iterative process can be expressed as a recursive function.

_p But recursion is marked by an original sin.

_p Let's go back again to the begining and remember the introduction of lambdatalk given in [[coding]]. Consider for instance the genesis of the {b SWAP} function. It begins with a text rewriting process
{pre 
{b replace} :a & :b 
     {b in} the sequence :b :a 
     {b by} hello & world
}

_p translated in lambdatalk as a prefixed parenthesized expression

{pre
'{{lambda {:a :b} 
          :b :a 
        } hello world}

-> {{lambda {:a :b} :b :a} hello world}
}

_p The technical name of such a text rewriting process is {b IIFE}, {code {b I}mmediately {b I}nvoked {b F}unction {b E}xpression}. Simply said it's an {b anonymous function} defined and immediately applied to some value. We have seen that, in order to make code more readable, we were quickly led to split an {b IIFE} into two steps, 1) first give a name to the function, 2) then {b apply} it to some value. Here

{pre
'{def SWAP {lambda {:a :b} :b :a}}
-> {def SWAP {lambda {:a :b} :b :a}}

'{SWAP hello world}
-> {SWAP hello world}
}

_p Any IIFE can be splitted into a function and an application. But is the reverse always possible ? Can we build the IIFE which a recursive function comes from? Can we build anonymous recursive functions? Can we write recursive processes as text rewriting processes?

_p And the first answer is {b No, we can't!} 
}

{{block}
_h2 combinators

_p The second answer is « {b Yes we can, using combinators!} »

_p Lambda-calculus was invented in the 30s as a formal system for text rewriting built on a reduced set of 3 rules and a basic process

{pre
x := w
  | λw.x
  | x x

λw.x w 
-> w         // called β-reduction
}

_p which can be translated in lambdatalk as

{pre
expression := word
           | '{lambda {words} expression}
           | '{expression expression}

'{{lambda {words} expression} words} 
-> words     // called IIFE
}

_p Thanks to this formalism it became possible to define a bunch of useful data structures and functions. For instance {b booleans} and {b pairs}

{pre
'{def TRUE {lambda {:a :b} :a}}
'{def FALSE {lambda {:a :b} :b}}

'{def PAIR {lambda {:a :b :c} {:c :a :b}}}
'{def LEFT {lambda {:c} {:c TRUE}}}
'{def RIGHT {lambda {:c} {:c FALSE}}}
}

_p See [[coding]] for a complete introduction. The thing to note is that names are {b always optional}, a facility introduced to write and read more easily deep combinations of expressions. But not in the case of a recursive function, which calls itself and needs to be named. The workaround was found in "strange" expressions named {b fixed-point combinators}.

_h3 Y

_p The best kown fixed-point combinator is the {b Y-combinator} defined in lambda-calculus.

{pre
Y := λf. (λx. f (x x)) (λx. f (x x))  
}

_p As rarely precised the lambda-calculus is supposed to be supporting lazy evaluation. But in a strict programming language, like lambdatalk, the Y combinator will expand until stack overflow, or never halt in case of tail call optimization. So a Z combinator was built to work in strict languages (also called eager languages, where applicative evaluation order is applied).

{pre 
Z := λf.(λx.f(λv.xxv)) (λx.f(λv.xxv)) 
}

_p and this could be its close translation in lambdatalk, renamed {b Y}
 
{pre
'{def Y
 {lambda {:f}
  {{lambda {:x} {:f {lambda {:v} {{:x :x} :v}}}}
   {lambda {:x} {:f {lambda {:v} {{:x :x} :v}}}}}}} 
}

_p But in lambdatalk functions are not implemented as closures, they {b can't} have free variables. Happily lambdatalk's functions accept partial application and the lack of closures can be circumvented using IIFEs.

{pre
'{def Y
 {lambda {:f}
  {{{lambda {:f :x}
            {:f {{lambda {:x :v} {{:x :x} :v}} :x}}} :f} 
   {{lambda {:f :x}
            {:f {{lambda {:x :v} {{:x :x} :v}} :x}}} :f}}}} 
-> {def Y
 {lambda {:f}
  {{{lambda {:f :x} {:f {{lambda {:x :v} {{:x :x} :v}} :x}}} :f} 
   {{lambda {:f :x} {:f {{lambda {:x :v} {{:x :x} :v}} :x}}} :f}}}}
}

_p Let's now rewrite the {b DISP} function, replacing the {b DISP} global reference by a local {b :f} reference

{pre
'{def DISP1 
 {lambda {:f :l}
  {if {not {P.pair? :l}}
   then 
   else {P.left :l}
        {:f {P.right :l}}}}}  // DISP replaced by :f
-> {def DISP1 
 {lambda {:f :l}
  {if {not {P.pair? :l}}
   then 
   else {P.left :l}
        {:f {P.right :l}}}}}

'{{Y DISP1} {HBNW}} 
-> {{Y DISP1} {HBNW}} 
}

_p We have replaced the {b DISP} recursive function by a new one, {b DISP1}, which could be seen as an "almost-recursive" function helped by the Y combinator acting as bridge.

_p Could it be any simpler?

_h3 Ω

_p Let explore another combinator, much simpler, simply applying a function to itself, summing up the whole recursive process in a nutshell. This combinator is defined in lambda-calculus like this

{pre
Ω := λf. f f
}

_p and easily translated in lambdatalk

{pre
'{def Ω {lambda {:f} {:f :f}}}
-> {def Ω {lambda {:f} {:f :f}}}
}

_p Let's rewrite the {b DISP} function, replacing the {b DISP} global reference by a {b double local reference}

{pre
'{def DISP2 
 {lambda {:f :l}
  {if {not {P.pair? :l}}
   then 
   else {P.left :l}
        {:f :f {P.right :l}}}}}  // DISP replaced by :f :f
-> {def DISP2 
 {lambda {:f :l}
  {if {not {P.pair? :l}}
   then 
   else {P.left :l}
        {:f :f {P.right :l}}}}}

'{{Ω DISP2} {HBNW}}
-> {{Ω DISP2} {HBNW}}
}

_p We can see that the so simple {b Ω-combinator} works as well as the so complex {b Y-combinator} with a small extra-cost, doubling the local reference in the almost-recursive function's body. My question is :

_p {b Why is the Y-combinator prefered to the Ω-combinator?}

_h3 IIFE

_p Using either {b Y} or {b Ω} we can now write a recursive function which doesn't call itself, and so we can forget its name and buid an {b IIFE}.

{pre
'{{{lambda {:f} {:f :f}}
 {lambda {:f :l}
  {if {not {P.pair? :l}}
   then 
   else {P.left :l}
        {:f :f {P.right :l}}}}}
 {P.new hello
  {P.new brave
   {P.new new
    {P.new world nil}}}}}

-> {{{lambda {:f} {:f :f}}
 {lambda {:f :l}
  {if {not {P.pair? :l}}
   then 
   else {P.left :l}
        {:f :f {P.right :l}}}}}
 {P.new hello
  {P.new brave
   {P.new new
    {P.new world nil}}}}}
}

_p This IIFE uses exclusively the pair data structure. The page [[coding]] shows how it's possible to go down to the lambda-calculus level, forgetting the {b if then else} control structure, using nothing but lambdas, the level of pure text rewriting.

_p In the following we play with other recursive algorithms:

_ul the factorial, a simple recursive function
_ul fibonacci numbers, a doubly recursive function
_ul gcd (greatest common divisor), a simple recursive function
_ul the Towers of Hanoï, a doubly recursive function 
_ul the Hilbert curve, two mutually recursive functions,

_p resulting each time in an IIFE and demonstrating that everything can be reduced to a simple text rewriting.
}

{{block}

_h2 factorial

_p The factorial of a natural number {b n} is defined as {b fac(n) = n*(n-1)*...*2*1} and translated into this recursive algorithm

{pre
fac(1) = 1
fac(n) = n*fac(n-1)
}
 
_p Here is the lambdatalk code

{pre
'{def fac
 {lambda {:n}
  {if {= :n 1}
   then 1
   else {* :n {fac {- :n 1}}}}}}
-> {def fac
 {lambda {:n}
  {if {= :n 1}
   then 1
   else {* :n {fac {- :n 1}}}}}}

'{fac 6}
-> {fac 6}
}

_h3 Y

{pre
'{def fac1  
 {lambda {:f :n}
  {if {= :n 1}
   then 1
   else {* :n {:f {- :n 1}}} }}}
-> {def fac1  
 {lambda {:f :n}
  {if {= :n 1}
   then 1
   else {* :n {:f {- :n 1}}} }}}

'{{Y fac1} 6}
-> {{Y fac1} 6}
}

_h3 Ω

{pre
'{def fac2  
 {lambda {:f :n}
  {if {= :n 1}
   then 1
   else {* :n {:f :f {- :n 1}}} }}}
-> {def fac2  
 {lambda {:f :n}
  {if {= :n 1}
   then 1
   else {* :n {:f :f {- :n 1}}} }}}

'{{Ω fac2} 6}
-> {{Ω fac2} 6}
}

_h3 IIFE

{prewrap
'{{{lambda {:f} {:f :f}}  
 {lambda {:f :n}
  {if {= :n 1}
   then 1
   else {long_mult :n {:f :f {- :n 1}}} }}} 100}
-> {{{lambda {:f} {:f :f}}  
 {lambda {:f :n}
  {if {= :n 1}
   then 1
   else {long_mult :n {:f :f {- :n 1}}} }}} 100}
}
_p just replacing {b *} by {b long_mult} to compute the exact value of {b fac(100)}.
}

{{block}
_h2 fibonacci

_p The fibonacci number of a natural number {b n} is defined as a doubly recursive algorithm

{pre 
fibo(0) = 0
fibo(1) = 1
fibo(n) = fibo(n-1) + fibo(n-2)
}

_p Here we will use the tail-recursive version

{pre
'{def fibo
 {lambda {:a :b :n} 
  {if {= :n 0}
   then :a
   else {fibo :b {+ :a :b} {- :n 1}}}}}
-> {def fibo
 {lambda {:a :b :n} 
  {if {= :n 0}
   then :a
   else {fibo :b {+ :a :b} {- :n 1}}}}}

'{fibo 0 1 10}
-> {fibo 0 1 10}
}

_h3 Y

{pre
'{def fibo1
 {lambda {:f :a :b :n} 
  {if {= :n 0}
   then :a
   else {:f :b {+ :a :b} {- :n 1}}}}}
-> {def fibo1
 {lambda {:f :a :b :n} 
  {if {= :n 0}
   then :a
   else {:f :b {+ :a :b} {- :n 1}}}}}

'{{Y fibo1} 0 1 10}
-> {{Y fibo1} 0 1 10}
}

_h3 Ω

{pre
'{def fibo2
 {lambda {:f :a :b :n} 
  {if {= :n 0}
   then :a
   else {:f :f :b {+ :a :b} {- :n 1}}}}}
-> {def fibo2
 {lambda {:f :a :b :n} 
  {if {= :n 0}
   then :a
   else {:f :f :b {+ :a :b} {- :n 1}}}}}

'{{Ω fibo2} 0 1 10}
-> {{Ω fibo2} 0 1 10}
}

_h3 IIFE

{pre
'{{{lambda {:f} {:f :f}}
 {lambda {:f :a :b :n} 
  {if {= :n 0}
   then :a
   else {:f :f :b {long_add :a :b} {- :n 1}}}}} 0 1 100}
-> {{{lambda {:f} {:f :f}}
 {lambda {:f :a :b :n} 
  {if {= :n 0}
   then :a
   else {:f :f :b {long_add :a :b} {- :n 1}}}}} 0 1 100} 
}

_p just replacing {b +} by {b long_add} to compute the exact value of fibo(100). 
;; 354,224,848,179,261,915,075
}

{{block}
_h2 gcd

_p The greatest common divisor of two numbers is recursively defined as

{pre
gcd(a,0) = a
gcd(a,b) = gcd(b,a%b)
}

_p and translated as

{pre
'{def gcd
 {lambda {:a :b}
  {if {= :b 0}
   then :a
   else {gcd :b {% :a :b}}}}}
-> {def gcd
 {lambda {:a :b}
  {if {= :b 0}
   then :a
   else {gcd :b {% :a :b}}}}}

'{gcd 54321 12345}
-> {gcd 54321 12345} 
}

_h3 Y

{pre
'{def gcd1
 {lambda {:f :a :b}
  {if {= :b 0}
   then :a
   else {:f :b {% :a :b}}}}}
-> {def gcd1
 {lambda {:f :a :b}
  {if {= :b 0}
   then :a
   else {:f :b {% :a :b}}}}}

'{{Y gcd1} 54321 12345}
-> {{Y gcd1} 54321 12345}
}

_h3 Ω

{pre
'{def gcd2
 {lambda {:f :a :b}
  {if {= :b 0}
   then :a
   else {:f :f :b {% :a :b}}}}}
-> {def gcd2
 {lambda {:f :a :b}
  {if {= :b 0}
   then :a
   else {:f :f :b {% :a :b}}}}}

'{{Ω gcd2} 54321 12345}
-> {{Ω gcd2} 54321 12345}
}

_h3 IIFE

{pre
'{{{lambda {:f} {:f :f}}
{lambda {:f :a :b}
  {if {= :b 0}
   then :a
   else {:f :f :b {% :a :b}}}}
} 54321 12345}
-> {{{lambda {:f} {:f :f}}
{lambda {:f :a :b}
  {if {= :b 0}
   then :a
   else {:f :f :b {% :a :b}}}}
} 54321 12345}
}
}

{{block}
_h2 hanoi

_p Explanations on the Towers of Hanoï are given in this page [[hanoi]]. The algorithm is given by this pseudo-code

{pre
move hanoi(n) from A to B via C
  if n = 0
  then stop
  else move hanoi(n-1) from A to C
       move disk n     from A to B
       move hanoi(n-1) from C to B
}

_p translated into a doubly recursive function

{pre
'{def hanoi
 {lambda {:from :to :via :n}
  {if {= :n 0}
   then 
   else {hanoi :from :via :to {- :n 1}}
        {br}move :n from :from to :to 
        {hanoi :from :via :to {- :n 1}}}}}
-> {def hanoi
 {lambda {:from :to :via :n}
  {if {= :n 0}
   then 
   else {hanoi :from :via :to {- :n 1}}
        {div}move :n from :from to :to 
        {hanoi :from :via :to {- :n 1}}}}}

'{hanoi A B C 3}
-> {hanoi A B C 3}
}

_h3 Y

{pre
'{def hanoi1
 {lambda {:g :from :to :via :n}
  {if {= :n 0}
   then 
   else {:g :from :via :to {- :n 1}}
        {br}move :n from :from to :to 
        {:g :from :via :to {- :n 1}}}}}
-> {def hanoi1
 {lambda {:g :from :to :via :n}
  {if {= :n 0}
   then 
   else {:g :from :via :to {- :n 1}}
        {div}move :n from :from to :to 
        {:g :from :via :to {- :n 1}}}}}

'{{Y hanoi1} A B C 3}
-> {{Y hanoi1} A B C 3}
}

_h3 Ω

{pre
'{def hanoi2
 {lambda {:g :from :to :via :n}
  {if {= :n 0}
   then 
   else {:g :g :from :via :to {- :n 1}}
        {br}move :n from :from to :to 
        {:g :g :from :via :to {- :n 1}}}}}
-> {def hanoi2
 {lambda {:g :from :to :via :n}
  {if {= :n 0}
   then 
   else {:g :g :from :via :to {- :n 1}}
        {div}move :n from :from to :to 
        {:g :g :from :via :to {- :n 1}}}}}

'{{Ω hanoi2} A B C 3}
-> {{Ω hanoi2} A B C 3}
}

_h3 IIFE

{pre
'{{{lambda {:f} {:f :f}}
 {lambda {:g :from :to :via :n}
  {if {= :n 0}
   then 
   else {:g :g :from :via :to {- :n 1}}
        {br}move :n from :from to :to 
        {:g :g :from :via :to {- :n 1}}}}} A B C 6}
-> {{{lambda {:f} {:f :f}}
 {lambda {:g :from :to :via :n}
  {if {= :n 0}
   then 
   else {:g :g :from :via :to {- :n 1}}
        {div}move :n from :from to :to 
        {:g :g :from :via :to {- :n 1}}}}} A B C 6}
}
}

{{block}
_h2 hilbert

_p The Hilbert curve is drawn using two mutually recursive functions

{prewrap
'{def hilbert.left
 {lambda {:d :n}
 {if {< :n 1}
   then
   else T90      {hilbert.right :d {- :n 1}}
        M:d T-90 {hilbert.left  :d {- :n 1}}
        M:d      {hilbert.left  :d {- :n 1}}
        T-90 M:d {hilbert.right :d {- :n 1}}
        T90}}}
-> {def hilbert.left {lambda {:d :n}
 {if {< :n 1}
   then
   else T90      {hilbert.right :d {- :n 1}}
        M:d T-90 {hilbert.left  :d {- :n 1}}
        M:d      {hilbert.left  :d {- :n 1}}
        T-90 M:d {hilbert.right :d {- :n 1}}
        T90}}}

'{def hilbert.right
 {lambda {:d :n}
 {if {< :n 1}
   then
   else T-90    {hilbert.left  :d {- :n 1}}
        M:d T90 {hilbert.right :d {- :n 1}}
        M:d     {hilbert.right :d {- :n 1}}
        T90 M:d {hilbert.left  :d {- :n 1}}
        T-90}}}
-> {def hilbert.right {lambda {:d :n}
 {if {< :n 1}
   then
   else T-90    {hilbert.left  :d {- :n 1}}
        M:d T90 {hilbert.right :d {- :n 1}}
        M:d     {hilbert.right :d {- :n 1}}
        T90 M:d {hilbert.left  :d {- :n 1}}
        T-90}}}

'{hilbert.left 10 2}
-> {hilbert.left 10 2}
}

_p where {b T90} means "rotate +90 degrees" and {b M10} means "move 10 pixels". Given to a graphic device it draws a [[Hilbert curve|?view=hilbert]] at a level of recursion equal to 2.

_h3 Y

{prewrap
'{def hilbert1.left
 {lambda {:f :d :n}
 {if {< :n 1}
   then
   else T90      {{Y hilbert1.right} :d {- :n 1}}
        M:d T-90 {:f  :d {- :n 1}}
        M:d      {:f  :d {- :n 1}}
        T-90 M:d {{Y hilbert1.right} :d {- :n 1}}
        T90}}}
-> {def hilbert1.left
 {lambda {:f :d :n}
 {if {< :n 1}
   then
   else T90      {{Y hilbert1.right} :d {- :n 1}}
        M:d T-90 {:f  :d {- :n 1}}
        M:d      {:f  :d {- :n 1}}
        T-90 M:d {{Y hilbert1.right} :d {- :n 1}}
        T90}}}

'{def hilbert1.right
 {lambda {:f :d :n}
 {if {< :n 1}
   then
   else T-90    {{Y hilbert1.left} :d {- :n 1}}
        M:d T90 {:f :d {- :n 1}}
        M:d     {:f :d {- :n 1}}
        T90 M:d {{Y hilbert1.left} :d {- :n 1}}
        T-90}}}
-> {def hilbert1.right
 {lambda {:f :d :n}
 {if {< :n 1}
   then
   else T-90    {{Y hilbert1.left} :d {- :n 1}}
        M:d T90 {:f :d {- :n 1}}
        M:d     {:f :d {- :n 1}}
        T90 M:d {{Y hilbert1.left} :d {- :n 1}}
        T-90}}}

'{{Y hilbert1.left} 10 2}
-> {{Y hilbert1.left} 10 2} 
}

_h3 Ω
{prewrap
'{def hilbert2.left
 {lambda {:f :d :n}
 {if {< :n 1}
   then
   else T90      {{Ω hilbert2.right} :d {- :n 1}}
        M:d T-90 {:f :f :d {- :n 1}}
        M:d      {:f :f :d {- :n 1}}
        T-90 M:d {{Ω hilbert2.right} :d {- :n 1}}
        T90}}}
-> {def hilbert2.left
 {lambda {:f :d :n}
 {if {< :n 1}
   then
   else T90      {{Ω hilbert2.right} :d {- :n 1}}
        M:d T-90 {:f :f :d {- :n 1}}
        M:d      {:f :f :d {- :n 1}}
        T-90 M:d {{Ω hilbert2.right} :d {- :n 1}}
        T90}}}

'{def hilbert2.right
 {lambda {:f :d :n}
 {if {< :n 1}
   then
   else T-90    {{Ω hilbert2.left} :d {- :n 1}}
        M:d T90 {:f :f :d {- :n 1}}
        M:d     {:f :f :d {- :n 1}}
        T90 M:d {{Ω hilbert2.left} :d {- :n 1}}
        T-90}}}
-> {def hilbert2.right
 {lambda {:f :d :n}
 {if {< :n 1}
   then
   else T-90    {{Ω hilbert2.left} :d {- :n 1}}
        M:d T90 {:f :f :d {- :n 1}}
        M:d     {:f :f :d {- :n 1}}
        T90 M:d {{Ω hilbert2.left} :d {- :n 1}}
        T-90}}}

'{{Ω hilbert2.left} 10 2}
-> {{Ω hilbert2.left} 10 2}  
}

_h3 IIFE

{prewrap
'{{{lambda {:f} {:f :f}}
 {lambda {:g :d :n}
  {if {< :n 1} then else T90      
{{{lambda {:f} {:f :f}} 
 {lambda {:g :d :n}
  {if {< :n 1} then else T-90    
{{{lambda {:f} {:f :f}} :g} :d {- :n 1}}
        M:d T90 {:g :g :d {- :n 1}}
        M:d     {:g :g :d {- :n 1}}
        T90 M:d 
{{{lambda {:f} {:f :f}} :g} :d {- :n 1}}
        T-90}}} :d {- :n 1}}
        M:d T-90 {:g :g :d {- :n 1}}
        M:d      {:g :g :d {- :n 1}}
        T-90 M:d 
{{{lambda {:f} {:f :f}} 
 {lambda {:g :d :n}
  {if {< :n 1} then else T-90    
{{{lambda {:f} {:f :f}} :g} :d {- :n 1}}
        M:d T90 {:g :g :d {- :n 1}}
        M:d     {:g :g :d {- :n 1}}
        T90 M:d 
{{{lambda {:f} {:f :f}} :g} :d {- :n 1}}
        T-90}}} :d {- :n 1}}
        T90}}} 
10 2}    
-> {{{lambda {:f} {:f :f}}
 {lambda {:g :d :n}
  {if {< :n 1}
   then
   else T90      
{{{lambda {:f} {:f :f}} 
 {lambda {:g :d :n}
  {if {< :n 1}
   then
   else T-90    
{{{lambda {:f} {:f :f}} :g} :d {- :n 1}}
        M:d T90 {:g :g :d {- :n 1}}
        M:d     {:g :g :d {- :n 1}}
        T90 M:d 
{{{lambda {:f} {:f :f}} :g} :d {- :n 1}}
        T-90}}} :d {- :n 1}}
        M:d T-90 {:g :g :d {- :n 1}}
        M:d      {:g :g :d {- :n 1}}
        T-90 M:d 
{{{lambda {:f} {:f :f}} 
 {lambda {:g :d :n}
  {if {< :n 1}
   then
   else T-90    
{{{lambda {:f} {:f :f}} :g} :d {- :n 1}}
        M:d T90 {:g :g :d {- :n 1}}
        M:d     {:g :g :d {- :n 1}}
        T90 M:d 
{{{lambda {:f} {:f :f}} :g} :d {- :n 1}}
        T-90}}} :d {- :n 1}}
        T90}}} 
10 2} 
}

_p As an illustration, see [[hilbert]], here is what would be produced by the evaluation of the last expression (with "12 5" instead of "10 2"), the sequence of {b Mx} and {b Tθ} sent to a SVG graphic device

{center
{svg {@ width="395px" height="395px"}
 {path 
 {@ id="spline"
     d="M {turtle 10 10 0 {hilbert.left 12 5}}"  
      fill="transparent" stroke="#fff" stroke-width="1"
 }}
 {circle 
  {@ cx="0" cy="0" r="5" fill="#0ff" stroke="#f00"}
  {animateMotion 
   {@ dur="100s" repeatCount="indefinite" rotate="auto"}
   {mpath {@ xlink:href="#spline"}}
 }} 
}}

}

{{block}
_h2 conclusion

_p It appears that a being as strange as the {b Y}-combinator, slightly simplified to {b Ω}-combinator, brings a good light on a concept known to be difficult to access, {b recursion}. By allowing the definition of immediately applied anonymous functions, {b IIFE}s, it reduces the evaluation of any expression to a simple text rewriting process, without any shadow area and easy to understand. The dreaded {b λ}-calculus thus becomes a faithful friend accompanying the act of [[coding]].   
_p What do you think about it?

_p {i alain marty | 2022/05/31}

_p See also [[from Y to Ω|?view=Y_en]] and [[divine_recursion]].

;; [[HN|https://news.ycombinator.com/item?id=31574264]]

;; [[Fixed-point_combinator|https://en.wikipedia.org/wiki/Fixed-point_combinator]]

}

;; coder's corner

{macro _h(\d)fr ([^\n]+)\n to {h€1 {@ class="fr"}€2}}
{macro _h(\d)en ([^\n]+)\n to {h€1 {@ class="en"}€2}}
{macro _pfr ([^\n]+)\n to {p {@ class="fr"}€1}} 
{macro _pen ([^\n]+)\n to {p {@ class="en"}€1}} 
{macro _l([\d]*)fr ([^\n]+)\n to {ul {@ class="fr" style="margin-left:€1px;"} {li €2}}}
{macro _l([\d]*)en ([^\n]+)\n to {ul {@ class="en" style="margin-left:€1px;"} {li €2}}}

{{hide} 
{def block 
  div {@ style="display:inline-block; width:600px; vertical-align:top; padding:5px; margin:30px; "}}

{def geek
 blockquote {@ style="transform:rotate(-2deg); border:1px dashed; padding:10px;"}}

{def toggle
 {input
  {@ type="button" value="french" onclick="toggle(this)"
     style="position:fixed; top:10px; left:10px; z-index:2;
            font:normal 1.0em courier; color:#fff; background:#f00;
            border:0; border-radius:30px; box-shadow:0 0 8px #fff;
            padding:5px 10px;"
}}}

{def toggle2
 {input
  {@ type="button" value="horizontal" onclick="toggle2(this)"
     style="position:fixed; top:10px; left:10px; z-index:2;
            font:normal 1.0em courier; color:#fff; background:#f00;
            border:0; border-radius:30px; box-shadow:0 0 8px #fff;
            padding:5px 10px;"
}}}

}

{style 
body { background:#444; }  
#page_frame {
 border:0; background:transparent;
 width:600px;
 margin:auto;      ;; margin-left:0; 
}
#page_content {
 background:transparent; color:#fff; border:0;
 box-shadow:0 0 0; font:normal 1.2em optima; 
 width:600px;      ;; width:5500px; 
}
.page_menu { background:transparent; color:#fff; }
a { color:#f80; }
pre { box-shadow:0 0 0px #000; padding:5px; background:#333; color:#fff; font:normal 1.0em courier new; }
b { color:cyan; }
h1 { font-size:4.0em; margin:0; color:#fff; }
h2 { font-size:3.0em; margin:0; color:#fff; }
h3 { font-size:1.5em; margin:0; color:#fff; }
h4 { font-size:1.2em; margin:0; color:#fff; }

code { font-style:bold; }
.fr { display:none; }
.en { display:block; }
}

{script 
var toggle = function(obj) {
  var frs = document.getElementsByClassName('fr');
  var ens = document.getElementsByClassName('en');
  if (obj.value==='english') {
    for (var i=0; i< frs.length; i++) frs[i].style.display="none";
    for (var i=0; i< ens.length; i++) ens[i].style.display="block";
    obj.value = 'français';
  } else {
    for (var i=0; i< frs.length; i++) frs[i].style.display="block";
    for (var i=0; i< ens.length; i++) ens[i].style.display="none"; 
    obj.value = 'english';   
  }
};