If you are an experienced programmer, reading the Pop-11 primer may be more informative for you:
JUMP TO CONTENTS LIST
Lists and sorting
Pop-11 has a great deal of support for programming using lists, which can
contain words, numbers, strings, lists, and other entities. Lists provide a very
general mechanism for storing and manipulating information, and Pop-11 provides
some powerful tools for using them, such as a list pattern matcher, and tools
built using it.
(Lists also play a central role in other languages designed for AI and more
generally for symbolic computation, e.g. Lisp, Scheme, Prolog.)
-- Introductory examples ----------------------------------------------
Here is a collection of little examples which should give you a
basic grasp of list processing in POP-11. Try the following Pop-11
commands and see what happens, then edit the commands and redo them,
to see how the results change:
vars list;
[1 2 3 4 5] -> list;
;;; we use "=>" to print out a Pop-11 value (preceded by two asterisks)
list =>
** [1 2 3 4 5]
The first line declared a variable called LIST,
vars list;
The next line assigned a list of numbers to it,
[1 2 3 4 5] -> list;
then the third line used the print-arrow to print out the value of the
variable LIST:
list =>
Now try assigning a different list of numbers:
[1 2 3 4 5 6] -> list;
list =>
** [1 2 3 4 5 6]
We can use a program to generate a list of numbers by putting a loop
instruction inside a special version of the list brackets [% ... %]
like this:
vars num;
[%
for num from 1 to 25 do num endfor
%] -> list;
list =>
** [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25]
or a list of words
[the cat ate the mouse] -> list;
We can reverse the list:
rev(list) =>
** [mouse the ate cat the]
NB: the original list is unchanged. The procedure rev produces
a new copy of the original, with the items in a different order.
Work out its length
length(list) =>
** 5
Sort the contents into alphabetical order
sort(list) =>
** [ate cat mouse the the]
Create a palindrome by concatenating the original list with its reversed
version using '<>' to do the concatenating:
list <> rev(list) =>
** [the cat ate the mouse mouse the ate cat the]
and compute the length of that
length( list <> rev(list) ) =>
** 10
and sort it
sort( list <> rev(list) ) =>
** [ate ate cat cat mouse mouse the the the the]
Notice that sorting the list in this way does not remove duplicate entries.
Later we'll see how to 'prune' a list, to remove
the duplicates.
Checking the contents of a list using member and the Pop-11 matcher
Previous examples showed how to construct, combine, reverse, and sort a list.
Sometimes it is useful to be able to check what is in a list. One way
to do that is to use the Pop-11 procedure (or function) member, which
takes an item and a list, and returns true or false:
member("cat", [the angry cat chased the dog]) =>
** <true>
member("dog", [the angry cat chased the dog]) =>
** <true>
member("cow", [the angry cat chased the dog]) =>
** <false>
What should this produce: true or false?
member("the", [the angry cat chased the dog]) =>
In fact member does not care how many times an item occurs in the list, as
long as it occurs.
Sometimes mere membership is not what you are interested in. Suppose you
want to know whether the word "cat" occurs before or after the word "dog":
you can then use the pop11 matcher with a pattern that matches only lists
containing those two words with "cat" occurring before "dog".
[the angry cat chased the dog] matches [== cat == dog == ] =>
** <true>
[the angry dog chased the cat] matches [== cat == dog == ] =>
** <false>
[the angry dog chased the cat and mouse ] matches [== dog == cat == ] =>
** <true>
The element "==" will match any number of items, 0, 1 or more, not matter
what they are. If we want to know if there are exactly two words between
"cat" and "doc" we can use the symbol "=" to match exactly one item:
[the angry cat chased the dog] matches [== cat = = dog == ] =>
** <true>
[the angry cat chased only one dog] matches [== cat = = dog == ] =>
** <false>
Will this one produce true or false?
[the angry cat chased only one dog] matches [== cat = = = dog == ] =>
Remembering what was found in a list
Sometimes you want to know not only whether something occurs in a certain
location but what occurs there. The pattern matcher can do that if you put
variables in a pattern, as follows.
Let's declare some variables for items and for lists.
vars item1, item2, list1, list2, list3;
(Actually, the names could be anything: Pop-11 doesn't care. So I could
have used
vars x1, y, boat1, boat2, boxes;
But it usually leads to clearer programs if you give variables names
reflecting their use.)
So we can ask the matcher whether exactly two items occurred between
"cat" and "dog" and, if so, what they were:
vars item1, item2;
[the angry cat chased the dog] matches [== cat ?item1 ?item2 dog == ] =>
** <true>
Note the use of the "?" symbol in ?item1 ?item2 to indicate that we are
using item1 and item2 as variables to be given values, not as words to be found in
the original list, like "cat" and "dog".
Because the match result was <true> we can ask what the items were:
item1 =>
** chased
item2 =>
** the
[Pop-11 prints out words without the quotes "".]
Or we can ask for both together
item1, item2 =>
** chased the
If we don't know how many items occurred in a region of a list, we can
ask the Pop-11 matcher to make a list of the items, using a "segment
variable" indicated by using the double query before a variable name, as in
"??list1" below:
For example, if we want to know what words occurred before "cat" we can
use this
vars list1;
[the angry cat chased the dog] matches [??list1 cat == dog == ] =>
** <true>
And because the result is true, it's worth looking at the new value
of list1:
list1 =>
** [the angry]
We can check several different segments of a list, using different
segment variables, e.g.
vars list1, list2, list3;
[the angry cat chased the hungry dog] matches [??list1 cat ??list2 dog ??list3] =>
** <true>
and we can find the contents of the three lists:
list1, list2, list3 =>
** [the angry] [chased the hungry] []
The third list is empty, because there was nothing after "dog".
We can use the found list segments to create a new list, by using
^^list1 to insert the contents of list1 into a new list, e.g.:
[^^list1] =>
** [the angry]
We can do that for list1, list2, and list3 to build a new list containing all
of them as list segments:
[^^list1 mouse ^^list2 elephant ^^list3] =>
** [the angry mouse chased the hungry elephant]
Because list3 is empty, nothing is inserted where it occurs.
How could you use list1 and list2 to create a list containing this?
[the angry eagle chased the hungry snake]
There are many more examples of how to use the list matcher in Poplog teach files
including 'TEACH MATCHES'.
We now show how the pattern matcher can be used to define a procedure to
prune a list -- i.e. remove repeated elements, such as we saw was needed after
sorting the list above:
Pruning a list using the pattern matcher
Previously we looked at sorting a list:
Declare a variable and assign to it in one instruction:
vars list = [the cat ate the mouse];
Create a palindrome from the list, an sort it:
sort( list <> rev(list) ) =>
** [ate ate cat cat mouse mouse the the the the]
Sorting does not remove duplicates. The duplicates could be removed by using a
procedure prune defined like this, using the pattern matcher, though that is
not the most efficient way to prune a list.
define prune( list ) -> pruned;
;;; given a list of words remove all repetitions, using
;;; the pop-11 pattern matcher
;;; we need four variables to record stuff to the left of
;;; a repeated word, the repeated word, stuff between the two
;;; occurrences, and stuff following the second occurrence.
lvars lefts, item, middle, rights;
;;; Use '??' to match any number of words, '?' to match only one:
;;; use two occurrences of '?item' to check for a repeated word:
while list matches ![ ??lefts ?item ??middle ?item ??rights]
do
;;; Rebuild the list without the second occurrence of item:
;;; when building lists use ^^ to splice in a list of words,
;;; and use ^ to insert one word
[ ^^lefts ^item ^^middle ^^rights] -> list;
endwhile;
;;; At this stage the 'while loop' has ended the list no longer matches
;;; the pattern detecting repetition. So no more repetitions were found.
;;; We can therefore set the value of list to be the value of the output
;;; variable pruned used in the procedure header:
list -> pruned;
enddefine;
Now test it:
prune( [ cat dog ] ) =>
** [cat dog]
prune( [ cat cat dog ] ) =>
** [cat dog]
prune( [ cat dog dog ] ) =>
** [cat dog]
prune( [ cat cat mouse apple dog ] ) =>
** [cat mouse apple dog]
prune( [ berry cat cat mouse apple dog dog ] ) =>
** [berry cat mouse apple dog]
prune( [ berry cat cat mouse apple dog dog elephant flea] ) =>
** [berry cat mouse apple dog elephant flea]
Try sorting before pruning:
prune( sort ( [ berry cat cat mouse apple dog dog elephant flea] ) ) =>
** [apple berry cat dog elephant flea mouse]
The notation used in the Pop-11 matcher is summarised in this help
file: 'HELP MATCHES'
QUESTION:
In the definition of prune we discarded the second of the repeated
items. What difference would it make if we discarded the first one
instead?
Try it and repeat the above tests.
-- How to read assignment and print instructions ----------------------
It is important to note that something like
[the cat ate the mouse] -> list;
is really made of two separate instructions. The first is
[the cat ate the mouse]
which means, "create the list [the cat ate the mouse] and put it on the
stack". The stack is a part of the computer's memory reserved by Pop-11
for communication between different procedures. All arguments for a
procedure (i.e. inputs for the procedure) are put on the stack, where
the procedure will find them, and if the procedure produces a result it
will leave it on the stack.
The second instruction is
-> list;
and this means, assign the last thing put on the stack to be the value
of the variable called "list".
The following print instruction also has two separate parts:
list =>
The first part "list" just means put the value of the variable "list" on
the stack.
The second part "=>" means, run the print-arrow procedure. This prints
out whatever is on the stack.
For more information on the use of the 'stack' in Pop-11 as in many
programmable calculators see the TEACH STACK file.
-- The procedure length -----------------------------------------------
The procedure length, when applied to a list, counts the number of
items in the list, and returns a number as its result.
length( [ 1 5 9 16 ] ) =>
** 4
Note the difference between the square brackets, which make a list, and
the round brackets, which function as "doit" brackets. I.e. they tell
Pop-11 to DO (or RUN or EXECUTE or OBEY) the procedure length.
(In that example, I typed extra spaces around the brackets, for
clarity, but they could be omitted:
length([1 5 9 16]) =>
** 4
But you can't omit the spaces between the numbers:
length([15916]) =>
** 1
You can tell Pop-11 to run the procedure without anything between the
doit brackets, but you will get a 'STACK EMPTY' error message. Try it
length() =>
;;; MISHAP - STE: STACK EMPTY (missing argument? missing result?)
;;; DOING : length ......
(The error message may have some additional information, e.g. the
file name, and the context if the error occurs while another
procedure is running. I have left out everything irrelevant.)
The procedure length requires an object to be given to it as its "input"
(sometimes called its "actual parameter" or its "argument"). If an
argument is given between the doit brackets, as in
length([ 9 8 7]) =>
** 3
Then the input (the list [9 8 7] in this case) is put on the stack, and
that is where the procedure finds it. If it does not find it, the STACK
EMPTY mishap message results.
For more on the the role of the 'stack' in Pop-11 see TEACH STACK
-- Length of an empty list --------------------------------------------
Note that the length of the empty list is 0
length( [] ) =>
** 0
That extra white space makes no difference to Pop-11
These all give the same result:
length( [ a b c d e f g ] ) =>
** 7
length( [ a b c d e f g ] ) =>
** 7
even line breaks and tabs are treated like spaces
length( [ a b
c d e f g
]
) =>
** 7
For more introductory material on using lists see the TEACH LISTS file.
We give more examples using the matcher below.
Simple arithmetic examples
Basics
The print arrow "=>" says to POP11, roughly,
"print out your results so far"
Try:
1 + 3 + 5 =>
The result is printed out preceded by two asterisks (usually in
another window if the commands are given in the Poplog editor Ved):
** 9
Try some more:
5 - 5 =>
** 0
99 + 88 - 77 =>
** 110
The print arrow makes it possible to use POP-11 as a desk-calculator.
Multiplication
Multiplication uses the "*" symbol. Try the following:
3 * 5 =>
** 15
333 * 99 =>
** 32967
22.5 * 6 =>
** 135.0
A few simple loops
Declare a variable x, and use it to print out the first 20 squares:
vars x;
for x from 1 to 20 do
x*x
endfor =>
** 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400
(By putting the '=>' after the loop end we get all the results in
one line.)
Now print out all the square roots of numbers 1 to 10:
vars x;
for x from 1 to 10 do
sqrt(x)
endfor =>
** 1.0 1.41421 1.73205 2.0 2.23607 2.44949 2.64575 2.82843 3.0 3.16228
Or create a tutorial display, using lists, each printed on a
separate line:
vars x;
for x from 1 to 10 do
['The square root of ' ^x ' is ' ^(sqrt(x))] =>
endfor;
** [The square root of 1 is 1.0]
** [The square root of 2 is 1.41421]
** [The square root of 3 is 1.73205]
** [The square root of 4 is 2.0]
** [The square root of 5 is 2.23607]
** [The square root of 6 is 2.44949]
** [The square root of 7 is 2.64575]
** [The square root of 8 is 2.82843]
** [The square root of 9 is 3.0]
** [The square root of 10 is 3.16228]
Writing a simple stand alone tutorial package on square roots
This shows how some of the above ideas can assembled in a tiny
tutorial program that repeatedly asks the user to provide the square
root of a randomly chosen perfect square up to 100.
;;; Declare some variables to be used below.
vars number, square, root, answer;
repeat
;;; create a perfect square by starting from a number
;;; between 1 and 10
random(10) -> number;
number * number -> square;
;;; Use that number to generate a question to ask the user
['Please type in the square root of:' ^square] =>
;;; Readline reads a list of items typed by the user, followed
;;; by the RETURN/ENTER key
readline() -> answer;
;;; There may be an empty list
if answer == [] then
[I guess you have had enough. Bye for now] =>
quitloop();
else
;;; if the list is not empty get the first item
hd(answer) -> root;
;;; now check whether it is the correct answer
if root = number then
['Excellent: that\'s right!']=>
else
;;; wrong answer so print out some tutorial information.
[Sorry no: ^root is the square root of ^(root*root)]=>
endif;
endif;
endrepeat;
Here is an example of the above program running:
** [Please type in the square root of: 36]
? 5
** [Sorry no : 5 is the square root of 25]
** [Please type in the square root of: 9]
? 22
** [Sorry no : 22 is the square root of 484]
** [Please type in the square root of: 64]
? 8
** [Excellent: that's right!]
** [Please type in the square root of: 100]
? 10
** [Excellent: that's right!]
** [Please type in the square root of: 36]
? 7
** [Sorry no : 7 is the square root of 49]
** [Please type in the square root of: 1]
?
** [I guess you have had enough . Bye for now]
Note there's at least one bug in the program. It cannot cope with
all possible responses from the user. What needs to be changed?
Hint: Pop-11 contains a predicate 'isinteger' which can be used to
test whether something is an integer.
What should happen if the user types in a negative number?
What should happen if the user types in more than one number?
Hint: Pop-11 contains a function called 'length', which can be
applied to lists.
Can you change the program to ask about the square of a number
instead of the square root of a number?
By using a 'memory' composed of lists, the program could be extended
to remember items the user got wrong and ask about them again more
frequently than items the user got right.
How should such a memory be structured, extended and used?
A more ambitious project would be to design a program that learns
things about numbers and then teaches what it has learnt? What would
be a suitable starting state for such a program?
What does a child start with when beginning to learn about numbers?
For some suggestions see this teach file.
Fractions (rational numbers)
Rational numbers are generated if you ever divide an integer by an
integer. The notation for rationals has to be got used to:
3/4 =>
** 3_/4
Pop-11 can reduce fractions to their simplest terms:
5/10 =>
** 1_/2
3/12 =>
** 1_/4
99/12 =>
** 33_/4
The 'TEACH ARITH' file, introduces the above information and a lot more.
JUMP TO CONTENTS LIST
Other mathematical operations
Pop-11 includes the main mathematical functions provided by other
programming languages, including trigonometric functions, etc.
It even knows about complex numbers though the syntax used to print
them out or type them in may be unfamiliar. E.g. this is how it
prints the square root of -1
sqrt(-1) =>
** 0.0_+:1.0
(i.e. 0.0 + 1.0i in a more familiar notation)
sqrt(-23) =>
** 0.0_+:4.79583
(i.e. 0.0 + 4.79583i in a more familiar notation)
And it has some constants built in:
pi =>
** 3.141593
A random number generator for positive integers:
repeat 20 times random(100) endrepeat =>
** 37 83 79 79 32 16 69 90 38 3 33 53 9 66 21 58 74 60 80 26
which also works with floating point numbers
repeat 8 times random(10.0) endrepeat =>
** 6.7742 5.03026 8.07819 7.51446 7.90437 9.95057 9.66306 3.23868
JUMP TO CONTENTS LIST
Defining new arithmetical procedures
We now show how these arithmetical operations can be used in defining
some procedures to help you sort out requirements for furnishing and
heating a room.
-- Defining a procedure- PERIMETER ------------------------------------
Suppose you know the length and the breadth of a rectangular room and
you want to know its perimeter. You can add up the lengths of all the
walls, thus (using the arrow '->' to indicate a variable that will hold
the output value for the procedure):
define perim(long, wide) -> total;
long + wide + long + wide -> total
enddefine;
Compile it and test it with a range of examples:
perim(3,4) =>
** 14
perim(10,20) =>
** 60
perim(10,10) =>
** 40
-- Carpeting the room -------------------------------------------------
In order to carpet the room you'll need to know the area of the floor.
This procedure will tell you:
define floor(long, wide) -> area;
long * wide -> area
enddefine;
Type that in then test it
floor(10,10) =>
** 100
floor(8,6) =>
** 48
-- Wallpaper required -------------------------------------------------
If you also know the height of the room you can work out the area of
wall-paper required to cover the walls. Imagine the walls all
straightened out into one long wall. Then the new wall would be as long
as the original perimeter of the room and to find its area you'd only
have to multiply the perimeter by the height.
So you can define the wallarea procedure to do that:
define wallarea(long, wide, high) -> total;
perim(long, wide) * high -> total
enddefine;
It can be compiled and tested:
wallarea(10,10,10) =>
** 400
wallarea(10,20,8) =>
** 480
-- The volume of a room -----------------------------------------------
If you need to buy an extractor fan, or heating system, you'll need to
know the volume of the room. So
define volume(long, wide, high) -> vol;
long * wide * high -> vol
enddefine;
Then test it:
volume(10,10,10) =>
** 1000
volume(8,12, 8) =>
** 768
JUMP TO CONTENTS LIST
Graphics (including 'turtle programming') in Pop-11, and plotting mathematical functions
Graphical tools are also available in Pop-11 for learning that requires,
or at least benefits from, using graphics, as illustrated in this unusual
introduction to turtle geometry, including, for example, a version of the
"polyspiral" program which takes four numbers as input, and is capable of
generating pictures like this (and many others):
To view actual size, use your browser's 'view image' option.
That introduction illustrates a subset of Pop-11 with graphical facilities
providing the functionality of the LOGO Turtle, but with additional features
available, including a little package for making silly faces out of circles and
rectangles, with results shown here, and explained
in this tutorial introduction to making pictures of faces, (and other things).
The 'Graphplot' extension to the program provides facilities for drawing
graphs of various kinds of mathematical function in a flexible manner.
Like everything else, that package is implemented in Pop-11 and can therefore
be copied and modified or extended by Pop-11 programmers (including teachers)
or easily invoked as a library in Pop-11 programs.
More complex graphical capabilities of Pop-11 illustrated here, make use
of the Pop-11 RCLIB package, a powerful and extendable object-oriented
graphical toolkit that is implemented in Pop-11 and therefore tailorable
by Pop-11 users, and easily integrated within a variety of other kinds of
Pop-11 programs.
(Note, however, that the phrase "Object Oriented" has several different
interpretations and the ambiguity mostly goes unnoticed by people who have
learnt only one interpretation. More details here.
For example, the RCLIB package is also used to provide a graphical
interface for the SimAgent toolkit, as shown in some of the videos here.
The combination has been used in various programs written in student
projects and also used for research based on simulated interacting animals
or other agents, e.g. in this online paper (The Role of Signaling Action
Tendencies in Conflict Resolution, in Journal of Artificial Societies and
Social Simulation vol. 7, no. 1)
The RCLIB package was used to produce an animated proof of Pythagoras' theorem
here:
http://www.cs.bham.ac.uk/research/projects/cogaff/tutorials/pythagoras.html
JUMP TO CONTENTS LIST
The "river world" -- an introduction for beginner programmers
(Getting the computer to solve a puzzle.)
An example very elementary introductory "teach file" on the
river-crossing problem is TEACH RIVER (originally the brain-child of
Max Clowes in the late 1970s).
This has been used to teach absolute beginners, including quite
young children elementary programming (as long as they can read and
type) though they first have to solve a non-programming puzzle
themselves.
This is based on a well-known puzzle:
How can a man get a fox, a chicken and a bag of grain from the left
bank of a river to the right bank without the fox eating the chicken
or the chicken eating the grain, given that the boat can hold only
two things (including the man), and only the man can row it across
the river, and only the presence of the man can prevent unwanted
consumption.
Make sure that you have worked out a solution to the problem (e.g.
using pencil and paper) before doing the exercises in the teach
file.
Students can read the TEACH RIVER file into the poplog editor Ved,
then "mark and run" the code portions to see what happens.
(Or they can read the file in another editor or browser and paste
the code into the pop11 command prompt, after starting pop11 in a
console window.)
For example, after the river library has been compiled, using the
command
lib river
the 'start();' command produces an initial state of the world, and
displays it.
In that command the 'doit' brackets are needed to tell pop11 to run
the start procedure even though no extra arguments are needed for
start to run.
start();
prints out:
** Here is the state of the river-world:
** [chicken fox grain man ---\ \_ _/ _________________ /---]
Various commands are available, provided by the library, including
putin( thing )
takeout( thing )
getin()
getout()
crossriver()
where thing can be fox, chicken or grain.
after 'putin(grain);' the student sees
putin(grain);
** Here is the state of the river-world:
** [chicken fox man ---\ \_ grain _/ _________________ /---]
The state of the world can also be shown by printing out the current
Pop-11 database, which is used to hold information about the current
state of the world, and is changed by actions performed:
;;; the 'pretty print' arrow ==> prints complex lists in a tidy way
database ==>
** [[grain isat boat]
[boat isat left]
[chicken isat left]
[fox isat left]
[man isat left]]
Note that the database is just a list of lists containing words.
The computer does not understand the words in those lists, but the
programs in the library are made to manipulate them as if it did.
The tempting fatal mistake can be demonstrated -- try getting into
the boat after putting in the grain:
getin();
** Here is the state of the river-world:
** [chicken fox ---\ \_ man grain _/ _________________ /---]
;;; MISHAP - DISASTER
;;; INVOLVING: fox has eaten chicken TOO BAD
;;; FILE : river
;;; DOING : river_mishap eat checkeat getin runproc
** Here is the state of the river-world:
** [fox ---\ \_ man grain _/ _________________ /---]
The disaster is confirmed by the absence of the chicken from the
database:
database ==>
** [[man isat boat] [grain isat boat] [boat isat left] [fox isat left]]
and of course the 'picture' printed out, showing no chicken:
** [fox ---\ \_ man grain _/ _________________ /---]
JUMP TO CONTENTS LIST
Putting repeated sequences into re-usable subroutines
After a full solution to the river problem has been constructed and
run as a sequence of commands, 'TEACH RIVER' invites learners to
combine the operations so as to build a specification for a process
to solve the whole problem, namely getting everything to the right
bank. That code sequence can be bundled into a named procedure.
They are then asked to look at recurring patterns in the solution,
and to rewrite the code so as to make it clearer, more compact and
more modular. An example would be the recurring sequence
getin();
crossriver();
getout();
That pattern could be used to define a procedure called cross(),
thereby shortening the program to solve the problem.
A new pattern may then become obvious after that, in sequences like:
putin(fox);
cross();
takeout(fox);
and
putin(chicken);
cross();
takeout(chicken);
inviting the type of abstraction that requires use of a procedure
with an input parameter:
define move (thing);
putin(thing);
cross();
takeout(thing);
enddefine;
Those two procedure definitions will dramatically reduce the length
of the complete program required to go through all the steps of a
solution to the puzzle.
Learning to see patterns in code that invite types of abstraction
supporting increased modularity and reusability is an important kind
of intellectual development. It can, of course, also be done with
graphical programming, but there is a limit to the generality
achievable that way.
JUMP TO CONTENTS LIST
TEACH RIVER is just one example among many
Of course, the above example is very limited: there are only a few
objects, a small number of actions, and little scope for ongoing
interaction. That is because it was intended originally merely as a
small exercise to introduce some fundamental programming constructs.
However the principle that it illustrates is that a teacher can
define a micro-world making use of concepts that intended learners
already understand, where every possible state of the
world is represented by the state of the Pop-11 database
and events and actions in the world can be represented by procedures
that add and remove database items. In some case such a world is
also representable graphically, as shown in the river example, and
the use of two forms of representation of what the program does,
with principled relations between them can be an important feature
of the learning process.
JUMP TO CONTENTS LIST
A benefit of the textual interface
This also demonstrates an advantage of textual over graphical
learning interfaces: textual results produced by several textual
commands can easily be preserved and compared, so that similarities
and differences can be studied. Graphical interactions, with
pictures of recognizable objects moving around on a screen, can be
much more engaging, but since graphical displays constantly replace
their contents, the task of thinking about and comparing the results
of the last ten graphical commands (except in simple cases where the
commands produce cumulative results) requires an extraordinarily
good visual memory, or tools to replicate the interface on demand
and repeatedly run the commands in slow motion in parallel so that
two or more processes can be compared as they run.
(A partial solution for the case of turtle graphics is the Pop-11
polypanel interface shown here,) which allows parameters for a
"polyspiral" command to be altered graphically and the program
re-run at varying speeds, to help make it clear how the
parameters chosen affect the construction of the picture.)
Using textual input and output, both teachers developing teaching
programs and documentation, and students making use of the
materials, can copy commands and change parameters or lists of words
in the code examples and then instantly re-run the code, with both
the commands and the output saved in one or more text files or
editor buffers, making it possible, and in simple cases easy, to
look back at and compare different episodes (as in the "riverworld"
example above.
For teachers, this makes development of teaching files littered with
tested code examples relatively quick and easy (at least compared
with authoring systems that require the teacher's input to be
compiled into some teaching engine which has to be restarted and
then run).
The interleaving of instructions with code that is editable and
runnable by students, as illustrated above, can facilitate rapid
exploratory learning -- by both teachers and learners -- making
teachers learners!
In particular, after testing their examples, teachers can select
portions of the examples to remove, presenting students with gaps in
code fragments, so that students can try various ways of filling in
the gaps, and run the commands to see what happens (put the fox,
chicken or grain in the boat, get into the boat, cross the river,
get out, take out what is in the boat, etc.). Gifted teachers will
learn which "size" gaps are suited to learners of different sorts.
JUMP TO CONTENTS LIST
Searching and combinatorics in simple microworlds
Standard list processing exercises include searching for items in
lists, or lists of lists. Exercises are provided in teach files.
E.g.
If you don't know whether some item occurs in a list or not, there is a
predicate (a procedure that returns true or false) built in to Pop-11
for testing whether something is a member of a list. the procedure is
called "member". It takes two inputs, an item and a list, and returns
the result true if the item is in the list, false otherwise.
member(3, [1 2 3 4 5]) =>
** ⟨true⟩
Compare the behaviour with this one-element list:
member(3, [ 12345 ])=>
** ⟨false⟩
Nothing is a member of the empty list:
member(3, []) =>
** ⟨false⟩
member("fox", [the fox ate the grain]) =>
** ⟨true⟩
member("chicken", [the fox ate the grain]) =>
** ⟨false⟩
Note that the special Pop-11 entities we refer to as 'true' and
'false' (called Booleans by programmers) are printed out by pop11
with angle brackets as in
** ⟨false⟩
** ⟨true⟩
to indicate that they are those entities, not the words "true" and
"false".
JUMP TO CONTENTS LIST
Searching with a test predicate
What if you want to know whether a word that satisfies a condition
occurs in a list, and you don't know in advance which words are in
the list. Then you cannot use the member procedure, since it has to
be told precisely what to search for.
For example we might be given a list of numbers and wish to know
whether a number between 15 and 25 occurs in the list, and if so
return the first one found.
vars list1, list2;
[ 3 9 88 6 22 77 33 7 16 ] -> list1;
[ 33 9 88 60 77 33 15 26 ] -> list2;
You can define a procedure that searches for a number satisfying the
condition:
define between_15_and_25( list ) -> found;
;;; if there is a number between 15 and 25 return it as
;;; 'found', otherwise return false, to indicate failure.
lvars item;
for item in list do
if 15 < item and item < 25 then
item -> found;
return();
endif;
endfor;
;;; failed, so result should be false
false -> found;
enddefine;
Test it with these two lists:
vars list1, list2;
[ 3 9 88 6 22 77 33 7 16 ] -> list1;
[ 33 9 88 60 77 33 15 26 ] -> list2;
between_15_and_25( list1 ) =>
prints out:
** 22
between_15_and_25( list2 ) =>
prints out:
** ⟨false⟩
A recursive version could look like this:
define between_15_and_25( list ) -> found;
if null( list ) then
;;; got to end of list without finding anything,
;;; so
false -> found
elseif 15 < hd( list ) and hd( list ) < 25 then
hd( list ) -> found;
else
;;; the recursive step -- search the tail of the list
between_15_and_25( tl( list ) ) -> found;
endif;
enddefine;
Test this as before:
between_15_and_25( list1 ) =>
prints out:
** 22
between_15_and_25( list2 ) =>
** ⟨false⟩
But now, because the procedure was defined recursively we can ask it
to trace itself when it runs:
trace between_15_and_25 ;
and now the intermediate steps are shown:
between_15_and_25( list1 ) =>
> between_15_and_25 [3 9 88 6 22 77 33 7 16]
!> between_15_and_25 [9 88 6 22 77 33 7 16]
!!> between_15_and_25 [88 6 22 77 33 7 16]
!!!> between_15_and_25 [6 22 77 33 7 16]
!!!!> between_15_and_25 [22 77 33 7 16]
!!!!< between_15_and_25 22
!!!< between_15_and_25 22
!!< between_15_and_25 22
!< between_15_and_25 22
< between_15_and_25 22
** 22
If applied to a list that does not contain a target the tracing
looks like this, showing how it gets to the end of the list then
returns false, which is passed all the way back up the recursive
calling chain:
between_15_and_25( list2 ) =>
> between_15_and_25 [33 9 88 60 77 33 15 26]
!> between_15_and_25 [9 88 60 77 33 15 26]
!!> between_15_and_25 [88 60 77 33 15 26]
!!!> between_15_and_25 [60 77 33 15 26]
!!!!> between_15_and_25 [77 33 15 26]
!!!!!> between_15_and_25 [33 15 26]
!!!!!!> between_15_and_25 [15 26]
!!!!!!!> between_15_and_25 [26]
!!!!!!!!> between_15_and_25 []
!!!!!!!!< between_15_and_25 ⟨false⟩
!!!!!!!< between_15_and_25 ⟨false⟩
!!!!!!< between_15_and_25 ⟨false⟩
!!!!!< between_15_and_25 ⟨false⟩
!!!!< between_15_and_25 ⟨false⟩
!!!< between_15_and_25 ⟨false⟩
!!< between_15_and_25 ⟨false⟩
!< between_15_and_25 ⟨false⟩
< between_15_and_25 ⟨false⟩
** ⟨false⟩
Since the procedure between_15_and_25 is just a special case of a
procedure that searches down a list for something that passes a
test, we can see that it cries out to be generalised to a procedure
that takes a list and a test predicate (a procedure that returns
true or false).
Here is an example of a "test procedures":
define iseven( item ) -> result;
;;; test whether item is even by seeing whether its remainder
;;; on division by 2 is 0
( ( item mod 2 ) == 0 ) -> result
;;; now result is true or false (the result of the '==' test),
;;; those parentheses are not needed -- they have been
;;; included for clarity.
enddefine;
iseven(3) =>
** ⟨false⟩
iseven(30568) =>
** ⟨true⟩
A procedure called 'isodd' can be defined similarly to test if a
number is odd. (How?)
Then the search procedure which takes a list and a test could be
based on either the looping or recursive version of procedure
between_15_and_25 defined above, e.g. the recursive version might
be:
define find_first( list, test ) -> found;
;;; list can contain anything. test is a predicate, a
;;; procedure that takes one input and returns true or false.
;;; See if something in the list satisfies the test predicate
if null( list ) then
;;; got to end of list without finding anything,
;;; so
false -> found
elseif test( hd (list) ) then
hd( list ) -> found;
else
;;; the recursive step -- search the tail of the list
find_first( tl( list ), test ) -> found;
endif;
enddefine;
So we can now test that, using the predicate iseven ("is even"), and
other predicates provided in pop11, (most of which start with 'is')
e.g. isnumber, isword, isstring:
find_first( [3 9 35 22 16 99 4], iseven ) =>
** 22
find_first( [3 9 35 23 17 99 5], iseven ) =>
** ⟨false⟩
find_first( [3 9 35 cat dog 17 mouse], isword ) =>
** cat
find_first( [3 9 35 cat dog 17 mouse], isnumber ) =>
** 3
Try defining the looping equivalent. Create some more test
procedures, including isodd and is_between_35_and_45.
You could also consider how to modify find_first to find_all, namely
a procedure that takes a list and a predicate and returns a list
containing all the items in the given list that satisfy the
predicate, and the empty list if there are none.
Incidentally, this kind of example shows why it is unfortunate to
have a programming language that uses the number 0 to represent
false. Why?
There are far more examples and exercises in available teach files,
e.g.
TEACH SETS
TEACH SETS2
TEACH RECURSION
Note for experienced programmers: closures (lexical closures and
partial application) can be used to increase generality of use of
procedures as explained (briefly) in
HELP PARTAPPLY (partially apply)
HELP CLOSURES
JUMP TO CONTENTS LIST
The Pop-11 database
The pop-11 database package provides a collection of mechanisms for
searching the database using patterns to select items, and for
adding and removing things that depend on the results of searches as
well as depending on explicit commands. It also provides simple
pattern-based mechanisms for iterating over the database. E.g. after
the start() command introduced in TEACH RIVER, this instruction
vars x;
foreach [?x isat left] do
[The ^x is on the left bank] =>
endforeach;
could print out
** [The boat is on the left bank]
** [The chicken is on the left bank]
** [The fox is on the left bank]
** [The grain is on the left bank]
** [The man is on the left bank]
After one of the actions listed above has been performed the same
command would print out different information.
It is also possible to iterate over combinations of database
items. So, instead of a "foreach" loop with a single pattern (as
above) a "forevery" loop can be used with a list of patterns to be
matched consistently with database items in different ways:
vars thing1, thing2, place;
forevery [ [?thing1 isat ?place] [?thing2 isat ?place] ] do
if thing1 /= thing2 then
[The ^thing1 and the ^thing2 are both at ^place] =>
endif
endforevery;
could print out something like this:
** [The boat and the chicken are both at left]
** [The boat and the fox are both at left]
** [The boat and the grain are both at left]
** [The boat and the man are both at left]
** [The chicken and the boat are both at left]
** [The chicken and the fox are both at left]
** [The chicken and the grain are both at left]
.... and so on up to ....
** [The man and the grain are both at left]
After the commands
putin(chicken);
getin();
crossriver();
getout();
takeout(chicken);
The above 'forevery' loop would print out
** [The chicken and the man are both at right]
** [The chicken and the boat are both at right]
** [The man and the chicken are both at right]
** [The man and the boat are both at right]
** [The boat and the chicken are both at right]
** [The boat and the man are both at right]
** [The fox and the grain are both at left]
** [The grain and the fox are both at left]
Students could learn the need for the test in the "if" expression
before the print command, by first trying it without that test.
They could then think about how to prevent the duplication in
information presented because, for example, the first and third
pieces of output give the same information (because of the semantics
of the example), and therefore should not both be printed (along
with other duplications):
** [The chicken and the man are both at right]
.....
** [The man and the chicken are both at right]
JUMP TO CONTENTS LIST
Beyond the 'River World'
It's not a long way from those examples to introducing some of the
students to the mathematics of combinations and permutations (and
also to logic programming).
Instead of information being printed out, as above, it could be
added to the database representing the state of the world.
That makes it possible to write programs that do their own reasoning
i.e. they propagate consequences of changes initiated by a user --
and in more ambitious projects the programs could learn when such
propagation should be controlled, and how to do it.
JUMP TO CONTENTS LIST
Chatbots with memory
Many programming tasks can be devised that depend on such an
interface, including the task of producing a chatbot with a memory.
An example mini-project based on this idea that, for some reason,
many students have found interesting, is to develop a
'Conversational Drinks Machine', whose state consists of ingredients
for various drinks plus a collection of coins available as change,
and which allows questions about prices and supplies to be asked,
requests for drinks to be given and change requested if the customer
does not have the exact the exact sum required. This can be
implemented with or without a flexible natural language interface,
and with or without a memory for previous conversations and
transactions. Variants could include making the vendor polite or
rude! Which will be more fun for the learner?
A more powerful set of mechanisms is provided in the POPRULEBASE
extension to Pop-11, which is part of the SimAgent toolkit
An introductory teach file on rule-based programming TEACH RULEBASE
includes a 'toy medical rule-based system' which is like Eliza with
a memory. In principle that example could be made very much more
sophisticated including keeping information provided by patients to
use in selecting future responses.
For more sophisticated games it may be useful to use the Pop-11 Objectclass
package providing object oriented programming with methods and
inheritance, as illustrated here, or the SUPER database package
that facilitates more sophisticated reasoning and problem solving in the
style of Prolog (another language included with Poplog).
JUMP TO CONTENTS LIST
Learning to think about how to represent information
At some later stage instead of using the built in library for
manipulating the 'river world' students can think about how to
design their own version.
At that point they have to start thinking about how to represent
information in the machine so as to satisfy various criteria:
o it should support searching for relevant items
o it should enable inferences to be made in order to answer
questions, or make plans or make predictions
o it should (in this case) be relatively easy for programs to
change the information stored, in order to record facts about
how the world has changed.
o it should be easy to store information about previous states,
if questions need to be answered about the past, or if
learning has to be based on what happened in the past.
o if certain powerful tools are available and they are going to
be used, then the form of representation should conform to the
formats needed for those tools (e.g. FOREACH and FOREVERY above).
Other requirements would be included, such as efficiency and
compactness, though for beginners those are secondary to learning
about the more directly functional aspects of representation.
An example approach to introducing such an exercise is TEACH RIVER2
That might in some cases be followed by TEACH RIVERCHAT
Neural representations
Some learners (and teachers) may be interested in ways of modelling learning and
other processes using forms of representation inspired by neural nets,
illustrated in a simple package produced by Riccardo Poli for that purpose, as
illustrated here (use your browser's 'view image' option to enlarge this):
The train_net function (whose definition, in Pop-11, should be simple enough for
students to understand) is given some training data for a boolean function, in
the form of a list of lists of input and output values. It designs a suitable
simple neural net architecture, trains it, and then displays a graphical tool
for interacting with the net after training. As with all Pop-11 libraries,
learners can copy and modify this one to explore more options. The Pop-11 code
for this is here.
Integrating language, reasoning, planning and acting
Students can learn about the need to produce complete systems in which
different competences are combined. An example package, called "GBLOCKS" which
is a simplified version of Terry Winograd's famous SHRDLU system, was implemented
in Pop-11 for teaching purposes. It can be used simply for demonstrating the
behaviour of the system, or as a package that students can extend, e.g. by
extending the grammar, enriching the world, to include more objects and more
actions, or allowing a wider variety of conversational interactions.
A video of the GBLOCKS package is available here.
The "world" of the program consists of a simulated robot with a hand above a table on
which there are six blocks, three large and three small, coloured red, blue and green.
A few snapshots of the system running follow:
Typing 'help' produces instructions and sample sentences to type
Typing "is the small red block on a blue one" produces a parse tree shown in
two formats as a list structure (list of list of lists...), namely in a textual
form and a graphical form.
That is followed by a semantic representation of the QUERY.
The answer is derived from the information in the database, and printed out:
"Yes it is"
Typing "put the big green block on the little red one" also produces a parse
tree shown both textually and graphically.
After deriving the parse tree the program produces a semantic representation
of the state of the world to be produced if the command is obeyed. It then
formulates a plan to achieve that state, and executes the plan, showing in the
display when blocks are grasped, lifted and put down.
Teaching and learning can go in several different directions after this package
has been demonstrated. Some of them involved modifying or extending the program,
while other directions involve looking at some of the history of AI,
investigating ways in which human understanding differs from the program's
understanding, porting the program to a physical robot and many more.
(NB: Contemporary natural language understanding systems are based on far more
complex programming techniques than this demo. But that does not detract from
its educational value as an introduction to some of the problems.)
JUMP TO CONTENTS LIST
Analogical reasoning
The uses of foreach and forevery illustrated above can lead to
the idea of a program that records descriptions of different objects
or different situations in different databases, then uses various
ways of examining each database to produce more abstract
descriptions of the objects or situations.
It is then possible to compare two such descriptions
(a) to see what they have in common,
(b) to see how they differ, and
(c) to find one or more ways of transforming one of the
situations so as to be more like the other.
As shown by T.G. Evans in the 1960s, this sort of technique can be
the basis of analogical reasoning used in some intelligence tests.
Pop-11 has library (created by Jonathan Cunningham) and a set of
teach files that introduce these ideas using a mixture of pictures
and symbolic descriptions.
See for example TEACH EVANS.
(For more on the analogy problem and Evans' work see Margaret
Boden's 1978 book Artificial Intelligence and Natural Man, which not only
expounds many of the early achievements of AI, but also discusses
their relevance for psychology and philosophy. Evans' work is also
discussed in other AI textbooks, and in this tutorial by Jocelyn Paine.)
The "forevery" construct is very powerful since it allows items to
be compared two at a time, three at a time, four at a time, etc.
However exploring these techniques can quickly expose students to
one of the recurring problems in designing, or modelling,
intelligent systems, namely how to control combinatorial explosions.
That can also introduce students to the need for a still more powerful
formalism, such as LIB SUPER, mentioned above, or a logic programming
language such as Prolog.
An example run of the Pop-11 demo version of Evans' analogy program
is here.
A teacher who wished to illustrate the principles with simpler
examples, could copy the file and replace the picture drawing
procedures to use simpler pictures.
(The library was written in 1983, using an older version of Pop-11,
which is still accepted by the compiler in a special compatibility
mode.)
Jocelyn Paine has more Pop-11 examples here:
http://www.j-paine.org/dobbs/poplog.html
His web site starts:
I have just installed some software on my PC. It gives me Lisp,
Prolog, ML, and a language that ought to be better known but isn't,
Pop-11. It has an editor from which I can compile and run programs
in any of these languages. And in this editor, I can read HELP files
and TEACH files. Note that: TEACH files. For teaching Poplog, but
also AI. How many compilers have built-in AI tutorials? This one
does. Poplog.
I like Poplog because I used to teach AI with it. One of my students
wrote a poetry generator in Poplog Prolog. The first poem it ever
produced went, and I'm not making this up:
Oh poetry,
Thy power is beauty.
JUMP TO CONTENTS LIST
MISHAPs
Students should explicitly be encouraged (or led) to do things that
produce error messages (called 'MISHAP' messages in Pop-11, after we
noticed that the word 'error' upset some beginners!).
In a well designed teaching environment, the error messages have
rich semantic content that helps with debugging, as shown above.
Learning to test for things going wrong, identifying the nature of
the problems and fixing them is an important aspect of cognitive
development. (I was once told by a beginner student that she really
enjoyed debugging her code when it did not work. Alas students who
have been badly educated merely get depressed when their programs
don't work. For such students the main job of a computing teacher
may be to find ways to build up confidence until the student can
drive his/her own learning.)
JUMP TO CONTENTS LIST
Introducing linguistic interaction
After becoming familiar with the 'riverworld' domain, learners can be
invited to switch to a different task. For example, they can play
with the Pop-11 Eliza chatbot and then try to define their own simple
chatbot based on pattern matching as explained in TEACH RESPOND.
This introduces lists, patterns, conditionals, loops and thinking
about designing an architecture to handle ongoing interaction.
Some students have to be weaned off the Eliza task because it is
always possible to go on adding more and more rules to a chatbot,
and many find that enjoyable. But after a while no more real
learning happens.
Instead they can try combining the chatbot techniques with the
riverworld commands to provide a natural language interface to the
riverworld, so that the typed in command
putin(chicken);
is replaced with requests like:
please put the chicken in the boat
In addition, the use of the Pop-11 database to represent the state
of the world allows questions to be added to the interaction:
is the man in the boat?
where is the fox?
And if the program records the history of events
what happened to the chicken?
could cause the program to list all the events in which the
chicken's location was changed.
JUMP TO CONTENTS LIST
How programming leads to philosophy
(One of the ways)
The interaction with the Pop-11 database representation of the state
of the world (e.g. whether the individuals are on the left or right
side of the river or on the boat) gives semantic content to the
verbal interchanges, even though strictly speaking the computer does
not know anything about real rivers, boats, foxes, etc. That is a
topic students can be invited to discuss, leading on to questions
about whether machines can ever really understand what we say to
them, whether cameras and motors will make a difference and whether
human brains are usefully thought of as extremely sophisticated
computers.
(A paper proposing a syllabus developing these ideas for linking
philosophy with programming is here (PDF).)
JUMP TO CONTENTS LIST
Towards more principled natural-language interfaces
After playing with and observing limitations of chatbot style
pattern-based interfaces, students will probably be ready to meet
the more principled grammar based approach to language, introduced
in TEACH GRAMMAR.
This uses a library program that allows a grammar and lexicon
provided by the user to be used either to create a parser for
analysing sentences in accordance with the grammar or else to
generate random sentences that accord with the grammar. As the teach
file shows, the grammatical notation used for programming linguistic
information into the computer is interestingly different from the
notation used for specifying actions to be performed. That
difference can be a subject for philosophical discussion, or
discussion about how minds of language users work.
An exercise that students can try, suggested in the teach file, is
generating railway station announcements. Other possibilities
include opening sentences for a romantic novel, or rudely expressed
complaints about service in a restaurant! (Stroppy chatbots are very
popular with some learners.)
Typically, a student who has used the formalism to specify a grammar
and lexicon will get some surprises when the random generator is
used. For example, the specification for railway station
announcements might generate things like
platform 5 will depart from the 4.20 train to London
express luggage must not leave slow passengers unattended
That sort of surprise can lead to deep reflection on how to add more
categories to the grammar and the lexicon so as to control more
tightly what is generated. Alas, for some students, this may be the
first time they encounter concepts like 'verb', 'adjective',
'prepositional phrase' because of misguided educational policies
in the last few decades.
But it is never too late to learn such things, and what could be
better than learning by using the concepts to design something
that works?
An experimental package that might be developed differently by
different teachers is TEACH GRAMMAREXAMPLES (still untested),
which shows how, with the same set of words in the lexicon, two
different grammars can produce unconstrained or constrained sets of
"acceptable" sentences and sentence substructures, by "compiling"
semantic distinctions into syntactic and lexical distinctions. This
could be the basis of a number of student projects involving
programming at the level of grammatical rules rather than at the
level of the underlying programming language.
More examples are in TEACH STORYGRAMMAR, which shows how the same
pop-11 library can be used to generate simple (poor) stories and
(strange) haikus.
JUMP TO CONTENTS LIST
Additional Pop-11 TEACH files
In addition to the files mentioned above, there are many more
'TEACH' files, such as the 'TEACH ARITH' file, which
introduces arithmetic operations, and encourages learning by doing,
exploring, testing, and revising or extending programs. Examples
of the use of a few of the procedures introduced there were given
above and more can be seen here.
A more subtle and challenging TEACH file, TEACHNUMS, encourages
learners to investigate how numbers could be added to a programming
language that does not already support them, using lists to
represent numbers (in a 'unary' notation).
This example illustrates how a teach file can start easy, or even
trivial, and lead to deep and difficult challenges, in this case
about the nature of negative numbers and what operations on them
could mean.
(This could be a possible link to philosophy of mathematics.)
Some of the teach files provide introductions to the core concepts
of other languages, but using Pop-11's syntax, e.g. TEACH SUPER_EXAMPLE,
which introduces Pop-11's 'superdatabase' library, giving an
introduction to the main features of Prolog, but in Pop-11 syntax.
(Poplog also includes a full implementation of Prolog in its own syntax.)
Another example is TEACH RULEBASE which introduces rule-based
programming through an extension to Pop-11.
Using the same editor, students can also learn how to write proposals for
projects (or mini projects) and also draft reports.
The programming examples in the 'teach' files can be run from within
the poplog editor (Ved or XVed), by marking the lines and giving a
'doit' command (e.g. CTRL-D).
The learner can then modify the commands (in the teach files, which
are write-protected) using the editor and run them again, or copy
them and create new combinations and run them. The output of such
commands, including error messages will go into an editor buffer
where they are displayed, so that it is easy to look back at
previous outputs and error messages -- something that is not so easy
to provide with a purely graphical mode of interaction.
Users are not forced to use the Poplog editor. Instead they can
edit programs in another preferred text editor and copy the code
into a Pop-11 command window to be run. Or the whole file can be
written and then compiled by Pop-11 (without restarting Pop-11,
because it uses an incremental compiler, available at run time).
JUMP TO CONTENTS LIST
Using a pop-11 turtle, matcher and database to introduce problems about vision
Besides the turtle that is part of pop-11's 2-D graphics package,
there is another (much older) simulated turtle, developed in the
1970s that can draw into a 2-D array, by leaving a trail of
characters (asterisks by default) as it moves. This can then be
printed out or displayed on a screen to examine the results.
More importantly, the contents of the array can also be examined by
a computer program. So the computer, like the user, can find out the
results of performing various drawing operations.
The following packages are provided:
o The TEACH TURTLE file illustrates ways of drawing into the array
and displaying the results
o TEACH SEEPICS introduces techniques for perceiving structures
at different levels of abstraction in such pictures, and
o TEACH PICDEM illustrates ways of learning concepts by
abstracting from the details of perceived examples.
These are not intended to teach up to date sophisticated vision,
learning and recognition techniques, but to introduce young learners
to the problems and to some ways of thinking about them that can be
explored in a friendly AI programming language with helpful
libraries.
JUMP TO CONTENTS LIST
Are textual interfaces boring?
Although it seems to be an axiom of many people concerned with ways
of teaching programming that textual programming is too dull and too
difficult for young beginners, it is arguable that that merely
reflects the ill-considered kinds of programming examples that
teachers of programming and computer science have tended to use in
the past.
In other words, what may be thought of as boring text-based
programming tools can, when used by creative teachers, provide
extremely versatile playthings that can be combined, extended,
decomposed, re-organised, reinvented, and used as inspiration for
deep and enjoyable learning about a variety of computing and
non-computing topics.
Many of the topics relate to the nature of human thinking, learning,
perceiving and communicating. This contrasts with the emphasis on
moving around, colliding, avoiding, shooting, killing, dressing-up,
etc., in some other programming environments for learners.
JUMP TO CONTENTS LIST
Graphical vs textual programming interfaces
Although complex graphical programming interfaces are more
fashionable for young learners, and are clearly able to engage them
and foster both learning and collaboration, it is arguable that the
learning achieved is not so deep because of the limited forms of
expression provided by such programming interfaces -- e.g. the
difficulty of expressing some abstractions, such as use of recursive
calls.
That may not matter in the earliest stages of learning to program.
In any case, there are deep and enjoyable things that can be done
without graphical tools, or in addition to using the graphical
programming tools.
Learning to use textual specifications for structures and processes
is in itself an important part of education for thinking and
communicating about complex phenomena, including finding appropriate
levels of abstraction for solving problems, and for describing how
something complex works. (Many experienced programmers cannot do
that well.)
Some important forms of abstraction are well suited to graphical
formalisms (e.g. trees, graphs and maps). Others are more closely
related to textual formalisms, including logical expressions and
computer programs.
Pop-11 supports a variety of styles, including the 'logic programming'
style illustrated here and not well
supported by most programming languages, and also the styles used
for a variety of artificial intelligence techniques, in addition to
most of the conventional programming styles. It is much less
cluttered and more intuitive than Java. Aspects of Pop-11 overlap
with Common Lisp, with Scheme and with Prolog.
JUMP TO CONTENTS LIST
Teachers can experiment with their own teach files
Teachers are not forced to use the existing teach files. They can
produce their own (as many have done), or copy and modify the files
provided, to suit the needs of their pupils or to fit better with
local educational objectives -- or even the needs of individual
students. The use of an incremental compiler makes it easy to test
every new example, or every modified example very quickly,
especially if using the integrated text editor.
Modified versions of the existing teach files could be used for
younger learners as long as they can read and type -- a typing tutorial
is included, invoked by typing just 'ttt' to Pop-11. Before
keyboards were in every school it gave many first year university
students their first introduction to typing, by providing strings to
copy, which are then checked by the program. It was also used by
some pre-school children, brought in by members of academic staff!
Poplog (especially Pop-11) comes with a lot of library programs with
associated documentation that can be used as building blocks in
student projects, or can be used as the basis for learning a set of
techniques.
Creative teachers can produce new 'teach' files, and, if necessary,
corresponding new program libraries, that can be linked into search
lists for different groups of learners.
A set of teach files and corresponding code files can be grouped
within a directory, and a command provided to add the files in that
directory to documentation and program library 'search lists'.
Different 'search lists' for documentation and code libraries can be
given to different groups of students.
The same 'grouping' mechanism for code and documentation can be used
for students collaborating on a common project. Those local code and
documentation files can be stored separately from the main poplog
installation, and as they are all plain text files can easily be
given to other schools or made available on the web for others to
use -- unlike some programming environments that store user
creations in special formats that can only be interpreted by running
the package.
The educational philosophy behind all this is explained in this PDF paper
'Teaching AI and Philosophy at School?' and in the paper referenced below.
JUMP TO CONTENTS LIST
The core language, Pop-11, is in some ways like Python (though it has built in support for more programming paradigms), in some ways like Lisp (though with a more conventional syntax), in some ways like Scheme (because it handles function names like Scheme rather than Common Lisp), and also like 'Forth' because it supports stack manipulation, and partly like Prolog because it allows list processing to be done with a pattern matcher, and provides mechanisms for storing and manipulating information in a structured database, instead of dealing only with values of variables. E.g. see the TEACH DATABASE file for some examples. Because the tutorial database mechanism is relatively unstructured -- every stored item merely has to be a list of some kind, students can easily explore different ways of structuring information for different problems -- instead of always having to use (or fight) the structure provided (e.g. [object attribute value] -- provided in some systems).At a later stage, some students may start using the Poprulebase package, which introduces a more powerful framework for using structured databases in connection with condition-action rules, e.g. as often used in "expert systems". The TEACH EXPERTS tutorial gives a partial overview, with pointers to more things to try. Students can be led in a different direction by introducing them to the 'Superdatabase' (SUPER), which introduces logic programming in a style close to Prolog.
In an interview reported here, Peter Denning was asked:How has the switch to C++ and Java brought new problems?To which he replied:DENNING: Students get consumed with trying to master the mechanics of programs. They are so busy trying to make programs work, they get sidetracked from understanding the underlying concepts of their programs. Their perception is that "Computer Science 1" is really "Programming" and not concepts of computing. The complexity of these languages has become a monster that we don't know how to cope with. One of the consequences is a high dropout rate from our first courses - about 30 to 50 percent. Another is that plagiarism and copying of programs is a major industry as students "do anything" to pass those courses.As the preceding comments illustrate, Pop-11 can be used to introduce, with relatively little counter-intuitive clutter, a variety of common programming paradigms, including use of looping constructs, recursion, standard arithmetic (and some unusual extensions, such as ratios, complex numbers, and arbitrarily large integers (bignums) -- more details here), arrays, strings, list processing facilities, pattern matching (with pattern restrictions) to simplify construction and analysis of list structures (partly like Prolog), rule-based programming, neural nets, Object-Oriented programming techniques with multiple inheritance, (using facilities similar to CLOS; though, the phrase "Object Oriented" means different things to different people, as explained here).
Pop-11 also has a "lightweight process" mechanism that supports learning about co-routines or threads, and is used in a tutorial introduction to operating systems. (Using the facilities in RCLIB that tutorial could now be given a graphical interface.)
Like Scheme and functional languages, Pop-11 allows a "functional style" of programming, to be used, using higher order functions and closures, which can make some complex tasks very much simpler. (The Wikipedia entry gives more information about functional programming.) However, pop-11 does not have strong syntactic typing: it uses semantic types and run-time type checking.
The importance of teaching students to think about the architecture of a complete program is not always emphasised, alongside designing ontologies, forms of representation to be used and algorithms for the various sub-systems. Even a beginner's introduction to a very simple chatbot can introduce ideas about architecture, e.g.*------* --- > --- *---------* --- > --- *----------------* | USER | |INTERFACE| |INFERENCE ENGINE| *------* --- < --- *---------* --- < --- *----------------*Diagrams representing architectures are probably more important in the long run than flow charts, which cannot cope well with most kinds of structured programming (using call and return, with recursion), and do not cope at all with the design and use of different forms of representation (e.g. trees, graphs, pattern-based databases).
Learning about a variety of AI programming techniques
There are many 'teach' files developed at Sussex University, Birmingham University and elsewhere, introducing concepts and techniques, with exercises ranging from simple program completion to development of whole systems, some of them making use of packages provided by tutors to hide details for beginners: e.g. some basic programming and AI teach files here and here, including the previously mentioned tutorial on building a simple chatbot based on pattern matching which can be followed by the introduction to grammars, parsing. sentence generation (also mentioned above), and TEACH STORYGRAMMAR, which introduces generation of stories and haikusAlthough Pop-11 is specially well suited for AI/Cognitive Modelling there are tutorials on many standard programming techniques, some mentioned above, including use of recursion for list-processing and both simple, and more complex exercises treating lists as sets (with answers available).
JUMP TO CONTENTS LIST
There are many more 'Teach files' available here, all if them using plain text both for exposition and for programming code, so that they are all easily editable by teachers if desired, e.g. to make them more suitable to the intended learners, either by including easier or more difficult exercises, adding (or removing) hints or changing contents of the examples to suit a particular culture or environment.If the editing is done using the Poplog editor Ved, then all the examples can be tested inline, and sample outputs generated in the editor to include in the teach files as was done in most of the files listed below. The more advanced and specialised teaching materials introduce many topics relevant to general programming and also AI/Cognitive Science, and Linguistics, including:
- neural nets, thanks to Riccardo Poli, who also provided
- an introduction to the use of genetic algorithms for evolutionary computation (also by Riccardo Poli);
- rule based techniques as in expert systems, and
- the use of the SimAgent "Agent Toolkit" with several introductory tutorials.
- The Popvision tutorials by David Young at Sussex University introduce a variety of image interpretation techniques as well as tools for generating and manipulating images.
- A linear algebra package, developed by David Young, based on Lapack and BLAS is described here, here, and here.
This links in Fortran libraries invoked by Pop-11, and provides many of the facilities of packages like matlab, though using the syntax of Pop-11. This is included in the Popvision package.(To be extended).
JUMP TO CONTENTS LIST
Other sources of information about using Pop-11 for teaching
A book, Computers and Thought, by Mike Sharples and others, originally published by MIT Press, though now out of print, provides an introduction to Cognitive Science/AI using Pop-11. The text is online here.A Pop-11 programming primer for people with previous programming experience, here.
Poplog also includes some tutorial exercises and online documentation on Prolog, Lisp, and Standard ML, though not as much as for Pop-11.
A web site with HTML versions of poplog documentation.
(Partly out of date, but mostly OK.)
Why teaching beginners requires powerful systems
This article Beginners need powerful systems explains the benefits of using a non-"toy" language for teaching beginners, to support variable rates of progression, to allow individual learners to go on developing and diversifying their expertise over an extended period, and to allow creative teachers to provide additional libraries and support tools. (A great deal of teaching using Poplog has been "team-teaching" where tutors build on one another's program library and documentation resources.)
Relating Programming to Biology, Cognitive Science, Philosophy
Some of the ideas behind the programming examples and tools presented here are part of a philosophy of computing education which is not primarily aimed at producing skilled programmers, but rather at broadening the minds of a wide range of learners, researchers and teachers who need to understand various parts of the natural world as involving information-processing systems of various kinds, many of them extremely complex, especially some of the products of biological evolution, e.g. human and animal minds. These ideas regarding education are spelled out in this paperhttp://www.cs.bham.ac.uk/research/projects/cogaff/09.html#apa
Teaching AI and Philosophy at School?
Newsletter on Philosophy and Computers, American Philosophical Association, 09, 1, pp. 42--48,
JUMP TO CONTENTS LIST
The built in text editor Ved/XVed
The built in text editor Ved (or its multi-window version XVed), provides a general purpose interface between the user, the user's programming input, the output from the compilers, the teach files, other documentation files, and the program libraries. Users can write things into the Editor buffer and can read what is in the editor buffer. Similarly the compiler can read what is in the buffer (and obey instructions) and can write things in the buffer. So the editor's text buffer acts as a two-way communication channel between user and programs run, and has done for nearly three decades, just as many graphical interfaces now do.It also provides simple actions to invoke documentation or tutorial files. For example, the Pop-11 command
uses XXXcan get the editor (via the Pop-11 compiler) to make sure that the XXX library has been compiled in the current session, so that its facilities can be used, including the HELP and TEACH files provided by the package. In many cases that will also automatically load other packages and extend both program and documentation search lists for items accessible using Ved's hypertext facilities.The command
showlib XXXasks the editor to read in and display the code of the XXX library file (that may contain cross-references to other documentation and code files). The commandhelp XXXwill invoke documentation on XXX for people who already have some experience with XXX, whereas the commandteach XXXasks the editor to read in a tutorial on XXX for beginners, usually giving examples to play with, by editing and recompiling bits of text in the documentation window. (There is no need to copy the text to another window.) Moreover placing the text cursor to the left of an identifier in a program (e.g. next to the name of a system procedure or library procedure) and typing ESC+h will invoke a documentation file with information about the identifier.These mechanisms can be used also by teachers to produce their own teaching materials for learners -- which is how all the teaching documentation was developed originally. On a shared server this makes it particularly easy for teachers to cooperate in building up cumulative layers of teaching materials. The integrated editor also allows students to produce documentation in which the examples are tested -- reducing the frequency of documentation bugs.
Since the same mechanisms can be used for code and documentation of many different levels of sophistication, the same system allows students at all levels (including both absolute beginners and very young children, as well as experienced programmers new to AI) to learn about many aspects of both general programming and Artificial Intelligence and Cognitive Science, by designing, implementing, testing, extending, analysing working programs, or program fragments. At an advanced stage they can use the same interface to develop projects, as several final year students, MSc students and PhD students have done.
Using the Poplog editor is not mandatory
There are several advantages in using the Poplog editor, Ved/XVed, but people who would rather use an editor with which they are familiar, then copy and paste text between their editor and the pop-11 command line can do so. There is also an Emacs interface to Poplog that provides most of the advantages of the integrated editor (though it requires far more memory!).For more information on the editor and how to use it see this overview.
Extended learning trajectories
The provision of continuous learning trajectories from absolute beginner to advanced researcher within the same framework was a major design objective, enabling teachers and their beginner and non-beginner students to use the same system. A subroutine or package produced by an older student could then easily be invoked and used (or copied and modified) by a less advanced student. Of course, emphasising assessment more than learning can rule such collaboration out.One of the advanced projects using Pop-11 was development of Poplog itself: because the developers were constantly using all its features for their own development work they found most bugs before they could reach users. This has made it an unusually robust package. Bugs reported in the years since 1999 are listed here. Many are concerned with installation procedures and libraries rather than the core system.
For more information on Poplog and its history see
http://www.cs.bham.ac.uk/research/projects/poplog/poplog.info.html
A history of developments in e-learning using Pop-11 and Poplog, starting at Sussex University in 1976 can be found here.
Editor, documentation and libraries
The environment has many of the interactive features of interpreted languages, though the Poplog languages are all incrementally compiled to machine code for efficiency. The 'TEACH' files, and other documentation files, are accessible through its integrated visual editor (Ved/XVed), which 'knows about' the compilers, the program libraries and the documentation libraries, and is extendable since it is implemented in Pop-11. E.g. a tutorial file can have a hypertext link to other documentation or to program libraries. Programming examples can be run from inside the editor, then modified and run again, without restarting the editor or Poplog.For Emacs users there is a conversion package that extends Emacs to support integration with the Pop-11 compiler. Another option, for people who do not wish to use a new editor is to type commands into the Pop-11 (or Prolog, or Lisp, or ML) prompt in a shell command line, while editing and reading documentation quite separate editor. This will add some inconvenience and slow down development a little. (To a 'normal' edit/compile/test loop.)There are many libraries extending the core system to support various kinds of programming tasks. For example the SimAgent toolkit supports exploration of architectures for more or less intelligent agents. The library and documentation system make use of search lists, allowing packages and teaching materials developed by different teachers, students and researchers to be combined flexibly, strongly encouraging team teaching.
There is also a collection of libraries and tutorials related to computer vision, i.e. image analysis and interpretation, in David Young's "Popvision" Library including neural net, array manipulation, and linear algebra utilities.
Some of the Poplog/Pop11 graphical facilities are illustrated here, and there are movies showing some student AI projects, based on the the SimAgent toolkit.
JUMP TO CONTENTS LIST
Poplog/Pop-11 as a commercial product (1983-1998)
For many years Poplog was an expensive commercial product, first sold commercially by Sussex University for use on VAX+VMS (for UK£3,000, and much less for academics) in 1982, and then continually developed, ported to other platforms, and commercially supported up to 1998, first by Systems Designers (from 1983) and later by a spin-off, Integral Solutions Ltd (founded in 1989).At one stage the commercial price was UK£1,500 (+VAT) for workstations, though the educational price was always much lower. Poplog was a solid, reliable, commercial product, used mainly, though not entirely, for AI and Software Engineering research, development and teaching. By about 1992 sales had exceeded $5,000,000.
The most famous product implemented in Poplog (mainly Pop-11) was the Clementine Data Mining system, developed by ISL, as a result of which they were bought by SPSS, so that Clementine (later renamed as "PASW modeller"), could be integrated with their other data-mining tools (after re-writing in Java and C++, with some loss of functionality). widely used (More on Clementine)
Another product based on Poplog was a software validation toolkit produced by Praxis.
Additional Information about Poplog and Pop-11
Poplog runs on PC+Linux and a number of Unix systems, and can also
work on Windows.
Information about downloading and installing it can be found here.
Information about how poplog works, including how the Poplog Virtual Machine supports several different languages (including Pop-11, Common Lisp, Prolog, Standard ML, and others) can be found in:
http://www.cs.bham.ac.uk/research/projects/cogaff/10.html#1005
POPLOG's two-level virtual machine support for interactive languages,
Robert Smith and Aaron Sloman and John Gibson,
in Research Directions in Cognitive Science Volume 5: Artificial Intelligence,
Eds. D. Sleeman and N. Bernsen, Lawrence Erlbaum Associates, pp. 203--231, 1992,
Further information is available on Wikipedia and other sites:
- Some sample lecture notes on AI and General Programming in Pop-11
- http://en.wikipedia.org/wiki/Poplog
- http://en.wikipedia.org/wiki/POP-2
- http://en.wikipedia.org/wiki/POP-11
- http://en.wikipedia.org/wiki/COWSEL
- Online Pop-11 primer
- Poplog as a Learning Environment
- 1976 computer-based learning environments.
- Pop-11 section of the Rosetta Code web site.
- Waldek Hebisch's (PDF) Draft Pop-11 book version of How to think like a computer scientist by Allen B. Downey.
- Pop-11 programming examples by Waldek Hebisch
-
David Young's popvision library
(WARNING: not all the popvision documentation files will be readable in a web browser, because they use a special character encoding to make the files more attractive in Ved. This is fixed for Poplog v15.63) -
Hakan Kjellerstrand has (enthusiastically) provided tutorial
examples in Pop-11 on his web site
"The Pop-11 programming language and Poplog environment"
http://www.hakank.org/webblogg/archives/001320.html - First year AI programming module at University of Birmingham.
- Information about Poplog users, Products and Services provided by ISL, before they were taken over by SPSS.
- Documentation Directories
I suspect a good team project that could be developed in stages
across a few teams would be a more portable version of
this machine code emulator
which runs on Windows only. As far as I can tell from the Web site
Pop-11 with its RCLIB package would make this feasible and fun. For
some videos of past student projects see
http://www.cs.bham.ac.uk/research/projects/poplog/figs/simagent/