Firbush News, No 6. pp 26-30, July 1976
Recent [Artificial Intelligence] developments with CODIL
C.F. Reynolds, Department of Computer Science, Brunel University, England, U.K.
CODIL (1, 2) is a computer language designed for the non-mathematically orientated user with open-ended real-life information processing problems. Every attempt has been made to minimise mathematical sophistication of the basic language framework, and to find a processing algorithm and storage strategy simple enough to seem "obvious" to the proposed users. In achieving this goal many of the generally accepted features of computer languages - in particular the distinction between program and data - were abandoned as being too sophisticated. The resulting interpreter works by comparing strings of items and the basic algorithm is simple enough to be described on the back of an envelope.
While the simplicity of the language and interpreter is important, it is equally important that the system can be used for non-trivial problems. As such it must be able to tackle problems which are incomplete or ambiguous to a greater or lesser degree. Fortunately the very simplicity of the approach makes this type of flexibility possible - if only because there are no 'primitive operators' sophisticated enough to be seriously offended by uncertain information.
By the end of 1974 the CODIL system was working operationally on the ICL 1903A computer at BruneI University, and it had been tested on a very wide range of applications on a scale ranging from the very small up to a data base of research clinical records for a department in a local hospital. It had been pointed out (3) that the processing algorithm was not only very simple, but could be explained in evolutionary terms. In addition, the main work locations, the facts, show a number of properties in common with human short term memory. However, apart from such speculations, and the hand coding of a few New Scientist Tantalizers, other activities precluded detailed research into the language's relevance to A.I.
During 1975 the position has completely changed. The first significant development was the inclusion of a learning "MEMORY". This file looks like any other to the user and to the main part of the interpreter. However, its internal structure is different in that each statement has associated with it an activity and a usage indicator. Varied learning strategies may be examined by altering the size of the MEMORY, the learning and forgetting ratio. recall levels, etc., and by giving positive or negative reinforcements In addition it is used for internal sorting and optimisation of files. These included inputting a "program" in jumbled order and using MEMORY to reorganise statements into the right order to produce a result on a single pass, discarding surplus irrelevant information.
The next development was that CODIL could be readily extended to provide significant algorithmic processing power, despite the original design that the user should not need to know what an algorithm is. The first non-trivial application chosen to test this new facility was to write an interactive (or batch) problem solving aid called TANTALlZE. This allows the user to define the problem by supplying a series of keywords and then answering a series of questions. TANTALIZE then enters a "compilation" phase in which the information provided is pre-processed prior to the main search phase. The search itself may proceed in several different ways (either separately or in combination).
(a) In depth search, in which the action / selections are applied recursively until the goal is found or no more progress is possible. When this happens the solver backtracks until an alternative route is found.
(b) In breadth search, in which the effects of applying one action, two actions, ... , etc., are examined in full until a solution is found.
(c) A directed search in which the distance from the goal is evaluated by a simple system generated distance function and the most promising path taken.
(d) An extension of the above in which the user provides a problem specific distance function. This allows in depth searching in very promising situations, and also allows sufficiently unpromising leads to be discarded entirely.
(e) Actions may suggest one or more possible successor actions.
(f) Non-standard searching techniques can be introduced by modifying the information written to or collected from the files holding the intermediate problem states.
(g) By using the learning file, MEM0RY, to hold intermediate states it is possible to modify the course of the search by restricting the capacity of MEMORY and/or introducing a non-zero forgetting rate. This can lead to situation where the solver will only succeed if supplied with a good distance function, or where the solver is made to prefer recently generated problem states over more favourable, but older ones. This type of performance is clearly relevant to human problem solving. (A zero forgetting rate and a large enough MEMORY gives a graph traverser behaviour).
In unfavourable conditions, searching may take an inordinately long time and various techniques are available to speed the process. For instance the particular lead being followed is abandoned as soon as an illegal or prior situation is reached (assuming these have been defined). In addition rapid back tracking is provided for the situation in which it is not necessary to try different permutations of the actions.
Great savings can be made by ensuring that actions and selections are only made when they are likely to be productive. There are a variety of facilities available, and the most sophisticated of these include backtracking from the goal and extensive constraint processing of selections. In one example a suitable combination of 4 knights / steeds / helmets / banners / shields / plumes is required. The constraint processing is so efficient that the resulting problem space contains a mere 34 items compared with the minimum of 24 items needed to define the solution state and a maximum of 63,826,261.
Another important aspect of the solver is the series of facilities for inputting simplified problem definitions. For instance, the bridges of Konigsberg problem involves the crossing of each bridge in either of two directions. However only one direction need be described as the description can be automatically expanded by using the correct keyword in the problem description preamble.
Finally, the user has access to virtually the full facilities of the CODIL language to augment the problem definition and this may well extend to the modification of the solver and its work files. In particular the user may TRY AGAIN after modifying files such a ILLEGAL, GOAL and TERMINATE, and may even get the solver to carry out such modifications automatically. Thus when a goal is reached it may be used to produce new goal, as is done when the aim is to find a minimum value.
Problems that have been solved to date include the missionaries and cannibals crossing the river, placing eight queens on a chess board in such a way that no queen can capture another, filling water jugs and helping the monkey to get a banana. It fails to cross the seven bridges of Konigsberg. Over 30 New Scientist Tantalizers have been solved (some more than once using different definitions), and a number of similar problems solved by other problem solvers have also been tackled. Other miscellaneous tasks include finding the minimum cost of holding stock, searching external files, and generating the nursery rhyme "One man went to mow". Detailed comparisons with REF-ARF (R. E. Fikes, Artificial Intelligence 1 (1970), 27-120) are under way and have shown that TANTALIZE is well over an order of magnitude faster, about an order of magnitude smaller (in terms of the number of source statements), and in virtually every case the problem definitions are shorter and much simpler.
To conclude: In CODIL we have a single computer system that provides:
1). A good man-machine interface aimed at the non-mathematician.
2). An operational system for handling open-ended and poorly defined life problems.
3). A processing algorithm and storage structure that to some extent mimics human information processing, and which is explicable in evolutionary terms.
4). An inbuilt learning facility which can be tuned to give a wide range of learning behaviour.
5). The capability for supporting a powerful and readily extendable heuristic problem solving system.
6). Comparatively low computer processing overheads.
7). Minimal human effort in setting up systems (TANTALIZE represent! less than 6 man-months effort, and the vast majority of the time was in setting up and testing the problems solved).
Firbush News was a newsletter circulated among the Firbush group of Artificial Intelligence research departments around the world, and published from the Machine Intelligence Research Unit at the University of Edinburgh.
The paper as published omitted the original source references. These have been reinserted and listed below
(1) CODIL: Part 1: The Importance of Flexibility, Computer Journal, Vol 14, pp 217-229, August, 1971.
(2) CODIL: Part 2: The CODIL language and its interpreter, Computer Journal, Vol 14, pp 327-332, November, 1971.
(3) An Evolutionary approach to Artificial Intelligence, Proceedings, Datafair 73, pp 314-320, April 1973.