Department of Computer Science

Evaluation Mechanism

There are three main strategies to evaluation that are embodied in existing languages. To understand what languages that use the functional evaluation model are like see my: Short Notes on Haskell and Functional Programming Languages, and to for an explanation of goal directed evauation see Short Notes on Prolog. Nearly all languages are procedural so most people will know what they are like already.

Procedural or State-Transition

This approach is modelled on the basic Von Neumann computer. Values are stored in pigeon holes "variables" and then statements are executed one after the other to alter the values stored in the variables. The whole method relies on the assignment statement and all the other statements just serve to sequence executions of assignments. Most languages use this approach: Ada, Cobol, Basic, assembler languages, Modula-2, C, Smalltalk-80, C++, Occam, Eiffel, Java, Delphi etc. Storage variables should be considered under the heading of evaluation mechanism because they are unique to procedural language. This brings in such issues as lifetime (ie. the allocation and addressing of storage). It also means there is a connection with issues to do with data types as storage depends on type. The main choices about the form of procedural evaluation are whether the language permits parallel evaluation or not, the choice of control statement and what sort of exception mechanism it might have.

Functional or Applicative

Here the required result is expressed as some function or expression in terms of input data, and the language evaluates the expression to produce the result. This can also be thought of as rewriting: functions are expressed as simple rules replacing the application of a name to a particular pattern of argument with another expression. This expression rewriting continues until only built-in operators are left which are then applied leaving a result. In such languages there are no stored variables, no assignment, no statements and no sequence of execution. Examples are: Miranda, SML, Hope and Haskell. The main choice in evaluation of expressions for such languages concerns the order of rewriting: left-most outer or left-most inner giving so-called lazy or eager evaluation.

Goal Achievment with Unification

Languages using such a mechanism are sometimes called "logical" or "relational". They express relationships between data values using predicates. The computation is an attempt to satisfy a goal (ie. see if it is provable). The satisfaction of the goal can result in binding constant data values to variables by unification, this is how "results" are produced. In addition some predicates are special and can do I/O or expression evaluation. There is only one language in this class and that is Prolog.

Comparison

What or How

The two non-procedural models are called declarative whereas the procedural model is imperative. This means that in Prolog and the functional languages the programmer says what they want done, not how to do it, whereas in procedural languages it is nearly all how.

For example in simple expressions like a * a + b * b the rules require that however it is done the multiplications should be done before the addition but it is left to the implementation to decide whether to do a * a before b * b or both at once. The only language that forces a programmer to say how to do this would be assembler where one has to have instructions to load registers, do multiplication etc. However with imperative languages, for everything except expressions, the programmer must write down the steps, in order, directing how the computation should be down. With declarative languages most of a program just says what, not how,

Referential transparency

means that the value an expression refers to depends simply (transparently) only upon the expression and the values in it. This means that the value of a function will always be the same with the same arguments. This might appear obvious but it is not the case in any procedural language where the use of changeable variables as globals, or in objects means that the value of any procedure depends on the arguments, the code AND the complete history of execution of the whole program. So to understand the value of one expression it might be necessary to dry run the program to see what variables will be changed before one can understand the value any expression refers to.

This means that understanding and debugging procedural programs is infinitely more complicated than debugging functional programs.

Secondly. in functional languages, because the value of an expression does not depend on when it is evaluated compilers can choose to evaluate sub-expressions in parallel or sequentially without changing the meaning of a program. Whereas trying to make procedural programs run in parallel requires explicit processes or threads and control of interactions.

Efficiency

Because procedural languages reflect the underlying machine they are much easier to compile and usually execute a lot faster than some functional language programs.

needing to model state transitions

Over the years most programmers have got used to thinking procedurally, step by step. This means that they naturally think of a large class of problem solutions this way; as a step by step alteration of state. It is hard to think of operating system file stores, program I/O, traffic light control programs etc. without thinking in terms of state changes. Unfortunately it is harder to model state changes in functional programs and so it is more tempting to stay with procedural languages.

Page generated: 2002-11-04 by Bob Dickerson

© University of Hertfordshire Higher Education Corporation (1998)

Disclaimer