The notion of expression is of central importance in the functional programming paradigm. In some sense, expressions is the only computational building block of the functional programming paradigm. As a contrast, the imperative paradigm makes use of both commands and expressions. In the imperative paradigm commands are executed with the purpose of modifying the state of the program, as it is being executed. Expressions are executed - or evaluated - with the purpose of producing a value. Values of expressions can be used as parts of surrounding expressions, in an evaluation process. Ultimately, the value of an expression is presented to the person who runs a functional program. The value serves as the 'result' of the computation.

4.1.  Expressions, values, and types
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The relationship between the three key concepts is as stated below.

In the itemized list below we will describe the most important properties of expressions, values, and types. The coverage given here is only a brief appetizer. We have much more to say about all three of them later in the material.

Expressions are part of the source program, as written by the programmer.

A function expression is called a lambda expression. We will encounter these important expressions later in this material.

The primitive values are those which cannot be decomposed into more primitive parts. Some of the important primitive values are numbers, the two boolean values (true and false), and the characters of some character set. Primitive values stand as a contrast to composite values, such as lists and arrays, which are aggregations of parts, each of which are compositive or primitive values themselves.

4.2.  Examples of expressions and their values
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Before we go into additional details, we will give examples of important kinds of expressions. This includes simple expressions, such as the well-known arithmetic expressions. Next we give an example of a conditional expression, which somehow corresponds to selective control structures in the imperative paradigm. Lambda expressions generate functions, and as such they are of primary importance for the functional programming paradigm. Finally, HTML expressions are of interest to the approach taken in the running example used in this material - an example from the domain of web program development. Wherever possible we wish to illustrate the use of functional programming in the web domain. In this domain, expressions that involve mirrors of HTML and XML elements are the key constituents.

The conditional expression is evaluated in two steps. First the boolean expression (even? x) is evaluated. If x is even, the boolean expression (even? x) evaluates to true and the trivial expression 7 is evaluated. Because x is 3 and therefore odd, the other expression (+ x 5) is evaluated, giving us the final value 8. It is important to realize that an if form does not evaluate all three constituent expressions at the outset. It first evaluates the boolean expression, and based on the outcome, it either evaluates the 'then part' or the 'else part'. Not both! We have much more to say about the order of evaluation of an if form in a later part of this material

Regarding the lambda expression, the x in parentheses after lambda is the formal parameter of the function. the expression (+ x 1) is the body. In functions, the body is an expression - not a command.

The HTML mirror expressions stem from the LAML libraries.

The functions html, body, title, head, and p correspond to the HTML elements of the same names. In the LAML software, the HTML elements are mirrored as functions in Scheme.

The evaluation order of the constituents in a conditional expression is discussed in details in Section 20.10. Conditional expression is a theme we will study in much more detail in Chapter 10. HTML mirror expressions are discussed in additional details in Chapter 27.

4.3.  Evaluation of parenthesized expressions
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Parentheses in Scheme are used to denote lists. Program pieces - expressions - are represented as lists. Evaluation of parenthesized expressions in Scheme follows some simple rules, which we discuss below.

The evaluation of the empty pair of parentheses ( ) is often - in concrete Scheme systems - considered as the same as '( ), which returns the empty list. However, you should always quote the empty pair of parentheses to denote the empty list.

Having reached the case where a function is called on some given data, which are passed as parameters, like in the call (a b c d), the next natural question is how to call a function. We will explore this in detail in Chapter 20, more specifically, Section 20.3where we see that the call should be replaced by the body of the called function, in which the formal parameters should be replaced by the actual parameters.

4.4.  Arithmetic expressions
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

It is natural to start our more detailed study of expressions by reviewing the well-known arithmetic expressions. The important thing to notice is the use of fully parenthesized prefix notation.

Prefix notation is defined in the following way:

Below we give examples of evaluation of a number of different arithmetic expressions. Notice in particular the support of rational numbers in Scheme, and the possibility to use arbitrarily large numbers.

(+ 4 (* 5 6))

34

(define x 6)
(+ (* 5 x x) (* 4 x) 3)

207

(/ 21 5)

21/5

(/ 21.0 5)

4.2

(define (fak n)
  (if (= n 0) 1 (* n (fak (- n 1)))))

(fak 50)

30414093201713378043612608166064768
844377641568960512000000000000

The observation about priorities of operators stands as a contrast to most other languages. In Lisp and Scheme, the use of parentheses makes the programmer's structural intentions explicit. There is no need for special rules for solving the parsing problem of arithmetic expressions. Thus, 1+2*3 is written (+ 1 (* 2 3)), and it is therefore clear that we want to multiply before the addition is carried out.

4.5.  Equality in Scheme
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Equality is relevant and important in most programming paradigms and in most programming languages. Interestingly, equality distinctions are not that central in the functional programming paradigm. Two objects o1 and o2 which are equal in a weak sense (structurally equal) cannot really be distinguished in the functional paradigm. One of them can be substituted by the other without causing any difference or harm.

When we encounter imperative aspects of the Scheme language, the different notions of equality becomes more important. In the imperative programming paradigm we may mutate existing objects. By changing one of the two structurally equal objects, o1 and o2, it is revealed if o1 and o2 are also equal in a stronger sense. If the mutation of o1 also affects o2 we can conclude that o1 and o2 are identical (eq? o1 o2). If a mutation of o1 does not affect o2, then (not (eq? o1 o2)).

In Scheme we have the following important equivalence predicates:

An equivalence predicate divides a number of objects into equivalence classes (disjoint subsets). The objects in a certain class are all equal. The most discriminating equivalence predicate is the one forming most equivalence classes.

To stay concrete, we show a number some examples of equality expressions in a dialogue with a Scheme system. You should consider to try out other examples yourself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1> (eq? (list 'a 'b) (list 'a 'b))
#f

2> (eqv? (list 'a 'b) (list 'a 'b))
#f

3> (equal? (list 'a 'b) (list 'a 'b))
#t

4> (= (list 'a 'b) (list 'a 'b))
=: expects type <number> as 2nd argument, given: (a b); other arguments were: (a b)

5> (string=? "abe" "abe")
#t

6> (equal? "abe" "abe")
#t

7> (eq? "abe" "abe")
#f

8> (eqv? "abe" "abe")
#f

4.6.  The read-eval-print loop
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

It is possible to interact directly with the Scheme interpreter. At a fine grained level, expressions are read and evaluated, and the resulting value is printed. This is a contrast to many other language processors, which require much more composite and coarse grained fragments for processing purposes.

The tool which let us interact with the Scheme interpreter is called a 'read-eval-print loop', sometimes referred to via the abbreviation 'REPL'.

We show the interaction with a Scheme REPL below. The interaction is quite similar to the exposition in Table 4.1. In this as well as in future presentations of REPL interaction, we often put a number in front of the prompt. This simple convenience to allow us to refer to a single interaction in our discussions.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1> (+ 4 (* 5 6))
34

2> (define x 6)

3> (+ (* 5 x x) (* 4 x) 3)
207

4> (/ 21 5)
21/5

5> (/ 21.0 5)
4.2

6> (define (fak n) (if (= n 0) 1 (* n (fak (- n 1)))))

7> (fak 50)
30414093201713378043612608166064768844377641568960512000000000000