Programming Languages

back to main page

On this page I'll put some of my experiments with several programming languages. I've written several compilers and interpreters, too. Don't expect too much, though! :-)



Lambda Calculus Interpreter
Here is a version for my EXP2C compiler: lambda.exp.zip
EXP2C (May, 23th, 2007)


EXP2C (old)
My own small compiler (translates EXP code to C code). EXP is a functional language that is quite similar to LISP. I also included a program that implements an automatic LI-deducer (which is the basic idea behind the PROLOG-solver).
[You will need VC6 or gcc if you want the translated program to actually run on your computer...]

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))

kc-scripts
download (171.7 KB)
Try these scripts with the "kentastic" tool evaldraw, available at http://www.advsys.net/ken/download.htm#evaldraw




back to main page