Back Home Up Next


Elisa is a new programming language. Its purpose is to combine the best features of procedural programming, functional  programming, object-oriented programming and logic programming into one coherent linguistic framework. The underlying assumption is that integration of the best features of different paradigms may create new possibilities of solving problems and may open new ways of programming. 

During this integration process it turned out that a complete integration of different paradigms is not always possible. Mainly because of conflicting requirements. For example, assignment statements are essential in procedural and object-oriented paradigms, but are forbidden in the functional paradigm. In such cases we have taken a pragmatic approach; for example, we accepted assignments statements but with a limited scope. And so we did in other cases. A more comprehensive justification can be found in Integrating Different Programming Paradigms.

The result is a language not hindered by compatibility requirements from the past but a language that uses the best concepts of different paradigms. Not by piling up feature by feature on top of an existing language but by carefully designing a new language. As explained, this approach also means that not all the features of the different paradigms can be preserved: compromises are sometimes necessary, as will be made clear. 

In this paper we will discuss the implications of three main topics: Multi-value Expressions, Pattern Matching, and Domain Orientation. More information can be found via  Elisa & Domain Orientation.















1  Multi-value Expressions

One of the  important concepts of Elisa are multi-value expressions. In almost all programming languages the evaluation of an expression results in one value. Such a value may be an integer, a real, a character, or a value representing (an element of) a compound data structure. The only exceptions are procedure calls that return no value.  

However, there are often situations in daily life where an expression may represent many things. For example, if we are talking about all the students who are speaking Spanish or about all the customers living in New York, we are using expressions that may represent several entities. The same applies to numeric values. For instance, we can talk about all the odd numbers between 0 and 50 or about all the prime numbers between 1 and 100. In those cases, the corresponding expressions are representing more than one value. 

In Elisa we have generalized the concept of an expression: an expression in Elisa may represent more than one value. If such an expression is evaluated it may result in what we call a stream of values.


1.1 Basic Constructs

There are two basic constructs in Elisa to express multi-value expressions. The first one consists of a series of expressions, separated by commas and enclosed in parentheses: 

( expr1, expr2, expr3 ... )

Here are some examples:

( 5, 3 + 7, 12 * 3, 17 - 11, 13)?	==> 	(5, 10, 36, 6, 13)
( 3.5, 2.7 + 3.5, 3.4 * 2.0, - 5.6)?	==> 	(3.5, 6.2, 6.8, - 5.6)

The second basic construct is the range-expression. A range-expression is only defined in the language for integer values and represents a stream of successive integer values. For example, 3 .. 7 is a multi-value expression for (3, 4, 5, 6, 7).  In general,

m .. n represents the multi-value expression ( m, m+1, m+2 ..., n)

With this construct the number of integer values may be variable depending on the values of m and n. Three interesting situations can be distinguished depending on the actual values of m and n:

if m < n the expression represents n - m + 1 values

if m = n the expression represents only one value

if m > n the expression represents no value

The two basic constructs may be combined. For example:

    ( 2 .. 5, 5 .. 3, 2*(1..3))?         ==>        ( 2, 3, 4, 5, 2, 4. 6)

1.2  Multi-value Definitions


With these two constructs we are now able to make so-called definitions that are representing multiple data items. Let us start with a simple example:

f (integer, integer) -> multi(integer);
f (p, q) = p .. q;

This definition is based on the range operation. It represents a number of multiple values. For example, the evaluation of f(3, 6) will result in the values (3, 4, 5, 6); but the evaluation of f (7, 2) will result in no value. 

The fact that our definition may produce more than one data item is reflected in its signature. A signature is the first rule of a definition. It specifies the name, the number and types of the parameters and the result specification. As part of the result specification a so-called quantifier may be used. A quantifier specifies how many data items may be returned. There are four quantifiers defined in the language with the following meaning:

multi specifies that zero, one, or more data items of the given type may be returned
single specifies that one and only one data item of the given type will be returned
optional specifies that zero or one data item of the given type may be returned
nothing specifies that no data item will be returned

If the quantifier multi is used in a specification then an evaluation of the definition produces as many data items as can be produced by the definition depending on the values of the arguments. Take as an example:

g (integer, integer) -> multi(integer);
g (p, q) = ( p - q, p + q, p .. q );

This definition will produce a stream of at least two data items but may be more, depending on the values of p and q. For example, the evaluation of g(7, 2) will result in only two data items: (5, 9); but the evaluation of g(3, 5) will result in the stream (-2, 8, 3, 4, 5).  Such a definition is called a generator

The quantifier single is used if the definition produces one data item. If in a specification no quantifier has been specified, as default the quantifier single is assumed. This means, for example, that the definition:

F (integer, integer) -> integer;
F (x, y) = x + y;

is equivalent with:

F (integer, integer) -> single(integer);
F (x, y) = x + y;

If the quantifier optional is used in a specification then an evaluation of the definition produces zero, or maximally one data item even if more data items can be produced by the definition. This quantifier  can be used if you want to limit the number of data items to a maximum of one, even if there are more. For example, if you need only one employee speaking Spanish, you may use the optional quantifier. (The multi quantifier would give you all the Spanish-speaking employees). The optional quantifier (as well as the multi quantifier) also takes care of the situation that there are no data items with the required characteristics. 

The quantifier nothing is used if no data items are produced by the definition. The quantifier nothing can be interpreted as the name of a special, built-in type that has no values. Because there are no values, there are also no operations defined on nothing. Function-definitions specified with the nothing quantifier are comparable to what in some other programming languages are called procedures.

Let us see how the nothing quantifier may be used in a definition:

G (integer, integer) -> nothing;
G (p, q) = print(p + q);

In this example, the definition calls another definition print (not defined here) that also returns nothing.

Definitions are not restricted to integer values. Any type may be used in the signature of a definition. As an illustration we will give an example that makes use of a symbolic enumeration type. It defines parental relations that can be used to answer questions about ancestors. These relations are defined as follows:

type Person = (Mary, George, John, Liz, Albert, Alice, Jane, Harry, Unknown);
mother (Person) -> Person;
mother (=Mary)   = Liz;
mother (=George) = Liz;
mother (=John)   = Alice;
mother (=Liz)    = Jane;
mother (others)  = Unknown;
father (Person) -> Person;
father (=Mary)   = John;
father (=George) = John;
father (=John)   = Albert;
father (=Liz)    = Harry;
father (others)  = Unknown;
parents(Person) -> multi(Person);
parents( P ) = ( father(P), mother(P) );
grandmothers(Person) -> multi(Person);
grandmothers( P ) = ( mother( father(P)), mother( mother(P)) );
grandfathers(Person) -> multi(Person);
grandfathers( P ) = ( father( father(P)), father( mother(P)) );
grandparents(Person) -> multi(Person);
grandparents( P ) = parents( parents(P) );

The first line in this example introduces the type Person and enumerates the names of the relevant persons, including an Unknown person. The following lines are introducing the mothers and the fathers of the different persons. And then some parental relations are given. Each parental relation defines that for a given person multiple persons may be returned. For example, a person has always two parents and four grandparents. So, the parent definition produces for one person two persons and a grandparent definition produces two times two persons.

In an interactive session we may now question the system about the ancestors of a person. We will show some questions with their answers:

mother(Mary)?			==> 	(Liz)
father(mother(George))?		==> 	(Harry)
parents(Mary)?			==>	(John, Liz)
parents(Harry)?			==>	(Unknown, Unknown)
grandfathers(Mary)?		==>	(Albert, Harry)
grandparents(George)?		==>	(Albert, Alice, Harry, Jane)

These examples show how definitions may produce multiple answers.  To understand the implications of these constructs you are invited to write a corresponding program in your favorite programming language.

See also:

Lexical Elements 

Basic Data Types and Expressions





1.3  Filters


To illustrate the use of the optional quantifier the concept of filters will be demonstrated. A filter can be used to select optional data items from a stream. Suppose we want to select all the odd numbers of an integer input stream. We may write the following filter definition for odd numbers:

Odd(integer) -> optional(integer);
Odd(i) = i when mod(i, 2) <> 0;

In this example we use the when construct. This is a special expression. It uses the builtin mod function.  The mod (i, 2) function computes the remainder of the integer division i / 2. If the result is unequal to zero i is an odd number and the result of the Odd function is the value of i. If the result is equal to zero the value is even and no value will be returned.

Applying the Odd filter to a stream of integer numbers we get the following results:

Odd(1..15)?   ==>     (1, 3, 5, 7, 9, 11, 13, 15)

Let us now assume that we want to select all multiples of three of the new output stream and multiply the selected integers with 10. We may now write the following filter definition:

Triple(integer) -> optional(integer);
Triple(j) = 10 * j when mod(j, 3) == 0;

Applying the Triple filter to the Odd filter to a stream of integer numbers we get the following results:

Triple(Odd(1..15))?        ==>  ( 30, 90, 150)

This last example demonstrates the combined use of a filter and a map function.

See also:


Statements and Special Expressions



1.4  Descriptors 


Multi-value expressions may also be used for so-called descriptors. A descriptor is a dynamic data-structure, which describes a data-object. Suppose we want to write a multi-value definition for concentric circles. First, we need to define the concept of a circle. But before that can be done we have to define the concept of a two-dimensional point:

type Point;                                   << type declaration >>

Point(x = integer, y = integer) -> Point;     << signature >>

Point(x, y) =  Point:[x; y];                  << constructor operation >>

The first line introduces a new user-defined type. The second line is a signature of a definition. The third line is the definition-rule. It defines a  Point-descriptor. In our example it describes the layout and the data of a two-dimensional Point-descriptor.  For example, the following call will produce a Point-descriptor:

Point(2, 5)?    ==>  Point:[x = 2; y = 5]

Now we can define a circle:

type Circle;                                         << type declaration >>

Circle(Center = Point, Radius = integer) -> Circle;  << signature >>

Circle(Center, Radius) = Circle:[Center; Radius];    << constructor >>

The Circle definition makes use of the preceding Point type. For example, a call to the Circle definition:

Circle(Point(3, 7), 9)? 


will produce the following compound descriptor:


Circle:[Center = Point:[x = 3; y = 7]; Radius = 9];

Finally we are able to define concentric circles:

ConcentricCircles(Center = Point, Number = integer) -> multi(Circle);

ConcentricCircles(Center, Number) = Circle(Center, 1..Number);

What happens if we call  ConcentricCircles(Point(1, 2), 5)? The definition will return a stream of 5 Circle-descriptors, which are concentric around Point(1, 2). This example shows how a single definition may represent a number of descriptors.    

See also:



1.5 Components


In Elisa a software component is a self-contained building block that can be used by different programs.  It has a well-defined interface with its outside world. A software component is designed to perform a number of related functions. It consists of two parts:

1. the interface-section, which contains the signatures of all the operations and functions which may be called from outside the component. Additionally, it may also contain type-specifications.

2. the implementation-section, which contains the definitions of the operations and functions that are externally accessible as specified in the interface-section. It may also contain other definitions that are local to the component.

To illustrate the structure and use of components, let us assume that we want to create a tree transversal component for binary trees. A binary tree is a tree where every node has at most two branches. This means that in a binary tree all sub-trees are also binary trees. Tree traversal refers to the process of visiting each node in a tree, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited. We will implement preorder, inorder, postorder and levelorder traversal algorithms in one component.

component BinaryTreeTraversals (Tree, ItemType);
type Node;
type Tree = Node;
     Node (ItemType, LeftNode = Node, RightNode = Node) -> Node;

     Leaf (ItemType)    -> Node;
     Item (Node)        -> ItemType;

     Preorder (Tree)    -> multi (Node);
     Inorder (Tree)     -> multi (Node);
     Postorder (Tree)   -> multi (Node);
     Levelorder(Tree) 	-> multi (Node);
     Node (Item, LeftNode, RightNode) = Node: [ Item; LeftNode; RightNode ];

     Leaf (anItem) = Node (anItem, null(Node), null(Node) );
     Item (aNode) = aNode.Item;

     Preorder (=null(Node)) = no(Node);
     Preorder (Node) = ( Node, Preorder (Node.LeftNode), Preorder (Node.RightNode));

     Inorder (=null(Node)) = no(Node);
     Inorder (Node) = ( Inorder (Node.LeftNode), Node, Inorder (Node.RightNode));

     Postorder (=null(Node)) = no(Node);
     Postorder (Node) = ( Postorder (Node.LeftNode), Postorder (Node.RightNode), Node);	

     Levelorder(Node) = [ Queue = {Node};
	                  node = Node:items(Queue);
			   [ result(node);
			     add(Queue, node.LeftNode) when valid(node.LeftNode); 	
 			     add(Queue, node.RightNode) when valid(node.RightNode); 	

end component BinaryTreeTraversals;

This example shows a generic component with two parameters: the tree type and the item type, as is specified by the first line of the component.

The interface-section of the component  contains a type-specification and the signatures of the definitions that may be called from outside the component. The implementation-section contains the definitions that are externally accessible as specified in the interface-section. It may also contain other definitions that are local to the component.

The first definition specified in the interface-section, and defined in the implementation-section is the definition of a Node descriptor. It describes the layout and data of a node of a Tree. The node of a Tree is also a Tree. A Leaf of a Tree is a node without branches, as defined by the Leaf-definition.

The definitions for Preorder, Inorder, Postorder and Levelorder traversals are all multi-value definitions. They have all similar structures, except the last one. To compute the data for levelorder traversal a procedural approach has been taken.

The traversal definitions are so simple because they are recursive multi-value definitions. In a conventional programming language the program would be much more complex and it would take much more lines of coding. Not only the programmer of the component benefits from these simple definitions  but also the user of the component because of its straightforward multi-value interfaces. These observations are not only valid for this example but are applicable to many other software components.

Let us return to our example of tree traversals. Suppose we want to implement the following binary tree to demonstrate the preorder, inorder, postorder and levelorder traversals. 

        /  \
       /    \
      /      \
     2        3
    / \      /
   4   5    6
  /        / \
 7        8   9

The following program will perform the required transversals: First we instantiate the generic component, specifying that a tree of integers is needed, then we create a BinaryTree as specified by the tree picture, and then we call the definitions for preorder, inorder, postorder and level-order traversals.

use BinaryTreeTraversals (Tree, integer);
BinaryTree = Node(1,
Item(Preorder(BinaryTree))?		==>  	( 1, 2, 4, 7, 5, 3, 6, 8, 9) 
Item(Inorder(BinaryTree))?		==>	( 7, 4, 2, 5, 1, 8, 6, 9, 3) 
Item(Postorder(BinaryTree))?		==>	( 7, 4, 5, 2, 8, 9, 6, 3, 1) 
Item(Level_order(BinaryTree))?		==>	( 1, 2, 3, 4, 5, 6, 7, 8, 9)

See also:




Generic Components 




1.6  Iterators


In Elisa, an iterator is a multi-value definition that enables a programmer to traverse a data structure. The data structure may be an array, a list, or any other type of collection.  Various types of iterators are often provided via a component's interface. The data structure itself is often part of the implementation section of the component. 

Let us return to the previous example of a component for BinaryTreeTraversals. The data structure containing the binary tree is a compound structure of Tree nodes and is defined in the implementation section. Based on this data structure, 4 iterators are defined. Each by means of a multi-value definition. They all traverse the tree structure in different order: the definitions for preorder, inorder, postorder and level-order traversals.

This example shows how easy it is to use iterators in Elisa. No separate iterator objects, no different types of iterators, no complex iterator interfaces as in traditional languages. Simple multi-value definitions in Elisa are sufficient.

See also:


Examples involving Lists



1.7  Multiple Solutions


Some applications will require multiple solutions. Take for example a program which has to find the shortest path between two cities. It has to search for a number of paths in order to find the shortest. One solution can be complex, several solutions are even more complex. It turns out that the use of multi-value definitions in Elisa may alleviate this task. An example is in Finding Paths in a Graph. Other examples are given in Searching State Spaces. In this kind of applications multiple solutions are required. In these solutions multi-value expressions are playing a major role.


See also:




2  Pattern Matching

Pattern matching is used in definitions to select a corresponding definition rule. A definition may consists of a number of definition rules. Each definition rule is defined for one or more specific input values.

Multiple definition rules are often used to distinguish a number of cases, depending on parameter values. As an example of such a case analysis, we will write a definition which determines the number of days in a month of a non-leap year:

days (integer) -> integer;
days (2) 	= 28;
days (4) 	= 30;
days (6) 	= 30;
days (9) 	= 30;
days (11)	= 30;
days (X) 	= 31;

This definition consists of a signature and 6 definition rules. The definition has an integer as input, representing the month ( January = 1, February = 2, etc.). The output is also an integer, representing the number of days in a given month. In this example five months are explicitly mentioned. The remaining months are defined by the last definition rule.

We see that this definition is properly returning the numbers of days in a given month. However it returns also the days of non-existing months. For example, days(17) returns 31 as well as days(-5).

If the parameter is a name, as is the case in the last definition rule, then any argument value will match. So, all months not covered by the preceding definition rules are covered by this one.

As a general rule, if a definition should be defined for all cases then the last definition rule of a definition should cover the remaining cases not covered by previous definition rules. Later on, we will see examples where definitions are not handling all cases but only a selection of possible values.

We may conclude that any integer number is accepted by our definition. And that was certainly not our intention! To avoid this kind of problem and, in addition, to make our definition more readable, we will introduce an enumerated type specifying the names of the months and an adapted definition for the days in a month:

type Month = ( January, February, March, April, May, June, July,
	       August, September, October, November, December);
Days (Month) -> integer;
Days (=February)  = 28;
Days (=April)     = 30;
Days (=June)      = 30;
Days (=September) = 30;
Days (=November)  = 30;
Days (X)          = 31;

With this approach, we will not be tempted to ask for the days of non-existing months.

There is another aspect of our new example which should be explained: In the first five definition rules the name of the month is preceded by a = sign. We learned that if a parameter is a name it will match all argument values. However, we also want sometimes, as in our example, that names are representing values. To distinguish parameter names and parameter values we use the = sign. The = sign is used here as a prefix operator which says that the following name, or, sometimes the following expression, represents a value which should be used for matching and which is not a parameter name such as the X of the last definition rule.

See also:




2.1  Categories


In daily life we classify things into various classes. We know the differences between cats and dogs, streets and houses, triangles and circles; they all are belonging to different classes. Classes may be grouped into categories. Cats and dogs are belonging to the category of mammals, triangles and circles are belonging to the category of geometric figures. A category represents a set of classes. A class may belong to more than one category. For example, cats and dogs are not only belonging to the category of mammals, they also belong to the category of domestic animals together with fowls as hens and geese. 

In Elisa a category is characterized by a type and by category operations. The type specifies the set of classes belonging to the category. For example, a Vehicle may be a Car, a Motorcycle, or a Truck. In that case, Vehicle is the name of a category that consists of the classes Car, Motorcycle, and Truck. This may be specified as:

type Vehicle = category(Car, Motorcycle, Truck);

This type specification introduces Vehicle as the name of a new category. Car, Motorcycle, and Truck are type names of existing descriptor types. In this example, we assume that they are already defined by corresponding components (not shown here). 

Suppose there is a garage with cars, motorcycles and trucks. All the relevant information is stored in a heterogeneous collection. A heterogeneous collection may contain objects with different types. For some reason the garage-proprietor wants to know the weight of a vehicle and the owner of a vehicle. With this knowledge we may now define operations for the category Vehicle.  We may specify it in the following way:

Weight(Vehicle) -> optional (Weight);
Owner (Vehicle) -> optional (Owner);

 A category may be defined by a component. For example, the Vehicles component may be defined as:

component Vehicles;
 type Vehicle = category (Car, Motorcycle, Truck);
      Weight (Vehicle) -> optional (Weight);
      Owner (Vehicle)  -> optional (Owner);
      Weight (Car: C)        = Weight (C);
      Weight (Motorcycle: M) = Weight (M);
      Weight (Truck: T)      = Weight (T);
      Owner (Car: C)         = Owner (C);
      Owner (Motorcycle: M)  = Owner (M);
      Owner (Truck: T)       = Owner (T);
end component Vehicles;

Each operation defined for a category is split into definition rules for the constituent types. The definition rules are using dynamic type matching to select the proper type and to call the corresponding definition of the selected type. In this example, it is assumed that the Weight and Owner operations are also defined for the Car, Motorcycle, and Truck descriptors. 

Elisa also allows overlapping categories such as :

type Vessel   = category (Boat, Ship, Seaplane);
type Aircraft = category (Seaplane, Airplane, Helicopter);

The categories for Vessel and Aircraft have the Seaplane in common.

Similarly, we may also define categories of categories, such as:

type Conveyer = category (Vehicle, Vessel, Aircraft);

The concept of categories allows the programmer to introduce higher levels of abstractions. It is based on dynamic type matching and it is particularly useful in handling members of heterogeneous collections. 

See also:




2.2 Symbolic Expressions

Symbolic expressions are used in many fields. Mathematics, logic, artificial intelligence are all using symbolic expressions. Elisa has the facilities to create and manipulate symbolic expressions. To illustrate some of the capabilities of Elisa we use as an example symbolic differentiation and simplification of algebraic formulas. Before we are going to discuss that in detail we will first introduce algebraic formulas as examples of symbolic expressions. Symbolic expressions are based on terms, which is a universal built-in data type. Therefore we are defining a component for Formulas.

component Formulas;
 type formula = term;
              + formula => formula; 
              - formula => formula;
      formula + formula => formula;
      formula + integer => formula;
      integer + formula => formula;
      formula - formula => formula;
      formula - integer => formula;
      integer - formula => formula;
      formula * formula => formula;
      formula * integer => formula;
      integer * formula => formula;
      formula / formula => formula;
      formula / integer => formula;
      integer / formula => formula;
      formula ** formula => formula;
      formula ** integer => formula;
      integer ** formula => formula;
      abs (formula)      => formula;
      sqrt (formula)     => formula;
      sin (formula)      => formula;
      cos (formula)      => formula;
      ln (formula)       => formula;
      exp (formula)      => formula;
     << empty implementation section >>
end component Formulas;

A component for algebraic formulas

The component is user-defined. It introduces in the interface-section the type formula, and the term-signatures of the usual infix and prefix operations and some functions. However, the implementation-section of the component is empty. That means that of each definition only the signatures are defined. To make that clear at the interface level the => symbol is used. It indicates that there are no definition rules associated with this signature and that a 'call' of this signature will result in the creation of a corresponding term.

All operations used in formulas are represented by corresponding terms. We are now able to use formulas in our applications. Let us use the following example:

a, b, c, x => formula;
y = a * x ** 2 + b * x + c;

The execution of the definition of y results in the symbolic expression a * x ** 2 + b * x + c, which is assigned to y. The expression is evaluated according to the operator precedence rules as ((a * (x ** 2)) + (b * x)) + c and each sub-expression is represented by a term. The whole expression is represented by a tree of terms which has the following form:

                                           x   2
                                            \ / 
                                         a  **  b  x
                                          \ /    \/
                                           *     *
                                            \   /
                                             \ /
                                              +     c
                                               \   /
                                                \ /

Tree of formula a * x ** 2 + b * x + c

In mathematics, symbolic differentiation is a procedure that converts an algebraic expression into another algebraic expression that is called the derivative. This procedure can be written in Elisa as a definition that has as input an algebraic expression and a variable, and as output the derivative of the expression with respect to the variable. The definition makes heavily use of pattern matching and recursion. The following is a component dedicated to symbolic differentiation.

component Differentiation;
   diff (formula, formula) -> formula;
   diff (x, x)              = formula: 1;
   diff (u + v, x)          = diff (u, x) + diff (v, x);
   diff (u - v, x)          = diff (u, x) - diff (v, x);
   diff (u * v, x)          = diff (u, x) * v + u * diff (v, x);
   diff (u / v, x)          = diff (u, x) / v - u * diff (v, x) / v ** 2;
   diff (y ** integer:n, x) = n * y ** ( n - 1) * diff (y, x);
   diff (sin (y), x)        = cos (y) * diff (y, x);
   diff (cos (y), x)        = -sin (y) * diff (y, x);
   diff (ln (y), x)         = 1 / y * diff (y, x);
   diff (others, x)         = formula: 0;
end component Differentiation;

Notice that there is only one signature for the differentiation operation but that there are many definition rules: for each possible operation or function symbol in the formula a rule has been given. So each rule represents a particular case. If the differentiation operation is applied to a formula, then the patterns in the parameter-expressions of the first rule will be compared with the input formulas. If they match then the expression of the right-hand side of the rule will be evaluated. If they do not match, the patterns of the next rule will be taken for comparison. This process will continue until the patterns of a rule are matching or until the last rule of the definition has been met. In our example, the last rule represents the most general case. It will always be applied if no preceding ones do. 

Suppose we want to differentiate y as given by the previous example. Then we start with the following situation:

diff (y, x)

Substitution of the value of y gives us:

diff (a * x ** 2 + b * x + c, x)

Now we start with tree climbing to apply for each operation the corresponding transformations. The final result is:

0 * x ** 2 + a * (2 * x ** 1 * 1) + (0 * x + b * 1) + 0

To simplify the result we will introduce a simplification component: T

component Simplification;
   simplify (formula) -> formula;
   simplify (x + y) = reduce ( simplify (x) + simplify (y) );
   simplify (x - y) = reduce ( simplify (x) - simplify (y) );
   simplify (x * y) = reduce ( simplify (x) * simplify (y) );
   simplify (x / y) = reduce ( simplify (x) / simplify (y) );
   simplify (x ** y)= reduce ( simplify (x) ** simplify (y) );
   simplify (x)     = reduce (x);
   reduce (formula) -> formula;
   reduce ( 0 + x) = simplify (x);
   reduce ( x + 0) = simplify (x);
   reduce ( integer: x + integer: y) = formula: (x + y);
   reduce ( x - 0) = simplify (x);
   reduce ( 0 - x) = simplify (- x); 
   reduce ( integer: x - integer: y) = formula: (x - y);
   reduce ( 0 * x) = formula: 0;
   reduce ( x * 0) = formula: 0;
   reduce ( 1 * x) = simplify (x);
   reduce ( x * 1) = simplify (x);
   reduce ( integer: x * integer: y) = formula: (x * y);
   reduce ( x / 1) = simplify (x);
   reduce ( 0 / x) = formula: 0;
   reduce ( integer: x / integer: y) = formula: (x / y);
   reduce ( x ** 1) = simplify (x);
   reduce ( x ** 0) = formula: 1;
   reduce ( integer: x ** integer: y) = formula: (x ** y);
   reduce (x) = x;
end component Simplification;

 Algebraic Simplification Component

The simplification procedure consists of two mutual recursive definitions, both based on pattern matching. This is because the simplification procedure creates many intermediate sub-trees that may be simplified further.

With this component it is possible to simplify algebraic expressions to some degree. This component will eliminate all redundant terms based on 0 and 1 and will lead to considerable size reduction. For example, simplification of the result of our previous differentiation example:

simplify (0 * x ** 2 + a * (2 * x ** 1 * 1) + (0 * x + b * 1) + 0)

will result in:

a * (2 * x) + b

which is considerably shorter.


Symbolic expressions may not only be used for algebraic formulas, but also in other fields such as knowledge representations and natural language processing.


See also:

Language Processing

Knowledge Representations




3  Domain Orientation


3.1 What is a Domain?

The word 'domain' is often used with different meanings depending on the context. In our context, we will use the words the representation of a concept in the computer. Concepts are abstract notions of things in the real world or in the problem space. Because we want to model concepts in such a way that they can be understood by a computer, we need a method to represent those concepts in a program. For that purpose we will use domains. Domains are defined by domain definitions.

Before domains can be defined first the key concepts in the problem domain should be identified. To illustrate the steps one has to make in domain orientation we will develop a domain implementation for families. We know from daily experience that a family may consists of a father, a mother, and possibly a number of children. So, the key concepts for our mini-application are: father, mother, and children.

See also:

Domain Modeling


3.2 Domain Definitions

After the key concepts have been identified the corresponding domain definitions can be specified. In our example, this is very simple:

	Family = Father + Mother + Children

This is an example of one of the different forms a domain definition may take. In this domain definition, the domain of Family is defined by using three other domains: Father, Mother, and Children. Also these domains should be defined:

	Father = Person
	Mother = Person
	Children = { Person }

All these domains are based on another domain, called Person. At the last line the curly brackets may be read as "some number of".

The domain of a Person should also be defined. In daily life, persons are characterized by name, address, birthdate, and so on. In our example, we will take a simpler view:

	Person = text

It says that a Person domain is characterized by a piece of text. And, because text is a predefined domain, this is the end of the domain derivation sequence.

These five domain definitions will now be used in following steps.

Note: Domain definitions are not the same as Elisa definitions!
Domain definitions are meta-linguistic tools for modeling problem-space concepts.


See also:


Domain Definitions



3.3 Domain Operations

The next step is to specify domain operations for the domains found in the previous step. Domain operations are depending on the meaning of a domain, the meaning of its sub-domains and on the programs which will use these domains.

We will assume in our example that a family starts with no children. That means that a so-called constructor operation for a Family has the following form:

	Family (Father, Mother) -> Family;

This operation creates a new Family with a given Father and Mother. The new Family is returned by the operation.

As families are getting children, we will need an operation to add a child to a family:

	add_Child (Family, Child) -> nothing;

This operation will add a given Child to the Family. The operation will return nothing. As expected, the add_Child operation may be used several times for a given Family.

Let us assume that we are interested in the children of a family. In that case we need the following operation:

	Children (Family) -> multi (Child);

This operation is a multi-value operation. It returns all the Children of the Family.

To complete our list of operations, let us also assume that we are also interested in the father and mother of a family. This will require the following operations:

	Father (Family) -> Father;


	Mother (Family) -> Mother;

This concludes the set of operations needed for our mini-application.

See also:

Domain Operations


3.4 Domain Components

The following step is to implement the domain specifications as specified in previous steps. We will need the domain definitions as developed in the second step, as well as the domain operations as defined in the third step. The result is a domain component.

An implementation for a set of domain definitions and domain operations is based upon the application of design patterns. The application of a design pattern depends on the particular form of a domain definition and the sort of operation. A design pattern makes use of skeletons which prescribe the sequence of language constructs that should be used. These skeletons are defined later on in another document.

For our mini-application a very simple domain component is defined:

component Families;
   type Father = Person;
   type Mother = Person;
   type Child  = Person;
   type Family;
   Family (Father, Mother)   -> Family;
   Father (Family)           -> Father;
   Mother (Family)           -> Mother;
   Children (Family)         -> multi (Child);
   add_Child (Family, Child) -> nothing;
   Family (Father, Mother) = Family:[ Father; Mother; Children = alist (Child) ]; 
   Father (Family) = Family.Father;
   Mother (Family) = Family.Mother;
   Children (Family) = items (Family.Children);
   add_Child (Family, Child) = add (Family.Children, Child);
end component Families; 

This component is an implementation of the Family domain and its associated operations. A component consists of two parts. The first part is the interface-section, the second part is the implementation-section.

The interface-section contains type declarations and operation specifications. The type declarations are derived from the domain definitions. The operation specifications are based upon the domain operations.

The implementation-section contains definitions of the specified operations. The first definition defines the layout and contents of the Family-descriptor which is derived directly from the domain definition of Family. The other operations are using elements of the Family-descriptor. The operations are also using predefined operations for lists: alist which creates an empty list, items which returns all the items of a list, and add which adds a new element to a list.

See also:

Domain Implementations


3.5 Domain Testing

The testing of our mini-application is very simple. We need to define what a Person is, and we have to make clear that we want to use the component for Families. Both are done as follows:

use Families;
type Person = text;

Now we may test our mini system in a dialogue session. We start by defining a new family:

aFamily = Family ("John", "Alice");

Then we are asking the system, what is the new family:


The system will respond with:

Family:[ Father = "John";
         Mother = "Alice";
         Children = { }]

This answer illustrates a very important property of the system. The system knows how internal data should be represented externally. Programs written in other languages often have to use quite a number of output statements to show the internal data. In the Elisa system not only the values but also the structure of the internal data is provided automatically. This facilitates the understanding of the dynamic behavior of software components and it makes testing of programs much easier.

We now will add three children to the family:

add_Child (aFamily, "Albert");
add_Child (aFamily, "Marianne");
add_Child (aFamily, "Jane");

We may now again ask for the composition of the family:


The system will respond with:

Family:[ Father = "John";
         Mother = "Alice";
         Children = { "Albert",

Now we want to test another operation of the Families component. We like to known what the children are of the family:

Children (aFamily)?

The system responds with the following answers:


This illustrates another property of the system. If the evaluation of a query results in more than one answer those answers will be given one after one. In this example three answers are given

See also:


Case study: An Order Processing System

Case study: An Airport Support System

Domain Orientation versus Object Orientation




4  More about Elisa

In this section we will give an overview of other language elements found in Elisa. The language favors the functional approach as much as possible, because of its mathematical foundations, its pattern matching capabilities, and the succinct notations. However, lambda functions and currying of functions was not included because of conflicting requirements of procedural and object-oriented programming. For the same reason: referential transparency was not included in the language but can be obtained by the programmer by excluding the use of global assignments in the program as is discussed in Mutable and Immutable Objects

In some cases procedural programming offers a number of advantages. That means that definitions in Elisa may contain imperative steps. A procedure may have a number of steps of language elements, such as assignment statements, if-statements, loops and so on. Those language elements have been modified and extended to cope with multi-value expressions as explained in Statements and Special Expressions.

Object-oriented programming offers a number of important concepts, such as objects, classes, inheritance, encapsulation and polymorphism. In Elisa objects has been replaced by descriptors, classes are incorporated as types of objects, inheritance has been replaced by object composition and delegation, encapsulation is offered by the concept of software components, and polymorphism is faclitated by type variables. In addition, there is no preferential treatment of main objects.


Logic programming has also a number of important concepts, such as relations, backtracking, unification, multiple answers, reasoning. In Elisa, relations may be expressed by terms, backtracking is part of the execution model of multi-value expressions, unfication is limited to pattern matching, multiple answers are provided by multi-value expressions, and reasoning is limited to one-directional activation of definitions based on pattern matching. 


Elisa uses strong typing. Every entity in a program has a type. The type may be a simple type constant, such as integer, real, or boolean. It may also be a compound type such as array(integer), list(real), or list(array(integer)). In addition, there are also type variables to support polymorphism. Furthermore, dynamic typing is allowed by using terms. The system uses Type Propagation to derive the type of an entity. The different kinds of types and associated type expressions are described in the chapter about TypesCategories are described in a separate chapter.


There is much more information about Elisa. In the  Language Description section you find a description of all the language elements. For example, it contains much more about important concepts such as Definitions, Streams, Descriptors, Components, CollectionsGeneric Components, Terms. Furthermore there are chapters describing Higher-order Definitions, Built-in Definitions and External Interfaces. In addition there is an Index.


In the  Data Structures section you find a number of advanced programming techniques to demonstrate how Elisa can be applied to program familiar data structures, used for Lists, Trees, Graphs.  Interesting applications of symbolic expressions are described in Searching State Spaces, Language Processing, and Knowledge Representations.


In the Domain Modeling section you will find an outline of a domain-oriented development method, based on the concepts used in Elisa. It also contains two case studies: one about an Order processing system, the other about an Airport Support system; both written in Elisa.


In the Design Patterns section you will find an overview of well known design patterns.


If you want to write and test Elisa programs you may download Elisa's Development System. It is a compiler-based system for Windows computers. Follow the instructions of Getting Started with Elisa.



Back Home Up Next         Highlights of Elisa



Home | Highlights of Elisa | Integrating Different Paradigms | Getting Started with Elisa | Demo's  | What is Domain Orientation | Bibliography | Copyright | News | Contact | Contents

Language Description:

Lexical Elements | Basic Data Types and Expressions | Definitions | Streams | Backtracking | Statements and Special Expressions | Arrays | Lists | Descriptors | Components | Collections | Generic Components | Terms | Categories | Types | Built-in Definitions | Higher-order Definitions | External Interfaces | Index 

Data Structures: Sequences | Examples involving Lists | Trees | Graphs | Searching State Spaces | Language Processing | Knowledge Representations
Domain Modeling:

Domain Modeling | Concepts | Domain Definitions | Domain Operations | Domain Implementations | Systems | Case study: an Order processing system | Case study: an Airport Support system | Domain Orientation versus Object Orientation

Design Patterns:

Introduction | Abstract Factory | Builder | Factory Method | Prototype | Singleton | Adapter | Bridge | Composite | Decorator | Facade | Flyweight | Proxy | Chain of Responsibility | Command | Interpreter | Iterator | Mediator | Memento | Observer | State | Strategy | Template Method | Visitor 


click tracking


Send me your comments


This page was last modified on 18-02-2014 14:33:42   

free hit counter