An Algebraic Compiler for LANG1 on StackM

Example:  Consider the simple conditional statement written in the concrete syntax of LANG1:

We can use doparse to transform this into the corresponding abstract syntax expression in the algebra T(LANG1Syn)

and then apply  the homomorphism  aitch("alg_LANG1StC", _ )  to get the corresponding StackM program:

which, looks as follows when written as a program listing:

   1     get(a)
   2     get(b)
   3     leq
   4     branch(11)
   5     get(c)
   6     1
   7     add
   8     put(c)
   9     true
   10   branch(16)
   11   get(c)
   12   1
   13   neg
   14   add
   15   put(c)


This computation, for trial inputs  "a"=10 and "b"=5, (so, by default, "c"=0) can be done in two steps  by performing the following expression on the UA-Calculator

setSTM(aitch("alg_LANG1StC", doparse( "If (a<=b) then c:=(c+(-1)) else c:=(c+1) fi")), [["a", 10], ["b", 5]])

and then performing runSTM(10).  Try it:
 
 



setSTM(aitch("alg_LANG1StC",doparse("If (a<=b)then c:=(c+(-1)) else c:=(c+1) fi")), [["a", 10], ["b", 5]])


• Now press reset, change the values of "a" and "b" so that "a" has a value less-than that of "b"  and try it again.

 
• Now press reset and put in an initial  value for "c" other than the default value of 0, and try it again.   To put in a value for "c" you just edit the input text, e.g., change  [["a", 10], ["b", 5]]  to, say,  [["a", 10], ["b", 5], ["c", 7]]
end

Example:  Consider the simple program, for the factorial function, written in the concrete syntax of LANG1:

 "b:=1; While (1<=a) do b:=(a*b); a:=(a+(-1)) od"

We can use doparse to transform this into the corresponding abstract syntax expression in the algebra T(LANG1Syn)

compos(assign(b( ), 1( )), wdo(leq(1( ),id2ae(a( ))), compos(assign(b( ), mult(id2ae(a( )),id2ae(b( )))), assign(a( ), add(id2ae(a( )),neg(1( )))))))

and then apply  the homomorphism  aitch("alg_LANG1StC", _ )  to get the corresponding StackM program:

 [1, "put(b)", 1, "get(a)", "leq", "branch(9)", true, "branch(20)", "get(a)", "get(b)", "mult", "put(b)", "get(a)", 1, "neg", "add", "put(a)", true, "branch(3)"]

which, looks as follows when written as a program listing:
 

   1   1
   2    put(b)
   3   1
   4    get(a)
   5    leq
   6    branch(9)
   7    true
   8    branch(20)
   9    get(a)
   10  get(b)
   11  mult
   12  put(b)
   13  get(a)
   14  1
   15   neg
   16  add
   17  put(a)
   18  true
   19  branch(3)
To execute this program on StackM  with "a"=10  takes 150 steps.
 
 


Click on "Example" to start


• Now press reset, change the value of "a" and try it again.  (If you choose "a">20 the calculator will fail due to the integers being to big for JavaScript)
• Note how much faster this StackM program is than the corresponding program using the algebra LANG1Sem!

 


end