Kurt Nørmark
Department of Computer Science, Aalborg University, Denmark

Abstract Previous lecture Next lecture Index References Contents

In this lecture we will explore the higher-order functions, both on classical ground and with examples from the WWW domain.

The concept higher-order function: A higher-order function accepts functions as arguments and is able to return a function as its result
The concept higher-order language: A higher-order language supports higher-order functions and allows functions to be constituents of data structures

The order of data Order 0: Non function data Order 1: Functions with domain and range of order 0 Order 2: Functions with domain and range of order 1 Order k: Functions with domain and range of order k-1 Order 0 data have nothing to do with functions. Numbers, lists, and characters are example of such data. Data of order 1 are functions which work on 'ordinary' order 0 data. Thus order 1 data are the functions we have been concerned with until now. Data of order 2 - and higher - are example of the functions that have our interest in this lecture.

Functions of order i, i >= 2, are called higher-order functions

Reference Foldoc: higher order function

Some simple and general higher-order functions Slide Annotated slide Contents Index References Textbook

It is time to look at some examples of higher-order functions. We start with a number of simple ones.

Program: The function flip changes the order of it's parameters. The function takes a function of two parameters, and returns another function of two parameters. The only difference between the input and output function of flip is the ordering of their parameters.

(define (flip f) (lambda (x y) (f y x)))

Program: An alternative formulation of flip without use of the sugared define syntax. For easy comparison we show the original version below the alternative formulation. The two different syntaxes are discussed in an earlier lecture, cf. the cross references.

(define flip (lambda (f) (lambda (x y) (f y x)))) (define (flip f) (lambda (x y) (f y x)))

Program: The function negate negates a predicate. Thus, negate takes a predicate function (boolean function) as parameter and returns the negated predicate. The resulting negated predicate returns true whenever the input predicate returns false, and vise versa.

(define (negate p) (lambda (x) (if (p x) #f #t)))

Program: The function compose composes two functions which both are assumed to take a single argument. The resulting function composed of f and g returns f(g(x)), or in Lisp (f (g x)), given the input x . The compose function from the general LAML library accepts two or more parameters, and as such it is more general than the compose function shown here.

(define (compose f g) (lambda (x) (f (g x))))

Exercise 4.2. Using flip, negate, and compose

Define and play with the functions flip, negate, and compose, as they are defined on this page . Define, for instance, a flipped cons function and a flipped minus function. Define the function odd? in terms of even? and negate. Finally, compose two HTML mirror functions, such as b and em, to a new function. Be sure you understand your results.

Reference The syntax of function definition

Linear search in lists Slide Annotated slide Contents Index References Textbook

Search criterias can be passed as predicates to linear search functions

Program: A linear list search function. A predicate accepts as input an element in the list, and it returns either true (#t) or false (#f). If the predicate holds (if it returns true), we have found what we searched for. The predicate pred is passed as the first parameter to find-in-list. As it is emphasized in blue color, the predicate is applied on the elements of the list. The first successful application (an application with true result) terminates the search, and the element is returned. If the first case in the conditional succeeds (the brown condition) we have visited all elements in the list, and we conclude that the element looked for is not there. In that case we return false.

;; A simple linear list search function. ;; Return the first element which satisfies the predicate pred. ;; If no such element is found, return #f. (define (find-in-list pred lst) (cond ((null? lst) #f) ((pred (car lst)) (car lst)) (else (find-in-list pred (cdr lst)))))

Program: A sample interaction using find-in-list. We define a simple association list which relates persons (symbols) and hair colors (strings). The third interaction searches for per's entry in the list. The fourth interaction searches for a person with pink hair color. In the fifth interaction nothing is found, because no person has yellow hair color. In the sixth interaction we illustrate the convenience of boolean convention in Scheme: everything but #f counts as true. From a traditional typing point of view the let expression is problematic, because it can return either a person (a symbol) or a boolean value. Notice however, from a pragmatic point of view, how useful this is.

1> (define hair-colors (pair-up '(ib per ann) '("black" "green" "pink"))) 2> hair-colors ((ib . "black") (per . "green") (ann . "pink")) 3> (find-in-list (lambda (ass) (eq? (car ass) 'per)) hair-colors) (per . "green") 4> (find-in-list (lambda (ass) (equal? (cdr ass) "pink")) hair-colors) (ann . "pink") 5> (find-in-list (lambda (ass) (equal? (cdr ass) "yellow")) hair-colors) #f 6> (let ((pink-person (find-in-list (lambda (ass) (equal? (cdr ass) "pink")) hair-colors))) (if pink-person (car pink-person) #f)) ann

Exercise 4.5. Linear string search

Lists in Scheme are linear linked structures, which makes it necessary to apply linear search techniques. Strings are also linear structures, but based on arrays instead of lists. Thus, strings can be linearly searched, but it is also possible to access strings randomly, and more efficiently. First, design a function which searches a string linearly, in the same way as find-in-list. Will you just replicate the parameters from find-in-list, or will you prefer something different? Next program your function in Scheme.

Exercise 4.5. Index in list

It is sometimes useful to know where in a list a certain element occurs, if it occurs at all. Program the function index-in-list-by-predicate which searches for a given element. The comparion between the given element and the elements in the list is controlled by a comparison parameter to index-in-list-by-predicate. The function should return the list position of the match (first element is number 0), or #f if no match is found. Some examples will help us understand the function: (index-in-list-by-predicate '(a b c c b a) 'c eq?) => 2 (index-in-list-by-predicate '(a b c c b a) 'x eq?) => #f (index-in-list-by-predicate '(two 2 "two") 2 (lambda (x y) (and (number? x) (number? y) (= x y)))) => 1 Be aware if your function is tail recursive.

Exercise 4.5. Binary search in sorted vectors

Linear search, as illustrated by other exercises, is not efficient. It is often attractive to organize data in a sorted vector, and to do binary search in the vector. This exercise is meant to illustrate a real-life higher-order function, generalized with several parameters that are functions themselves. Program a function binary-search-in-vector, with the following signature: (binary-search-in-vector v el sel el-eq? el-leq?) v is the sorted vector. el is the element to search for. If v-el is an element in the vector, the actual comparison is done between el and (sel v-el). Thus, the function sel is used as a selector on vector elements. Equality between elements is done by the el-eq? function. Thus, (el-eq? (sel x) (sel y)) makes sense on elements x and y in the vector. The ordering of elements in the vector is defined by the el-leq? function. (el-leq? (sel x) (sel y)) makes sense on elements x and y in the vector. The call (binary-search-in-vector v el sel el-eq? el-leq?) searches the vector via binary search and it returns an element el-v from the vector which satisfies (el-eq? (sel el-v) el). If no such element can be located, it returns #f. Here are some examples, with elements being cons pairs: (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 7 car = <=) => (7 . i) (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 2 car = <=) => (2 . x) (binary-search-in-vector '#( (2 . x) (4 . y) (5 . z) (7 . i) (9 . c) (11 . c)) 10 car = <=) => #f Be sure to program a tail recursive solution.

Generation of list selectors Slide Annotated slide Contents Index References Textbook

It is attractive to generate generalizations of the list selector functions car, cadr, etc

Program: A simple version of the make-selector-function function.

(define (make-selector-function n) (lambda (lst) (list-ref lst (- n 1))))

Program: The existing LAML make-selector-function. It is crucial that you get good error messages in case you access a non-existing list component. This version handles this. For error messages purposes this version of the function accepts an optional parameter, which (somehow redundantly) gives the name of the selector function.

;; Returns a function, which selects element number n in a list. ;; The second parameter, which is optional, is used for error message purposes. ;; In general, this parameter should be a string corresponding to the name of the selector function. ;; If the second parameter is given, we check whether the list is long enough for selection. ;; If not, we give a decent error message. We recommend use of the second parameter in order to ;; avoid meaningless error messages. ;; The first element is number 1. ;; (make-selector-function 1) corresponds to car, (make-selector-function 2) corresponds to cadr, etc. ;; .form (make-selector-function n [selector-name]) (define (make-selector-function n . optional-parameter-list) (let ((selector-name (optional-parameter 1 optional-parameter-list #f))) (if selector-name (lambda (lst) (let ((lgt (length lst))) (if (> n lgt) (display-error (string-append "The selector function " (as-string selector-name) ": " "The list " (as-string lst) " is is too short for selection. " "It must have at least " (as-string n) " elements." )) (list-ref lst (- n 1))))) (lambda (lst) (list-ref lst (- n 1))))))

Program: Example usages of the function make-selector-function. In interaction 1 through 3 we demonstrate generation and use of the first function. Next we outline how to define accessors of data structures, which are represented as lists. In reality, we are dealing with list-based record structures. In my every day programming, such list structures are quite common. It is therefore immensely important, to access data abstractly (via name accessors, instead of via the position in the list (car, cadr, etc). In this context, the make-selector-function comes in handy.

1> (define first (make-selector-function 1 "first")) 2> (first '(a b c)) a 3> (first '()) The selector function first: The list () is is too short for selection. It must have at least 1 elements. > 4> (define (make-person-record firstname lastname department) (list 'person-record firstname lastname department)) 5> (define person-record (make-person-record "Kurt" "Normark" "Computer Science")) 6> (define first-name-of (make-selector-function 2 "first-name-of")) 7> (define last-name-of (make-selector-function 3 "last-name-of")) 8> (last-name-of person-record) "Normark" 9> (first-name-of person-record) "Kurt"

There exists a few higher-order functions via which a wide variety of problems can be solved by simple combinations

Overview: Mapping: Application of a function on all elements in a list Filtering: Collection of elements from a list which satisfy a particular condition Accumulation: Pair wise combination of the elements of a list to a value of another type Zipping: Combination of two lists to a single list

The functions mentioned above represent abstractions of algorithmic patterns in the functional paradigm The idea of patterns has been boosted in the recent years, not least in the area of object-oriented programming. The classical higher-order list functions encode recursive patterns on the recursive data type list. As a contrast to many patterns in the object-oriented paradigm, the patterns encoded by map, filter, and others, can be programmed directly. Thus, the algorithmic patterns we study here are not design patterns. Rather, they are programming patterns for the practical functional programmer.

Mapping Slide Annotated slide Contents Index References Textbook

The idea of mapping is to apply a function on each element of a list, hereby collecting the list of the function applications

A mapping function applies a function on each element of a list and returns the list of these applications The function map is an essential Scheme function

Figure. Mapping a function m on a list. m is applied on every element, and the list of these applications is returned.

Reference Foldoc: map

The mapping function Slide Annotated slide Contents Index References Textbook

It is now time to study the implementation of the mapping function. We program a function called mymap in order not to redefine Scheme's own mapping function (a standard function in all Scheme implementations).

A possible implementation of map, called mymap:

Program: An implementation of map. This is not a good implementation because the recursive call is not a tail call. We leave it as an exercise to make a memory efficient implementation with tail recursion - see the exercise below.

(define (mymap f lst) (if (null? lst) '() (cons (f (car lst)) (mymap f (cdr lst)))))

Exercise 4.7. Iterative mapping function

In contrast to the function mymap on this page , write an iterative mapping function which is tail recursive. Test your function against mymap on this page, and against the native map function of your Scheme system.

Exercise 4.7. Table exercise: transposing, row elimination, and column elimination.

In an earlier section we have shown the application of some very useful table manipulation functions. Now it is time to program these functions, and to study them in further details. Program the functions transpose, eliminate-row, and eliminate-column, as they have been illustrated earlier. As one of the success criteria of this exercise, you should attempt to use higher-order functions as much and well as possible in your solutions. Hint: Program a higher-order function, (eliminate-element n). The function should return a function which eliminates element number n from a list.

Examples of mapping Slide Annotated slide Contents Index References Textbook

We will now study a number of examples.

Table. In the first row we map the string? predicate on a list of atoms (number, symbols, and strings). This reveals (in terms of boolean values) which of the elements that are strings. In the second row of the table, we map a 'multiply with 2' function on a list of numbers. The third row is more interesting. Here we map the composition of li , b , and red font coloring on the elements a, b, and c. When passed to the HTML mirror function ul , this makes an unordered list with red and bold items. Notice that the compose function used in the example is a higher-order function that can compose two or more functions. The function compose from lib/general.scm is such a function. Notice also that the HTML mirror function ul receives a list, not a string. The fifth and final row illustrates the raw HTML output, instead of the nicer rendering of the unordered list, which we used in the third row.

Expresion Value (map string? (list 1 'en "en" 2 'to "to")) (#f #f #t #f #f #t) (map (lambda (x) (* 2 x)) (list 10 20 30 40)) (20 40 60 80) (ul (map (compose li (compose b (lambda (x) (font-color red x)))) (list "a" "b" "c") ) ) a b c Same as above <ul> <li> <b><font color = "#ff0000">a</font></b> </li> <li> <b><font color = "#ff0000">b</font></b> </li> <li> <b><font color = "#ff0000">c</font></b> </li> </ul>

Filtering Slide Annotated slide Contents Index References Textbook

As the name indicates, the filter function is good for examining elements of a list for a certain property. Only elements which possess the property are allowed through the filter.

A filtering function applies a predicate (boolean function) on every element of a list. Only elements on which the predicate returns true are returned from the filtering function. The function filter is not an essential Scheme function - but is part of the LAML general library

Figure. Filtering a list with a predicate f. The resulting list is the subset of the elements which satisfy f (the elements on which f returns true).

References The LAML general library Foldoc: filter

The filtering function Slide Annotated slide Contents Index References Textbook

The next item on the agenda is an implementation of filter .

For practical purposes it is important to have a memory efficient filter function

Program: An implementation of filter which is memory efficient. If the predicate holds on an element of the list (the red fragment) we include the element in the result (the brown fragment). If not (the green fragment), we drop the element from the result (the purple fragment).

(define (filter pred lst) (reverse (filter-help pred lst '()))) (define (filter-help pred lst res) (cond ((null? lst) res) ((pred (car lst)) (filter-help pred (cdr lst) (cons (car lst) res))) (else (filter-help pred (cdr lst) res))))

Exercise 4.8. A straightforward filter function

The filter function illustrated in the material is memory efficient, using tail recursion. Take a moment here to implement the straightforward recursive filtering function, which isn't tail recursive.

Examples of filtering Slide Annotated slide Contents Index References Textbook

As we did for mapping, we will also here study a number of examples. As before, we arrange the examples in a table where the example expressions are shown to the left, and their values to the right.

Table. In the first row we filter the first five natural numbers with the even? predicate. In the second row, we filter the same list of numbers with the odd? predicate. Rather than using the name odd? we form it by calculating (negate even?) . We have seen the higher-order function negate earlier in this lecture. The third and final example illustrates the filtering of a list of atoms with the string? predicate. Only strings pass the filter, and the resulting list of strings is rendered in an ordered list by means of the mirror function of the ol HTML element.

Expression Value (filter even? '(1 2 3 4 5)) (2 4) (filter (negate even?) '(1 2 3 4 5)) (1 3 5) (ol (map li (filter string? (list 1 'a "First" "Second" 3)))) First Second Same as above <ol> <li>First</li> <li>Second</li> </ol>

Reduction of a list by means of a binary operator transforms the list to a value in the range of the binary operator.

Figure. Left and right reduction of a list. Left reduction is - quite naturally - shown to the left, and right reduction to the right.

There is no natural value for reduction of the empty list. Therefore we assume as a precondition that the list is non-empty.

The reduction functions Slide Annotated slide Contents Index References Textbook

The function reduce-right is a straightforward recursive function The function reduce-left is a straightforward iterative function

Program: The function reduce-right. Notice the fit between the composition of the list and the recursive pattern of the right reduction.

Program: The function reduce-left. There is a misfit between left reduction and the recursive composition of the list with heads and tails. However, an iterative process where we successively combine e1 and e2 (giving r1), r1 and e3 etc., is straightforward. As we have seen several times, this can be done by a tail recursive function, here reduce-help-left.

Table. Examples of reductions. The - left reduction of the list corresponds to calculating the expression (- (- (- (- 1 2) 3) 4) 5). The - right reduction of the list corresponds to calculating the expression (- 1 (- 2 (- 3 (- 4 5)))).

Expression Value (reduce-left - '(1 2 3 4 5)) -13 (reduce-right - '(1 2 3 4 5)) 3 (reduce-left string-append (list "The" " " "End")) "The End" (reduce-left append (list (list 1 2 3) (list 'a 'b 'c))) (1 2 3 a b c)

Exercise 4.9. Quantifier Functions

The mathematical quantifiers for all and there exists are well-known. In this exercise we will write similar Scheme quantifier functions. The function (for-all lst p) is supposed to check if all elements in the list lst satisfy the predicate p. The function (there-exists lst p) is supposed to check if one or more elements in the list lst satisfy the predicate p. Finally, the function (there-exists-1 lst p) is supposed to check if exactly on element in the list lst satisfies p. Program and test these functions. You should in addition consider how to program these function by use of map, filter, and reduction (accumulation). Please decide if your functions are tail recursive.

Accumulation Slide Annotated slide Contents Index References Textbook

It is not satisfactory that we cannot reduce the empty list We remedy the problem by passing an extra parameter to the reduction functions We call this variant of the reduction functions for accumulation

Program: The function accumulate-right. The recursive pattern is similar to the pattern of reduce-right.

Table. Examples of right accumulations. The first row illustrates that we can accumulate the empty list. The second and third rows are similar to the second and third rows in Table 15.1.

Expression Value (accumulate-right - 0 '()) 0 (accumulate-right - 0 '(1 2 3 4 5)) 3 (accumulate-right append '() (list (list 1 2 3) (list 'a 'b 'c))) (1 2 3 a b c)

In relation to web programming we most often append accumulate lists and strings accumulate-right is part of the general LAML library Due to their deficiencies, the reduction functions are not used in LAML

Zipping Slide Annotated slide Contents Index References Textbook

Two equally long lists can be pair wise composed to a single list by means of zipping them

Figure. Zipping two lists with the function z. The head of the resulting list is (z e i f i), where the element e i comes from the first list, and f i comes from the other.

The zipping function Slide Annotated slide Contents Index References Textbook

Program: The function zip.

Table. Examples of zipping.

Expression Value (zip cons '(1 2 3) '(a b c)) ((1 . a) (2 . b) (3 . c)) (apply string-append (zip string-append '("Rip" "Rap" "Rup") '(", " ", and " ""))) "Rip, Rap, and Rup" (string-merge '("Rip" "Rap" "Rup") '(", " ", and ")) "Rip, Rap, and Rup"

Zip is similar to the function string-merge from the LAML general library However, string-merge handles lists of strings non-equal lengths, and it concatenates the zipped results

Reference The string-merge function

The concept currying: Currying allows us to understand every function as taking at most one parameter. Currying can be seen as a way of generating intermediate functions which accept additional parameters to complete a calculation

Figure. The signatures of curried functions. In the upper frame we show the signature of a function f, which takes three parameters. The frames below show the signature when f is curried. In the literature, the notation shown to the bottom right is most common. The frame to the left shows how to parse the notation (the symbol -> associates to the right).

Currying and Scheme is not related to each other. Currying must be integrated at a more basic level to be elegant and useful

Reference Foldoc: curried function

Currying in Scheme Slide Annotated slide Contents Index References Textbook

It is possible to generate curried functions in Scheme. But the parenthesis notation of Lisp does not fit very well with the idea of currying

Program: Generation of curried and uncurried functions in Scheme.

(define (curry2 f) (lambda(x) (lambda(y) (f x y)))) (define (curry3 f) (lambda(x) (lambda(y) (lambda(z) (f x y z))))) (define (uncurry2 f) (lambda (x y) ((f x) y))) (define (uncurry3 f) (lambda (x y z) (((f x) y) z)))

Exercise 4.10. Playing with curried functions in Scheme

Try out the functions curry2 and curry3 on a number of different functions. You can, for instance, use then curry functions on plus (+) and map. Demonstrate, by a practical example, that the uncurry functions and the curry functions are inverse to each other.

Examples of currying Slide Annotated slide Contents Index References Textbook

Curried functions are very useful building blocks in the functional paradigm In particular, curried functions are adequate for mapping and filtering purposes

Table. Examples of currying in Scheme.

Expression Value (font-1 4 red "Large red text") Large red text (define curried-font-1 (curry3 font-1)) (define large-font (curried-font-1 5)) ((large-font blue) "Very large blue text") Very large blue text (define small-brown-font ((curried-font-1 2) brown)) (small-brown-font "Small brown text") Small brown text (define large-green-font ((curried-font-1 5) green)) (list-to-string (map large-green-font (list "The" "End")) " ") The End

Ad hoc currying in Scheme (1) Slide Annotated slide Contents Index References Textbook

It is possible to achieve 'the currying effect' by generalizing functions, which requires two or more parameters, to only require a single parameter

Motivation:

Table. A legal mapping and an impossible attempt to curry the mapping function. The last example shows an application of curry2 to achieve the wanted effect, but as it appears, the solution is not very elegant.

Expression Value (map li (list "one" "two" "three")) ("<li>one</li>" "<li>two</li>" "<li>three</li>") (define li-mapper (map li)) map: expects at least 2 arguments, given 1 (define li-mapper ((curry2 map) li)) (li-mapper (list "one" "two" "three")) ("<li>one</li>" "<li>two</li>" "<li>three</li>")

Program: The function curry-generalized. This is a higher-order function which generalizes the function passed as parameter to curry-generalized. The generalization provides for just passing a single parameter to f, in the vein of currying.

(define (curry-generalized f) (lambda rest (cond ((= (length rest) 1) (lambda lst (apply f (cons (car rest) lst)))) ((>= (length rest) 2) (apply f (cons (car rest) (cdr rest)))))))

Ad hoc currying in Scheme (2) Slide Annotated slide Contents Index References Textbook

Better results:

Table. Examples of curry generalization of map. Using curry-generalized it is possible to make a li-mapper in an elegant and satisfactory way. The last row in the table shows that gmap can be used instead of map. Thus, gmap can in all respect be a substitution for map, and we may chose to redefine the name map to the value of (curry-generalized map).

Expression Value (define gmap (curry-generalized map)) (define li-mapper (gmap li)) (li-mapper (list "one" "two" "three")) ("<li>one</li>" "<li>two</li>" "<li>three</li>") (gmap li (list "one" "two" "three")) ("<li>one</li>" "<li>two</li>" "<li>three</li>")

There are three different cases to consider: double tag elements, single tag elements, and tags that can be both single and double. A well-known tag, that can be both single and double is the p tag.

Program: The two higher-order functions for the HTML mirror generation. This version corresponds to the an earlier version of LAML's HTML mirror.

(define (generate-double-tag-function tag-name) (lambda (contents . attributes) (double-tag tag-name contents attributes))) (define (generate-single-tag-function tag-name) (lambda attributes (single-tag tag-name attributes)))

Program: Functions that generate single and double tags.

(define (single-tag name attributes) (start-tag name attributes)) (define (double-tag name contents attributes) (string-append (start-tag name attributes) (as-string contents) (end-tag name)))

Program: Functions that generate individual single and double tags.

(define (start-tag kind attributes) (if (null? attributes) (string-append "<" kind ">") (let ((html-attributes (linearize-attributes attributes))) (string-append "<" kind " " html-attributes " >")))) (define (end-tag kind) (string-append "</" kind ">"))

Program: Functions for attribute linearization. The parameter attr-list is a property list.

(define (linearize-attributes attr-list) (string-append (linearize-attributes-1 (reverse attr-list) "" (length attr-list)))) (define (linearize-attributes-1 attr-list res-string lgt) (cond ((null? attr-list) res-string) ((>= lgt 2) (linearize-attributes-1 (cddr attr-list) (string-append (linearize-attribute-pair (car attr-list) (cadr attr-list)) " " res-string) (- lgt 2))) ((< lgt 2) (error "The attribute list must have even length")))) (define (linearize-attribute-pair val attr) (string-append (as-string attr) " = " (string-it (as-string val))))

Program: All functions from above in a single file.

(define (generate-double-tag-function tag-name) (lambda (contents . attributes) (double-tag tag-name contents attributes))) (define (generate-single-tag-function tag-name) (lambda attributes (single-tag tag-name attributes))) (define (single-tag name attributes) (start-tag name attributes)) (define (double-tag name contents attributes) (string-append (start-tag name attributes) (as-string contents) (end-tag name))) (define (start-tag kind attributes) (if (null? attributes) (string-append "<" kind ">") (let ((html-attributes (linearize-attributes attributes))) (string-append "<" kind " " html-attributes " >")))) (define (end-tag kind) (string-append "</" kind ">")) (define (linearize-attributes attr-list) (string-append (linearize-attributes-1 (reverse attr-list) "" (length attr-list)))) (define (linearize-attributes-1 attr-list res-string lgt) (cond ((null? attr-list) res-string) ((>= lgt 2) (linearize-attributes-1 (cddr attr-list) (string-append (linearize-attribute-pair (car attr-list) (cadr attr-list)) " " res-string) (- lgt 2))) ((< lgt 2) (error "The attribute list must have even length")))) (define (linearize-attribute-pair val attr) (string-append (as-string attr) " = " (string-it (as-string val)))) (define (map-concat f lst) (apply string-append (map f lst)))

The current HTML mirror in LAML is more advanced and sophisticated than the one illustrated above

References The HTML4.01 transitional validating mirror The XHTML1.0 strict validating mirror

HTML mirror usage examples Slide Annotated slide Contents Index References Textbook

The example assumes loading of laml.scm and the function map-concat, which concatenates the result of a map application. The real mirrors use implicit (string) concatenation

Table. An example usage of the simple HTML mirror which we programmed on the previous page. The bottom example shows, as in earlier similar tables, the HTML rendering of the constructed table. The map-concat function used in the example is defined in the general LAML library as (define (map-concat f lst) (apply string-append (map f lst))). In order to actually evaluate the expression you should load laml.scm of the LAML distribution first.

Expression Value (let* ((functions (map generate-double-tag-function (list "table" "td" "tr"))) (table (car functions)) (td (cadr functions)) (tr (caddr functions))) (table (string-append (tr (map-concat td (list "c1" "c2" "c3")) 'bgcolor "#ff0000") (tr (map-concat td (list "c4" "c5" "c6"))) (tr (map-concat td (list "c7" "c8" "c9")))) 'border 3)) <table border="3"> <tr bgcolor="#ff0000"> <td> c1 </td> <td> c2 </td> <td> c3 </td> </tr> <tr> <td> c4 </td> <td> c5 </td> <td> c6 </td> </tr> <tr> <td> c7 </td> <td> c8 </td> <td> c9 </td> </tr> </table> Same as above c1 c2 c3 c4 c5 c6 c7 c8 c9

Making tables with the real mirror Slide Annotated slide Contents Index References Textbook

The real mirror provide for more elegance than the simple mirror illustrated above Here we will use the XHTML1.0 transitional mirror

Table. A XHTML mirror expression with a table corresponding to the table shown on the previous page and the corresponding HTML fragment. Notice the absence of string concatenation. Also notice that the border attribute is given before the first tr element. The border attribute could as well appear after the tr elements, or in between them.

Expression Rendered value (table 'border 3 (tr (map td (list "c1" "c2" "c3")) 'bgcolor "#ff0000") (tr (map td (list "c4" "c5" "c6"))) (tr (map td (list "c7" "c8" "c9"))) ) <table border = "3"> <tr bgcolor = "#ff0000"> <td>c1</td> <td>c2</td> <td>c3</td> </tr> <tr> <td>c4</td> <td>c5</td> <td>c6</td> </tr> <tr> <td>c7</td> <td>c8</td> <td>c9</td> </tr> </table> Same as above c1 c2 c3 c4 c5 c6 c7 c8 c9

Tables with higher-order functions Slide Annotated slide Contents Index References Textbook

Instead of explicit composition of td and tr elements we can use a mapping to apply tr to rows and td to elements

Table. In the table expression we map - at the outer level - a composition of tr and a td-mapper. The td-mapper is made by (gmap td).

Expression Value (define rows '(("This" "is" "first" "row") ("This" "is" "second" "row") ("This" "is" "third" "row") ("This" "is" "fourth" "row")) ) (table 'border 5 (gmap (compose tr (gmap td)) rows)) This is first row This is second row This is third row This is fourth row

The last example illustrates that (gmap td) is a useful building block, which can be composed with other functions. The last example depends on the fact that the HTML mirror functions accept lists of elements and attributes.

HTML element modifications Slide Annotated slide Contents Index References Textbook

The idea behind the function modify-element is to perform an a priori binding of some attributes and some of the contents of a mirror function.

Program: The function modify-element.

(define (modify-element element . attributes-and-contents) (lambda parameters (apply element (append parameters attributes-and-contents))))

Table. Examples of element modification using the function modify-element.

Expression Value (define td1 (modify-element td 'bgcolor (rgb-color-list red) 'width 50)) (table 'border 5 (map (compose tr (gmap td1)) rows)) This is first row This is second row This is third row This is fourth row (define ol1 (modify-element ol 'type "A")) (ol1 (map (compose li as-string) (number-interval 1 10))) 1 2 3 4 5 6 7 8 9 10 (define ul1 (modify-element ul 'type "square")) (ul1 (map (compose li as-string) (number-interval 1 10))) 1 2 3 4 5 6 7 8 9 10

The function simple-html-table Slide Annotated slide Contents Index References Textbook

In an earlier exercise - 'restructuring of lists' - we have used the function simple-html-table We will now show how it can be implemented

Program: The function simple-html-table. Locally we bind gmap to the curry generalized map function. We also create a specialized version of td, which includes a width attribute the value of which is passed as parameter to simple-html-table . In the body of the let construct we create the table in the same way as we have seen earlier in this lecture.

(define simple-html-table (lambda (column-widht list-of-rows) (let ((gmap (curry-generalized map)) (td-width (modify-element td 'width (as-string column-widht)))) (table 'border 1 (tbody (gmap (compose tr (gmap td-width)) list-of-rows))))))

Reference The page with the 'Restructuring of lists' exercise

The XHTML mirror in LAML Slide Annotated slide Contents Index References Textbook

LAML supports an exact mirror of the 77 XHTML1.0 strict elements as well as the other XHTML variants The LAML HTML mirror libraries are based on a parsed representation of the HTML DTD (Document Type Definition). The table below is automatically generated from the same data structure.

Table. HTML elements, their status, and their attributes in the XHTML1.0 strict Scheme mirror. The Content model information is - for most elements - shown as predicates which validate the individual elements. An EMPTY indication tells that there is no content model to validate, because the element is a terminal one (no constituent elements). For a few elements a non-trivial string is given as content model. These elements calls for specialized validation predicates, which have be hand written, from case to case.

Element Content model Attributes html (sequence-with-optionals "head" "body") lang dir xml:lang xmlns head "((script|style|meta|link|object)*, ((title, (script|style|meta|link|object)*, (base, (script|style|meta|link|object)*)?) | (base, (script|style|meta|link|object)*, (title, (script|style|meta|link|object)*))))" lang dir xml:lang profile title pcdata-checker lang dir xml:lang base "EMPTY" href meta "EMPTY" lang name xml:lang content dir scheme http-equiv link "EMPTY" id onmousemove class onmouseout style onkeypress title onkeydown lang onkeyup xml:lang charset dir href onclick hreflang ondblclick type onmousedown rel onmouseup rev onmouseover media style pcdata-checker lang media xml:lang title dir xml:space type script pcdata-checker charset defer type xml:space src noscript (zero-or-more "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick body (zero-or-more "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "ins" "del" "script" "noscript") id onmouseup class onmouseover style onmousemove title onmouseout lang onkeypress xml:lang onkeydown dir onkeyup onclick onload ondblclick onunload onmousedown div (zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick p (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick h1 (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick h2 (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick h3 (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick h4 (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick h5 (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick h6 (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick ul (one-or-more "li") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick ol (one-or-more "li") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick li (zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick dl (one-or-more "dt" "dd") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick dt (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick dd (zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick address (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick hr "EMPTY" id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick pre (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "map" "tt" "i" "b" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick xml:space blockquote (zero-or-more "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick cite ins (zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmouseup class onmouseover style onmousemove title onmouseout lang onkeypress xml:lang onkeydown dir onkeyup onclick cite ondblclick datetime onmousedown del (zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmouseup class onmouseover style onmousemove title onmouseout lang onkeypress xml:lang onkeydown dir onkeyup onclick cite ondblclick datetime onmousedown a (zero-or-more "#PCDATA" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onkeydown class onkeyup style charset title type lang name xml:lang href dir hreflang onclick rel ondblclick rev onmousedown accesskey onmouseup shape onmouseover coords onmousemove tabindex onmouseout onfocus onkeypress onblur span (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick bdo (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousemove class onmouseout style onkeypress title onkeydown onclick onkeyup ondblclick lang onmousedown xml:lang onmouseup dir onmouseover br "EMPTY" id style class title em (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick strong (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick dfn (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick code (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick samp (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick kbd (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick var (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick cite (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick abbr (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick acronym (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick q (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick cite sub (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick sup (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick tt (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick i (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick b (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick big (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick small (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick object (zero-or-more "#PCDATA" "param" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onkeydown class onkeyup style declare title classid lang codebase xml:lang data dir type onclick codetype ondblclick archive onmousedown standby onmouseup height onmouseover width onmousemove usemap onmouseout name onkeypress tabindex param "EMPTY" id valuetype name type value img "EMPTY" id onmousemove class onmouseout style onkeypress title onkeydown lang onkeyup xml:lang src dir alt onclick longdesc ondblclick height onmousedown width onmouseup usemap onmouseover ismap map "((p | h1|h2|h3|h4|h5|h6 | div | ul | ol | dl | pre | hr | blockquote | address | fieldset | table | form | ins | del | script | noscript)+ | area+)" lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick id onmousedown class onmouseup style onmouseover title onmousemove name area "EMPTY" id onmouseout class onkeypress style onkeydown title onkeyup lang shape xml:lang coords dir href onclick nohref ondblclick alt onmousedown tabindex onmouseup accesskey onmouseover onfocus onmousemove onblur form (zero-or-more "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "ins" "del" "script" "noscript") id onmousemove class onmouseout style onkeypress title onkeydown lang onkeyup xml:lang action dir method onclick enctype ondblclick onsubmit onmousedown onreset onmouseup accept onmouseover accept-charset label (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmouseover class onmousemove style onmouseout title onkeypress lang onkeydown xml:lang onkeyup dir for onclick accesskey ondblclick onfocus onmousedown onblur onmouseup input "EMPTY" id name class value style checked title disabled lang readonly xml:lang size dir maxlength onclick src ondblclick alt onmousedown usemap onmouseup tabindex onmouseover accesskey onmousemove onfocus onmouseout onblur onkeypress onselect onkeydown onchange onkeyup accept type select (one-or-more "optgroup" "option") id onmouseout class onkeypress style onkeydown title onkeyup lang name xml:lang size dir multiple onclick disabled ondblclick tabindex onmousedown onfocus onmouseup onblur onmouseover onchange onmousemove optgroup (one-or-more "option") id onmouseup class onmouseover style onmousemove title onmouseout lang onkeypress xml:lang onkeydown dir onkeyup onclick disabled ondblclick label onmousedown option pcdata-checker id onmouseover class onmousemove style onmouseout title onkeypress lang onkeydown xml:lang onkeyup dir selected onclick disabled ondblclick label onmousedown value onmouseup textarea pcdata-checker id onkeypress class onkeydown style onkeyup title name lang rows xml:lang cols dir disabled onclick readonly ondblclick tabindex onmousedown accesskey onmouseup onfocus onmouseover onblur onmousemove onselect onmouseout onchange fieldset (zero-or-more "#PCDATA" "legend" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick legend (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick accesskey button (zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "table" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "ins" "del" "script" "noscript") id onmouseout class onkeypress style onkeydown title onkeyup lang name xml:lang value dir type onclick disabled ondblclick tabindex onmousedown accesskey onmouseup onfocus onmouseover onblur onmousemove table "(caption?, (col*|colgroup*), thead?, tfoot?, (tbody+|tr+))" id onmousemove class onmouseout style onkeypress title onkeydown lang onkeyup xml:lang summary dir width onclick border ondblclick frame onmousedown rules onmouseup cellspacing onmouseover cellpadding caption (zero-or-more "#PCDATA" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onmousedown class onmouseup style onmouseover title onmousemove lang onmouseout xml:lang onkeypress dir onkeydown onclick onkeyup ondblclick thead (one-or-more "tr") id onmousemove class onmouseout style onkeypress title onkeydown lang onkeyup xml:lang span dir width onclick align ondblclick char onmousedown charoff onmouseup valign onmouseover tfoot (one-or-more "tr") id onmousemove class onmouseout style onkeypress title onkeydown lang onkeyup xml:lang span dir width onclick align ondblclick char onmousedown charoff onmouseup valign onmouseover tbody (one-or-more "tr") id onmouseover class onmousemove style onmouseout title onkeypress lang onkeydown xml:lang onkeyup dir align onclick char ondblclick charoff onmousedown valign onmouseup colgroup (zero-or-more "col") id onmouseover class onmousemove style onmouseout title onkeypress lang onkeydown xml:lang onkeyup dir align onclick char ondblclick charoff onmousedown valign onmouseup col "EMPTY" id onmouseover class onmousemove style onmouseout title onkeypress lang onkeydown xml:lang onkeyup dir align onclick char ondblclick charoff onmousedown valign onmouseup tr (one-or-more "th" "td") id onmouseover class onmousemove style onmouseout title onkeypress lang onkeydown xml:lang onkeyup dir align onclick char ondblclick charoff onmousedown valign onmouseup th (zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onkeypress class onkeydown style onkeyup title abbr lang axis xml:lang headers dir scope onclick rowspan ondblclick colspan onmousedown align onmouseup char onmouseover charoff onmousemove valign onmouseout td (zero-or-more "#PCDATA" "p" "h1" "h2" "h3" "h4" "h5" "h6" "div" "ul" "ol" "dl" "pre" "hr" "blockquote" "address" "fieldset" "table" "form" "a" "br" "span" "bdo" "object" "img" "map" "tt" "i" "b" "big" "small" "em" "strong" "dfn" "code" "q" "sub" "sup" "samp" "kbd" "var" "cite" "abbr" "acronym" "input" "select" "textarea" "label" "button" "ins" "del" "script" "noscript") id onkeypress class onkeydown style onkeyup title abbr lang axis xml:lang headers dir scope onclick rowspan ondblclick colspan onmousedown align onmouseup char onmouseover charoff onmousemove valign onmouseout

References The XHTML1.0 strict validating mirror The XHTML1.0 transitional validating mirror The XHTML1.0 frameset validating mirror The HTML4.01 transitional validating mirror

Generation of a leq predicate from enumeration Slide Annotated slide Contents Index References Textbook

In some contexts we wish to specify a number of clauses in an arbitrary order For presentational clarity, we often want to ensure that the clauses are presented in a particular order Here we want to generate a leq predicate from an enumeration of the desired order

Table. A simple example of an application of generate-leq.

Expression Value (define simple-leq? (generate-leq '(z a c b y x) id-1)) (sort-list '(a x y z c c b a) simple-leq?) (z a a c c b y x)

Program: A hypothetical manual page clause. Before we present the clauses of the manual page we want to ensure, that they appear in a particular order, say title, form, description, pre-condition, result, and misc. In this example we will illustrate how to obtain such an ordering in an elegant manner.

(manual-page (form '(show-table rows)) (title "show-table") (description "Presents the table, in terms of rows") (parameter "row" "a list of elements") (pre-condition "Must be placed before the begin-notes clause") (misc "Internally, sets the variable lecture-id") (result "returns an HTML string") )

Program: The functions generate-leq and the helping function list-index .

;; Generate a less than or equal predicate from the ;; enumeration-order. If p is the generated predicate, ;; (p x y) is true if and only if (selector x) comes before ;; (or at the same position) as (selector y) in the ;; enumeration-order. Thus, (selector x) is assumed to give a ;; value in enumeration-order. Comparison with elements in the ;; enumeration-list is done with eq? (define (generate-leq enumeration-order selector) (lambda (x y) ; x and y supposed to be elements in enumeration order (let ((x-index (list-index (selector x) enumeration-order)) (y-index (list-index (selector y) enumeration-order))) (<= x-index y-index)))) ; A helping function of generate-leq. ; Return the position of e in lst. First is 1 ; compare with eq? ; if e is not member of lst return (+ 1 (length lst)) (define (list-index e lst) (cond ((null? lst) 1) ((eq? (car lst) e) 1) (else (+ 1 (list-index e (cdr lst))))))

Program: An application of generate-leq which sorts the manual clauses.

(define (syntactic-form name) (lambda subclauses (cons name subclauses))) (define form (syntactic-form 'form)) (define title (syntactic-form 'title)) (define description (syntactic-form 'description)) (define parameter (syntactic-form 'parameter)) (define pre-condition (syntactic-form 'pre-condition)) (define misc (syntactic-form 'misc)) (define result (syntactic-form 'result)) (define (manual-page . clauses) (let ((clause-leq? (generate-leq '(title form description pre-condition result misc) first)) ) (let ((sorted-clauses (sort-list clauses clause-leq?))) (present-clauses sorted-clauses))))

Chapter 4: Higher-order Functions
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: July 2, 2013, 09:15:26