|
Note that this HTML page was
generated from Word 2000. Some
of the code cannot be pasted into Qi. You are advised to download the program
files through the above link. 4 Lists 4.1 Representing Lists in Qi__________________ In Qi, a list begins with a [ and ends with a ]. So the list composed of 1, 2 and 3
would be written as [1 2 3].
Spaces or commas are used to separate items; the list [123] is not the
same as the list [1 2 3], since [123] is the list containing the single
number 123. Qi evaluates lists according to the list evaluation rule. The List
Evaluation Rule The normal form of a list L = [i1,...,in] is the list [i'1,...,i'n]
arrived at by evaluating the contents of L from left to right where for each
ij (1 £ j £ n), i'j = the
normal form of ij. Suppose we wish to find the normal
form of [(* 8 9) (+ 46 89) (- 67 43)] using the list evaluation rule. We evaluate (* 8 9)
first. (* 8 9) Þ 72 Second we evaluate (+ 46 89)
(+ 46 89) Þ 135 Last we evaluate (- 67 43).
(- 67 43) Þ 24 So the result is [72 135 24]. Lists can be placed within lists without restriction (figure
4.1).[1][1] The last example in that figure
features one rather special sort of list - the empty list [ ]; a list which contains nothing and
which evaluates to itself.[2][2]
Qi requires all brackets to balance before undertaking an evaluation.
If there unequal number of (s
and )s, or [s and ]s, then Qi will wait for the user to balance them. ^ can be used to abort the line input
in periods of confusion. [[1]] Þ [[1]] [tom dick harry] Þ [tom dick harry] [[1 dick [3]]] Þ [[1 dick [3]]] [(+ 1 2) [(+ 2 3)]] Þ [3 [5]] [(+ 34 34)
[(* 7 8) "foobar" [(- 9 8)]]] Þ [72
[56 "foobar" [1]]] [] Þ [] Figure 4.1
Some examples of lists and their normal forms 4.2 Building Lists with Cons_________________ There is one basic function for
building up lists called cons. The function
cons receives two
inputs, an object O and a list L[3][3] and builds a list L' through adding O to the front of
L. This is called consing O to L
(figure 4.2). (0-) (cons 1 [2 3]) [1 2 3] (1-) (cons tom [dick harry]) [tom dick harry] (2-) (cons 1 [ ]) [1] (3-) (cons tom (cons dick (cons
harry [ ]))) [tom dick harry] Figure 4.2
Using the cons function Using cons,
a supply of self-evaluating expressions, and the empty list [], any finite list can be built up. For instance, suppose we wish to
construct the list [[a b] c [d e]]. The list [a b] is formed by
consing a to the result of consing b to []. [a b] = (cons a (cons b [ ])) [d e] is the result of consing d to the result of consing e to [ ] [d e] = (cons d (cons e [ ])) The list [[d e]] is formed by consing [d e] to [ ]. [[d e]] = (cons [d e] [ ]) The list [[a b] c [d e]] is the result of consing [a b] to consing c to [[d e]]. [[a b] c [d e]] = (cons [a b]
(cons c [[d e]])) By making the necessary
substitutions in the right-hand-side of this equation, the expression [[a
b] c [d e]] is expressed in terms of consing operations. [[a b] c [d e]] = (cons (cons a
(cons b [ ])) (cons c (cons (cons d (cons e [ ])) [ ])))) When a list is described like this, using only conses, [ ] and
self-evaluating expressions we say that it is in cons form. For practical
purposes, writing lists in cons form is tedious and unnecessary. However,
when we come to reason about programs, it is important to know that any list
can be recast in cons form. The
translation of a list to its cons form version is purely mechanical. Simply keep applying the following
rules throughout any list representation until they can no longer be
applied. Cons Form
Translation Rules (i) [ ] is translated as [ ]. (ii) [e1,...,en] where (n ³ 1) is translated as (cons e1
[,...,en ]). 4.3 | is Shorthand for Cons___________________ A shorter way of expressing
consing (as an alternative to writing “cons”) is to use |;
every expression to the left of | is consed in turn to the list on the right of | (figure 4.3). (0-) [1 | [2 3]] [1 2 3] (1-) [tom dick harry | [ ]] [tom dick harry] Figure 4.3
Using | in Qi to cons expressions We explain how to evaluate
expressions containing | by showing how such expressions can be
translated into expressions not containing |, but cons instead.
The translation involves applying the following rules to every part of any
given expression until the |s are gone. | Elimination Rules (i) [e1 | e2]
is translated to (cons e1 e2). (ii) [e1 ,..., en
| en+1] (n ³ 2) is
translated to (cons e1 [
,..., en | en+1]). We apply these rules to [tom
dick harry | [ ]]. [tom dick harry | [ ]] = (cons tom [dick harry | [ ]])
by rule (ii) = (cons tom (cons dick [harry |
[ ]])) by rule (ii) = (cons tom (cons dick (cons
harry [ ])))
by rule (i) Þ [tom dick harry]. 4.4 Head and Tail Access Parts of Lists________ cons builds lists out of component parts. head and
tail allow these component parts to be extracted from the assembled
lists. head receives a
non-empty list and returns the first element in it; tail receives a
non-empty list and returns all but the first element of that list
(figure 4.4). (0-) (head [1 2 3]) 1 (1-) (tail [1 2 3]) [2 3] (2-) (head [[tom] dick harry]) [tom] (3-) (tail [tom [dick harry]]) [[dick harry]] Figure 4.4
Using head and tail to extract elements from a list Using head and tail
in composition, we can access any element in a list. (4-) (head (tail [1 2 3])) 2 (5-) (head (tail (tail [1 2 3]))) 3 4.5 Characters_____________________________ In Qi, any object can be mapped
into its essential characters;
for instance the symbol cat is composed of three characters,
represented as #\c #\a and #\t. The string "cat" is represented by a
series of 5 characters - #\", #\c, #\a, #\t,
and #\". The
function explode decomposes any object into its constituent
characters. (6-) (explode cat) [#\c #\a #\t] (7-) (explode "the cat") [#\" #\t #\h #\e #\Space #\c
#\a #\t #\"] (8-) (explode [cat]) [#\[ #\c #\a #\t #\]] Figure 4.5
Using explode to extract characters The decomposition of an object
into characters is useful when we want to analyse the component parts of a
symbol or string. For example,
here is a function that recognises Qi variables. element? searches a list to see if the first object
supplied to it is found in the list.[4][4] (define qi_variable? X -> (element? (head (explode X)) [#\A #\B #\C #\D #\E #\F #\G #\H #\I #\J #\K
#\L
#\M #\N #\O #\P #\Q #\R #\S #\T #\U #\V #\W #\X #\Y #\Z])) 4.6 Recursive List Processing_________________ The function element? returns true if its first
input X occurs somewhere in the list that is its second input Y and false otherwise. How may
this function be defined?
Intuitively, nothing is a member of the empty list, and if the element
is found to be at the head of Y then we may return true. If neither of these
obtain, then we have to search in the rest of the list. We express this reasoning as an
equational specification in figure 4.6. member(X, [ ]) = false member(X,Y) = true if X = head(Y) member(X,Y) = member(X, tail(Y))
if X ¹ head(Y) Figure 4.6
The equational specification of the member function Turning this into an Qi function
is easy (figure 4.7). (define member _ [ ] -> false X Y -> true where (= X (head Y)) X Y -> (member X (tail Y))) Figure 4.7 The member function in Qi |