EXPi v2.6


Introduction

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.

Availability

EXPi is completely written and tested in prolog (exactly: Sicstus Prolog v3.6) and is freely available at http://www.logic.at/lvas/eti/EXPi/EXPi.tgz

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 prolog interpreter.

Description

The simplest way to work with EXPi is by

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> '"'
			'calltype="' <calltype>
			'datatype="' <datatype>
			'fvsenv=' <fvsenv>
			'ivsenv="' <ivsenv> '"'
			'exp="' <exp> '"'


<calltype> -->		'cnb'
			| 'cbv'

<datatype> -->		'numbers'
			| 'binarystacks'
			| 'lists'
			| 'strings'

<fvsenv> -->		'"' <fenv> '"' <fvsenv>
			| <empty>

<fenv> -->		'@' <fenvname> '=' <exp>

<fenvname> -->		<char-or-digit> <fenvname>
			| <char-or-digit>

<char-or-digit> -->	<char>
			| <digit>

<number> -->		'0' 
			| <not-null-digit> <number>

<string> -->		<char> <string>
			| <digit> <string>

<char> -->		<lower-char>
			| <upper-char>

<lower-char> -->        'a' | ... | 'z'

<upper-char> -->        'A' | ... | 'Z'

<digit> -->		'0' |  ... | '9'

<not-null-digit> -->	'1' | ... | '9'

<ivsenv> -->		'I(' <ivs> ')=' <constant> <ivsenv>
			| <empty>

<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 used datatype).
For a description on how to build complex expressions read the lecture notes!

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>
<01sequence> -->	'0' <01sequence>
			| '1' <01sequence>
			| '0'
			| '1'
<functions> -->		'push0'
			| 'push1'
			| 'pop'
<predicates> -->	'ist0?'
			| 'ist1?'
			| 'istleer?'

Datatype of lists:

<constants> -->		''('')''
			| <atom>
<domain> -->		<lists>
<atom_> -->		<char> <atom_>
			| <char>
<atom> -->		''' <atom_> '''
<list> -->		<atom>
			| ''('')''
			| ''('' <lis> '')''
<lists> -->		<list> <lists>
			| <list>
<functions> --> 	'first'
			| 'rest'
			| 'build'

<predicates> -->	'atom?'
			| 'eq?'

Datatype of numbers:

<constants> -->		<number>
<domain> -->		<number>
<functions> -->		'plus'
			| 'minus'
			| 'prod'
<predicates> -->	'smaller'
			| 'equal'

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:

<evaluations
  <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 interpreter with

	cd <path to EXPi>/prolog/ 
sicstus -l ./expi.pl

After this type

	evalfile("").
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 version.
If there are any questions, comments, bugs, report them to goth@logic.at (and maybe I'm willing to read and answer your mails).