lambdaway :: recursion

5 | list | login |load

| |

_img https://miro.medium.com/max/4000/1*g2B3g2ikPqsoaWiCXQDUGw.jpeg

_p See also 
_ul [[https://javascript.info/recursion| https://javascript.info/recursion]]
_ul [[https://news.ycombinator.com/item?id=26377312|https://news.ycombinator.com/item?id=26377312]]
_ul [[https://blog.moertel.com/tags/recursion-to-iteration%20series.html|https://blog.moertel.com/tags/recursion-to-iteration%20series.html]]
_ul [[https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration|https://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration]]

_p Rule: On a known interval use iteration else recursion:

_ul Recursion is the native control structure in lambdatalk which {b can be used everytime} but may lead to stack overflows.
_ul Iteration of a function on a sequence of terms can be done using {code map & serie}, for instance

{pre
'{S.map {lambda {:i} {* :i :i}} {S.serie 1 10}}  
-> {S.map {lambda {:i} {* :i :i}} {S.serie 1 10}}
}

_p Note that {code S.map} applies a function on every words of a sentence, {code W.map} on every characters of a word and {code A.map} on every terms/slots of an array. For recurrent functions, ie {code u(n) = n * u(n-1)}, lambdatalk can't use mutation, or any counter in a loop. But arrays are mutable via a {code '{A.set! i v a}} function and can be used to store successive values. And in the mean time {b we get memoization for free}.

_h2 1) factorial

_p Several ways to compute {code Π{sub i=1}{sup n}(i) which is equal to 1*2*...*n}

{pre
1) using the * primitive

'{S.reduce * {S.serie 1 10}}

or simply, because * is a variadic operator

'{* {S.serie 1 10}}
-> {* {S.serie 1 10}}

2) using recursion

fac(0) = 1
fac(n) = n*fac(n-1)

'{def rfac
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {* :n {rfac {- :n 1}}}}}}
-> {def rfac
 {lambda {:n}
  {if {= :n 0}
   then 1
   else {* :n {rfac {- :n 1}}}}}}

'{rfac 10}
-> {rfac 10}

3) using iteration

We store in a local array successive values
      mem[i] = i * mem[i-1]
coded as : '{A.set! :i {* :i {A.get {- :i 1} :mem}} :mem}
   then return the last

'{def ifac
 {def ifac.map
  {lambda {:mem :n}
   {S.map {{lambda {:mem :i}     
                   {A.set! :i 
                           {* :i {A.get {- :i 1} :mem}}
                           :mem}
           } :mem}
          {S.serie 1 :n} }}}
 {lambda {:n}
  {A.last {S.last {ifac.map {A.new 1} :n}}} }} 
-> {def ifac
 {def ifac.map
  {lambda {:n :mem}
   {S.map {{lambda {:mem :i}
                   {A.set! :i {* {A.get {- :i 1} :mem} :i} :mem}} :mem}
          {S.serie 1 :n} }}}
 {lambda {:n}
  {A.last {S.last {ifac.map :n {A.new 1}}}} }}

'{ifac 10}
-> {ifac 10}

}

_h2 2) fibonacci

{pre
fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1)+fib(n-2)

1) using naïve recursion

'{def rfib
 {lambda {:n}
  {if {< :n 2}
   then 1
   else {+ {rfib {- :n 1}} {rfib {- :n 2}}}}}}
-> {def rfib
 {lambda {:n}
  {if {< :n 2}
   then 1
   else {+ {rfib {- :n 1}} {rfib {- :n 2}}}}}}

'{rfib 10}
-> {rfib 10}

{b It's slow and locks the computer for values greater than 25}

2) using iteration

We store in a local array successive values 
   mem[i] = mem[i-1]+mem[i-2] 
   then return the last. it's memoization !

'{def ifib
 {def ifib.map
  {lambda {:mem :n}
   {S.map {{lambda {:mem :i}       // mem[i] = mem[i-1]+mem[i-2] 
                   {A.set! :i 
                           {+ {A.get {- :i 1} :mem}  
                              {A.get {- :i 2} :mem}} 
                           :mem}
           } :mem}
          {S.serie 2 :n} }}}
 {lambda {:n}
  {A.last {S.last {ifib.map {A.new 1 1} :n}}}}}
-> {def ifib
 {def ifib.map
  {lambda {:n :mem}
   {S.map {{lambda {:mem :i}
                   {A.set! :i 
                           {+ {A.get {- :i 1} :mem}
                              {A.get {- :i 2} :mem}} 
                           :mem}
           } :mem}
          {S.serie 2 :n} }}}
 {lambda {:n}
  {A.last {S.last {ifib.map :n {A.new 1 1}}}}}}

'{ifib 1000}
-> {ifib 1000}  // quick and without limit
}

_h2 3) a pattern for memoized iteration

_p We look for a general pattern using memoization in iteration. In fact the {code mem} array is space to store successive states as a sequence of computed values.

{pre
'{def iter
 {def iter.map
  {lambda {:mem :range}
   {S.map {{lambda {:mem :i}
                   {A.set! :i computed_value :mem} 
           } :mem}
          {S.serie :range} }}}
 {lambda {:args}
  {S.last 
   {iter.map {A.new initial values}
             :range  
}}}}
}

_p We can put some syntactic sugar with {code '{for a to b do func with init}}

{prewrap
'{def for
 {lambda {:start to :end step :step do :fun with :init}
  {S.last
   {{lambda {:mem :fun :start :end :step}
            {S.map {:fun :mem} {S.serie :start :end :step} }}
    {A.new :init} :fun :start :end :step}}}}
-> {def for
 {lambda {:start to :end step :step do :fun with :init}
  {S.last
   {{lambda {:mem :fun :start :end :step}
            {S.map {:fun :mem} {S.serie :start :end :step} }}
    {A.new :init} :fun :start :end :step}}}}
}

_p The {code for} function returns an array.

{pre
'{for 1 to 10 step 1
  do {lambda {:mem :i} {A.set! :i {* :i :i} :mem}} 
  with 0}
-> {for 0 to 10 step 1 do {lambda {:mem :i} {A.set! :i {* :i :i} :mem}} with 0}

'{let { {:euler {for 1 to 17 step 1
                 do {lambda {:mem :i}
                            {A.set! :i {/ 1 {S.serie 1 :i}} :mem}} 
               with 0}}
     } {+ 1 {S.map {{lambda {:euler :i}
                            {A.get :i :euler}} :euler}
                   {S.serie 0 16 1}}} }
-> {let { {:euler {for 1 to 17 step 1
                    do {lambda {:mem :i} {A.set! :i {/ 1 {S.serie 1 :i}} :mem}} 
                  with 0}}
     } {+ 1 {S.map {{lambda {:euler :i}
                            {A.get :i :euler}} :euler}
                   {S.serie 0 16 1}}} }
   {E}  
 
'{A.last
 {for 1 to 10 step 1
   do {lambda {:mem :i}
              {A.set! :i {* {A.get {- :i 1} :mem} :i} :mem}}
   with 1}}
-> {A.last
 {for 1 to 10 step 1 
   do {lambda {:mem :i}
              {A.set! :i {* {A.get {- :i 1} :mem} :i} :mem}} 
 with 1}}

'{A.last
 {for 2 to 100 step 1
   do {lambda {:mem :i}
              {A.set! :i {+ {A.get {- :i 1} :mem}
                            {A.get {- :i 2} :mem}} :mem}} 
   with 1 1}}
-> {A.last
 {for 2 to 100 step 1
   do {lambda {:mem :i} 
              {A.set! :i {+ {A.get {- :i 1} :mem}
                            {A.get {- :i 2} :mem}} :mem}}
 with 1 1}}
}

_h2 4) a pattern for memoized recursion

{pre
'{def rfac
 {def rfac.r
  {lambda {:mem :n :i}
   {if {< :i :n}
    then {rfac.r {A.set! :i {* :i {A.get {- :i 1} :mem}} :mem}
                 :n 
                 {+ :i 1}}
    else :mem}}}
 {lambda {:n}
  {A.last {S.last {rfac.r {A.new 1 1} :n 2}}}}}
-> {def rfac
 {def rfac.r
  {lambda {:mem :n :i}
   {if {< :i :n}
    then {rfac.r {A.set! :i {* :i {A.get {- :i 1} :mem}} :mem}
                 :n 
                 {+ :i 1}}
    else :mem}}}
 {lambda {:n}
  {A.last {S.last {rfac.r {A.new 1 1} :n 2}}}}}

'{rfac 10}
-> {rfac 10}

'{def rfib
 {def rfib.r
  {lambda {:mem :n :i}
   {if {<= :i :n}
    then {rfib.r {A.set! :i 
                         {+ {A.get {- :i 1} :mem}   
                            {A.get {- :i 2} :mem}} 
                         :mem}
                 :n 
                 {+ :i 1}}
    else :mem}}}
 {lambda {:n}
  {A.last {S.last {rfib.r {A.new 1 1} :n 2}}}}}
-> {def rfib
 {def rfib.r
  {lambda {:mem :n :i}
   {if {<= :i :n}
    then {rfib.r {A.set! :i 
                         {+ {A.get {- :i 1} :mem}   
                            {A.get {- :i 2} :mem}} 
                         :mem}
                 :n 
                 {+ :i 1}}
    else :mem}}}
 {lambda {:n}
  {A.last {S.last {rfib.r {A.new 1 1} :n 2}}}}}

'{rfib 100} 
-> {rfib 100}
}

_h2 some more thing

_p Compare this javascript code

{pre
var fac = function(n) '{
// 1) initializations

var a = 1,
      b = n;

// 2) loop

while (b > 0) {
    a = a*b;
    b = b-1;
  }
  return a;
};
}

_p to this lambdatalk code

{pre
'{def fac

// 2) loop
 {def loop
 {lambda {:a :b}
   {if {> :b 0}                    // while b > 0
    then {let { {:a {* :a :b}}     // do a = a*b
                {:b {- :b 1}}      //    b = b-1
              } {loop :a :b}}      //    goto loop
    else :a}}}                     // return a

// 1) initialization

{lambda {:n}
  {let { {:a 1}                    // a = n
         {:b :n}                   // b = 1
       } {loop :a :b}}}}           // goto loop

-> {def fac
 {def fac.r
  {lambda {:a :b}
   {if {> :b 0}
    then {let { {:a {* :a :b}}
                {:b {- :b 1}}
              } {fac.r :a :b}}
    else :a}}}
 {lambda {:n}
  {let { {:a 1}
         {:b :n}
       } {fac.r :a :b}}}}

}

_p Well, we can see similarities but lambdatalk is very encumbered by its parentheses! Even if its syntax is perfectly uniform (nothing but prefixed parentheses expressions), even if in contrast the javascript syntax is a mix of instructions, assignments and control structure, even if, in the real life, the lambdatalk code would obviously be written more simply

{pre
'{def fac
 {def fac.r
  {lambda {:a :b}                    // recurse with a & b
   {if {> :b 0}                      // if b > 0
    then {fac.r {* :a :b} {- :b 1}}  // then recurse with a=a*b & b=b-1
    else :a}}}                       // else return a
 {lambda {:n}
  {fac.r 1 :n}}}    // initialize and recurse
}

_p the battle seems to be lost. Ok! The one and considerable advantage of the lambdatalk syntax remains its proximity to the foundations, λ-calculus. Nothing but IIFES made of abstractions and applications. Nothing but text substitutions.

_p {b There is another advantage}: with lambdatalk I can write {code '{b 1 2 3 4 5 6}} to get {b 1 2 3 4 5 6} and {code '{* 1 2 3 4 5 6}} to get {* 1 2 3 4 5 6} and even {code '{b {* 1 2 3 4 5 6}}} to add some style to computation : {b {* 1 2 3 4 5 6}}. With javascript I can't. {b And I need it.}

_p Finally my last question is: {i could a kind of macro be used to translate {b automatically} a lambdatalk tail-recursive code into a javascript iterative code?}

_p Any idea?

{hr}

_p Added to [[rosettacode|https://rosettacode.org/wiki/Anonymous_recursion#Lambdatalk]] on 2022/04/18
{pre
1) defining a quasi-recursive function combined with a simple Ω-combinator:
'{def fibo {lambda {:n}
 {{{lambda {:f} {:f :f}} 
  {lambda {:f :n :a :b}
   {if {< :n 0}
    then the number must be positive! 
    else {if {<  :n 1}
    then :a
    else {:f :f {- :n 1} {+ :a :b} :a}}}}} :n 1 0}}}
-> {def fibo {lambda {:n}
 {{{lambda {:f} {:f :f}} 
  {lambda {:f :n :a :b}
   {if {< :n 0}
    then the number must be positive! 
    else {if {<  :n 1}
    then :a
    else {:f :f {- :n 1} {+ :a :b} :a}}}}} :n 1 0}}}

2) testing:
'{fibo -1} -> the number must be positive!
'{fibo 0} -> 1
'{fibo 8} -> 34
'{fibo 1000} -> 7.0330367711422765e+208
'{S.map fibo {S.serie 1 20}}
-> 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
 
We could also avoid any name and write an IIFE 
 
'{{lambda {:n}
 {{{lambda {:f} {:f :f}} 
  {lambda {:f :n :a :b}
   {if {< :n 0}
    then the number must be positive! 
    else {if {<  :n 1}
    then :a
    else {:f :f {- :n 1} {+ :a :b} :a}}}}} :n 1 0}}
 8}
-> 34
}
{hr}

{style 
body { background:#444; }
#page_frame { border:0; }
#page_content { background:transparent; color:#fff; border:0;}
.page_menu { background:transparent; color:#e1bc91;}
a {color:red}
h1, h2, h3, h4, h5, h6 { text-align:center; margin:10px 0 10px -20px; color:#ffd9a9; }
blockquote { font-style:italic; color:#ffd9a9; }
pre { box-shadow:0 0 8px #000; padding:10px; }

}