XPL – an Expert Systems Framework

Vector Vol. 1 No. 2

XPL: AN EXPERT SYSTEMS FRAMEWORK IN APL

by Robert Bittlestone

It is hardly possible to pick up a computerjournal today withoutseeing referencesto the Alvey projectin the UK,the Esprit projectrun by the EEC, the Japanese Fifth generation initiative, the proliferation of knowledge-based computer companies around Stanford in California and MIT in Massachusetts, and the large amounts of moneythat are being poured into the development of expert systems. The references abound: as writethis article the September 1984 issue of International Management (1) arrives on my deskwith a cover depicting a digitised human brain image ona computerscreen and a caption saying Artificialintelligence: the race to make it work for managers , | like the use of the word race here; it seemsto imply thatthis is our last chance nowthatthe prospect of humanintelligence in managers has declined asymptotically to zero.

Among the savantscited in the International Management article is Sir Clive Sinclair, no less, whohas becomenotoriouswith the British Computer Society's Expert Systems Specialist Group: notoriousforarriving unexpectedly at meetings and giving the rest of the audience something to think about. Sir Clive apparently said in the interview: Once machinesofsilicon surpassus, they will be capable of their own design. In a real sense, theywill be reproductive,andsiliconwill have ended carbon's long monopoly. And ourstoo, ! suppose, for we will no longer be able to deem ourselvesthe finest intelligence in the known universe. Maybe expert systemswill dominate usafterall it's just that there ll be a ten-month delay between quoting your Visa number and becoming aninferior intelligence.

Allthis is quite fascinating since the phenomenonis very recent: before 1983 the phrase expert systems waslargely unheard of and certainly notinitself viewed as the potential salvation of the Western world (there are asyetfew hints of Eastern bloc developmentapart from in Hungary, wherethe University of Budapest, along with thoseof Marseilles, Edinburgh and London's Imperial College, claims to have invented PROLOG). However, by now there has been Horizon television coverage of the genre and there seems little doubt that expert systems are here to stay. But before | take up the themeofmytitle, perhaps | might be allowedto state my position on one or two related matters. First ofall: Expert systems are not the samething asartificial intelligence Wecanseethe beginningsof a bandwagoneffect herein which technical namedroppers, bored ofstating that UNIX is the coming thing or The future of computing lies in networking are catching up withthislatest trend: Life is just anotherform of domain specialism . Expert systems are in fact a very narrowly defined class of computer program with certain in-built inference- drawing capabilities. Artificial intelligence, on the other hand, is a much wider field involving the generic search for synthetic rationallife. Much of the mostinteresting work in artificial intelligence does notinvolve digital computersat all but concerns the possibility of producing artificial modelsofbrain process,using special fabrication techniques to emulate neurons, axons and synapses. Which brings me to my second definition: Artificial intelligence will not be implemented on digital computers Itturns out that the useof a digital clocked device,irrespective of speed, imposesa fatallimitation onthe sophistication of a genuine searchforartificial intelligence, and parallel processing makes no difference. The reason is thatin the brain it is the dynamic connections between atleast 10 to the power 10 asynchronous independent processing elements that provide the kind of complexity that is required. The processors in the brain are called neurons and the interconnections are called axons, and there is substantial evidence to indicate thatto a first approximation, almost any neuron can grow an axon to connect to almost any other neuron.

65

Vector Vol. 1 No. 2

Nowthe numberof connections between N elements increases in proportion to the square of N . if you have three neurons you can connect A to B, Ato C, B to C, and the same in the otherdirection, whichis valid sinceit correspondsto a negative signal(inhibition vs. excitation). Consequently we have 6 possibilities for the network topology: ie 3x2. For 4 elements we have 12 options: 4x3. If we had a mere 100 neuronstheresult of 100x99is still only about 10,000. However, in the brain we are considering about 10,000,000,000 neurons. So the number of possible connections is 100,000,000,000,000,000,000 a number ofliterally astronomic proportions. We haven't yet introduced the complexity of neurons which connect to more than one other neuron (the majority do), nor signal processing within the neurons themselves(estimated as a seventh orderdifferential equation), nor chemical effects at the synapses, which are retransmissionpoints along the axons. When you drink too muchalcohol, itis primarily the synaptic effects whichalter your responses.| am unconvinced thatthere yetexists anartificially intelligent program capable of intoxication.

If you now consider the implications of asynchronous(butnotparallel) operations taking place between arbitrarily connectable elementsonthis scale, you begin to see that evena billion 64-bit microprocessors would makenodifferenceatall. The emphasisin the brain is on analoguecircuits in which feedbackand frequencyof signal are the determining factor and wherethereis no single location at which processingcanbesaid to be taking place; the wholeofthe brainis in this sense intelligent.

When| asked the Alvey representative at a recent meeting of the Expert Systems Specialist Group (yes, Sir Clive was there too) why there wassolittle emphasis on neurophysiologyin the Alvey programme(I was uncharacteristically diplomatic asin factthere is noneatall) his response wasthat the programmeconcerned the hard sciences and engineering:the bridge to biology was too narrow for engineersto cross, | believe he was genuinely rueful. However,if your appetite is in any way whettedfor real artificial intelligence, you had better go out and buy two rather extraordinary books. One of them is, of course, Hofstadter s Godel Escher Bach: An Eternal Golden Braid (2). The otheris less well-known: William T. Powers s Behaviour: The Control of Perception (3).

In Hofstadter s bookthe notion of recursion is explored in manydelightful ways. For those who have missedit, here is a sampler. Our heroes, Achilles and the Tortoise, have found a lamp. Theyrub it and a Genie appears, The Genie will grant three wishes. This prospectis greeted with glee by Achilles, who has read the Arabian Night and knowsthe form. He makeshisfirst wish:

Achilles: | wish that | had 100 wishesinstead ofjust three. Genie: lam sorry, Achilles, but | don t grant meta-wishes. Achiltes: I wish you'd tell me what a meta-wish is. Genie: But that is a meta-meta-wish, Achilles, and | don t grant them either.

But after somepleading, the Genie agreesto try (meta-wishesare his favourite wishes too) and from inside his cloak he praduces a lamp. He rubsit and out pops a MetaGenie:

Genie: I wish for permission for temporary suspensionofall type-restrictions on wishes, for the duration of one typeless wish. MetaGenie: Half a momentplease (produces a lamp,rubsit, etc.).

This continues for a short infinite period until we get to the top-level MetaGenie, also known as GOD,who grants permission for the typeless wish:

Achilles: I wish my wish would not be granted!

(There follows a SYSTEM CRASH: oras Hofstadterputsit, the land of dead hiccoughs and extinguishedlightbulbs ).

66

Vector Vol. 1 No. 2

Earlier, when quizzed on what the word GOD means, the Genie explainsthatit's an acronym G.O.D. standing for GOD OVER DJINN (Djinn being a generic typeof intermediate Eastern Deity). Does this help? Ah yes, because we can expandit: GOD = GOD OVER DJINN = (GOD OVER DJINN) OVER DJINN = (GOD OVER DJINN) OVER DJINN) OVER DJINN

If this is starting to look familiar,it's becauseit is. A deep knowledgeoftherelation of a system to its metasystem and of the closely connected notiomof recursion is an essential pre-requisite for serious workin artificial intelligence. tn fact | suspect that: Artificial intelligence = recursion + superficial incompetence

What about the other book| referred to: Behaviour: The Contro! of Perception (or as they write it in the USA, Behavior: The Control of Preeption ')? In my estimation this book ranks with Norbert Wiener s Cybernetics (4) and Stafford Beer's Brain of the Firm (5): together they form the twentieth century triumviratein this fiald. Powersstartsoff with some deceptively simple experiments and ends up with a necessary butnotsufficient model of human intelligence based onfirst principles and an appeal to reason. The argumentis convincing andis closer than anyother| have read to the true core of artificial intelligence. Significantly, | don t recall in the booka single serious mention of digital computer programming.

Powersexplainsthat the basic circuit elements in organic brains are notdigital atall. They are analogue,but they use frequencynot voltage asthe yardstick. If 10 neural impulses per second flow in an axon, that may cause(atthe lowestlevel) a certain amountof contraction to be applied to a single musclefibre. 20 impulses per second might double the contraction force. However, the key pointis the perceptionofall this. Feedback from local sensors is compared against a reference level for the desired state, and the output signal is adjusted accordingly. This compensatesfor unexpectedresistanceto the muscle s work andif you think aboutit, you've neverlifted a weight by applyinglinear pressurein your life.Literally millions of low-level frequency sensitive feedbackcircuits create what Powerscalls Level 1 theinterface to the outside world at the sensory/motorlevel.

Thenwestart to encounterhierarchy. Where dothe reference levels for the desired states come from? Well, these are the outputs from Level 2, but this time they correspondto a higher-level notion: like thatof vertical vs. horizontal movernent. By positing a hierarchyof feedbackcircuits whose outputs becomethe referencelevels (le. contro! signals) for lower levelcircuits, Powers willlead you to agree that when youare walking at 2 miles per hour,there isan identifiable, traceable neural frequencyin your brain which doubles in frequency when you walk at 4 mph. Andif you find that hard to swallow,by the time you reach higherlevels of hierarchy we are talking about frequencies which correspond to degrees of emotion. Of hate. Of love. To sleep, perchance to dream... Do Androids Dream of Electric Sheep? (6).

| suspect| have strayed somewhatfrom thetitle ofthis article. But I do think it's important to set the context. !f you want somefun with computers,start playing with expert systems. If you wantto learn something useful aboutartificialintelligence, start reading some books. The two are not the same and I personally doubtthat insights from one muchhelp in the assimilation of the other.

Perhaps we should focus on the main theme. This gives me a small problem since the arbitrary readerofthis article exists in four configurations: you know about APL (or you don t) and you know about expert systems(or you don t). Here | am going to pitch the discussion slightly in favour of someone who knowsa bit about APL but nothing about expert systems,although | hopethere will be some comfort for the others here and there.

67

Vector Val. 1 No. 2

Let s recap on APL s strengthsin this area. We have a language which supports recursion with no limits apart from workspacesize. Localvariables and argumentsto recursive functions are properly masked and pushedto a stack on each recursiveinvocation, Logical operations in APL are generally implemented at data word bit level and are very comprehensive and very fast. Arrays of arbitary dimension are supported and most primitive operations apply element-wise without looping. APLis a threaded interpretive languagein whichindividualbuilding blocks are defined and can beinvokedin free-standing manner(like LISP). If LISP suffers from parentheses, APLsuffers fromsilly specialist symbols, but fortunately this last aspectis starting to disappear in the more enlightened implementations. APL is very good indeed at numeric computation of high complexity in both the scientific and the commercial domains, and in additionit is fast and elegantat string handling.

Standard APL disallows non-orthogonalarrays andthoseof mixed character and numeric type. This is undoubtedly a disadvantage for expert systems workbutis overcome in APL2. However, I haven't used APL2 seriously yet, like most other APLers | suspect, and shall confine my remarks totraditional (or as my American friends wouldputit, vanilla } APL. So the question becomes: What has PROLOGgot that APL hasn t? The answer, surprisingly to APL aficionados, is: quite a lot. However, perhaps surprisingly to PROLOG programmers,it turns out that one can codeall the standard PROLOGbacktracking and similar logic capability into APL user-defined functions(ie. into a subroutinelibrary). You then end up with an APL workspace oriented towards the developmentof expert systems, but with the great advantageofcarrying withit all the hooks and existing facilities which have been developed in APL overthe last 20 years.

Evidently PROLOGusersdon t mind that they have no properfiling, no error control, no serious peripheral control, no multi-process synchronisation, no inter-user communication, no user or file security, no computationalintrinsics beyond add, subtract, divide and multiply, no interpreter available on IBM mainframes, nolinks te COBOL and other languages, no screen control, no graphics capability, no links to deviceslike mice ... It makesit fun to develop expert systems in PROLOG, but awfully hard to sell them. So far | keep seeing demonstrations of PROLOG expert systemstelling me how to water my houseplants,butthe florist down the road isn t selling the packageyet.

Let s look at the frameworkof an expert system in APL terms. This path has beentrodden before (7) butI'd like to look at the problem in a slightly different way. To makeit morepractical, let metell you about an expert system | have been writing and playing with. It s called GENESIS 4. This soundslike a reasonable namefor a package: GENESIS Release 4.0; but actually this is to do with the Bible (8). Not that | am particularly religious by nature; it s just that the Bible predates Behaviour: The Control of Perception as a functional specification of humanity by about 5000years,soit s of interestto all artificial intelligence bufts.

All expert systems have three chunks,

The SITUATION MODELis a wholeload of information about(in this case) Adam s descendants, their marriages, their progeny and the main eventsin theirlives.

The KNOWLEDGE BASE isa setof rules whichindicate the laws of genealogy. For example, Ais offspring of B if B begat A and so on.

The SYSTEM MANAGER is a setof programsthat allows you to explore the situation model, askit questions, andaskit to draw conclusions:for example, ls Z descended fram A? . Clever system managers sometimestry to propose rules by looking for patternsin large amountsof datain a situation model,

That s all.

68

Vector Vol. 1 No. 2

What| will do now is re-write parts of Genesis Chapter4 asif | were entering lines into an APL- based expert system, trying to keep it as muchlike PROLOGaspossible. The numbersin the margins are the verses.

1. "'And Adam knew Evehis wife; and she conceived, and bare Cain, and said I have gotten a man from the Lord . ADAM IS-MARRIED-TO EVE CAIN |S-OFFSPRING-OF ADAM CAIN IS-OFFSPRING-OF EVE CAIN IS-SEX MALE

2. And she again bare his brother Abel. ABELIS-OFFSPRING-OF EVE ABEL IS-SEX MALE

8. Cain rose up against Abel his brother, and slew him." CAIN KILLS ABEL

16."*Cain wentout from the presenceofthe Lord, and dweltin the land of Nod, onthe east of Eden. CAIN INHABITS NOD NOD1S-EAST-OF EDEN

17."And Cain knew his wife, and she conceived, and bare Enoch: and he builded a city, and called the nameofthecity,after the name of his son, Enoch. And unto Enoch wasbornIrad: and Irad begat Mehujael: and Mehujae! began Methusael: and Methusael begat Lamech. CAIN IS-MARRIED-TO MRS.X ENOCH IS-OFFSPRING-OF CAIN ENOCH IS-OFFSPRING-OF MRS.X CAIN BUILDS-CITY-CALLED ENOCH IRAD (S-OFFSPRING-OF ENOCH MEHUJAEL IS-OFFSPRING-OF !RAD METHUSAEL IS-OFFSPRING-OF MEHUJAEL LAMECH|S-OFFSPRING-OF METHUSAEL

There's a lot moreofthis sort of thing. | know that the Bible is now available in compressed text form onfloppy discs as THE WORDProcessor (9) but! ll wagerthat the logicalinferences remain unencoded.

Whatcan we do with APL so far? Well, we need to encode this information into APL datastructures. There are many ways ofdoing this, of course. An obvious approachisto write little parser which takes statementslike LAMECH IS-OFFSPRING-OF METHUSAELanddivide them into their different text strings(3 in this case). Westart building a text matrix with a uniqueinstance of each name. Whena statement comesin, we look up the row numberof eachstring or we add the new string to the end ofthe matrix. So the sequence: MEHUJAELIS-OFFSPRING-OF IRAD METHUSAEL1S-OFFSPRING-OF MEHUJAEL LAMECH IS-OFFSPRING-OF METHUSAEL would be represented by these two matrices: MEHUJAEL 1 2 3 \IS-OFFSPRING-OF 4 2 1 IRAD 5 2 4 METHUSAEL LAMECH

69

Vector Vol. 1 No. 2

Actuallyit s slightly trickier than this as we shall need flag bit to indicate which entry is a relationship and whichis a noun, and they aren't alwaysbinary relationships, and the arguments aren't always on each side. But the basic idea s the same. A simple parsing function in APL is about5 lines of code, and if we call it ADD it really does looklike PROLOG.: ADD LAMECH IS-OFFSPRING-OF METHUSAEL'

So far, so trivial, but we ve done something epoch-making: we've defined our first function in XPL, which is the name | have chosen forthis set of functions, written in APL but using ASCII character set throughout. Now we wantto interrogate the database: Is Lamechthe offspring of Methusael? DOES LAMECH IS-OFFSPRING-OF METHUSAEL TRUE Is Irad the offspring of Mehujael? DOES IRAD !S-OFFSPRING-OF MEHUJAEL FALSE

Funnysyntax,isn'tit? I'm trying to stick to PROLOGthough, andthisisit. Now is it mindbogglingly hard to code this in XPL? Notreally: function DOESlooksto be at least one tine long: it has to find a particular row of integers in the matrix. Of course things get tougher in PROLOG quite quickly: Whois the offspring of Methusael? WHICH X:X IS-OFFSPRING-OF METHUSAEL LAMECH Whois the offspring of Lamech? WHICH X:X IS-OFFSPRING-OF LAMECH NO MATCH

This time not only do we haveto find a particular row ofintegers in the numeric matrix, we also have to work out who X refers to and find him in the fist of names. Fiendish stuff. Still, | think wecanjust about cope.Let s move onto the knowledge base. Here s someusefuljargon. You and | are knowledge engineers in the context of our translation of the Bible into XPL format. Priests are domainspecialists : Heaven and Hell is their domain. To this | would add that people who create expert systems languages, as we are doing at this moment, are presumably metadomain specialists (I believe this is an original coinage).

It gets boring telling XPL everything twice. For example: ADD LAMECH IS-OFFSPRING-OF METHUSAEL ADD METHUSAEL IS-PARENT-OF LAMECH How aboutdefining a rule instead? ADD X IS-PARENTOFY IF Y IS-OFFSPRING-OFX and while we're aboutit: ADD 'X JS-OFFSPRING-OF Y IF Y IS-PARENT-OF X Not too hard to handle eitheris: ADD X IS-HUSBAND OFY IF X IS-MARRIED-TO Y AND X IS-SEX MALE Nowtry: ADD XIS-GRANDCHILD-OFY IF X1S-OFFSPRING-OFZ AND Z IS-OFFSPRING-OF Y

70

Vector Vol. 1 No. 2

We'veintroduced the conceptof place markers , which are analogousto the local namesof the argumentsoffunctions, exceptthat the functions are relations (data) rather than programs. There are many waysto incorporate these into XPL and your ownideaswill undoubtedly be better then mine: | use negative numbersin the integer matrix to denote place markers: MEHUJAEL 1 2 3 IS-OFFSPRING-OF 4 2 1 IRAD 5 2 4 METHUSAEL -1 6 -2 LAMECH -1 2 -3 1S-GRANDCHILD-OF -3 2 -2

The functions DOES and WHICH now becomerather moreinteresting. Suppose we ask the question: DOES ENOCH IS-GRANDCHILD-OF ADAM DOESnowhasto go scouting around to seeif this is a bit of knowndata. If not, it goes to see if it has a rule-based definition for the grandchild relation. If it does, it hasto find the first match for Enoch basedontheoffspring relation, and then pause while it tests whetherthis match in turn relates to Enoch. If not, it can resume looking for further matches for Enoch. It goes without saying that an XPLfunction employing recursionis the elegant(possibly the only) way to implement this process.It isn t very difficult to do.

Here s a moreinteresting rule: ADD X IS-DESCENDANT-OFY IF X IS-CHILD-OFY ADD X IS-DESCENDANT-OFY IF X IS-CHILD-OF Z AND Z IS-DESCENDANT-OFY"

Recursion groupieswill see the classic syntax: thefirst line denotesthelimiting condition, the seccnd line forms the recursive relation. The extensive use of recursive tests based on goal- seeking requests from the useris termed backtracking for obvious reasons. The standard mechanism ofthe state indicator in APL handles such requests beautifully.

| hopethat thase with some APL experiencecanseethatit is not inordinately tricky to implement these aspects of PROLOGin user-defined APL functions. After a while the imagination starts runningriot: ADD X PROBABLYIS-CHILD-OF Y IF X IS-CHILD-OF Z AND Y IS-MARRIED-TO 2

| suppose there s always the milkman. Adverbslike DEFINITELY, PROBABLY, POSSIBLY, CONCEIVABLY(oops) and INCONCEIVABLYcan conveniently carry probability valueslike 1.0, 0.75, 0.5, 0.25 and 0; if you want to change the climate of expert opinion you can tinker with the values. And don t forget NOT: ADD X IS-SEX FEMALE IF X NOT IS-SEX MALE Well, we don tall live in San Francisco.

Whatabout expert systems themselves? If you recall the three elements: situation model knowledge base system manager then it turns out in languages like PROLOGthatthe preceding constructs are used on an intermixed basis to representdatain the situation model and rules in the knowledge base. In XPL onefeels it may be cleaner to keep them separate, butthat's a matterfor personaltaste.

71

Vector Vol. 1 No. 2

More importantly, most PROLOGusers don t seem to have caughton to the fact that muchof the datain the situation model may well be a transform of, for example, data aboutpatientsin a medicalfile whose records have been painstakingly composed over manyyears. File access to other systemsis imperative; most of the facts are already there.

Furthermore, although PROLOGis goodatrelations, it s very bad at numerical tests. An expert system for shopfloor control needs to copewith quantified tests based on quasi-real-time input from process sensors: for example: ADD TURBINE SWITCH-SETTING OFF IF RPM ABOVE5000 is as far as | know impossible to handle in PROLOGif RPM is intended to be directly linked to the real world, whereas in APL one simply makes RPM variable shared with an auxiliary processor which handles direct data capture. For non-APLers this means:variable RPM in the APL workspace is dynamically coupled via a programmer-specifiable update protocol with an arbitrary machine code segment,whichisitself either handling process input/outputoris talking to someother processthat is. The pointis that a robust and very well established framework for this kind of dynamiclinking already exists in APL.

I hope | have managedto whettwokindsof appetite.If you know APLalready, you maybe starting to think about building your own XPL functions (mineare for private consumption and you've had numeroushints already) and writing your own expert system.If you know about expert systems and aretoiling with inadequate tools, you mightjust think aboutlooking at APL instead. An unlikely marriage? I don tthink so. No more than Cain s, anyway;the identity of Mrs is the theological riddle of the millenium, Good luck with such experiments: may thy domainspecialities be brought forth and multiply upon the interface of the digital computer.

References

(1) Artificial intelligence: the race to makeit work for managers. International Management, September 1984, pp. 20-26.

(2) Godel Escher Bach: An Eternal Golden Braid Douglas Hofstadter: Harvester Books & Penguin Press.

(8) Behaviour: The Control of Perception William T. Powers: Wildwood House

(4) Cybernetics Norbert Wiener: MIT Press

(6) Brain of the Firm (2nd edition) Stafford Beer: John Wiley & Sons

(6) Do Androids Dream of Electric Sheep? Ray Bradbury (publisher untraced)

(7) Logic Programming in APL Robert Jernigan: APL84 Conference Proceeding

(8) Book of Genesis Chapter 4 Holy Bible, King Jamesversion

(9) The Word Processor: King JamesBible on floppy discs Bible Research Systems, 9415 Burnet Road, Austin, Texas.

72

Vector Vol.1 No.2

STEPS TOWARDSA BETTER BASIC PART 2 by Anthony Comacho

in this second extract from Anthony Comacho s series aimed at convincing BASICusersof the delights ofAPL, the notionofarrayprocessing /s discussed and an intriguing example is selected from the Gregorian calendar.

The article is reproduced with the kind permission of DATALINK magazine. Alanguage which allowsa singleinstruction or commandto processall the membersof an array at once so to speak, has the advantagesthat it saves the programmerthinking about unnecessary loops and it makes the programs compatible with parallel processors.

In any programming languageit is necessary to have a methodfor teferring to variables which allows the variable referred to to be changed under program control.

An easywayis to name all thefields in a record and thento step from the recordto the next through afile. This approach avoidsthe needto vary the nameof the variable that you are dealing with while at the sametime achieving the objectof dealing with a seriesof variablesin the same waywith the same piece of program. This is common in Cobol.

Asecond way one familiar to people who have programmedin Basic is to define an array of variables which have a name in commonand a subscriptto distinguish betweenthe various members ofthe array, for example ARRAY(25) for 25 numbers.

The third methodis to use the array name to referto all the members of the array and to use a subscripting method whenoneor more of the membersofthe array is to be singled out for individual special treatment.

Of these three methods, only the third allows simple instructionsto referto all the members of an array.

The first advantageofthis is that the programmerdoesn't have to think of so manyloops.All he needsto dois to ensurethat all the variables on which he wantsto performa similar operation are membersof the samearray. Of course,this doesn t actually removetheloopfrom the program. The machine codestill runs round processing eachitem of the array in turn until they are all done, butit is done in machine code by the interpreter program, not slowly as a FOR...NEXT, DO WHILE or REPEAT UNTIL loop and the programmerdoes nothaveto bother aboutstart and end conditions of the loop.

Theother main advantageis that this method explicitly allows for parallel processing. We will not benefit much from this until a new generation of computersis in commonuse. The problem with array processorsor parallel processorsof any kindis that they normally require programs to be specially rewritten for them. This is because an ordinary compiler cannot tall whether the sequencegivenis important.

Aconsequence of this is that most programs get no advantage from array processors and so very few array processorsare in regular daily use.

The leap yearfunction shownin Figure 1 demonstrates the great brevity of APL. Instead of explaining the use of the symbols, | will stick to the principles. It takes in YEARS a one dimensionalarr ay(ie a row or list) of years and outputs LEAPS another one dimensional array of leap years. | have putin an extra pair of brackets to show the sequenceof calculation. Thefirst operation (inner bracket) is to find the remainder after dividing each yearin thelist by 4 and 100 and 400 and 4000.

The result of this is a table of remainders four deep and aslong as the numberofyears in the 73

Vector Vol.1 No.2

list. Then for each year(ie column in the table) this table is processed (outer brackets). If the remainderfrom division byfour waszero thenitis aleap year unless the remainderfrom division by 100 was zero, in which case it is not. But even then it would be if the remainder from the division by 400 was zero and the remainderfrom division by 4000 wasnot.

The result of the processing is an array of true or false or yes or no values ones for years that passed the test and are leap years, and zeros for years that did not passthe test. The last thing to dois to select out of the original array all those years which correspond to onesin the array of true and false values and this is done outsideall the brackets bythe (true and false array)/YEARSoperation. Notice how the operations on each year can be donein parallel. The line works equally well with two, 20 or 200 years in the YEARSarray.

Figure 1: A Leap Year Solution in APL

YEARS : 1984 1985 1986 1987 1988 1989 199) 1991 1492 LEAPS (# +0=(4 100 400 40009 IVEARSI YEARS

LEAPS 1984 1988 1992

74