lambdaway :: funstacker2

2 | list | login |load

| |

_img https://defeo.lu/M1-AlgoProg/tds/NPI.jpg

{macro \/\/ ([^\n]*)\n to <span style="color:blue">// €1</span></br>}

_h1 stacker {sup [[array|?view=funstacker]] | list | [[next...|?view=funstacker3]] }

_p We evaluate expressions in [[reverse polish notation|https://fr.wikipedia.org/wiki/Notation_polonaise_inverse]], {b here using lists} and displaying the successive states of the stack. We give in blue the equivalent lambdatalk expressions, in a direct prefixed parenthesized notation.

_ul the example on top of this page
{pre                       
'{calc 1 2 + 4 * 3 +}           // '{+ 3 {* 4 {+ 1 2}}}
-> {calc 1 2 + 4 * 3 +} 
}
_ul the four operators {b + - * /}
{pre
'{calc 3 4 +}                   // '{+ 3 4}
-> {calc 3 4 +}

'{calc 3 4 -}                   // '{- 3 4}
-> {calc 3 4 -}

'{calc 3 4 *}                   // '{* 3 4}
-> {calc 3 4 *}

'{calc 3 4 /}                   // '{/ 3 4}
-> {calc 3 4 /}
}
_ul the pythagora formula
{pre
'{calc 3 3 * 4 4 * + sqrt}      // '{sqrt {+ {* 3 3} {* 4 4}}}
-> {calc 3 3 * 4 4 * + sqrt}             
}
_ul computing the factorial of 6, to be compared with the standard recursive code
{pre
'{calc 6 5 4 3 2 1 * * * * *}   // '{* 6 {* 5 {* 4 {* 3 {* 2 1}}}}}
-> {calc 6 5 4 3 2 1 * * * * *}              
}                     
_ul computing the factorial of 6, to be compared with the tail-recursive code
{pre
'{calc 6 5 * 4 * 3 * 2 * 1 *}
-> {calc 6 5 * 4 * 3 * 2 * 1 *}            
}
_p Following the task in [[rosettacode.org|http://rosettacode.org/wiki/Parsing/RPN_calculator_algorithm#Lambdatalk]]
{pre
'{calc 3 4 2 * 1 5 - 2 3 pow pow / +}    // 
-> {calc 3 4 2 * 1 5 - 2 3 pow pow / +}  // '{+ {/ {pow {pow 3 2} {- 1 5}} {* 2 4}} 3}

+
         / \
       div  3
       / \
      /   \
    pow    +
    / \   / \
  pow  \ 2   4
  / \   \
 3   2   -
        / \
       1   5
}
_ul the golden ratio φ 
{pre
'{calc 1 5 sqrt + 2 /}          // '{/ {+ 1 {sqrt 5}} 2}  
-> {calc 1 5 sqrt + 2 /}            
}
_ul computing in a local context the positive root of {code ax{sup 2} + bx + c = 0}, {code x = (-b + √(b{sup 2}-4ac))/2a}, for {code a=1, b=-1, c=-1}
{pre 
;; x = '{/ {+ {- b} {sqrt {- {pow b 2} {* 4 {* a c}}}}} {* 2 a}}
'{let { {:a 1}    
       {:b -1}
       {:c -1}
     } {calc :b -1 * :b 2 pow 4 :a * :c * - sqrt + 2 :a * /}
}
-> {let { {:a 1}
       {:b -1}
       {:c -1}
     } {calc :b -1 * :b 2 pow 4 :a * :c * - sqrt + 2 :a * /}
} 
}
_ul and so on...

_h2 the calc function

_p The {b calc} function is built on 3 lambdatalk primitives {b cons, car, cdr} and 5 user defined functions {b unop?, binop?, list, empty?, disp}

{pre
'{def calc

{def calc.r
  {lambda {:x :s}
   {if {empty? :x}
    then -> {b {car :s}}
    else {car :x}: {disp :s}{br}     // optional, used to display steps
         {calc.r {cdr :x}
                 {if {unop? {car :x}}
                  then {cons {{car :x} {car :s}} {cdr :s}}
                  else {if {binop? {car :x}}
                  then {cons {{car :x} {car {cdr :s}} {car :s}} {cdr {cdr :s}}}
                  else {cons {car :x} :s}} }}}}}

{lambda {:s}
  {calc.r {list :s} nil}}}
-> {def calc
 {def calc.r
  {lambda {:x :s}
   {if {empty? :x}
    then -> {b {car :s}}
    else {car :x} : {disp :s}{br}
         {calc.r {cdr :x}
                 {if {unop? {car :x}}
                  then {cons {{car :x} {car :s}} {cdr :s}}
                  else {if {binop? {car :x}}
                  then {cons {{car :x} {car {cdr :s}} {car :s}} {cdr {cdr :s}}}
                  else {cons {car :x} :s}} }}}}}
 {lambda {:s}
  {br} {calc.r {list :s} nil}}}
}

_p Comparing this code with this [[Racket code|https://beautifulracket.com/funstacker/source-listing.html]] - which works with two binary operators [{b +, *}] only - can help to accept the accumulation of parentheses so typical of LISP dialects. IMHO.

_p The {b unop?} & {b binop?} functions are used to test an extensible set of unary and binary operators

{pre
'{def unop?
 {lambda {:op}
  {or {W.equal? :op sqrt}       // n sqrt  sqrt(n)
      {W.equal? :op exp}        // n exp   exp(n)
      {W.equal? :op log}        // n log   log(n) 
      {W.equal? :op cos}        // n cos   cos(n)
      ... and so                // ...
}}}
-> {def unop?
 {lambda {:op}
  {or {W.equal? :op sqrt}
      {W.equal? :op exp}        
      {W.equal? :op log}           
      {W.equal? :op cos} 
}}}

'{def binop?
 {lambda {:op}
  {or {W.equal? :op +}          // m n +     m+n
      {W.equal? :op -}          // m n -     m-n
      {W.equal? :op *}          // m n *     m*n
      {W.equal? :op /}          // m n /     m/n
      {W.equal? :op %}          // m n %     m%n
      {W.equal? :op pow}        // m n pow   m^n
      ... and so on             // ...
}}}
-> {def binop?
 {lambda {:op}
  {or {W.equal? :op +}
      {W.equal? :op -}
      {W.equal? :op *}
      {W.equal? :op /}
      {W.equal? :op %}  
      {W.equal? :op pow} 
}}}
}
_p A more general way to deal with operators can be seen in the [[next...|?view=funstacker3]] page.

_p The {b list, empty?, disp} functions are used to create a list from a string, test its emptynes and display it.

{pre
'{def list
 {lambda {:s}
  {if {S.empty? {S.rest :s}}
   then {cons {S.first :s} nil}
   else {cons {S.first :s} {list {S.rest :s}}}}}}
-> {def list
 {lambda {:s}
  {if {S.empty? {S.rest :s}}
   then {cons {S.first :s} nil}
   else {cons {S.first :s} {list {S.rest :s}}}}}}

'{def empty?
 {lambda {:x}
  {W.equal? :x nil}}}
-> {def empty?
 {lambda {:x}
  {W.equal? :x nil}}}

'{def disp
 {def disp.r
  {lambda {:l}
   {if {empty? :l}
    then 
    else {car :l} {disp.r {cdr :l}}}}}
 {lambda {:l}
  ({disp.r :l})}}
-> {def disp
 {def disp.r
  {lambda {:l}
   {if {empty? :l}
    then 
    else {car :l} {disp.r {cdr :l}}}}}
 {lambda {:l}
  ({disp.r :l})}}
}

_h2 conclusion

_p It's important to note that everything - except {b list} - was {b exclusively} built on {b 5} lambdatalk primitives, {b cons, car, cdr}, to create lists, {b W.equal?} which test the equality between two words, and the {b or} boolean function. The {b list} function, which is useful but optional, uses 3 lambdatalk primitives dealing with sentences, {b S.empty?, S.first & S.rest}.

_p Finally using {b immutable lists} instead of [[mutable arrays|?view=funstacker]] leads to a more homogeneous and elegant code.

_p The LISP way, "{i Lot of Insane and Silly Parentheses}", is great.

_p {i alain marty 2022/05/20-22}
_p [[HN|https://news.ycombinator.com/item?id=31455491]]

_h2 post scriptum

_p {i At the end of the 70's I bought a (very expensive) HP67 and discovered the inverse Polish notation, "1 2 +". Much later I came across LISP and discovered prefixed parenthesized expressions, '{+ 1 2}, i.e. direct polish notation with parentheses. Then I discovered that an HTML expression like "{code <{span}b><{span}i><{span}u>Hello World<{span}/u><{span}/i><{span}/b>}", requiring that closed brackets be written in the  reverse order, would be better written in a LISP style, {b '{b {i {u Hello World}}}}, without boring anymore with the order of closing brackets. Finally I found that if writing '{b 1 2 3 4 5 6} displayed "{b 1 2 3 4 5 6}" in bold, writing '{* 1 2 3 4 5 6} displayed the product, "720", and writing '{b {* 1 2 3 4 5 6}} displayed "{b 720}" in bold. Mixing pure text and active code to style it and make it "dynamic" had became obvious. 
_p This made me want to write a programming language and its current state is in the [[lambdaway project|?view=start]].}

{style 
pre { box-shadow:0 0 8px #000; padding:10px; }
}