.EQdelim $$.EN.ls 1.cePROGRAMMING BY EXAMPLE REVISITED.sp.ceby John G. Cleary.ceMan-Machine Systems Laboratory.ceUniversity of Calgary..sp.sh "Introduction".ppEfforts to construct an artificial intelligence have relied onever more complex and carefully prepared programs.  While useful inthemselves, these programsare unlikely to be useful in situations where ephemeral andlow value knowledge must be acquired.  For example a person (or robot)working in a normal domestic environment knows a lot about whichcupboards have sticky doors and where the marmalade is kept.  It seemsunlikely that it will ever be economic to program such knowledge whether this be via a language or a discourse with an expert system..ppIt is my thesis, then, that any flexible robot system working in thereal world must contain a component of control intermediatebetween hard wired 'reflex' responses and complex intellectual reasoning.  Such an intermediate system must be adaptive, be ableto carry out complex patterned responses and be fast in operation.It need not, however, carry out complex forward planning or be capableof introspection (in the sense that expert systems are able to explaintheir actions)..ppIn this talk I will examine a system that acquires knowledge by constructing a model of its input behaviour and uses this to select itsactions.  It can be viewed either as an automatic adaptive system  oras an instance of 'programming by example'.  Other workers haveattempted to do this, by constructing compact models in some appropriateprogramming language:e.g. finite state automata [Bierman, 1972], [Bierman and Feldman, 1972]; LISP [Bierman and Krishnaswamy, 1976]; finite non-deterministicautomata [Gaines,1976], [Gaines,1977],[Witten,1980]; high level languages [Bauer, 1979], [Halbert, 1981].These efforts, however, suffer fromthe flaw that for some inputs their computing time is super-exponential in the numberof inputs seen.  This makes them totally impractical in any system whichis continuously receiving inputs over a long period of time..ppThe system I will examine comprises one or more simple independentmodels.  Because of their simplicity and because no attempt is made to construct models which are minimal,the time taken to store new information and to make predictions is constant and independent of the amount of information stored[Cleary, 1980].  This leads to a very integrated and responsive environment.All actions by the programmer are immediately incorporated into the programmodel. The actions are also acted upon so that their consequences are immediately apparent.However, the amount of memory used could grow linearly with time. [Witten, 1977] introduces a modelling system relatedto the one here which does not continually grow and which can be updatedincrementally..ppIt remains to be shown that the very simple models used are capable of generating anyinterestingly complex behaviour.In the rest of thistalk I will use the problem of executing a subroutine to illustratethe potential of such systems.The example will also illustrate some of the techniques which have beendeveloped for combining multiple models, [Cleary, 1980], [Andreaeand Cleary, 1976], [Andreae, 1977], [Witten,1981].  It has also beenshown in [Cleary, 1980] and in [Andreae,1977] that such systems cansimulate any Turing machine when supplied with a suitable external memory..sh "The modelling system".ppFig. 1 shows the general layout of the modeller.  Following the flowof information through the system it first receives a number of inputsfrom the external world.  These are then used to update the currentcontexts of a number of Markov models.  Note, that each Markov modelmay use different inputs to form its current context, and that theymay be attempting to predict different inputs.  A simple robotwhich can hear and move an arm might have two models; one, say, inwhich the last three sounds it heard are used to predict the nextword to be spoken, and another in which the last three sounds and the lastthree arm movements are used to predict the next arm movement. .ppWhen the inputs are received each such context and its associated prediction (usuallyan action) are added to the Markov model.  (Nocounts or statistics are maintained \(em they are not necessary.)  When thecontext recurs later it will be retrieved along with all the predictionswhich have been stored with it..ppAfter the contexts have been stored they are updated by shifting in the new inputs. These new contexts are thenmatched against the model and all the associated predictions are retrieved.These independent predictions from the individual Markov modelsare then combined into a single composite prediction.(A general theory of how to do this has beendeveloped in [Cleary, 1980]).  .ppThe final step is to present this composite prediction to a device I have called the 'choice oracle'.This uses whatever information it sees fit to choose the next action.There are many possibilities for such a device.  One might be to choosefrom amongst the predicted actions if reward is expected and to choosesome other random action if reward is not expected.  The whole system then looks likea reward seeking homeostat.  At the other extreme the oracle might bea human programmer who chooses the next action according to his ownprinciples.  The system then functions more like a programming byexample system \(em [Witten, 1981] and [Witten, 1982] give examples of such systems.[Andreae, 1977] gives an example of a 'teachable' system lying betweenthese two extremes..ppAfter an action is chosen this istransmitted to the external world and the resultant inputs are usedto start the whole cycle again.  Note that the chosen action willbe an input on the next cycle..sh "Subroutines".ppAn important part of any programming language is the ability to write a fragment of a program and then have it used many times without it havingto be reprogrammed each time.  A crucial feature of such shared code isthat after it has been executed the program should be controlled by thesituation which held before the subroutine was called. A subroutine can be visualised as a black box with an unknown and arbitrarily complex interior.There are many paths into the box but after passing through each splits againand goes its own way, independent of what happened inside the box..npAlso, if there are $p$ paths using the subroutine and $q$ different sequenceswithin it then the amount of programming needed should be proportional to$p + q$ and not $p * q$.  The example to follow possess both these propertiesof a subroutine..rh "Modelling a Subroutine."The actual model we will use is described in Fig. 2.  There are two Markovmodels (model-1 and model-2) each seeing and predicting different parts ofthe inputs.  The inputs are classified into four classes; ACTIONs thatmove a robot (LEFT, RIGHT, FAST, SLOW), patterns that it 'sees' (danger,moved, wall, stuck) and two types of special 'echo' actions, # actionsand * actions (*home, #turn).  The # and * actions have no effect on the environment,their only purpose is to be inputs and act as place keepers for relevantinformation.  They may be viewed as comments which remind the system ofwhat it is doing.  (The term echo was used in [Andreae,1977], where theidea was first introduced, in analogy to spoken words of which onehears an echo.).ppModel-2 is a Markov model of order 2 and uses only # actions in itscontext and seeks to predict only * actions.  Model-1 is a Markov model of order 3 and uses all four classes of inputs in its context.  Itseeks to predict ACTIONs, # actions and * actions.  However, * actionsare treated specially.  Rather than attempt to predict the exact * actionit only stores * to indicate that some * action has occurred.  Thisspecial treatment is also reflected in the procedure for combining thepredictions of the two models.  Then the prediction of model-2 is used,only if model-1 predicts an *.  That is, model-1 predicts that some * action will occur and model-2 is used to select which one. If model-1does not predict an * then its prediction is used as the combined predictionand that from model-2 is ignored..ppThe choice oracle that is used for this example has two modes.  Inprogrammer mode a human programmer is allowed to select any actionshe wishes or to acquiesce with the current prediction, in which caseone of the actions in the combined prediction is selected.  Inexecution mode one of the predicted actions is selected and theprogrammer is not involved at all..ppBefore embarking on the actual example some points about the predictionsextracted from the individual Markov models should be noted.  First, if no context can be found stored in the memory which equals the currentcontext then it is shortened by one input and a search is made for anyrecorded contexts which are equal over the reduced length.  If necessarythis is repeated until the length is zero whereupon all possibleallowed actions are predicted..ppFig. 3 shows the problem to be programmed.  If a robot sees danger itis to turn and flee quickly.  If it sees a wall it is to turn and returnslowly.  The turning is to be done by a subroutine which, if it gets stuck when turning left, turns right instead..ppFig. 4 shows the contexts and predictions stored when this is programmed.This is done by two passes through the problem in 'program' mode: onceto program the fleeing and turning left; the other to program the wallsequence and the turning right.  Fig. 5 then shows how this programmingis used in 'execute' mode for one of the combinations which had not beenexplicitly programmed earlier (a wall sequence with a turn left).  Thefigure shows the contexts and associated predictions for each step.(Note that predictions are made and new contexts are stored in bothmodes.  They have been omitted from the diagrams to preserve clarity.).sh "Conclusion".ppThe type of simple modelling system presented above is of interest for anumber of reasons.  Seen as a programing by example system, it is very closely integrated. Because it can update its models incrementally in real timefunctions such as input/output, programming, compilation and executionare subsumed into a single mechanism. Interactive languages such as LISPor BASIC gain much of their immediacy and usefulness by being interpretive and not requiring a separate compilation step when altering the sourceprogram. By making execution integral with the process of program entry(some of) the consequencs of new programming become immediately apparent..ppSeen as an adaptive controller, the system has the advantage of being fastand being able to encode any control strategy. Times to update the modeldo not grow with memory size and so it can operate continuously in real time..ppSeen as a paradigm for understanding natural control systems, it has theadvantage of having a very simple underlying storage mechanism. Also,the ability to supply an arbitrary choice oracle allows for a widerange of possible adaptive strategies..sh "References".in +4m.sp.ti -4mANDREAE, J.H. 1977Thinking with the Teachable Machine.  Academic Press..sp.ti -4mANDREAE, J.H. and CLEARY, J.G. 1976A New Mechanism for a Brain.  Int. J. Man-Machine Studies8(1):89-119..sp.ti -4mBAUER, M.A. 1979 Programming by examples. Artificial Intelligence 12:1-21..sp.ti -4mBIERMAN, A.W. 1972On the Inference of Turing Machines from Sample Computations.Artificial Intelligence 3(3):181-198..sp.ti -4mBIERMAN, A.W. and FELDMAN, J.A. 1972On the Synthesis of Finite-State Machines from Samples oftheir Behavior.  IEEE Transactions on Computers C-21, June:592-597..sp.ti -4mBIERMAN, A.W. and KRISHNASWAMY, R. 1976 Constructing programs from example computations. IEEE transactions on Software Engineering SE-2:141-153..sp.ti -4mCLEARY, J.G. 1980An Associative and Impressible Computer. PhD thesis, Universityof Canterbury, Christchurch, New Zealand..sp.ti -4mGAINES, B.R. 1976Behaviour/structure transformations under uncertainty.Int. J. Man-Machine Studies 8:337-365..sp.ti -4mGAINES, B.R. 1977System identification, approximation and complexity.Int. J. General Systems, 3:145-174..sp.ti -4mHALBERT, D.C. 1981An example of programming by example. Xerox Corporation, Palo Alto, California..sp.ti -4mWITTEN, I.H. 1977An adaptive optimal controller for discrete-time Markovenvironments.  Information and Control, 34, August: 286-295..sp.ti -4mWITTEN, I.H. 1979Approximate, non-deterministic modelling of behavioursequences.  Int. J. General Systems, 5, January: 1-12..sp.ti -4mWITTEN, I.H. 1980Probabilistic behaviour/structure transformations usingtransitive Moore models.  Int. J. General Systems, 6(3):129-137..sp.ti -4mWITTEN, I.H. 1981Programming by example for the casual user: a case study.Proc. Canadian Man-Computer Communication Conference, Waterloo,Ontario, 105-113..sp.ti -4mWITTEN, I.H. 1982An interactive computer terminal interface which predicts user entries. Proc. IEE Conference on Man-Machine Interaction,Manchester, England..in -4m