To begin with, I did not know how Scheme works. How it reads a computer program to make a response. This is actually really simple.
The big idea is the evaluator, which is a computer program itself that determines the meaning of expressions in a programming language. And we say, a computer program is simply a sequence of expressions, whereas, computer programming is simply the act of writing these expressions. There you go.
I will use Guile as the Scheme implementation and its evaluator to determine the meaning of expressions. The meaning can be simple or complex, depending on the nature of the language.
Suppose you think of a random number and write it as an expression in Guile:
> 37
$1 = 37The result stored in $1 is the very same number 37 as in the expression, and we say that numbers are self-evaluating expressions. Numbers are not unique in that sense, as functions in Scheme self-evaluate as well.
One example of a function is addition. The Scheme standards define the + operator to compute addition. Knowing that functions are self-evaluating, you may expect that writing + as an expression returns the very same function:
> +
$2 = #<procedure + (#:optional _ _ . _)>In Scheme, functions are named procedures, as not all functions will be compliant to the mathematical definition of a function. The way the return value is printed is specific to Guile. Here it says that the return value is a procedure named + that accepts an arbitrary number of optional arguments. Note the three underscores _ which represent arguments. The dot . inbetween means that + sums an arbitrary number of numbers.
You call Scheme procedures, like +, by writing them as the first element inside parentheses and by adding arguments as other elements, separated by whitespace.
> (+)
$3 = 0
> (+ 1)
$4 = 1
> (+ 1 2)
$5 = 3
> (+ 1 2 3 4 5)
$6 = 15We call this parenthesized prefix notation. Clearly, parenthesized because you write ( and ) a lot. Prefix because the operator is always the first element within the parentheses.
Let us see in more detail how these expressions look like.
A Lisp/Scheme expression is either an identifier or a parenthesized sequence of expressions. We call them symbolic expressions, s-expressions, s-exp, or simply sexp. An s-expression is one of the following:
Note that the definition of an s-expression is a recursive definition, as an s-exp can be a sequence of s-exp’s itself.
Many also differentiate between primitive and derived expressions. Primitive expressions are procedure calls, variables, lambda, if, set!, and literal expressions. Derived expressions can be defined as macros and are in general built upon primitive expressions. You will learn what each of these terms means later.
Here are three examples of s-expressions:
37
(define x 37)
xThe first expression is a number. The second is a compound expression. The third is an identifier.
In Scheme, an identifier is any word made out of an alphabet of letters. The alphabet depends on the version of the Scheme standard and on the implementation. The alphabet in r5rs consists of letters from A to z, numbers, and special characters not limited to ~!@#$%^&*()_+{}|<>? . The r6rs and r7rs standards provide Unicode support. Guile supports UTF-8 for identifiers.
The process of evaluating an expression is a procedure itself and the name of this procedure is eval. Guile implements primitive-eval that accepts only one argument – the expression.
> primitive-eval
#1 = #<procedure primitive-eval (exp)>Note that the Scheme standards define a different kind of eval, one that takes the additional argument of the environment, but I will discuss environments in later chapters.
> (primitive-eval 37)
$2 = 37
> (define x 37)
> (primitive-eval x)
$3 = 37However, eval does not allow definitions:
> (primitive-eval (define x 37))
While compiling expression:
Syntax error:
unknown file:4:16: definition in expression context, where definitions are not allowed, in form (define x 37)I mentioned that s-expressions can contain themself. We call such expressions as compound expressions. The following text shows their evaluation.
A compound expression is an expression that contains other expressions.
Suppose the compound expression is:
(<exp-1> (* 50 12) (1 is not an operator)) There are at least two approaches for evaluating this. Scheme may evaluate a compound expression by applicative order evaluation or normal order evaluation. The word order here does not describe the order in which the expressions are evaluated, but rather describes the evaluation strategy.
Note that for a compound expression you do not know in which order the expressions are evaluated. The evaluation order may be left-to-right, right-to-left, or completely random, as decided by the Scheme implementation. The standard does not force left-to-right (or any other) evaluation order.
Applicative order is when the evaluator evaluates each expression in a compound expression.
For example, the expression:
(<exp-1> (* 50 12) (1 is not an operator))returns an error as (1 is not an operator) begins with a number, which is illegal, as the first element within the parentheses must be a procedure.
Do not confuse normal for normality as an adjective. The normal is for historical reasons, as it referes to the concept of a reduction to normal form. In any case, normal order is when the evaluator does not necessarily evaluate each expression in a compound expression.
For example, the expression:
(<exp-1> (* 50 12) (1 is not an operator))may not result in an error in some cases. This is because in normal order, the expression (1 is not an operator) may not be needed and, thus, never evaluated.
Programming is simply the act of writing expressions. Running a program means evaluating expressions. Most Scheme expressions are evaluated in applicative order. Normal order evaluation is rare. Suppose you write one expression and evaluate it. In Scheme, evaluation has two kinds of results:
You can print the value of the evaluated expression, ignore the side-effects and continue writing expressions. This is called a read-evaluate-print loop, or better known as REPL.
Here are the REPL steps:
The guile executable is a REPL. It reads one expression, evaluates, prints a value, and loops back to reading expressions.