Diary of an implementer

VECTOR Vol.3 No.4

Diary of an implementer

by Paul Chapman

(Editor’s note: This article comprises various thoughts recorded during the initial stages of the development of the I-APL interpreter. They have deliberately been left un-edited, in order to give readers some insight into the issues that become uppermost in the mind at various stages of such a project. I hope that Paul can into producing a more leisurely retrospective overview of the project when it has been completed.)

Monday 10th November 1986 00:10

I’ve spent a week getting started on the development language and environment for implementing I-APL. I wish I had six months instead of three weeks to finish this part of the project alone  it’s proving possibly more interesting than the APL itself. Romilly Cocking told me that at the moment the fight is on for the world’s sixth most popular language (how do they judge these things?) between FORTH, LISP and APL. Perhaps DE (for that is what this new language is called at the moment - I started by calling it DEL, but typing DEL toa DOS prompt causes other things to happen. Not too expensive, . .), perhaps DE might be up there somewhere in a couple of years.

Some compromises forced, however, because of lack of space on the target machines for the APL itself. For example, it is important to know exactly how much stack space is going to be used by I-APL (porters shouldn’t have the responsibility of having to put in stack overflow checks and handlers), so it must be possible to analyse completely (by machine, of course) the full calling structure of the interpreter. This means no recursion, and that is a decision I may live to regret.

Recursion is easy in a language like APL, since the workspace has a fully flexible heap manager, but I such luxuries (I must take pity on the poor porter and not give him too much original code to write). Languages like C are recursive, but then the system goes BANG when the stack overflows, and anyway, starting with 20K too much on the stack is not much of a penalty in a 512K machine.

analysability also means function pointer variables are out, since the structure: you may know when they’re stored, but how do you know how full the stack is when the function being pointed to is actually executed? After six months of the freedom of C, these jackets will be severely straight.

Still, it means that the structure of the language, which is sort of FORTH-like but with local variables (which, as I’ve rediscovered from my FORTRAN days, don’t have to be on the stack) and nicer looking blocks (surrounded by of braces, with the occasional semicolon) and some powerful self checking abilities (to reduce programmer-error  yes, it does exist, but don’t tell the guys who are paying me. . .), anyway, the structure a lot simpler.

129

VECTOR Vol.3 No.4

I’ve actually got the compiler working. A week ago I was phoning up Geoffrey Roughton (the sugar daddy of VIZ::APL) asking if he had any compiler-compilers for the PC, and generally panicking as I tried to remember about LR@) and recursive descent, which only analyse the syntax anyway and are a far cry from actual code generation. But everything came out OK in the end (thanks to recursion  oh dear, what shall I do without it?), but now the symbol-table structure is groaning under the pressure of putting local variables in (into DE, not APL - 1

haven’t started the APL yet, but don’t tell the guys who are paying me. . .), and now I wonder if a general namespace approach is possible (which makes DE itself much more saleable in the end), and how many pointers and two-way linked lists are needed and whether there is an elegant solution.

Elegant solutions are satisfying, of course, but they are also maintainable. Note well.

About four o’clock yesterday morning I discovered that my rationalised algorithms for compiling the likes of IF, FOR and WHILE structures were the same as those implemented in MVP FORTH. I know I’m on the right track.

Only three more weeks to finish DE. Yet to go in are: the DE interpreter, the DE assembler (which produces the final target code from the source), the DE debug/trace facilities (all full screen and interactive), the virtual memory manager (if I need it  I hope not. Maybe Pll buy another 128K for this machine). And ] move house next weekend. I’ll have to work 12 or 16 hours a day to get it done. Please tell the guys who are paying me. . .

Monday 17th November 1986 16:44

I had thought of putting the development environment up under Microsoft Windows. But then I saw the size of Windows. There simply wasn’t going to be enough room, and learning the Windows system calls and so on would have taken far too long. And my budget doesn’t stretch to a mouse at the moment. Anyway,

why use a pre-existing package when you can re-invent the wheel yourself? Most consultants would tell you that there is every reason, and despise the not invented here” attitude. But when you invent something yourself, you don’t have to learn how to use it. And it doesn’t come overloaded with features you’ll never use, which just use up space in memory and in the manuals, And if you don’t like the system limitations, you can modify them. And if, after a while, it turns out that your system doesn’t quite do what you had hoped, why, you can start again from scratch.

And when you’ve finished it, you can cobble together some obscure documentation, think up a thousand and one new uses, and then sell it at a premium to all those people who took their consultants’ advice.

So I wrote a windows system. It runs on a text screen, has exactly six windows (always open), has a user editor for changing the relative size of the windows on the screen, and is small and fast.

130

VECTOR Vol.3 No.4

Now [ have a prototype front end, which allows me to define tables (ROM resident fixed lists of addresses and/or constants), strings (zero terminated sequences of characters), data areas (uninitialised RAM vectors), constants (numbers or characters), and functions. Functions and tables can have tables, strings, data areas, constants and functions included explicitly in-line, or, in the case of functions, in the header by name.

After I wrote the last entry, J spent some more time rationalising the workings of block structures. Here is an extract from the C source of the definitions which govern their behaviour: {"case", 'b', (int) CocPombpjs sxfgUpxsjflomDpjs }xfgUpxsjflock"}, {"do", tbh’, Cint) Cock "3, {"for", 'b', (int) "ocPombpjsxfmUpxsjflpjs djfvgd"}, Cf", bt, Cnt) "Lockpjs sjfqxfgupxsjflojs }jfl"}, {"repeat", 'b’, (int) "{achpjs }jfvgu"), until", tb', Cint) "{ocNpjs }jfvgF"}, C'whi Cint) "CocNpjs }ifvgT"}, (Editor: I hope that little lot has not been mysteriously translated in the many electronic transfers between Paul’s diskette and the typesetting equipment!)

A little bit of code in the compiler just interprets the one letter instructions. The capitals are codes for actual intermediate code instructions to be compiled into the object. The { s, } s and : s just label the pieces to be interpreted when those characters are encountered in the source. You can see I’ve been having fun.

Now the operation of the user interface is in the process of being designed. Golly, how I hate designing things ~ APL programmers will know what I mean: with APL you just keep playing around until you like it, at no extra cost. (However, I would not recommend this approach for designing files and file based systems.)

At the moment, I’m using a word processor and program editor called WordVision, in which the function keys in the first column have global meanings (extracts, search/replace, format, files and print), and the second column have meanings depending on which of these five modes, plus one more (text entry), the operator is in. This is simple. I will try to do the same. The trouble is finding five (or six) functional headings which are logical, consistent and cover all options which are needed now or might be developed in the future.

And I still can’t actually execute any of the code I type in, though I can save it on disk. By next week, however. Tuesday 25th November 1986 04:05

By next week, I still can’t execute the code. But all the C to execute code is written now, and all [ need is a front end to get at it.

Talking of front ends, it is mostly finished now. It uses nearly every finite combination of function keys to provide facilities to edit source, examine source by token, examine object by word, list names of al! objects of type ~ constants, arrays (which used to be called data areas), functions and lists (which used to be called tables)  and so on. I caneven find out how much space I've got left. Needless to say, the structure is logical, consistent and covers all the options I’ve thought of so far.

131

VECTOR Vol.3 No.4

Dave Ziemann and Anthony and Sylvia Camacho were here on Sunday to talk about the schedule. Naively, 1 gave them an idea of what I thought mine might be. It is rather daunting to look at the amount of work to be done. In the end, it all comes back to design. It seems to me that the best thing to do when you’re tight for time is leave the design until as late as possible. Again, this sounds like rather the wrong advice for consultants to give, butit is possible to work this way, You just make sure that every element of the system is as general and as self-contained as possible.

Dave Ziemann lent me a book called Reliable Software through Composite Design by an TBMer called Glenford J} Myers (would IBM ever take me on with a dull name like Paul Chapman?). He’s got some crazy ideas about Module Strength and Module Coupling which are wonderful in an ideal world filled with ideal programming languages, and aren’t too bad in the real world. He stresses these ideas with a view to making systems more maintainable, and they do indeed work, so I hear. So we have the traditional development strategy: firstly, specify the problem; then design the solution, then implement it using Myers ideas, then maintain and extend it as necessary.

My approach is to regard the implementation phase as just another maintenance exercise, which means the design of the solution can be skimped a bit. To me, the absolute top-level design (what it does) is fairly obvious, and the absolute bottom-level functionality (how all the bits work) should be made up of units which are as general as possible, Then the middle level (how it does it) is just (inevitably, in my experience) the rules which best suit the requirements today, which everyone knows are different from the requirements tomorrow (or usually yesterday, because nobody’s bothered to tell you yet).

Enough of these ramblings. Goodnight.

Wednesday 27th November 1986 05:00

Just a quick note to say WOW! not only is 1 plus 1 equal to 2, but 2 the sixth power is 64. J can execute things. Now all I’ve got left is local variables and a few more primitives and user I/O and breakpoints and source level trace and object level trace and... Monday Ist December 1986 07:15

In principle, at least, the deadline for completing the first phase of the implementation of: the APL interpreter passed a little over seven hours ago. However, I measure the passing of days by going to bed, and I haven’t done that yet.

It is finished. In this last session, breakpoints finally went in, as did checkpoints (show current state without stopping), and the facility to record on file all changes to any source code throughout an entire session. One important aspect of the system is that source code is stored in a straightforward text file, so that it can be examined and edited off line, i.e. outside DE itself.

132

VECTOR Vol.3 No.4

It was only in the last day that I actually checked that garbage collection worked, which it did without trouble. There are still one or two features that I would like to have, but I shall strictly limit any further enhancements to DE to one hour a day. I would like to be able to change the contents of arrays without having to write a one-off function to do it, and for that matter I have to write a function every time I want to execute anything ~ at the moment there is no equivalent of immediate execution mode in DE. T have started looking at the APL standard. What a nightmare. It looks like it might be possible to implement each definition and evaluation sequence as a subroutine, and then it would all work by the end. What’s wrong with this approach, then? Well, you don’t know whether it works until it’s finished, and even if I correctly interpreted and implemented each aspect of the standard definition, which is in the form of a formal model of a particular implementation of Standard APL”, I doubt that the standard itself is without error, Perhaps a good control for the standards committee would be to employ a team of Programmers who knew nothing about APL to imptement the language using just the standard and without reference to any existing APL system or document. It couldn’t be done, of course. One sad fact about the standard is that it abandons the beauty and simplicity of APL constructs and algebra in favour of straight mathematical concepts such as sets, counting numbers, dense sets, open and closed intervals, and so on. I am lucky enough to have received a formal education which covered these ideas, although I find them difficult now. I sympathise with the committee’s desire to avoid having to refer to any existing APL, or to have to use a lot of circular definitions. However, it seems absurd that APL itself, which was originally developed both to express mathematical ideas in a more accessible way than that available with traditional notation, and to describe the behaviour of computers (particularly the IBM System/360), cannot be used to express the concepts and algorithms which underlie the language. Ah, well. At least once the APL standard is published, all future standards in other fields will be able to use the APL notation to clarify and simplify. So now my first task is to get the free storage (heap) management subsystem working, and then to concentrate on the design of fundamental things like the symbol table, internal storage of arrays, the state indicator, and the APL tokeniser. Maybe by next week I will have found that DE is totally unusable. I hope not. Tuesday 9th December 1986 04:40 Well, not bad. I have the free storage manager running, and the symbol table, and two different versions of the lexical analyser  one based on a code-driven version of the actual ISO standard diagrams, and one based on a finite state machine (FSM). The first works fine, but is a little slow, since it has to try to fit the arriving characters to various patterns, which means the character +  would be attacked as if it were the first character of a numeric vector, a name, or a character constant before the software realises that it must be a primitive.

133

VECTOR Vol.3 No.4

So I tried the FSM approach. Backtracking is more difficult here, and must be sidestepped by using more states. I have 15 at the moment, and it looks as though I might end up with many more if I’m not careful.

The problem lies in the fact that the characters ? and overbar (high minus), as well as having meaning in numeric constants, are also designated as primitives for some bizarre reason. So have a look at this:

11.1E1 parses as you would expect as a two element vectors 11.El too; and then not surprisingly LIE parses as a syntax error; but, hold on 1LE as the vector 1 1, the inner product operator . , and the identifier E.

Now, as far as it goes, this doesn’t matter too much, because inner product isn’t defined in the standard for array or user defined arguments. But from the treatment of characters like «?, overbar and underbar as having at least lexical meaning in this version of the standard, one can deduce with reasonable confidence that extensions are envisaged that would also give meaning to these characters when they stand alone. In some visions of APL, they already have meaning (‘.’ for the generalised inner product, where | 1. E is defined semantically at least, and overbar and underbar have been used for plus/minus infinity).

Now, the standard insists that a conforming APL system must behave in a consistent manner ona conforming program. Consider this: 11,EFOO2 According to the standard, this statement will be successfully decomposed into lexical units” (as explained above), and the part-expression E FOO 2” must be executed before the erroneous , is found. Nowhere in the standard does it specify that a conforming program must run without error, although one part of the definition of a conforming program does relate to the signalling of errors. J shall come back to this in a moment.

So, FOO itself is called and executed before the inner product operator is parsed and the error is detected. I think I would prefer to be told that 1.E is a badly-formed number before FOO destroys my data base (E contains 2 0, and of course you realise that FOO makes the tea if the first element of the left argument isa 1 (as intended), and deletes the data base if it is a 2 (as it turned out)).

So now here are the problems. There are two, one for me (the implementor striving to produce a standard conforming APL), and one for ISO (the international organisation attempting to standardise the implementation and use of APL).

Mine is that J can’t figure out if I am allowed to decide that 1.E is a syntax error before I execute FOO. On the one hand, this is specifying behaviour different from that required by a literal interpretation of the standard, and is certainly not a consistent extension, which may only be made by removing an error signal, not by inserting one. On the other hand, to quote the standard: A conforming-program shall not depend on the signalling of any error

134

VECTOR Vol.3 No.4

by a conforming-implementation.” The question arises, is my program conforming? Does it rely on the signalling of an error by a conforming implementation?

Well, that depends on whether it is possible to build a conforming implementation which produces a different left argument for FOO. Suppose we have an implementation which interprets I.E as 1.E0 . This would certainly change the behaviour of the program, but conforming? It removes the syntax error which would have been reported after FOO was executed, so in that sense it is a consistent extension. But it changes the way the lexical analyser works, although no error is reported by either version at the lexical analysis stage.

Finally, if this new interpreter is standard conforming, then my program is not. If the program is conforming, then the interpreter is not. But who is to say which way round? Now, if you’re still with me, what about this?

1.J2.

Again, according to the standard, the lexical analyser has no problem with this. It is the number 1 , the inner product operator . , the identifier J2 , and the inner product operator again. Of course, there is no semantic analysis possible within the standard. So

what if I want to build an APL interpreter which uses this well-known syntax for complex numbers? Can I write a standard conforming interpreter? It definitely removes an error, at the semantic analysis stage. But it alters the behaviour of the lexical analyser significantly.

So now you are as confused as I am.

Now for the ISO. The first their problem is the very specific interpretation of the behaviour of the lexical analyser. This could be easily fixed (except that it is too late for that. . .), either by insisting on one or more decimal digits after a decimal point in a number (1.1J2.2 produces a syntax error during lexical analysis according to the standard, consistent extension is obviously possible), or insisting that the .  (and preferably also the overbar and underbar), when not used in a numeric constant, be separated from any letter, digit, . , overbar or underbar by at space (as, for example, be separated from letters: 123ABC is a syntax error according to the standard). The second part of their problem is catastrophic. The standard goes to great lengths to terms it uses precisely, and prints such defined terms in bold letters. Forward references are avoided where possible, and are usually pointed out where they do occur. It seems that the definitions of conforming-implementation and conforming-program are central if the purpose of the standard is to assist interpreter writers and APL programmers to produce conforming implementations and programs, and to assist the ISO in determining whether implementations and programs submitted for approval are in fact standard conforming.

So here are some extracts. Part of the definition of conforming-implementation is this:

135

VECTOR Vol.3 No.4

A conforming-implementation shall provide all defined-facilities and implementation-defined-facilities. Each such facility shall behave as specified by this standard.” The words defined-facility , implementation-defined-facility and facility are defined terms. Here is part of their definition: Facility (of an implementation): A unit of behaviour. Every facility is one of:

Defined-Facility: A facility fully specified in this standard and not designated optional or implementation-defined.

Optional-Facility: A facility fully specified in this standard and designated optional.

Implementation-Defined-Facility: A facility not fully specified by this standard that is designated implementation-defined.” Now there are specific places in the standard which refer to the terms optional facility and implementation-defined-facility (eg the shared-variable-protocol is defined as an optional- facility). But nowhere is any algorithm defined defined-facility (at least, the term has only three references in the index: its definition, its use in the definition of conforming- implementation, and its appearance in the notes accompanying the definition of the shared- variable protocol, pointing out, tautologically, that this optional-facility is not a defined- facility). In this sense, the terms facility and defined-facility are defined in terms of each other (hee hee !). To make matters worse, section 16.2.1 is called User Facilities” and the word facility is used freely throughout the section, presumably standing in this instance for itself since it does not appear in bold type. So what is a defined-facility? If everything is, then everything has to be implemented literally, But the symbol-table is defined as A list of all symbols whose names are unique”, which, if interpreted literally, would require, for a maximum symbol length of 6, in excess of 27 gigabytes to store! So they can’t mean that. Which calls into question the specific behaviour of the lexical analyser. If it is a defined-facility , must it be implemented literally? Can the lexical analyser and syntactic analyser and semantic analyser be taken together as a single defined-facility, in which case, as long as an error is eventually produced for 1.E , does the error have to be signalled in the lexical analyser?

The standard doesn’t say, and I have tried to demonstrate that there is no common-sense solution to these difficulties of interpretation.

Well, there is one. Ignore the standard, and do the sensible thing. But what will the ISO do then? Of course, if everybody’s idea of the sensible thing is the same, there is no problem. The ISO can adopt this sensible interpretation of the standard, and verify implementations on that basis. But IBM, IPSA, STSC etal all believe that they are each pretty sensible, and look where they're leading us... Wednesday 17th December 1986 01:56

The floating point representation has been decided and implemented. It is 8-digit BCD with a 7-bit binary biased exponent. This means that all arithmetic is performed internally

136

VECTOR Vol.3 No.4

in decimal rather than binary. This proves to take rather a long time  division in particular must be implemented as long division, which is almost as hard for computers as it is for people.

There are a few reasons why I decided to do it this way. Firstly, [ had a lot of trouble when writing VIZ::APL with converting between ASCII representations of numbers and internal binary (or, in fact, hexadecimal) floating point. The only way of working out the internal format for 1E70 is to raise 10 to the 70th power (effectively  in fact, had power of two powers of ten stored ready, so that 1E70 was calculated as 1E64 x 1E4 x 1E2). This could lead to loss of precision in the floating point routines even before the user started his calculations. Using BCD this problem is overcome. Another reason is to be sure that | divided by 5 really is .2  children expect this, and with binary representation, the calculation produces a recurring binary (like 1/3 is a recurring decimal, .3333. . .), which may not come out quite as intended. Now, I know

a lot of work has been done on this sort of thing, and itis possible to get binary floating point representations to behave in a sensible and predictable way, most of these sorts of problems are removed. Unfortunately, I skipped numerical analysis (for that is how the subject is known academically) during my degree, so I am still in ignorance of the techniques involved. In fact, I have a strange superstition regarding floating point numbers  I do not quite believe that they’re real (get the pun?). I very rarely program in floating point, and when faced with the inevitable (like graphics for example) I try to avoid floating point until the last minute, and even then will prefer to write my own graphics interface to address the pixels directly, rather than having to try to figure out how to scale my numbers to fit the 1024 by 1024 (or whatever) co-ordinate system used.

Also on this point, [ would like to say that there seems to be a confusion in graphics between points and cells  in other words, is a pixel a point with floating point co-ordinates, or is it a finite cell which is addressed by its centre? The problem becomes important when trying to find the distance between pixels in the internal scale of the package (eg STSC APL) when you know the number of pixels, On the Hercules card there are 720 physical pixels horizontally, and this is mapped to the range 0 to 1024 in APL. If the pixels are cells, each is 1024/720 units wide. But if they are points, each is 1024/719 units wide.

In fact, both of these are wrong. The answer is 1023/719! Figure that one out. This is why I don’t like floating point.

The last reason for choosing BCD is that I haven’t done it before ~ it was different, and why shouldn’t I have a lite fun?

Anyway, it all works. I’m little worried about speed  worse case division (99999998 / 33333333) takes 40 seconds on the development system. I anticipate about a one- hundredfold speed-up for the live version, but still .4s seems a little long. I will have to think on this further.

137

APL + PC’s

Whatever your area of interest, if it includes APL ona PC, Mercia will have something to offer. Hardware, Software, Liveware - we're sure you could use some of our products or services to make your APL work even more productive. Take a look through this summary  then give us a ring for more details.

APL SYSTEMS SOFTWARE/HARDWARE AlLcard - AREAL benefit to APL* PLUS/PC users with workspace size problems. Up to 750,000K REAL workspace, Check your OWSSIZE in a CLEAR WS, and think how you could use those extra bytes. If that’s not enough, it does up to 10Meg battery backed RAM disks, and ail the standard expanded memory specs. Multi-APL  Multi-user/Multi-tasking/LAN for APL* PLUS, includes APL file component locking etc. APL*PLUS/PC- The old favourite  Lower price, full support, plus all the add-ons.

APPLICATIONS SOFTWARE IN APL STATGRAPHICS  Comprehensive statistical Graphics System  PLUS our unique customisation service for users who don't think it's comprehensive enough. Exec-U-Stat  Stats and graphics for the business user. LOGOL - R G Brown's latest logistics decision support system for the PC. Forecasting, Inventory Control, Distribution, Master Scheduling.

CONSULTANCY Could you use some extra Liveware? Mercia's consultants are experienced APLers, specialising in OR, stats and math's applications  both Birmingham based.

TRAINING See our course listing elsewhere in Vector, if none suits please contact us regarding In-house and specialised courses.

MERCIA SOFTWARE LIMITED Aston Science Park, Love Lane, Birmingham B7 4Bj. Telephone: 021-359 8096