```.
INT_PLACES is an integer specifying the number of character
positions that  should occupy, including leading spaces, and
minus sign, if NUM is negative. FRAC_PLACES specifies the number of
positions the  part should occupy, excluding the ".", and
including trailing zeros if necessary. E.g.

pr("|"); prnum(-3.52, 4, 5);pr("|");
|  -3.5200|

Runs the procedure P, which should take N arguments, ITEM_1 to
ITEM_N, in an environment in which pop_pr_radix has the integer
value RADIX. So any printing done by P uses that value of

2D.0000

More sophisticated general purpose printing procedures are defined in
REF PRINT, including:

printf, nprintf, pr_field, format_print

-- Maximum and minimum integer sizes: pop_max_int, pop_min_int

(Almost) all the arithmetic operators in Poplog can be applied to all
the different kinds of numbers and will produce appropriate kinds of
results. So for example if you add or multiply integers together you'll
get integers until the result is too large to fit into the maximum space
allowed for integers, and in that case the result will be a biginteger.
Where the transition occurs will depend on the word size of your
INT_PARAMETERS library:

lib int_parameters

This makes available two variables: pop_max_int, which is the largest
(i.e. most positive) integer value and pop_min_int, which is the
smallest (i.e. most negative) integer value. On a typical 32 bit machine
these give:

pop_max_int, pop_min_int =>
** 536870911 -536870912

So any integer operation producing a number bigger than the first or
smaller (more negative) than the second will produce a biginteger, not
an integer.

isinteger(pop_min_int) =>
**
isinteger(pop_min_int - 1) =>
**
isbiginteger(pop_min_int - 1) =>
**

-- The representation of floating point numbers: lib float_parameters

In order to obtain information about decimals and ddecimals in your
version of Pop-11 use the following library

lib float_parameters

This provides the following implementation dependent constants, all of
which are explained fully in REF NUMBERS:

pop_most_positive_decimal
pop_least_positive_decimal
pop_least_negative_decimal
pop_most_negative_decimal
pop_most_positive_ddecimal
pop_least_positive_ddecimal
pop_least_negative_ddecimal
pop_most_negative_ddecimal

pop_plus_epsilon_decimal
pop_plus_epsilon_ddecimal
pop_minus_epsilon_decimal
pop_minus_epsilon_ddecimal

point numbers can be obtained using facilities defined below.

-- Basic arithmetical facilities --------------------------------------

There are several procedures for manipulating numbers of all types. The
most commonly used ones are represented by 'infix' identifiers. That is
they can be used to create expressions without using parentheses, e.g.

3 + 5,  77 * 9,

although it is legal to write +(3, 5) or *(77, 9) instead if you prefer.

The operations listed below are available for constructing arithmetic
expressions. They all take numbers of every variety in all combinations.
I.e. they are "overloaded" or "polymorphic" operators. (The exception is
"mod" which cannot be applied to complex numbers.)

When the result is a floating point number, whether it is represented as
a decimal (single precision) or ddecimal (double precision) will depend
on whether the global variable popdprecision is false or not, as
explained below.

In general the rules in Pop-11 for deciding on the type of result to be
produced by a mathematical procedure conform to standard mathematical
expectations. For example, a decimal divided by an integer will give a
decimal, unless popdprecision is true, in which case it will give a
ddecimal.  Division of one integer by another may produce a surprise
in the form of a ratio, as described below.

-- Arithmetical operators ---------------------------------------------

OPERATOR PRECEDENCE DESCRIPTION
-       5       subtract two numbers, or negate one number.
(The syntactic context is used to determine whether this is
a binary subtraction operator or a unary negation operator)
*       4       multiply two numbers
**      3       exponentiation:
e.g. A ** 3 means A*A*A i.e. A cubed.
/       4       divide first number by second (See note below)
//      4       divide first number by second, produce
remainder and quotient.

X div Y    2       returns the number of times Y goes into X
X rem Y    2       returns the remainder on dividing X by Y.
X mod Y    2       returns the remainder on dividing X by Y.
mod, unlike rem, requires both numbers to be real, i.e.
non-complex. It always returns a result with the same sign as Y

-- . Examples of arithmetical expressions

Here are some expressions formed using arithmetic operators:

3 + 5 * 2 =>
** 13

(3 + 5) * 2 =>
** 16

The expression:

(X + Y) * (99 - Z/3)

has many sub-expressions, e.g. X, Y, 99, Z, 3, X + Y, Z/3, etc.

Notice how parentheses can affect the order in which operations are
applied.

-- . Illustrating the use of // (which produces two results)

The operator // is unusual in that it produces two results. It takes two
integers, and produces two integers, a remainder and a divisor, as in:

10 // 3 =>
** 1 3

23 // 10 =>
** 3 2

Thus one can do things like

vars remainder, quotient;  223 // 10 -> (remainder, quotient);
remainder, quotient =>
** 3 22

or, combining the declaration with a multiple initialisation:

vars (remainder, quotient) = 223 // 10;

To illustrate the use of // on different kinds of numbers:

Dividing integers

10 // 3 =>
** 1 3
10 // -3 =>
** 1 -3
-10 // 3 =>
** -1 -3
-10 // -3 =>
** -1 3

Dividing decimals (or ddecimals)
10.5 // -3.2 =>
** 0.9 -3

Dividing ratios
(7/3) // (11/23) =>
** 29_/69 4

Dividing complexes
(33 + sqrt(-57)) // sqrt(-5) =>
** 1.69505_+:0.841633 3_-:14

-- -- Binary and unary negation

Most of the above are 'binary' operations. That is, they require TWO
arguments. For example the expression

3 + 4

applies the operation + to the two arguments 3 and 4. It denotes the
number 7. The arguments may themselves be complex expressions, e.g.

(3 + 4) + (5 + 6)

The operation - can be binary (two arguments) or unary (one argument),
and Pop-11 works out from the context which it is. When it is unary, as
in

- 4

or

- (3 + 5)

it produces a number by NEGATING its argument.

When it is a binary operator, as in

3 - 4

or

(2 + 1) - (2 + 2)

it subtracts the second argument from the first. So the latter denotes
the number -1.

Roughly, the rule is that if "-" occurs as part of an expression in
which it is immediately preceded by an expression, and not a comma,
semicolon, or opening bracket of any kind, then it is treated as binary
and represents a subtraction. Otherwise it is unary and represents a
negation (change of sign).

The following are all binary (i.e. subtractions)

x - y,    (33 * x) - sqrt(y),   x + y - z,  x * y - z - 1

The following are all unary (i.e. negation)

-3 + 5,   sqrt(- 22),  if x > 0 then -x else x endif

One consequence of this is that although the other arithmetical
operators can be used as normal functions, e.g.

+(3, 5),  *(9, 10) =>
** 8 90

The minus symbol will normally be interpreted as a unary negation symbol
in this sort of context, producing an unexpected result, e.g.

-(6, 3) =>
** 6 -3

which is equivalent to

6, -3 =>

or

6, 3, - =>
** 6 -3

However, according to the rule given, the following will work as a
binary negation, which may also be surprising:

6, 3 - =>
** 3

When unary negate is required, this can be specified unambiguously by
invoking the procedure negate, e.g.

3 + negate(4) * 5 =>

Compared with

3 + -4 * 5 =>

Similarly, because "nonop -" is always taken to refer to the subtraction
procedure, the name "negate" must be used when unary minus is to be
given as argument to a procedure, e.g.

maplist([ 1 2 3 4 5 6], negate) =>
** [-1 -2 -3 -4 -5 -6]

Compare using the subtraction operator concatenated with the sqrt
procedure:

define sqrt_sub = nonop - <> sqrt enddefine;

sqrt_sub(8, 4) =>
** 2.0

Or the subtraction operator partially applied to 3:

define sub_3 = nonop - (% 3 %) enddefine;

sub_3(66) =>
** 63

sub_3(5.4) =>
** 2.4

-- -- WARNING: division of integers using "/" can produce ratios

The division operator "/" when given two integers (or bigintegers) will
will not produce a decimal or ddecimal as result, but an integer (or
biginteger) or ratio. Thus

10/5 =>
** 2

10/6 =>
** 5_/3

The reason for printing out ratios in this way, i.e. with the numerator
and denominator joined by "_/" is that this will allow them to be read
in again as ratios without violating Pop-11's syntactic rules for
lexical items, mentioned briefly in chapter 1, and described fully in
REF ITEMISE

This sort of result of integer division can cause confusion if you are
used to a language which in which non-integer results of division are
automatically converted (i.e. coerced) to decimals (reals, floats). This
means that if you require such conversion you should ensure that one of
the arguments to "/" is a decimal. e.g.

10/6.0 =>
** 1.66667

or

10.0/6 =>
** 1.66667

-- Infix predicates on numbers ----------------------------------------

Besides arithmetical operations that take numbers as arguments and
produce numbers as results, Pop-11 includes various predicates for
testing properties of numbers, or relations between numbers. These
predicates all have boolean (i.e. true or false) results. The most
widely used infix predicates are:

OPERATOR PRECEDENCE DESCRIPTION
>       6       test two numbers: TRUE if first greater than second.
<       6       test two numbers: TRUE if first less than second.
>=      6       test two numbers: TRUE if first greater than or
equal to second.
<=      6       test two numbers: TRUE if first less than or equal
to second.

==      7       Exact identity (i.e. the very same object in the
machine.)
=       7       Equality: i.e. the same type of object with
equivalent contents.
/==     7       Not identical
/=      7       Not equal
==#     7       Same type of number and same numeric value.
(E.g. 8 = 8.0 is TRUE 8 ==# 8.0 false)

The rules for "=" and "/=" when the two arguments are of different types
are quite complicated. If X and Y are of different types and are
integers, bigintegers or ratios then they cannot be either "=" or "==".
If floating point numbers (decimals and ddecimals) are compared with
integers, bigintegers or ratios then they are first converted to
ddecimals and then compared. Further details are given in HELP EQUAL and
REF NUMBERS

What sort of thing is denoted by an arithmetical expression depends on
the "top level" operator. E.g. consider:

99 > (X + Y)

This takes the expression '99' and the expression '(X + Y)' each of
which may denote a number, and creates a new expression which denotes
true or false, depending on whether the first number is greater than or
less than the other. I.e. > is a binary operator, taking two numbers and
producing a TRUTH-VALUE, i.e. a BOOLEAN as a result. So

99 > 66        denotes TRUE
66 > 99        denotes FALSE

-- Recognizer predicates for number types -----------------------------

There are recogniser procedures which can be applied to any object and
will always return a boolean (true or false) result.

isinteger(ITEM)
Returns  if ITEM is a simple integer,  otherwise.

isbiginteger(ITEM)
Returns  if ITEM is a biginteger,  otherwise.

isintegral(ITEM)
Returns   if ITEM  is a  simple integer  or a  biginteger,
otherwise.

isratio(ITEM)
Returns  if ITEM is a ratio,  otherwise.

isrational(ITEM)
Returns  if ITEM  is a simple  integer, a biginteger  or a
ratio, and  otherwise.

isdecimal(ITEM)
Returns   if ITEM  is  a decimal  or a  ddecimal,
otherwise.

issdecimal(ITEM)
Returns   if  ITEM is  a  single length  decimal,
otherwise.

isddecimal(ITEM)
Returns  if ITEM is a ddecimal,  otherwise.

isreal(ITEM)
Returns  if ITEM is  any number except a complex,
otherwise.

iscomplex(ITEM)
Returns  if ITEM is a complex number,  otherwise.

isnumber(ITEM)
Returns  if ITEM is any kind of number,  otherwise.

-- Coercing numbers from one type to another --------------------------

number_coerce(NUM1, TO_NUM) -> NUM2
Produces a number NUM2 which is the number NUM1 converted to the
representation class  (i.e.  rational, single-float  decimal  or
double-float ddecimal) of the number TO_NUM.

number_coerce(3.5, 1) =>
** 7_/2

number_coerce(3.5, 1_/2) =>
** 7_/2

number_coerce(1_/2, 3.5) =>
** 0.5

-- Other arithmetic procedures ----------------------------------------

Other arithmetic procedures available in Pop-11 include the following,
most of which can be applied to numbers of all types.

abs(x)      absolute value (modulus) of x
exp(x)      exponential of x (e to the power x)
max(x,y)    the bigger of two numbers
min(x,y)    the smaller of two numbers
sign(x)     -1 if x is negative, + 1 if positive, 0 if x = 0, or 0.0
random(x)   a random integer in range 1 to x
round(x)    the integer nearest to x, unless x is complex in which
case the result is a complex number with real part and
imaginary parts both rounded.
arccos(x)   trigonometric arc cosine of angle
arcsin(x)   trigonometric arc sine of angle
arctan(x)   trigonometric arc tangent of angle
cos(x)      trigonometric cosine of angle
log(x)      natural logarithm of a number - inverse of exp
log10(num)  returns the base 10 logarithm of num
negate(x)   negation of the number (i.e. -x)
sin(x)      trigonometric sine of angle
sqrt(x)     square root of number
tan(x)      trigonometric tangent of angle

NOTE:
The trigonometric procedures use degrees, unless the variable popradians
is set TRUE. The default is FALSE (i.e. use degrees.) (This is one of a
large collection of user definable global variables controlling the
behaviour of Pop-11. See HELP POPVARS).

The variable popradians controls whether the trigonometric procedures
take arguments, or produce results in degrees or radians. We can use the
fact that "pi" is a built in constant thus:

sin(90) =>
** 0.893997

sin(pi/2) =>
** 1.0

arcsin(1) =>
** 1.5708

sin(90) =>
** 1.0

sin(pi/2) =>
** 0.027412

arcsin(1) =>
** 90.0

-- Other global variables controlling arithmetical computations -------

-- -- popdprecision

The value of this variable controls the production of results from
floating-point computations, in combination with the types of the
arguments supplied to the relevant procedure. If it is false then only
decimals (single precision floats) are produced. If it is the word
"ddecimal" then ddecimal results are produced by arithmetic operators
only if at least one of the arguments is ddecimal. If the value is
anything else (e.g. true), then a ddecimal result can be forced if at
least one of the arguments is integral or rational, even if the others
are all decimals.

In NO case is there an increase in precision of floating point
computations if all arguments are single-float decimal to start
with. The default value of popdprecision is false.

Examples:

Case 1: Only single precision results

false -> popdprecision;

dataword(sqrt(3.5d0)) =>
** decimal

dataword(sqrt(3.5s0)) =>
** decimal

dataword(3.5d0 + 3.5s0) =>
** decimal

dataword(sqrt(2)) =>
** decimal

Case 2: Double precision whenever a ddecimal is involved initially

"ddecimal"-> popdprecision;

dataword(sqrt(3.5d0)) =>
** ddecimal

dataword(sqrt(3.5s0)) =>
** decimal

dataword(3.5d0 + 3.5s0) =>
** ddecimal

dataword(sqrt(2)) =>
** decimal

Case 3: Double precision produced if either ddecimal or non-decimal
number is involved initially.

true -> popdprecision

dataword(sqrt(3.5d0)) =>
** ddecimal

dataword(sqrt(3.5s0)) =>
** decimal

dataword(3.5d0 + 3.5s0) =>
** ddecimal

dataword(sqrt(2)) =>
** ddecimal

This means that if popdprecision is non false, then the evaluation of
arithmetical expressions in which intermediate floating point numbers
are produced will sometimes create temporary ddecimal numbers that are
then discarded. As these are compound items (explained above) this can
cause garbage collections, leading to reduced speed, the price of
greater accuracy.

-- -- pop_reduce_ratios

This is normally true. Making it false prevents Pop-11's normal
behaviour in which a ratio result is always reduced to its lowest common
terms (and therefore to an integral result if the denominator becomes
1).

-- Miscellaneous operations on integers, ratios, floats

-- -- checkinteger,  gcd_n,  lcm_n

checkinteger(ITEM, LOW_INT, HI_INT)

Checks ITEM to be an integer within the range specified by lower bound
LOW_INT and upper bound HI_INT (inclusive). Either or both bounds may be
to indicate no upper or lower limit. If all conditions are
satisfied the procedure returns with no action, otherwise a mishap
occurs.

gcd_n(INT1, INT2, ..., INT_N, N) -> GCD

Computes the greatest common divisor of the all the N integers INT1,
INT2, ..., INT_N, where the number N itself (a simple integer >= 0)
appears as the rightmost argument. If N = 0, then GCD = 0; if N = 1,
then GCD = INT1.

lcm_n(INT1, INT2, ..., INT_N, N) -> LCM

Computes the least common multiple of the all the N integers INT1, INT2,
..., INT_N, where the number N itself (a simple integer >= 0) appears as
the rightmost argument. If N = 0, then LCM = 1; if N = 1, then LCM =
INT1.

-- -- destratio, numerator, denominator

destratio(RAT)   -> (NUMERATOR, DENOMINATOR)
numerator(RAT)   -> NUMERATOR
denominator(RAT) -> DENOMINATOR
These procedures return (on the stack) the numerator and denominator
parts of a rational number, either together (-destratio-), or
separately (-numerator- and -denominator-). When RAT is an integer
or biginteger, then NUMERATOR = RAT, and DENOMINATOR = 1.

-- -- Operations on floats (decimals and ddecimals)

-- -- intof, fracof, float_digits, float_precision

fracof(x)   fractional part of a decimal number
intof(x)    integer part of a decimal number, positive or negative

intof(-123.456), fracof(-123.456) =>
** -123 -0.456

float_digits(FLOAT) -> DIGITS
Returns an integer, the number of digits represented in the internal
(usually binary) floating-point format of the argument. (I.e. DIGITS
has only two possible values, one for decimals and one for
ddecimals. In all current Poplog implementations, b = 2 and DIGITS
is around 22 for decimals, 53-56 for ddecimals.) On a Sparcstation:

float_digits(1.0e0), float_digits(1.0s0) =>
** 53 22

float_precision(FLOAT) -> SIGDIGITS
Same as -float_digits-, except that the number of significant bits
in the argument is returned. This will in fact be identical to
float_digits(FLOAT), except that float_precision(0.0) = 0

-- -- float_decode, float_scale, float_sign

float_decode(FLOAT, INT_MANTISSA) -> (MANTISSA, INT_EXPO, FLOAT_SIGN)
This procedure takes a floating-point number and splits it into its
component parts, i.e. mantissa, exponent and sign. For full (gory)
details see REF NUMBERS

float_scale(FLOAT1, INT_EXPO) -> FLOAT2
This is equivalent to
FLOAT1 * 2**INT_EXPO
but is more efficient and avoids any intermediate overflow or
underflow. If the final result overflows or underflows (i.e. the
absolute value of the exponent is too large for the representation),
then  is returned. This procedure can be used in conjunction
with -float_sign- to put back together a floating-point number
decomposed with -float_decode-. That is, after

float_sign(FLOAT_SIGN, FLOAT1) -> FLOAT2
Returns a floating-point number FLOAT2 of the same type and absolute
value as FLOAT1, but which has the sign of the float FLOAT_SIGN. If
FLOAT1 is false> then FLOAT2 is returned as a 1.0 or -1.0 of the
same type and sign as FLOAT_SIGN.

For more details see REF NUMBERS

-- Complex Specific Operations ----------------------------------------

NUM1  +:  NUM2  ->  NUM3
NUM1  -:  NUM2  ->  NUM3
These two operators are the basic way of creating complex numbers.
Effectively, they both multiply their second argument by "i" (the
positive square root of -1), and then either add the result to (+:)
or subtract the result from (-:) the first argument.

+: NUM1  ->  NUM2
-: NUM1  ->  NUM2
As prefix operators, +: and -: are equivalent to unary_+:(NUM1) and
unary_-:(NUM1) respectively.

unary_+:(NUM1)  ->  NUM2
unary_-:(NUM1)  ->  NUM2
Single-argument versions of +: and -:, which multiply their argument
by i and -i respectively.

conjugate(NUM1) -> NUM2
Returns the complex conjugate of its argument. The conjugate of a
real number is itself, while for a complex number it is

realpart(NUM1) -: imagpart(NUM1)

destcomplex(NUM) -> (REALPART, IMAGPART)
realpart(NUM)    -> REALPART
imagpart(NUM)    -> IMAGPART
These procedures return the real and imaginary parts of a complex
number, either together (-destcomplex-), or separately (-realpart-
and -imagpart-). When NUM is real, then REALPART = NUM, and a zero
of the same type as NUM is returned for IMAGPART.

-- random and oneof ---------------------------------------------------

Pop-11 provides a useful (but relatively sophisticated) pseudo-random
number generator, controlled by an integer variable ranseed whose value
is changed whenever the generator is called. By re-setting ranseed to
the same initial value (e.g. 0) one can sure that the same sequence of
"random" numbers will be generated every time. If false is assigned to
ranseed then an unpredictable integer value depending on the exact time
of day will be assigned to it when the next random number is generated.

random0(NUM) -> RANDOM

Given a non-zero positive integer or floating-point number, this
procedure generates a random number of the same type, in the range:

0 <= RANDOM < NUM

where the distribution of RANDOM will be approximately uniform.

random(NUM) -> RANDOM

Same as -random0-, except that whenever the latter would return 0 or
0.0, the original argument NUM is returned instead. It can thus
be defined as

random0(NUM) -> RANDOM;
if RANDOM = 0 then NUM else RANDOM endif;

Hence the range of the result is

0 < RANDOM <= NUM

for a float, or

1 <= RANDOM <= NUM

for an integer.

Examples

repeat 10 times random(5) endrepeat =>
** 3 5 2 1 2 1 2 4 3 3

2 -> pop_pr_places;
repeat 10 times random(5.0) endrepeat =>
** 0.49 4.3 1.48 3.65 0.52 4.25 2.49 0.14 2.37 3.47

A closely related procedure is oneof, which takes a list and returns
a randomly chosen element.

repeat 10 times oneof([1 2 3 4 5]) endrepeat =>
** 5 4 5 5 4 2 4 5 3 3

Less common mathematical functions defined in REF NUMBERS include:

phase(NUM)
Returns the complex phase angle of NUM as a floating-point
quantity.

cis(REALANGLE)
Returns the float-complex number cos(REALANGLE) +: sin(REALANGLE)

arctan2(REAL_X, REAL_Y) -> REALANGLE
Computes the arctangent of REAL_Y / REAL_X, but using the signs of
the two numbers to derive quadrant information.

sinh(ANGLE)
cosh(ANGLE)
tanh(ANGLE)
These procedures compute the hyperbolic sine, hyperbolic cosine and
hyperbolic tangent of ANGLE. The result is a floating-point, or a
float-complex if ANGLE is complex.

arcsinh(NUM)
arccosh(NUM)
arctanh(NUM)
These procedures compute the hyperbolic arcsine, hyperbolic
arccosine and hyperbolic arctangent of NUM. For NUM complex, the
result is a float-complex. For NUM real, the result will be a real
float, except in the following cases:

arccosh:    NUM < 1
arctanh:    abs(NUM) > 1

For -arctanh-, it is an error if NUM = 1 or -1.

linearfit(LIST) -> (M,C)
The library LIB LINEARFIT makes available the procedure linearfit,
which takes a list of pairs of numbers representing co-ordinates of
points, works out the best straight line through the points, and
returns its slope M, and its Y-intercept C.

linearfit([% conspair(0,0), conspair(1.01, 0.98),
conspair(1.85, 2.005), conspair(3.0, 3.0) %]) =>
** 1.015095 0.009136

For vertical or nearly vertical lines it will produce an error.

-- Exercises --------------------------------------------------

1. What are the data types of each of the following?

33
33.0
8:777
"cat"
'asdf;lkj876 *+*++ '
[1 2 3 4]
33 + sqrt(-5)
123.45e3
123.45s-3

2. How would the data types of the preceding example change if
popdprecision had the value false, "ddecimal" or true ?

3. What do the following expressions denote?

33 + 3
3 + 4 * 5
(3 + 4) * 5
6 - 3.0
sign(random(20))
1.5e5
1.5e-5
2:11111

using '=>'. E.g.

6 - 3.0 =>

4. What is the effect of the variable POPRADIANS?

5. What variable can be given the value 2 to make pop print numbers
in binary notation?

6. What happens if that variable is given the value 1?

7. How can you make pop-11 print in hexadecimal form?

8. How would you represent the numbers 16, 21, 30, 35, 40

(a) in binary form?
(b) in hexadecimal form (i.e. 16:???????)?

9. Define a procedure which produces a random decimal between -1 and 1

10. Define a procedure which produces a random ratio between -10 and 10

-- Testing for equality and inequality --------------------------------

It is often necessary to use conditional imperatives, in order to
write flexible programs which do not always do the same thing. This
requires the ability to test certain conditions, to see if they are
true or false. An important class of such tests is testing for
equality or similarity.

==  test any two objects. TRUE if they are identical:
i.e. not really two objects but one and the same.
(Strict equality). In Lisp this is referred to as EQ.

=   test any two objects. TRUE if they are identical,
OR if they are of the same type with the same elements,
i.e. if they are 'similar'. In Lisp this is referred to
as EQUAL

E.g.

3 == 3      is TRUE because it's the same thing, the number 3
that's referred to on both sides.
3 == 5 - 2  is also TRUE for the same reason.

[A B C] == [A B C]  is FALSE, since they are two lists
Each time Pop-11 reads in '[ .... ]' it creates a
new list, even if there was a similar one earlier.

[A B C] = [A B C]  is TRUE, since they are two SIMILAR lists.

'A STRING' == 'A STRING'    is FALSE, because there are two strings
but
'A STRING' = 'A STRING'     is TRUE, because the two strings are
similar

Thus it is possible to have two lists or strings with the same
components, but which are not the very same object, e.g. if you type
in the string 'silly' twice.

'silly' == 'silly' =>
**

If you type in the same number twice Pop-11 will not treat the two
expressions as denoting two different objects. So 999 will always
refer to the same number. Strings and lists are different.

Words have to be treated like numbers. Pop-11 has to know about
certain words, e.g. "define", "if", "(" and to be able to recognise
new occurrences of the very same word. So words are entered in a
dictionary when they are first read in, and if an expression
denoting a word with the same characters is read in later, then
instead of creating a new object Pop-11 finds the same word in its
dictionary and re-uses that.

Thus, words, unlike strings, are 'standardised' in a dictionary, so
that you cannot have two different words with the same characters. If
you attempt to type in a second one, Pop-11 will find the original in
its dictionary, and assume you wanted to refer to it. So both the
following are TRUE:

"CAT" == "CAT" and  "CAT" = "CAT"

Writing two expressions on either side of an equality operation
produces a new expression, which denotes a truth-value, TRUE or
FALSE. In other words = and == each take two arguments and produce
one BOOLEAN result.

-- Bitwise (Logical) integer operators --------------------------------

Pop-11 provides a collection of operations for manipulating integers
considered as bit patterns. In order to see which bits are involved in
a positive integer, use the pr_binary procedure defined above, e.g.

pr_binary(-100);
1100100

The rightmost bit corresponds to bit 0, and if there are N+1 bits the
Nth bit is the leftmost one thus printed, except that negative numbers
conceptually have 1 bits extending indefinitely to the left of the sign
bit representation. In all the following definitions remember that the
lowest value for N is 0, not 1.

-- -- Bit accessing procedures for integers

testbit(INT, N) -> BOOL
This procedure tests the bit at position N in the integer INT
returning true for 1 and false for 0. It has an unusual updater,
which also returns a result:

BOOL -> testbit(INT, N) -> NEWINT
This clears or sets the N'th bit of INT to 1 if BOOL is true or 0 if
false, and the returns NEWINT as the resulting integer.

integer_leastbit(INT) -> N
Returns the bit position N of the least-significant bit set in the
integer INT. E.g.
integer_leastbit(4), integer_leastbit(5) =>
** 2 0

integer_length(INT) -> N
Returns the length in bits of INT as a two's-complement integer.
That is, N is the smallest integer such that

INT  <   ( 1 << N),   if INT >= 0
INT  >=  (-1 << N),   if INT <  0

Put another way: if INT is non-negative then the representation of
INT as an unsigned integer requires a field of at least N bits;
alternatively, a minimum of N+1 bits are required to represent INT
as a signed integer, regardless of its sign.

integer_bitcount(INT)
Counts the number of 1 or 0 bits in the two's-complement
representation of INT. If INT is non-negative, N is the number of 1
bits; if INT is negative, it is the number of 0 bits.

-- -- Infix and prefix bitwise (logical) operators

OPERATOR  PRECEDENCE  DESCRIPTION
&&      4       Logical and of bits in two integers

&&~~    4       Logical and of first argument and negation of
second. (Useful for clearing bits.)

||      4       Logical "inclusive or" bits in two integers.

||/&    4       Logical "exclusive or" of bits in two integers.

&&/=_0  6
&&=_0   6
These two operators provide the same results as the
boolean expressions

INT1 && INT2  /==  0
INT1 && INT2  ==   0

but are more efficient and avoid producing intermediate
results.

-- -- Unary bitwise negation ~~

The unary operator ~~ has precedence 4
It produces the logical complement of its argument, i.e. there is a
1 in the result for each bit position for which the argument has 0.
It is always true that ~~ INT = -(INT + 1)

-- -- Bitwise (logical) shift operators

OPERATOR  PRECEDENCE  DESCRIPTION
I << N     4       Shifts the bits in I N places left (or -N places
right if N is negative).

I >> N     4       Shifts the bits in I N places right (or -N places
left if N is negative).

integer_field(SIZE, POSITION) -> ACCESS_P
This procedure, described fully in REF NUMBERS can be used to create
very efficient procedures for accessing and updating sub-bitfields
within integers, and provides a more convenient (and more efficient)
way of manipulating such fields than by masking and shifting with
the operators && and >>, etc.

-- Iteration over numbers ---------------------------------------------

-- -- for num from ... by ... to ... do ... endfor

There are many ways of expressing iteration over sets of numbers in
Pop-11, including using repeat ... endrepeat, while ... endwhile, and
until ... enduntil.  However, it is usually "for" loops that are most
convenient. These allow a variable to take successive values in a series
of numbers defined by repeatedly adding or subtracting a fixed amount.

The basic syntactic form provided to support this kind of iteration is
the following (where line-breaks are equivalent to spaces):

for  from  by  to  do

endfor;

However the "from" and "by" components may be omitted where the number
in question is 1. So the following forms are also permitted:

for  from  to  do  endfor
(Default: "by 1")

for  by  to  do  endfor
(Default: "from 1")

for  to  do  endfor
(Defaults: "from 1", "by 1")

Examples of arithmetical for loops are:

vars x;
for x to 10 do spr(x) endfor;
1 2 3 4 5 6 7 8 9 10

for x by 0.5 to 5 do spr(x) endfor;
1 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0

for x by 1/3 to 5 do spr(x) endfor;
1 4_/3 5_/3 2 7_/3 8_/3 3 10_/3 11_/3 4 13_/3 14_/3 5

for x from 1 to 6 do spr(x) endfor;
1 2 3 4 5 6

for x from 19 by -1 to 8 do spr(x) endfor;
19 18 17 16 15 14 13 12 11 10 9 8

for x from -5 by -0.6 to -9 do spr(x) endfor;
-5 -5.6 -6.2 -6.8 -7.4 -8.0 -8.6

For loops may be nested. For example, to make a list of all possible
pairs of numbers between 3 and 5 do

vars x, y;
[% for x from 3 to 5 do
for y from 3 to 5 do
[^x ^y]
endfor
endfor %] =>
** [[3 3] [3 4] [3 5] [4 3] [4 4] [4 5] [5 3] [5 4] [5 5]]

-- -- Using fast_for

When it is known that the values of the loop variable and the increment
or decrement will all be integers, then it is permissible to use the

vars x;
fast_for x from 1 by 300 to 10000 do x endfor =>
** 1 301 601 901 1201 1501 1801 2101 2401 2701 3001 3301 3601 3901
4201 4501 4801 5101 5401 5701 6001 6301 6601 6901 7201 7501 7801
8101 8401 8701 9001 9301 9601 9901

Using this form will eliminate some of the run-time checks that are
otherwise required. However, it is risky in that errors may not be
detected. (See HELP EFFICIENCY).

-- -- Iterating over non-arithmetical progressions

For sequences of numbers not defined by constant intervals it may be
convenient to use the following form:

for  step  till  do  endfor

For example to produce a list of the powers of 2 less than 10000 do

vars x;
[% for 2 -> x step x * 2 -> x; till x >= 10000 do x endfor%] =>
** [2 4 8 16 32 64 128 256 512 1024 2048 4096 8192]

-- Using external mathematical libraries ------------------------------

For some programs it is desirable to use existing mathematical libraries
written in C or Fortran or other languages, e.g. the NAG libraries.

can save work duplicating code, and also produce faster performance than
rewriting the programs in Pop-11.

The mechanisms for linking in external programs are described in

REF EXTERNAL
REF EXTERNAL_DATA
REF DEFSTRUCT
These files describe the basic mechanisms for linking in and
communicating with "external" programs.

HELP EXTERNAL
HELP NEWEXTERNAL
HELP NEWC_DEC
HELP FORTRAN_DEC
These files describe higher level language-specific tools
for managing external programs.

-- CHAPTER.6: LIST PROCESSING IN POP-11

In Chapter 1 an example of the use of lists to represent a collection of
items of information about rooms was used to introduce a number of
features of the language Pop-11. We have occasionally used lists to
illustrate other points in preceding chapters. This chapter explains in
more detail why lists are important, how they are implemented and how
they can be used.

The chapter will provide more general information on syntax for
constructing lists, together with an overview of the basic procedures
available for operating on lists including the two list-pattern matchers
provided in Pop-11.

-- On knowing about lists ---------------------------------------------

There are several things a Pop-11 user needs to know about lists:

What they are used for
How to construct them
How to extract information from them
How they are represented in the machine
How dynamic lists and static lists differ
How to compare them or test them to see whether they satisfy
certain conditions relevant to deciding what to do.
Which facilities are available for manipulating lists
How to design your own facilities for manipulating lists
How to optimise your list-processing programs

A comprehensive overview of all these topics would require a whole book.
This chapter, introduces the basic ideas and gives some examples of how
to use them.

-- Why use lists? -----------------------------------------------------

For work in Artificial Intelligence, and many other applications where
we need to represent data in a variety of forms, lists are a very
useful data type, partly because it is possible for two lists to share
common sublists, partly because it is possible for lists to change their
size by being extended in the middle or at either end, and partly
because there is a way of representing them that is simple and flexible.

In Lisp and closely related languages, such as Scheme and T, it is also
the case the lists can represent interpreted procedures: this is
sometimes useful, though not as useful as the early inventors of Lisp
supposed it would be. Pop-11 has a different philosophy regarding
procedures and some of the things that a Lisp programmer would do by
building a list and interpreting it, a Pop-11 programmer would do by
using partial application to build closures that can be run (as
described in chapter 4).

Also, the incremental compiler provided in Pop-11 allows lists of text
items representing procedure definitions to be compiled at run time.
For example

vars name = "silly", func = "last", list = [a b c];
popval([define ^name; ^func(^list); enddefine;]);

creates a new COMPILED procedure called silly, which can be run like any
other procedure and then applies last to [a b c]

silly() =>
** c

This is sometimes useful, in writing programs that create new programs.

However, Pop-11 does not provide the equivalent of Lisp's EVAL, which
interprets Lisp procedure definitions.

Nevertheless lists play a very important role in representing
information in many Pop-11 programs.

-- -- Lists can contain a mixture of elements of any type in Pop-11

Lists can be used to represent or store many kinds of information. In
Pop-11, like most AI languages, lists can contain any type of object,
including, for instance, numbers, words, procedures, and other lists.
Moreover, the same list can contain a mixture of items of different
types. This is impossible to achieve in strongly typed languages,
including even some languages with a polymorphic type system (e.g. ML).

This generality has a number of implications. First of all it is
possible conveniently to use lists to represent all kinds of information
in a common format, especially information that changes its structure
while a program is running. Moreover, because one does not need to use
different datastructures for different kinds of information it is
possible to produce a collection of very general re-useable procedures
that work on lists containing different kinds of data. The Pop-11
"pattern matcher", described below, is an example of a very powerful
general purpose utility procedure for operating on many types of lists.
Another example is the Pop-11 database package, based on the matcher.

Being able to use such "generic" procedures with lists of different
kinds can simplify program development and lead to more compact and
robust programs.

-- . Illustrating generality: isinlist

To illustrate here is a simple example. In Pop-11 it is possible to
provide a single "isinlist" procedure, which takes an item and a list
and returns a boolean result, which is true if the item is in the list
otherwise false, as follows:

define isinlist(target, list) -> found;

lvars item;
for item in list do
if item = target then
true -> found;
return();
endif
endfor;
false -> found
enddefine;

This procedure is very general, insofar as it can then be used on lists
of numbers, words, strings, lists, etc. in any combination, as it makes
no assumptions about the types of the values of the variables "target"
and "list", except that the value of "list" should be a list: if not a
run time error will occur, because it uses the list iteration construct.
Although it assumes that the second argument will always be a list, it
makes no assumptions about the contents of the list. In some languages,
such as Pascal it would be necessary to produce a different version of
the procedure for each type of list, and it would not be possible to mix
items of different types in one list.

The versatile behaviour of isinlist can be illustrated thus:

vars person_data =
[name joe age 23 wife mary salary 20000 children [sue fred]];

isinlist("mary", person_data) =>
**

isinlist(20000, person_data) =>
**

isinlist("fred", person_data) =>
**

isinlist([sue fred], person_data) =>
**

(In fact the built in Pop-11 procedure "member" behaves like isinlist,
so it is not necessary for users to define isinlist. Try replacing
"member" in all the above examples.)

There are many other examples of re-usable general procedures that
operate on lists no matter what their contents. For example, applist,
maplist, syssort, the concatenator <>, and other procedures described
below.

The library procedure assoc can create an associative memory made of
two-element lists, no matter what the contents of the lists are.

vars person =
assoc([[name fred]
[sex male]
[age 30]
[kids [sue tom dick]]]);

;;; person is now an association mechanism.
person("age") =>
** 30
person("age") + 1 -> person("age");
person("age") =>
** 31
person("kids") =>
** [sue tom dick]

-- Lists vs other representations -------------------------------------

How to choose between the use of lists or other means of representation
is not always obvious: it can take many years of experience to make good
decisions, weighing up such criteria as ease of program design, ease of
testing, ease of long term maintenance, compactness, speed, generality.

Sometimes the reason for using a particular representation is simply
that there already exist utilities that do the job one needs and one
does not wish to have to rewrite them.

Although in principle lists can be used for every type of data, it is
sometimes useful on grounds of compactness of data, or speed of access,
or more useful run-time checking to use a more specific data-type for a
particular problem.

When more specialised representations are required, Pop-11 provides
records, vectors, arrays, strings, properties and user defined record
classes and vector classes. (See the list of data types in Chapter
2.)

Moreover, the object-oriented extensions to Pop-11 (Objectclass and
Flavours) provide additional means of structuring large programs.
See Chapter 8 below for a brief introduction to Objectclass.

-- Lists in AI --------------------------------------------------------

A central thesis of much work in Artificial Intelligence is that certain
sorts of computational processes provide a good way to represent many of
the processes we call thinking, seeing, reasoning, speaking, learning.
But what sorts of computations? Not only the manipulation of numbers
found in much scientific and engineering computation, but also a wide
variety of non-numerical symbol manipulations. Intelligence seems to
involve the manipulation of many kinds of symbols that can be used to
store information about many kinds of things and their properties and
relationships.

The role of symbolic and non-symbolic processing is the subject of
considerable debate among those interested in how intelligent systems
work. For now, we shall avoid getting embroiled in such debates and
merely point out that for many purposes where symbolic manipulation is
useful, lists can provide a powerful and general representation. They
can also be used for programs operating on numerical data, though
in that case some other representation will often be more efficient and
more natural, e.g. arrays or vectors.

-- Constructing lists in Pop-11 ---------------------------------------

The simplest way to construct a list is to use square brackets. But
there are several others:

-- -- Lists are constructed using [    ]

These "list constant brackets" may contain text items, i.e  words,
numbers strings, lists, or anything else. E.g.:

[ A B C D]            is a list of four words
[1 cat 2 dog 3 pig ]  is a list of six items.
[string 'a short string' 66]
is a list with a word a string and a number.

[]  is the empty list. There's more on this below.

List brackets may also be used to construct lists which contain lists,
E.g.:

[ [1 2]  [3] 4 ]

is a list with two lists of numbers and one number. It contains exactly
three elements, of which the first contains two elements.

A list can also contain vectors, signified with the vector brackets {  }
which themselves can enclose further lists or vectors to any depth:
e.g. (using more spaces than necessary, for clarity):

[ a b { c d [ e { f } ] } [ g h ] ]

This is a list containing four items: two (quoted) words "a" and "b", a
vector { c d [ e { f } ] } and a two element list [ g h ].

-- -- List brackets quote their contents

The words in a list are by default quoted, apart from the list and
vector brackets, which signify embedded lists and vectors.

So even if the words are Pop-11 identifiers, their values are not
inserted in the list, just the words themselves. (This is unlike the
convention in Lisp, where, by default, the values are inserted.)

Example:

[true false if + * then sqrt ] =>
** [true false if + * then sqrt]

-- -- Unquoting using ^ and %

In order to get the contents of a list (or vector) expression evaluated,
or unquoted, it is possible to use either ^ or matching pairs of % ... %
as in this deliberately confusing example

vars x = "cat", cat = "x";

[x cat ^x ^cat] =>
** [x cat cat x]

which is equivalent to each of

[x cat %x% %cat%] =>
[x cat %x, cat%] =>
[% "x", "y", x, cat %] =>

Another example would be

vars n1 = 5, n2 = 7;
[the sum of n1 and n2 is %n1 + n2%] =>
** [the sum of n1 and n2 is 12]

So, in order to insert the value of a single variable, it is simplest to
use ^variable, whereas pairs of percents % ... % may be more
appropriate for longer expressions to be evaluated.

NOTE: ^ cannot cannot be used outside a list or vector expression.
However, % has an additional use in forming closures, using partial
application, as described in Chapter 4, and HELP PERCENT

Between the percent signs in a list or vector expression the normal
syntactic rules for Pop-11 apply, so that, for example, expressions must
be separated by commas, and in order to quote a word the word quote
symbol '"' must be used.

-- -- ^( ... ) is equivalent to % .... %

For historical reasons, the use of the percent symbols is equivalent
to the use of ^ followed by a parenthesised expression. Thus, the
last two examples could be written

[ ^( "x", "y", x, cat )] =>
[the sum of n1 and n2 is ^(n1 + n2)] =>

There is no difference in meaning or efficiency between ^( ... ) and
% ... %.

If embedded list or vector expressions are used inside these "unquoted"
portions of a list, then by default they too quote their contents,
unless % or ^ is used to unquote, e.g.

[% [two words], [% n1, "a"%], [% n2 % b c] %] =>
** [[two words] [5 a] [7 b c]]

is a list of three lists, whose contents depend on the values of the
identifiers n1 and n2, but treats all other words as quoted.

The symbol "%" can occur anywhere in a list expression (or vector
expression). But it must occur in pairs. Roughly speaking, in a list the
first occurrence of each pair means: "switch from quoting to non-quoting
mode", and the second occurrence means "switch from non-quoting to
quoting mode". In non-quoting mode variables are replaced by their
values and any procedures are run and their values are inserted in the
list instead of the names of the procedures being put in the list.

-- -- Loops can occur in unquoted portions of a list

There is no restriction at all on the sequence of expressions that can
occur in the unquoted portion of a list. The Pop-11 instructions are
run, and any results produced that are left on the stack will be
incorporated in the final list.

So for example, it is possible to use a loop between % .. % to create a
list of numbers.

vars n;
[% for n from 1 to 20 do n endfor % ] =>
** [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]

Similarly the contents of the list, may be conditional on something
else, as in

[The list was % if n > 15 then "big" else "small" endif % ] =>
** [The list was big]

-- WARNING lists in procedures are not "constants" --------------------

An expression using the list (and vector) brackets, and containing no
occurrences of the un-quoters "^", "^^" or "%" may LOOK as if it
represents a constant object, in the way that a word expression, e.g.
"cat" or a string expression does e.g. 'the cat'.  However, in Pop-11 an
expression like

[ a b { c d [ e { f } ] } [ g h ] ]

compiles into a collection of instructions to CREATE a list of words,
vectors and lists. Although the very same words are used each time (they
are are stored in the Pop-11 dictionary for that purpose), the other
structures are recreated each time the procedure is run. So for example
if you define a procedure to return what looks like a constant list, it
will return a new copy each time, thus:

define a_list();
[a list]    ;;; create a list and leave on stack
enddefine;

;;; Use it to create a list
vars x1 = a_list();
x1 =>
** [a list]

;;; create another list using the same procedure
vars x2 = a_list();
x2 =>
** [a list]
;;; test for equality
x1 = x2 =>
**
;;; test for identity
x1 == x2 =>
**

So although the different lists returned by the procedure are = to each
other (i.e. they are of the same type and they contain objects that are
= to each other) nevertheless they are not == to each other. They are
not the same object, even though they have the same structure and
contain objects that are = to each other.

Similarly two apparently identical list expressions will create copies
of each other but not identically the same object:

[a list] = [a list] =>
**

[a list] == [a list] =>
**

Contrast the case of words, which are identical if they look the same:

"list" == "list" =>
**

Similarly, if a list is assigned to a variable outside a procedure then
as long as nothing new is assigned to the variable, it will always point
to the same list.

vars x2 = [another list];

x2 == x2 =>
**

For more on the difference between "=" and "==" see HELP EQUAL

-- -- Creating a truly constant list expression

A consequence of all this is that a procedure that uses a list
expression will create a new copy each time it runs, even though this
may not be strictly necessary, and this can cause more garbage
collections to occur than the program really needs. (The garbage
collector is described briefly in Chapter 2). This will happen if you
define a procedure that uses the pattern matcher and includes something
like

if list matches [room ?name ?len ?width ?height] then

In such cases the pattern to the right of "matches" will be recreated
on every execution of the procedure.

For many programs where speed is not crucially important this will not
matter as the Pop-11 garbage collector is very fast, and the creation of
unnecessary temporary structures will not make very much difference.
Where it does matter, there are two things you can do to ensure that
exactly one list is created and then re-used.

-- . Using lconstant

If inside a list you declare a variable using lconstant, then you MUST
initialise it, and the expression to initialise it will be evaluated
only once, at compile time, and thereafter the same result will be used
on every call of the procedure. E.g.

define the_list();
lconstant list = [the list];
list
enddefine;

the_list() =>
** [the list]

the_list() == the_list() =>
**

If "lvars" or "vars" had been used instead of "lconstant" that last
identity comparison would have been false.

-- -- using #_< ... >_# to evaluate an expression at compile time

Another way to get a truly constant constant list is to use these
brackets which cause their contents to be evaluated once, at compile
time and then the result is re-used each time the procedure is run.

define another_list();
#_< [another list] >_#
enddefine;

another_list() =>
** [another list]
another_list() == another_list() =>
**

So you can use these brackets in expressions like

if list matches #_< .... >_# then

However this will NOT work properly if the list expression includes
items whose values are not known until the procedure is actually
running, e.g. list or vector expressions containing any of

^  ^^  % ... %

as described above.

-- -- WARNING constant lists can cause strange behaviour

If you use a truly constant list, and your program changes that list
then the change will be remembered between invocations of the procedure,
and the list will then not be a constant.

Form example, on each call of this procedure, it will return the value
of item, which is got from the head of the stored list.

define counter() -> item;
lconstant list = [0];

list(1) -> item;        ;;; get the first item.
item + 1 -> list(1);    ;;; increment the stored value
enddefine;

counter() =>
** 0
counter(), counter(), counter() =>
** 1 2 3

If "lconstant" were replaced by "lvars" then on every execution the
procedure would construct a new list containing [0], and would therefore
always print out the same result.

If a constant list is returned as a result, and then altered OUTSIDE the
procedure that produced it, this will change the future behaviour of the
procedure.

define announce() -> list;
lconstant list = [0 is a number];
enddefine;

announce() =>
** [0 is a number]

But if the result is tampered with....

vars x = announce();
999 -> x(1);
x =>
** [999 is a number]

then that "corrupts" the procedure:

announce() =>
** [999 is a number]

Some of the issues relating to constant lists are described in the
online file HELP EFFICIENCY. The are two dangerous procedures described
in REF sys_grbg_list and sys_grbg_destpair which explains how a list
once created can be returned to the "free" store so that it can be
re-used without creating unnecessary garbage collections. These
procedures are dangerous and should only be used by very experienced
programmers who know how to make sure when it a list really cannot be
used again, and therefore can safely be returned to the free store.

It is precisely because that sort of thing can be very difficult to
determine that Pop-11 uses an AUTOMATIC garbage collector, which is very
much safer.

-- Concatenating lists using <> ---------------------------------------

If two lists are to be joined together, the general-purpose Pop-11
concatenator can be used, as in

vars list1 = [a b c], list2 = [d e f];
list1 <> list2 =>
** [a b c d e f]

list1 <> list2 <> list1 <> list2 =>
** [a b c d e f a b c d e f]

-- Merging lists using the double up-arrow ----------------------------

A more flexible facility than <> is the use of ^^ which allows the
contents of one list to be spliced into another at any location, whereas
<> allows only joining lists "end on". For example:

vars list1 = [a b c], list2 = [d e f];

[1 2 ^^list1 3 4 ^^list2 ] =>
** [1 2 a b c 3 4 d e f]

The same list can be spliced in at several different points:

[ ^^list1 x y z ^^list1] =>
** [a b c x y z a b c]

It is possible to use an arbitrary Pop-11 expression that evaluates to a
list after ^^ provided that it is enclosed in parentheses.

[a set of numbers ^^( [% 1 + 2, 3 + 4, 5 + 6%])] =>
** [a set of numbers 3 7 11]

Compare the use of ^ without the embedded list brackets and % symbols:

[a set of numbers ^( 1 + 2, 3 + 4, 5 + 6)] =>
** [a set of numbers 3 7 11]

So inside a list, the form

^^( [%  %] )

is exactly equivalent to

^(  )

except that the former wastefully creates a temporary list and then
discards it after its contents have been spliced into the final list.
so it is worth using ^^ only when a list already exists, although it may
be necessary to use a complex expression to access it, e.g.

vars list = [a [b c d] e f];
[another list with : ^^(list(2)) ] =>
** [another list with : b c d]

Here list(2) was used to get at the second element of list.

If the above had used ^ instead of ^^, the result would have been:

[another list with: ^(list(2)) ] =>
** [another list with : [b c d]]

In other words ^^ removes a layer of list brackets that ^ will leave.
The prefix "^^" can be thought of as meaning "remove the list brackets".

If the value is not a list, an error will result.

vars x = 99;
[a b c ^^x] =>

;;; MISHAP - LIST NEEDED
;;; INVOLVING:  99

-- Lists are a derived data-type --------------------------------------

-- . Pairs are the primitive datatype used: conspair, front, back

LISTS in Pop-11 are built out of a data type called PAIRS, which are
two-element records. Pairs can be created using the procedure conspair.

vars pair1 = conspair(3, "cat");

pair1 =>
** [3|cat]

Note how pairs are printed almost like lists, except for the vertical
bar to indicate that they are not two element lists.

The built in system procedures front and back can be used to access or
update their elements. E.g.

front(pair1) =>
** 3

"dog" -> back(pair1);
pair1 =>
** [3|dog]

Pairs can be chained together, e.g. by creating a new pair whose back is
the old one.

vars pair2 = conspair(2, pair1);
pair2 =>
** [2 3|dog]

Notice how the printing procedure starts printing pair2 as if it were a
list,  that is a chain of pairs, then suddenly it finds that the list
ends in a pair that has a word as its back, rather than another pair or
the special end of list object [], so it indicates that it's not a
proper list, by using the vertical bar again.

-- -- destpair(pair) -> (pair_front, pair_back)

The procedure destpair, when given a pair, puts both the front and the
back on the stack. So using destpair can sometimes be more efficient
than first calling front then back.

destpair(pair1) =>
** 3 dog

The front and the back of the second pair created above, pair2, can also
be accessed in one Pop-11 instruction, using destpair:

destpair(pair2) =>
** 2 [3|dog]

For example, a loop doing something to every item in a chain of pairs
might have:

while ispair(chain) do
destpair(chain) -> (item, chain);
.... instructions involving item .....
endwhile;

while ispair(chain) do
front(chain) -> item;
.... instructions involving item .....
back(chain) -> chain;
endwhile;

-- . A chain of pairs ending in [] is a list

The chain of two pairs created above involving pair1 and pair2 is not
yet a proper list, since every list must end with the empty list [] as
the back of the final pair (except for dynamic lists, described below.)

vars
pair1 = conspair("b", "c"),
pair2 = conspair("a", pair1);

So neither pair1, nor pair2 is a proper list, as is indicated by the way
they are printed, e.g.:

pair2 =>
** [a b|c]

If we now change the back of pair1, by assigning [] to it, we'll get
a proper list:

[] -> back(pair1);
pair1 =>
** [b]

and this has also changed pair2 into a properly terminated list.

pair2 =>
** [a b]

NOTE: The empty list [] is a special, unique object, with its own
dataword (like termin and popstackmark).

dataword([]) =>
** nil

The system identifier "nil" can also be used to refer to the empty list:

nil =>
** []

nil == [] =>
**

conspair(3, conspair(4, nil)) =>
** [3 4]

-- -- List expressions are "syntactic sugar"

From this, it should be clear that the list expression [a b] is actually
just "syntactic sugar" for the expression:

conspair("a", conspair("b", []))

and [a ^x b] is syntactic sugar for

conspair("a", conspair(x, conspair("b", [])))

and [a %x + y% b] is syntactic sugar for

conspair("a", conspair(x + y, conspair("b", [])))

So, inside a list expression, words are quoted by default and "^" or "%"
is used to unquote them, whereas outside a list words are by default not
quoted and """ is used to quote them. The same applies to vector
expressions using { ... }

Exercise: What is [the cow is brown] syntactic sugar for?

-- -- Recursively chaining down list links

Because all lists end in the unique object [], there are many programs
that chain down a list made of pairs by assigning the first pair to a
variable, then the second pair, then the third, and so on, stopping only
when it is found that the variable points to [].

For example here is a recursive procedure to copy a list (which could be
written more compactly but would be less clear):

define copy_list(oldlist) -> newlist;
lvars newtail ;

if oldlist == [] then
[] -> newlist
elseif ispair(oldlist) then
;;; recursively copy the back of the list
copy_list(back(oldlist)) -> newtail;
;;; and create a new list using the old front
;;; and the new tail
conspair(front(oldlist), newtail) -> newlist
else
mishap('LIST NEEDED', [^oldlist])
endif
enddefine;

copy_list([a b c d]) =>
** [a b c d]

Recursive procedures can often be understood more easily if traced,
using the trace mechanism described in Chapter 4 (or HELP TRACE). So
try running the previous command after first doing:

trace copy_list

Note that the Pop-11 system procedure copylist does exactly what
copy_list does, so there's no need for the user to define copy_list.

-- -- Recursing down the front and the back of a "tree"

Note also that if there were an embedded list, it would not be copied:
it would reappear in the new list, as in [a b [c d] e]. Lists like
this have a "tree" structure, as shown by the boxes diagrams below.

Complete copying of a tree can be achieved by a "doubly recursive"
procedure, which copies list elements that are lists as well as copying
the "top level" list.

For example, here's a doubly recursive version, which simply leaves its
results on the stack instead of using an output local variable:

define copy_tree(tree);
if ispair(tree) then
;;; copy the front if its a pair, otherwise use it, and
;;; then put the result in a new pair, with a copy of the
;;; old back
conspair(
if ispair(tree) then copy_tree(front(tree))
else tree endif,
copy_tree(back(tree)) )
else
;;; just return the item that is not a pair
tree
endif
enddefine;

vars tree = [[a 1 2] [b 3 4] [c [x y] 5 6] d];
copy_tree(tree) =>

Running that example with copy_tree traced, will show all the recursive
calls.

We turn now to showing in more detail how the static lists are actually
represented.

-- -- Numeric subscripts and lists

We have already seen on numerous occasions that lists can be treated as
if they were one dimensional arrays, whose elements can be accessed via
numerical subscripts, starting from 1.

vars list = [a bird in the hand];

list(2) =>
** bird

"fish" -> list(2);
list(2) =>
** fish

list =>
** [a fish in the hand]

If the number is too small or too large an error will result.

list(8) =>
;;; MISHAP - BAD ARGUMENTS FOR INDEXED LIST ACCESS
;;; INVOLVING:  8 [a fish in the hand]
;;; DOING    :  compile ....

-- -- Iterating down list links

Here is a rather different program that uses iteration rather than
recursion. It searches down the list links until if finds a target
element and then returns a copy of the rest of the list, starting from
the target.

define tail_list(target, oldlist) -> newlist;

oldlist -> newlist;

repeat
if newlist == [] then
mishap('TARGET NOT IN LIST', [^target ^list])
else
if front(newlist) = target then
return();   ;;; result is newlist
else
;;; get next link in the list
back(newlist) -> newlist
endif
endif
endrepeat
enddefine;

tail_list("cat", [The black cat sat on the mat]) =>
** [cat sat on the mat]

Exercise: re-write that procedure using the for loop format:

for  on list do .... endfor

-- Why use "hd" and "tl" instead of "front" and "back" ?

-- . The need to hide implementation details

We have seen that a list is actually a chained collection of pairs. But
facilities for manipulating lists are provided, which conceal from the
user the details of how they are represented in the machine. For example
Pop-11 provides special syntax using the list brackets [ ... ] together
with "^", "^^" and "%" for creating lists by specifying what they should
"look like", without worrying about their implementation at a lower
level.

Additional facilities provided that "hide the implementation details"
are the following procedures:

matches, copylist, applist, maplist, and the list concatenator <>.

In addition there are looping constructs, e.g. using

for  in  do ... endfor
foreach  in  do ... endforeach

which also make it convenient to manipulate lists without knowing how
they are implemented. (The faster version: "fast_for ... endfast_for"
described in REF FASTPROCS) assumes that there are no dynamic lists
(described below), and therefore does not do as much checking.)

For the sake of efficiency it is sometimes useful to know how lists are
implemented and to use the procedures conspair, destpair, front and back
as in previous examples. This would have the disadvantage that if the
implementation were ever to change and something other than simple
chained pairs were used for lists, then programs that used these
procedures would stop working.

In fact, in some versions of the Pop language that is already the case,
because Pop2, Pop10 and Poplog Pop-11 support what are called "dynamic"
lists, which have a slightly different implementation from the lists
described so far, which are all "static" lists. These will be described
below.

Meanwhile, the main justification for using hd, tl, and dest can be
thought of as being to "hide the implementation details", which allows
the implementation to be changed.

Note: "hd" and "tl" in Pop-11 correspond to "CAR" and "CDR" in LISP.

-- -- using :: instead of conspair

For this reason it is desirable to use something other than conspair,
which is guaranteed always to give a list. An infix list constructor
operator is provided, namely "::". It's infix precedence is 4. It is
similar to conspair, except that it will complain if its second argument
is clearly not a list.

"a" :: [b c d] =>
** [a b c d]

conspair("a", "b") =>
** [a|b]

"a" :: "b" =>
;;; MISHAP - LIST NEEDED
;;; INVOLVING:  b
;;; DOING    :  :: (etc.)

Warning:
Unfortunately, for historical reasons, "::" associates to the left
rather than to the right, so parentheses are needed to produce a flat
list, as with conspair:

1 :: (2 :: (3 :: [])) =>
** [1 2 3]

Without the parentheses, it is equivalent to

((1 :: 2) :: 3) :: [] =>

And the embedded invocation of "1 :: 2" will produce a LIST NEEDED
error.

For this reason, when constructing a list from a number of known items
it is usually simpler and clearer to use the "syntactic sugar" of list
expressions than to use multiple occurrences of "::", e.g.

[1 2 a ^x ^y]

1 :: (2 :: ("a" :: (x :: (y :: []))))

-- -- The difference between :: and <>

It is important to be aware of the difference between the list
constructor :: and the list concatenator <>.

The procedure :: takes a potential list-head and a potential list-tail
(which must already be a (possibly empty) list and makes a new list with
that head and tail (and without copying the tail). Thus the first
argument of :: is the first element of the new list.

By contrast the concatenator <> takes a potential initial segment of a
list and a potential final segment, and makes a new list containing
those segments. The first argument of <> is not the first ELEMENT of the
new list: though its elements are the initial elements of the new list.

The difference can be interested with the following two examples, where
both operators are applied to two lists:

[a b c] :: [d e f] =>
** [[a b c] d e f]

[a b c] <> [d e f] =>
** [a b c d e f]

The first example produces a list of four items, the second a list of
six items.

Each could be defined in terms of the other. To illustrate we can use
<> to define an infix operator like :: called :+:, and we can use :: to
define an infix operator like <> called <+>. In each case we give the
infix precedence as an integer following "define".

define 4 :+: (item, list);
[^item] <> list
enddefine;

;;; Test it:

"a" :+: ("b" :+: []) =>
** [a b]

This is wasteful because each invocation of :+: creates a temporary list
to give to <>, which is then copied and discarded.

We can also define a concatenator in terms of ::, though this time we
use recursion. The idea is that in order to create list1 <> list2 we
first create tl(list1) <> list2, then use hd(list1) and :: to finish the
job. The recursive call on the tail of list1 will, of course, use ::
repeatedly. When it gets down to list1 == [], the concatenator simply
needs to return list2, since [] <> list2 = list2.

define 5 <+> (list1, list2);
if list1 == [] then list2
else
hd(list1) :: (tl(list1) <+> list2)
endif
enddefine;

;;; Test it:

[a b c] <+> [d e f] =>
** [a b c d e f]

Notice that list2 is used exactly as it is: it is not copied. However,
:: creates new list links for the elements of list1.

-- Diagrams showing static lists represented as pairs -----------------

This section shows how (non-dynamic) lists are represented as chained
collections of pairs linked together. It is based on the Poplog file
TEACH BOXES, originally written by Steve Hardy.

Consider the following set of instructions in Pop-11. We first explain
what each one means to a user, and then present a graphical
representation of the effects on the computers memory.

vars x;

This puts an entry for the word "x" in the Pop-11 dictionary (unless it
was already there), and, in the current section, associates it with an
ordinary identifier record (identprops = 0). The "valof" cell in the
record originally has an  record as its contents.

.---.
x! *-+---->
.---.

"a" -> x;

This creates an entry for the word "a" in the Pop-11 dictionary (unless
it was already there) and stores a pointer to the word in the valof cell
of the identifier record associated with "x"

Dictionary     Identifiers in
Current section

.========.
----> |ident * |
.======+=.
|
<-----------+

------>....

Here the notation *----> is used to represent a "pointer" where the "*"
indicates a bit pattern that gives the address in (virtual) memory of
the item at the other end of the arrow. When a memory cell contains a
pointer to the word "a" we shall sometimes abbreviate this by displaying
the word directly in the cell. Also instead of separately representing a
word in the dictionary and its identifier record, we can write the word
immediately to the left of a box representing its "valof" cell. Thus the
above representation of the effect of "a" -> x can be abbreviated as
follows:

.===.
x| a |
.===.

We'll use this sort of abbreviation in subsequent examples.

[a] -> x;

This is equivalent to

conspair("a", []) -> x;

It creates a new list, consisting of a single pair record, with a
pointer to the word "a" in its front and a pointer to the empty list []
in its back.

.===.   .---.---.
x| *-+-->| a | *-+----->[]
.===.   .---.---.

To simplify such examples, we'll display "[]" in the box, instead of
showing a pointer to it. So the above example becomes

.===.   .---.--.
x| *-+-->| a |[]|
.===.   .---.--.

[how now brown cow] -> x;

This creates records for the four words "how", "now", "brown" and "cow"
and puts them in the dictionary (so that they'll be found and re-used if
the words occur somewhere else). It does not create identifier records
for value cells for the words, because they are merely quoted in the
list, not used as variable names. It then creates a four element
list, made of four list links, the first containing a pointer to "how"
in its front and a pointer to the second in its back, the second
containing a pointer to "now" in its front, and so on. The fourth link
contains a pointer to [] in its back. When the list has been constructed
a pointer to the first pair is put on the stack. Then the assignment
removes it from the stack and puts it in the valof cell for "x", with
the following result:

.===.   .---.---.   .---.---.   .-----.---.   .---.--.
x| *-+-->|how| *-+-->|now| *-+-->|brown| *-+-->|cow|[]|
.===.   .---.---.   .---.---.   .-----.---.   .---.--.

[[a]] -> x;

This creates a list consisting of a single pair, whose front contains
"a" and whose back contains [], then creates a new list whose front
points to the original list and whose back also points to [], thus:

.===.   .---.--.
x| *-+-->| * |[]|
.===.   .-+-.--.
|         (Note: the backs of both pairs point to the
v          very same item, not two copies of [].)
.---.--.
| a |[]|
.---.--.

[[the man] kicked [a dog]] -> x;

This one is easier to show than to describe. It might be a good idea for
the reader to draw the diagram corresponding to this before looking at
the one given here.

.===.   .---.---.   .------.---.   .---.--.
x| *-+-->| * | *-+-->|kicked| *-+-->| * |[]|
.===.   .-+-.---.   .------.---.   .-+-.--.
|                          |
v                          v
.---.---.   .---.--.       .---.---.   .---.--.
|the| *-+-->|man|[]|       | a | *-+-->|dog|[]|
.---.---.   .---.--.       .---.---.   .---.--.

[a b c] -> x; tl(x) -> y;

This creates the expected two-element list containing pointers to the
quoted words "a", "b" and "c" (added to the dictionary if necessary),
and inserts a pointer to the first link into the valof cell for "x".

The procedure "tl"  then takes a copy of the pointer in the back of the
first link pointed to by "x" (i.e. its tail, or "tl") and the assignment
puts it in the valof cell for the word "y", so that "x" and "y" now both
provides route to the second pair in the list, though it can be reached
more directly from "y".

.===.   .---.---.   .---.--.     .---.--.
x| *-+-->| a | *-+-->| b | * +--->| c |[]|
.===.   .---.---.   .---.--.     .---.--.
^
.===.                 |
y| *-+-----------------*
.===.

After the above has been constructed, the expression "y == tl(x)"
evaluates to TRUE. I.e. it is only the pointer that has been copied
across: the list cell pointed to has not been copied. So if we were
to assign something to hd(y) then that would also change hd(tl(x)) and
vice versa.

The next example illustrates the use of the structure concatenator
"<>" when used with lists. An expression of the form list1 <> list2
creates a new list, which starts with the elements of list1 and
continues with the elements of list2. However although it makes a
complete copy of list1, it re-uses the list2, so that we end up with
two lists sharing a common "tail", as above.

[a b] -> x; [c d] -> y; x <> y -> z;

This creates two two-element lists, putting pointers to the first in the
valof cell for "x", the second in the valof cell for "y". It then
creates a third list which starts with a *complete* copy of the list
links in the first list (i.e. x) , and then instead of ending the copy
with [], puts a pointer to the first link of the second list, with the
following overall result:

.===.   .---.---.   .---.--.
x| *-+-->| a | *-+-->| b |[]|       (Copied to start off z)
.===.   .---.---.   .---.--.

.===.   .---.---.   .---.--.
y| *-+-->| c | *-+-->| d |[]|
.===.   .---.---.   .---.--.
^
|
*---------------*
|
.===.   .---.---.   .---.-+-.
z| *-+-->| a | *-+-->| b | * |
.===.   .---.---.   .---.--.

Note that the two occurrences of "a" are actually two copies of a
pointer to the very same word "a" in the dictionary. Similarly the two
occurrences of "b". So both of the following are true:

hd(x) == hd(z),         hd(tl(x)) == hd(tl(y))

Also y == tl(tl(z)) is true.

[a b] -> x; [c d] -> y; y -> tl(tl(x));

This is similar except that instead of making a copy of the two pairs in
x and making the final link of the COPY point to the list in y, it puts
a pointer to the second list in the back of the last link of x,
producing this:

.===.   .---.---.   .---.--.
x| *-+-->| a | *-+-->| b | * |
.===.   .---.---.   .---.-+-.
|
*---------------*
|
v
.===.   .---.---.   .---.--.
y| *-+-->| c | *-+-->| d |[]|
.===.   .---.---.   .---.--.

-- -- The lack of symmetry between hd and tl

Notice the lack of symmetry between hd and tl. hd(list) is the same
as list(1). But tl(list) is not the same as list(2): it is a list of ALL
remaining elements, or [] if there are not any more.

-- Dynamic lists: generators and pdtolist -----------------------------

Pop-11 includes mechanisms for creating and using 'dynamic lists', whose
elements are created as needed by a generator procedure. This is an
example of what is sometimes referred to as "lazy evaluation".

Dynamic lists are created using the (horribly named) pdtolist procedure
(derived from "ProceDure TO LIST"). This procedure takes a "generator
procedure" as argument and produces a dynamic list as result.

-- -- Generator procedures

A generator procedure is a procedure that can be called repeatedly
without any arguments and will produce a new result each time; and if it
ever produces as its result the unique Pop-11 object termin, that
signifies that there are no more items to be generated.

Here is a generator procedure that uses a private list and goes on
forever generating even numbers, i.e. 0, 2, 4, 6, 8, 10, etc.

define gen_evens() -> next;
;;; create a local, constant, private list containing 0
;;; the number will be changed each time the procedure is run.
lconstant store = [0];

store(1) -> next;
next + 2 -> store(1);
enddefine;

gen_evens() =>
** 0
gen_evens() =>
** 2
gen_evens(), gen_evens(), gen_evens() =>
** 4 6 8

We can use a procedure like gen_evens to create a conceptually
"infinite" list, thus

vars gen_list = pdtolist(gen_evens);

-- -- Printing dynamic lists

If you try to print out gen_list, Pop-11 will only show the part of
the "infinite" list that corresponds to how far the generator procedure
has actually got. We can force it to generate the first N additional
items by accessing the first N items of the list:

gen_list =>
** [...]

The dots indicate an unexpanded dynamic list.

gen_list(1) =>
** 10
gen_list(2) =>
** 12

Now look at the list

gen_list =>
** [10 12 ...]

Part of it is "static", or has been "solidified". But part is still
dynamic, waiting to be expanded, as shown by the three dots. We can move
things on:

gen_list(15) =>
** 38

gen_list =>
** [10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 ...]

-- . Using gensym to make a dynamic list

The potential of dynamic lists can be illustrated using the procedure
gensym. This takes a word as input and each time it is invoked it
produces a new word got by appending a number to the word, e.g.

;;; Make the gensym library procedure accessible
uses gensym;
gensym("cat"), gensym("dog"), gensym("cat"), gensym("dog") =>
** cat1 dog1 cat2 dog2

By partially applying gensym to a word we can create a generator. By
applying pdtolist to the generate we make a dynamic list.

1 -> gensym("pig");     ;;; make sure it starts with pig1, pig2,...

vars pig_gen = pdtolist(gensym(%"pig"%));
pig_gen =>
** [...]

The three dots show that the dynamic list is still unexpanded.
We can force pig_gen to run the generator procedure three times, by
asking for the third element of the list, after which it will print
out as partially expanded:

pig_gen(3) =>
** pig3

pig_gen =>
** [pig1 pig2 pig3 ...]

To restart gensym, use cleargensymproperty().

cleargensymproperty();

;;; This will affect the contents of the dynamic list
pig_gen(4) =>
** pig1
pig_gen(10) =>
** pig7
pig_gen =>
** [pig1 pig2 pig3 pig1 pig2 pig3 pig4 pig5 pig6 pig7 ...]

-- . Note that gensym will be replaced after V14.5

From Poplog V14.5, the procedure gensym is superseded by the procedure
gen_suffixed_word, with the same functionality, and the action

cleargensymproperty()

is replaced by by

clearproperty(gen_suffixed_word_prop)

See REF *gen_suffixed_word, after V14.5

-- -- Accessing components of dynamic lists: hd, tl, dest

The procedures front, back and destpair would not work on on a dynamic
list as expected. Instead we need procedures that can check whether a
list is dynamic or not, and if it is, then run the generator procedure
if necessary to get another element of the list, then create a static
initial portion of that list, leaving the generator on the end.

The procedures hd, tl and dest are designed to do exactly that.
Otherwise they work like front, back, and destpair respectively.

dest([a b c]) =>
** a [b c]

So nearly all the general purpose procedures for operating on lists are
implemented using hd and tl and dest rather than front and back and
destpair, so that they can also work on dynamic lists.

An example of a procedure that will NOT work on dynamic lists is
matches. There are also certain "fast" procedures, described in the
files HELP EFFICIENCY and REF FASTPROCS, that operate on static lists
but not on dynamic lists. Their use can lead to obscure errors if you
suddenly start using dynamic lists!

-- . null(list) vs list == []

Another case that has to be handled is the case of a dynamic list that
is empty.

Let's define a procedure that produces nothing but termin.

define gen_nothing() -> result;
termin -> result;
enddefine;

gen_nothing(), gen_nothing(), gen_nothing() =>
**

If used to create a dynamic list this will effectively create an
empty list:

vars nothing_list = pdtolist(gen_nothing);

nothing_list =>
** [...]

Now if you try to tell whether this is an empty list by comparing it
with [], you'll get the wrong result:

nothing_list == [] =>
**

The procedure null, however, recognises both [], and this dynamic
list as empty lists:

null([a b]) =>
**
null([]) =>
**
null(nothing_list) =>
**

And it changes the internal representation of the dynamic list to tell
the Pop-11 print routines that the generator is finished, so that now it
prints AS IF it were the same as []

nothing_list =>
** []

But it is not

nothing_list == [] =>
**

It's a null dynamic list.

So if you are going to sometimes use dynamic lists then define all your
procedures to use hd, tl, and null rather than front, back and == [].

-- -- The representation of dynamic lists

Readers interested in knowing how dynamic lists are actually represented
should read the Poplog file REF LISTS. Essentially they depend on the
fact that if the final pair in the chain of lists contains as its back a
procedure rather than [], and a non-false front, then the list is taken
to be dynamic. However if the generator procedure has already produced
termin, then the representation is changed by adding a pair whose front
is false and whose back is the generator procedure.

We can look at the contents of nothing_list by using the procedure
destpair, which, when applied to a pair, produces its front and its
back:

destpair(nothing_list) =>
**

By contrast, the procedure dest, which works on lists which may be

dynamic, and returns the hd and the tl of the list, will complain

dest(nothing_list) =>
;;; MISHAP - NON-EMPTY LIST NEEDED
;;; INVOLVING:  []
;;; DOING    :  dest ...

-- -- The uses of dynamic lists

Dynamic lists are often useful for mathematical purposes using number
generators of various kinds. Another use is to represent a stream of
input to the computer. In Pop-11 input devices are often "converted" to
generator procedures (sometimes called "producers") which, each time
they are called produce the next item of input (if it is ready,
otherwise they usually wait).

The Pop-11 compiler, called "compile" (named "popval" in earlier
versions of Pop-11 and Pop-2), is able to take a list of text items
(consisting of words, strings, numbers, and possibly other objects) and
cause them to be compiled into instructions for the computer.

This list is called "proglist" and is described in detail in the files
REF PROGLIST and REF POPCOMPILE. It is possible for the list to be a
simple static list, as in

compile([3 + 3 => ]);
** 6

More usefully, when a file is being compiled the text items in the file
are transformed into a dynamic list, which is then compiled. It would be
possible in principle to read in the whole file and make a huge static
list, then compile that, but usually that's not sensible as a lot of
space will be wasted while the early parts of the file are being
compiled.

It is also useful when Pop-11 is being used interactively to treat the
terminal as if it were an infinite file of text items. This is done by
creating a dynamic list containing the items that are being typed in.
This is based on a generator procedure that returns an item at a time,
which it obtains from a generator procedure (charin) that returns a
character at a time from the terminal, each time it is applied. You can
test it interactively by giving this command:

charin(),charin() =>

It will prompt you for input. You can type a letter or number followed
by the RETURN key. It will then print out two numbers, one being the
ascii code for the letter or number, and the second being the ascii code
for a newline, i.e. 10. (There is a separate character repeater for
'raw' mode interaction used by the editor, which does not wait for you
to type RETURN after typing another character.).

The item repeater for interactive Pop-11 is created by applying the
system procedure incharitem to charin, thus:

incharitem(charin)

This creates a new procedure, which is an item repeater. Each time the
item repeater is run it consumes enough characters to make a complete
text item, and it returns that item, and then the next time it is run it
returns the next item, and so on.

The dynamic list constructor pdtolist, can be applied to this item
repeater, and that will create a dynamic list of program text items.
That, in fact, is what proglist is when programs are being compiled
either from a file or from the terminal. I.e.

pdtolist(incharitem(charin)) -> proglist;

Because proglist is a dynamic list, if the compiler is reading in an
expression of some kind and the user has not finished typing it, the
compiler simply waits till more is typed (every time the user presses
the RETURN key, the items typed so far are made available as an
extension to proglist).

Note that the above is highly modular: instead of compiling from the
current input stream Pop-11 can compile from any sequence of characters,
including the characters stored in a string, as illustrated by the
following command, which uses stringin to turn a string into a
character repeater:

compile(pdtolist(incharitem(stringin('66*33 =>'))));
** 2178

You can experiment with an infinite list connected to the current input
stream as follows:

vars inputlist = pdtolist(incharitem(charin));

inputlist =>
** [...]

-- . An example of an infinite list of input
This example will work well only in the editor.

The following will prompt for input until you have typed enough for
three full text items. Suppose you respond by typing "the cat" on one
line, followed by RETURN, followed by "on" on the next line:

inputlist(3) =>
** on

You can now print out the current state of inputlist:

inputlist =>
** [the cat on ...]

This will now prompt for two further input items:

inputlist(5) =>
inputlist =>

For more information on dynamic lists and the compiler input stream see
REF LISTS, and REF PROGLIST

For writing interactive programs it is not usually convenient to use
charin and proglist. Generally it is safer for beginners to use the
built in procedure readline, illustrated in TEACH RESPOND, which might
be defined thus:

global vars pop_readline_prompt = '? ';
lvars item, list,
procedure rep = incharitem(charin);     ;;; item repeater

;;; temporarily change two global variables.
dlocal
popnewline = true,  ;;; make newlines recognisable

;;; Make a list items to next newline
[% until (rep() ->> item) == newline do item enduntil %] -> list;

enddefine;

;;; Test it
? pretty polly pretty polly
** [pretty polly pretty polly]

Please say something: how are you today?
** [how are you today ?]

In the last example the words after ":" were typed in, and made into a
list.

-- Some procedures for manipulating lists -----------------------------

We have already met some expressions denoting lists. This section
will introduce some of the procedures used for manipulating lists,
including new procedures for creating new lists, or modified versions of
old ones.

-- -- cons, conslist, initl, sysconslist

cons(ITEM, LIST) -> LIST

This is strictly equivalent to ITEM :: LIST. It is included in Pop-11
merely as an analogue for the function CONS in Lisp.

conslist(ITEM1, ITEM2, ..., ITEMN, N) -> LIST

Returns a list constructed from the top N items on the stack. E.g.

conslist("a", "b", [c d], 3) =>
** [a b [c d]]

conslist(#| vars i; for i from 2 to 13 do i*i endfor|#) =>
** [4 9 16 25 36 49 64 81 100 121 144 169]

initl(N) -> LIST

This constructs a list of empty lists, of length N. E.g.

initl(6) =>
** [[] [] [] [] [] []]

sysconslist() -> LIST

Collects all items placed on the stack since the last stackmark, into a
list. This is used by Pop-11 list constructor syntax. E.g.

[% 1, 2, 3, 4 %]

is equivalent to

popstackmark, 1, 2, 3, 4; sysconslist();

See REF LISTS, for a description of sysconslist_onto(LIST_1), which
is used when ^^ precedes the last item in a list expression.

-- -- allbutfirst, allbutlast

allbutfirst(N, LIST) -> SUB_LIST
allbutlast(N, LIST) -> SUB_LIST

These two can be used to "chop off" an initial or final segment of a
list, of length N.

allbutfirst(2, [a b c d e]) =>
** [c d e]
allbutlast(2, [a b c d e]) =>
** [a b c]

In the first case, the result will share list links with the input list.

-- -- dl or explode, destlist

The procedure dest (or destpair) when given a list puts its and its tail
on the stack. Sometimes it is necessary to put all the elements of a
list on the stack, e.g. in order to use them to make a copy of the
original list. The procedure explode will do this.

explode([a b [c d] e f]) =>
** a b [c d] e f

However, explode works on a variety of different structures, including
words, strings, vectors and lists. A version specific to lists is also
available, known as "dl".

dl([a b [c d] e f]) =>
** a b [c d] e f

destlist is similar, except that it also returns the number of
items in the list. It's the reverse of conslist.

destlist([a b [c d] e f]) =>
** a b [c d] e f 5

-- -- applist, maplist, ncmaplist

Both of these take a list and a procedure and apply the procedure to
every element of the list. The only difference is that maplist makes
a list of everything put on the stack.

applist([1 2 3 4 5], nonop +(% 10 %)) =>
** 11 12 13 14 15

maplist([1 2 3 4 5], nonop *(% 10 %)) =>
** [10 20 30 40 50]

ncmaplist, non-constructive maplist, is like maplist, except that it
re-uses the links of its first argument.

-- -- recursive_front

This procedure can be applied to any object. If it's a list or pair, it
repeatedly applies the procedure front, until a non-pair is found, and
returns that as its result. This is useful for digging out items deeply
embedded in lists.

recursive_front([[[[[a]  b ] c]] d]) =>
** a

-- -- expandlist

expandlist(LIST) -> LIST

Returns LIST unchanged, unless the list is dynamic, in which case it
runs the generator procedure to completion and makes the list static. It
will loop forever if the list is of infinite length.

-- -- rev and ncrev

rev(LIST) -> LIST

rev, when given a list, produces a new version which has the same
elements in reverse order:

rev([1 2 3 4]) =>
** [4 3 2 1]

The procedure does not alter the order of elements in the original list:
that is left unchanged.

ncrev(LIST) -> LIST

This is like rev, except that it re-uses the list links of the original
list, so that it does not use any new store. This can reduce garbage
collections but is dangerous if there is any risk that something else
was dependent on the original list surviving unchanged.

vars list1 = [a b c], list2 = ncrev(list1);
list2 =>
** [c b a]
list1 =>
** [a]

-- -- setfrontlist

setfrontlist(ITEM, LIST_1) -> LIST_2

Returns LIST_2 formed by moving the ITEM to the front of LIST_1, or
adding the ITEM if not already present. (This is used by the
editor VED whenever a file in vedbufferlist becomes "current".)

-- -- sort and syssort

sort(LIST_1) -> LIST_2

The list should contain either numbers only or words only or strings
only or a mixture of words and strings. Any other items will produce an
error. It returns a list of sorted items. If it contains numbers only,
then the result is equivalent to

syssort(LIST_1, nonop <)

otherwise

syssort(LIST_1, alphabefore)

sort([the cat sat on the mat]) =>
** [cat mat on sat the the]

sort([ 111 222 33 ]) =>
** [33 111 222]

syssort(LIST, P) -> LIST
syssort(LIST, BOOL, P) -> LIST

The first argument is a list, the last argument is a procedure which
takes two items and returns a boolean result (e.g., nonop < for numbers
or -alphabefore- for string and words, etc). The items in the list are
compared using the procedure and the result is a list with elements
sorted in accordance with the procedure. If the optional boolean
argument is , then the sorting is non-copying, and merely
re-arranges the elements of the argument list, like ncrev. A merge sort
algorithm is used. Example

syssort([[the] [cat] [sat] [on] [the] [mat]],
procedure(l1, l2);
alphabefore(hd(l2), hd(l1))
endprocedure) =>
** [[the] [the] [sat] [on] [mat] [cat]]

-- -- last, lastpair

last finds or updates the final element of a list:

last([cat dog mouse]) =>
** mouse

last([[tom brown] [mary green] [suzy white]]) =>
** [suzy white]

Note that in the latter example, the procedure LAST was applied to a
list of lists, and produced as its result a list, i.e. the last
list.

vars list = [a b c d];
list =>
** [a b c d]

999 -> last(list);
list =>
** [a b c 999]

NOTE: last can also work on words, vectors and strings, though the
updater cannot be used with words.

lastpair(LIST) -> PAIR
PAIR -> lastpair(LIST)

Returns or updates the last PAIR of the list LIST, i.e. the last link in
the chain. LIST cannot be null. Having a pointer to the last pair of a
list, instead of the last item in the list makes various things much
simpler. For example, here is one way to define a queue:

vars queue = [a b c d], queue_start = lastpair(queue);

queue_start =>
** [d]

To add something to the queue at the far end, do this:

conspair("e", []) -> back(queue_start);
back(queue_start) -> queue_start;
queue =>
** [a b c d e]
queue_start =>
** [e]

Remove something at the left end:

tl(queue) -> queue;
queue =>
** [b c d e]

-- -- oneof, shuffle

oneof applied to a list chooses an element at random. Thus using it
repeatedly on the same list may or may not produce different results:

repeat 4 times
oneof([ [you are gorgeous]
[everyone loves you]
[how masterful you are]
[you are quite stunning]
]) =>
endrepeat;
** [you are quite stunning]
** [everyone loves you]
** [you are quite stunning]
** [you are quite stunning]

shuffle(LIST_1) -> LIST_2

Returns a copy of its argument with the elements randomly re-ordered.
It uses -oneof-.

repeat 4 times shuffle([a b c d e]) => endrepeat;
** [b d c a e]
** [b d a c e]
** [b e c d a]
** [d c e b a]

Since oneof and shuffle are defined in terms of random, illustrated
previously, (in Chapter 5) their behaviour can be controlled by
assigning to the variable ranseed, as in the case of random.

-- -- delete, ncdelete

delete produces copies of a list which do not contain a certain element.
It has several different formats

delete(ITEM, LIST_1)          -> LIST_2
delete(ITEM, LIST_1, EQ_P)    -> LIST_2
delete(ITEM, LIST_1, N)       -> LIST_2
delete(ITEM, LIST_1, EQ_P, N) -> LIST_2

These all delete occurrences of ITEM from LIST_1, producing a new
list LIST_2 (which shares the largest possible trailing sublist of
the original).

The parameter EQ_P is an optional argument; if supplied, it must be a
procedure of the form

EQ_P(ITEM, LIST_ELEMENT) -> BOOL

EQ_P is then used to compare ITEM against each list element, and those
for which it returns true are deleted. If not supplied EQ_P defaults to
nonop = (i.e. structure equality). (See HELP EQUAL)

N is a second optional argument: if supplied, it is an integer >= 0
which specifies how many matching elements should be deleted (e.g, if 1
then only the first occurrence will be removed). If not supplied, all
occurrences are deleted.

For example,

delete(1, [1 2 3 4 5 6 1 9 8]) =>
** [2 3 4 5 6 9 8]
delete(1, [1 2 3 4 5 6 1 9 8], 1) =>
** [2 3 4 5 6 1 9 8]

delete("cat", [mouse cat dog flea], nonop == ) =>
** [mouse dog flea]

delete('cat', ['mouse' 'cat' 'dog' 'flea'], nonop == ) =>
** [mouse cat dog flea]

delete('cat', ['mouse' 'cat' 'dog' 'flea'], nonop = ) =>
** [mouse dog flea]

(The difference between the last two is due to the fact that two strings
can be "=" but never "==").

ncdelete(ITEM, LIST_1)          -> LIST_2
ncdelete(ITEM, LIST_1, EQ_P)    -> LIST_2
ncdelete(ITEM, LIST_1, N)       -> LIST_2
ncdelete(ITEM, LIST_1, EQ_P, N) -> LIST_2

Non-constructive delete. Same as delete, but does not copy list pairs
that need to be changed, and thus (may) destructively change the
original list. The result LIST_2 will be == to LIST_1 unless there are
one or more leading matching occurrences of ITEM that are deleted.

-- -- flatten and flatlistify

flatten(LIST_1) -> LIST_2

Explodes LIST_1 and all sub-lists in LIST_1. I.e. it converts a tree
into "flat" list of elements at the "fringe" of the tree.

flatten([ a [ b c [d e] [f]] g [ h [i] ] j]) =>
** [a b c d e f g h i j]

flatlistify(STRUCT) -> LIST

Given a structure, STRUCT, made of lists and/or vectors embedded
arbitrarily, -flatlistify- will return a list, LIST. The result
contains all the words needed to create a list isomorphic with the
original one, if given to compile.

flatlistify([ a [ b c [d e] [f]] g [ h [i] ] j]) =>
** [a [ b c [ d e ] [ f ] ] g [ h [ i ] ] j]

NB. That is a 20 item list containing "a", "[", "b", etc.

-- -- length and listlength

These can both be applied to a list and will return the number of
elements. The difference is that length can be applied to many other
types of objects besides lists, e.g. strings, vectors.

listlength([a [ b c d] e ]) =>
** 3
listlength({ a b c }) =>
;;; MISHAP - LIST NEEDED
;;; INVOLVING:  {a b c}

-- -- copy, copylist, copydata, copytree

The procedure copy when given a Pop-11 data-structure returns a copy
that is = to the original. In the case of lists, it merely copies the
first link, returning a new pair with the same front as the old one and
the same back as the old one. This means that the two lists share tails.

vars list1 = [a b c d], list2 = copy(list1);
list2 =>
** [a b c d]

33 -> list1(3);
list1 =>
** [a b 33 d]
list2 =>
** [a b 33 d]

An assignment to the first element of a will not affect list2, and
vice-versa, but replacing any other element of either will affect the
other.

In order to avoid this what is needed is a complete copy of the original
provided for that purpose. The above example may be tried with copylist

Even if copylist did not exist, there are several ways it could be
defined by users, including the following:

define copylist1(list);
maplist(list, identfn)
enddefine;

define copylist2(list);
[% applist(list, identfn) %]
enddefine;

define copylist3(list);
[% explode(list) %]
enddefine;

define copylist4(list);
conslist(#| explode(list) |#)
enddefine;

define copylist5(list);
conslist(destlist(list))
enddefine;

copytree(LIST_1) -> LIST_2

This makes a list, LIST_2, which is a copy of LIST_1. Any elements of
LIST_1 which are themselves lists are recursively copied.

copydata is a generalisation of copytree that works on arbitrary
datastructures. Thus if a list contains vectors containing lists, etc.
then, in order to obtain a completely new copy use copydata, not
copylist.

-- -- subscrl, fast_subscrl

subscrl(N, LIST) -> ITEM
ITEM -> subscrl(N, LIST)

Returns or updates the N-th element of the list LIST (where  the first
element is has subscript 1). Because this procedure is the -class_apply-
procedure of pairs, this  can also be used in  the form

LIST(N) -> ITEM
ITEM -> LIST(N)

fast_subscrl(N, LIST) -> ITEM
ITEM -> fast_subscrl(N, LIST)

This is like subscrl, but does not check argument data types, and does
not expand dynamic lists.

-- Predicates on lists ------------------------------------------------

-- -- atom, islist, ispair, islink, null

atom(ITEM)-> BOOL

This will be true for all items except pairs, and false for pairs.
This is therefore equivalent to not(ispair(ITEM)).

islist(ITEM) -> BOOL

This is intended to recognise the empty list [], dynamic lists, or
ordinary lists. However, for efficiency it does not check that all the
links in the chain have lists in their tail, and so it can be fooled.
e.g.

islist(conspair(3,4)) =>
**
islist(conspair(2,conspair(3,4))) =>
**

The latter is not really a list because it does not end in []. A "proper"
list recogniser would be something like this

define is_really_list(item);
if islist(item) then
if null(item) then true
elseif atom(item) then false
else is_really_list(tl(item))
endif
else
false
endif
enddefine;

is_really_list(conspair(2,conspair(3,4))) =>
**
is_really_list(conspair(1, conspair(2,conspair(3,4)))) =>
**
is_really_list(conspair(1, conspair(2,conspair(3,[])))) =>
**

The above definition could be optimised slightly by checking for dynamic
lists directly on the basis of the definition of dynamic lists instead
of using islist to do that.

ispair(ITEM) -> BOOL

A recogniser for pair datastructures.

This is equivalent to
ispair(item) and not(null(item))

null(ITEM) -> BOOL

This recognises empty lists, including empty (exhausted) dynamic lists.
If ITEM is a dynamic list that has not been expanded it will expand it
by one step, so that front and back can be used on that link instead of
hd and tl, in order to avoid repeating the test for a dynamic list.

-- -- isdynamic

isdynamic(ITEM) -> P

Recognizes dynamic lists. If ITEM is a dynamic list it returns the
generator procedure, otherwise it returns false.

-- -- member, lmember

member(ITEM, LIST) -> BOOL

This procedure returns true if ITEM is an element of the list LIST,
otherwise false, equality being determined with the operator "=".

lmember(ITEM, LIST) -> SUB_LIST
This is like member except that
1. The test for equality is "==" not "="
2. If ITEM is found to be == to an element of the list, then the
procedure returns the trailing portion of LIST starting  with
that element

lmember("on", [the cat sat on the black mat]) =>
** [on the black mat]

-- -- user defined predicates

In a language like Pop-11 it is very easy to define additional list
processing procedures. For example, a slight variant of maplist would
take a list and two procedures and return a list of two element lists:

define map2list(list, proc1, proc2) -> list;
[%
lvars item;
for item in list do [%proc1(item), proc2(item)%] endfor
%] -> list
enddefine;

map2list([1 -2 3 -4 5 -6], identfn, negate) =>
** [[1 -1] [-2 2] [3 -3] [-4 4] [5 -5] [-6 6]]

A procedure to merge two lists by interleaving elements:

define merge(list1, list2) -> list;
lvars item1, item2;
[%
for item1, item2, in list1, list2 do item1, item2, endfor
%] -> list
enddefine;

merge([1 2 3 4], [a b c d]) =>
** [1 a 2 b 3 c 4 d]

Note if either list has more elements than the other this procedure will
ignore trailing items in the longer list.

The variety of possible user defined list manipulating procedures
is endless. In Poplog Pop-11 several examples can be found in the
library directories, i.e. \$usepop/pop/lib/auto and \$usepop/pop/lib/lib

-- Iterating on lists -------------------------------------------------

The main Pop-11 iteration constructs were given in an earlier chapter.
Here we give a number of examples of iteration involving lists. Using
iteration we can easily perform a subset of the operations previously
illustrated using recursion. Iteration is sometimes easier to
understand, and can be more efficient (i.e. easier for the computer). It
has the disadvantage that you cannot use TRACE to make explicit what is
happening when the program runs.

There are many different forms of iteration over lists. The simplest
is a serial scan over the elements of the list. Here is a new
definition of TRAVERSE, using an UNTIL loop.

define traverse(list);
until list = [] do
hd(list) =>
tl(list) -> list
enduntil;
enddefine;
traverse([a b c d]);
** a
** b
** c
** d

-- Using for ... in ... do .... with lists ----------------------------

E.g., to add all the numbers in a list

lvars x, total = 0;
for x in list do
x + total -> total
endfor
enddefine;

** 24

-- -- Using for inside [% ..... % ]

We could use the FOR construct to define a procedure like delete. We use
a local variable, say 'x', to denote successive elements in a list. If
the element is not the same as the item to be deleted, then leave the
element on the stack. If all this is done inside the list brackets,
using '%', then the items left on the stack will be made into a list.

define new_delete(item, list) -> result;
lvars x;
[% for x in list do
unless x = item then x /* left on stack */  endunless;
endfor
%] -> result
enddefine;

new_delete([a b], [[1 2] [3 4] [a b] [c d]]) =>
** [[1 2] [3 4] [c d]]

-- Iterating over two or more lists -----------------------------------

if list1, list2, list3, ... listN, are lists, then it is possible
to use N variables and iterate over all the N lists at once, thus:

for item1, item2, ... itemN in list1, list2, ... listN do

endfor

The instructions will be obeyed N times, each time taking one item from
each list. If any lists are shorter than the shortest list, then their
trailing items will be ignored.

E.g.

vars item1, item2, item3;
for item1, item2, item3 in
[the every each all some],
[men pig cow cars],
[stank slept fell ate]
do
[^item1 ^item2 ^item3] =>
endfor;
** [the men stank]
** [every pig slept]
** [each cow fell]
** [all cars ate]

-- Iteration vs Recursion ---------------------------------------------

Instead of using FOR, it is always possible to recurse on the TL of
the list. The recursive technique has the great advantage that
successive calls of the procedure can be TRACEd. Constructions
utilising loops (REPEAT, WHILE, UNTIL, FOR) do not admit of easy
monitoring through TRACE.

Often, however, it is very quick and easy, using VED, to temporarily
alter the definition so that each time round the loop the procedure
prints something (e.g. the value of 'x' in the last example). In a
system such as Poplog altering and recompiling a procedure is so fast
that temporary changes for debugging purposes can be very much more
useful than in a conventional language.

Moreover, if a looping construct is used, then the list brackets [ ... ]
( or the vector brackets { ..... } ) can be used to collect together
all the items left on the stack into a list, if that is desired. (This
is one of the features of Pop-11 not available in LISP, which uses
alternative mechanisms.) Compare the following two different definitions
of procedures equivalent to maplist.

define maplist1(list, proc);
if null(list) then []
else
proc(hd(list)) :: maplist1(tl(list), proc)
endif
enddefine;

define maplist2(list, proc);
lvars item;
[%for item in list do proc(item) endfor%]
enddefine;

The former uses the so-called "functional" style of programming.
However, I have no doubt that the second is easier to understand and
that programmers using the second style will make fewer mistakes.

Another example: here are two ways make a list of all the non-empty
tails of a list:

define all_tails1(list);
if null(list) then []
else
list :: all_tails1(tl(list))
endif
enddefine;

define all_tails2(list);
lvars tail;
[%for tail on list do tail endfor%]
enddefine;

all_tails1([ a b c d ]) =>
** [[a b c d] [b c d] [c d] [d]]

An advantage of the recursive version is that when it is traced it shows
clearly what is going on, whereas extra printing instructions have to be
put into programs using for ... endfor to show what is happening on each
iteration.

Try

trace all_tails1;

then redo the above command. (See TEACH TRACE)

Using the integrated editor VED makes it very quick and easy to add or
remove printing instructions and recompile, so the difference in
traceability is not very great.

-- Exercises ----------------------------------------------------------

What should the following print out? Which of the expressions produce
words, and which produce lists? (Work out your won answers and write
them down before running the commands in Pop-11).

last(hd([[tom brown] [mary green] [suzy white]])) =>

last(last([[tom brown] [mary green] [suzy white]])) =>

hd(hd([[tom brown] [mary green] [suzy white]]))=>

hd(tl([[tom brown] [mary green] [suzy white]]))=>

tl(hd([[tom brown] [mary green] [suzy white]]))=>

tl(tl([[tom brown] [mary green] [suzy white]]))=>

-- More exercises on lists --------------------------------------------

1. Write down some examples of expressions denoting:
a list of numbers
a list of words
a list of numbers and words
a list of lists of words
a list of lists of numbers

2. What is denoted by each of the following:

hd( [ once upon a time ] )
last( [ mary had a little lamb ] )
hd( [ [mary had] [a little lamb] ] )
rev( [ mary had a little lamb ] )
last( hd( [ [ mary had ] [ a little lamb ] ] ) )
delete( "cat", [mouse pig cat dog cat] )
delete( "cat", [mouse pig cat dog cat], 1 )

3. What does oneof do?
ONEOF is a procedure which takes one argument (or one input
item) and produces one result. The argument must be a ....
The result will be .....

4. What does delete do?
(I.e. how many arguments does it take? What sorts of things
can they be? How many results does it produce? How is the
result related to the arguments?)

5. What do the following denote:

delete(3, rev([ 1 2 3 4 5]) )

rev( delete( "little", [mary had a little lamb] ) )

-- Exercises on the meaning of the single and double up-arrows

Here are some puzzles to test your understanding. If we assign [a b] to
x, thus:

[a b] -> x;

then the list [^^x c] is [a b c] and the list [^x c] is [[a b] c].

What values would have to be assigned to x, y etc so that the
following were true (some are impossible - which ones?):

[^^x ^^x] = [a b a b]         ;;; answer is [a b] -> x;
[^x ^^y] = [[a b] b c]        ;;; answer is [a b] -> x; [b c] -> y;
[^^x mother ^^y] = [i love my mother]
[the height of steve is ^^x] = [the height of steve is 70 inches]
[every ^^x is a ^^y] = [every fire man is a civil servant]
[every ^x is a ^y] = [every fire man is a civil servant]
[^^x i ^^y you] = [sometimes i hate people like you]
[[^x ^^y] ^^z] = [[a b c d]]
[^x [^^y] ^z] = [[a b] [c d] [e f]]
[i saw ^^n ships] = [i saw 3 ships]
[i saw ^n ships] = [i saw 3 ships]
[i ^x you] = [i hate computers]
[^x ^y ^z] = [i hate computers]

Use the computer to check your answers. For example, if you think
the answer to the fourth one is:

[6 feet] -> x;

then try printing the list:

[the height of steve is ^^x] =>

Later you will see that the procedure MATCHES could be used to find

-- CHAPTER.7: THE POP-11 PATTERN MATCHER AND DATABASE

We have already seen how the equality symbol "=" can be used to
compare two lists. The operation MATCHES provides more sophisticated
facilities for matching lists against a partially specified pattern.

(In Poplog version 15.5, the equality operator "=" was extended to
include this matching capability, based on a new kind of
matchvar data-type. See the section on Patterns in HELP EQUAL).

The pattern matcher makes it possible to express some complex ideas in a
way that is both much clearer and easier to read than normal procedural
formulations, and also easier to get right first time when programs are
being developed. So for many kinds of programs it can substantially
speed up the development time. There are additional facilities based on
the pattern matcher in the Pop-11 database, and these add to the power
of the language for solving quite complex problems, including developing
expert systems.

The matcher can be used in several different formats. The most common is
an expression of this form, which always evaluates to TRUE or FALSE,
depending whether the list does or does not match the pattern.

matches

;;; Simple examples, using the matcher like an equality tester:

[a b c d] matches [a b c d] =>
**

[a b c d] matches [d b c a] =>
**

The use of pattern elements allows the matcher to perform more complex
comparisons. The pattern matcher assumes that information is stored in
lists whose contents can be searched by specifying a pattern (a sort of
template list) containing special pattern elements described below. Some
of these pattern elements are used to match individual items in a list.
Others can match arbitrarily long subsets of lists and are called
"segment" pattern elements. We illustrate the power of segment pattern
elements first.

-- -- The anonymous segment pattern element: "=="

We start by illustrating the use of the segment pattern element "==" to
create templates that can be used to match lists.

The symbol "==", which we have previously met as an equality symbol
can be used in patterns with an entirely different function, to
represent an unspecified number of unknown elements. For example
both the following complex expressions denote TRUE

[who is the father of joe] matches [who is == ]

[where is the father of joe] matches [where is == ]

The following also denote TRUE:

[you are my favourite programming pupil] matches [== pupil]

[the little dog laughed to see such fun] matches [== dog ==]

-- Using matches to define a procedure --------------------------------

MATCHES is a Pop-11 procedure which takes two arguments, a list and a
pattern (which is also a list), and produces one result, a boolean, i.e.
either TRUE or FALSE. The name of the procedure "matches" is defined to
be an infix operator (like "=", "+", "<>" and "::") so that it can be
used in the form

list matches pattern

It takes two arguments, both lists, and returns one result, a
boolean. The first argument is called the DATUM (what is given) and
the second the PATTERN, against which the datum is to be compared.

The pattern may contain special pattern elements, of which "==" is a
simple example. Other types of pattern elements are explained below.
Notice the asymmetry: the pattern must be the second argument, never the
first.

To illustrate, here is a procedure which uses MATCHES to decide
whether a question requires a person or a place as its answer:

if     list matches [who is ==] then
"person" -> type
elseif list matches [where is == ] then
"place" -> type
else
"undef" -> type
endif
enddefine;

The procedure type_of_answer takes as its input a list, and produces
a word as its result. The word is one of "person" "place" "undef".
Notice the use of the multi-branch conditional form:

if condition1 then
action1
elseif condition2 then
action2
else
default action
endif

An expression using "matches" can be used as a condition because it
always produces a boolean result. We can test the above definition thus:

** person

** place

** undef

"undef" is a word often used in in Pop-11 to indicate something
unknown.

Of course, this definition is not at all adequate to recognising
requests for information about persons or places, e.g.

** undef

The matching procedure MATCHES is used by the database procedures
ADD, REMOVE, PRESENT, LOOKUP, and FLUSH and the database looping
constructs FOREACH and FOREVERY, about which more is said below. These
provide very useful problem-solving tools for both AI programming and
other kinds of programming requiring manipulation of complex, changing
structures.

-- Exercise ---------------------------------------------------

Using the previous definition as a model, define a procedure called
FRIENDLY, which takes a list of words as input, and produces a result
which is TRUE, or FALSE or UNDEF. The result should be TRUE if the list
contains the words 'LIKES YOU' and FALSE if the list contains the words
'HATES YOU', and UNDEF if it contains neither. The definition can start:

define friendly(list) -> result;

Hint: you'll need to use "==" as a pattern element more than once in
the same pattern.

You may test your definition with commands like:

friendly([everybody hates you today]) =>
friendly([father christmas likes you ]) =>
friendly([I can not bring myself to like you]) =>

What results should these print out?

-- Use of the matcher to extract the contents of a list ---------------

In the previous uses of the matcher with "==" the portion of the list
that corresponded to "==" was ignored. We might want to revise the above
procedure so that it extracted that portion and returned it as a result.
For that we use a "segment variable" pattern element, in which a
variable name is preceded by "??". The use of "??" indicates that the
variable should match an arbitrary number of items in the datum, and if
the whole match is successful a list containing those items should be
assigned to the variable. Here is an example, in which we change the
above procedure to return two results, the type of question, and the
contents of the question. Note that we have to use "vars" to declare a
variable as a pattern variable:

vars remainder;

if     list matches [who is ??remainder] then
"person" -> type;
remainder -> contents;
elseif list matches [where is ??remainder ] then
"place" -> type;
remainder -> contents;
else
"undef" -> type;
[] -> contents;
endif
enddefine;

This can now be tested:

** undef []

** person [the murderer]

** place [the murderer]

NOTE: if you have obtained the Birmingham university extensions to the
pattern matcher you can use the pattern prefix "!" to convert pattern
variables to work with lexically scoped identifiers. See the 1999
Preface to the Third edition of this Primer. At some stage the examples
in this chapter using "?" and "??" in patterns should be rewritten to
use the pattern prefix.

-- The use of "?" variables -------------------------------------------

The variable preceded by "??" in the above example matched a segment of
the list. We can also use a variable to match a single element of a
list, and have that element assigned as its value. For example, here is
a way of getting the third element of a list assigned to the variable
"item". We use "=" as an anonymous pattern element to match exactly one
element of the datum without saving the value and "?item" to match
one element and save the value in the variable item.

vars item;
[ the cat sat on the mat] matches [ = = ?item ==] =>
**

item =>
** sat

Here we use the matcher to extract the third and fourth elements of a
list:

vars third, fourth;
[the cat sat on the black mat] matches [= = ?third ?fourth ==] =>
**

third =>
** sat
fourth =>
** on

-- -- Example: Using the matcher to define next_item

Consider how to define a procedure that searches down a list looking for
a given item, and if it finds it returns the next item. You could write
that using normal list processing procedures as follows:

define next_item(item, list) -> next;
repeat
if list = [] then
false -> next;
return();
elseif hd(list) = item then
;;; found the target, get the next item and stop
hd(tl(list)) -> next;
return()
else
;;; move one step down the list.
tl(list) -> list;
endif
endrepeat
enddefine;

Here is a version using the pattern matcher.

define next_item(item, list) -> next;
vars found;  ;;; this is to be used as a pattern element

if list matches [ == ^item ?found ==] then
found -> next
else
false -> next
endif
enddefine;

Note that we use "^item" as explained previously to insert the value of
the variable item in the pattern. This means that instead of our
programs always having fixed patterns they can have dynamically
constructed patterns.

Now test the procedure

vars person = [name sue age 30 job teacher home york];
next_item("age", person) =>
** 30
next_item("home", person) =>
** york
next_item("height", person) =>
**

That example should illustrate how much easier it is to use the matcher
than ordinary list processing in such cases. Programs using the standard
list processing method will run faster, however. If that is important,
program using the matcher can be "translated" after they have been
developed.

-- -- Exercise: define previous_item

Using the above example as a template produce a definition of a
procedure called previous_item that behaves thus:

vars person = [name sue age 30 job teacher home york];
previous_item(30, person) =>
** age
previous_item("york", person) =>
** home
previous_item("height", person) =>
**

-- The matcher arrow "-->" --------------------------------------------

The matcher arrow is often very useful when you are sure two things
will match, but you want to use the matcher to examine the contents
of one of them. That way you don't use a conditional expression of the
form:

if ... matches ... then ....

Instead we use the matcher arrow "-->". "-->" should not be confused
with "->". The latter is the assignment arrow.

The infix operation "-->" could have been defined thus:

define 8 datum --> pattern;
unless datum matches pattern then
mishap('NON MATCHING ARGUMENTS FOR -->',[%datum,pattern%])
endunless
enddefine;

The '8' in the procedure heading indicates that an infix operation
of precedence 8 is being defined.

This definition looks as if it doesn't do anything when the datum
matches the pattern. We shall see that, on the contrary, it can be
used to 'decompose' a list.

-- -- Examples of the use of "-->"

The simplest use of '-->' is to check that a list has a certain format:

list --> [junction == ];

checks that LIST starts with "JUNCTION". If not, an error occurs.

[a b c d] --> [junction ==];

;;; MISHAP - NON MATCHING ARGUMENTS FOR -->
;;; INVOLVING:  [a b c d] [junction ==]
;;; DOING    :  --> compile

The operation --> can also be used to decompose a list, i.e. to assign
some of its components to variables.

vars first, second, rest;
vars list = [dogs like wagging their tails];

list --> [?first ?second ??rest];
first =>
** dogs
second =>
** like
rest =>
** [wagging their tails]

That would have caused an error if LIST had had fewer than two elements.
Since there are at least two elements, it gives FIRST the first element,
as its value, SECOND the second element, and REST a list containing all
the remainder.

Here's another example.

vars first, second, rest;

[mary had a little lamb] --> [?first ?second ??rest];

first =>
** mary

second =>

rest =>
** [a little lamb]

Notice the different effects of "?" and "??". The former means, roughly
"match ONE element", the latter means, roughly "match any number of
elements". The use of "??" and "==" can mean that there are alternative
ways of matching a list against a pattern. In that case the matcher will
find only one of them. Which one it finds is not defined. The Birmingham
ftp directory has a library called "doesmatch" that finds all the
possible matches.

-- Findroom revisited -----------------------------------------

We can illustrate the use of the matcher to simplify the definition
of a searching procedure, by redefining the procedure 'findroom'
introduced in chapter 1, and defined thus:

define findroom(name, list_of_lists) -> data;
;;; search list_of_lists for one starting with name

for data in list_of_lists do
if data(1) = name then
return();       ;;; i.e. stop the procedure
endif;
endfor;

;;; produce a mishap message
enddefine;

Compare this with the following:

define findroom(name, list) -> data;
vars len, breadth, height;  ;;; pattern variables

if list matches [ ==  [^name ?len ?breadth ?height] == ]
then
[^name ^len ^breadth ^height] -> data;
else
endif
enddefine;

The line

if list matches [ == [^name ?len ?breadth ?height] == ]

runs the operation called 'matches' with two inputs, the value of the
variable 'list', and the pattern on the right, which instructs the
matcher what to look for in the list. It says, look for any number of
elements (matched against "=="), then a list starting with the given
name and containing three other things, followed by any number of
elements (matched against "==" again).

-- Setting a value ("?") vs Using a value ("^")

Notice the difference between "?" and "^" here.  The searched-for
information is represented by the list

where the symbol "^" says that the given name must be found. "^" can be
read as 'use the value of', whereas the occurrences of "?" can be read
as 'set the value of'. I.e. the three variables will be given values
depending on what numbers are found after the name, once the list with
the required name is found. If we had used "?name" instead of "^name",
then ANY name would have been accepted.

If the MATCHES operation produces the result TRUE, having found what is
required then the instruction after 'then' is obeyed, which ensures that
the output local 'data' has an appropriate value, to be returned as the
result of the procedure.

If MATCHES cannot find what is required in list, then it produces the
result FALSE, and the instruction after 'else' is obeyed, causing an
error message to be printed out.

Using the fact that "-->" will cause an error when a match fails, we
could adopt the even shorter definition:

define findroom(name, list) -> data;

;;; Use vars for pattern variables (with "?")

list --> [ ==  [^name ?len ?breadth ?height] == ];

[^name ^len ^breadth ^height] -> data;
enddefine;

-- List pattern matching --------------------------------------

We now provide a more general motivation for the pattern matcher,
and give a complete account of its operation.

If we wish to search down a list for an item we can use a test something
like

item = hd(list)

to accomplish this. But list representations of more complex situations
do not exhibit their significant features in terms of single items
considered in isolation. Rather the norm is one of a context or
co-occurrence of elements. Thus we are much more likely to want to know
whether a list contains two designated elements occurring in a
particular order, or even whether it satisfies some rather more complex
condition. E.g. does the sentence start with a noun phrase? For now we
consider only the relatively simple cases.

Supposing we have this list

[a b c d e] -> x;

In some problem we might wish to test might be to establish whether it
contains "b" and "d" occurring in that order. Now

member("b",x) =>
**
member("d", x) =>
**

tell us that both are present i.e.

member("b", x) and member("d",x) =>
**

but we know nothing of their relative positions in x nor indeed of
their intervening or surrounding context.

We can capture this ordering of "b" and "d" for example:

x(1) == "b" and x(2) == "d"

which specifies that "d" should immediately follow "b: in the list. In
fact the relationship that does obtain in X has the form

x(2) == "b" and x(4) == "d"

In this way we can specify any arbitrary patterning of elements in a
list structure. It will however  be very tedious to try all possible
combination of pairs of successive numbers. The situation gets even
worse if you merely want to test whether "d" occurs SOMEWHERE to the
right of "b", although you do not mind where exactly.

This need to be able to give a more complex specification of the
structure of a list is met by the procedure MATCHES that tests a given
list for the presence of some specified pattern.

-- Describing the shape of a list pattern ---------------------

The B, D example is of course but one of an infinite variety of
patternings that we might want to look for. So our specification of
a pattern has to be couched in a suitably descriptive language. The
pattern for 'B immediately followed by D' would be:

[== b d ==]

But the 'B followed somewhere by D' pattern would be specified like
this:

[== b == d ==]

Where '==' denotes any number of list elements (including no
elements). Thus all of these lists should meet that specification:

[a b c d e]
[b d]
[b a a c d f]

To test a given list, say X, for presence of this specified pattern
we'd call MATCHES like this

x matches [== b == d ==] =>
**

What result would you expect from the following:

x matches [a == e] =>
x matches [a == d == e] =>

variation in x - it's a rather sloppy fit: and often that is a useful
way of representing generality.

There are a number of ways in which we can tighten it up, when required.
We might for example want just one intervening element between B and D:

x matches [== b = d ==] =>
**

These two symbols == and = are basic descriptors of pattern shape
and we may think of them as 'Gobbling up' intervening list items. We
can call '=' Gobble-one and '==' Gobble-any. (These names were suggested
by the late Max Clowes.)

Gobble-one and Gobble-any help us characterise the linear shape of a
pattern. We may also want to characterise its structural organisation.
For example that the first element in the target list must itself be a
list - as it is in CUPBOARD for example.

cupboard matches [[==] blanket ==] =>
** true

And this device may of course be used to dig arbitrarily 'deep' into
a list structure.

The pattern is then a sort of picture with lots of missing details,
of the kind of list we are looking for.

-- Using variables in a pattern specification -------------------------

So far we've described our patterns in very literal terms. i.e. that
there needs to be a "B" and a "D", or a list etc. In practice the
items we want to include in our specification may have been
constructed by other procedures (and as we shall see by procedures
that use MATCHES). Typically these items will be the value of
variables.

Suppose we have a variable "box" whose value is a list representing the
contents of a box.

vars box = [shoes tins brushes] ;

And a variable cupboard corresponding to a cupboard that contains the
box and other things:

vars cupboard = [[shoes tins brushes] blanket hats coats umbrellas];

If we write

cupboard matches [box blanket ==] =>
**

The result is false because the first element of cupboard is not
the word "box" but a list which is the same as the value of the variable
box. We need to enrich the pattern specification language so as to
distinguish between words used literally and words used as variable
names. We do this with the up-arrow ^ prefix, as explained in the
chapter on lists. Thus

cupboard matches [^box blanket ==] =>
**

The use of ^ (up-arrow) in the pattern specification here is
the same as that introduced earlier. Thus

[box blanket ==] =>
** [box blanket ==]

But

[^box blanket ==] =>
** [[shoes tins brushes] blanket ==]

And it is of course only this latter version that matches CUPBOARD.

-- Matching a "segment" of a list -------------------------------------

Had the value of cupboard been

** [shoes tins brushes blanket pillow]

then that MATCH would have failed.

We need to 'strip off' the list brackets of the value of BOX if we
are to match this new kind of CUPBOARD, and we can do this by using
a double up-arrow:

[^^box blanket ==] =>
** [shoes tins brushes blanket ==]

This uses the value of the variable box to insert a collection of items
to form a SEGMENT of the list, rather than inserting a single list as an
ELEMENT of the enclosing list.

To illustrate the power of matches and the pattern language, consider
the following definition of the procedure ismember which could be
compared with the definition of iselement in Chapter 3:

define ismember(item, list) -> trueorfalse;
list matches [== ^item ==] -> trueorfalse
enddefine;

ismember(3, [ 1 2 4 ] ) =>
**
ismember(3, [ 1 2 3 4 ] ) =>
**
ismember("c", [ a b c d e]) =>
**

This uses the fact that matches returns a 'boolean' result, i.e.
either TRUE or FALSE.

-- Retrieving details of the target list ----------------------

In some of our examples we have merely been concerned to establish
whether a particular target list meets some pattern specification, where
that specification only cited various list fragments embedded within a
context whose precise composition was not germane to the recognition of
this key configuration.

We may however want to know what that context is, when a match is
obtained. For instance, a sentence analysing program which finds a
verb in a sentence may want to know what came before and after the
verb. It is also used in programs which interrogate the Pop-11
database not merely to see if a particular piece of information is
there, but also to find out exactly what it is. E.g. you may not
merely wish to find out if the database has an item of the form

[age fred ....]

you may also want to know what the age is.

Thus in recognising the ordered co-occurrence of "B" and "D" in the list

vars x = [a b c d e];

we might want to be 'told' what the value of the intervening list
element(s) is (are).

To set a variable say P to take on the value of  single list element
prefix the variable name with "?" Thus

vars p;
x matches [== b ?p d ==] =>
**
p =>
** c

Similarly to set the value of the variable to be some SEQUENCE of list
elements use "??" Thus:

vars q;
x matches [a ??q d ==] =>
**
q =>
** [b c]

Think of "?" as "get ONE element" and "??" as get ANY elements", by
analogy with "=" and "==".

Try the following, which gives LIST a new value, then uses it:

[i like talking to you] matches [i ??list you] =>
**
[you ^^list me?] =>
** [you like talking to me?]

This is typical of the sort of trick used by Eliza.

Whenever the MATCH fails because the list does not match the pattern the
queried variables may have their values altered in an unpredictable way
as part of the process of determining that the match fails.

[i like talking to you] matches [i ??list you alone] =>
**
list =>
** [like talking to you]

-- Using a "restriction" to control or check the match ----------------

The basic concept of matching as illustrated so far uses identity
between elements of the target list and corresponding elements of the
pattern specification. We can generalise this by requiring that a target
element have some specified PROPERTY.

For example in the ELIZA world, the occurrence of a word indicating
reference to the family e.g. "son", "sister", "father", "mother", etc.
in an input sentence is an important response-determining cue. To detect
that a list element belongs to such a set, rather than being identical
with a given pattern element, we can use a "restriction procedure" as an
affix to a queried variable in the pattern specification. Thus if we
have a procedure that produces TRUE when applied to family word and
false otherwise, then we can use it to restrict the value of "x" in the
following match:

vars x;
[my father loved me] matches [== ?x:family ==] =>
**
x =>
** father

[you remind me of my brother] matches [== ?x:family ==] =>
**
x =>
** brother

[you remind me of my car] matches [== ?x:family ==] =>
**

where FAMILY is a (previously-defined) procedure that might be something
like this:

define family(word) -> result;
member(word, [son sister father mother brother]) -> result
enddefine;

You can gain experience with MATCHES ?, ??, ^, ^^, and variables by
working through TEACH RESPOND.

-- Summary of match notations -----------------------------------------

Basic format:

list MATCHES pattern

Pattern specification can contain the following:

1) [cat mouse x 99 'string']
literal words numbers, strings, and other items to be
checked in the target list

2) =
The 'Gobble-one' spacer

3) ==
The 'Gobble-any' spacer

4) ^A
Put into the pattern an object which is the value of the
variable A. That object will then be compared with the
corresponding object in the target list.
^()
Put into the pattern whatever results from evaluation of
the expression.

5) ^^A
The variable A MUST have a list as value. Put into the pattern
all the elements of the list, for comparison with elements of
the target list.

6) ?A
Set the value of the variable A to be a single element in the
matching target list.

7) ??A
Set the value of the variable A to be a list containing a
sequence of elements in the target list.

8)  ?A:TEST
Only allow the variable A to match an element such that TEST(A)
is not FALSE.

9) ??A:TEST
Like (8), but the TEST is applied to a LIST of successive elements
from the target list to be matched against the variable A.

(Future versions of Pop-11 with a more sophisticated matcher will use

NOTE: If the predicate TEST in the last two cases returns not TRUE
but some other non-FALSE result, then the result will be assigned to
the variable A instead of the item or list of items from the target
list. For example, define a procedure to recognise a list of colours,
and return a list of their initials:

First a procedure to produce a one character word from a word:

define initial(word);
subword(1,1,word)
enddefine;

Use that to define a procedure that returns a list of initials if given
a list of colour words:

define all_colours(list) -> result;
;;; given a list of colour words return a list of single
;;;  character words, using the first character of each word.
lvars item;
for item in list do
unless member(item, [red green blue indigo violet orange])
then
false -> result;
return();
endunless;
endfor;
;;; create list of initials
maplist(list, initial) -> result;
enddefine;

all_colours([red square]) =>
**
all_colours([green red orange]) =>
** [g r o]

This can be used to transform the output of the matcher, because it
returns the transformed list rather than simply true. E.g.

vars colours;
[the big green blue red orange thing on the wall]
matches [== ??colours:all_colours thing ==] =>
**

colours =>
** [g b r o]

See HELP MATCHES/RESTRICTIONS

-- MATCHing on a corpus of lists - the DATABASE concept ---------------

The description of some task situation may take the form of a large
corpus of lists, representing propositions. For instance we might
know that B1, B2, ... etc are blocks, that each has a colour and a
size, and that some are on others. These facts could be represented
as a database consisting of a list of lists:

[[b1 isa block]
[size b1 big]
[colour b1 green]
[on b1 b2]
.........
]

We could also describe the contents of an image in terms of which
objects are in it what their properties are, and how they are
related. The library program SEEPICTURE builds up just such a list
representation of a PICTURE pattern to provide a basis for
recognition.

-- Adding and removing database items ---------------------------------

Since this facility is often required, Pop-11 provides a collection
of automatically loaded library procedures for manipulating lists of
lists. They all make use of a global variable 'database' which may
contain arbitrary information.

We can build up a DATABASE using ADD

vars database;
[] -> database;

database =>
** [[b] [a]]

Notice that items appear in reverse order to the order of ADDing.

More concisely  we can use ALLADD

database =>
** [[d] [c] [b] [a]]

remove([c]);
database =>
**[[d] [b] [a]]

The order of items in a call of ALLREMOVE is not important i.e. it does
not need to reflect the ordering of the DATABASE

allremove([[a] [b] [d]]);
database =>
** []

The procedure REMOVE will remove at most one item from the database,
even if it is given a pattern which matches several. Thus REMOVE([==]);
instead of removing everything, removes just one item. Moreover, REMOVE
will generate a MISHAP if it does not find one item to remove. Similarly,
ALLREMOVE will generate a mishap if it can't remove something for every
element of the list of patterns given to it as argument.

The procedure FLUSH is provided without these restrictions. FLUSH
deletes everything in the database that matches its argument, but if
there is nothing that matches, then FLUSH does nothing!

The argument given to FLUSH is a pattern specification, that is
FLUSH uses MATCHES to determine the list items that it will DELETE.
It is however very powerful in its action... it removes ALL the
matching DATABASE entries. Thus with the DATABASE [[D] [C] [B] [A]]
the action

flush([=]);

clears the DATABASE, thus:

database =>
** []

Thus in this situation FLUSH([=]) is equivalent to:

allremove([[a] [b] [c] [d]]);

Whenever the database contains only one-element lists, the command

flush([=]);

will remove them all.

Similarly

flush([==]);

will remove all lists from the database no matter what is in them. It is
therefore equivalent to

[] -> database;

-- Using "it" to record what was removed ------------------------------

After using FLUSH or REMOVE the variable IT will hold the item last
removed. E.g.

remove([dogs like == ]);
it =>
** [dogs like meat]

The procedure ALLREMOVE, uses the variable THEM instead. This will
be a list of all the items removed. Similarly, ADD updates IT, and

-- Finding items in the database ------------------------------

One of the most commonly used procedures is PRESENT, which takes a
pattern and returns true or false depending on whether there is
something in the database that matches the pattern. If the pattern
contains variables preceded by "?" or "??", and the match is true, then
the values of those variables will give information about the list
that matched the pattern. For example:

[the big red box] [the long square pole][the tiny blue flea]])
vars x y;

present([the ?x ?y pole]) =>
**
x, y =>
** long square

Exercise:  what will the values of x and y be after

present([the ?x ?y flea]) =>

-- -- How PRESENT works. -----------------------------------------------

It does this by trying to MATCH the pattern against every item in the
database. If the match is ever successful then true is returned as the
result of PRESENT, otherwise the result is false.

alladd([[a b c d] [d c b a] [a b d c]]);

present([== b ==]) =>
**

present ([== b c]) =>
**

Notice that PRESENT finds the 'first' matching item.

PRESENT is frequently employed in a conditional e.g.

if present(pattern) then action

The 'IF... THEN' construction 'uses up' the boolean value returned
before THEN i.e. try:

if present([== b ==]) then => endif;

The "STACK EMPTY" error message arises because Pop-11 treats the value
returned by PRESENT between "IF" and "THEN" as  or . So
the value is no longer there for "=>" to print out, and that produces
the error message.

-- Using "it" to record what was matched ------------------------------

The value returned by present when successful is TRUE. But that does not
determine what exactly matched the pattern in the database. For many
purposes however we will need to know what the matched item is for
example to use it in the THEN branch of the conditional. For this
purpose the DATABASE variable IT is set to have the value of the
matching item, when PRESENT finds something.

alladd([[a b c d] [d c b a] [a b d c]]);

if present([== b ==]) then
it =>
remove(it);
endif;
** [a b c d]

Thus we see that the item matched, and subsequently removed was the
first item in the database.

Note that it found only ONE item, matching the pattern, and removed
it. FOREACH, explained below, shows how you can search for ALL items
matching some pattern.

-- Retrieving values from within a matching ITEM ----------------------

Since all of the apparatus of MATCHES is utilised in those DATABASE
procedures, PRESENT can be used to set values of appropriately queried
variables in the pattern specification.

vars x;
present([?x b ==]) =>
**
x =>
** a
it =>

Notice that if "?" or "??" is used before a word in a pattern, then
that word should be declared as a variable name. Hence the "vars x;"
above.

If the variables in patterns are not declared to be local, to the
procedures which use them, then different procedures can mess each other
up. This applies to procedures which use MATCHES or any of the database
operations PRESENT, FLUSH, LOOKUP, REMOVE, etc.

-- Using LOOKUP to extract information from the database --------------

We do not always want to know what the matching item was. Sometimes we
will know in advance that an item matching the pattern is present in the
DATABASE and want only the value of some fragment of the item.

For this purpose the procedure LOOKUP is provided. It does not return
or  but merely sets the value of queried pattern variables
when a match is found, and causes an error if no match is found.

alladd([[a b c d] [d c b a] [a b d c]]);

lookup([= ?x b ==]);
x =>
** c

In the event of no match being found an error will result

lookup([?x == e]);
;;; MISHAP - LOOKUP FAILURE
;;; INVOLVING:  [? x == e]
;;; DOING    :  sysprmishap mishap lookup ......

Note that PRESENT is to MATCHES as LOOKUP is to -->. PRESENT and MATCHES
check a condition and return a true/false result, and may simultaneously
bind pattern variables. But only PRESENT searches over a list. LOOKUP
and --> do not return any result, and only LOOKUP searches.

procedure   returns           iterates over       mishap on
a boolean         the database        failure
---------------------------------------------------------
matches      yes                   no               no
-->          no                    no               yes
present      yes                   yes              no
lookup       no                    yes              yes

-- FOREACH: iterates over all items PRESENT matching a pattern --------

There will often be a need to find not just one matching item in the
DATABASE, (or to set the value of queried pattern variable for just
one matching item) but to find all of them. For this purpose the
looping construct FOREACH is provided, We can use it, for example to
find all the items in the database in which "b" precedes "a":

[[a b c d] [d c b a] [a b d c] [b d c a]] -> database;

foreach [== b == a ==] do
it =>
endforeach;

** [d c b a]
** [b d c a]

Note that FOREACH is a "syntax" word (like IF and DEFINE), not a
procedure name, and hence the pattern specification that follows
need not be enclosed in round brackets '(' ')'.

The general form of FOREACH is

FOREACH  DO  ENDFOREACH;

For example, to print out every item in the database representing
something blue:

vars x;
foreach [??x is blue] do
x ==>
endforeach;

Inside the  the variable IT is available to represent the
database item which has matched the pattern. E.g. suppose you have
various database entries of forms:

[p1 is a person]
[b3 is a block]
[c5 is a cat]

etc. Then, to print out all the blocks do:

foreach [??x isa block] do
x =>
endforeach;

you can use "[%" and "%]" to make a list of all the blocks:

[% foreach [??x isa block] do
x
endforeach
%] -> blocks;

Each time round the value of X is left on the stack and the [%...%]
brackets make a list of all of them. The variable IT can be used
each time round the loop to refer to the database entry which was
found to match the pattern given after FOREACH.

FOREACH can be followed by IN to specify a list other than DATABASE to
search in, i.e.

FOREACH  IN  DO  ENDFOREACH;

If you have access to a working Poplog system you can get more
information and examples in:

TEACH MATCHES; TEACH DATABASE; TEACH FOREACH; TEACH RIVER2;

-- Checking a set of patterns against the database --------------------

Just as ALLADD and ALLREMOVE can be given a list of patterns to add
or remove, similarly, ALLPRESENT can be given a list of patterns to
look for in the database. If it finds items for all of them it
returns a list of the found items (and also assigns it to the
variable THEM). Otherwise its result is false. E.g. to find a
grandson of TOM:

[dick father harry]
[tom father jack]
[bill father tom]
[jack father dick]]);

vars x, y;
if allpresent([[tom father ?x] [?x father ?y]]) then
y =>
endif;
** dick
them =>
** [[tom father jack] [jack father dick]]

For more summary information on the database procedures see:

HELP DATABASE,  HELP ADD,   HELP PRESENT,
HELP REMOVE,    HELP FLUSH, HELP LOOKUP.
HELP FOREACH,   HELP FOREVERY

-- Forevery: simultaneously satisfying a collection of patterns -------

Just as ALLPRESENT is a generalisation of PRESENT, so Pop-11
includes FOREVERY which is a generalisation of FOREACH, and allows
some fairly powerful manipulations of the database. In particular,
we can find all possible combinations of a SET of patterns in the
database. E.g. to find all paternal grandfather relations, i.e. all
combinations of the form

[?x father ?y][?y father ?z]

Here's an example

[
[dick father harry]
[tom father jack]
[bill father tom]
[dick father mary]
[jack father dick]] -> database;

vars x, y, z;
forevery [[?x father ?y] [?y father ?z]] do
[^x is the paternal grandfather of ^z] =>
endforevery;
** [tom is the paternal grandfather of dick]
** [bill is the paternal grandfather of jack]
** [jack is the paternal grandfather of harry]
** [jack is the paternal grandfather of mary]

Note that FOREVERY made sure that whatever matched "y" in in the two
patterns was the same.

The permitted formats of FOREVERY are:

FOREVERY  DO  ENDFOREVERY;

FOREVERY  IN  DO  ENDFOREVERY;

When 'IN ' is omitted, then the value of the variable DATABASE
is used as the database.

Another example: find all the blocks and print out their colours:

forevery [[?x isa block] [colour ?x ?col]] do
[^x is a ^col block] =>
endforevery;

Or to find all maternal grandfather relationships:

forevery [[?x father ?y] [?y mother ?z]] do
[^x is grandfather of ^y] =>
endforevery;

-- -- More powerful database-related mechanisms

In addition to these procedures the Pop-11 library contains some more
powerful procedures SCHECK and SCHOOSE, for matching a whole database
pattern against a database, and indicating whether the match was
partially successful, what was missing, what was surplus, etc. For
details see TEACH SCHEMATA

A simple expert system shell based on the matcher is described in
HELP NEWPSYS, and TEACH PSYSRIVER.

A more sophisticated version, POPRULEBASE was added in 1999. For information

uses newkit

then these commands will be available

TEACH RULEBASE
Tutorial introduction

HELP POPRULEBASE
More comprehensive overview (for experts)

-- -- LIB SUPER: A Prolog-like extension to Pop11

Poplog includes a full prolog system implemented in Pop11, using the syntax of
prolog. You can get information about it in these two Poplog files

TEACH PROLOG
Also available here
http://wwwcgi.rdg.ac.uk:8081/cgi-bin/cgiwrap/wsi14/poplog/pop11/teach/prolog
http://www.cs.bham.ac.uk/research/projects/poplog/doc/popteach/prolog

HELP PROLOG
http://www.cs.bham.ac.uk/research/projects/poplog/doc/pophelp/prolog
(A comprehensive list, at the University of Reading)

For a general introduction to Prolog, see, for example:

W. Clocksin and C.S. Mellish
PROGRAMMING IN PROLOG, Springer Verlag.

Although the Pop11 database procedures described earlier are very powerful
compared with what most programming languages provide. They are still, in
certain respects, not as powerful as the facilities built into the language
Prolog.

However, Pop11's LIB SUPER provides some of the additional power of prolog,
using the syntax of pop11 and its matcher. See these two files, which are
included in the poplog documentation as well as being online

TEACH SUPER_EXAMPLE
http://www.cs.bham.ac.uk/research/projects/poplog/teach/super_example

HELP SUPER
http://wwwcgi.rdg.ac.uk:8081/cgi-bin/cgiwrap/wsi14/poplog/pop11/help/super

Here's a taster from TEACH SUPER_EXAMPLE:

-- -- -- LIB SUPER: Some examples

;;; You can use 'mark and load range' commands in Ved or XVed
;;; to run these examples.

uses super

;;; startup an empty database
newdatabase([]);

;;; we can search for a person who is big

;;; declare a variable person
vars person;

;;; is there anyone small?
present([small ?person]) =>
**

;;; anyone big?
present([big ?person]) =>
**

;;; who was found?

person =>
** john

-- -- -- Printing out the SUPER database

At this stage, several things have been added to the database.

At any time you can print out the database, using Pop-11's  pretty-print
arrow (==>), like this

database ==>
** [[big [big john] [big fred] [big sally]]]

If you add some other facts the facts will be grouped according to their
first word.

;;; now look at the database
database ==>
** [[satellite [satellite moon]]
[star [star sun]]
[planet [planet earth] [planet saturn]]
[round [round moon] [round sun] [round saturn]]
[big [big john] [big fred] [big sally]]]

NOTE:
This grouping of database entries according to their first word
can save a lot of space and a lot of time, but it is not nearly
as sophisticated or as efficient as the techniques used in
professional database packages (e.g. mysql).

But SUPER's greater visibility and intelligibility makes it far
more suitable as a teaching tool: students can then explore
extensions and applications that would be very hard for them to
code with a 'real' database package.

POPRULEBASE uses a similar mechanism to SUPER and has been used for
serious a AI system which outperform many rivals on standard
benchmark tests.

-- -- -- Using 'which' to get complete information

;;; Previously used PRESENT to check one thing at a time
;;; We can find all the big persons using the WHICH command:

vars person;

which("person", [[big ?person]]) =>
** [john fred sally]

;;; you can also use 'foreach' to find all the heavy things, and do
;;; something to them one at a time.

;;; We use ?person as a variable to be set in a list by matching.
;;; We use ^person as a variable whose already set value is to be
;;; put in the list. We can't use "^" like that outside a list.

foreach [big ?person] do
[I know that ^person is big] =>
endforeach;

;;; That prints out:

** [I know that john is big]
** [I know that fred is big]
** [I know that sally is big]

;;; is anyone heavy?
which("person", [[heavy ?person]]) =>
** []

;;; the empty list is returned, so nobody is heavy.

;;; But we can add an inference rule saying, that if you need
;;; to find someone heavy, check if there's someone big

;;; now is anyone heavy?

which("person", [[heavy ?person]]) =>
** [john fred sally]

;;; So SUPER has *inferred* that each of john, fred and sally is heavy.
;;; But it has not stored that information in the database, as you
;;; can tell by printing out the database.

For more on SUPER see the TEACH and HELP files.

-- Some limitations of the Pop11 matcher --------------------------

The pattern matching facilities shown so far have serious
restrictions in that they will not work properly with sections, a
mechanism for separating variable scopes (a bit like 'packages' in
Common Lisp), and the pattern variables also cannot be used with
lexically scoped variables, which is why all pattern variables have
to be declared with "vars", not "lvars". (See HELP LVARS).

-- -- LIB FMATCHES overcomes some limitations of the matcher

There is a modified version of the matcher described in HELP
FMATCHES which partially overcomes these restrictions, though
FMATCHES is no longer an infix operator like MATCHES, but a new
syntax word.

FMATCHES is superseded by the DOESMATCH library and the READPATTERN
library, both included by default in the current version of Linux poplog,
along with the pattern prefix "!", which allows pattern variables to be
lexically scoped variables.

-- -- The POP11 pattern prefix !

(For expert programmers.)

This mechanism is described in detail in
HELP DOESMATCH

Warning: The pattern prefix is incompatible with LIB SUPER. So if
you have tried the SUPER examples above, you should leave Pop11, and
restart before trying the next few examples.

For many novice programs the pattern prefix is not essential, but for more
complex programs the ability to use lexically scoped variables as pattern
variables is essential, to prevent interference between different program
fragments, defined in different sub-programs, using the same variable
non-locally.

For this reason, in Birmingham, after the introduction of the
pattern prefix we started using it in most of our teaching examples,
even though it was not strictly necessary.

This mechanism is not described in any of the published books on
pop11.

Here are some examples from HELP READPATTERN:

-- -- -- list_between

E.g. here's a procedure to make a list of the items between two
specified elements in a list.

;;; Make sure readpattern has been compiled
;;; Not really necessary in current versions of Poplog (e.g. V15.6 onwards)

define list_between(item1, item2, list) -> found;

;;; Here found is automatically declared as lvars, as are the input variables
;;; item1, item2, list

;;; note the use of the pattern prefix "!"

unless list matches ![== ^item1 ??found  ^item2 ==] then
false -> found;
endunless;

;;; If the match is successful, the list of items between
;;; ITEM1 and ITEM2 in the list will be assigned to the
;;; variable FOUND, and returned as result of the procedure.

;;; Otherwise false is the result returned.

enddefine;

;;; Now test the procedure

vars words = [a b c d e f g];

list_between("a", "g", words) =>
** [b c d e f]

list_between("c", "g", words) =>
** [d e f]

list_between("b", "b", words) =>
**

list_between("g", "e", words) =>
**

Note that the value returned by the procedure is the value of the output
local variable FOUND, which is a lexical variable, which is given a
value by matches when the match is successful. This works only
because of the use of the pattern prefix "!".

-- -- -- Without the prefix "!"

(Next bit only for expert programmers.)

Try without the pattern prefix

define list_inner(item1, item2, list) -> found;

unless list matches [== ^item1 ??found  ^item2 ==] then
false -> found;
endunless;

enddefine;

vars words = [a b c d e f g];

list_inner("a", "g", words) =>
;;; DECLARING VARIABLE found
;;; IN FILE pop11-primer.txt
;;; LINE 17154
** 0

It declared the non-lexical (global) variable "found" and returned
the default value of the lexical variable found, namely 0.
But the global variable has this value
found =>
** [b c d e f]

That is terribly confusing, explaining the need for "!"

(For complete illumination see TEACH VARS_AND_LVARS !)

As far as I know no other language offers this kind of flexibility
in use of lists both as data-structures and as code items when they
contain pattern variables, apart from Prolog. (Common Lisp may have
features that I have not encountered that are equivalent to this.)

A consequence is that it is hard in most languages to build packages
like Poprulebase.

-- CHAPTER.8 AN AI APPLICATION: A GENERAL PROBLEM SOLVER

As explained in many AI text books, it is often necessary to search an
abstract space in order to find a solution to a problem.

This chapter, which will be of use only to fairly experienced
programmers, uses a subset of some of the contents of a Pop-11 "teach"
file developed by the author, to define an illustrative general purpose
problem solver which searches for a solution to a variety of problems.

In order to use the procedure solve_problem you have to choose a
representation for your problem and the search space it defines. That
requires choosing a representation for each state, including the initial
state, the goal state or goal states if there are several alternative
ways of solving the problem, and other intermediate states.

You also need to define four procedures, as follows:

-- Procedures to be supplied by users

-- . is_goal_state

is_goal_state(state, goal) -> boolean

This is given a state, and a specification of the current goal and
returns true if the state is acceptable as a goal state, otherwise
false. This procedure will be different for different sorts of problems.

-- . next_states

next_states(state) -> newstates;

The procedure next_states is given a state and returns a list of states
that can be reached in one step from that state. The procedure will be
have to be defined differently for different problems.

-- . same_state

same_state(state1, state2) -> boolean

This procedure is required so that the problem solver can tell whether a
particular new state is equivalent to one that has previously been
examined, so that time is not wasted examining it again and trying to
explore its successors. Since the notion of equivalence will depend on
the kind of problem and how states are represented, this has to be
defined by the user.

If this procedure is provided, then the general problem solver can keep
a "history" list of the states that have already been examined, and
whenever new states are generated it can discard any of them that are
"the same" as a state already on the history list.

-- . insert_state

insert_state(state, oldstates) -> newstates

This procedure can embody some "heuristic" information. It is given a
new state (e.g. something produced by the procedure next_states) and
list of states waiting to be explored, and it returns a new list of
states, with an order which represents the best current guess as to
which one should be examined first. For example it is often useful to
prune a search space by working first on items that are going to be most
difficult to fit into a complete solution, so that those that are
unusable are quickly eliminated from further combinations of items.

-- . is_in_list

The problem solver described below needs this utility procedure which
can be applied to a state, a list of states, and the user's procedure
same_state, to check whether the first state is equivalent to one of
those in the list. It returns a true or false result.

define is_in_list(newitem, list, sameitem) -> boole;
;;; Return true if and only if the newitem is the same as something in
;;; in the list, as compared using the procedure sameitem

lvars procedure sameitem;   ;;; declare it as a procedure, for speed

lvars olditem;

for olditem in list do
if sameitem(newitem, olditem) then
;;; found an olditem which is the same, so return with true
true -> boole;
return();
endif
endfor;
;;; did not find anything that was the same
false -> boole
enddefine;

-- The definition of solve_problem

If the user has defined the above procedures they can be given to the
following general problem solver. It takes six arguments and produces
a result which is the goal state if one is found and otherwise the
value FALSE.

The first argument is a representation of the initial state. The second
is a representation of the goal to be achieved. The next four arguments
are procedures, which are the users versions of the four procedures
listed above: the goal recogniser, the procedure for generating new
states from old ones, the state equivalence recogniser, and the
procedure to insert a new state into a list of states.

Here is one of many ways to define such a problem solver:

define solve_problem
(initial, current_goal, isgoal, nextstates, samestate, insert)
-> result;

lvars
initial,        ;;; the initial state
current_goal,   ;;; the second argument for isgoal
;;; four procedures defining the problem and a strategy
procedure (isgoal, nextstates, samestate, insert),
result;

lvars
alternatives = [^initial],  ;;; the list of alternative states
history = [] ;              ;;; the list of previous states

vars current_state, rest;       ;;; use "vars" for pattern variables

repeat
if null(alternatives) then
;;; failed
false -> result;
return();
else
alternatives --> [?current_state ??rest];
rest -> alternatives;

;;; Check if current_state is a goal state
if isgoal(current_state, current_goal) then
;;; problem solved
current_state -> result;
return();
else
;;; Keep a history list, avoid circles
[ ^current_state ^^history ] -> history;

;;; generate successor states to current_state
lvars states;
nextstates(current_state) -> states;

;;; put all the "new" states onto the alternatives list
lvars state;
for state in states do
unless is_in_list(state, history, samestate) then
insert(state, alternatives) -> alternatives
endunless;
endfor;
;;; now go back to the beginning of the repeat loop
endif
endif
endrepeat
enddefine;

-- Using solve_problem to solve a simple problem

Suppose you have a set of parent child relationships stored in a
database (see TEACH * DATABASE).

For example you could set up a database like this:

define start_family_tree();
[
[father [tom jones] [dick jones]]
[father [tom jones] [sue smith]]
[mother [ginny jones] [dick jones]]
[mother [ginny jones] [sue smith]]
[father [dick jones] [mary jones]]
[mother [sue smith] [joe smith]]
[mother [sue smith] [fred smith]]
[father [jack smith] [joe smith]]
[father [jack smith] [fred smith]]
[father [fred smith] [angela green]]
[mother [angela green] [willy green]]
] -> database;

enddefine;

Then the following command will set up the initial database:

start_family_tree();
;;; print out database to check
database ==>

Now suppose you had to find out whether someone A is an ancestor of
someone else B.

One way you could do that is set up a search space consisting of a start
node A, and all paths from A to descendents of A. Then the solve_problem
procedure could be given the task of searching for a path through the
family tree starting from A and ending with B. If such a path is found,
it would answer the question positively: A is an ancestor of B.

You could represent a state in the search space as consisting of a
list of names representing a path found so far through the family tree.
For example if we wanted to find out whether [ginny jones] is an
ancestor of [angela green] we would have a succession of states showing
routes up the tree to ginny jones thus

[[ginny jones]]                 ;;; initial state
[[dick jones] [ginny jones]]    ;;; a successor state
[[sue smith] [ginny jones]]     ;;; another successor state

If we use this representation, then it is easy to tell whether the
problem has been solved: check whether the target person B is the first
item of the list.

Thus we can define the following procedures to use with solve_problem

define is_ancestor_goal(state, target) -> boole;
;;; The state is a list of names defining a route up the family tree
lvars state, target, boole;
state matches [^target == ]  -> boole
enddefine;

However, we also have to create a procedure for generating new states
from a given state. Remember that a state is a list of names of people

[personN ... person3 person2 person1]

where person1 represents a parent of person2, person2 a parent of
person3, and so on. Person1 is the one given as the original alleged
ancestor, and personN is the latest person found in searching down the
tree from person1.

Then in order to find successors to this state we need to find
individuals who are immediate descendants of personN, and form
a set of new routes up the tree from each of them. First we need a
procedure to find the immediate descendants. We can use the database
searching procedure foreach (described in TEACH FOREACH)

define immediate_descendants(person) -> list;
lvars person, list;
vars next;  ;;; a pattern variable used with foreach below

;;; start making a list
[%
;;; first collect all those to whom person is father
foreach [father ^person ?next] do
next;   ;;; just leave the next person on the stack
endforeach;

;;; now collect all those to whom person is mother
foreach [mother ^person ?next] do
next;   ;;; just leave the next person on the stack
endforeach;

%] -> list
enddefine;

You can test this as follows

immediate_descendants([ginny jones]) =>
** [[dick jones] [sue smith]]
immediate_descendants([sue_smith]) =>
** []

Using the procedure immediate_descendants we can define a procedure to
create extensions to a state represented as a route up the tree

define family_next_states(state) -> newstates;
lvars state, states;
;;; make a list of new states that start with one descendant
;;; and the rest of state

lvars nextpeople, person;
immediate_descendants(hd(state)) -> nextpeople;

;;; Now make a list of the new states
[%
for person in nextpeople do
;;; make a new state and leave it on the stack, to go into
;;; the list being created by [% ... %]
[^person ^^state]
endfor
%] -> newstates

enddefine;

Now test it

family_next_states([[ginny jones]]) ==>
** [[[dick jones] [ginny jones]] [[sue smith] [ginny jones]]]

Note that the output was a list of TWO lists.

[[dick jones] [ginny jones]]

and

[[sue smith] [ginny jones]]

Try extending the first list:

family_next_states([[dick jones] [ginny jones]] ) ==>
** [[[mary jones] [dick jones] [ginny jones]]]

This time there is only one extension, containing three names. You may

We now need a test for whether a state is the same as one we have tried
before and for this problem it is easy - just see if the two states are
the same. (It is not always that easy.)

define family_same_state(state1, state2) -> boole;
state1 = state2 -> boole
enddefine;

And finally we define the simplest possible state insertion procedure
for combing a new state with a list of states: just put it at the front,
so that it will be examined next. (This defines a depth first search
strategy).

define family_insert(state, states) -> newstates;
[^state ^^states] -> newstates
enddefine;

You should now be able to use the solve_problem procedure to see whether
one person is a descendant of another. We can define a new procedure
called check_ancestor which does the work, as follows:

define check_ancestor(person1, person2) -> result;
;;; use solve_problem to do the work
solve_problem
([^person1],        ;;; start state (must be a list with a name)
person2,            ;;; goal state information
is_ancestor_goal,   ;;; goal state recogniser
family_next_states, ;;; generator for next states
family_same_state,  ;;; circle detector procedure
family_insert       ;;; insertion procedure
) -> result
enddefine;

;;; Now test it
check_ancestor([ginny jones], [mary jones]) ==>
** [[mary jones] [dick jones] [ginny jones]]

;;; Compare this case, with a different target descendant
check_ancestor([ginny jones], [tom jones]) ==>
**

Try some other tests using an extended version of the database.

NOTE All this apparatus is already provided in Prolog and in
LIB Super.

By implementing such search mechanisms yourself you can add
mechanisms to take advantage of known features of the problem
domain, though that will not be illustrated here.

-- Exercises

1. The above strategy is not always the most efficient. See if there are
ways of improving it e.g. by re-defining the next states generator or
the insertion procedure.

2. Try using the above problem solver to set up a route-finding
program,
and then trying to find a route between any two towns. If you want the
shortest route to be found you will have to have distance information
and the insert procedure or the next states procedure, or both could use
the distance measure to order the states, so that shorter routes are
tried first. Text books on AI define alternative algorithms for doing
this sort of thing.

3. Try using the problem solver to solve the problem of selecting some
blocks from a pile of blocks to build a tower of exactly a given height.
E.g. you may be given a list of numbers representing the heights of the
available blocks:

[3 16 12 22 5 5 24 14 8 7 22 11]

and the task of finding blocks to make a tower exactly 30 units high.

(How would you do it?)

4. The above problem solver stops as soon as it finds a solution. If
for some reason you wish to look for another solution to the same
problem that could be very wasteful. Try extending the procedure so
that it not only returns the solution, but enough information about
what it has done so far to enable the search to be re-started with
that information. This will require a change to the procedure to
allow it to be run with information saved from a previous run, which
might default to [].

(This 'back-tracking' capability is one of the features of Prolog,
and LIB SUPER.)

-- CHAPTER.9 RECORDS, VECTORS AND OBJECTCLASS

This chapter is about different ways in which users can extend the
variety of types of data-structures their programs use, and also
about the associated procedures that are created, either automatically
or explicitly.

Records and vectors have been part of the language for many years.
Objectclass is a recent extension providing ``Object oriented''
programming facilities.

-- Records

A recordclass is a class of objects all of the same general structure,
where each object contains zero or more fields that can contain data. A
record is an instance of a recordclass. All instances of the same class
have the same number of data fields.

Examples of recordclasses that are predefined in Pop-11 are pairs,
created by conspair, which are used for lists, and references, created
by consref. E.g. all pairs have two fields, all refs have one field.

A field may be "full", i.e. unrestricted in type, and therefore able to
contain any legal Pop-11 data-type, or restricted, e.g. to 7 bit
integers, or 16 bit decimals, etc.

Each record class has an associated "key" and a family of procedures, as
follows:

o A constructor procedure, for creating new instances (e.g. conspair)
o An exploder (or destructor) which can be applied to an instance
and puts all of its contents on the stack (e.g. destpair)
o A recogniser
o A collection of accessor/updater procedures, one for each field
in the recordclass. (For instance pairs have front and back, and
their updaters.)
o A class_print procedure for printing instances of the class.
(The class_print procedure for pairs, knows about printing
list structures using "[" and "]")
o A class_apply procedure for deciding what to do if an instance
is applied to some other object, as if it were a procedure.
(The class_apply procedure for pairs is invoked if you apply
a list to an integer N. It returns the N't item of the list.)

Each key is itself an instance of a special recordclass data-type called
keys, and its contents provide a lot of information about the class and
its instances.

In addition to the class-specific procedures there are generic
procedures that can be applied to instances of many different
data-types.

-- Defining new record types in Pop-11

The procedure conskey provides the most general mechanism for creating
new record classes (and new vector classes). However there are two
syntax words that are generally easier to use.

-- -- DEFCLASS and RECORDCLASS

The defclass construct defined in REF DEFSTRUCT can be used to create
other new record classes or new vector classes (see below for vector
classes). The syntax word "defclass" is defined in the autoloadable
library, on the basis of conskey.

However, for many purposes the older recordclass construct can be used
as a simpler mechanism for defining new record classes. ("recordclass"
is also a library syntax word defined in terms of "conskey").

-- -- An example: recordclass point3D

Suppose it were necessary to represent points in 3-D by means of four
element triples, one for each coordinate of the point and one for the
colour. The corresponding recordclass could be defined thus:

recordclass point3D point_x point_y point_z point_colour;

The newer syntax for this, using defclass would appear thus:

defclass point3D {point_x, point_y, point_z, point_colour};

As mentioned above, this automatically creates a family of new
procedures associated with the new recordclass, including conspoint3D,
destpoint3D, ispoint3D, point_x, point_y, etc.

An instance of the class can then be created using the procedure
conspoint3D and its components can be accessed or changed using the
field selector/updater procedures whose names correspond to the field
names above. For example, create two points, one at the origin:

vars
point1 = conspoint3D(0, 0, 0, "green"),
point2 = conspoint3D(10, 10, 10, "red");

;;; print them out
point1 =>
**

point2 =>
**

point_colour(point2) =>
** red

"yellow" -> point_colour(point2);

point2 =>
**

-- -- When should records be used?

Lists (and vectors, explained below) can be used whenever records are
used. However, records have certain advantages in some contexts. Records
are are used in preference to lists when:

o Very large numbers of instances are to be created: records
normally take less space in memory than the corresponding lists

o Elements of the records need to be accessed and updated rapidly.
Accessing or changing the fourth element of a list normally takes
longer than accessing or updating the fourth element of a record.
That is because with lists it is necessary to "chain" down the
list links, whereas the Nth component of a record can be accessed
in one go. (Using offsets from the beginning of the record.)

o Run time type-checking is desirable for robustness or debugging.
If you attempt to access the fourth element of a list it will work
as long as the list has four or more elements, even if something
has gone wrong and the wrong sort of list has been found. If you
apply a recordclass field accessor to the wrong sort of structure,
even if it has the right number of fields, this will produce a
run time error message. For example:

front(point1) =>
;;; MISHAP - PAIR NEEDED
;;; INVOLVING:
;;; DOING    :  sysprmishap mishap front .....

Lists are particularly useful when you wish to extend a structure by
inserting new items in the middle, or when you wish to have a number
of structures with shared "tails", as in these examples:

vars
list1 = [a b c],
list2 = [d e f],
list3, list4;
list1 =>
** [a b c]
;;; Extend list1 by adding a new item after "a"
conspair("item", tl(list1)) -> tl(list1);
list1 =>
** [a item b c]

;;; Make two new lists that both share list2 as their tail

[apple ^^list2] -> list3;
[orange ^^list2] -> list4;
list3 =>
** [apple d e f]
list4 =>
** [orange d e f]
;;; they have identical tails, sharing memory
tl(list3) == tl(list4) =>
**

That cannot be done with vectors or records.

-- Defining new vector types in Pop-11

A vector class is a class of data whose instances may be of different
lengths, though once an instance is created, its length cannot be
changed.

Pop-11 includes two main built in vector classes, namely
strings and vectors. A string is an instance of a vector class that
is constrained to contain an ordered set of characters, i.e. 8-bit
integers. Strings may be of different lengths, but each component
of a string must be an 8-bit character. E.g.

'a tiny string'         'a much longer string of characters'

Ordinary Pop-11 vectors can also be of different lengths, but their
contents are unconstrained.

{1 2 3}     {1 2 3 a vector with numbers [words and] [lists]}

Vectors play a major role in the construction of arrays. See REF ARRAYS
Roughly speaking a multidimensional array in Pop-11 is a combination of
a one dimensional vector and a procedure for mapping between the high
dimensional array and the low dimensional vector.

-- -- Using DEFCLASS and VECTORCLASS

The defclass construct described in REF DEFSTRUCT can be used to create
new vector classes as well as new record classes. However it is often
simpler to use the vectorclass construct.

-- -- Example of creation of a new vector class.

This example is based on HELP VECTORCLASS. The imperative

vectorclass short 16;

declares a new vector class called "short" which is restricted to
containing 16 bit integers in its fields. This creates procedures

initshort, consshort, destshort, isshort
subscrshort, fast_subscrshort,

and declares the variable

short_key

with the new key as its value.

The newer syntax for doing this uses defclass, as follows:

defclass short :16;

To create an instance of short, with 32 fields do this:

vars shortie = initshort(32);
shortie =>
**

By default the number 0 is put into each of the fields of a newly
created short vector. But this can be changed, e.g. by using the updater
of the subscriptor function subscrshort:

99 -> subscrshort(3, shortie);
shortie =>
**

Because of the use of the number "16" in its declaration, vectors of the
class "short" can only contain integers in the range 0 to (2 ** 16) - 1.
Attempting to assign something else will cause an error. E.g.

"cat" -> subscrshort(5, shortie);

;;; MISHAP - INTEGER 0 TO 65535 NEEDED
;;; INVOLVING:  cat
;;; DOING    :  subscrshort ....

By contrast, the word "undef" is used as the default value for fields of
unconstrained vectors. For example, create a five element ordinary
vector:

vars vec5 = initv(5);

vec5 =>
** {undef undef undef undef undef}

Ordinary vectors have associated procedures initv, consvector, isvector,
subscrv, destvector. See REF VECTORS

The anomaly that some of the names end in "v" and some in "vector" is a
historical accident. Similarly for strings the corresponding procedures
are inits, consstring, isstring, subscrs, deststring. (See REF STRINGS).

For creating ordinary vectors the 'curly braces' can be used to simplify
the syntax.

There are several procedures that apply equally to different sorts of
vectors, notably <> which can be used to join two vectors of the same
type, e.g. two strings, or two full vectors:

'one string ' <> 'and another' =>
** one string and another

{one vector} <> {and another} =>
** {one vector and another}

As explained above, there are other generic procedures that apply
equally to vectors and records, e.g. appdata, fill, explode, datalist,
copydata.

-- OBJECTCLASS: an Object-Oriented extension to Pop-11 ----------------

If it is not already included, or you are not sure whether it is
already included, all you need do to make sure it is compiled is to

uses objectclass

LIB OBJECTCLASS makes available an object-oriented programming (OOP)
extension to Pop-11. This provides a natural extension to the notion of
a recordclass with the added features:

o Different classes can share fields, and associated procedures.

o Information can be inherited from one class to other classes (its
sub-classes). In Objectclass ``multiple inheritance'' is supported, so
that classes can inherit from more than one superclass.

o Procedures (known as methods) can be defined which behave differently
depending on the classes of their arguments. This is already true of
some built in procedures: e.g. the arithmetic operators such as + behave
differently depending on whether their arguments are integers,
bigintegers, decimals, ratios, etc. Because their behaviour depends on
the classes (or types) of more than one argument they are sometimes
known as ``multi-methods''. Objectclass includes multi-methods.

o Object Oriented programming also adds an element of ``data
encapsulation'' or ``data hiding'' in that details of an implementation
of a particular type may be hidden from the users of that type. (This is
not unique to OOP: it is an aspect of all good programming, and was
already an aspect of vectors and records in Pop-11.)

Some OOP systems, e.g. Smalltalk, are based on the notion of "message
passing". This is not used by Objectclass: it follows the Common Lisp
Object System (CLOS) in using multi-methods instead. All the behaviour
of a message passing system can be obtained as a special case.

The Objectclass library is remarkable in the way that it neatly maps OOP
ideas onto existing Pop-11 ideas.  The correspondence of ideas is as
follows :-

methods:
procedures, which act according to the type of their
arguments.

instances:
records, the instance variables of which are simply the
fields of the record and are accessed by appropriate methods.

classes:
keys, although the keys that  play the role of classes are
given some extra fields (via hidden properties) so that they can
provide inheritance of behaviour.

Because this is a natural mapping, the overhead of a method call is
relatively low.  This means that the objectclass package provides an
efficient means of doing object-oriented programming.

You can get an introduction by looking at TEACH OBJECTCLASS_EXAMPLE.
More detailed technical information is provided in REF OBJECTCLASS.

For more on the general idea of Object Oriented Programming (OOP),
which has a number of different interpretations, and some history,
see TEACH OOP

-- -- Some examples of the use of Objectclass

Here is a simple definition for an objectclass to represent people. We
assume each person has a name, an age and a sex. The class definition
has "slots" for each of these. We can specify default values for
some of these attributes, as in the following example:

uses objectclass;

define :class person;
slot person_name = "no_name";
slot person_age  = 0;
slot person_sex;
enddefine;

Slots for which no default value is provided will have the word "undef"
as value.

You can then use this to create an instance of the class. Various
syntactic forms are available for this. Here is one of them, to create
an instance of class person, where the variable xxx will have the new
instance as its value:

define :instance xxx:person;
person_age = 27;
person_sex = "female"
enddefine;

;;; look at the value of xxx
xxx =>
**

;;; xxx can be given a name, as if it were a record with a field
;;; accessor/updater person_name

"mary" -> person_name(xxx);
xxx =>
**

-- -- Defining an objectclass method

Objectclass methods are procedures that act differently depending on the
types (keys) of their arguments. Compare the way the Pop-11 operator
"<>" can be applied to words, lists, strings, procedures, etc.

Different definitions of a method are needed for each combination of
objectclasses. For example, you could write a method for giving a person
a birthday.

define :method birthday( p:person );
lvars age;
person_age(p) + 1 -> age;
age -> person_age(p);
[Happy birthday ^(person_name(p)) - now aged ^age] =>
enddefine;

This method can be applied to xxx

person_age(xxx) =>
** 27

birthday(xxx);
** [Happy birthday mary - now aged 28]
person_age(xxx) =>
** 28

It would be possible to define a different version of the "birthday"
method for cars. For example, the car version might print out a reminder
to get the the car's licence renewed and its insurance revalued.
Similarly if "child" were a subclass of "person" then a special birthday
method could be defined for instances of child and it would take
precedence over the default method for person. E.g. it might light some
candles and sing a song.

-- -- Defining a subclass of a class

We can define a new subclass of persons, called adults, with default age
18, who are able to have a spouse, as in the next example. The spouse
may be nonexistent, which we'll make the default, represented by the
boolean false. Note that the second line of this definition specifies
that the adult class is a subclass of class "person". That means that
all the slots and methods previously defined for persons will

is person;                      ;;; specify superclass
slot person_spouse = false;     ;;; and additional slot
slot person_age = 18;           ;;; A new default age
enddefine;

person_sex = "male";
enddefine;

Let's give yyy the name "fred".

"fred" -> person_name(yyy);
yyy =>
** >

define a method called marry, that is applicable to two adults and makes
each of them the spouse of the other.

The 2D graphical extension to Poplog RCLIB, gives many more examples, used for
defining objects that can be useful components of graphical interfaces,
some of whose methods are invoked by actions performed by the user with
a mouse.

See
TEACH RC_LINEPIC

A wide variety of examples is provided in

TEACH RCLIB_DEMO.P

This file gives a more complete overview
HELP RCLIB

There are examples of what can be done using RCLIB here:

http://www.cs.bham.ac.uk/research/projects/poplog/figs/rclib/

RCLIB is used as the graphical interface in the SIM_AGENT library,
described here:

http://www.cs.bham.ac.uk/research/projects/poplog/packages/simagent.html

[To be continued]

-- APPENDIX
-- -- Additional topics and relevant documentation files

The previous chapters merely provide an introduction to the Pop-11
language. A more complete definition can be found in the online Poplog
REF files.

The rest of this section provides some pointers to further information
that might be useful, though it does not aim at completeness. There
is lots more documentation in poplog than is listed here.

Words and identifiers

words, the dictionary, identifiers, cancel, synonyms,
valof, idval, identprops, identtype, sections
(REF * WORDS, REF * IDENT, REF * SECTIONS))
(HELP * WORDS)

Ascii character codes, special graphic codes in VED

HELP * ASCII, REF * ITEMISE/Graphics

Data structures, classes,

defclass, recordclass, vectorclass keys, conskey, class_print,
class_apply, etc.
(REF * DEFSTRUCT, HELP * RECORDCLASS, REF * DATA, REF * KEYS)

Control facilities for use in Pop-11 procedures

chain, chainto, chainfrom, breakto, breakfrom, catch, jumpout, etc.
(REF * PROCEDURE, HELP * CONTROL)

Character and item streams

discin, discout, charin, charout,
itemiser, incharitem, proglist
macros, syntax words, and code planting procedures
(REF * CHARIO,  REF * ITEMISE)

File handling

syscreate, sysopen, sysread, syswrite, sysdelete, pop_file_versions
discin, discout, discappend
(REF * SYSIO)

Pipes and mail boxes

syspipe, pipein, pipeout
(REF * SYSIO)

Arrays

newarray, newanyarray, arrayvector, boundslist
(REF * ARRAYS)

Properties (hashed arrays)

newproperty, newanyproperty, newmapping

Interrupt handling

signal handling (sys_send_signal, sys_signal_handler)
(See REF * SYSTEM, REF * SIGNALS)

Active variables (with associated procedures that run when the variable
is accessed or updated).

HELP ACTIVE, HELP DLOCAL, REF IDENT
REF * active, * nonactive

Dynamic local expressions (expressions whose values are automatically
accessed and saved on procedure entry and restored via updater
procedures on procedure exit):

HELP DLOCAL
REF VMCODE has two relevant sections, entitled
--  Dynamic Local Expressions
-- More On Dynamic Local Expressions

Processes ("lightweight processes")

consproc, consprocto, runproc, suspend, resume
(REF * PROCESS, HELP * PROCESS,
HELP * ACTOR (may be called NEWACTOR))

Library mechanisms,

document browsing facilities, vedgetsysfile
Different categories of documentation and libraries
private help (etc) libraries
(REF * LIBRARY)

'fast_' procedures. Efficiency "tips"

See HELP * EFFICIENCY, REF * FASTPROCS

The garbage collector and memory management procedures.

sysgarbage, popgcratio, popmemlim, pop_callstack_lim
(REF *SYSTEM)

Error handling and warnings.

(REF * EXCEPTION)

Timing facilities

time, profile, timediff, sys_timer,
(See REF * TIMES)

Debugging, tracing and profiling aids

(REF * TRACE, HELP * DEBUGGER, HELP * PROFILE)

Printing

pr, syspr, sys_syspr, =>, ==>, pop_pr_quotes, pop_pr_radix
(REF * PRINT)

VED as a general purpose front end

(REF * VEDPROCS, REF * VEDCOMMS, REF * REGEXP from Version 14.5)

Calling external procedures

(HELP * EXTERNAL
REF * EXTERNAL, REF * EXTERNAL_DATA, REF * DEFSTRUCT)

Saved images

syssave, sysrestore, sys_lock_system
(REF * SYSTEM, HELP * MKIMAGE, HELP * SYSSAVE)

Initialisation, and startup files.

init.p, vedinit.p vedinitfile, vedfiletypes etc.
(REF * SYSTEM, REF * VEDTERMINALS
HELP * INITIAL, HELP * TERMINAL, HELP * VEDFILETYPES)

Exiting Poplog

sysexit and related procedures, popexit, vedpopexit
ved_xx, ved_qq
(REF * SYSTEM)

Syntactic sugar available in Pop-11

switchon
form
for_form
prefix

(and many more, e.g. in poprulebase)

Defining new define_forms

HELP * DEFINE_FORM

Defining new looping constructs

HELP * FOR_FORM

A selection of useful or interesting library packages

sets
profile
showtree
vturtle/turtle
grammar/tparse/facets
format
msblocks
prefix

Programming style in Pop-11

(TEACH * PROGSTYLE, HELP * EFFICIENCY)

The X window facilities in Poplog Pop-11 are very rich and complex.

HELP * X
REF * X
TEACH * RC_GRAPHIC
TEACH * PROPSHEET
(Warning: up to version 14.2 the latter is incomplete!)

HELP RCLIB

For a more complex list of detailed REF files expanding on the
definition of Pop-11 see REF * INDEX

For a list of Pop-11 ref files concerned with the X interface see

REF * XPOPINDEX

The file HELP NEWS gives information on recent changes to Poplog up
to Poplog version 15, and includes references to older versions of
the file giving a reverse chronological history of the development
of Pop-11 and Poplog. There are other news files for Prolog, Lisp,
ML, and X.

The most recent news file for poplog can be found here:

http://www.cs.bham.ac.uk/research/projects/poplog/latest-poplog/CHANGES.txt
http://www.cs.bham.ac.uk/research/projects/poplog/latest-poplog/CHANGES-PACKAGES.txt

-- -- Overview of REF files

The following is an extract from REF * REFFILES

REF *INDEX
--- List of REF files

REF *ARRAYS

REF *ASYNC
Describes asynchronous traps and signals in Poplog.

REF *CHARIO

REF *DATA
---  General  data  procedures  and  datatypes  (See  also
HELP *PROGRAMMING)

REF *DEFSTRUCT
--- POP11 syntax for defining and accessing structures

\$usepop/pop/ref/doc_index
--- This is not a ref file, as explained above.

REF *DOCUMENTATION
--- The Poplog online documentation system

REF *ENVIRONMENT_VARIABLES (Unix only)
--- Environment variables defined by the Poplog system.

REF * EXCEPTION
--- Poplog exception  (error  and  warning)  handling.
(See   also HELP * MISHAP, HELP * PROGRAMMING.)

REF *EXTERNAL
HELP *EXTERNAL, *PROGRAMMING)

REF *EXTERNAL_DATA
--- Using external data structures in Poplog

REF *FASTPROCS

REF *FLAVOURS
---  The  flavours  object  oriented  language  (See  also
HELP *FLAVOURS). Made obsolete by Objectclass.

REF *IDENT
--- Identifiers (constants and variables)

REF *INTVEC
--- Signed  integer  vectors  (See  also  REF  *DATA,  *VECTORS,
*STRINGS, HELP *PROGRAMMING)

REF *ITEMISE

REF *KEYS
*CLASSES, *DATASTRUCTURES)

REF *LIBRARY

REF *LISTS

REF *LOGICAL_NAMES (VMS only)
--- Logical names defined by the Poplog system.

REF *MISHAP_CODES
--- Some  error  messages  include  a  "code"  abbreviating  the
message.  This  file  includes  full  explanations  and   cross-
references to relevant  information about the  error. (See  also
HELP *MISHAP)

REF *MISHAPS
--- Poplog  mishap  (error)  handling (See  also  HELP  *MISHAP,
*PROGRAMMING)

REF *NEWC_DEC
--- Procedures concerned with the "new" interface  to externally
loaded C programs. See HELP * NEWC_DEC for more details.

REF *NUMBERS
*NUMBERS)

REF *OBSOLETE
---   Obsolete   features   still   supported   for    backwards
compatibility

REF *POPCOMPILE
--- POP11 compiler procedures

\$usepop/pop/ref/popindex.*
--- These files (which  really should be  in another place)  are
used by the *POPINDEX and *VED_SOURCEFILE mechanisms.

REF *POPSYNTAX
--- POP11 syntax in diagram form

REF *PRINT

REF *PROCEDURE
--- The nature  of procedures and  closures, list of  predicates

REF *PROCESS

REF *PROGLIST
--- The  input stream  used in  Poplog by  many system  modules,
including the  POP11  compiler.  (See  also  REF  *ITEMISE,  REF
*CHARIO, HELP *PROGRAMMING)

REF *PROLOG
--- Procedures that support the Prolog system in Poplog

REF *PROPS

REF *PWM
--- The original Poplog Window Manager (now defunct, as it
requires Sunview).

REF *RECORDS
---  The  reference  and  boolean  data  types  (See  also
HELP *RECORDS)

REF *REFFILES
--- Overview of REF files, with the information presented here.

REF *REFFORM
--- Describes the format of REF files, explains the  conventions
used  to  indicate  the  types  of  arguments  and  results   of
procedures, and provides some VED utilities to help creation  of
REF files in the proper format.

REF * REGEXP
--- Describes the Pop-11 regular expression matcher, used in VED
and other Poplog facilities, for searching in strings.

REF *SECTIONS
--- Sections (hierarchies  of permanent  identifiers) (See  also
HELP *SECTIONS)

--- Mechanisms for bridging the gap between Pop-11 data
structures and external structures, e.g. for C programs.

REF *SIGNALS
---  Contents now transferred to REF *ASYNC.

REF *SOCKETS
--- A set of procedures for creating and operating on Unix
sockets.

REF *STACK
--- The POP11 stack and procedures for operating on it (See also
HELP *STACK, TEACH *STACK)

REF *STRINGS

REF *SUBSYSTEM
--- Describes mechanisms for  handling sub-systems like  Prolog,
Pop-11, Lisp, ML and switching conveniently between them.

REF *SYNTAX

REF *SYSIO
--- Device  Input  &  Output  procedures,  including  pipes  and
mailboxes

REF *SYSTEM
--- Various Poplog system control procedures, including starting
up, interrupts, saving and restoring saved images, etc.

REF *SYSUTIL
--- Operating System utility procedures

REF *TIMES
--- Date and Time and Timer procedures

REF *TRACE
--- Information about tracing Pop-11 procedures.

REF *VECTORS

REF *VED
--- Overview of REF files about the Poplog editor, VED

REF *VEDCOMMS
--- Summary of VED  commands

REF *VEDPROCS
--- Summary of VED system procedures

REF *VEDTERMINALS
--- Summary of  VED terminal types  and terminal  initialisation
procedures

REF *VEDVARS
--- Summary of VED's global control variables

REF *VMCODE

REF *WORDS
--- Words and the Poplog dictionary mechanism.

REF *WVED
--- Variables and procedures associated with Windowed VED,
i.e. XVed and PWM.

There are additional REF files to be found in

\$usepop/pop/x/ved/ref
\$usepop/pop/x/pop/ref

and, at least in Poplog versions 14.5 and 15.0,

\$usepop/pop/lib/objectclass/ref/objectclass
--- Information about the objectclass system
Available as REF * OBJECTCLASS after the pop11 command

uses objectclass

\$usepop/pop/lib/proto/go/ref
--- Information about the graphical object system
[NOW REMOVED.
It was too buggy and unfinished to include by default]

-- VMS DCL or UNIX shell commands in Pop-11

(A) For UNIX users:

You can give a UNIX Shell command by typing a dollar as the first symbol
on the line, followed by the command, e.g.

\$ ls -l *.p

On UNIX if you use a percent symbol '%' instead of the dollar, you'll
get the CSHELL rather than the SHELL.

In either case you can use the character '~' in file names to
identify a user's login directory. E.g.

% ls ~fred

will get a listing of fred's directory (if it is readable by you).

If you use '!' as the shell "escape" character, then you will get
whichever shell is the currently value of the Unix environment
variable \$SHELL

To switch temporarily to a sub-SHELL, so that you can give a series
of commands, type one of '%', '\$' or '!' on its own, at the
beginning of a line. Pop-11 will be temporarily suspended, and you
can give SHELL commands. Later, you can leave the shell by typing
the end of file character (CTRL-D), or typing 'exit', after which

(B) For VAX VMS users:

DCL commands can be given by typing the dollar as the first symbol on
the line, e.g.

\$ show time

or

\$ dir *.p

If you type the dollar on its own at the beginning of a line it will
spawn a new sub-process running DCL. You can type several DCL commands,
and then type "q" to terminate the DCL process and return to Pop-11.

See also the following facilities for invoking a shell or DCL from
a VED window:

ved_imcsh ved_imsh ved_imdcl

See
TEACH * TEACHFILES

HELP * POP
Summary of online documentation about Pop-11.

REF * REFFILES
Overview of the online REF files which give the "definitive"
definition of the language.

HELP * OBJECTCLASS
This gives an overview of the main object oriented extension to
Pop-11, still under development.
TEACH * OBJECTCLASS_EXAMPLE
This can be read after doing:
lib objectclass

TEACH * FLAVOURS
An older object oriented extension to Pop-11, based on message
passing and much influenced by Smalltalk.

HELP * DOCUMENTATION
Gives an overview of online documentation available in Poplog.

HELP * POPREFS

James Anderson, editor, Pop-11 Comes of Age
Ellis Horwood, 1989

This is a collection of papers on the history of dialects of Pop, the
features and benefits of the language, and some applications using
Pop-11.

This document may be freely copied and distributed, as long as the