[LOGO]

ENTRE
Explicit Naive Term Rewriting Engine

Contents

  • What is entre?
  • Using entre
  • Launching compiled entre
  • Launching entre using Hugs on UNIX or DOS
  • Launching entre using Hugs on a Macintosh
  • Entre commands
  • The entre language
  • Atomic data types
  • Basic operators
  • Expressions
  • Bindings
  • Scripts
  • Functions
  • Conditional expressions
  • Recursive functions
  • Lists
  • Undefined values
  • Higher-order functions
  • Summary of operator binding powers
  • Summary of predefined functions
  • entre.cgi
  • Obtaining entre
  • Compiling and installing entre
  • Known problems
  • What is entre?

    Entre is an interpreter for a toy functional programming language. Its main purpose is to evaluate expressions in as straight-forward 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 higher-order functions in action.

    Using entre

    Entre can be used in two ways:

    as a compiled, stand-alone program; and

    Entre works fastest and best as a compiled stand-alone program. See compiling and installing entre below.

    in the Hugs interpreted environment.

    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.

    Launching compiled entre

    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
    

    Launching entre using Hugs on UNIX or DOS

    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
    

    Launching entre using Hugs on a Macintosh

    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
    

    Entre commands

    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.

    The entre language

    Atomic data types

    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? 1--2
    => 1
    entre?
    

    Integers have unlimited precision.

    Boolean values are True and False.

    Basic operators

    Entre has the following basic operators.

    Table A: 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
    && andTrue && 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.

    entre? 10 - 3 - 2
    => 10 - 3 - 2
    => 7 - 2
    => 5
    
    yields the same answer as
    entre? (10 - 3) - 2
    => 10 - 3 - 2
    => 7 - 2
    => 5
    
    but this expression is different.
    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.

    Expressions

    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.

    Bindings

    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

    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

    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.

    Conditional expressions

    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? 
    

    Recursive functions

    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

    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 dot-dot 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 (front-most) element of a non-empty 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 non-empty 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.

    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? 
    
    It is possible to build and work with lists of lists. E.g.
    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?
    

    Undefined values

    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? 
    

    Higher-order functions

    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 higher-order functions in the prelude.

    Summary of operator binding powers

    Table B: Summary of operator binding powers.
    highest binding power function application
    . * `div` `mod`
    . + -
    . < <= > >= == /=
    . :
    . &&
    lowest binding power ||

    Summary of predefined functions

    Table C: Summary of predefined functions.
    name and arguments returns where defined
    abs x absolute value of x built-in
    compose f g composition of functions f and g prelude.es
    div x y same as x `div` y built-in
    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, left-to-right, or z if xs is empty prelude.es
    foldr f z xs the result obtained by combining the elements of xs using f, right-to-left, or z if xs is empty prelude.es
    head xs first element of list xs built-in
    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 built-in
    negate x -x built-in
    not x logical negation of x built-in
    signum x -1, 0, or 1, such that abs x * signum x == x built-in
    tail xs all elements after the first element of list xs built-in

    entre.cgi

    A version of entre has been created that conducts its dialogue with the user using a WWW form. Try it.

    Obtaining entre

    Entre is available at http://www.cit.gu.edu.au/~arock/entre/ .

    The README file explains what each file at this location is for.

    Compiling and installing entre

    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

    Known Problems

    Command line entry (Hugs, UNIX)

    When running under Hugs 1.3 on UNIX, you can't backspace to correct command lines. Requires a fix to Hugs' getLine implementation.

    Command line entry (Hugs, Macintosh)

    When running under Hugs 1.3 on a Macintosh, command lines get echoed twice. Requires a fix to the Hugs Macintosh port.


    [ABR]
    Last modified 25/3/98 by Andrew Rock
    A.Rock@cit.gu.edu.au
    http://www.cit.gu.edu.au/~arock/