     [file version.texi not included]

epsilon
*******

This is the manual documenting GNU epsilon (version VERSION, last updated on UPDATED).

GNU epsilon is a functional language implementation.

Copyright © 2002, 2003, 2004 Luca Saiu

     Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with the Invariant Sections being ``GNU General Public License'', the Front-Cover texts being (a) (see below), and with the Back-Cover texts being (b) (see below).

     (a) The FSF's Front-Cover Text is

          A GNU Manual

     (b) The FSF's Back-Cover Text is

          You have freedom to copy and modify this GNU Manual, like GNU software.

     A copy of the license is included in the section entitled ``GNU Free Documentation License''.

     [file gpl.texi not included]

Part I - Introduction to epsilon
********************************

Introduction
************

This book is the comprehensive documentation of the epsilon functional programming language, library and tools.

In this book ``epsilon'' is always written in lower case, and even indicated as a lower case ``e'' in acronyms. This convention and the name of the language itself come from the idea that epsilon is intended to be a simple language with uniform syntax, easy to learn --- which however does not prevent it from being powerful and expressive.

epsilon is thought to be a production language, useful for writing real applications. It has an elegant type system, compositional semantics, referential transparency; it will be also easy to write compilers and interpreters in epsilon. But all these features are intended to help writing applications, and were not implemented only for the sake of creating a beautiful conceptual model. Also the default library has its weight, and it will be worked on as much as possible.

epsilon is a young project, and many things still remain to be completed or rewritten. Help is welcome.

Suggestions, bug-reports and comments
=====================================

This book is not finished yet. For any comment, suggestion or correction you can send us a message using the public mailing list bug-epsilon@gnu.org. Documentation problems are not unlike bugs, and any input from users aiming to improve the quality of this book is precious.

Please understand that Luca Saiu's English is not native, and as such it is surely far from being perfect; any reporting of misspelling, or generally of any mistake, is welcome. You can use bug-epsilon@gnu.org also for this.

If you need help for using GNU epsilon you can write to help-epsilon@gnu.org.

Audience
========

In this book we do not assume any previous knowledge of functional programming, nor of programming altogether; nonetheless some previous programming experience will ease reading.

The functional programming tutorial explains everything is needed to start, and the following chapters introduce concepts as they are needed. There should be no forward-references, so this book can be mostly read sequentially, from beginning to end. Some sections, however, are primarily meant as reference documentation, and you can safely just skim them in a first reading, and rewiew them with more attention at the time you actually need them. We are referring, first of all, to the chapters about Library and Internals.

History
=======

The epsilon language was born at the end of 2001 as a small programming project (hence its name: the Greek letter epsilon is used in mathematics to indicate small constants (A late
thought: epsilon is also used to express errors in numerical
analysis. Fun.)), a way to experiment with the implementation of functional machines. That first implementation was fully written in C (with flex and Bison), including the compiler. The code could only be executed via a virtual machine written in C for that purpose, the LVM. The LVM managed memory with a reference counter, later replaced by the Boehm-Demers garbage collector.

In the winter of 2002, while playing with the language and adding new features the author Luca Saiu became more and more impressed by the power and expressivity of the functional paradigm and decided to make epsilon a ``real'' language: many important features were added at that time, including type inference, polymorphism, modules and abstract types.

Additions from the spring and summer of 2002 are garbage collector support, concrete types and exceptions. In Autumn 2002 the new abstract machine, the epsilon Abstract Machine or eAM, was started. The eAM works generating fast C code from the epsilon Abstract Machine Language (eAML), an intermediate code representation.

In Autumn 2002 Matteo Golfarini joined the project. In this period the eAM, epsilonlex and the purely functional I/O system were developed.

On 27th December 2002 epsilon was officially approved as part of the GNU Project (See http://www.gnu.org for information about the GNU Project.). Richard Stallman asked to enable epsilon to generate also Scheme as target code, so that epsilon can be used as an extension language for applications supporting GNU Guile (See http://www.gnu.org/software/guile for information about Guile.). Scheme generation from eAML is still at an experimental stage, but works.

The most recent important additions are the peephole optimizer and the eAM garbage collector. The collector works, is fast and reliable, but is not yet incremental and could be made parallel with relatively little work.

The eAM was essentially completed in Autumn 2003. The epsilonlex scanner-generator worked and was usable, and the epsilonyacc parser-generator was planned as the next step. Some new features introduced in late 2003 are C-libraries (a clean an easy way to extend the eAM with compiled, dynamically-loaeded C code), support for graphics and a library to handle S-expressions; epsilonlex was rewritten from scratch twice. The third implementation is much cleaner and faster than the previous ones. It still lacks the frontend, but the backend works very well. epsilonyacc was initially written for SLR grammars; it worked, but the author was not satisfied about the implementation, so he started a new rewrite from scratch. This new version supporting canonical LR(1) grammars is much better than the first one, and is next to be finished.

The author now plans to push the language towards the direction of Lisp, allowing runtime generation and execution of epsilon code, but retaining type-safety and the functional style. This will be the feature making the epsilon language really unique.

On 20th January 2004 around 11pm epsilonyacc bootstrapped (When we say ``bootstrap'' dealing with a tool like a scanner generator or a parser generator we mean generating the scanner or parser for the tool itself.) for the first time, followed by epsilonlex on 24th January, at 2:30am.

The language was influenced by ML, Haskell and Lisp, and in a minor way by the author's favourite imperative languages: Ada, Java, Python, C++, Smalltalk.

Functional programming tutorial
*******************************

This chapter introduces functional programming, not assuming any previous programming experience. If you already know functional programming you can just skim it.

What functional programming is
==============================

The functional paradigm is a very high-level programming style. ``High-level'' means that you program in an abstract way, ``far'' from the machine details and ``near'' your human way of thinking.

With functional programming you can safely ignore low-level details such as allocating and freeing memory; there is no need of using pointers or references; no need to know the internal representation of data structures. And don't even worry if you don't understand the above concepts. You will simply have no need of any such complication for using a functional language like epsilon.

Simplifying a bit, a program in a functional language is an expression, i.e. a piece of code which computes some value, and writes it back to you. In fact you can also use a functional language as a desk calculator. You can simply write 2 + 3 - 1, and get 4 as result.

Of course you can also do much complex things: you can write a program playing chess, or drawing graphics. You will even be able to write programs which generate other programs and execute them. Reading this book you will learn, among the other things, why and when this is useful.

Mathematical foundations
========================

For understanding the principles of functional programming you need to understand some very basic mathematical concepts. No advanced algoebra or analysis is needed, and this presentation will be informal.

Sets
----

A basic concept involved in most functional languages, including epsilon, is the idea of set. A set is a collection of homogeneous objects, such as number, words, or even real-world objects like people, houses, books. You can represent any object you can imagine in some way; the one thing you must remember is that a set is homogeneous: you choose some related objects to represent, and you can think of a set containing all of them.

A common example of a set is the set of natural numbers, written as N. It contains all integer numbers starting from zero: {0, 1, 2,...}

N contains an infinite number of elements.

The set of integer numbers contains all natural numbers and also negative numbers: {..., -3, -2, -1, 0, 1, 2, 3, ...}

You can find a representation for any object you can think; for example, say you are interested in representing your collection of books (for brevity let's assume you only have three):

{Tom Sawyer, Macbeth, Ulysses}

This latest set is finite.

In a programming language, when a given object a belongs to a set A, you say that a has type A. ``Has type'' is commonly written as a colon (:). For example, you can write ``-27 : integer'', or ``Ulysses : book''. By convention, sets have plural names but types have singular names: you write 0 : natural, and not 0 : naturals.

Functions
---------

A function is a relation from some elements in a set A and some elements of a set B (A and B can also be the same set.), with one constraint: for any element a belonging to A, the function must associate it with at most one element b of B.

If the function f is between the set A and the set B you can say that f maps A into B or that f is a function
from A to B, and write ``f : A -> B''. It is not a coincidence that we used the ``:'' operator; the function f is itself an element of a set, i.e. has a type: the set is the set of functions mapping A into B.

Functions can be applied, i.e. they can be given an object of type A (called argument or parameter (Formally there would be some difference between an argument and a parameter, but the difference is not important in this context. We will use these names interchangeably.)); when functions are applied they compute some value of type B as result, and they finally return it.

For example, the successor (The successor of a number n is n + 1; for example the successor of 34 is 35.) succ is a function with maps the integer set into the integer set itself. You can write ``succ : integer -> integer'', and indeed succ belongs to the set of functions from integer to integer. Let's see an example of application: ``succ 10'' gives as result 11 (you can write ``succ : 10 |-> 11'', or ``succ 10 = 11''). For applying a function, just write its argument after it. That's all.

If a function is undefined on one or more elements, we say it is partial, and if a is an element which f is undefined on we write ``f(a) = _|_'', or ``f : a |-> _|_''; read ``_|_'' as ``bottom''. Partial functions are very common and useful.

Another example: let g be the function which associates a book with its author (for example, it maps Ulysses into James Joyce). g is from book to author, so we can write ``g : book -> author''. Note that the constraint above compels us to associate one book to at most one author; we cannot use g if we want to describe the relationship between a book and its authors when they are more than one.

How could we solve this problem? Quite easy: let's use another function instead of g, say h, mapping the set of books into the set of sets of authors. For example, h maps The Capital into the set {Marx, Engels}: the element is mapped into only one element (even if this single element is a set containing two elements), so the constraint is respected. For the type, we can write ``h : book -> set of authors''.

Lambda-notation
===============

Let's get back to the succ example. How could we define succ?

A common way of defining functions is the lambda-notation (Since the letter
lambda) does not belong to most standard keysets, epsilon uses the character \ in its place. This convention was inspired by the language Haskell.: we can define the successor as \ n . n + 1. This means ``if we call n the argument of the function, then the value which the function computes is n + 1''.

One more example: let's define the reverse_number function (reverse_number maps 2 into 1/2, 3 into 1/3, etc.); very simple: the definition of reverse_number is \  x . 1/x. Note also that reverse_number is a partial function, since it is undefined on 0.

How can we define a function taking more than one argument? In lambda-notation you can simply write the arguments sequentially, between the \ and the .; for example, (say this function is called plus) \ x y . x + y. We can say that plus is a function with two arguments, or that plus is a function of arity 2.

There is another way to see the question: we could define plus as \ x . \ y . x + y; with this definition plus is a function which takes a parameter named x and returns another function which takes one parameter named y and returns x + y. This way of defining functions is called currying (The name is in honour of Haskell Curry, the mathematician who invented this technique.), and we can say that with this new definition plus is curried.

Note that with currying we can only use functions with one argument, without losing generality: \ x . \ y . x + y is a function taking only one argument, x; the object returned by the function is another function, also taking only one argument, y.

Another advantage of currying is the possibility of partial application: for example we can apply plus to only one argument: (\ x . \ y . x + y)
7 returns the function \ y . 7 + y (it's nothing so strange, just a function which takes an argument and returns it incremented by 7). Of course we can also pass two arguments:

(\ x . \ y . x + y) 7 3

returns 10, as expected. Just pay attention to the type:

plus : integer -> (integer -> integer)

plus is a function which takes an integer and returns a function which takes another integer and finally returns a third integer.

Curried functions are extensively used in epsilon.

A first introduction to recursion
=================================

Let's define a more complex function, the factiorial (The
factorial of n, written n!, is the product of all
natural numbers from 1 to n included. For example
4! = 1 * 2 * 3 * 4 = 24.
By definition 0! = 1.) function fact.

A way to see the factorial is this: if the argument (we call it n) is 0 then the result is 1, else the result is n times the factorial of (n - 1). You should convince yourself that this definition is correct: for example

5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 * 0! = 5 * 4 * 3 * 2 * 1 * 1

Ok, let's write it in a more formal way: the definition of fact is

     \ n . if n = 0 then
             1
           else
             n * (fact (n - 1))

Here is the main point: while defining fact we used fact itself. The technique we used, defining a function using itself, is called recursion.

Recursion is a very powerful tool; you can define many important and useful recursive functions, from simple ones such as fact to very complex ones.

Another simple example: the identity (The identity function
maps an object into itself. An obvious definition is \ n . n) function id, restricted to map integers to integers.

Let's define id as a recursive function. The idea is this: call the argument n; if n is zero then the result is zero, else the result is one plus (id (n - 1)).

More formally, id is

     \ n . if n = 0 then
             0
           else
             1 + (id (n - 1))

You have surely noticed some similarity with fact. In fact this pattern is quite common in recursive definitions, even if it is surely not the only one.

Before going on with recursion we are going to make a little digression introdcing a fundamental data structure (a data structure is an object made of other objects), the list.

Introduction to lists
=====================

A list is a sequence of objects of the same type. In lists order does matter: for example [1;2;3] is different from [2;1;3].

Formal definition: a list can be the empty list (written []), or the cons (Lisp The name cons derives from the Lisp language, and is now a universally accepted way of denoting the ``construction'' operation inserting an element before a list.) of an object a and a list L (written a::L).

Intuitively speaking, consing means adding one element before a list: to obtain the list [17;-2;32], for example, you can cons 17 and [-2;32], writing 17::[-2;32].

Beware of the types: you can't, for example, cons a book and a list of integers; you can only cons a book and a list of books (and obtain another list of books), or an integer and a list of integers (and obtain another list of integers). The empty list [] poses no type problems: you can see it as a list of integers, of books, or of any type you need in a given moment (polymorphism This feature is called polymorphism. Polymorphism will be fully discussed later in this book.).

An example: you can cons 1 to the empty list:

1::[]

then you may cons 2 to the list you built:

2::1::[]

The list you obtained, 2::1::[], can also be written as [2;1], and the previous one 1::[] can also be written as [1]; they are commodity abbreviations.

A final note: re-read the definition ``a list can be the empty list, or the cons of an object a and a list L''. You may have noticed that we defined lists using lists: it's a recursive definition.

More on lists: empty, head and tail
===================================

Other than cons there are three operators for working on lists: they are called empty, head and tail (In the Lisp language (hence by tradition) they are called null, car and cdr, repectively.). We are now going to describe them in some detail.

empty : (list of T1) -> boolean

You can read T1 as ``any type'' (Here's one more case
of polymorphism.). This is the first time you see the boolean type; it is a very simple yet important type: the set of booleans is the set containing only the two values true and false. empty, given a list L as parameter, returns true only if L is the empty list []; if L is not empty then empty returns false. Two examples: empty [] returns true; empty [1;2] returns false.

head  : (list of T1) -> T1

head, given a list L as parameter, returns the first element of L. It is an error to apply head to the empty list (Applying head to [] raises an exception. Exceptions are a general and powerful way to deal with errors, and will be dealt with later in this book.). For example, head [-2;450;0;3] returns -2.

Notice that head is a partial function: head : [] |-> _|_.

tail  : (list of T1) -> list of T1

tail, given a list L as parameter, returns the the whole list without the first element. It is an error to apply tail to the empty list (tail [] also raises an exception.). For example tail [1;2;3] returns [2;3]; tail [17] returns [] (don't forget that [17] is the same as 17::[]).

tail is also partial: tail : [] |-> _|_.

Always pay attention to types: head takes a list of objects of some type T1 and returns an object of the same type T1; tail takes a list of objects of some type T1 and returns another list of objects of the same type T1. This is very intuitive: for example, if you have a list of numbers and extract its first element with head, you expect to find a number, and not something different.

More on recursion
=================

Now we are going to illustrate some important concepts about recursion, analyzing few noteworthy functions in all their important aspects.

In this section the concept of reduction will be used for the first time. We say that an expression E ``reduces to'' an expression F, and we write

E ==> F

when computing E leads to compute F, as a single computation step (The idea of ``computation step'' is indeed quite subjective. In this book we say ``a single computation step'' to mean the minimum computation unit which is interesting in the context. The discussion about reductions will be informal.). For example

3 + (7 - 2) ==> 3 + 5 ==> 8.

Reductions are a useful mean to express computations.

The function last
-----------------

We can easily compute the first element of a list using head, but say you want to know which is the last element of a list; for example, if we pass ["a"; "b"; "c"] to the function (we call it last), we expect to be given back as result "c".

Always start thinking of the type: last takes as its parameter a list of objects, each having some type T1, and returns a single object of the same type T1; the returned object belongs to the list, so it must have the same type as the elements of the list.

last : (list of T1) -> T1

This is a definition of last:

     \ x . if empty (tail x) then
             head x
           else
             last (tail x)

We call X the parameter.

There are two cases:

 1. X is a one-element list, i.e. its tail is the empty list:

     In this case the first element of X is also the last element of the list: we return head x.

 2. X is not a one-element list, i.e. its tail is a non-empty list:

     The last element of X is the last element of its TAIL: we return last (tail x).

Pay attention to the second case: it the list is not one-element (for example say it has three elements), we return the last of its tail, which in the example is a two-element list: the last of the two-element list is the last of its tail, which is one-element. The important fact to note is that the arguments of successive recursive calls are more and more simple: this is very typical when recurring over data structures (For example lists as in this case, opposing to, say, naturals. This is not conceptually exact, but the complexity of a natural number seen as a data structure is not entirely evident.), and a different behaviour is nearly always an indicator of errors.

Let's track down how this function works for, say, [45; 43; -4; 35], step by step:

  * evaluate last [45; 43; -4; 35]:

     is [45; 43; -4; 35] a one-element list? No (we are in case 2), return last [43; -4; 35].

  * evaluate last [43; -4; 35]:

     is [43; -4; 35] a one-element list? No (we are in case 2), return last [-4; 35].

  * evaluate last [-4; 35]:

     is [-4; 35] a one-element list? No (we are in case 2), return last [35].

  * evaluate last [35]:

     is [35] a one-element list? Yes (we are finally in case 1), return head [35], i.e. 35.

``Coming back'' to the first function call we have:

last [45; 43; -4; 35] ==>

last [43; -4; 35] ==>

last [-4; 35] ==>

last [35] ==>

35, which is the value we were expecting.

Notice that in the definition of last it is assumed that the argument is not []: if X is [] then the evaluation of head (tail x) fails. last is a partial function, being it undefined on []: last : [] |-> _|_.

The function interval
---------------------

Say you want to compute the list of integers from a given value to another given value; for example, if we pass 1 and 5 to the function, we expect to be given back as result [1; 2; 3; 4; 5]; if the first parameter is greater than the second one, then we expect the empty list []; if we use the same value X for both parameters we expect [X]. We are going to call this function interval.

interval takes two integer parameters and returns a list of integers; we write it curried, so we may think of it as a function taking an integer parameter and returning another function, which takes another integer parameter and returns a list of integers:

interval : integer -> (integer -> list of integer)

interval is defined as

     \ a . \ b . if a > b then
                   []
                 else
                   a :: (interval (a + 1) b)

As you could image interval is a (curried) function taking two parameters; we call them A and B, respectively.

As often happens, there are two cases:

 1. Case 1: A is greater than B.

     We simply return the empty list, as the definition says.

 2. Case 2: A is less than or equal to B.

     The list that we are going to return will surely contain A as the first element; the rest of the list will be the interval from (A + 1) to B; so we cons A to (interval (A + 1) B).

Let's examine an example of application, say interval 5 7, step by step:

  * is 5 greater than 7? No, so we are in the second case, and we return 5 :: (interval (5 + 1) 7).

  * Now we need to evaluate (interval (5 + 1) 7), i.e. interval 6 7: is 6 greater than 7? No, so we are again in the second case: we return 6 :: (interval (6 + 1) 7).

  * Evaluate interval (6 + 1) 7, i.e. interval 7 7: is 7 greater than 7? No (it's equal to it, not greater than it), so we are in the second case: we return 7 :: interval (7 + 1) 7

  * Evaluate interval (7 + 1) 7, i.e. interval 8 7: is 8 greater than 7? Yes, so we are in the first case: return [].

Now we have evaluated everyhing we needed: ``coming back'' to the first function call we have:

interval 5 7 ==>

5 :: (interval 6 7) ==>

5 :: (6 :: (interval 7 7)) ==>

5 :: (6 :: (7 :: (interval 8 7))) ==>

5 :: (6 :: (7 :: [])), i.e. 5 :: 6 :: 7 :: [],

which can be abbreviated into [5; 6; 7], the value we were expecting to be given.

Tail-recursion
--------------

Notice the difference between the evaluation of interval and the evaluation of last: each call to interval, except for the last one, is expanded to an expression containing another call to itself among other things (here the expression is the cons of an object and another call to interval). In last the situation is simpler: each call, except the last one, is simply expanded to another call, with no other expressions involved which ``surround'' the recursive call:

interval 1 3 ==> 1 :: (interval 2 3) ==> ...

last [345; -50; 4555] ==> last [-50; 4555] ==> ...

Said in another way, you have no need to ``keep track'' of temporary results when evaluating a call to last, but you have when evaluating a call to interval: for computing interval 1 3 you need to compute interval 2 3, then cons 1 to it; to compute interval 2 3 you have to compute interval 3 3 and cons 2 to it, and so on. With interval you have first to compute temporary values, then to ``attach'' them with expressions. With last you can simply forget all the temporary values before the last one; once you have computed them, you will not need them anymore:

last [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16] ==>

last [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16] ==>

last [3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16] ==>

...

==> last [16].

For all these reasons it's easy to see that last is somehow simpler than interval (apart from the number of parameters: this is not important in this context). last is said to be a tail-recursive function, while interval is not (When defined in this form. interval can also be defined in a tail-recursive form, but the definition becomes somewhat more complicated.).

We are going to explain more formally what means for a function to be tail-recursive, later in this book. For this time just an intuitive understanding is enough.

Evaluating a call to a tail-recursive function with a computer is noticeably more efficient than evaluating a call to a plain recursive function: when using a functional language the programmer should strive to use tail-recursion whenever possible.

Non-termination: the function dontstop
--------------------------------------

Let's examine a recursive function called dontstop, defined in this way:

     \ x . dontstop x

epsilon would detect (infer is the most appropriate term) its type as

dontstop : T1 -> T2,

altough the reason for this may not appear evident yet. The argument X can have any type, hence the generic type T1. But what is the type of the object returned by the function? The answer is that the function never returns, so in a sense the returned object has an unknown type; and there is no reason to suppose that the returned object has the same type as X, hence the new type T2. This may seem counterintuitive now, but there are deep reasons (These reasons are bound to the type system of epsilon, i.e. the set of rules which govern the typing of expressions. epsilon supports the Hindley-Milner type system, also used by the languages ML and Haskell. The enforcing of such rules prevents many programming errors and can also make programs run faster. Details will be explained later in this book.) (which will be explained later in this book) not to write, say,

dontstop : T1 -> nothing.

The behaviour of dontstop is quite simple to understand: let's see it when applied to [[10; 3]; [2]] (an object with type list of list of integer, which is ok: the parameter X can have any type, as we have just said):

dontstop [[10; 3]; [2]] ==>

dontstop [[10; 3]; [2]] ==>

dontstop [[10; 3]; [2]] ==>

...,

never stopping. A call to dontstop expands to another call to dontstop, with exactly the same argument. The fact that the complexity of the argument does not lessens in successive calls usually indicates that evaluation does not terminate, as in fact happens in this case.

Any expression whose computation is non-terminating is said to diverge. If E diverges you can write E diverges. By constrast, if the evaluation of E terminates at some point then E is said to converge, and you can write E converges.

dontstop is a partial function, being undefined for at least some values of its argument (in this case for all the possible values), and the meaning of dontstop can be expressed as \ x . _|_; note, however, that here the symbol ``_|_'' stands for something different from the meaning of last [], also expressed by ``_|_''. Here ``bottom'' stands for non-termination, in the other case it stood for error. The actual meaning of an expression including _|_ will be specified case by case, when ambiguity can occour.

As a final comment notice that dontstop is a tail-recursive function.

Of course dontstop is illustrative as an example, but such a function should never be needed in actual programs.

Differences from imperative programming
=======================================

This section is aimed to the readers with some experience in imperative programming. If you are learning to program from this book you can safely skip this part.

No side effects
---------------

The most obvious difference between functional languages and imperative languages is that in functional languages there are no side effects. For example in an imperative language you can write something like a := 67, or, to increment a variable, a := a + 1. How can we increment a variable in a functional language? The answer is simply that there is no way; what is achieved with side effects in imperative languages must be dealt with in some other way, in most cases using recursion.

This has some advantages: when you create a variable you give it a value, and you are sure that the value will never change; in imperative languages, instead, it's a common mistake to think a variable has some value, while instead it has been updated, possibly by some procedure you are not thinking of: this is impossible in a functional language. It's equally impossible to have uninitialized variables: you name it, you create it; there will never be a uninitialized-variable or null-reference error.

Recursion instead of loops
--------------------------

The absence of loops in functional programmers captures the attention of many programmers even more than the absence of side effects; however the absence of side effects obviously implies the absence of loops: iterating means executing some command many times, but what command are we about to execute? There is no state to change since there are no side effects. You just keep calling recursive functions and computing values until you reach the one you are interested in, and finally return it.

Recursion is not inherently more difficult to use than loops, but requires a little adapting to ``think recursively''. Don't be afraid if you find yourself stuck to think ``iteratively'' at first: just try to express the same idea as a recursive function. In many cases, when you have finished, you will be surprised from the clearness of recursive code with respect to iterative code.

No pointers or references
-------------------------

In a functional language there is no need for pointers or references. Data structures are beautifully expressed without pointers or references (References (as in Java, or, to a lesser extent, in C++) do not to cause the same problems which pointers cause. However they are nonetheless error-prone: you can forget initializations by mistake, and in general references suffer from all the vulnerabilities which are bound to side-effects.) using abstract and concrete types, which are very intuitive to define and to use, and not error-prone at all.

Concrete and abstract types will be fully dealt with, later in this book.

Semantics (Semantics is a branch of Computer Science dealing with the formal meaning of computer programs. It's not required you know Semantics for using epsilon.) also gives some more justifications (Semantics says pointers and references are related with memory, also named store. All side effects are also operations on stores. In a functional language there is no concept of store and all operations are made only on environments; imperative programs, by constrast, use both environments and stores. This is a deep reason why functional programming can be simpler than imperative programming.) to our claims.

First-class functions
---------------------

In functional languages a function is an first-class object, i.e. an object like any other: you can compute a function at run time, you can make a function return another function, you can define a function with no special syntax, you can write an unnamed lambda-expression in the middle of a bigger expression: for example

2 + ((\ x . x + x) 3)

gives back 8 as result, as expected.

For an example of a function returning a second function, think of any curried function (look at its type if you don't understand at first).

This use of functions is natural and simple, but is forbidden in nearly all imperative languages.

Higher-order
------------

In nearly all functional languages functions can have other functions as parameters (we speak about second order in this case), and the parameters of those functions can be yet other functions (third order), and so on. If there is no limit to the order of functions then the language is said to be omega-order (In
mathematics the letter omega
is used to indicate the cardinality, i.e. the number of elements, of
the set of the natural numbers N.). epsilon is an omega-order language.

You will learn later in this book how higher-order functions are useful to write simple and compact programs; in many cases you can even use higher-order functions as substitutes for recursion.

Higher-order functions don't exist or their use is seriously restricted in imperative languages.

Referential transparency
------------------------

In functional languages a noteworthy property holds, named referential tranparency: in practical terms it says that if an expression E has value v, you can replace every occurrence of E with v in a program, without changing its meaning. This makes programming more clear and less error-prone and allows the compiler to make some optimizations which would be impossible in an imperative language.

Type safety
-----------

Many functional languages, epsilon included, are strongly typed, i.e. they recognize  as invalid all the programs which contain type errors, such as multiplying an integer and a boolean, at compile time (i.e. before execution.). Many type errors are subtle, and in general having the compiler detecting them is a great help, saving time and frustration.

Most imperative languages allow unsafe use of types, and this may lead to detect errors very late, even after program release.

Type inference
--------------

Some functional languages (ML and Haskell are important exemples.), including epsilon, infer types; it's the compiler to tell the type of an expression to the programmer, and the programmer is saved from the pain of declaring, say, the type of every function parameter. The output from the compiler is a mean to verify that the meaning of the program is really what the programmer intended.

Implementations of imperative languages do not usually provide type inference.

Purely functional I/O
---------------------

Purely functional languages, including epsilon and Haskell, completely avoid the dangers of side effects forbidding the user to mix input/output with normal computations, as a way to preserve referential transparency (Other referentially transparent solutions exist in the functional world, such as linear types; however we decided to implement the I/O system following the lesson of Haskell, which in our opinion employs the most clean and usable way to make safe I/O.). For example, the epsilon compiler refuses to accept code like 2 + input_integer + 3.

Anyway not all functional languages have these restrictions. ML, for example, has some imperative features including side effects and I/O in imperative style.

Languages like epsilon and Haskell are said to be purely functional.

Before going on
===============

This introduction to functional programming, even if brief, may seem too abstract at a first glance, but as the name functional language suggests the basic mathematical aspects are of fundamental importance: while programming in epsilon you will be defining recursive functions with complex types all the time.

If you have not understood at least the basics of types, lists and recursion you should read again this chapter, paying particular attention.

Of course any suggestion for improving this documentation is welcome, but we deem this chapter particularly important. You can use the public mailing-list bug-epsilon@gnu.org to talk with us about these matters. No subscription is needed.

However, don't be afraid if you still have some doubts; most of the same concepts which were outlined here will be presented in practical terms in the next chapter.

epsilon tutorial
****************

In this chapter you are going to learn the basics of the epsilon language by using the tools yourself.

Before starting: a notice
=========================

We are now assuming that the epsilon meta-interpreter is already implemented and working. This is not yet true, but you can use the temporary quick-and-dirty REPL (The REPL, (Read-Eval-Print Loop), is a simple C program which takes an epsilon expression, compiles it into bytecode, and runs it on the eVM (epsilon Virtual Machine). The REPL as it is now has some serious flaws, and can not execute all the code which the compiler can run. You can always use the compiler instead of the REPL, at the cost of some additional complications. In the rest of this chapter we assume you are using the interpreter, which when it's ready will behave much like the current REPL.) in the meantime.

You can invoke the temporary REPL simply typing epsilon.

In the same way, in this chapter we purposefully ignore the bytecode interpreter eVM, which is likely to disappear in the future, when the interpreter is ready.

The interpreter and the compiler
================================

An epsilon program can be run using one of two distinct tools, which are useful in different situations:

the interactive interpreter
     The interpreter (The interpreter is also called meta-interpreter, or meta-circular interpreter. This means that the interpreter was written in the same language it implements: in this case the epsilon interpreter itself was written in epsilon.) can be used as an interactive program: you type a small piece of epsilon code, the code is promptly executed and the result is shown back to you on the screen; then you can start again: write some more code, execute it, look at the result, and so on.

     When used in the way explained above, the interpreter is said to act as a REPL, i.e. ``Read-Eval-Print Loop'': it reads a piece of code, evaluates (executes) it, prints back the result and starts again.

     This way of working is very comfortable when you are developing a new program: it makes easy to write some code, to test it soon, and to fix it soon if some error is found. There is a drawback, however: the code runs slowly and uses much memory.

the compiler
     The compiler is a non-interactive program: you write your epsilon code in one or more files using an editor such as GNU Emacs, and you invoke the compiler which translates the files into a form which is directly executable on your computer. Then you can execute the translated program.

     Using the compiler you use an ``Edit-Compile-Run Loop'' (Often called ``Edit-Compile-Debug Loop'', since it's very uncommon to write a nontrivial program which works without errors the first time.) approach. Note that it is not a program to ``loop'', it's you; it's you who must manually edit the files, save them, compile them, wait for the translation to finish, and execute the translated program.

     The advantage of this approach is the high speed and efficiency of the translated code. Its drawbacks are the slowness of the translation, and the general clumsiness of the approach. The compiler is the right tool to use when you have finished writing and testing a program which works well, and want it to run fast.

A program run with the interpreter (interpreted) or translated by the compiler (compiled) behaves identically: only speed and memory use are different. You have not to worry about compatibility, since the interpreter and the compiler support the exact same language.

The interpreter is also better suited to learn the language and experiment. In the rest of this chapter we are going to assume you use the epsilon interpeter.

Using the epsilon interpreter: a first session
==============================================

Try starting the interactive interpreter: at the command prompt of your system, type

     # epsilon

The interpreter will show a banner similar to

     -------------------------------------------------------------------------------
                                             i  ll
                      eeeeee                     l                  version 0.2.1CVS
                     ee      p pppp   ssss  ii   l   oooo  n nnnn
                      eeee    p    p s       i   l  o    o  nn   n
                     ee       p    p  sses   i   l  o    o  n    n
                     ee       p    p      s  i   l  o    o  n    n
                      eeeeee  ppppp   sses  iii lll  oooo   n    n
                              p
                              p                  http://www.gnu.org/software/epsilon
                             ppp
     -------------------------------------------------------------------------------
     GNU epsilon 0.2.1CVS, Copyright (C) 2002, 2003 Luca Saiu
     GNU epsilon comes with ABSOLUTELY NO WARRANTY; for details type `:no-warranty'.

     This is free software, and you are welcome to redistribute it under certain
     conditions; type `:license' for details.

     Welcome to the epsilon meta-interpreter.
     Type :? for help.

     1 >

The prompt > followed by a blinking cursor means that the interpreter is ready to accept your code; now try typing

     2 + 2;

(remember the trailing semicolon), and pushing Enter. The interpreter will answer

     - : integer
     4
     1 >

The first line means that the expression you entered, indicated by -, has integer type. The second line shows the computed value, which, as you were expecting, is 4. The third line is a new prompt; the interpreter is ready to accept more code.

For exiting the interpreter, type

     :quit

(note the leading colon, and the absence of a trailing semicolon) and push Enter at the prompt. Another way to exit the interpreter is by pressing Ctrl-D.

Interpreter syntax and epsilon syntax
-------------------------------------

Pay attention to the syntax: :quit, :help and :license are commands directed to the interpreter itself, in the sense that they don't deal with your epsilon program. Interpreter commands need a leading : and no trailing ;. Expressions such as 2 + 2;, instead, are part of the epsilon syntax. They need no leading : and they do need a trailing ;.

Queries and definitions
=======================

Now start the interpreter again, typing epsilon at the command prompt of your system.

Try making some computations with integers; parentheses are used to group subexpressions to be computed before, as in arithmetic. The 'times' symbol is written as an asterisk (*), the 'divided' symbol is written as a slash (/).

     1> (2 + 6) * 2 / 4;
     - : integer
     4

You can try other more complex expressions if you like.

The expression above was a query: you asked the interpreter to evaluate an expression for you, and you were interested in the result. Queries are a common way, among the rest, to test a function you wrote, supplying a value and verifying the result is what you are expecting. Let's now show how to define a function, starting from a very simple one.

Say you want to define a function adding 3 to its only (integer) argument: you learnt in the previous chapter that such a function is written as \  x . x + 3. Since the letter \ is usually not present on keyboards, epsilon uses the backslash (\) character instead of it. So try entering

     \ x . x + 3;

What you get as an answer is

     - : integer -> integer
     <function>

which maybe is not what you were expecting. Let's examine the answer of the interpreter: the first line says that the expression you entered has type integer -> integer, which is right; the second one says that the value of your expression is a function; often doesn't make much sense to write them: they are usually complex and not very useful as output from the interpreter (they are useful as input for it). Hence the interpreter just writes <function> when the result of your computation is a function. And indeed it is, in this case.

The problem is that you wrote a function, but it still was a query. For a definition there is need for a different syntax. Of course this syntax exists, and it is very simple: just write, for this same example,

     define f = \ x . x + 3;

The interpreter answers saying just

     f : integer -> integer

Now you have given your function the name f (you could have used any different name, of course). You can now use your function f in queries and in other definitions: try

     f 10;

The result is 13, as you expected.

We have shown examples of function definitions, and indeed that is the most common case, but you can make definitions for objects of any type, not necessarily functions. The following example shows several non-function definitions:

     define twenty = (\ x . x * 2) 10;
     define forty = twenty + twenty;
     define this_is_a_string = "Hello, world!";
     define pi = 3.14159265358979323846264338327;
     define empty_list = [];

Booleans
========

As we already said in Functional programming tutorial, a boolean value (also called truth value) is either true or false. Booleans are useful in a wide range of contexts. One of the most simple is in a query comparing two objects: ``is 1 less than 2?''

     1 < 2;
     - : boolean
     true

A slightly more complex query (note that >= stands for `greater or equal', and <= stands for `less or equal'):

     (f 1) >= (f 2);
     - : boolean
     false

You can always think of reductions if this helps you:

(f 1) >= (f 2) ==>

((\ x . x + 3) 1) >= ((\ x . x + 3) 2) ==>

(1 + 3) >= (2 + 3) ==>

4 >= 5 ==>

false

You can also directly use the constants true and false: try writing the trivial query

     true;

The interpreter will answer

     - : boolean
     true

Logical connectives
-------------------

You can use the usual logical connectives not, and, or and xor with boolean expressions. ``or'' is also called ``inclusive or'', and ``xor'' is also called ``exclusive or''.

Let us explain the meaning of boolean connectives, where E, e_1 and e_2 are epsilon expressions with boolean type. The result has always boolean type, too.

The meaning of logical connectives is:

  * not E ==> true if and only if E ==> false

  * e_1 and e_2 ==> true if and only if e_1 ==> true and e_2 ==> true

  * e_1 or e_2 ==> true if and only if e_1 ==> true or e_2 ==> true, or both

  * e_1 xor e_2 ==> true if and only if one of the following two statements holds:

       - e_1 ==> true and e_2 ==> false

       - e_1 ==> false and e_2 ==> true

     (or, said in a different way, if and only if e_1 and e_2 reduce to different truth values).

As we said above, boolean connectives applied to boolean objects yield other boolean objects, so they can be combined to form boolean expressions of any complexity. Try the following query with the interpreter:

(true and (not not false)) xor ((1 < 2) or false);

The result is true. Let us show why:

(true and (not not false)) xor ((1 < 2) or false) ==>

(true and (not true)) xor (true or false) ==>

(true and false) xor true ==>

false xor true ==>

true,

which is to say that reductions apply to boolean expression as to any other type of expression.

Here are some more sample queries; try computing them in your mind or with paper and pencil using reductions before using the interpreter:

     true and (true or false);

     (1 < 2) xor false;

     not ((20 < 22) and true);

Conditionals: if..then..else
============================

In the examples of Functional programming tutorial we used the conditional operator if..then..else several times, without explaining the details.

The syntax is

if guard then expression_a else expression_b

where guard, expression_a and expression_b are epsilon expressions. There are two constraints:

  * guard must have boolean type; said in a more formal way

       - guard : boolean

  * expression_a and expression_b must have the same type, which can be any type. Formally,

       - expression_a : T1

       - expression_b : T1

The intuitive meaning is: evaluate guard; then, if it reduces to true then reduce the whole if..then..else expression to expression_a, else if it reduces to false then reduce the whole if..then..else expression to expression_b. Said more formally:

  * if guard ==> true then

     (if guard then expression_a else expression_b) ==> expression_a

  * if guard ==> false then

     (if guard then expression_a else expression_b) ==> expression_b

  * if guard diverges then (If guard diverges then we will never be able to
     choose between the then branch and the else branch: we
     will keep evaluating the guard for ever, without ever evaluating
     either branch.)

     (if guard then expression_a else expression_b) diverges

Some brief comments about the type constraints:

The first constraint is obvious (Even if it is absent in some languages such as Lisp and C; however nowadays it is widely known that such absence of type constraints can lead to many programming errors.): for deciding between two options you need a boolean: any other type (integer, string, list, etc.) would not be the right thing.

To understand the second constraint, try entering the query

     if 1 < 2 then 1.0 else "abc";

This will lead to an error, since the second constraint was violated: 1.0 and "abc" have different types (float and string, respectively). This is reasonable: in an actual program it would be very difficult (Some dynamically-typed languages such as Lisp do permit having different types in the then and else branches; however this lack of compile-time checking makes programming errors very frequent. It's rare to actually need such a feature, and when it is really needed it can be easily simulated in epsilon via concrete types. Concrete types will be explained later in this book.) to do something reasonable if the two branches (the ``then branch'' and the ``else branch'') have different types; and thare are also other reasons: which type would you give to the expression \ x . if x then 1.0 else "abc"? You would not be able to decide between boolean -> float and boolean -> string.

An example: the function monus is somewhat famous: it takes two numbers X and Y, and returns X - Y if it is not negative, else returns 0. Let's see a definition:

     define monus = \ x . \ y .
       if x - y >= 0 then
         x - y
       else
         0;

Try calling monus:

     monus 10 12;
     - : integer
     0

     monus 12 (5 + 5);
     - : integer
     2

A final note for imperative programmers: if you know imperative programming, you might ask whether an if..then operator, without else, exists. The answer is a strong no: in a functional language an expression must always be reduceable to something: it is not acceptable to say ``if a is less than b then 10''; and if a is not less than b, what are we going to return? An explicit else branch is always needed.

Temporary variable bindings: let..be..in
========================================

In many cases it is useful to have an ``abbreviation'' for a given subexpression, which is used more than once. For example, say you want to compute

2^5 + 3^5 + 4^5 + 5^5.

A way to compute it with a query is:

     2 * 2 * 2 * 2 * 2 + 3 * 3 * 3 * 3 * 3 + 4 * 4 * 4 * 4 * 4 + 5 * 5 * 5 * 5 * 5;

The above expression is perfectly good for the interpreter, but not very readable by humans. The let construct allows you to write, instead,

     let f be
       \ x . x * x * x * x * x
     in
       (f 2) + (f 3) + (f 4) + (f 5);

The meaning is quite intuitive: the name f is temporarily used for (bound to is the correct term) a function which takes a number x and returns x^5; this name occours four times in the following code (said the body of the let expression), as a placeholder for the function (\ x . x * x * x * x * x). Out of the let expression, this association of a value to the name f (this binding of f) is not visible.

If you expand the body replacing every occurrence of f with the value which is bound to it, you obtain an equivalent expression: in fact the whole query above has exactly the same meaning of

     ((\ x . x * x * x * x * x) 2) +
     ((\ x . x * x * x * x * x) 3) +
     ((\ x . x * x * x * x * x) 4) +
     ((\ x . x * x * x * x * x) 5);

This expansion shows how much let can make programs more readable.

As a side note, writing a * a * ... * a (with a occourring b times) is not the most clever way to compute a^b. The right way is using the power operator **, which allows to simply write a ** b. We did not do so above just because using ** was not convenient for us to illustrate the let construct: we needed some more ``visual clutter''.

To do: syntax (single binding), intuitive semantics, more examples, multiple binding

Digression: free occurrences and bound occurrences
--------------------------------------------------

To do: move this part to the beginning of this part, with a more precise explaination substitutions and reductions.

A free occurrence of a variable is an occurrence of the variable which does not refer to an inner \ or let. An occurrence which is not free is called bound.

For example, if we replace the free occurrences of x with 100 in

     x + ((\ x . x + 1) (x + let x be 1 in (x + y)))

we obtain

     100 + ((\ x . x + 1) (100 + let x be 1 in (x + y)))

Explaination:

  * The first x is free.

  * The x in x + 1 is bound by the inner \ x ..

  * The x in x + let ... is free.

  * The x in (x + y) is bound by the inner let x be.

Free occurrences were briefly introduced here since they will be needed once in the next subsection. This same topic will be covered at length later in this book.

A more formal explaination
--------------------------

A first approximation (This first description does not cover the ``multiple let'', so it is not the complete syntax. It will be explained later.) of the syntax of a let expression is

let variable_a be expression_a in expression_b

Here is the intuitive semantics: the subexpression expression_b typically contains one or more occurrences of variable_a, even if this is not required; every free occurrence of variable_a in expression_b is replaced by the value which expression_a reduces to, and the whole let expression reduces to the modified expression_b.

More formally:

  * If expression_a diverges then (let variable_a be expression_a in expression_b) diverges.

  * Else expression_a converges, and expression_a ==> y; (let variable_a be expression_a in expression_b) ==> expression_c, where expression_c is obtained from expression_b replacing every free occurrence of variable_a with y.

An example: let's show the evaluation of let x be 1 + 2 in x + x - 1.

  * First see what expression_a (here 1 + 2) reduces to: 1 + 2 ==> 3. Ok, expression_a converges.

  * Replace the free occurrences of variable_a (here x) in expression_b (here x + x - 1) with the value we have just computed (here 3): 3 + 3 - 1.

  * The whole let expression reduces to what we have just computed: let x be 1 + 2 in x + x - 1 ==> 3 + 3 - 1

  * Reduce again until possible: 3 + 3 - 1 ==> 6 - 1 ==> 5

To do: computability: let is not needed for Turing-completeness

Recursive functions
===================

We are now going to define the factorial function with the epsilon interpreter. The definition, as we already said in Functional programming tutorial, is

\ n . if n = 0 then 1 else n * (fact (n - 1))

To do

Part II - Specification
***********************

In this part we give a complete and formal description of the epsilon language, of its library and tools.

Some notions of Semantics and Languages would help to understand the mathematical parts, but they are not essential.

This is essentially reference material: feel free to skim it at a first reading.

Language
********

Lexicon
=======

Whitespace
----------

Comments
--------

Identifiers
-----------

Numbers
-------

Characters and strings
----------------------

Basic types and expressions
===========================

The void expression
-------------------

Integer expressions
-------------------

Floating-point expressions
--------------------------

Boolean expressions
-------------------

Character expressions
---------------------

String expressions
------------------

Promise expressions
-------------------

Basic constructs
================

The declare declaring construct
-------------------------------

The define naming construct
---------------------------

The if..then..else conditional construct
----------------------------------------

The let block construct
-----------------------

Functions
=========

lambda-notation
---------------

Functions with more than one argument
-------------------------------------

Recursion
---------

The fix fixpoint operator
.........................

Mutually-recursive functions
............................

Higher-order types
==================

Lists
-----

Arrays
------

Concrete types
--------------

Type inference
==============

Type declarations in function parameters
----------------------------------------

Exceptions
==========

Modules
=======

Abstract types and synonym types
--------------------------------

Polymorphism
============

Classes
=======

Monads
======

The epsilon meta-interpreter
============================

Foreign languages interface
===========================

Calling C from epsilon
----------------------

Calling epsilon from C
----------------------

Library
*******

Default prelude
===============

Containers
==========

Meta-interpreter and meta-compiler
==================================

I/O
===

Terminal I/O
------------

Curses I/O
----------

Filesystem I/O
--------------

Sockets I/O
-----------

Graphics I/O with OpenGL
------------------------

CORBA bindings
--------------

Bonobo bindings
---------------

Tools
*****

Common command line behavior
============================

The programs in the epsilon distribution, like all the other GNU programs, accept the following two options:

--help
-?
     Writes short usage information to the standard output and exits with success without executing.

--version
-V
     Writes program version and short license information to the standard output, and exits with success without executing.

Every option in the long form --XXXX has also the negative form --no-XXXX, which does the opposite.

The epsilon interpreter
=======================

The epsilonc compiler
=====================

To do: non-option parameters

The epsilonc compiler translates epsilon modules source files into eAML. By default it also calls the eamlas assembler, the eamld linker, the eamx2c C code generator, and finally the system C compiler to generate a full native executable program.

If any of the intermediate pass fails the compiler writes an error message to the standard error and exits with failure.

The default behavior is all that is needed in simple cases; for more complex program it's conventient to direct epsilonc via command-line options to stop after any stage of compilation, allowing the user to manually call the other translators.

The program accepts the options described below.

--verbose
-v
     Makes the program verbose while executing; in particular it makes the program output the current compilation phase which is going to be executed to the standard error.

--show-types
-t
     Makes the program write the inferred types of all the objects that are defined, and the definitions of user-defined types. It's a useful feedback allowing the programmer to check for correctness.

     This option is on by default.

--unescaped-string
-s
     Makes the generated program program write the strings and characters contained in the result of the evaluation of the main expression without quoting and without escapes. For example, if the main expression were "ab\ncd"  the generated program would print ab, a newline character and cd, without surrounding double quotes.

--generate-eaml
-S
     Stops before the assembling phase.

--generate-eamo
-c
     Stops before the linking phase.

--generate-eamx
-x
     Stops before the C code generation phase.

--generate-eama
-a
     Generates a library containing the compiled modules instead of making an eAM executable file, then stop.

--generate-c
-C
     Stops before the native code generation phase executed by the system C compiler.

--generate-scheme
     Generates Scheme code instead of C code from the eAM executable file, then stop; Scheme code does not normally need to be compiled.

--cc-options=XXXX
     Passes the additional options XXXX to the C compiler when compiling the generated C code.

--main=XXXX
-m XXXX
     Specifies the name of the main module. Note that this is a module name, and not a file name, so it can not have extension.

--output=XXXX
-o XXXX
     Specifies the name of the output file, i.e. the one generated in the last phase; the extension must be in accord with the type of the file generated.

The eamlas assembler
====================

The eamld linker
================

The eamx2c eAM executable to C compiler
=======================================

The eamx2scheme eAM executable to Scheme compiler
=================================================

The epsilonlex scanner generator
================================

The epsilonyacc parser generator
================================

Part III - Internals
********************

This part contains a detailed description of the implementation of epsilon.

It is of no particular utility for simple users of epsilon, except for who wants to have a deep feeling of how things work ``below''. It's very important, instead, for programmers who want to modify epsilon to extend it or to re-use a part of its code for some other purpose  (Remember that epsilon is free software (``free'' in the sense of ``free speech'': see http://www.gnu.org) covered by the GNU General Public License. See Copying for the full text.).

The chapters of this part have somewhat stronger requisites than the rest of the book: proficiency with compiler and run-time support design, C, flex, Bison, bash and Scheme is required to fully understand the sources. Also some notions of operating systems would help.

Internals overview
******************

This chapter describes the implementation of epsilon, how it was written the way it is and why.

Architecture
============

As any nontrivial software project, epsilon is structured in layers.

To do: talk about the REPL

At the top level there is the compiler, translating a module written in epsilon into a lower-level form. This form is called eAML, for ``epsilon Abstract Machine Language''. The compiler outputs a textual form of the eAML language, relatively easy to read for humans. This helps the developer of epsilon to test and debug the compiler, and also allows to write code directly in eAML. The eAML language is quite low-level and resembles an assembly language. It is an imperative language, making explicit the control flow, the ordering of the computations and the environment management.

Under the compiler there is the second component, the assembler, translating an eAML module from the textual form into a binary form called bytecode object file, so that the computer can deal with eAML in a more efficient way. Instructions are translated one by one with no important modifications. It's simply a change of format.

The linker takes several bytecode object files (normally each one derives form an epsilon source module) and links them into a single larger bytecode object file; this is necessary since the lower part of the system can only deal with one bytecode object at the time. The linker can also read or write a bytecode archive file, which is a library of bytecode object files, tipically with some external references not yet resolved.

The bottom part of the system, called the epsilon Abstract Machine or eAM, supports execution via one more tranlation pass: the bytecode-to-C translator compiles a bytecode object file into a C source program, to be compiled by an optimizing C compiler into native machine code, and finally executed. The drawback of this approach is the delay due to the compilation of optimized C code (the delay of bytecode-to-C translation is negligible), but the runtime speed of the generated code should be very high.

The epsilonc compiler
---------------------

To do: I need to rewrite the compiler in epsilon, and to document it.

The eamlas assembler
--------------------

The eamlas assembler is a simple single-pass translator with backpatching, written in C with flex and Bison.

A few words about source file organization before starting: the assembler source files are in the eam/ subdirectory. For each category of instructions with the same format (e.g. with an integer parameters, or with no parameters, or with a label parameter) there is a subdirectory under eam/c_instructions/, containing the code for the instructions, one instruction per file. For example, the code for s_nlcl instruction, having two integer parameters, is in the file eam/c_instructions/integer_integer/s_nlcl.

To ease the developing of epsilon and to provide a better structuring, the source files eamlas.l and eamlas.y are not written by hand; instead they are automatically generated by the bash scripts make_eamlas_l and make_eamlas_y. The scripts scan the instructions/ subdirectories to find the opcodes of all the instructions and to divide them into categories after the format of parameters. The division into categories is useful while generating the frontend files eamlas.l and eamlas.y. The advantage of this approach is evident: to add, remove or rename an instruction it is sufficient to work only on the single file for that instruction: the assembler (together with the other low-level parts of the system) is updated automatically.

The output of the bytecode in written into the file using the module bytecode.c (also used by other parts of the system).

Other than bytecode.c, nothing more than the generated eamlas.l and eamlas.y is needed; the main logic is in eamlas.y: just a single scan in which all the found instructions are memoized, and all labels uses and definitions are stored in a data structure (essentially an hash table). At the end of the parsing all label references are resolved with a backpatch, and the output file is finally written.

The eAM abstract machine
------------------------

The epsilon Abstract Machine is relatively complex, and deserves a whole chapter. See The epsilon Abstract Machine.

The eamold linker
-----------------

To do: write the linker and document it

The eamo2c bytecode-to-C translator
-----------------------------------

To do: document eamo2c internals

The epsilonlex scanner generator
--------------------------------

The epsilonyacc parser generator
--------------------------------

Extending the eAM
=================

To do: talk about how to create new eAM instructions.

File formats
============

eAML file format
----------------

bytecode object file format
---------------------------

bytecode archive file format
----------------------------

The epsilon Abstract Machine
****************************

The epsilon Abstract Machine, or eAM, is a model of the operations involved in the execution of epsilon programs.

The eAM is imperative and, at the time of this writing, sequential; many functional properties of the epsilon language such as referential transparency and indipendency from evaluation order are lost in the translation from epsilon to eAML.

The eAM is relatively low-level, based as it is on a stack, a heap and an array of registers. The garbage collector is run automatically, even if it can be tuned with some special instructions.

It is worth repeating that the eAM is an abstract machine, and not a virtual machine. This is to say that there is not necessarily a step-by-step interpretation of bytecode instructions. The eAM model is only an abstraction of the functionality which is available at this level; in the implementation eAM instructions are translated into C and then compiled into native code with optimizations, or into Scheme code and then passed to Guile. However, for ease of implementation and for better undertanding, it's also useful to think of the eAM as a proper machine with its registers, stack, heap and instructions. Just remember that this does not mirror the execution model.

eAM types
=========

Any datum used by the eAM is of exactly one of these types:

integer
     Integer objects hold a limited range of integer values, roughly balanced around 0; their width is guaranteed to be at least 32-bit.

wide integer
     Wide integer objects also hold a limited range of integer values. They are guaranteed to be at least as wide as integers, and possibly wider.

float
     Float objects hold floating-point numbers. Their width is guaranteed to exactly match the width of integer objects.

wide float
     Wide float objects hold floating-point numbers at least as wide as and possibly wider than float objects.

wide wide float
     Wide wide float objects hold floating-point numbers at least as wide as and possibly wider than wide floats.

pointer
     A pointer object holds holds the memory address of another eAM datum, of itself, or of nothing; in this latest case a pointer is called a ``null pointer''. Null pointers are all seen as identical upon comparation, as NULLs in C. Internal pointers are forbidden: pointers are not allowed to refer to memory addresses inside a word or inside an array. Pointers are guaranteed to be exactly as wide as integers.

array
     Arrays are random-access ordered collections of word objects (see below); elements can have heterogeneous types. Arrays only hold their elements: no information about size is implicitly included. However it is common to store length information in the first element, when needed; some instructions are provided to make this fast and convenient. eAM arrays are always indicized starting from 0.

The internal representation of floats, wide floats and wide wide floats should follow the IEEE 754 Standard on modern architectures.

Note that no booleans, characters or strings are provided. Objects which in epsilon have these types, or higher-order types (such as epsilon functions, lists or tuples) are implemented using only the above eAM types.

The integer, float and pointer types are collectlively known as word types. The reason is that, in all reasonable architectures (These days, and in the foreseeable future, physical processors are 32-bit or 64-bit (the GNU Project does not support 16-bit machines, since they are long obsolete). 32-bit processors should have 32-bit pointers, and 32-bit general registers. 64-bit machines should have 64-bit pointers, and they should be able to do computations with 64-bit integers at assembly level. If they aren't, it's hoped that at least the C compiler provides support for 64-bit integer operations. We don't know of any counterexample; please write us to bug-epsilon@gnu.org if you know some, specifiyng.), any word object exactly fits in a physical machine general register. By contrast array, wide integer, wide float and wide wide float objects may be larger than a physical word. For this reason word objects are typically faster to manipulate.

No objects smaller than a word are provided.

Note that no run-time type tagging exists (opposing to Lisp and Smalltalk implementations, for example. The absence of type tags at runtime speeds up execution and reduces memory usage.): it's up to the compiler which generates eAML code to check for type errors at compile time, or to arrange runtime checks generating appropriate instructions when needed. When type tagging is needed on an object A (for simplicity you can think of a C union; all other cases can be reconducted to this one), it can be realized implementing A as an array whose (say) first element is an integer value discriminating between all possible types that A can assume at run-time; the second (and third, fourth and so on if needed) element holds the proper datum.

Memory model
============

References are managed via pointers, directly from runtime-support structures such as the stack or the registers, or from elements of array type.

Data structures can be realized with arrays containing pointers (and other word objects, if needed). Cyclic data structures are allowed without restrictions.

Storage allocation is realized with explicit eAM instructions, but storage reclamation is automatically managed by the garbage collector.

Representation of epsilon data in the eAM
=========================================

Every epsilon object has an underlying representation in the eAM; epsilon objects of most basic types are quite easily mapped to eAM objects of word types; for higher-order objects the mapping is more complex.

The eAM deals with non-word objects using pointers, which are word objects: for example a list is represented with the usual pointer-based data structure, and the whole list is referred using a pointer to the first cons (or a null pointer if the list is empty); to summarize, an epsilon datum which does not fit in an eAM word object is represented with non-word objects, and a pointer (word) referring ``the first element'', whatever we mean as ``the first element''. Note that internal pointers are forbidden in the eAM, so the first element must be a whole eAM objects (which can be an array).

We are now going to describe the mapping in its details.

integer, character and boolean
------------------------------

The epsilon types integer, character, and boolean are easily mapped into eAM integers.

Note that also a character uses a full word; this enables to use modern encodings such as Unicode (even if such support is not yet implemented). GNU epsilon is a new language, and we deliberately chose not to be restricted by obsolete 8-bit encodings such as ASCII or Latin1.

The epsilon boolean false is represented as the eAM integer 0. true is represented by any non-zero eAM integer.

When held in the stack or in a register these objects are copied rather than referred by a pointer. The rationale behind this is that it would be a waste of time and memory to hold pointers to immutable objects (remember that epsilon is a functional language), when the pointer has the same cost as the whole object.

float
-----

The epsilon type float is trivially mapped into the eAM type float. A float object fits in a machine word.

Floats can be directly held in the stack or in a register: there are no pointers to float objects. The rationale is the same as the one for the case above.

Tuples
------

epsilon tuples are mapped into eAM arrays holding the representation of each element; the order of the elements in the eAM representation always reflects the order of the elements in epsilon.

No information about the length of the tuple is held at runtime, since if the program was correctly compiled no bound-checks are ever needed at runtime for tuples.

When held in a register or in the stack the tuple is always referred by a pointer to the eAM array which represents it.

Arrays
------

epsilon arrays of size N are mapped into eAM arrays of size N + 1, where the first element is an integer holding the size of the array, and the following elements are the representation of the actual elements.

Holding the information about the lenght at runtime enables the eAM to make bound checks.

Empty arrays follow the general rule: they are represented as eAM arrays of size 1, where the only element is an integer with value 0.

When held in a register or in the stack the array is always referred by a pointer to the eAM array which represents it.

Strings
-------

epsilon strings are representated just as if they were arrays of characters.

Note that this representation allows computing the size of a string in O(1).

Lists
-----

epsilon lists are represented with the usual pointer-structure: each cons holds a pointer to the next one.

Each cons is represented as an eAM array of size 2, where the first element (the head, or car) holds the representation of an actual list element, and the second element (the tail, or cdr) holds a pointer to the rest of the list, or a null pointer if the rest of the list is [] (nil).

The empty list [] has no representation.

When held in a register or in the stack the list is always referred by a pointer to the eAM array which represents its first cons, or by a null pointer if the list is empty.

Objects of concrete types
-------------------------

To do

Objects with behavior
---------------------

To do

Promises
........

Functions
.........

Actions
.......

Objects of abstract types
-------------------------

The objects of an abstract type actually have another type (said the implementation type), which is usually hidden in the module which defines operations on them.

epsilon objects of abstract types are represented as objects of their implementation type; abstract types have no penality on representation. They are essentially gratis.

Examples
........

We are now showing the representation of some epsilon objects as eAM objects. We describe what appears in a register holding each of the sample epsilon objects:

  * 12

     The eAM integer 12.

  * 1.323

     The eAM float 1.323.

  * (1, 0.4)

     A pointer to an eAM array of two elements: the first element holds the eAM integer 1, the second one holds the eAM float 0.4. Note that the size of the tuple (2) is not needed at runtime, so it is not explicitly stored anywhere.

  * <| 1, 0.4 |>

     A pointer to an eAM array of three elements: the first element holds the eAM integer 2, which represents the size of the array; the following elements are the eAM objects 1 and 0.4.

     Note how in the eAM the proper elements of the array are indicized starting at 1: the zero-th element holds the size, which can be extracted very efficently (one or two assembler instructions in most processors).

  * <| |>

     A pointer to an eAM array of one element holding the eAM integer 0.

     It's worth repeating that epsilon empty arrays are not represented as eAM null pointers. This convention saves some nullity tests at runtime and makes the representation more uniform.

  * "Abc"

     A pointer to an eAM array of four elements: the first element holds the eAM integer 3, which represents the size of the string. The following elements are eAM integers holding the integer representation of the characters 'A', 'b' and 'c'.

  * [ 1; 2 ], which is an abbreviation of (1 :: 2 :: [])

     A pointer to an eAM array C1 of two elements: the first element of C1 holds the eAM integer 1. The second element of C1 holds a pointer to the eAM array of two elements C2.

     The first element of C2 holds the eAM integer 2. The second element of C2 holds a null pointer, i.e. a ``reference'' to the representation of [].

     Note that the elements of the list are integers in this example. If they were something more complex, for example strings, the first elements of C1 and C2 would be pointers.

To do: examples of objects with behaviour.

Runtime support structures
==========================

Most non-word objects are stored in a garbage-collected heap. The management of the heap is entirely transparent even at the eAM level: many instructions allocate a datum on the heap and return a pointer to it, storing the pointer on the stack or in a register. The stack and the registers are provided to hold temporary data.

The stack is a simple LIFO container of word objects, divided into frames. Each frame represents an activation of a subprogram or a block, and is essential especially to implement recursion. Many eAM instructions work on the stack, taking operands from it or using it to return a computed value. Other instructions push or pop entire frames on the stack: they are needed to enter or exit a block, and to implement subprogram calls. The stack is not limited in size and can not overflow.

Some eAM instructions use the registers instead of the stack to make computations. Registers are faster to manipulate than the stack, but are provided in a limited number and are not sufficient by themselves to handle recursion.

Registers are created at initialization time; their number is defined by the program and cannot grow at runtime. Registers are divided in several groups, according to the data they can hold:

word registers
     A word register, also called general register, can contain an object of any word type; this is very useful to implement polymorphic procedures, whose semantic does not depend on the type of the argument.

     Word registers are also the only ones used by eAM instructions operating with registers to do compuations on integers and pointers. Computations (The idea of ``computation'' does not include copying: any word-sized value can be passed in a word register and hence blindly copied into the stack, the heap or another register. This generic operation does not depend on the type of the operand but only on its size, and it is reasonable to allow it in general registers.) with floats can not be done in word registers, even if word registers can hold float values (since they are word-sized).

wide integer registers
     A wide integer register can only contain a wide integer object.

float registers
     Float registers are the only ones used by the eAM instructions operating with registers to do computations on floats. Computations with integers and pointers can not be done in float registers.

wide float registers
     A wide float register can only contain a wide float object.

wide wide float registers
     A wide wide float register can only contain a wide wide float object.

A similar distinction does not exist for the stack: there is only one stack, and it is limited to word objects (including floats): you can not directly push a non-word object onto the stack: you can only push a pointer to it.

This is an eAM program example using the stack to evaluate the expression (2 + 5) - 1:

     pshci   2       # Push 2
     pshci   5       # Push 5
     s_addi          # Pop two values, sum them and push the result
     # The value of (2 + 5) is on the top of the stack
     pshci   1       # Push 1
     s_subi          # Subtract top from undertop, pop both and push
                     # the result of the subtraction
     # The result is on the top of the stack

This program also evaluates the same expression, but uses registers instead of the stack:

     ldci    $g1 2       # $g1 := 2
     ldci    $g2 2       # $g2 := 5
     addi    $g3 $g1 $g2 # $g3 := $g1 + $g2
     # Now $g3 holds (2 + 5), i.e. 7
     ldci    $g4 1       # $g4 := 1
     subi    $g5 $g3 $g4 # $g5 := $g3 - $g4
     # Now $g5 holds the result

The previous examples are meant to illustrate the two possible styles of evaluation, and nothing more. Both could be heavily optimized.

Subroutines and blocks
======================

To do: talk about frame pointer, stack pointer, frame format

Calling conventions with operands in the stack
----------------------------------------------

To do: document To do: an example

Calling conventions with operands in the registers
--------------------------------------------------

To do: design, implement and document To do: an example

The eAM garbage collector
=========================

The eAM includes a pseudo-generational mark and sweep collector with conservative pointer finding, not incremental at the time of this writing.

The implementation is relatively simple; it can be roughly divided into two parts: the allocator and the collector.

Objects are allocated from buffers called pages. There are two sorts of pages: homogeneous pages and large pages.

Homogeneous pages
-----------------

A homogeneous page contains objects (called homogeneous objects) of the same size K (in words); all homogeneous pages have exactly the same size S (tunable via a C macro #define); hence the number of objects in a single homogenous page depends on K: pages with a smaller K contain more objects, and pages with a larger K contain fewer objects.

In each homogeneous page non-allocated objects are linked via a simple unidirectional free-list. For each object there is an associated allocated bit, also stored in the same page, which is set to 1 if and only if the object is allocated. Each page finally contains a field holding the number of its allocated objects.

These simple data structures allow to perform the following operations with time complexity O(1):

  * check whether an object is allocated in a given page

  * allocate an object from a given page

  * free an object, returning it to its page

  * check whether a page is empty

  * check whether a page is full

Each large page also holds a GC bit for each object, used by the collector.

All homogeneous pages are allocated with alignment S using memalign(); this allows to find the page of an homogeneous object with a bit-masking of its address, a very fast operation. In the implementation the value of S is computed from the value of the C macro PAGE_OFFSET_WIDTH defined in eam/gc/heap.h.

A pointer to each homogeneous page is stored in the hash table set_of_homogeneous_pages (defined in eam/gc/homogeneous.c). This makes possible to check whether an object is homogeneous with complexity O(1) in the average case (one bit-masking plus one hash table access).

Homogeneous pages with various values of K are created during initialization, but of course not covering every possibile size. So, if an object of a given size is asked, the allocator could return a slightly larger object: in this case we speak about inexact allocation (in the other case we speak about exact allocation). The little waste of space implied by inexact allocation seems not to be a problem in practice.

There is an array indicized by any given possible K from 0 to the maximum allowed value MAXIMUM_HOMOGENEOUS_SIZE, homogeneous_pages, defined in eam/gc/gc.c; among the rest it contains, for each size, its best approximation. So also inexact allocation has complexity O(1) when a non-full page of the right size exists.

The other fields of homogeneous_pages are, for each K, the bidirectional list of non-full homogeneous pages for objects of size K and the bidirectional list of full homogeneous pages for objects of size K. The list structures make easy adding or removing homogeneous pages as needed.

A final note: even if the GNU system allows to free a block allocated with memalign() there is no portable way to do it; so homogeneous page are actually destroyed only on GNU systems (The type of system is automatically determined at configure time.); on the other systems they are created and kept allocated forever, in the hope that they will be needed again.

Large pages
-----------

Sometimes objects larger than MAXIMUM_HOMOGENEOUS_SIZE words, or even larger than S words, are needed. Some other structure is needed, since those objects can not fit in homogeneous pages some other structure is needed.

Managing a large page is simpler than managing a homogeneous page: a large page holds one and only one large object: large pages are created when allocating a large object, and destroyed when a large object is freed: there is no need to keep free-lists or allocated bits. Moreover freeing a large object immediately releases storage; this can be an advantage when really large sizes are involved.

Each large page also holds the GC bit (The ``bit'' is effectively implemented with a word. In C it makes sense to use a bit vector, but a bit vector of just one element effectively takes more space than a bit.) for its object.

Large pages do not need a specific alignment: they are simply allocated with malloc() and freed with free().

A pointer to each homogeneous object is kept in the hash table set_of_large_objects, defined in eam/gc/large.c. This enables to check whether an object is large with complexity O(1) in the average case (one hash table access).

All large pages are linked in the bidirectional list list_of_large_pages, defined in eam/gc/gc.c. Note that all large pages are full, since when they become empty they are immediately destroyed, and there is no intermediate condition: large pages can only be full or empty.

A large page is just a thin shell enclosing its large object and the little bookkeeping information needed.

Allocator
---------

After the initialization performed by void initialize_garbage_collector(), declared in eam/gc/gc.h, all data structures are set up and a homogeneous page is created for the values of K belonging to a certain predefined set Q (The current algorithm allocates pages for
S = 1, 2, 3, ... MAXIMUM_SMALL_HOMOGENEOUS_SIZE and
S= 2*MAXIMUM_SMALL_HOMOGENEOUS_SIZE,
4*MAXIMUM_SMALL_HOMOGENEOUS_SIZE,
8*MAXIMUM_SMALL_HOMOGENEOUS_SIZE, ... MAXIMUM_HOMOGENEOUS_SIZE.

MAXIMUM_SMALL_HOMOGENEOUS_SIZE and MAXIMUM_HOMOGENEOUS_SIZE are
defined in eam/gc/gc.h.). No large pages are created at initialization time. They are created at runtime, just when needed.

The interface of the allocator is very simple; all the needed functions are declared in the header eam/gc/gc.h.

Exact allocation is performed by word_t allocate_exact(integer_t words_no).

allocate_exact() works by allocating an object from the first page of the list of non-full homogeneous pages at homogeneous_pages[WORDS_NO]; the list is always kept non-empty. When the page gets full it is moved from the list of non-full pages to the list of full pages at homogeneous_pages[WORDS_NO]; if the list of non-full pages becomes empty then a new page is created.

Inexact allocation is performed by word_t allocate_inexact(integer_t desired_words_no). If desired_words_no is not greater than MAXIMUM_HOMOGENEOUS_SIZE then allocate_inexact() computes the best approximated size by simply looking at the field inexact_size of homogeneous_pages[DESIRED_WORDS_NO], then calls allocate_exact(); else it creates a new large page and returns its object.

Note that allocation of large objects is always considered inexact.

Exact allocation is slightly faster than inexact allocation, but can be used only when the requested size K belongs to Q; if the requested size does not belong to Q the behaviour is undefined, which is a nice way to say that the program will most probably crash, and the collector will surely not work.

Collector
---------

The header eam/gc/gc.h also contains the interface to the collector.

void initialize_garbage_collector() transparently starts a new concurrent thread which from time to time (In the current implementation the concurrent thread wakes up every GC_TEST_TIMEOUT nanoseconds.) checks whether a collection would be needed, and in the affermative case sets the flag int should_we_collect to a nonzero value.

The mutator has the responsibility to periodically (In the current implementation the mutator checks the flag right after each application of a recursive function.) check the flag, and request a collection if the flag is nonzero. Note that there is no need of synchronization here: one thread reads the flag but does not write it, the other one writes it but does not read it.

For each collection cycle the mutator must explicitly notify the collector about all roots, calling void add_gc_root(word_t p) or, when there is more then one root in a single buffer, void add_gc_roots(word_t* buffer, size_t words_no).

The roots of the eAM are:

  * All the elements of the stack

  * Word registers

  * The I/O register

  * Globals

  * The environment register

  * exception_value

  * exceptions_stack[I].environment, for each element I of the exception stack

String constants are not roots: there is no need to keep them in the garbage-collected heap, so they are simply allocated with malloc() at startup time. This saves a little time when marking.

After notifying the collector about the roots a call to void garbage_collect() performs marking and sweeping (In the current implementation garbage_collect() suspends the mutator.).

To do: more details? Implementation is quite ``conventional'' here...

Pseudo-generational garbage collection
......................................

It would be slow to perform a full mark at every garbage collection cycle, so the eAM collector implements a pseudo-generational marking algorithm. What we call ``pseudo-generational'' garbage collection is a particular case of the generational garbage collection, particularly simple but quite effective. The heap is conceptually partitioned into two generations:

  * the old generation contains all the object which survived the last garbage collection cycle;

  * the young generation contains the objects which were allocated after the last collection.

Minor collections, performed relatively often, only scan the young generation, making the marking phase noticeably faster; note that marking time usually dominates over sweeping time.

Major collections, performed less often (The current implementation uses a rough heuristic: one collection every MINOR_GC_CYCLES_NO minor collections is major (MINOR_GC_CYCLES_NO is defined in the header eam/gc/gc.h). This will be improved.), scan both the young and the old generation. Major collection are slower than minor collection but free more storage.

The main idea of pseudo-generational collection is that the GC bits are cleared only at the beginning of major collections: in minor collactions the old generation objects are seen as already marked, so they are not recursively (However old generation objects can be scanned from the roots. This is rarely a problem: roots should have not a very large size (at least if stack usage is not high, and high stack usage usually indicates subotimal use of tail-recursion).) scanned.

The mutator has no direct control over the generations. It can only request a collection, and it's the function garbage_collect() to decide whether a minor or major collection is needed.

Safe points
-----------

To do

eAM instructions
================

The instructions of the eAM are described in full detail in eAM instructions.

eAM instructions
****************

This chapter describes in detail all the instruction of the epsilon Abstract Machine. Familiarity with the epsilon memory model and runtime structures is assumed.

This chapter is of no particular use for writing programs in epsilon. It is useful, instead, to understand how the internals of epsilon work and especially to extend the language or the runtime system.

Naming conventions
==================

Each eAM instruction is identified by a unique mnemonic in the textual form of eAML. We are going to introduce the rules which were used to choose the mnemonics names to make them more consistent and easier to remember.

By convention, when an instruction works on operands with fixed type, a suffix of the mnemonic identifies that type: i for integers, f for floats and s for strings. For example the s_addi instruction executes an addition on integer operands.

When more than one instruction exists doing the same work, but with a version taking a parameter from a register, another taking a parameter from the stack and still another taking one or more immediate parameters, the versions are easily recognizable from the prefix or desinence in their mnemonic:

  * The version with immediate parameters has the _i desinence in its mnemonic.

  * The version with parameters from the stack has the s_ prefix in its mnemonic.

  * The version with parameters in the registers has no prefix or suffix.

For example, s_addi adds two integer taken from the stack, and s_addi_i adds an integer taken from the stack to the immediate integer which is the parameter of the instruction.

Some instructions are provided in two versions, one safe (i.e. making runtime checks) but less fast, the other faster but not safe. ``Fast'' versions are identified by a f_ prefix in their mnemonic. If the s_ prefix is also present, s_ preceeds f_ in the mnemonic, such as in s_f_divi.

In the following immediate integer parameters are indicated by N, M, X, Y or Z; strings are indicated by S, and labels by L:. Register parameters are indicated by a dollar-sign ($) followed by an letter, such as $A or $X.

Writing conventions for stack and registers configurations
==========================================================

In this chapter we also describe instructions updating the stack or the registers: for brevity we follow these writing conventions:

  * Stack configurations are written horizontally, with the bottom of the stack at the left side. The bottom is identified by a ``||'' symbol, the top by a ``|'' symbol, and elements are separated by a ``|'' symbol. For example ||A|B| is a two-elements stack containing the A object at the bottom, and the B object on the top. The ``...'' symbol stands for ``some elements whose value is not specified'', except when found in sequences like ``|A1|...|AN|'', where the dots stand for exectly N-2 elements which have as values the elements of the succession A from 2 to N-1.

  * Register configurations are written horizontally as semicolon-separated sequences surrounded by backets, such as [-1;"a";3.7]. The leftmost element represents the content of the $0 register, the second one of $1, and so on. For the ...-notation we follow the same conventions as in writing the stacks.

  * For illustrating the effect of executing an instruction we show the configuration of stack, registers or anything relevant before the execution, the instruction name with parameters, and finally the configuration after the execution. When the ...-notation is used in both the before and after configurations, the unexpressed elements are considered to be the same, if not otherwise noted.

     For example:

     ||...|A|

     s_addi_i N

     ||...|A+N|

     For brevity's sake register updates can also be noted as

     $A := EXP($B, ..., $Z)

     where $A is the updated register, and EXP($B, ..., $Z) is any expression involving registers $B, ..., $Z. Note that in the expression at the right of the ``:='' symbol ``$X'' represents the content of the $X register, not its address.

Writing conventions for structures
==================================

If we stay at the level of the eAM, epsilon structures are not anything more than arrays (or tuples).

Arrays are shown in a visual way as sequences of objects separated by commas and surrounded by angular parentheses. Null pointers are written as ``null''. For example this

<1, <2, <3, <4, null>>>>

is the eAM representation of the epsilon list [1; 2; 3; 4].

This, instead,

<<"test", null>, null>

is the eAM representation of the epsilon object (["test"], []), and also of the epsilon object [["test"]].

Instructions classification
===========================

eAM instructions are divieded into several categories:

  * arithmetic/logic instructions make computations of arithmetic or logic nature. Some instructions are available to work with integer values, others for working with float values.

  * conversion instructions translate data from one representation to another.

  * structures management instructions work with memory structures bigger than one word such as arrays and conses.

  * stack management instructions update the stack, copying or removing elements from the top, or copying objects from the registers to the stack or from the stack to the registers.

  * flow control instructions control the flow of the execution, with unconditional or conditional jumps.

  * subprograms management instructions manage entering and exiting from subprograms and blocks.

  * variables management instruction deal with program variables, be they locals, nonlocals or globals.

  * input/output instructions do input and output, and allow interfacing with code written in other languages.

  * exception handling instructions are used to signal error conditions and to manage failures.

  * special instructions are the few instructions which do not fit in the above categories.

Arithmetic/logic instructions on integers
=========================================

Arithmetic/logic instructions operating on integer values are essential since they are used even in the simplest programs. They do not involve memory management, and for this reason they are fast compared to other ones.

Some instructions taking two operands from the stack exist also in a version with the second operand as an immediate parameter (for example s_addi and s_addi_i N). The versions with immediate parameters are not always applicable, but faster.

In the following subsections we are going to describe every instruction in detail.

addi $A $B $C
-------------

The addi $A $B $C instruction adds the content of the $B register to the content of the $C register, storing the result into the $A register:

$A := $B + $C

addi_i $A $B N
--------------

The addi_i $A $B N instruction adds N to the content of the $B register, storing the result into the $A register:

$A := $B + N

andi $A $B $C
-------------

The andi $A $B $C instruction stores a nonzero value into $A if both $B and $C have nonzero value, else it stores zero into $A.

divi $A $B $C
-------------

The divi $A $B $C instruction divides the content of the $B register by the content of the $C register, storing the result into the $A register:

$A := $B / $C

If the content of the $C register is zero the execution terminates reporting an error.

divi_i $A $B N
--------------

The divi_i $A $B N instruction divides the content of the $B register by N, storing the result into the $A register:

$A := $B / N

No division-by-zero check is made, since it would make never sense to use this instruction with N=0.

f_divi $A $B $C
---------------

The f_divi $A $B $C instruction divides the content of the $B register by the content of the $C register, storing the result into the $A register:

$A := $B / $C

No divide-by-zero check is made, so the program may crash if the content of the $C register is zero. This instruction is faster than divi $A $B $C, but you should only use it when you are definitively sure that $C can not hold a zero value.

f_modi $A $B $C
---------------

The f_divi $A $B $C instruction divides the content of the $B register by the content of the $C register, storing the rest of the division into the $A register:

$A := $B mod $C

No divide-by-zero check is made, so the program may crash if the content of the $C register is zero. This instruction is faster than divi $A $B $C, but you should only use it when you are definitively sure that $C can not hold a zero value.

ldci $R N
---------

The ldci $R N instruction updates the content of the $R register to the integer constant N:

$R := N

modi $A $B $C
-------------

The modi $A $B $C instruction divides the content of the $B register by the content of the $C register, storing the rest of the division into the $A register:

$A := $B mod $C

If the content of the $C register is zero the execution terminates reporting an error.

modi_i $A $B N
--------------

The modi_i $A $B N instruction divides the content of the $B register by N, storing the rest of the division into the $A register:

$A := $B mod N

No division-by-zero check is made, since it would make never sense to use this instruction with N=0.

muli $A $B $C
-------------

The muli $A $B $C instruction multiplies the content of the $B register for the content of the $C register, storing the result into the $A register:

$A := $B * $C

muli_i $A $B N
--------------

The mul_i $A $B N instruction multiplies the content of the $B register for N, storing the result into the $A register:

$A := $B * N

nxori $A $B $C
--------------

The nxori $A $B $C instruction stores a nonzero value into $A if either both $B and $C have nonzero content, or both $B and $C have zero content, else it stores zero into $A.

ori $A $B $C
------------

The ori $A $B $C instruction stores a nonzero value into $A if at least one of $B and $C has nonzero content, else it stores zero into $A.

s_f_divi
--------

This instruction is identical to s_divi, except that it does not check for the divison-by-zero error condition.

The program may crash if the top of the stack is 0; you should use this instruction only if you are definitively sure that the divisor is not zero.

s_f_divi is faster than s_divi.

s_addi
------

The s_addi instruction replaces the two integer objects on the top of the stack with a single object with their sum as value.

||...|A|B|

s_addi

||...|A + B|

s_addi_i N
----------

The s_addi_i instruction replaces the integer object on the top of the stack with the sum of it and the N parameter.

||...|A|

s_addi_i N

||...|A + N|

s_addi_i N is faster than pshci N; s_addi.

s_andi
------

The s_andi instruction replaces the two integer objects A and B on the top of the stack with a single object with a nonzero value if both A and B have nonzero value, otherwise with a single object with zero value.

For example:

||...|-34|0|

s_andi

||...|0|

s_divi
------

The s_divi instruction replaces the two integer objects on the top of the stack with a single object with their quotient as value.

In case of division by zero this instruction prints an error message and terminates the execution of the program.

||...|A|B|

s_divi

||...|A / B|

s_divi_i N
----------

The s_divi_i instruction replaces the integer object on the top of the stack with the quotient of it and the N parameter.

The program may crash if N is 0; no divide-by-error check is done since it makes never sense to use s_divi_i 0.

||...|A|

s_divi_i N

||...|A / N|

s_divi_i N is faster than pshci N; s_divi, and even than pshci N; s_f_divi.

s_eqi
-----

The s_eqi instruction replaces the two integer objects on the top of the stack with a single object with a nonzero value if the integer objects are equal, otherwise with zero.

For example:

||...|A|A|

s_eqi

||...|1|

s_gti
-----

The s_gti instruction replaces the two integer objects A and B on the top of the stack with a single object with a nonzero value if A is greater than B, otherwise with zero.

For example:

||...|172|200|

s_gti

||...|0|

s_gtei
------

The s_gtei instruction replaces the two integer objects A and B on the top of the stack with a single object with a nonzero value if A is greater than or equal to B, otherwise with zero.

For example:

||...|172|172|

s_gtei

||...|-1|

s_lti
-----

The s_lti instruction replaces the two integer objects A and B on the top of the stack with a single object with a nonzero value if A is less than B, otherwise with zero.

For example:

||...|172|200|

s_lti

||...|-1|

s_ltei
------

The s_ltei instruction replaces the two integer objects A and B on the top of the stack with a single object with a nonzero value if A is less than or equal to B, otherwise with zero.

For example:

||...|172|172|

s_ltei

||...|-1|

s_modi
------

The s_modi instruction replaces the two integer objects on the top of the stack with a single object with the rest of their division as value.

In case of division by zero this instruction prints an error message and terminates the execution of the program.

||...|A|B|

s_divi

||...|A mod B|

s_modi_i N
----------

The s_modi_i instruction replaces the integer object on the top of the stack with the rest of the divion of it by the N parameter.

The program may crash if N is 0; no divide-by-error check is done since it makes never sense to use s_divi_i 0.

||...|A|

s_modi_i N

||...|A mod N|

s_modi_i N is faster than pshci N; s_modi, and even than pshci N; s_f_modi.

s_muli
------

The s_muli instruction replaces the two integer objects on the top of the stack with a single object with their product as value.

||...|A|B|

s_muli

||...|A *B|

s_muli_i N
----------

The s_muli_i instruction replaces the integer object on the top of the stack with the product of it and the N parameter.

||...|A|

s_muli_i N

||...|A *N|

s_muli_i N is faster than s_pshci N; muli.

s_noti
------

The s_noti instruction replaces the integer object A on the top of the stack with a nonzero value if A has zero value, else with zero.

For example:

||...|-34|

s_noti

||...|0|

s_neqi
------

The s_neqi instruction replaces the two integer objects on the top of the stack with a single object with value zero if the integer objects are equal, otherwise with a single object with a nonzero value.

For example:

||...|A|A|

s_neqi

||...|0|

s_nxori
-------

The s_nxori instruction replaces the two integer objects A and B on the top of the stack with a single object with zero value if exactly one of A and B has a nonzero value, otherwise with a single object with a nonzero value.

||...|-34|0|

s_nxori

||...|0|

s_ori
-----

The s_ori instruction replaces the two integer objects A and B on the top of the stack with a single object with a nonzero value if at least one of A and B has nonzero value, otherwise with a single object with zero value.

||...|0|-23|

s_ori

||...|1|

s_subi
------

The s_subi instruction replaces the two integer objects on the top of the stack with a single object with their difference as value.

||...|A|B|

s_subi

||...|A - B|

s_subi_i N
----------

The s_subi_i instruction replaces the integer object on the top of the stack with the difference of it and the N parameter.

||...|A|

s_subi_i N

||...|A - N|

s_subi_i N is faster than pshci N; s_subi.

s_xori
------

The s_xori instruction replaces the two integer objects A and B on the top of the stack with a single object with a nonzero value if exactly one of A and B has a nonzero value, otherwise with a single object with zero value.

||...|-34|0|

s_xori

||...|1|

subi $A $B $C
-------------

The subi $A $B $C instruction subtracts the content of the $C register from the content of the $B register, storing the result into the $A register:

$A := $B - $C

subi_i $A $B N
--------------

The subi_i $A $B N instruction subtracts $N from the content of the $B register, storing the result into the $A register:

$A := $B - N

swp $A $B
---------

The swp $A $B instructions swaps the contents of the $A register and the $B register. The semantics of this instruction might be summarized as:

$A := $B, $B := $A

where the two assignments take place in parallel.

xori $A $B $C
-------------

The xori $A $B $C instruction stores a nonzero value into $A if exactly one of $B and $C has nonzero content, else it stores zero into $A.

Arithmetic/logic instructions on floats
=======================================

Conversion instructions
=======================

Structures management instructions
==================================

mka $A $B
---------

The mka $A $B instruction assigns to the $A register a new array with undefined content and with the content of the $B register as size.

mka_i $A N
----------

The mka_i $A $B instruction assigns to the $A register a new array with undefined content and with size N.

s_mka
-----

The s_mka instruction replaces the integer N on the top of the stack with a new uninitialized array of size N:

For example:

||...|3|

s_mka

||...|<???, ???, ???>|

s_mka_i N
---------

The s_mka_i N instruction pushes a new uninitialized array of size N on the top of the stack:

For example:

||...|

s_mka_i 2

||...|<???, ???>|

cns $A $B $C
------------

s_cns
-----

car $A $B
---------

s_car
-----

cdr $A $B
---------

s_cdr
-----

lkp $A $B $C
------------

lkp_i $A $B N
-------------

s_lkp
-----

s_lkp_i N
---------

f_lkp $A $B $C
--------------

f_lkp_i $A $B N
---------------

s_f_lkp
-------

s_f_lkp_i N
-----------

upd $A $B $C
------------

upd_i $A N $B
-------------

f_upd $A $B $C
--------------

f_upd_i $A N $B
---------------

s_upd
-----

s_upd_i N
---------

s_f_upd
-------

s_f_upd_i N
-----------

Stack management instructions
=============================

cpy
---

grw N
-----

pop
---

popm N
------

s_swp
-----

ld $R
-----

st $R
-----

Flow control instructions
=========================

j L:
----

jnz $R L:
---------

jz $R L:
--------

s_jnz L:
--------

s_jz L:
-------

Subprograms management instructions
===================================

cll N
-----

clltr N
-------

ret $R
------

s_ret
-----

Variables management instructions
=================================

lcl $R N
--------

s_lcl N
-------

nlcl $R N M
-----------

s_nlcl N M
----------

Input/output instructions
=========================

Exception handling instructions
===============================

Special instructions
====================

ccod S
------

The ccod S instruction exectutes the C code contained in the immediate string parameter S.

gc
--

The gc instruction performs a full garbage collection cycle, temporarily suspending the program.

This instruction is used when there is an urgent need of free memory. Normally the garbage collector would run concurrently with the program, without the need of executing eAM instructions for this purpose.

hlt N
-----

The hlt N instruction halts the program. The integer parameter N is returned to the operating system as the process exit code.

nop
---

The nop instruction does absolutely nothing. It is used in contexts where an instruction is expected but no effect is needed, such as after a label which is the target of a jump.

For example:

       # Compute a number and store it into $4:
       ...
       jz $4 END_OF_PROGRAM:
       ...
     END_OF_PROGRAM:
       nop

nop instructions have no effect on runtime performance.

Part IV - Extending epsilon
***************************

This part deals with the problems of extending GNU epsilon with code written in other languages, and with the ways of interfacing epsilon with other languages.

Knowledge of the eAM (especially data representation, see Representation of epsilon data in the eAM) and experience with C programming are assumed.

C libraries
***********

Say you want to access a database, or to do some 3D graphics in an epsilon program. These are not unusual requirements.

It's relatively easy to do that in C: there is an interface someone else has written (for example the client library of PostgreSQL libpq, or Mesa3D); you just have to call some already defined functions in your code.

Most other languages, such as C++, Java, Python and most Lisp implementations have some feature allowing you to call code written in C; this is a solution to the problem: instead of, for example, natively supporting PostgreSQL, most languages allow you to call your C code in some way, and your C code can make use of all the needed libraries.

This is also the solution provided by epsilon.

A wrong solution
================

Let us start with a wrong solution, which was actually implemented in an early version of epsilon. An ``easy'' way to extend the library is to extend the eAM: for example, if you need access to the C function system(), you can just add a new eAM instruction sstm, which takes a string, converts it from the epsilon format into the C format, and calls the system() function of the C library. They you must write some ``glue'' code to call the eAM instruction sstm: you will need an epsilon function taking a string and returning an action of integer:

     execute_program : string -> i/o of integer

Note that now execute_program will have to be written in eAML! There is no way around this (Except modifying the compiler.), since you need to use the eAM instruction sstm, which is not generated by the epsilon compiler.

Also note that the aAM has changed: the new instruction has made the abstract machine incompatible with the old version; all epsilon libraries must be recompiled, too.

This solution is wrong for several different reasons:

  * It incompatibly changes the eAM

  * It is complicated and error-prone to write eAM instructions

  * It makes the generated C code grow

  * Writing the glue function in eAML is very tedious and error prone

  * For linking new libraries at compile time you also have to update the Autoconf/Automake machinery

  * ...

The right solution
------------------

The right solution is writing the extension code at a level which is somewhere in the middle between eAML and epsilon; you must be able to do that without recompiling the eAM, to retain compatibility.

The eAM provides a mechanism for linking a C library at initialization time. The C library can define some functionalities (either limited to pure calculus or comprising I/O) to be made available to epsilon. Often a C library needs to refer to some other shared library written to be called from C (such as libpq). This can be linked at initialization time, too, and is called a dynamic library. Dynamic libraries are not directly visible from epsilon.

To do: I don't like this chapter. Rewrite most of it.

Using epsilon with Scheme
*************************

Part V - Examples
*****************

In this part some nontrivial examples of epsilon programs are presented; they are not necessarily useful by themselves or complete, but nonetheless they show some usage patterns quite common in epsilon programming.

In this context formal elegance and readability is considered more important than efficiency.

Of course also the example programs are free software, covered by the GNU General Public License (see Copying). The complete source code for all these examples is distributed along with GNU epsilon.

mu-lisp
*******

mu-lisp is a simple Lisp (For more information about Lisp,
and for realistic implementations, see http://www.lisp.org.) interpreter with static scoping, fully written in epsilon.

Like any other Lisp implementation mu-lisp is interactive: the implementation of its REPL constitues a good example of purely functional I/O.

It is a Lisp/1, i.e. it has a single namespace for variables and functions.

To do: scanner and parser...

To do...

The predefined symbols are...

To do: source overview

To do: example programs.

mu-basic
********

To do

Appendices
**********

This part will be a collection of various important non-technical information related to epsilon, licenses and references.

Copying This Manual
*******************

     [file fdl.texi not included]