Programming Languages

EXP was used for educational purposes in the course "Einführung in die Theorie der Informatik" at the technical university of vienna. Professor Gernot Salzer invented the language [Lately Prof. Salzer pointed out to me, that he did not invent EXP... it is used in the book: M. Wand, "Induction, Recursion and Programming", North Holland, '84, so M.Wand most probably invented EXP] . It seems that an implementation of the language (compiler / interpreter) has not existed before! Unfortunately by now the language isn't used anymore in this course...

Features:

• supports natural numbers (N), binary stacks (S) and lists (L) as datatypes
• only a few simple and easy to understand built-in operations for each datatype -> it's really easy to learn how to write programs in a functional language!
• accepts "//" and "/**/" comments with the same semantics as in C/C++
  
• support for both call-by-name and call-by-value calling conventions (which is tricky to implement when translated to C; C has no support for call-by-name; note that MAKRO-expansion does not support recursive substitutions!)
• included EXP program of an LI-deducer - SLD resolution (Linear resoultion with Selection function of Definite clauses) - you can see how to implement it in a functional language based on "list-rewriting/-substitutions" and experiment with it to find out a little more about how PROLOG works (the program will print current goal & chosen unifying rule with the resolvent after each step!)
• [May, 23th, 2007]: includes a quine written in EXP (requires the new EXP2C version to work). Scroll down on this page to inspect it immediately. A quine is a program which produces its source-code as its only output. I also wrote a short tutorial for writing a quine (included in the new EXP2C download); additionally you can download some of my quines for other programming languages here ([May, 28th, 2007]: currently features the languages Basic, C, Java, Smalltalk, Scheme, Forth).
  

Sample EXP programs (the function-bodies are taken from Prof. Salzer's "slides", except for the quine, which I've written myself):
Note: 'leer' is the german word for 'empty'

/* factorial:     e=x! with x=6, should yield 720*/
EXP(N) 
I(x) = 6; 
e=fact(x);
%fact = if =(x1,0) then 1 else *(fact(-(x1,1)),x1)

/* call-by-name vs. call-by-value  - in this example by-name terminates, by-value ends up in endless recursion */  
EXP(S)
call-by-name;  // if nothing is specified, call-by-value is assumed
I(x)=s1; // a stack that consits of "1"
r(F)=2;  // arity for F; only needed for call-by-name
r(G)=1;  // arity for G; only needed for call-by-name
e=F(x,x); // the initial call
%F = if istleer?(x2) then leer else F(G(x1), pop(x2))
%G = G(x1) 
 
/* bitwise AND */
EXP(S)
    I(a)=s10;
    I(b)=leer;
    e=AND(a, b);
%AND = if istleer?(x1) then
                if istleer?(x2) then leer
                else push0(AND(pop(x1), pop(x2)))
                else if ist0?(x1) then push0(AND(pop(x1), pop(x2)))
                else if ist1?(x2) then push1(AND(pop(x1), pop(x2)))
                else push0(AND(pop(x1), pop(x2)))


/* represent N in L; the numbers themselves are coded in the unary system */
EXP(L)
 
I(l1) = (i i i i i);  // this stands for 5
I(l2) = (i i i);  // this stands for 3
I(c) = i;
 
e = MAL(l1, l2);
 
%PLUS = if eq?(x1, nil) then x2
        else build(l_i, PLUS(rest(x1), x2))
%MIN = if eq?(x2, nil) then x1
       else MIN(rest(x1), rest(x2))
%MAL = if eq?(x1, nil) then nil
       else PLUS(x2, MAL(rest(x1), x2))
 
 
%LT = if eq?(MIN(x2, x1), nil) then false else true
%EQ = if eq?(x1, x2) then true else false


/* represent S in L */
EXP(L)
 
I(l) = (i o);
I(m) = (o i i o i);
 
e = PUSH0(l);
 
%PUSH0 = build(l_o, x1)
%PUSH1 = build(l_i, x1)
%POP = rest(x1)
 
%IST0 = if eq?(first(x1), l_o) then true else false
%IST1 = if eq?(first(x1), l_i) then true else false
%ISTLEER = if eq?(x1, nil) then true else false


/* represent L in L */
EXP(L)
I(l) = c;
I(m) = (A (B)  c);

e = ATOM(m);
 
%FIRST = first(x1)
%REST = rest(x1)
%BUILD = build(x1, x2)
 
%ATOM = if atom?(x1) then true else false
%EQ = if eq?(x1, x2) then true else false


/* a quine in EXP
 * NOTE: for the sake of readability, the "layout" is not identic to the output
 * I also added a comment here, which is not part of the output
 * simply run exp2c once on this source and redirect the output to a new EXP-file (looks similar to this - depending on your OS):
 *     runWin32_exp2c.bat quine.exp.c > quine_correct.exp.c
 *     or
 *     runLinux_exp2c.sh quine.exp.c > quine_correct.exp.c
 * finally you'll be rewarded with the actual quine
 */
EXP ( L )

//I(a) Begin
I(a)= ( 

I(b) = (EXP ( L ) I(a)= );
I(c)=e;
I(d)==;
I(e)=;;
I(f)=(helper(x1,x4), x2, x3, x4, x5, x6);

e=funcquine( b , a, c, d, e, f);

%strip =
if eq?(first(rest(x1)),nil) then x4
else strip(helper(x1, x2), x2, x3, x4)

%hd = if eq?(print_list(x2), ()) then strip(x1, x1, x2, x3) else strip(x1, x1, x2, x3)

%hz = if eq?(print_list(x1), ()) then hd(x1,x2,x3) else hd(x1,x2,x3)
%helper = if eq?(print_list(first(x1)), x2) then rest(x1) else rest(x1)

%funcquine=
if eq?(first(x1), nil)
then hz(x2, x5,x6)
else funcquine(helper(x1,x4), x2, x3, x4, x5, x6)

    );
//I(a) End

I(b) = (EXP ( L ) I(a)= );
I(c)=e;
I(d)==;
I(e)=;;
I(f)=(helper(x1,x4), x2, x3, x4, x5, x6);

e=funcquine( b , a, c, d, e, f);

%strip =
if eq?(first(rest(x1)),nil) then x4
else strip(helper(x1, x2), x2, x3, x4)

%hd = if eq?(print_list(x2), ()) then strip(x1, x1, x2, x3) else strip(x1, x1, x2, x3)

%hz = if eq?(print_list(x1), ()) then hd(x1,x2,x3) else hd(x1,x2,x3)
%helper = if eq?(print_list(first(x1)), x2) then rest(x1) else rest(x1)

%funcquine=
if eq?(first(x1), nil)
then hz(x2, x5,x6)
else funcquine(helper(x1,x4), x2, x3, x4, x5, x6)



// towers of hanoi in EXP
//note: since we are using lists as datatype, we must encode
//any natural number as a list, so e.g. "3" == "(i i i)"

EXP(L)
I(num)=(i i i);
I(A)=(stick A);
I(B)=(stick B);
I(C)=(stick C);
e=toh(num, A, B, C);

%toh=
if eq?(x1, build(l_i, nil)) then move_disk(x2, x3)
else _3LIST(
            toh(rest(x1), x2, x4, x3),
            move_disk(x2, x3),
            toh(rest(x1), x4, x3, x2)
          )

%move_disk=_3LIST(x1, l_to, x2)

%_2LIST = build(x1, build(x2,nil))
%_3LIST = build(x1, _2LIST(x2, x3))