This package realises an interpreter for the functional language
EXP described in the lecture notes
"Einführung in die Theorie der Informatik" by G. Salzer
which we call EXPi. EXPi was written by Christoph Rettig as part of
the computer science curriculum in an Informatik-Praktikum.
The purpose of the interpreter is, given as input a specification of
to do an evaluation of the expression under this given circiumstances
just like it is done manually in the mentioned lecture notes.
This should give you the opportunity to experiment with the language
EXP, code larger programs and look at the results without always having
to do the evaluation by hand.
- an expression to evaluate
- an individual variable symbol environment
- an functional variable symbol environment
- a calltype
- the name of some datatype (yes, there are a few of them)
EXPi is completely written and tested in prolog (exactly: Sicstus
Prolog v3.6) and is freely available at
I did not have the time to test it with other (yes, that's the
point: freely-available) prolog platforms but if anybody out there wants to
do the job: there is a file named expi_depend.pl which (I hope so) will
include an overlay for all sicstus-specific relations (I think, I only
used atom_chars/2 and number_chars/2).
I don't know, if some other prolog platforms (e.g. SWI-prolog) do use the
same module concept as Sicstus but if not, that would also be something
to work over.
Maybe I will do this by myself but for the moment it doesn't look so :(
For those people that don't use Sicstus Prolog (and also don't want to
port this package) I have written a java-based
interface which produces the same results as working directly on a
The simplest way to work with EXPi is by
- writing an input file
- passing this file to
- the prolog interpreter
- the java interface
Step 1 - Writing the input file
The input file has the following format (given in BNF):
<input file> --> <evaluationlist>
<evaluationlist> --> '<evaluations' <evaluations> '>'
<evaluations> --> <eval> <evaluations>
| < eval >
<eval> --> '<eval"' <string> '"'
'ivsenv="' <ivsenv> '"'
'exp="' <exp> '"'
<calltype> --> 'cnb'
<datatype> --> 'numbers'
<fvsenv> --> '"' <fenv> '"' <fvsenv>
<fenv> --> '@' <fenvname> '=' <exp>
<fenvname> --> <char-or-digit> <fenvname>
<char-or-digit> --> <char>
<number> --> '0'
| <not-null-digit> <number>
<string> --> <char> <string>
| <digit> <string>
<char> --> <lower-char>
<lower-char> --> 'a' | ... | 'z'
<upper-char> --> 'A' | ... | 'Z'
<digit> --> '0' | ... | '9'
<not-null-digit> --> '1' | ... | '9'
<ivsenv> --> 'I(' <ivs> ')=' <constant> <ivsenv>
<ivs> --> 'x' <number>
| 'y' <number>
| 'z' <number>
depends on the used datatype, stands for the empty-word
and stands for well formed expressions (it's syntax changes with the
For a description on how to build complex expressions read the lecture
As you may have mentioned there are four datatypes which can be used.
With each datatype, the syntax of constants, the domain of it and
the name of functions and predicates changes!!
Now for a specification of these (also in BNF):
Datatype of binary stacks:
<constants> --> 'leer'
<domain> --> 'leer'
<01sequence> --> '0' <01sequence>
| '1' <01sequence>
<functions> --> 'push0'
<predicates> --> 'ist0?'
Datatype of lists:
<constants> --> ''('')''
<domain> --> <lists>
<atom_> --> <char> <atom_>
<atom> --> ''' <atom_> '''
<list> --> <atom>
| ''('' <lis> '')''
<lists> --> <list> <lists>
<functions> --> 'first'
<predicates> --> 'atom?'
Datatype of numbers:
<constants> --> <number>
<domain> --> <number>
<functions> --> 'plus'
<predicates> --> 'smaller'
Datatype of strings:
<constants> --> <string>
<domain> --> <string>
<functions> --> 'ring'
<predicates> --> 'pref'
All these datatypes are also describes in the lecture notes, so read
the corresponding pages to be sure of the actual semantic.
Following we give an example of such an input file:
<eval "ue 3.6"
calltype = cbn
datatype = numbers
fvsenv = "@F = prod(if equal(x1,0) then x2 else minus(1,x1),x2)"
ivsenv = "I(x) = 1 I(z) = 1"
exp = "F(minus(1,x),plus(z,1))"
<eval "ue 3.7"
calltype = cbn
datatype = binarystacks
fvsenv = "@F = if istleer?(x2) then leer else F(G(x1), pop(x2))"
"@G = G(x1)"
ivsenv = "I(x) = 1"
exp = "F(x,x)"
<eval "ue 3.19"
calltype = cbn
datatype = lists
fvsenv = "@F = build(x1,'('')')"
ivsenv = "I(y) = '(' 'A' ')'"
exp = "if atom?(F(y)) then F(F(y)) else first(F(y))"
Step 2 - Using the input file
Once you have written the input file (and saved it under )
you can pass over the work to EXPi.
Using the prolog interpreter:
If you are using Sicstus Prolog you only need to start up the
cd <path to EXPi>/prolog/
After this type
sicstus -l ./expi.pl
where <inputfilename> stands for the name you gave to your input file and
<path to input file> is the path to your input file.
Using the Java-interface:
The java applet has two text areas, where the upper one is the
input area. You have to type (or cut&paste) you input there and click
on the "Start EXP Interpreter" button to start the evaluation.
After some time the result of the evaluation will appear in the lower
textarea (the output area).
There are two further buttons to clear the windows before another
evaluation (if wanted).
Something on versions
EXPi has now grown to version 2.6 which (I hope so :) will be the final
If there are any questions, comments, bugs, report them to
(and maybe I'm willing to read and answer your mails).