In this lecture we first introduce the main programming paradigms.
Next we introduce the functional programming paradigm using the
programming language Scheme. In this lecture We cover expressions, types, lists, definitions, and
the basic function concept. A number of examples
are given, when possible from the web domain.
The introduction to the paradigm and Scheme is continued in the next
lecture which covers name binding, recursion and iteration.
Exercise 2.2. Getting started with Scheme and LAML
The purpose of this exercises is learn the most important practical details of using a Scheme system on Unix.
In case you insist to use Windows we will assume that you install the necessary software in your spare time.
There is no time available to do that during the course exercises. Further details on installation of Scheme and LAML on Windows.
You will have to choose between DrScheme and MzScheme.
DrScheme is a user friendly environment for creating
and running Scheme programs, with lots of menus and lots of help. However, it is somewhat awkward to use DrScheme
with LAML. Only use DrScheme in this course if you cannot use Emacs, or if you are afraid of textually, command based tools.
Follow this link for further details.
MzScheme is the underlying engine of DrScheme. MzScheme is a simple read-eval-print loop, which let you enter an expression,
evaluate and print the result. MzScheme is not very good for debugging and error tracing.
MzScheme works well together with Emacs, and there is a nice connection between MzScheme
and LAML. MzScheme used with Emacs is preferred on this course. Please go through the following steps:
Insert the following line in your .emacs file in your home dir, and then restart Emacs:
Have a session with a naked Scheme system by issuing the following command in Emacs: M-x run-scheme-interactively
Define a couple of simple functions ( odd and even, for instance) and call them.
Split the window in two parts with C-x 2 and make a buffer in the topmost one named sources.scm ( C-x b ).
Bring the Scheme interpreter started above into the lower part of the window. The buffer with the Scheme process
is called *inferior-lisp*.
Put the sources.scm buffer in Scheme mode ( M-x scheme-mode ). Define the functions odd and even in the buffer and use the Scheme
menu (or the keyboard shortcuts) to define them in the running Scheme process.
Have a similar session with a Scheme+LAML system by issuing the following command in Emacs: M-x run-laml-interactively (You may have to confirm that a previously started Scheme process is allowed to be killed).
All you did in item 2 can also be done here.
Evaluate a simple HTML expression, such as
(html (head (title "A title")) (body (p "A body")))
Use the function xml-render to make a textual rendering of the HTML expression.
Make a deliberate grammatical error in the LAML expression and find out what happens.
Make a file 'try.laml'.
Control that Emacs brings the buffer in Laml mode.
Issue a M-x laml-mode explicitly, if necessary.
Use the menu 'Laml > Insert LAML template' to insert an XHTML template.
Fill in some details in the head and body.
Process the file via the LAML menu in Emacs: Process asynchronously. The file try.html will be defined.
Play with simple changes to the HTML expression, and re-process. You can just hit C-o on the keyboard for processing.
We will now describe and characterize the important concepts of expressions, values and types.
Evaluation of an expression yields a value which belongs to a type
Written by the programmer
Will typically involve one or more function calls
A Function - as written by the programmer - is itself an expression
Primitive as well as composite
A function expression is evaluated to a function object
A set of values with common properties
Type checking can be used to validate a program for certain errors before it is executed
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.
(lambda (x) (+ x 1)) has the value 'the function that adds one to its parameter'
HTML mirror expressions
(p "A body paragraph"))
The value of this expression can be rendered as a string in HTML which can be presented in an Internet browser.
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.
This material includes a lecture that explains the important and relevant details about LAML.
Not least, this lecture explains the calling conventions of the so-called HTML mirror functions.
Here we will emphasize the rules of evaluating a form like (a b c d e) in Scheme
How is the form (a b c d e) evaluated in Scheme?
The form (a b c d e) appears as a pair of parentheses with a number of
entities inside. The question is how the parenthesized expression is evaluated, and which constraints apply to the evaluation.
The evaluation of the empty pair of parentheses ( ) is in principle an error
If a is the name of a special form, such as lambda, if, cond, or define special rules apply
In all other cases:
Evaluate all subforms uniformly and recursively.
The value of the first constituent amust be a function object. The function object is called with the values of b, c, d, and e as actual parameters.
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.
On this page we will discuss equality functions in Scheme
As most other programming languages, Scheme supports a number of different equivalence predicates
The most discriminating
The least discriminating - structural equivalence
Exact numerical equality
eqv? is close to eq?
string=? is structural equivalence on strings
Program: A sample interaction using and demonstrating the equivalence functions in Scheme.
1> (eq? (list 'a 'b) (list 'a 'b))
2> (eqv? (list 'a 'b) (list 'a 'b))
3> (equal? (list 'a 'b) (list 'a 'b))
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")
6> (equal? "abe" "abe")
7> (eq? "abe" "abe")
8> (eqv? "abe" "abe")
Types plays an essential role in any programming language and any programming paradigm.
In many languages types are used in the program text as constraints on variables and parameters.
C, Pascal, and Java are such languages.
In others, the types are inferred (somehow extracted from use of variables, parameters etc. relative
to the ways the variables and parameters are used in operators and functions). ML is such a language.
Yet in other languages, types are solely used to classify the values (data objects) at run time.
Scheme is such a language. Thus, in Scheme we do not encounter types in the source program, but
only at run time.
The notion of type is used to make programs more readable, make them run more efficient, and
to detect certain errors before they cause errors in the calculation.
Explicitly typed variables, parameters and function
serve as important documentation, which enhances the program understanding.
Knowledge of the properties of data makes it possible to generate more efficient code
Explicit information about types in a program is a kind of redundancy against which it is
possible to check expressions and values
Programmers usually wish to identify type errors as early as possible in the development process
As already mentioned the use of types in source programs makes it possible
to deal with program correctness - at least in some simple sense.
In this context, correctness is not relative to the overall intention or specification
of the program. Rather, it is in relation to the legal use of values as input to
operators and functions.
Type checking is the processes of identifying errors in a program based on explicitly or implicitly stated type information
Type errors can lead to erroneous calculations
Type errors cannot cause erroneous calculations
The type check is done at compile time or run time
The types of all expressions are determined before the program is executed
The type check is typically carried out in an early phase of the compilation
Comes in two flavors: explicit type decoration and implicit type inference
Static typing implies strong typing
According to section 1.1 the Scheme Report (R5RS)
'Scheme has latent as opposed to manifest types.
Types are associated with values (also called objects) rather than with variables.'
In our categorization, Scheme is strongly typed and types are dealt with at run time (on values) as a contrast to
compile time (on variables).
Is the expression (+ 1 (if (even? x) 5 "five")) correct with respect to types?
The example shows an arithmetic expression that will cause a type error with most type checkers.
However, if x is even the sum can be evaluated to 6. If x is odd, we encounter a type error because we cannot
add the integer 1 to the string "five".
It is not realized that the expression (+ 1 "five") is illegal.
We can imagine that it returns the erroneous value 47
If, for instance, x is 2, the expression (+ 1 (if (even? x) 5 "five")) is OK, and has the value 6
If x is odd, it is necessary to identify this as a problem which must be reported
before an evaluation of the expression is attempted
(+ 1 (if (even x) 5 "five")) fails to pass the type check, because the type of the expression cannot be statically determined
A list is recursively composed of a head and a tail, which is a (possibly empty) list itself
The building blocks of lists are the cons cells
Every such cell is allocated by an activation of the cons function
An illustration list construction and list selection. We first construct
a list (d c b a) and we bind it to the variable lst. Next we select the first
element, the tail of lst, the second element, and the second tail of lst.
Construction of the list structure which we here call x
(car x) => e
(cdr x) => f
The constructor function cons takes an element e and a list f and constructs a new list. As illustrated above
cons makes exactly one new cons cell, and no kind of list copying is involved at all.
The selector car returns the first element of the list. A better name of car would be head .
The selector cdr returns the list consisting of all but the first element in the list. A better name of cdr would be tail .
A proper list is always terminated by the empty list
In Scheme the empty list is denoted '(). When we in this context talk about the termination of the list we mean
the value we get by following the cdr references to the end of the list structure.
The cons function is suitable for definition of binary trees with 'data' in the leaves
Figure. A symbolic expression which illustrates the most general form it can take - a binary tree
Figure. The same symbolic expression laid out as a list. The expressions is a proper list if and only if h is the empty list.
If h is not the empty list, the symbolic expression is an improper list.
Exercise 2.3. Construction of symbolic expressions
Construct the symbolic expressions illustrated on this page via the cons primitive in Scheme.
The entities named a through h should be symbols. As a help, the rightmost part of the structure is made by (cons 'g 'h).
'g is equivalent to (quote g), meaning that g is not evaluated, but taken for face value.
Experiment with h being the empty list. Try to use a proper list function, such as length, on your structures.
cons is the basic list constructor function - but it can be applied through a number
of other means as well
List and S-expression construction:
Deep cons expressions
Using the list function
Using quote or quasiquote also known as backquote
Table. Examples of list construction by use of cons , list and quoted list expressions.
(cons 1 (cons 2 (cons (+ 1 2) '())))
(1 2 3)
(list 1 2 (+ 1 2))
(1 2 3)
(quote (1 2 (+ 1 2)))
(1 2 (+ 1 2))
'(1 2 (+ 1 2))
(1 2 (+ 1 2))
(quasiquote (1 2 (unquote (+ 1 2))))
(1 2 3)
`(1 2 ,(+ 1 2))
(1 2 3)
Exercise 2.4. Every second element of a list
Write a function, every-second-element, that returns every second element of a list. As examples
(every-second-element '(a b c)) => (a c)
(every-second-element '(a b c d)) => (a c)
It is recommended that you formulate a recursive solution. Be sure to consider the
basis case(s) carefully.
It is often worthwhile to go for a more general solution than actually needed.
Sometimes, in fact, the general solution is simpler than one of the more specialized solutions.
Discuss possible generalizations of every-second-element, and implement the one you find most appropriate.
There exists a number of important List functions in Scheme, and we often write other such functions ourselves
We will here take a look at some of the most important list functions, as defined by the language itself.
You are encouraged to read about them in the Scheme Report, to which we make a reference below.
(null? lst) A predicate that returns whether lst is empty
(list? lst) A predicate that returns whether lst is a proper list
(length lst) Returns the number of elements in the proper list lst
(append lst1 lst2) Concatenates the elements of two or more lists
(reverse lst) Returns the elements in lst in reverse order
(list-ref lst k) Accesses element number k of the list lst
(list-tail lst k) Returns the k'th tail of the list lst
It should be noticed that the first element is designated as element number 0. Thus (list-ref '(a b c) 1) returns b
Association lists are used in the same way as associative arrays
Table. Examples of association lists. The function assq uses eq? to compare the first parameter
with the first element - the key element - in the pairs. As an alternative, we could use
the function assoc, which uses equal? for comparison. A better and more general solution would be
to pass the comparison function as parameter. Notice in this context, that both assq and assoc are 'traditional Lisp functions' and part of Scheme, as defined in the language report.
Program: A simple LAML document with emphasis on the attributes, represented as property lists.
There are four attribute lists (property lists, each with its own color). Notice
the CSS attribute css:text-decoration, given inline in the document .
(load (string-append laml-dir "laml.scm"))
(html 'xmlns "http://www.w3.org/1999/xhtml"
(meta 'http-equiv "Content-Type"
'content "text/html; charset=iso-8859-1")
(title "Attribute Demo"))
(body 'id "KN" 'class "generic"
(p "Here comes a camouflaged link:")
(p (a 'href "http://www.cs.auc.dk" 'css:text-decoration "none"
'target "main" "Link to the CS Department"))
(p "End of document."))))
In the LAML general library there are functions ( alist-to-propertylist and propertylist-to-alist ) that convert between association lists and
It is natural to represent tables as lists of rows, and to represent a row as a list
Tables play an important roles in many web documents
LAML has a strong support of tables
Table. Examples of table transposing, row elimination, and column elimination. We will program and
illustrate these functions in a later exercise of this material. The function show-table is similar to table-0 from a LAML convenience library.
Using higher-order functions it is rather easy to program the show-table function. We will come back to this
later in these notes.
Vectors in Scheme are heterogeneous array-like data structures of a fixed size
Vectors are denoted in a similar way as list
Example: #(0 a (1 2 3))
Vectors must be quoted in the same way as list when their external representations are used directly
The function vector is similar to the function list
There are functions that convert a vector to a list and vice versa
The main difference between lists and vectors is the mode of access and the mode of construction
There is direct access to the elements of a vector. List elements are accessed by traversing a chain of references.
This reflects the basic differences between arrays and linked lists.
The mode of construction for list is recursive, using the cons function. Lists are created incrementally:
New elements can be created when needed, and prepended to the list.
Vectors are allocated in one chunck, and cannot be enlarged or decreased incrementally.
The conceptual starting point is the well-known mathematical concept of functions
The notational starting point is lambda calculus
The mathematical function concept
A mapping from a domain to a range
A function transfers values from the domain to values in the range
A value in the domain has at most a single corresponding value in the range
Totally or partially defined functions
Extensionally or intensionally defined functions
A very terse notation of functions and function application
An extensionally defined function is defined by a set of pairs, enumerating corresponding
elements in the domain and range. Notice that this causes practical problems if there
are many different values in the domain of the function. An intensionally defined
function is based on an algorithm that describes how to bring a value from the domain
to the similar value in the range. This is a much more effective technique to
definition of most the functions, we program in the functional paradigm.
We will here introduce the notation of the lambda calculus, mainly in order to understand
the inspiration which led to the concept of lambda expressions in Lisp and Scheme.
Lambda calculus is a more dense notation than the similar Scheme notation
Table. A comparison of the notations of abstraction and combination (application) in the lambda calculus and Lisp.
In some variants of lambda calculus there are more parentheses than shown here: (λ v . E). However, mathematicians tend to like ultra brief notation, and they often eliminate the parentheses.
This stands as a contrast to Lisp and Scheme programmers.
Functions are represented as lambda expressions in a source program
At run time, functions are represented as first class function objects
Program: A sample read-eval-print session with lambda expressions and function objects. In a context where we define x to the number 6 we first evaluate a lambda expression.
Scheme acknowledges this by returning the function object, which prints like ' #<procedure> '. As
a contrast to numbers, lists, and other simple values, there is
no good surface representation of function values (function objects). Next we bind the name inc
to the same function object. More about name binding in a later part of this material. The expression (if (even? x) inc fac)
returns inc because the value of x is 6, and as such it is even. Therefore the value of ((if (even? x) inc fac) 5)
is the same as the value of (inc 5), namely 6.
The concept function object: A function object represents a function at run time. A function object is created as the value of a lambda expression
A function object is a first class value at run time, in the same way as numbers, lists and other data are values. This is different from
more traditional programming languages, where procedural and functional abstractions have another status than ordinary data.
The concept closure: A function object is also known as a closure.
The name 'closure' is related to the interpretation of free names in the body expression of the function.
Free names are used, but not defined in the body. In a function object (or closure) the free names are bound
in the context of the lambda expression. This is a contrast to the case where the free names are bound in
the context of the application of the function.
Characteristics of function objects:
First class objects
Does not necessarily have a name
A function object can be bound to a name in a definition
Functions as closures:
Capturing of free names in the context of the lambda expression
Static binding of free names
A closure is represented as a pair of function syntax and values of free names
A function object can be
applied on actual parameters,
passed as a parameter to a function,
returned as the result from another function, and
organized as a constituent of a data structure
The concept first class citizen: A first class citizen is an entity which can be passed as parameter to functions, returned as a result from a function, and
organized as parts of data structures
Program: A few interactions which illustrate the first class properties of function objects.
We bind the variable toplevel-html-elements to the list of the two functions html and frameset. Both
are HTML mirror functions defined in the LAML general library. We illustrate next that the value of the variable indeed is a list of two
functions. Thus, we have seen that we can organized functions as elements in lists.
The function cadr returns the second element of a list. It is equivalent to (compose car cdr), where compose is functional composition. In the third evaluation we apply the mirror function frameset on
a single frame. The last interaction shows the HTML rendering of the this. xml-render is a function defined in the LAML general library.
A function object does not have a name, and
a function object is not necessarily bound to a name
Program: An illustration of anonymous functions. The function (lambda(x) (+ x 1)) is the function that adds one (to its parameter).
It is organized in a list side by side with the function that multiplies by five. Notice in this context that none of these
two functions are named. In the last interaction we apply the latter to the number 6.
1> ((lambda(x) (+ x 1)) 3)
2> (define fu-lst
(list (lambda (x) (+ x 1)) (lambda (x) (* x 5))))
4> ((second fu-lst) 6)
It is often useful to pass one or more optional parameters to a function
In case an optional parameter is not passed explicitly, a default value should apply
Program: A example of a function f that accepts optional-parameters. Besides the required parameter rp, the function accepts an arbitrary number of additional parameters,
the list of which are bound to the formal parameter optional-parameter-list. The function optional-parameter
from the LAML general library accesses information from optional-parameter-list. In case an optional parameter
is not passed, the default value (the last parameter of optional-parameter) applies.
The function optional-parameter is a LAML function from the general library
The optional parameter idea works well if there is a natural ordering of the relevance of the parameters
If parameter n is passed, it is also natural to pass parameter 1 to n-1
The idea does not work well if we need to pass optional parameter number n, but not number 1 .. n-1
Keyword parameters is a good alternative to optional parameter lists in case many, 'unordered' parameters need to passed to a function
We have demonstrated how we simulate optional parameter via the 'rest parameter list' mechanism in Scheme.
It is also possible to simulate a keyword parameter mechanism. In a LAML context, this is done
with respect to the passing of attributes to the HTML mirror functions.
A function object can be bound to a name via define like any other kind of value.
But we often use a slightly different, equivalent syntax for function definitions, where the 'lambda' is implicitly specified
Syntax: The ordinary way to bind f to the value of a lambda expressions
(define f (lambda (p1 p2) ...))
Syntax: An equivalent syntactic sugaring with a more shallow parenthesis structure.
Whenever Scheme identifies a list at the 'name place' in a define form, it carries out the transformation
(define (f p1 p2) ...) => (define f (lambda (p1 p2) ...)) . Some Scheme programmers like the form (define (f p1 p2) ...) because the calling form (f p1 p2) is a constituent of the
form (define (f p1 p2) ...)
We will here give a simple example of a web-related function.
Much more interesting examples will appear later in the material.
Program: The definition of a www-document function. The www-document function is useful if you want to abstract the HTML envelope formed by
the elements html, head, title, and body. If you need to pass attributes to html or body the proposed function is not adequate.
Program: A sample application of the function www-document. Notice the way we pass a number of body contributions, which - as a list - are bound to the formal parameter body-forms.
"This is the document title"
(h1 "Document title")
(p "Here is the first paragraph of the document")
(p "The second paragraph has an" (em "emphasized item")
"and a" (em "bold face item")_"."))
Program: The whole story - including the LAML context.
(load (string-append laml-dir "laml.scm"))
(define (www-document the-title . body-forms)
(head (title the-title))
"This is the document title"
(h1 "Document title")
(p "Here is the first paragraph of the document")
(p "The second paragraph has an" (em "emphasized item")
"and a" (em "bold face item")_"."))
Program: The definition of the indent-pixel function. This is a function which we use in many web documents to indent
the contents a number of pixels relative to its context.
Here we implement
the indentation by use of a table, in which the first column cell
is empty. As we will se, other possibilities exist.
Program: An alternative version of theindent-pixel function. This version uses Cascading Style Sheets expressiveness. As it appears,
this is a more compact, and more direct way of achieving our indentation goal.
Program: A sample application of indent-pixel with some initial LAML context (software loading). Notice the use of the XHTML mirror.
In HTML we define colors as text strings of length 7:
The symbols r, s, t, u, v, and w are all hexadecimal numbers
between 0 and f (15). rs is in that way the hexadecimal representation
for red, tu is the code for green, and vw is the code for blue.
As an example, the text string
represents white and
In Scheme we wish to represent a color as the list
(color r g b)
where color is a symbol, r is number between 0 and 255 which represents the amount of red,
and g and b in a similar way the amount of green and blue in the color.
Write a Scheme function that transforms a Scheme color to a HTML color string.
It is a good training to program the function that converts decimal numbers to hexa decimal numbers.
I suggest that you do that - I did it in fact in my solution! If you want to make life a little easier,
the Scheme function (number->string n radix) is helpful (pass radix 16 as second parameter).
Exercise 2.9. Letter case conversion
In many web documents it is desirable to control the letter case of selected words.
This allows us to present documents with consistent appearances.
Therefore it is helpful to be able to capitalize a string, to transform a string
to consist of upper case letters only, and to lower case letters only. Be sure
to leave non-alphabetic characters untouched. Also, be sure to handle
the Danish characters 'æ', 'ø', and 'å' (ASCII 230, 248, and 229 respectively). In addition, let us emphasize that
we want functions that do not mutate the input string by any means. (It means that
you are not allowed to modify the strings passed as input to your functions).
Write functions capitalize-a-string, upcase-a-string, downcase-a-string for these purposes.
As examples of their use, please study the following:
(capitalize-a-string "monkey") => "Monkey"
(upcase-a-string "monkey") => "MONKEY"
(downcase-a-string "MONkey") => "monkey"
Hint: I suggest that you program the necessary functions yourself.
Convert the string to a list of ASCII codes, do the necessary transformations on this list,
and convert the list of modified ASCII codes back to a string. The Scheme functions list->string and string->list are useful.
Hint: If you want to make life a little easier (and learn less from this exercise...) you can
use the Scheme functions char-upcase and char-downcase, which work on characters. But
these functions do maybe not work on the Danish letters, so you you probably need some patches.