The NewtonScript Programming Language


Arno Schödl, Georgia Institute of Technology


 


NewtonScript, developed for the Apple Newton PDA platform, is a prototype-based programming language. Rather than two levels of abstraction, class and object, there is just one, the object. Major design goals of the language were small memory consumption of the created programs and the ability to easily program graphical user interfaces. Both are well met by prototype-based languages. A third design goal, good learnability, was attained by an easy syntax. Though, the author's experience with a class project revealed that some other simplifying features as well as the dynamic typing of the language in conjunction with a bad programming environment make programming and especially debugging of NewtonScript programs difficult.

1. Introduction

The Apple Newton MessagePad was introduced into the market on August 3, 1993. With the Message Pad the former Pepsi manager and then CEO of Apple Computer, John Sculley coined the term Personal Digital Assistant, or PDA, which is the common term today for a small handheld computer to perform personal organisation tasks like note taking, scheduling, and communication. The Newton has a built-in handwriting recognition capability that allows to recognize almost natural handwriting anywhere in the screen area.

The original Message Pad had a 20 MHz Acorn Risc Machine (ARM) 610 processor, 640 KB RAM and 4 MB ROM. The RAM was further divided up into system RAM of 482 KB and only 158 KB available to programs for their code and data. Heap space was only 50 KB. These memory constraints had a big influence on the design of NewtonScript, the main application language for the Newton. The language was designed by Walter R. Smith who also wrote the interpreter and the compiler for NewtonScript and parts of the Newton's operating system.

The language design was influenced by LISP and SELF, a prototype-based language developed at Stanford university and published in 1988.

NewtonScript is like SELF prototype-based. Rather than two different layers of abstraction, classes and objects, found in class-based languages like Eiffel or C++, prototype-based languages only have objects. Functions are treated as objects as well, and can be assigned to variables or passed as function parameters. This plus the fact that all statements return a value gives NewtonScript a little bit of a functional aspect. The influence of LISP is obvious here. NewtonScript is as default compiled into byte code and executed by an interpreter, though compiling NewtonScript to native code is possible at a per-function granularity and recommended for performance-critical program parts. NewtonScript, like most dynamic languages, has a built-in garbage collection, thus freeing object storage space explicitly is not necessary.

In the following sections I will describe some features of NewtonScript to illustrate the difference between the prototype- and the class-based OO-programming paradigm and to give some idea of the NewtonScript flavor.

2. Types in NewtonScript

All typing is dynamic. Variables are not declared, except for scoping or optimization purposes, and any variable can hold any type. When a previously unused variable is used it is automatically created. Type violations are detected at run time. The language inherent type system is restricted to six basic types. Types are called classes in NewtonScript, although they are not templates to build objects with like in class-oriented languages such as C++ or Java. It is better to think of them as tags attached to some object. All objects are self-describing, there are functions in the standard environment to test an object's type.

2.1 Built-in types

The primitive type (or class) immediate has the subtypes integer, character and boolean. All these are stored in expanded form directly in the variable. All other types are reference types and behave as such in assignments and parameter passing. There are three basic reference types, binary, array and frame. The special value NIL is similar to a NULL in C, it denotes an empty reference. It is also used to denote the false boolean value.

The three built-in binary types are string, real, and symbol. While the first two are self-explanatory, symbol needs some explanation. A symbol is the type of a NewtonScript identifier. Variable or function names have a type which is symbol! By putting a single quote in front of a character sequence the programmer can denote a symbol rather than the entity meant by this symbol. Symbols are used for example as constants in a certain context, here to define a fill pattern in a drawing function call:

:DrawShape( mycircle, fillPattern: 'vfBlack );

Symobls are also used to pass a function name rather than a function reference to some other function, or to denote user-defined types, as we will see later.

The main difference between an array in NewtonScript and in other languages is that an array in NewtonScript can hold a collection of objects of different types. An array consisting of an integer, a string and another array of an integer and a character is perfectly fine. Again, no declaration is necessary:

myArray := [ 3, "Hello", [ 7, $A ] ];

NewtonScript's dynamic extension of arrays makes them similar to lists in functional languages.

A frame is the object data structure in NewtonScript. It is similar to a structure in C or a record in Pascal, elements of a frame are designated by a symbol rather than by a number. Like arrays frames need not to be declared. An element of an array or a frame is called a slot which can be either an attribute or a function reference. Array and frame slots can be inserted or deleted dynamically at run time.

A declared frame or array is only created once, you can replicate it by assigning the reference to another variable, or by cloning it, thereby creating a real copy of the contents. Frames with slots containing functions are similar to classes in class-oriented languages like Eiffel or C++. This code fragment shows a frame with some slot functions:

func myfunc() begin
   Stack := {
      class: 'stack,
      Content: [],
      Push: func (item) begin
         AddArraySlot(Content,item);
         /* Adds the item as the new last element to the array */
      end,
      Pop: func () begin
         local item:=Content[Length(Content)-1];
         ArrayRemoveCount(Content,Length(Content)-1,1);
         item;
         /* the last expression is always the function result,
            here item is returned */
      end
   };
   Stack:Push(1);
   Stack:Push(2);
   Print(Stack:Pop()); /* Print does debugging output */
   Print(Stack:Pop());
end;

2.2 User-defined types

Initially an object's class is set to its data structure type, a string is of class string and a frame is of class frame. Compliant with the tag character of types in NewtonScript it is possible to replace the initial type of any reference object with a new one. The built-in function SetClass attaches a symbol to a reference object as its new class name. The class symbol is stored in some special slot of the object.

There are functions in the standard environment to query an object's class. Since Newton 2.0, by including a dot into the class symbol even a subclass relationship can be expressed. This does imply that all frames are automatically subclasses of the frame class, you can make this explicitly so by setting the frame's class to some frame.mytype class if you need it.

This whole class system is used by some operating system functions and can be used by user functions, but it is not used by the language. Think of it as a tag, that is all that is to it.

Much more language-inherent is the frame inheritance scheme that I will discuss next.

3. Inheritance

NewtonScript uses an inheritance scheme which is derived from SELF. SELF's inheritance mechanism is very flexible. For the special purpose of writing GUI application, NewtonScript has a simplified double inheritance scheme. The two ways of inheritance are very much fixed in purpose when implementing windows and dialog controls, but can be used more generally as well.

3.1 Prototype inheritance

First, each frame can have a prototype frame from which it is derived. The mechanism is rather simple, the frame contains a slot called _proto and each time the NewtonScript interpreter does not find a slot variable or function locally it looks into the frame's prototype and then recursively into its prototype until the whole inheritance chain was searched through. When a new slot variable is created that already exists in a prototype a new slot variable is created in the current frame. During lookup this new variable is found first and semantically replaces the prototype variable. From a conventional viewpoint prototypes serve two roles. First, they are the equivalent to user-defined types, to create an instance of the type, you just have to create an object derived from the object that defines the behavior of your type. Second, prototypes provide the class inheritance mechanism of class based languages.

The dialog creation mechanism of NewtonScript uses prototype inheritance extensively to create dialog items. When a new instance of a built-in dialog element is created the new instance has the built-in object as its prototype. This object created by the user is then called a template in NewtonScript terminology. When this object is then actually put onto the screen, the system itself creates another object having the template as prototype, with some redefined slots to designate view boundaries for example. Thus the template can be reused to create more dialog controls with similar properties.

3.2 Parent inheritance

The second way of inheritance is conceptually quite similar to prototype inheritance, besides the _proto slot a slot called _parent points to another inheritance chain similar to the prototype chain. This second inheritance scheme is again made to fit into the GUI design, all child-windows have a child-parent inheritance relationship to their parent windows. An application normally consists of a parent window, which is in turn child of the system's root window. All windows and dialog controls are then hierarchically ordered below this application parent window. Parent inheritance has an effect similar to prototype inheritance, variables not found neither in the frame itself nor in its prototypes are searched for in the parent frames and their prototypes and so forth. Thus slots in the parent window of an application serve as application wide globals. Assignment rules are a little different from the prototype inheritance rules, you can assign values to slots which reside in your chain of parents and grandparents as you can assign values to global variables in other languages without replicating these variables locally in the current frame.

For function lookup, NewtonScript only searches the prototype chain, not the parent chain, although a frame can call a function in one of its parents directly by dereferencing its _parent slot. It does not become entirely clear why this is so, I think it is more because of practicality than principle.

The next picture summarizes the use of parent and prototype inheritance within the Newton GUI system.

Besides their use to implement the GUI architecture parent and prototype inheritance can be used together to simulate classes. The parent frame acts as a class description. A function within this class frame returns a frame that is a new instance of the class, with the _parent of this frame set to the class frame. All class methods are defined in the class frame. Class inheritance can be done by using prototype inheritance in the class description. Note that this class creation scheme does not allow data hiding, instance variables are still accessible from other functions not belonging to the class. It allows factoring out common behaviour of frames and gives some clearly defned interface to a set of data.

4. Functions and function calls

Being the equivalent of class methods functions inside frames have access to all slots of the frame they are defined in. The inheritance mechanisms make function calls, or sending messages to frames in NewtonScript terminology, more complicated than in conventional languages. Functions can be defined somewhere in the inheritance chain of a frame but upon invocation the function must use the current values of slots redefined in the current frame.

Class-oriented languages circumvent this problem because variables used in inherited functions have storage space somewhere in the class they are defined in, even if some descendants of this class assign a different value to the inherited variable. Only calls to redefined functions have to use some kind of indirection (like the VIRTUAL keyword in C++) to determine which definition of the function is the intended implementation. To redefine variables as functions or other variables is not possible. Even Eiffel restricts redefinition to redefining functions as variables, not vice versa.

In NewtonScript redefinition of variables can occur naturally. Each time a value is assigned to a variable which was already defined in a prototype, it is replicated and redefined in the current frame. A function in the prototype using this variable should then be able to use the new value of the variable rather than the one defined in the prototype.

It gets even worse. Functions are objects, and it is valid to assign a function to a variable which separates it from the frame it is defined in. You should still be able to execute this function.

To achieve these requirements function objects are closures, which include the function code as well as an environment. The environment consists of the lexical environment and the message environment. The lexical environment is all local variables of functions the function definition is nested in, all parameters of these functions and the parameters of the defined function itself. The message environment consists of a reference to the implementor, which is the frame the function is defined in, and a reference to the receiver, this is the frame the message that caused the function call was sent to. Each time a function is called inside a frame the receiver reference of the function is set to the receiving frame, regardless of whether the implementation of the function comes from the called frame or from some frame in its inheritance chain.

When inside a function a variable is looked up, the function first searches the lexical environment, that is, local variables and parameters. It might seem strange to look up local variables of the function that once implemented the called function, but this is possible because the garbage collection mechanism does not discard local variables that are still referenced by somebody, even when the function these locals belong to already returned.

If a variable is not found in the syntactical environment the receiver reference is used to search the receiver's slots and slots in the prototype chain of the receiver.

5. Design goals and how they were addressed

One important design goal of NewtonScript was low memory consumption. At the time the Newton was designed RAM was expensive, and to accommodate any magnetic storage would have been too expensive, too heavy, too delicate to handle and too energy-consuming. The prototype-based scheme and prototype inheritance are the two major means to minimize memory consumption.

In class-based languages an instantiation of a class causes memory being allocated for all object attributes, even if they are rarely changed when the object is actually used. Only function code is reused rather than copied for each instance.

In prototype-based languages creating an instance is equivalent to creating a frame that inherits from some prototype frame. Except for some _proto or _parent pointers no memory is allocated. The Newton Operating System allows so called magic pointers that point into ROM. They are set at runtime to their actual values because the addresses of ROM objects are not known to the development environment. Besides resources like sounds or icons, prototypes for all standard dialog controls reside in ROM, RAM is only used for those attributes whose values were changed by the program, like size and position of the control, or user data. This minimizes memory consumption for the normally quite memory-demanding GUI.

The extensive use of reference pointers in NewtonScript in conjunction with a MMU allows another optimization. Objects can be stored on permanent storage like Flash Card or the part of the internal memory of the Newton which is set aside to contain permanent data. When an object stored on disk is accessed, only the top-level object is actually loaded into memory. Pointers in the object are translated to some virtual addresses, and when such a pointer is dereferenced a page fault occurs which causes the data the pointer references to be fetched into memory. The mechanism is similar to virtual memory but more efficient because the granularity of retrieval can be much finer and customized to the object that is retrieved. Implementation of a similar scheme for class-oriented languages is possible but not as useful because all the object data normally comes in one big chunk.

A third contribution to small memory consumption is the fact that NewtonScript is compiled into byte code and then interpreted. Byte code is much more compact than RISC machine instructions.

A second design goal led to the choice of a prototype-based language. Writing interactive applications normally encompasses two tasks, writing the data model and writing the interface. The designer of NewtonScript claims that prototypes are a more natural way to write the interface part which is very important for a device that has not much of input devices on it to compensate for a bad user interface. Often only a single instance of a control is needed, and directly writing an object for some dialog item rather than implementing a class for it which has then to be instantiated to be effective is a much more direct approach to programming a GUI.

Some class mechanism simulation (s. a.) is possible in NewtonScript to provide the necessary support to write the data model.

A third design goal was definitely ease of use and especially good learnability to inspire more programmers to program for the Newton platform. The relatively liberal nature of the language, with well-known Pascal syntax, no variable declarations and dynamic typing reminds me of BASIC which also had as main design goal good learnability. NewtonScript also shares with BASIC that it is capital-insensitive. I think there is some conflict here between learnability and the prototype paradigm. I think the necessity to learn a new language will drive away many potential developers, especially companies with a pool of experienced but older and more conservative programmers. Hobby programmers are more appealed by the casual character of the language, as the big pool of shareware programs for the Newton shows, but they cannot form the backbone that can drive the Newton to commercial success. I do not want to elaborate on this point of critique further because the two other design goals show that the development of a new language or at least the choice of a somewhat unconventional language can be justified.

6. Practical Aspects of NewtonScript and critique of the language

NewtonScript is a special purpose language so far only implemented for the Newton MessagePad. The development environment called Newton Toolkit runs on a Macintosh or Windows computer connected to the Newton via a serial cable. There is some alternative environment called "Newt" available from third party that runs on the Newton itself and uses NewtonScript but it is only intended for small application projects.

I conducted an HCI class project using the Newton as platform and therefore NewtonScript as programming language. The application was a prototype for a communication device used in hospitals. It extensively used the Newton graphics and sound capabilities and had to implement some graphical dialog controls which were quite different from the built-in controls of the Newton GUI. I think we got a quite good overview of the advantages and disadvantages of NewtonScript.

I think it is justifiable to look at NewtonScript in conjunction with the Newton hardware and the Newton Toolkit programming environment because from a practical viewpoint this is the interface a potential NewtonScript programmer is faced with. This also sheds some light on the environment requirements that a particular language requires. In class we mainly looked at principles of language design independent of the environment the programmers works in. I think that the language properties have a big influence on the kind of environment that is required to effectively use the language.

As I already pointed out in the paragraphs before NewtonScript is a very liberal language, with no variable declarations and all structures extensible at run time. For practical purposes two major drawbacks arise. First, NewtonScript is slow. Because all data structures are dynamic variable lookups cannot be done using a simple pointer dereference as in statically typed languages such as Eiffel or C++. Rather all lookups require searching through the local variables first, then the slot variables continuing with the current frame and all inherited frames. The same applies to function lookups. The Newton MessagePad, at least up to the Message Pad 130 with its 20 MHz ARM 610, is not a particularly fast piece of hardware. The NewtonScript programming manual contains a whole section on speed optimizations for NewtonScript.

A straight-forward and quite clean way is to specify a function as native, causing its code to be compiled into machine instructions. Some other optimization techniques include declaring variables as local because this avoids lookup when they are accessed. For the same reason functions that are repeatedly called should be copied into local variables as well.

Using a different syntax for function calls can avoid the traversal of the inheritance chain and the setting of the receiver which occurs when using the message-passing syntax. The whole inheritance mechanism is then put out of effect and semantically wrong results can occur because the receiver is not set to the frame the function is intended to be called in.

I think that these optimizations are not something the programmer should be concerned with. It makes programs harder to read and programming more error-prone. The main reason why the language does not do these optimizations automatically is probably simplicity of the interpreter/compiler. I think that more effort should be put on automatic optimization when there are some language features with inherent performance problems.

The second major drawback comes with debugging and is partly due to the relatively bad run time error messages the Newton Toolkit provides. The liberal form of programming in NewtonScript combined with the limited debugging capabilities of the environment makes programming for the Newton definitely less enjoyable and sometimes even frustrating. Especially with variables, scoping and typing NewtonScript has some features which are inconsistent or simply odd.

Variables which are used and not defined are considered local. You get an error message when you try to read from undefined local variables. This only applies to undefined variables which are written without any qualifier. When you declare a variable x explicitly as local with the statement
local x;

reading from it gives you NIL! The same applies if you access slot variables that are not defined. self denotes the current receiver frame, and self.x denotes the slot variable x in this frame. If you read self.x and it does not exist you get NIL as its value.

This NIL value can now be assigned to some other variable and the error can propagate until somebody checks for non-NIL like an arithmetic operation or a function checking its parameters. Second, NIL is perfectly valid in NewtonScript as a boolean value and means false. I think the missing error message when reading a variable you never used before is a major flaw of the language. I don't see any benefit in being able to read a variable when nothing is assigned to it. NewtonScript even gives you the feature to check if a variable is already defined. You can use this function if you need code that runs in both cases, when the variable is defined and when it is not, so allowing reads from undefined variables is simply not justifiable.

Once you declared a variable it is no more visible if the variable that is accessed is a slot or is local. This, too, can provoke program errors:

func() begin
   if a = 3 then self.x := 3;
   x := 2;
   ...
end;
The second x can mean two different things here, depending on how the first line evaluates. What it comes down to is that you can do conditional variable declarations, imagine in C a variable that is declared as global or local depending on some expression in an if-statement. It is arguable if this is a useful feature, I think it leads to confusion. Some easy way out would be consistency, the language should always require the frame qualifier which is self for the current frame if some slot variable is accessed, or alternatively, require the declaration of all local variables.

It is not clear to me why declaring variables is not required. Some type check could be enforced each time an assignment is made. An argument that could be put forward is that reusing variables for more than one purpose saves space, but this arguments dates back to MS-BASIC days and cannot be taken seriously. Again, especially reading from a variable and getting NIL back without any notification to the programmer is unbearable.

All these liberal language features could be justified if good runtime checking could be invoked that gives really good error information. But unfortunately this definitely is lacking within the Newton Toolkit development environment. Let a slot called ViewSetupFormScript which is part of the window creation mechanism of the Newton GUI contain this function:

func()
begin
   y:=self.x+self.x;
end;
self.x is undefined and implicitly read as NIL here and the arithmetic operation fails at run time with a type error. All you get from the Inspector, the debugging tool built into the Newton Toolkit, is the following:
(#60029C9D).ViewSetupFormScript(), 7: SetFindVar y
Entering break loop: level 1
   evt.ex.fr.type;type.ref.frame
Expected a number, got nil
   Error -48404
Unfortunately the function name is the only hint where to look for the error, there is no line number given, just a "7" which denotes some byte code instruction count which is not very helpful to the programmer. The Newton Toolkit has no real source code level debugging. This makes finding errors in longer procedures difficult, or when the error propagates via function parameters into other functions, virtually impossible.

When we wrote our class project sometimes we had to make a copy of the program and delete parts of it to cut down search space to find a runtime error that occured.

Imagine that you have the bear traps in the language I pointed out above, only syntax errors are checked at compile time and you get bad runtime error messages. This is what the frustration of programming the Newton is all about.

I want to list some other points of critique here although I think that they are not critical in terms of the usefulness of the language. They are given here for completeness, but I did not find them particularly annoying when programming the language. A reason why NewtonScript was designed this way could be again simplicity in implementing the language. For example, all variables are allocated dynamically whenever they are used, but you have to use some built-in function to expand an array:

myarray := [ 1, 2 ];
addArraySlot(myarray,3); /* instead of myarray[2] := 3 */
The behaviour of frames is completely different. You can add slots at arbitrary depth just with an assignment.
myframe := {};
myframe.yourframe.ourframe.value:= 7;
is equivalent to

myframe := { yourframe: { ourframe: {value: 7 } } };

It is remarkable that some kind of declaration is needed here. addArraySlot can only be applied to an array which already exists, and the assignment of slots can only be applied to variables that are already a frame, again not to unknown variables. The last case is especially hard to justify, because the declaration of the slot variable yourframe which is inside myframe is not necessary to add slots to it.

For completeness' sake I want to mention that the uniform access principle is not followed in NewtonScript. Slot variable accesses and slot function calls look different:

a:=myFrame:aFunction();

versus

a:=myFrame.aValue;

7. Conclusion

NewtonScript is an interesting approach to programming for PDAs. It is always delightful to look at a different programming paradigm especially when it is not part of the normal university curriculum. NewtonScript is somewhere in between a full-blown application programming language and a scripting language. NewtonScript inherits the features of a full-blown language from SELF, and was specialized and simplified towards the Newton application development needs, for example by restricting inheritance and replacing the Smalltalk syntax by the more popular Pascal syntax.

Some language features are hard to justify, like the NIL content of unknown variables, or the strange optimization techniques and are probably due to simplicity in implementation. Some more theoretical principles would have done good here.

Otherwise the liberal nature of NewtonScript is by itself not a major flaw. NewtonScript is not indended for programming Ariane rocket control software and a Newton application crash is the worst thing to face in case an error slips through the testing process. Newton applications tend to be rather small, so thorough empirical testing is still possible. NewtonScript certainly allows fast results which are typical for special purpose scripting languages. This is a feature programmers like as the success of PERL shows although hardcore OO-language designers will step back here with disgust. This also implies that I do not recommend NewtonScript as general application development language for large projects. NewtonScript certainly has good structured programming features but it does not enforce them on the programmer. Some discipline is needed at the programmer's side to organize his program. With a hacky programming language, to make visible what is going on is crucial though to enjoy the liberal art of programming. In this domain the Newton Toolkit is simply not powerful enough.

8. Appendix

8.1 References

  1. Newton Toolkit User's Guide For Windows, Apple Computer Inc., Cupertino 1997.
  2. Newton Programmer's Reference For Newton 2.0, Apple Computer Inc., Cupertino 1996.
  3. Newton Programmer's Guide For Newton 2.0, Apple Computer Inc., Cupertino 1996.
  4. The NewtonScript Programming Language, Apple Computer Inc., Cupertino 1996.
  5. Walter R. Smith, SELF and the origins of Newtonscript. In: PIE Developers, July 1994.
  6. Walter R. Smith, Class-based NewtonScript Programming. In: PIE Developers, January 1994
  7. Walter R. Smith, The Newton Application Architecture. In: Proceedings of the 39th IEEE Computer Society International Conference, San Francisco 1994.
  8. Walter R. Smith, The Newton Operating System. In: Proceedings of the 39th IEEE Computer Society International Conference, San Francisco 1994.
Special thanks go to Walter R. Smith for pointing me to his papers.

8.2 A sample NewtonScript program

This is a larger piece of sample code written in NewtonScript. Admittedly algorithm code is not very enlighting to illustrate the NewtonScript principles. The problem is that in fact NewtonScript programs cannot be written just with a text editor, but have to be put together using the Newton Toolkit environment, therefore it is not possible to demonstrate a piece of GUI code because most of it is done graphically. The inheritance mechanisms are automatically invoked by the environment and normally not assigned by the programmer. Anyway, just to get a feeling of the syntax which is close to Pascal and really easy to understand:
func native(int destx, int desty)
/* This procedure finds the shortest way through a grid labyrinth with
   walls along the grid line from the current location to a given
   point. It is taken from the class project I conducted using
   NewtonScript. Is is compiled native for speed. Very much is
   inlined because calls are expensive. Execution time for
   a 20x20 array with some walls going from one end to the other
   is about half a second, so it is still bearable. 
   The whole program including this function is available from
   my homepage http://wwwwbs.cs.tu-berlin.de/~schoedl */

begin
   /* Gets the X dimension of the labyrinth */
   local int xsize:=leftWalls.bounds.right-leftWalls.bounds.left;
      /* and create an array with an entry for each position between the
         grid lines to store the distance to each point in there */
   local array dist:=Array((leftWalls.bounds.bottom
                           -leftWalls.bounds.top)*xsize,nil);

   /* This queue contains the outer limit of our distance knowledge.
      Neighbors of these places need to be set next. */
   local array queue:=[youx,youy];
   local int read:=0;
   /* Pointer, up to which point the queue was already worked on.
      For simplicity storage space in the queue is not freed until
      the end of the procedure */ 

   local int x;
   local int y;
   local int curdist;
   local int store;

   /* the distance to our current position given by youx and youy
      is defined to be 1 and put into the array which is initialised
      to 0 by NewtonScript. Distances to points whose entry in the
      array is 0 were Places are still not determined, so initially
      no distance is known except the one to our current location. */
   dist[youx+xsize*youy]:=1;

   loop begin
      /* This infinite loop takes a pair of coordinates from the queue
         and sets the distance to all the neighbors of this
         place in the grid if it has not been set by someone else
         already. If the distance is set the neighbor is enqueued
         in the queue to let his neighbors processed sometime later.*/
      /* read from queue */
      x:=queue[read];
      y:=queue[read+1];

      /* If we reached our destination break out of loop */
      if x=destx and y=desty then break; 

      /* if we are not at the border of the grid and there is no
         wall between us and the neighbor set the distance and
         add neighbor to queue (which is just an array).
         Pixels in a BMP picture which is set up at compile time to
         contain the wall locations, two picture, one for vertical,
         one for horizontal walls. */
      if x>0 then if dist[x-1+xsize*y]=nil
        and not PtInPicture(x,y,leftWalls) then begin
         dist[x-1+xsize*y]:=dist[x+xsize*y]+1;
         AddArraySlot(queue,x-1);
         AddArraySlot(queue,y);
      end;

      /* And do the same thing for the other three neighbors */
      if dist[x+1+xsize*y]=nil
        and not PtInPicture(x+1,y,leftWalls) then begin
         dist[x+1+xsize*y]:=dist[x+xsize*y]+1;
         AddArraySlot(queue,x+1);
         AddArraySlot(queue,y);
      end;

      if y>0 then if dist[x+xsize*y-xsize]=nil
        and not PtInPicture(x,y,topWalls) then begin
         dist[x+xsize*y-xsize]:=dist[x+xsize*y]+1;
         AddArraySlot(queue,x);
         AddArraySlot(queue,y-1);
      end;
 
      if dist[x+xsize*y+xsize]=nil 
        and not PtInPicture(x,y+1,topWalls) then begin
         dist[x+xsize*y+xsize]:=dist[x+xsize*y]+1;
         AddArraySlot(queue,x);
         AddArraySlot(queue,y+1);
      end;
      /* There are tuples of two coordinates in the array, so advance
         array resp. queue pointer by two. */
      read:=read+2;
   end;

   /* Now the array is walked back from the destination to the origin
      (you can do it either way) to find the right way which is
      stored as a set of lines which are used to paint the shortest
      way into a moving map on the Newton screen. curdist contains
      the current distance to out origin. */

   curdist:=dist[x+xsize*y];

   /* If the destination was not the current position */
   if curdist>1 then begin
      /* the coordinates of the destination which is still
         contained in (x,y) is the first point of our line */
      wayArray:=[x,y];

      loop begin

         /* if we go any distance in one direction we have to store
            the endpoint of our walk, but if one direction does
            not work at all, we do not store the endpoint. We don't
            want one point to be stored more than once, that will
            cost us drawing performance. */
         store:=0;

         /* Again, check for grid boundary (some guard walls would be
            better here, but I did it the hacky way) */
         if x>0 then
            /* Go as far as you can while the distance to our
               is decreasing, if you can go at all, store the
               endpoint */
            while dist[x-1+xsize*y]=curdist-1
              and not PtInPicture(x,y,leftWalls) do begin
               store:=1;
               x:=x-1;
               curdist:=curdist-1;
               if x=0 then break;
            end;
         /* Here the endpoint is stored into an array. When the
            current distance went down to 1 we reached our
            origin and can quit. wayArray contains pairs
            of coordinates then describing the way through the
            labyrinth around the walls */
         if store=1 then begin
            AddArraySlot(wayArray,x);
            AddArraySlot(wayArray,y);
            if curdist=1 then break;
         end;

         /* Do the same thing for the other three neighbors */
         store:=0;
         while dist[x+1+xsize*y]=curdist-1
           and not PtInPicture(x+1,y,leftWalls) do begin
            store:=1;
            x:=x+1;
            curdist:=curdist-1;
         end;
         if store=1 then begin
            AddArraySlot(wayArray,x);
            AddArraySlot(wayArray,y);
            if curdist=1 then break;
         end;

         store:=0;
         if y>0 then
            while dist[x-xsize+xsize*y]=curdist-1
              and not PtInPicture(x,y,topWalls) do begin
               store:=1;
               y:=y-1;
               curdist:=curdist-1;
               if y=0 then break; 
            end;
         if store=1 then begin
            AddArraySlot(wayArray,x);
            AddArraySlot(wayArray,y);
            if curdist=1 then break;
         end;

         store:=0;
         while dist[x+xsize+xsize*y]=curdist-1
           and not PtInPicture(x,y+1,topWalls) do begin
            store:=1;
            y:=y+1;
            curdist:=curdist-1;
         end;
         if store=1 then begin
            AddArraySlot(wayArray,x);
            AddArraySlot(wayArray,y);
            if curdist=1 then break;
         end;
      end;
      /* This sets up a timer that causes a repaint of the map 
         somewhere else */
      :SetupIdle(200);
   end;
end