ENTRE

Entre is an interpreter for a toy functional programming language. Its main purpose is to evaluate expressions in as straightforward a manner as possible, showing each and every step, so that the user can follow the computation.
Entre syntax is a subset of Haskell syntax. Entre can manipulate integers and Booleans and lists and functions of these. Entre has no type checker. So computations are free to "go wrong" in all the ways that a type checker would prevent. Entre can't perform pattern matching and doesn't have tuples or algebraic data types.
Entre is not lazy like Haskell. In fact, it's eager to try to simplify arguments before invoking functions, so the steps are easy to read.
Entre's strength is in its ability to demonstrate functions, substitution, recursion, Currying and higherorder functions in action.
Entre can be used in two ways:
Entre works fastest and best as a compiled standalone program. See compiling and installing entre below.
Entre can run in the Hugs interpreter on any platform, if enough memory is available. (There are some problems with command line entry. See the known problems list below.)
Entre runs the same either way, once it has been launched. How you launch, depends on the whether you are using a compiled version, or Hugs and under what operating system.
In the examples below, text which is underlined is text you type. Dollar signs ($) represent the command line prompt, which you don't type. Press the enter or return key after typing the command.
If entre has been compiled and installed on your machine and is in your current path, you should be able to launch entre by typing:
$ entre
You should put all of the entre source files (files ending in ".lhs") into one directory, along with any entre scripts (files ending in ".es") you wish to use. Make this directory your current directory, e.g.
$ cd entre
If Hugs has been compiled and installed on your machine and is in your current path, you should be able to launch Hugs by typing:
$ hugs
Then load entre by typing the following command at the Hugs prompt, "?".
? :l entre.lhs
Then launch entre, by typing:
? entre
You should put all of the entre source files (files ending in ".lhs") into one folder, along with any entre scripts (files ending in ".es") you wish to use.
To launch Hugs and load entre, drag ad drop the icon for the file "entre.lhs" onto the icon for the Hugs application.
Then launch entre, by typing:
? entre
When entre starts it prints these messages.
Welcome to ENTRE (Explicit Naive Term Rewriting Engine). 90% sugar free! Reading prelude: prelude.es Type ":?" for help. entre?
The messages identify the program, and show you that it is loading the prelude script. "entre?" is the prompt at which you type entre commands.
The ":?" command displays a list of available commands.
entre? :? Commands: :q Quit ENTRE. :? Print this message. expression Evaluate this expression. :s expression Silently evaluate expression. :w expression Walk the expression, one step at a time. :f expression Evaluate the expression, printing fewer steps. :wf expression Evaluate the expression, using :w and :f name = expression Bind name to expression. name := expression Bind name to evaluated expression. f x y ... = expr Define function. :p Print all bindings. :r "filename" Read commands from file. entre?
The ":q" command quits the program.
Entre evaluates any expression typed to the prompt, showing its pedestrian workings as it goes. E.g.
entre? 3 + 4 * 5 => 3 + 4 * 5 => 3 + 20 => 23 entre?
The command ":s" before an expression tells entre to evaluate the expression silently; i.e. not printing anything except the answer.
entre? :s 3 + 4 * 5 => 23 entre?
The command ":w" before an expression tells entre to evaluate the expression at a walking pace; i.e. printing the evaluation steps one at a time, waiting until the return/enter key is pressed before proceeding.
entre? :w 3 + 4 * 5 => 3 + 4 * 5 [RETURN] => 3 + 20 [RETURN] => 23 entre?
The command ":f" before an expression tells entre to evaluate the expression printing fewer steps. (See the example given for Recursive functions below).
The command ":wf" before and expression combines the actions of the ":w" and ":f" commands.
A command of the form name = expression binds the name to the expression. No evaluation of the expression takes place. This name can be used in subsequent expressions.
The names that have been bound so far can be listed with the the ":p" command. E.g.
entre? a = 3 + 4 * 5 entre? :p a = 3 + 4 * 5 entre? 2 * a => 2 * a => 2 * (3 + 4 * 5) => 2 * (3 + 20) => 2 * 23 => 46 entre?
If you wish expressions to be evaluated silently by default, type the binding:
entre? print_mode = s
Note: There is an underscore (_) in the name "print_mode", which can also be bound to the names, "w", "f" and "wf" to make those the defaults. To reset entre to full verbosity, bind print_mode to anything else, e.g.
entre? print_mode = full verbosity entre?
A command of the form name := expression binds the name to the expression. The expression is simplified as much as possible before the binding takes place. This name can be used in subsequent expressions.
entre? a := 3 + 4 * 5 entre? 2 * a => 2 * a => 2 * 23 => 46 entre?
The command ":r "filename"" reads a file of bindings (a script). The entire filename must be typed in double quotes.
Integers are written as a sequence of decimal digits.
Take care: A minus sign in front of a sequence of digits is either taken as a binary infix minus or a unary prefix minus, depending on the context. It is not parsed immediately as part of a number. E.g.
entre? 1  2 => 1  negate 2 => 1  2 => 3 entre?
Another thing to be careful of:  starts a comment.E.g.
entre? 12 => 1 entre?
Integers have unlimited precision.
Boolean values are True and False.
Entre has the following basic operators.
operator  name  example 

+  plus  33 + 3 = 36 
  minus  33  3 = 30 
  unary minus (negate)   24 = 24 
*  multiply  10 * 24 = 240 
`div`  integer division  31 `div` 3 = 10 
`mod`  modulus  31 `mod` 3 = 1 
<  less than  10 < 24 = True False < True = True 
<=  less than or equals  10 <= 24 = True 10 <= 10 = True 
>  greater than  10 > 24 = True 
>=  greater than or equals  10 >= 24 = False 
==  equals  10 == 24 = False False == False = True 
/=  not equals  10 /= 24 = True False /= False = False 
&&  and  True && False = False 
  or  True  False = True 
These operators have binding powers (precedence) according to table B below. Parentheses can be used to override the normal order of precedence.
The binary operators in the table above also have the property of associativity to the left. E.g.
yields the same answer asentre? 10  3  2 => 10  3  2 => 7  2 => 5
but this expression is different.entre? (10  3)  2 => 10  3  2 => 7  2 => 5
entre? 10  (3  2) => 10  (3  2) => 10  1 => 9
Grouping with parentheses on the left has no effect, but grouping on the right may change the result.
An expression is a sequence of characters which represents a value. Examples:
42 42 42 + 35 42 + 35 `div` 2 3 + 4 * 5 (3 + 4) * 5 10 < 24 True 1 + 3 < 45
There are more ways to write expressions introduced below, but however they are written, they all represent a value.
A name is any sequence of letters, digits, underscores and apostrophes, starting with a lower case letter.
A binding is an assertion of the form "name = expression".
Bindings may be typed at the command line prompt or are more commonly typed into files for loading into entre (scripts).
A binding associates the name with the expression.
A binding of the form "name := expression" binds the name to the expression after it has been reduced as much as possible.
Scripts are files of bindings, ready to be loaded by entre.
Blank lines in scripts are ignored.
Comments begin with the sequence "" and extend to the end of the line.
Bindings are as described above. Bindings in scripts can be continued across multiple lines so long as all symbols belonging to the binding after the = or := operator stay to the right of = or := operator. This is the "offside" rule. E.g.
f = 1  This will work + 2 g = 1  This will NOT work + 2
Functions may be defined using lambda expressions.
Functions defined this way are just expressions. They do not have to be bound to a name (unless the function is to be recursive).
This is a function that adds 1 to numbers: "\x > x + 1".
The "\x" part introduces a dummy name to define the function in terms of. "x" represents the value to which the function is to be applied.
The "x + 1" part shows the value that the function returns when applied to x.
This function can be applied to a number by juxtaposition. E.g.
entre? (\x > x + 1) 41 => (\ x > x + 1) 41 => 41 + 1 => 42 entre?
We can see the function application step in the above example. When the function is applied "41" is substituted for "x" in the expression that defines the function result.
Expressions which are functions are typically bound to names, so they are easy to remember and reuse. E.g.
entre? square = \x > x * x entre? square 3 => square 3 => (\ x > (x * x)) 3 => 3 * 3 => 9 entre?
Functions may have more than one argument if the defining lambda expressions are nested. E.g. the following example defines the less than or equal function.
entre? le = \x > \y > x < y  x == y entre? le 3 6 => le 3 6 => (\x y > x < y  x == y) 3 6 => (\y > 3 < y  3 == y) 6 => 3 < 6  3 == 6 => True  3 == 6 => True  False => True entre?
You will have noticed in the previous example that entre uses the abbreviated form \x y > for \x > \y >. This is also accepted as input.
Since the applications are performed left to right, function application is left associative.
Make sure that the dummy names used to define each function are different when the lambda expressions are nested.
An alternative way exists to define functions and bind them to names. That is to write the names of the arguments after the function name and before the =. E.g.
entre? add x y = x + y entre? :p add = \x y > x + y entre? add 3 4 => add 3 4 => (\x y > x + y) 3 4 => (\y > 3 + y) 4 => 3 + 4 => 7 entre?
Note that entre converts this notation for functions to the normal lambda expression form, in order to work with them.
An expression of the form "if expr1 then expr2 else expr3" is a conditional expression. The value of the expression is expr2 if expr1 equals True or expr3 if expr1 equals False.
It follows that expr1 must evaluate to a Boolean value (True or False). expr2 and expr3 may be of any type. E.g.
entre? not p = if p then False else True entre? not True => not True => (\p > if p then False else True) True => if True then False else True => False entre?
Functions bound to a name may reference that name. E.g.
entre? fact n = if n <= 1 then 1 else n * fact (n  1) entre? fact 3 => fact 3 => (\n => if n <= 1 then 1 else n * fact (n  1)) 3 => if 3 <= 1 then 1 else 3 * fact (3  1) => if False then 1 else 3 * fact (3  1) => 3 * fact (3  1) => 3 * fact 2 => 3 * (\n => if n <= 1 then 1 else n * fact (n  1)) 2 => 3 * (if 2 <= 1 then 1 else 2 * fact (2  1)) => 3 * (if False then 1 else 2 * fact (2  1)) => 3 * (2 * fact (2  1)) => 3 * (2 * fact 1) => 3 * (2 * (\n => if n <= 1 then 1 else n * fact (n  1)) 1) => 3 * (2 * (if 1 <= 1 then 1 else 1 * fact (1  1))) => 3 * (2 * (if True then 1 else 1 * fact (1  1))) => 3 * (2 * 1) => 3 * 2 => 6 entre? :f fact 6 => fact 6 => 6 * fact 5 => 6 * (5 * fact 4) => 6 * (5 * (4 * fact 3)) => 6 * (5 * (4 * (3 * fact 2))) => 6 * (5 * (4 * (3 * (2 * fact 1)))) => 6 * (5 * (4 * (3 * (2 * 1)))) => 6 * (5 * (4 * (3 * 2))) => 6 * (5 * (4 * 6)) => 6 * (5 * 24) => 6 * 120 => 720 entre?
Lists are used to represent sequences of values.
The simplest list is the empty list: "[]".
Elements are added to the empty list by attaching them to the front with the cons operator, ":".
One element: 1 : [] Two elements: 2 : 1 : [] Three elements: 3 : 2 : 1 : []
The : operator is used to construct lists. "Cons" is short for "constructor".
The expression on the left of the : is an element. The expression on the right of : must be a list of the same type of element.
For the above examples to be correct, : must associate to the right; i.e. these are equivalent
1 : 2 : 3 : [] 1 : (2 : (3 : []))
but this is different and not actually a valid list at all.
((1 : 2) : 3) : []
Lists may also written within square brackets, with commas separating the elements. Entre will print lists in this format when it can.
Lists containing ranges of integral values can be defined using dotdot lists, and in these examples.
entre? [2..2] => [negate 2, negate 2 + 1 .. 2] => [2, negate 2 + 1 .. 2] => [2, 2 + 1 .. 2] => [2, 1 .. 2] => 2 : [1, 0 .. 2] => 2 : 1 : [0, 1 .. 2] => 2 : 1 : 0 : [1, 2 .. 2] => 2 : 1 : 0 : 1 : [2, 3 .. 2] => 2 : 1 : 0 : 1 : 2 : [3, 4 .. 2] => [2, 1, 0, 1, 2] entre? [1, 3 .. 10] => [1, 3 .. 10] => 1 : [3, 5 .. 10] => 1 : 3 : [5, 7 .. 10] => 1 : 3 : 5 : [7, 9 .. 10] => 1 : 3 : 5 : 7 : [9, 11 .. 10] => 1 : 3 : 5 : 7 : 9 : [11, 13 .. 10] => [1, 3, 5, 7, 9] entre?
The "==" and "/=" operators can can be used to compare lists, but only if one of the lists is empty.
The predefined function "head" can be used to return the head (frontmost) element of a nonempty list. E.g.
entre? head [1, 2, 3] => head [1, 2, 3] => 1 entre?
The predefined function "tail" can be used to return the tail (what's left after the head) of a nonempty list. E.g.
entre? tail [3, 2, 1] => tail [3, 2, 1] => [2, 1] entre?
Example: a function to return the length of a list.
It is possible to build and work with lists of lists. E.g.entre? length xs = if xs == [] then 0 else 1 + length (tail xs) entre? :f length [1, 3 .. 10] => length [1, 3, 5, 7, 9] => 1 + length [3, 5, 7, 9] => 1 + (1 + length [5, 7, 9]) => 1 + (1 + (1 + length [7, 9])) => 1 + (1 + (1 + (1 + length [9]))) => 1 + (1 + (1 + (1 + (1 + length [])))) => 1 + (1 + (1 + (1 + (1 + 0)))) => 1 + (1 + (1 + (1 + 1))) => 1 + (1 + (1 + 2)) => 1 + (1 + 3) => 1 + 4 => 5 entre?
entre? :f length [[], [1], [1,2]] => length [[], [1], [1, 2]] => 1 + length [[1], [1, 2]] => 1 + (1 + length [[1, 2]]) => 1 + (1 + (1 + length [])) => 1 + (1 + (1 + 0)) => 1 + (1 + 1) => 1 + 2 => 3 entre?
When entre is asked to evaluate something it can not, it returns the value "Undefined". E.g.
entre? 5 + 4 `div` 0 => 5 + 4 `div` 0 => 5 + Undefined => Undefined entre?
Functions can have other functions as arguments. E.g.
entre? compose f g x = f (g x) entre? a x = x * x entre? b x = x + 2 entre? compose a b 2 => compose a b 2 => compose (\x > x * x) b 2 => (\f g x > f (g x)) (\x > x * x) b 2 => (\g x > (\x > x * x) (g x)) b 2 => (\g x > (\x > x * x) (g x)) (\x > x + 2) 2 => (\x > (\x > x * x) ((\x > x + 2) x)) 2 => (\_x > _x * _x) ((\_x > _x + 2) 2) => (\_x > _x * _x) (2 + 2) => (\_x > _x * _x) 4 => 4 * 4 => 16 entre? compose b a 2 => compose b a 2 => compose (\x > x + 2) a 2 => (\f g x > f (g x)) (\x > x + 2) a 2 => (\g x > (\x > x + 2) (g x)) a 2 => (\g x > (\x > x + 2) (g x)) (\x > x * x) 2 => (\x > (\x > x + 2) ((\x > x * x) x)) 2 => (\_x > _x + 2) ((\_x > _x * _x) 2) => (\_x > _x + 2) (2 * 2) => (\_x > _x + 2) 4 => 4 + 2 => 6 entre?
There are more examples of higherorder functions in the prelude.
highest binding power  function application 
.  * `div` `mod` 
.  +  
.  < <= > >= == /= 
.  : 
.  && 
lowest binding power   
name and arguments  returns  where defined 

abs x  absolute value of x  builtin 
compose f g  composition of functions f and g  prelude.es 
div x y  same as x `div` y  builtin 
elem x xs  True if x is an element of list xs, False otherwise  prelude.es 
filter f xs  the list of elements of xs for which f returns True  prelude.es 
flip f  a function that returns the same as f, but with f's two arguments reversed  prelude.es 
foldl f z xs  the result obtained by combining the elements of xs using f, lefttoright, or z if xs is empty  prelude.es 
foldr f z xs  the result obtained by combining the elements of xs using f, righttoleft, or z if xs is empty  prelude.es 
head xs  first element of list xs  builtin 
length xs  number of elements in list xs  prelude.es 
map f xs  the list of results obtained by applying f to every element of xs  prelude.es 
mod x y  same as x `mod` y  builtin 
negate x  x  builtin 
not x  logical negation of x  builtin 
signum x  1, 0, or 1, such that abs x * signum x == x  builtin 
tail xs  all elements after the first element of list xs  builtin 
A version of entre has been created that conducts its dialogue with the user using a WWW form. Try it.
Entre is available at http://www.cit.gu.edu.au/~arock/entre/ .
The README file explains what each file at this location is for.
Entre can be compiled by the Glasgow Haskell Compiler, GHC.
If you have GHC installed, use the supplied Makefile to either:
$ make entre
or
$ make entre.cgi
The binaries may be moved anywhere, as can the prelude file, "prelude.es".
If you have put "prelude.es" somewhere other than your current working directory set the environment variable ENTRE_PRELUDE to point to it. E.g.
setenv ENTRE_PRELUDE /usr/lib/entre/prelude.es
When running under Hugs 1.3 on UNIX, you can't backspace to correct command lines. Requires a fix to Hugs' getLine implementation.
When running under Hugs 1.3 on a Macintosh, command lines get echoed twice. Requires a fix to the Hugs Macintosh port.
Last modified 25/3/98 by
Andrew
Rock A.Rock@cit.gu.edu.au http://www.cit.gu.edu.au/~arock/ 