Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'Expressions, Types, and Functions
8.  Functions

We have now reached the most central concept in this material, namely functions. Functions play a key role in the functional programming paradigm.

Before we look at the function concept as such, we will take a look at definitions.

8.1 Definitions8.9 Optional parameters of Scheme functions (1)
8.2 The function concept8.10 Optional parameters of Scheme functions (2)
8.3 Lambda calculus8.11 Closures
8.4 Functions in Scheme8.12 Function definition in Scheme
8.5 Function objects8.13 Simple web-related functions (1)
8.6 Functions as first class values8.14 Simple web-related functions (2)
8.7 Anonymous functions8.15 Function exercises
8.8 Lambda expressions in Scheme
 

8.1.  Definitions
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

A definition binds a value to a name. The name is often referred to as a variable. The value bound to a name may be a function value (function object/closure), but it may also be another kind of value, such as a number or a list.

A definition binds a name to a value

Below we show the syntactic form of a definition in Scheme.


(define name expression)
Syntax 8.1    A name is first introduced and the name is bound to the value of the expression

  • About Scheme define forms

    • Appears normally at top level in a program

    • Creates a new location named name and binds the value of expression to that location

    • In case the location already exists we have a redefinition, and the define form is equivalent to the assignment (set! name expr)

    • Does not allow for imperative programming, because define cannot appear in selections, iterations, etc.

    • Can also appear at certain positions in bodies, but only as syntactic sugar for local binding forms (letrec)

In Section 8.12 we discuss definition of functions, and a particular variation of define which applies only for function definition.

As it is stated in the first item, define forms appear normally, but not necessarily at top level of a Scheme program. By top level we mean 'at the outer level' of a program - not nested into other constructs.

It is, however, possible to have define forms at certain other locations in a Scheme program. The Scheme Report [Abelson98] explains this in section 5.2. Later in this material, in Section 29.3, where we discuss simulation of object-oriented concepts in Scheme, we will use nested define forms.

 

8.2.  The function concept
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

We start our coverage of functions with the observation that there is both a conceptual and a notational starting point.

The conceptual starting point is the well-known mathematical concept of functions

The notational starting point is lambda calculus

The conceptual starting point is well-known for most readers, due to the common knowledge of the mathematical meaning of functions.

The notational starting point is probably not familiar to very many readers. It happens to be the case that the notational inspiration of lambda calculus is quite superficial, as applied in Scheme and Lisp.

  • 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

  • Lambda calculus

    • 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.

Before we continue the conceptual and programming-related discussion of functions, we will in Section 8.3 take a closer look at the notational starting point.

 

8.3.  Lambda calculus
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Lambda calculus is a more dense notation than the similar Scheme notation

Lambda calculus Scheme
Abstraction λ v . E (lambda (v) E)
Combination E1 E2 (E1 E2)
Table 8.1    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.

 

8.4.  Functions in Scheme
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

On this page we introduce the crucial distinction between a lambda expression and a function object. Lambda expressions are part of a source program. Lambda expressions can be evaluated as all other Scheme expressions. The value of a lambda expression is a function object.

Functions are represented as lambda expressions in a source program

At run time, functions are represented as first class function objects

Below we show a sample dialogue with a Scheme system. In the dialogue we define functions, and we play with them in order to illustrate some of the basic properties of function in relation to function definition and application. Please play with these elements yourself!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> (define x 6)

> (lambda (x) (+ x 1))
#<procedure>

> (define inc (lambda (x) (+ x 1)))

> inc
#<procedure:inc>

> (if (even? x) inc fac)
#<procedure:inc>

> ((if (even? x) inc fac) 5)
6
Program 8.1    A sample read-eval-print session with lambda expressions and function objects.

 

8.5.  Function objects
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Let us now define the concepts of function objects and closures.

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 also known as a closure.

  • 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 first characteristics of functions, as mentioned in the itemized lists above, is 'the first class status'. We will consolidate our understanding of first class 'citizens' in Section 8.6 .

 

8.6.  Functions as first class values
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

As it is discussed in this section, first class entities in a language can be passed as parameters, returned as results, and organized in data structures.

We are used to the first class status of numbers and lists. But with a background from imperative programming, we are not used to organize functions and procedures in data structures, and we are not used to the possibility of returning procedures and functions from other abstractions.

Notice that objects, as known from the object-oriented paradigm, are of first class.

Here is our definition of being 'of first class'.

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

A function object is a first class citizen

In Program 8.2 we show an interaction with a Scheme system, which illustrates that functions can be used as elements in data structures.

1
2
3
4
5
6
7
8
9
10
1> (define toplevel-html-elements (list html frameset))

2> overall-html-elements
(#<procedure> #<procedure>)

3> ((cadr toplevel-html-elements) (frame 'src "sss"))
(ast "frameset" ((ast "frame" () (src "sss") single)) () double)

4> (xml-render ((cadr toplevel-html-elements) (frame 'src "sss")))
"<frameset><frame src = \"sss\"></frameset>"
Program 8.2    A few interactions which illustrate the first class properties of function objects.

 

8.7.  Anonymous functions
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The reader may believe that a function name is a necessary constituent of a function. This understanding is not correct, however. We can chose to associate a name with a function by using an enclosing define form, as explained in Section 8.1. But the function itself is not named.

A function object does not have a name, and a function object is not necessarily bound to a name

The interactions below illustrate the use of anonymous functions, i.e., functions without names.

1
2
3
4
5
6
7
8
9
10
11
1> ((lambda(x) (+ x 1)) 3)
4

2> (define fu-lst 
  (list (lambda (x) (+ x 1)) (lambda (x) (* x 5))))

3> fu-lst
(#<procedure> #<procedure>)

4> ((second fu-lst) 6)
30
Program 8.3    An illustration of anonymous functions.

 

8.8.  Lambda expressions in Scheme
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The syntax definitions in Syntax 8.2 and Syntax 8.3 below show the two possible forms of lambda expressions.

Each of the formal parameters in a formal parameter list are binding name occurrences. It means that a formal parameter introduces a new name with a new role. The new name can be used and referred from other parts of the program. We can talk about the scope of the name as the area of the program in the which the binding is in effect. The scope of a formal parameter is - quite naturally - the body expression of the lambda form.

In the first syntax definition, formal-parameter-list is a list of formal parameters. The formal parameter list may be improper, such as (a b . c). In this case all actual parameters after the second one is bound to c.


(lambda (formal-parameter-list) expression)
Syntax 8.2    

In the second case, the list of actual parameters is simply bound to the name formal-parameters-name.

Be sure to understand the correspondence between formal parameters (in the two forms) and the actual parameters. Use Exercise 2.6 to strengthen your understanding.


(lambda formal-parameters-name expression)
Syntax 8.3    

  • Lambda expression characteristics in Scheme:

    • No type declaration of formal parameter names

    • Call by value parameters

      • In reality passing of references to lists and other structures

    • Positional and required parameters

      • (lambda (x y z) expr) accepts exactly three parameters

    • Required and rest parameters

      • (lambda (x y z . r) expr) accepts three or more parameters

    • Rest parameters only

      • (lambda r expr) accepts an arbitrary number of parameters


Exercise 2.6. Parameter passing in Scheme

Familiarize yourself with the parameter passing rules of Scheme by trying out the following calls:

  ((lambda (x y z) (list x y z)) 1 2 3)
  ((lambda (x y z) (list x y z)) 1 2)
  ((lambda (x y z) (list x y z)) 1 2 3 4)
  ((lambda (x y z . r) (list x y z r)) 1 2 3)
  ((lambda (x y z . r) (list x y z r)) 1 2)
  ((lambda (x y z . r) (list x y z r)) 1 2 3 4)
  ((lambda r r) 1 2 3)
  ((lambda r r) 1 2)
  ((lambda r r) 1 2 3 4)

Be sure that you can explain all the results

There is no solution to this exercise


 

8.9.  Optional parameters of Scheme functions (1)
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

In LAML software we use a particular pattern to deal with optional parameters. This pattern is built on top of the rest parameter mechanism discussed in Section 8.8. The pattern also involves a function optional-parameter, defined in the LAML general library, as an important brick.

When we use optional parameters of a function, the caller may chose not to pass a value. In that case, the parameter is bound to a default value, which is defined as part of the function.

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

The example in Program 8.4 illustrates how to define a function which requires one parameter rp, and up to three optional parameters op1, op2, and op3.

1
2
3
4
5
(define (f rp . optional-parameter-list)
 (let ((op1 (optional-parameter 1 optional-parameter-list 1))
       (op2 (optional-parameter 2 optional-parameter-list "a"))
       (op3 (optional-parameter 3 optional-parameter-list #f)))
  (list rp op1 op2 op3)))
Program 8.4    A example of a function f that accepts optional-parameters.

The following dialogue with a Scheme system shows optional parameters in play.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0>
(define (f rp . optional-parameter-list)
  (let ((op1 (optional-parameter 1 optional-parameter-list 1))
	(op2 (optional-parameter 2 optional-parameter-list "a"))
	(op3 (optional-parameter 3 optional-parameter-list #f)))
    (list rp op1 op2 op3)))

1> (f 7)
(7 1 "a" #f)

2> (f 7 "c")
(7 "c" "a" #f)

3> (f 7 8)
(7 8 "a" #f)

4> (f 7 8 9)
(7 8 9 #f)

5> (f 7 8 9 10)
(f 7 8 9 10)

6> (f 7 8 9 10 11)
(7 8 9 10)
Program 8.5    A number of calls of the function f.

In the next section we will discuss a major shortcoming of the optional parameter mechanism.

 

8.10.  Optional parameters of Scheme functions (2)
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Optional parameters, as discussed in Section 8.9 is not a perfect solution in all respects. On this page we will discuss a major weakness.

  • Observations about optional parameters:

    • 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

For more information about the simulation of keyword parameters in HTML and XML mirror functions, please consult Section 27.2.

 

8.11.  Closures
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Function objects are also called closures. In this section we will see why.

Functions capture the free names in the context of the lambda expression

The illustration below shows a closure. For a better visualization, you should visit the web version of the page, which uses animation to illustrate the capturing of free names.

When we talk about a free name it is always relative to a given construct, such as a lambda expression. A free name in the construct is used, but not bound in the construct. The formal parameter names of a lambda expression are 'binding positions'. Thus, names in the body of a lambda expression, which correspond to formal parameter names of the lambda expressions, are not free names.

Figure 8.1    An illustration of a closure, as formed by the syntactical lambda expression together with the necessary free names

In the table below we illustrate free names and closures. Notice that in the inner lambda expression, (lambda (txt) ...), both p and b are free names, whereas in the lambda expression bound to f only p is a free name.

Expression

Value

(define f
 (let ((b (lambda (x) 
            (string-append x ":" x))))
  (lambda (txt) (p (b txt)))))

(f "A text")

A text:A text

(b "A text")
A text
(f (b "A text"))

A text:A text

Table 8.2    Examples of the closuring effect. In the first example b is locally bound to a function which replicates its parameter with a colon in between. f is bound to a function (the inner lambda) in which b refers to the string replicating function. Notice that outside this this context, b is the HTML mirror function that renders a text in bold face.

 

8.12.  Function definition in Scheme
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

In Section 8.1 we studied definitions in general. In a definition we associate a name with a value through the evaluation of an expression. As already discussed there, we can define functions in the same way we associate names with other types of values.

In this section we will study a particular twist on function definitions.

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

In Syntax 8.4 we show the ordinary way of defining a function. With this, f is bound to a function object.


(define f (lambda (p1 p2) ...))
Syntax 8.4    The ordinary way to bind f to the value of a lambda expressions

In Syntax 8.5 we show an alternative way of defining a function. The second element of the define form is a list, which corresponds to the calling profile of the function. The two definitions are fully equivalent, and it is a matter of style and personal preference which one to use.

I typically use the form in Syntax 8.5 because it is a little more shallow (with respect to parentheses) than the one in Syntax 8.4. As another reason, it is nice to have the calling form as a constituent of the definition. It is often convenient to copy it out of the definition to some context, in which the function is to be called.


(define (f p1 p2) ...)
Syntax 8.5    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) ...)

 

8.13.  Simple web-related functions (1)
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The programs in Program 8.6 and Program 8.7 show the definition and a call of a www-document function, which abstracts the outer HTML elements. In the web version of the material you will, in addition, find an illustration with all the LAML details necessary to execute the example.

1
2
3
4
(define (www-document the-title . body-forms)
 (html
  (head (title the-title))
  (body body-forms)))
Program 8.6    The definition of a www-document function.

1
2
3
4
5
6
7
8
(www-document   
  "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 8.7    A sample application of the function www-document.

 

8.14.  Simple web-related functions (2)
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The example on this page shows an indent-pixel function, which indents a block of text a number of pixels to the right.

In Program 8.8 you find a version which is implemented in terms of tables.

1
2
3
4
5
6
(define (indent-pixels p . contents)
  (table 'border "0"
   (tbody
     (tr 
      (td 'width (as-string p) "")
      (td 'width "*" contents)))))
Program 8.8    The definition of the indent-pixel function.

In Program 8.9 we show an alternative version of indent-pixels, which is implement by use of Cascading Style Sheets (CSS) features.

1
2
3
(define (indent-pixels p . contents)
  (div 'css:margin-left (as-string p) 
    contents))
Program 8.9    An alternative version of theindent-pixel function.

Below, in Program 8.10 we show a sample application of the indent-pixels function. The program in Program 8.10 is complete and self contained relative to the LAML libraries.

In the web version of the material (slide or annotated slide view) you will find references to the generated documents.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(load (string-append laml-dir "laml.scm"))
(laml-style "simple-xhtml1.0-strict-validating")

(define (indent-pixels p . contents)
  (div 'css:margin-left (as-string p) 
    contents))

(write-html 'raw
 (html
  (head (title "Indent Pixel Example"))
  (body

    (p "Here is some initial text")

    (indent-pixels 45
       (p "First paragraph of indented text")
       (p "Second paragraph of indented text")
    )

    (p "Here is some final text"))))
Program 8.10    A sample application of indent-pixel with some initial LAML context (software loading).

 

8.15.  Function exercises
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

In this last section of the chapter we provide a couple of extra exercises.


Exercise 2.7. Colors in HTML

In HTML we define colors as text strings of length 7:

    "#rstuvw"

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

    "#ffffff"

represents white and

    "#ff0000"

is red.

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).

Solution


Exercise 2.8. 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.

Solution


 

8.16.  References
[Abelson98]Richard Kelsey, William Clinger and Jonathan Rees, "Revised^5 Report on the Algorithmic Language Scheme", Higher-Order and Symbolic Computation, Vol. 11, No. 1, August 1998, pp. 7--105.

Generated: Tuesday July 2, 2013, 09:14:51
Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'