Källkoden till programmeringsspråket APL

Software Gems: The Computer History Museum Historical Source Code Series

Tusentals programmeringsspråk uppfanns under de första 50 åren av datorernas tidsålder. Många av dem liknade varandra och många följde en traditionell, evolutionär väg från sina föregångare.

Men vissa revolutionära språk hade en vinkling som skilde dem från sina mer allmännyttiga bröder. LISP var för listbehandling. SNOBOL var för hantering av strängar. SIMSCRIPT var för simulering. Och APL var för matematik, med tonvikt på arraybehandling.

Det som så småningom blev APL uppfanns först av Harvardprofessorn Kenneth E. Iverson 1957 som en matematisk notation, inte som ett datorprogrammeringsspråk. Även om det fanns andra matrisorienterade symbolsystem, inklusive den kortfattade tensor-notationen som uppfanns av Einstein, var de mer inriktade på matematisk analys och mindre på syntes av algoritmer. Iverson, som var elev till Howard Aiken, lärde ut det som blev känt som ”Iverson Notation” till sina Harvardstudenter för att förklara algoritmer.

Iverson anställdes av IBM 1960 för att arbeta tillsammans med Adin Falkoff och andra på sin notation. I sin numera berömda bok ”A Programming Language” 1 från 1962 säger han att notationen är avsedd för att beskriva ”förfaranden … som kallas algoritmer eller program”, och att det är ett språk eftersom det ”uppvisar en betydande syntaktisk struktur”. Men vid den tidpunkten var det bara en notation för människor att läsa, inte ett språk för programmering av datorer. I boken ges många exempel på dess användning både som ett beskrivande verktyg (t.ex. för att dokumentera definitionen av datorinstruktionsuppsättningar) och som ett sätt att uttrycka allmänna algoritmer (t.ex. för sortering och sökning). Eftersom han förutser motstånd mot något så nytt säger han i förordet: ”Det är den centrala tesen i den här boken att den beskrivande och analytiska kraften hos ett adekvat programmeringsspråk gott och väl betalar tillbaka den avsevärda ansträngning som krävs för att behärska det”. Kanske varnade han för att det inte var trivialt att behärska språket. Kanske signalerade han också att andra notationsspråk enligt honom var mindre än ”adekvata”.

Gruppen såg naturligtvis snart att notationen kunde omvandlas till ett språk för programmering av datorer. Det språket, som kallades APL från och med 1966, betonade hantering av matriser och använde okonventionella symboler. Det liknade inget annat datorprogramspråk som hade uppfunnits.

APL blev populärt när IBM introducerade ”APL360” för sin stordator System/360. Till skillnad från de flesta andra språk på den tiden var APL360 också en komplett interaktiv programmeringsmiljö. Programmeraren, som satt vid en elektromekanisk skrivmaskin kopplad till en tidsdelad dator, kunde skriva APL-satser och få ett omedelbart svar. Programmen kunde definieras, felsökas, köras och sparas på en dator som samtidigt användes av dussintals andra personer.

Skriven helt och hållet i 360-assembleringsspråk tog denna version av APL kontroll över hela maskinen. Den implementerade ett komplett timesharing-operativsystem utöver ett högnivåspråk.

Med tillstånd från IBM har Computer History Museum nöjet att göra källkoden till 1969-1972 års ”XM6”-version av APL för System/360 tillgänglig för icke-kommersiellt bruk.

Textsamlingen innehåller 37 567 rader, vilket inkluderar kod, makron och globala definitioner. De 90 enskilda filerna är separerade med ’./ ADD”-kommandon. För att få tillgång till detta material måste du godkänna villkoren i den licens som visas här, som endast tillåter icke-kommersiell användning och som inte ger dig rätt att licensiera den till tredje part genom att lägga ut kopior någon annanstans på webben.

Ladda ner APL360-källkoden

Jürgen Winkelmann vid ETH Zürich har gjort ett fantastiskt arbete med att omvandla denna källkod till ett körbart system. För mer information, se MVT for APL Version 2.00.

Skapande av programmeringsspråket APL

Iversons bok ”A Programming Language” 1 använder en grafisk notation som skulle ha varit svår att direkt använda som ett programmeringsspråk för datorer. Han betraktade det som en utvidgning av matrisalgebra och använde vanliga matematiska typografiska konventioner som subscripts, superscripts och distinktioner baserade på teckenens vikt eller typsnitt. Här är till exempel ett program för sortering av tal:

För att linjärisera notationen så att den kunde användas som programmeringsspråk för datorer som skrivs på ett tangentbord var APL-utförarna säkerligen tvungna att ge upp användningen av märkta pilar för kontrollöverföringar. Men en funktion som de i viss utsträckning kunde behålla var användningen av speciella symboler för primitiva funktioner, vilket illustreras i detta program som skapar Huffman-koder:

APL använder symboler som ligger närmare standardmatematik än programmering. Symbolen för division är till exempel ÷, inte /. För att stödja de okonventionella symbolerna använde APL360 ett specialdesignat tangentbord med specialsymboler i versaler.

Till och med det fanns det fler specialtecken än vad som fick plats på tangentbordet, så en del av dem skrevs genom att man överströk två tecken. Till exempel skapades ”grade up”-tecknet ⍋, en primitiv operatör som används för sortering, genom att skriva ∆ (shift H), sedan backspace och sedan ∣ (shift M). Det fanns inget utrymme kvar för både stora och små bokstäver, så APL stödde endast stora bokstäver.

För att skriva ut program fick Iverson och Falkoff IBM att designa en speciell typboll för sina terminaler 1050 och 2741, som använde sig av IBM:s Selectric-maskin för skrivmaskiner.

Nu kunde program både skrivas in och skrivas ut. Här är till exempel den utskrivna versionen av ett program från APL Language manual 2 som beräknar den matematiska determinanten för en matris:

A Taste of APL

APL är ett kortfattat programmeringsspråk på hög nivå som skiljer sig från de flesta andra språk som utvecklades på 1960-talet i flera avseenden:

Evalueringsordning: Det finns ingen hierarki i fråga om funktioners företräde. Om man till exempel skriver in uttrycket

får datorn att omedelbart skriva in det resulterande värdet

Värdet är inte, som i många andra språk som har operatörsprecens, 11. Parenteser kan naturligtvis användas för att gruppera ett deluttryck för att ändra utvärderingsordningen. Den allmänna regeln är att det högra argumentet i en funktion är värdet av uttrycket till höger om den.

Automatiskt skapande av vektorer och matriser: En högre dimensionell struktur skapas automatiskt genom att utvärdera ett uttryck som returnerar den, och skalarer kan blandas fritt. Exempelvis

skapar vektorn ”1 2 3”, lägger till skalaren 2 till den och skapar variabeln A för att hålla vektorn vars värde är

Variabler deklareras aldrig, utan de skapas automatiskt och antar storleken och formen för det uttryck som tilldelas dem.

En uppsjö av primitiver: APL har en rik uppsättning inbyggda funktioner (och ”operatörer” som tillämpas på funktioner för att ge olika funktioner) som fungerar på skalarer, vektorer, matriser, även högre dimensionella objekt och kombinationer av dem. Till exempel är uttrycket för att summera siffrorna i vektorn ”A” som skapats ovan helt enkelt

där / är ”reduktionsoperatorn” som gör att funktionen till vänster tillämpas successivt på alla element i operanden till höger. Uttrycket för att beräkna medelvärdet av talen i A använder också den primitiva funktionen ρ för att bestämma hur många element det finns i A:

Här är några tabeller från 1970 års ”APL360 User’s Manual” 3 som ger en smak av kraften och sofistikeringen hos de inbyggda APL-funktionerna och operatorerna. (Klicka på bilderna för större versioner.)

APL uppmuntrar dig att tänka annorlunda kring programmering och att använda tillfälliga högdimensionella datastrukturer som mellanliggande värden som sedan reduceras med hjälp av de kraftfulla primitiva funktionerna. Ett känt exempel är följande korta men fullständiga program för att beräkna alla primtal upp till R.

Här är hur detta uttryck utvärderas:

uttryck	betydelse	värde om R är 6
⍳R	Generera en vektor av tal från 1 till R.	1 2 3 4 5 6
T←1↓	Släpp det första elementet i vektorn och tilldela resten till den tillfälliga vektorn T.	2 3 4 5 6
T∘.×T	Skapa den yttre multiplikationsprodukten: en tabell som innehåller resultatet av att multiplicera varje element i T med varje element i T.
T∊	Använd operatören ”set membership” för att ta reda på vilka element i T som finns i tabellen.	0 0 1 0 0 1
~	Negera resultatet för att identifiera vilka element i T som inte finns i tabellen. Detta är de heltal som inte har några multiplar i tabellen.	1 1 0 1 1 0
( )/T	Välj de element i T som vi har identifierat. Dessa är alla primtal mindre än R.	2 3 5

Bemärk att det inte finns några slingor i detta program. Styrkan hos APL-uttryck innebär att villkorliga förgreningar och slingor behövs mycket mer sällan än i mer traditionella programmeringsspråk.

APL-operatorer kan användas på enkla sätt för alla typer av beräkningar som vanligtvis skulle kräva slingor. Ett uttryck som till exempel beräknar antalet element i vektorn X som är större än 100 är

Det fungerar eftersom X>100 returnerar en bitvektor av 0:or och 1:or som visar vilka element i X som är större än 100, och +/ adderar alla bitar i den vektorn.

Men villkorligt utförande och slingor behövs förstås ibland. Mot bakgrund av senare utveckling av strukturerad programmering är APL:s enda primitiv för kontrollöverföring, ”GO TO LINE x”-angivelsen →, särskilt svag. Här är ett exempel på en funktion som beräknar den största gemensamma divisorn för sina två argument. Det sista uttalandet skapar en slinga genom att grena till början. I rad 2 leder en villkorlig överföring av kontrollen till rad 0 till att funktionen avslutas och returnerar det värde som senast tilldelades G.

Om du vill veta mer om APL-språket från 1960-talet kan du läsa referensmanualen ”APL Language” 2 och Paul Berrys 1969 års ”APL360 Primer” 4.

Språket har förstås utvecklats under årens lopp, och nyare versioner innehåller kontrollstrukturer som IF-THEN-ELSE.

Hur APL implementerades

Den första datorimplementeringen av APL-notationen var en batchorienterad språktolkare skriven i FORTRAN 1965 för stordatorn IBM 7090 av Larry Breed vid IBM Research Center i Yorktown Heights NY och Philip Abrams, som då var doktorand vid Stanford University.

Den första interaktiva versionen skrevs kort därefter för 7093 (en experimentell 7090 med virtuellt minne) av Larry Breed och Roger Moore. Den kördes under timesharing-systemet TSM och kallades lustigt nog ”IVSYS”, vilket rimmar på ”IBSYS”, namnet på standardoperativsystemet 7090. I ett e-postmeddelande från 2012 säger Breed,

En annan implementering av en delmängd av språket gjordes 1967 för minidatorn IBM 1130.

Den första implementeringen av APL som fick stor spridning utanför IBM var för IBM System/360. Den kallades ”APL360” och togs först i bruk inom IBM i november 1966. (Noteringen ”APL360″, eftersom backslash var APL:s ”expansion”-operator, hade också en dold betydelse: ”

Breed säger om tiden strax före,

I augusti 1968 fanns APL360 tillgängligt för IBM:s kunder som ett program utan stöd (”typ III”) i IBM:s ”Contributed Program Library” 5. De främsta implementatörerna var Larry Breed, Dick Lathwell och Roger Moore; andra som hade bidragit var Adin Falkoff och Luther Woodrum.

På grund av APL-variablernas dynamiska natur implementerades APL360 som en tolk, inte som en kompilator som genererade maskinkod. Programmen lagrades i en intern form som kallades ”kodsträng” och som direkt motsvarade det som användaren hade skrivit. Tolken undersökte sedan kodsträngen när programmet utfördes och tilldelade och konfigurerade om variabler dynamiskt när uttryck utvärderades.

De första versionerna av APL360 tog kontroll över hela maskinen. Det var alltså en kombination av operativsystem, filsystem, tidsdelningsmonitor, kommandotolk och programmeringsspråk. Med tanke på det begränsade huvudminnet byttes användarnas arbetsutrymmen ut till trummor eller diskar efter behov. Prestandan var imponerande, vilket Larry Breed i sin tydliga och kortfattade beskrivning av genomförandet tillskriver förmågan att skräddarsy operativsystemet efter språkets krav.

APL360 var ett konversationsspråk som gav snabb respons och effektivt utförande för så många som 50 samtidiga användare. Varje användare hade en ”aktiv arbetsyta” som innehöll program, variabler och tillståndet för uppskjuten programutförande. Systemkommandon som ”)LOAD”, ”)SAVE” och ”)COPY” upprätthöll användarens bibliotek av lagrade arbetsutrymmen. Andra systemkommandon kontrollerade språkfunktioner; till exempel kunde programmeraren med ”)ORIGIN” styra om vektorer och matriser ska numreras från 0 eller 1.

APL var den första introduktionen till interaktiv tidsdelning för många i den generation programmerare som hade lidit av batchprogrammering med hålkort.

Applications of APL

Alltsedan innan det blev ett datorprogrammeringsspråk var Iverson Notation användbart som ett språk för att dokumentera algoritmer för människor. Det klassiska exemplet är den formella definitionen av instruktionsarkitekturen för den nya datorn IBM System/360, som publicerades i en artikel i IBM Systems Journal av Adin Falkoff, Ken Iverson och Ed Sussenguth 1965 7.

• Starmap: En uppsättning APL-funktioner för att beräkna och plotta positioner för stjärnor och planeter. 8 9 Det skrevs 1973 av Paul Berry från IBM och John Thorstensen, då astronomistudent vid Bryn Mawr College, numera professor i fysik och astronomi vid Dartmouth College. Den använder klassiska lösningar på Keplers ekvationer för ett visst datum och en viss tid och en serie rotationer av koordinater för att visa var planeterna och stjärnorna skulle synas i himlens skål.
• IBGS: Interactive Business Game Simulation: ”En allmän datorsimulering för företagsledning som omfattar beslutsfattande och planering inom funktionsområdena produktion, marknadsföring och ekonomi.”
• Nollor och integraler i APL: ”Med hjälp av både klassiska metoder som Newtons och Mullers och nyligen utvecklade metoder som Jenkins och Traubs, finner man reella nollor av en reell funktion, reella och komplexa nollor av ett polynom med reella eller komplexa koefficienter, och komplexa nollor av en komplex funktion.”
• Graphpak – Interactive Graphics Package for APL360: ”… funktioner som sträcker sig från stöd för grafiska gränssnitt på lägsta nivå till flera tillämpningsområden på högre nivåer… En plottningskomponent… linjär eller logaritmisk… kurvanpassning… En komponent för beskrivande geometri gör det möjligt att definiera, skala, förstora, översätta, rotera och projicera tredimensionella objekt.”
• Grafer och histogram i APL: ”producerar kurvor och stapeldiagram vid en skrivmaskinstation”.
• APL:s koordinatgeometrisystem: ”löser koordinatgeometriska problem interaktivt vid en terminal… för användning av lantmätare, civilingenjörer, stadsplanerare…”
• APL/PDTS – Programming Development Tracking System: ”…för att hjälpa chefer och planerare att övervaka prestationer i förhållande till planerna i programutvecklingsprojekt.” MINIPERT: ”A Critical Path Method (CPM) system for Project Management”
• APL Econometric Planning Language: ”Den praktiserande ekonomen, företagsprognostikern eller läraren får tillgång till lättanvända verktyg för interaktiv modellbygge och modelllösning.”
• APL Financial Planning System: APL Financial Planning System: APL är ett system för finansiell planering: ”låter finansanalytiker och planerare utforma rapporter, specificera beräkningar, ange och ändra data och få utskrivna rapporter med omedelbar leveranstid.”
• APL Text Editor and Composer: ”Funktioner ingår för att skriva in, revidera, komponera, skriva ut och lagra text … för användning av sekreterare, vetenskapsmän, ingenjörer, administratörer eller andra som producerar papper, brev, rapporter eller specifikationer.”

Många av dessa tillämpningar betonade interaktivitet, vilket gav en enorm produktivitetsökning jämfört med den batch-arbetsbehandling som var mer typisk för den tiden. Dessutom gjorde APL det möjligt att utveckla tillämpningar mycket snabbare. I ett e-postmeddelande från 2012 noterade Larry Breed följande:

De områden där APL hade störst genomslagskraft var inom vetenskapliga, försäkringstekniska, statistiska och finansiella tillämpningar. För detaljer om utvecklingen av APL under dess första 25 år, se specialnumret från 1991 av IBM System Journal 10 med 12 artiklar och en essä i ämnet.

APL beröm och kritik APL var ursprungligen inte utformat som ett programmeringsspråk. Som Iverson sade,

Med så många kortfattade och ovanliga symboler har APL-datorprogrammen, i likhet med den matematiska notation som inspirerade dem, en kortfattadhet och elegans som många finner tilltalande. APL lockar till sig fanatiska anhängare. Alan Perlis (den första mottagaren av ACM:s Turingpris 1966) var en av dem:

Många tycker att uttrycksfriheten i APL är befriande.

Men APL-programmen är ofta kryptiska och svåra att avkoda. Vissa har skämtat om att det är ett ”write-only language” eftersom till och med författaren av ett program kan ha svårt att förstå det senare. Det inspirerar till programmeringsknep. Det är svårt att motstå utmaningen att skriva en APL-”one-liner” för att genomföra en komplett komplex algoritm. Här är till exempel två olika APL-liners som implementerar versioner av John Conways ”Game of Life”:

Inte för de svaga, helt klart. Den holländske datavetaren Edsger Dijkstra sade,

Men fans av APL skulle säga att kryptisk APL-kodning är en dålig programmeringsstil som kan vara en åkomma för alla språk. APL ger en rikare palett för att uttrycka algoritmer, menar argumentet, så man kan lösa svårare problem snabbare och med mindre irrelevant syntaktiskt virrvarr.

Oavsett din åsikt är APL och de språk som det inspirerade, till exempel APL2 och J, fortfarande en aktiv del av det mångsidiga universumet av programmeringsspråk.

En kort biografi om Ken Iverson

Kenneth Eugene Iverson föddes den 17 december 1920 på en gård nära Camrose, Alberta, Kanada. Han utbildades i enrumsskolor på landsbygden fram till slutet av nionde klass, då han hoppade av skolan eftersom det var depressionens höjdpunkt och det fanns arbete att göra på familjens gård. Han sade senare att det enda syftet med att fortsätta sin skolgång skulle ha varit att bli lärare, och det var ett yrke som han definitivt inte ville ha. Under de långa vintermånaderna studerade han kalkyl på egen hand.

Han blev inkallad 1942, och under sin tjänstgöring tog han tillräckligt många korrespondenskurser för att nästan slutföra gymnasiet. Efter militärtjänsten tog han en kandidatexamen i både matematik och fysik från Queen’s University i Kingston, Ontario, och sedan en magisterexamen i fysik från Harvard University. År 1954 disputerade han under datorpionjären Howard Aiken med en avhandling med titeln ”Machine Solutions of Linear Differential Equations: Applications to a Dynamic Economic Model”.

När han hade disputerat anslöt sig Iverson till Harvard-fakulteten för att undervisa i Aikens nya program för automatisk databehandling. Han var där i ett år som instruktör och i fem år som biträdande professor. Han blev alltmer frustrerad över den konventionella matematiska notationens otillräcklighet när det gällde att uttrycka algoritmer, så han började uppfinna sina egna.

År 1960 gick Iverson med i IBM:s nya forskningscenter i Yorktown Heights, New York, på inrådan av Frederick Brooks, som hade varit en av hans lärarkollegor på Harvard och som nu var på IBM. De två samarbetade i den fortsatta utvecklingen av den nya notationen. År 1962 publicerade Ken den numera klassiska boken ”A Programming Language” 1, vars titel gav namnet APL till den notation som fram till dess informellt hade kallats ”Iversons notation”.

Iverson fortsatte att arbeta med utvecklingen av APL under hela sin tid på IBM. År 1980 lämnade han IBM och återvände till Kanada för att arbeta för I.P. Sharp Associates, som hade etablerat en APL-baserad timesharing-tjänst.

År 1987 ”pensionerade han sig från betald anställning” och vände sig helt och hållet till utvecklingen av en mer modern dialekt av APL. APL användes framgångsrikt för kommersiella ändamål, men Iverson ville utveckla en ny enkel exekverbar notation som lämpade sig bättre för undervisning och som skulle vara tillgänglig till låg kostnad. Den första implementeringen av detta språk, kallat J, tillkännagavs vid APL90 Users’ Conference.

Iversons förmåga att skapa sådana språk berodde på hans ”rena njutning av språk och ord”, minns hans dotter Janet Cramer. ”Han läste ordböcker som folk läser romaner.” Iverson tyckte att det var viktigt att språk, både engelska och matematik, kommunicerar tydligt och kortfattat.

Med medarbetare som inkluderade hans son Eric fortsatte Iverson att arbeta med utvecklingen av J, och han fortsatte att publicera flitigt. Lördagen den 16 oktober 2004 drabbades han av en stroke – medan han arbetade med en handledning om J – och avled tre dagar senare, den 19 oktober, vid 83 års ålder.

Det finns många historier om Ken Iverson. Här är några:

Acknowledgements

Bibliografi

1. K. E. Iverson, A Programming Language, John Wiley and Sons, Inc. 1962.
2. IBM, ”APL Language”, mars 1975.
3. IBM, ”APL360 User’s Manual”, mars 1970.
4. IBM, Paul Berry, ”APL360 Primer – Student Text”, 1969.
5. L. M. Breed och R. H. Lathwell, ”APL360”, 1968.
6. L. M. Breed och R. H. Lathwell, ”The Implementation of APL360”, i ACM Symposium on Experimental Systems for Interactive Applied Mathematics, 1967.
7. A. D. Falkoff, K. E. Iverson och E. H. Sussenguth, ”A Formal Description of SYSTEM/360”, IBM Systems Journal, vol. 3, no. 3, pp. 198-261, 1964.
8. P. C. Berry och J. R. Thorstensen, ”Starmap,” 1978.
9. P. C. Berry och J. R. Thorstensen, ”Starmap,” IBM Systems Development Division, 1975.
10. IBM Systems Journal, vol. 30, no. 4, 1991.
11. K. E. Iverson, ”A Personal View of APL”, IBM Systems Journal, vol. 30, no. 4, 1991.
12. A. J. Perlis, ”In Praise of APL: A Language for Lyrical Programming”, SIAM News, juni 1977.
13. B. McCormick, ”A Programming Language”, 2000,2002.
14. E. W. Dijkstra, ”How Do We Tell Truths That Might Hurt?”,” SIGPLAN Notices, vol. 17, no. 5, maj 1982.
15. A. D. Falkoff och K. E. Iverson, ”The Design of APL,” IBM Journal of Research and Development, vol. 17, no. 4, 1973.
16. A. D. Falkoff och K. E. Iversion, ”The Evolution of APL,” SIGPLAN Notices, vol. 13, no. 8, pp. 45-57, augusti 1978.
17. L. Breed, ”How We Got to APL1130,” 10 maj 2004.
18. ACM, ”Proceedings of the APL’69 Conference on APL”, SUNY Binghamton, NY, 1969.
19. ”The Origins of APL – 1974”; en underbar intervju med de ursprungliga utvecklarna av APL.

Historiska källkodsreleaser

• Källkod för MacPaint och QuickDraw, 18 juli 2010
• Källkod för programmeringsspråket APL, 10 oktober 2012
• Källkod för Adobe Photoshop, 13 februari 2013
• Apple II DOS Source Code, 12 november 2013
• Microsoft MS-DOS Early Source Code, 25 mars 2014
• Microsoft Word for Windows Version 1.1a Source Code, 25 mars 2014
• Early Digital Research CP/M Source Code, 1 oktober 2014
• Xerox Alto Source Code, 21 oktober 2014
• Electronic Arts DeluxePaint Early Source Code, 22 juli 2015