lambdaway :: fac2iife

5 | list | login |load

| |

_h1 fac2iife

{pre
'{let { {:om {lambda {:f} {:f :f}}}
       {:fac {lambda {:f :n}
                     {if {< :n 1} 
                      then 1 
                      else {* :n {:f :f {- :n 1}}}}}}
     } {{:om :fac} 6}
}
-> {let { {:om {lambda {:f} {:f :f}}}
       {:fac {lambda {:f :n} {if {< :n 1} then 1 else {* :n {:f :f {- :n 1}}}}}}
     } {{:om :fac} 6}
} 
}

{pre
{def fac
 {lambda {:n}
  {if {W.equal? :n 1} 
   then 1
   else {* :n {fac {- :n 1}}}}}}

{fac 6}

{def disp
 {lambda {:l}
  {if {W.equal? :l nil}
  then
  else {car :l} {disp {cdr :l}}}}}

{def l {cons a {cons b {cons c {cons d nil}}}}} = {l}

{disp {l}}

}

_p We can avoid {b if then else} using the {b cons, car, cdr} structure and an {b equal} function

{pre
{def equal
 {lambda {:a :b}
  {if {W.equal? :a :b} then car else cdr}}}

{def fac2
 {lambda {:n}
  {{{equal :n 1}
   {cons
    {lambda {:n} 1}
    {lambda {:n} {* :n {fac2 {- :n 1}}}}}} :n}}}

{fac2 6}

{def disp2
 {lambda {:l}
  {{{equal :l nil}
  {cons
   {lambda {:l} }
   {lambda {:l} {car :l} {disp2 {cdr :l}}}}} :l}}}

{disp2 {l}}
}

_p We can avoid the name in the recursive call

{pre
{def afac2
 {lambda {:f :n}
  {{{equal :n 1}
   {cons
    {lambda {:f :n} 1}
    {lambda {:f :n} {* :n {:f :f {- :n 1}}}}}} :f :n}}}

{afac2 afac2 6}

{def adisp2
 {lambda {:f :l}
  {{{equal :l nil}
  {cons
   {lambda {:f :l} }
   {lambda {:f :l} {car :l} {:f :f {cdr :l}}}}} :f :l}}}

{adisp2 adisp2 {l}}
}

_p We can avoid doubling the name using some Ω-combinator

{pre
{def Ω {lambda {:f} {:f :f}}}

{{Ω afac2} 6}

{{Ω adisp2} {l}}
}

_p We can avoid the  Ω-combinator's name

{pre
{{{lambda {:f} {:f :f}} 
 {lambda {:f :n}
  {{{equal :n 1}
   {cons
    {lambda {:f :n} 1}
    {lambda {:f :n} {* :n {:f :f {- :n 1}}}}}} :f :n}}} 6}

{{{lambda {:f} {:f :f}} 
 {lambda {:f :l}
  {{{equal :l nil}
   {cons
    {lambda {:f :l} }
    {lambda {:f :l} {car :l} {:f :f {cdr :l}}}}} :f :l}}} {l}}

}

_p We can avoid {b cons} using a new {b when} function

{pre
{def when
 {lambda {:a :b :c} {:a {cons :b :c}}}}

{{{lambda {:f} {:f :f}} 
 {lambda {:f :n}
  {{when {equal :n 1}
   {lambda {:f :n} 1}
   {lambda {:f :n} {* :n {:f :f {- :n 1}}}}} :f :n}}} 6}

{{{lambda {:f} {:f :f}} 
 {lambda {:f :l}
  {{when {equal :l nil}
    {lambda {:f :l} }
    {lambda {:f :l} {car :l} {:f :f {cdr :l}}}} :f :l}}} {l}}
}

_p We can avoid {b cons, car, cdr} redefining everything as lambdas

{pre
{def NIL {lambda {:a} }}  // the void function

{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}}}

{def EQUAL {lambda {:a :b} {if {W.equal? :a :b} then LEFT else RIGHT}}}

{def WHEN {lambda {:a :b :c} {:a {PAIR :b :c}}}}

{def FAC
 {lambda {:n}
  {{WHEN {EQUAL :n 1}
   {lambda {:n} 1}
   {lambda {:n} {* :n {FAC {- :n 1}}}}} :n}}}

{FAC 6}

{{{lambda {:f} {:f :f}} 
 {lambda {:f :n}
  {{WHEN {EQUAL :n 1}
   {lambda {:f :n} 1}
   {lambda {:f :n} {* :n {:f :f {- :n 1}}}}} :f :n}}} 6}

{def L {PAIR a {PAIR b {PAIR c {PAIR d NIL}}}}}

{def DISP
 {lambda {:l}
  {{WHEN {EQUAL :l NIL} 
   {lambda {:l} }
   {lambda {:l} {LEFT :l}
                   {DISP {RIGHT :l}}}} :l}}}

{DISP {L}}

{{{lambda {:f} {:f :f}} 
 {lambda {:f :l}
  {{WHEN {EQUAL :l NIL} 
   {lambda {:f :l} }
   {lambda {:f :l} {LEFT :l}
                   {:f :f {RIGHT :l}}}} :f :l}}} {L}}

{{{lambda {:f} {:f :f}} 
 {lambda {:f :l}
  {{{EQUAL :l NIL} 
   {PAIR 
    {lambda {:f :l} }
    {lambda {:f :l} {LEFT :l}
                    {:f :f {RIGHT :l}}}}} :f :l}}} {L}}
}

_h2 numbers

{prewrap
 {def LENGTH
 {lambda {:n}
  {{WHEN {EQUAL :n NIL} 
   {lambda {:n} }
   {lambda {:n} •{LENGTH {RIGHT :n}}}} :n}}}

{def SUCC {lambda {:n} {PAIR • :n}}}
{def PREV {lambda {:n} {RIGHT :n}}}

{def N {SUCC {SUCC {SUCC {SUCC NIL}}}}}

{LENGTH {N}}
{LENGTH {SUCC {N}}}
{LENGTH {PREV {N}}}
{LENGTH {PREV {PREV {N}}}}
{LENGTH {PREV {PREV {PREV {N}}}}}
{LENGTH {PREV {PREV {PREV {PREV {N}}}}}}

{def ADD
 {lambda {:a :b}
  {{WHEN {EQUAL :b NIL}
   {lambda {:a :b} :a}
   {lambda {:a :b} {ADD {SUCC :a} {PREV :b}}}} :a :b}}}

{LENGTH {ADD {N} {N}}}

{def MUL
 {def MUL.r
  {lambda {:a :b :c}
   {{WHEN {EQUAL :b NIL}
    {lambda {:a :b :c} :c}
    {lambda {:a :b :c} {MUL.r :a {PREV :b} {ADD :a :c}}}} :a :b :c}}}
 {lambda {:a :b}
  {MUL.r :a :b NIL}}}  
  
{W.length {LENGTH {MUL {N} {N}}}}

{def FAC2 
 {lambda {:n}
  {{WHEN {EQUAL :n NIL}
   {lambda {:n} {PAIR • NIL}}
   {lambda {:n} {MUL :n {FAC2 {PREV :n}}}}} :n}}}  
  
{LENGTH {FAC2 {N}}}
 
}

°°°
_p an alternative with lists}

{pre
{def IF {lambda {:a :b :c} {:a :b :c}}}

{def ISNIL {lambda {:c} {:c {lambda {:a :b} FALSE}}}}

{ISNIL {L}}
{ISNIL {RIGHT {L}}}
{ISNIL {RIGHT {RIGHT {L}}}}
{ISNIL {RIGHT {RIGHT {RIGHT {L}}}}}
{ISNIL {RIGHT {RIGHT {RIGHT {RIGHT {L}}}}}}

{{{lambda {:f} {:f :f}} 
 {lambda {:f :l}
  {{IF {ISNIL :l}
   {lambda {:f :l} }
   {lambda {:f :l} {LEFT :l}
                   {:f :f {RIGHT :l}}}} :f :l}}} 
 {L}}

°°°