This is the article that instantly made me crazy about programming, before even having been near any computer. The example program (an implementation of the game NIM written in BASIC) and matching flowchart, although very cryptic, even messy, were an excellent example of the way a computer program independently can make decisions based on some given data. Data, partly coming from a user (a player making a move), partly from the current state of the system itself (the number of sticks in each row).
It is nice to see the ideas people had in 1982 about presenting source code. Like the advice to use as few spaces as possible, or the zero being written as 'Ø'.
Below you will find the original text of the article, together with figures and the listing of the example program. The flow chart is included separately as an MS Draw object in a Word 6.0 document. This document can be opened with WordPad, the word processor that comes standard with Windows 95/98.
Sorry English readers, this is in Dutch only.
Computers zijn machines die voor steeds meer mensen toegankelijk worden. Ze zijn allang niet meer uitsluitend in bedrijven of wetenschappelijke instellingen te vinden. Ook op school en thuis wordt er mee gewerkt. Wie de computer met meesterhand wil besturen, moet hem in een speciale taal toespreken: Basic. Echt moeilijk is dat niet. Op deze pagina's vertellen we er iets meer over. Wie iets van Basic weet en echt durft, kan aan onze wedstrijd meedoen en de ZX 81 computer van Sinclair winnen.
Een computerprogramma is een "schaduw" van degene die het schrijft. Als het af is bevat het programma een deel van de kennis en vaardigheid van de schrijver, en kan het een bepaalde taak uitvoeren zonder dat de schrijver er zich verder mee bemoeit. Het schaduw-idee wordt het beste geïllustreerd door de "expert-systemen", zoals Prospector en Internist. Dit zijn programma's waarin de kennis en ook de manier van denken van menselijke experts zijn vastgelegd. Prospector is een geologische expert; kort geleden voorspelde het programma nauwkeurig een vindplaats van molybdeen bij Mount Tolman in de Amerikaanse staat Wahington. Internist helpt artsen bij het stellen van een diagnose. De belangstelling voor expert-systemen neemt snel toe, omdat een computerprogramma op meerdere plaatsen aanwezig kan zijn (in verschillende computers) en daardoor de kennis van experts veel toegankelijker en bruikbaarder maakt. Niet dat menselijke experts overbodig worden, integendeel. Zonder hun hulp kan immers geen expert-systeem worden gemaakt. Computers kunnen zelf geen programma's schrijven. De grote kracht van computers is hun veelzijdigheid; dezelfde compuyer kan een medische diagnose stellen, maar ook een chemische fabriek besturen, of - als het gaat om een kleine "huiscomputer" - een redelijke partij schaak spelen, het huis bewaken tegen brand en inbraak, de kinder les geven in Frans, de boekhouding doen, of nog een onbeperkt aantal andere opdrachten uitvoeren. De mogelijkheden van een computer worden voornamelijk beperkt door de fantasie en de kennis van degene die hem instructies geeft. Maar zonder die instructies kan een computer totaal niets. Zonder programmaschrijver is er ook geen schaduw.
Of het moeilijk is, om een computer te vertellen wat hij moet doen? Dat is vooral afhankelijk van de taak die men het ding wil laten uitvoeren. De programma-schrijver hoeft in elk geval niets van elektronica te weten; het is zelfs niet nodig om te weten hoe een computer precies werkt! Kennis van een programmeertaal is voldoende.
NIM - het programma waar de wedstrijd om gaat - is geschreven in BASIC (Beginner's All-purpose Symbolic Instruction Code). BASIC is een "hogere" programmeertaal, die vooral op de gebruiker is gericht; de computer zelf begrijpt er niets van. Er is een vertaler nodig om een programma in BASIC voor de machine uitvoerbaar te maken. In de meeste kleine computers is dat een "BASIC-interpreter", een programma op zichzelf dat BASIC regel voor regel vertaalt in "machinetaal", de eigen taal van de computer. Er is een groot aantal BASIC-interpreters voor kleine computers op de markt. Daardoor bestaan er ook heel wat "BASIC-dialecten". Aangezien niemand zonder computer een programma kan schrijven, moeten deelnemers aan de wedstrijd kunnen beschikken over een machine waarvan de BASIC-interpreter NIM zonder al te veel aanpassingen kan verwerken (het programma is geschreven op de KIJK-computer, een CBM-3032 van Commodore). Natuurlijk heeft niet iedereen zoiets in huis, maar er valt allicht wat computertijd te lenen; school, leraren of vrienden en kennissen zijn voor de hand liggende bronnen. In de handboeken van de geleende computer is waarschijnlijk al het een en ander te vinden over programmeren in BASIC. Verder heeft elke goede technische boekhandel uitgebreide literatuur in voorraad. Door NIM in de computer in te voeren en met de boeken bij de hand wat met het programma te spelen zal het inzicht snel groeien, want BASIC is geen moeilijke taal. Tot slot volgt hieronder nog een overzicht van de belangrijkste in NIM toegepaste BASIC-instructies. Veel succes!
|
Hieronder de "listing" van het programma NIM.
Merk op dat het cijfer 0 wordt geschreven als Ø
(gebruikelijk in computertaal om de 0 en de letter o uit elkaar te houden),
behalve in regelnummers, waar de schuine streep is weggelaten
om ze van andere getallen te onderscheiden.
Door handig gebruik van subroutines en een slimmer systeem van beslissingen
voor de laatste zetten kan NIM (nu 1763 bytes) aanmerkelijk worden ingekort.
Zoals het nu is staan er zelfs instructies in, die zonder meer overbodig zijn.
Het laatste deel van het programma bestaat uit vier subroutines,
beginnend op de regels 580, 610, 740 en 780.
5 f=Ø 10 fory=1to6 20 forx=1toy:t(y,x)=1:nextx 30 nexty 40 v(1)=1:v(2)=2:v(3)=3:v(4)=4:v(5)=5:v(6)=6 50 iff=Øthen70 60 v(6)=1 70 gosub740:gosub780 80 iff=Øthen100 90 print"¯¯":print"is mijn eerste zet":f=Ø 100 print"¯":print"u bent aan de beurt¯" 110 input"rij";d:print"" 120 input"hoeveel over";b 130 ifv(d)<=bthenprint"¯ongeldige zet":goto100 140 v(d)=b:gosub580:gosub780 150 print"¯¯ik denk na" 160 b=Ø:fory=1to6:ifv(y)>Øthenb=b+1 170 nexty:ifb=1then410 180 fory=1to6:ifv(y)=1then200 190 nexty:goto510 200 forx=(y+1)to6:ifv(x)=1then250 210 nextx 220 b=Ø:fory=1to6:ifv(y)>Øthenb=b+1 230 nexty:ifb=2then440 240 goto510 250 b=Ø:fory=1to6:ifv(y)>Øthenb=b+1 260 nexty:ifb=2then450 270 fory=(x+1)to6:ifv(y)=1then330 280 nexty 290 b=Ø:forx=1to6:ifv(x)>Øthenb=b+1 300 nextx:ifb<>3then510 310 forx=1to6:ifv(x)>1thenv(x)=1:goto70 320 nextx 330 forx=(y+1)to6:ifv(x)=1then380 340 nextx 350 b=Ø:forx=1to6:ifv(x)>Øthenb=b+1 360 nextx:ifb<>4then510 370 forx=1to6:ifv(x)>1thenv(x)=Ø:goto70 375 nextx 380 b=Ø:forx=1to6:ifv(x)>Øthenb=b+1 390 nextx:ifb=5then310 400 goto510 410 fory=1to6:ifv(y)=1then460 420 nexty 430 fory=1to6:ifv(y)>1thenv(y)=1:goto490 435 nexty 440 fory=1to6:ifv(y)>1thenv(y)=Ø:goto490 445 nexty 450 fory=1to6:ifv(y)>1thenv(y)=Ø:goto490 455 nexty 460 print"¯¯":print"ik heb verloren¯":input"mag ik een revanche";a$ 470 ifa$="ja"thenf=1:goto10 480 end 490 gosub740:gosub780 500 print"¯¯":print"u hebt verloren!":end 510 gosub610:ifc=1then530 520 fory=1to6:ifv(y)>Øthenv(y)=v(y)-1:goto70 525 nexty 530 ford=1to6:z=v(d) 540 ifv(d)=Øthenv(d)=z:gosub580:nextd 550 v(d)=v(d)-1:gosub580 560 gosub610:ifc=1then540 570 goto70 580 forx=1tov(d):t(d,x)=1:nextx 590 forx=(v(d)+1)to6:t(d,x)=Ø:nextx 600 return 610 fory=1to6 620 ifv(y)=Øthenw=2ØØØ 630 ifv(y)=1thenw=2ØØ1 640 ifv(y)=2thenw=2Ø1Ø 650 ifv(y)=3thenw=2Ø11 660 ifv(y)=4thenw=21ØØ 670 ifv(y)=5thenw=21Ø1 680 ifv(y)=6thenw=211Ø 690 w$=str$(w):forx=3to5:w(y,x)=val(mid$(w$,x,1)):nextx:nexty 700 forx=3to5 710 b=w(1,x)+w(2,x)+w(3,x)+w(4,x)+w(5,x)+w(6,x) 720 c=b/2-int(b/2):ifc=Øthennextx:return 730 c=1:return 740 fory=1to6 750 forx=1tov(y):t(y,x)=1:nextx 760 forx=(v(y)+1)to6:t(y,x)=Ø:nextx 770 nexty:return 780 print" clr home ":print"rij" 790 fory=1to6:print"¯":printy;")",:ifv(y)=Øthennexty:return 800 forx=1tov(y):printt(y,x);:nextx 810 nexty:return Het stroomdiagram |
REGELNUMMERS
Een programma in BASIC is opgebouwd uit genummerde regels,
die elk een of meer instructies bevatten.
In de meeste versies van BASIC zijn meerdere instructies per regel mogelijk,
onderling gescheiden door een dubbele punt (:).
Regelnummers geven de volgorde aan waarin de instructies worden uitgevoerd.
De nummers hoeven niet opvolgend te zijn;
het is gebruikelijk om in tientallen te werken,
zodat men later nog regels kan tussenvoegen
(aan de nummers van NIM is te zien dat de schrijver hier en daar
een "next" was vergeten: 375 nextx, 525 nexty enz.)
GOTO
Komt de computer in een programma de goto-instructie tegen
(altijd gevolgd door een regelnummer),
dan wordt de uitvoering voortgezet op de aangegeven regel.
Een voorbeeld is regel 240 van NIM.
Na 240 wordt niet 250 uitgevoerd, maar 510.
GOSUB
Een subroutine is een klein programma op zichzelf,
dat door het hoofdprogramma meerdere malen wordt gebruikt
(zoals in NIM de subroutine beginnend op regel 780,
die de lucifers in beeld brengt).
Een subroutine wordt "opgeroepen" door de gosub-instructie:
Na "gosub 780" gaat de uitvoering verder op regel 780,
tot "return" wordt bereikt.
Daarna springt de uitvoering terug naar de instructie
volgend op de oproepende gosub.
Gebruik van subroutines maakt een programma korter en overzichelijker.
LET
De meeste BASIC-versies kennen numerieke en "string"-variabelen
bestaande uit een letter, twee letters of een letter gevolgd door een cijfer.
Een string-variabele wordt bovendien afgesloten met een $
(zoals in regel 470 van NIM).
Voor het toekennen van een bepaalde waarde aan een variabele
wordt de let-instructie gebruikt.
Voorbeelden: leta=b+4, letk2=2.75, leta$="hallo".
In veel BASICs mag het woordje "let" uit de instructie worden weggelaten,
zoals in NIM overal is gebeurd.
Was let verplicht, dan zou bijvoorbeeld regel 160 luiden:
letb=Ø:fory=1to6:ifv(y)>Øthenletb=b+1
INPUT
De input-instructie laat de computer om gegevens vragen;
de informatie wordt opgeslagen in een numerieke of string-variabele.
Voorbeelden: regel 110 input "rij";d
De computer vraagt "rij?" en variabele d verandert in het opgegeven cijfer.
Regel 460 . . .: input "mag ik een revanche";a$
De computer vraagt "mag ik een revanche?"
en het antwoord wordt opgeslagen in a$.
PRINT
De print-instructie laat de computer bepaalde gegevens zichtbaar maken.
Printy of printa$ brengt de inhoud van een variabele in beeld,
terwijl print"is mijn eerste zet" letterlijk "is mijn eerste zet" laat zien.
Print kan ook een uitvoerende waarde hebben:
zo geeft print2+4 het antwoord 6 in beeld.
LIJSTEN EN TABELLEN
BASIC kent speciale instructies voor het werken met lijsten en tabellen.
Zo maakt NIM gebruik van tabel t (zes rijen, zes kolommen)
voor opslag van de stelling;
y is het nummer van de rij, x geeft de kolom aan.
De lijst v - v(1) t/m v(6) - bevat de aantallen lucifers in elke rij.
Meestal moeten de afmetingen van een tabel of lijst
in de eerste regels van een programma worden gedefinieerd met de dim-instructie
(dimt(j,k) definieert de afmetingen van t als j bij k elementen).
Sommige BASIC-versies laten echter het gebruik van lijsten en tabellen
met een klein aantal elementen zonder definitie van de afmetingen toe.
Vandaar dat in NIM geen dim-instructie voorkomt.
FOR/NEXT
Wanneer een bepaalde bewerking meerdere malen achter elkaar
moet worden uitgevoerd, gebruikt met de instructie:
forx-atobstepz
bewerking (willekeurig aantal regels)
nextx
a en b zijn begin- en eindwaarden voor x.
Telkens als de computer de instructie "nextx" tegenkomt,
wordt z bij x opgeteld
en springt de uitvoering naar de eerste instructie na for/to/step.
Weglaten van step is gelijk aan de instructie "step 1"
(in NIM is de step dus overal 1).
Meerdere for/next "lussen" kunnen zich in een programma binnen elkaar bevinden
(zie NIM regel 10, 20, 30).
Verder kan de variabele uit for/next in de bewerking worden gebruikt
(wat in NIM overal gebeurt).
IF/THEN
Deze instructie laat de computer een beslissing nemen.
Een voorbeeld is regel 50 uit NIM: iff=Øthen70.
Alleen als f = Ø springt de uitvoering naar regel 70.
In alle andere gevallen wordt eerst regel 60 uitgevoerd.
Behalve = zijn er nog de tekens > (groter dan), < (kleiner dan),
<= (kleiner of gelijk aan), >= (groter of gelijk aan)
en <> (ongelijk aan).
Als de regel waarin "then" staat meer dan één instructie bevat,
worden alle instructies na then alleen uitgevoerd
als aan de voorwaarde is voldaan.
Bijvoorbeeld 310 forx=1to6:ifv(x) > 1thenv(x)=1:goto70.
Alleen als v(x) groter is dan 1 wordt v(x) gelijk gemaakt aan 1,
en springt de uitvoering naar regel 70.
CURSOR-INSTRUCTIES
De cursor is meestal een knipperend vierkantje op het beeldscherm,
dat aangeeft waar het eerstvolgende karakter wordt afgebeeld.
In NIM geeft print"¯" aan dat een regel moet worden overgeslagen
("¯¯" is twee regels overslaan).
clr home veegt het scherm schoon
en stuurt de cursor naar de home-positie linksboven.
END
Deze instructie geeft het eind van het programma aan.
Als het ook de laatste regel van het programma is,
mag "end" meestal worden weggelaten.
SPATIES
Het is gebruikelijk om in BASIC-regels geen spaties te gebruiken.
Sommige versies accepteren de spaties wel,
maar opslag kost extra geheugenruimte.
| 001 ¡ (1)
010 ¡ ¡ 011 ¡ ¡ ¡ 100 ¡ ¡ ¡ ¡ 101 ¡ ¡ ¡ ¡ ¡ 110 ¡ ¡ ¡ ¡ ¡ ¡ 333 |
001 ¡ (2)
010 ¡ ¡ 011 ¡ ¡ ¡ 100 ¡ ¡ ¡ ¡ 101 ¡ ¡ ¡ ¡ ¡ 001 ¡ 224 |
| 001 ¡ (3)
010 ¡ ¡ 001 ¡ 100 ¡ ¡ ¡ ¡ 101 ¡ ¡ ¡ ¡ ¡ 001 ¡ 214 |
001 ¡ (4)
000 001 ¡ 100 ¡ ¡ ¡ ¡ 101 ¡ ¡ ¡ ¡ ¡ 001 ¡ 204 |
| 001 ¡ (5)
000 001 ¡ 100 ¡ ¡ ¡ ¡ 010 ¡ ¡ 001 ¡ 113 |
001 ¡ (6)
000 001 ¡ 011 ¡ ¡ ¡ 010 ¡ ¡ 001 ¡ 024 |
| 001 ¡ (7)
000 001 ¡ 001 ¡ 010 ¡ ¡ 001 ¡ 014 |
001 ¡ (8)
000 001 ¡ 001 ¡ 001 ¡ 001 ¡ 005 |
De spelregels van hun lucifersspelletje NIM zijn simpel. Elk op hun beurt mogen de spelers uit één rij zoveel lucifers wegnemen als zij willen, met een minimum van één lucifer. Degene die de laatste lucifer moet pakken heeft verloren. De beginstelling (1) bestaat uit zes rijen met een oplopend aantal lucifers. De winnende strategie van het programma NIM is alsvolgt. Schrijf naast de rijen in een binair getal (opgebouwd uit de cijfers 0 en 1) hoeveel lucifers de rij bevat, en tel vervolgens de enen in de kolommen. In de beginstelling bevat elke kolom drie enen. Een juiste zet moet ervoor zorgen, dat het aantal enen in elke kolom even wordt; in de beginstelling kan dat alleen door uit de laatste rij vijf lucifers weg te nemen (2). De tegenstander maakt daarna onvermijdelijk een kolom oneven (3), waarna weer een juiste tegenzet kan volgen (4) enzovoort. Alleen in de laatste zetten loopt het mis. Zou NIM in (7) de kolommen even maken (door rij vijf leeg te maken), dan is verlies onvermijdelijk. NIM gebruikt een tamelijk onhandige structuur van beslissingen om in zo'n geval toch een oneven kolom over te laten. Verbeteren van dit systeem is een belangrijke sleutel tot het winnen van de wedstrijd.
WEDSTRIJDREGELS
Doel van de wedstrijd is het schrijven van het kortste programma
dat dezelfde taken uitvoert als NIM, dus:
Het programma geeft de tegenstander de eerste zet
en wint als de tegenstander een fout maakt.
Verliest het programma, dan vraagt het om een revanche,
waarbij het zelf de eerste zet doet en wint.
Ongeldige zetten mogen niet worden geaccepteerd,
en de presentatie op het beeldscherm moet gelijk zijn aan die van NIM.
Het programma moet "kaal" het kortste zijn;
de geheugenruimte die na de instructie "run" extra wordt ingenomen
voor de opslag van variabelen in niet belangrijk,
net zomin als de "denktijden" van het programma.
Programma's moeten geschreven zijn in
een van de voor micro-computers gebruikelijke BASIC-dialecten.
Deelnemers moeten hun programma's insturen vóór 1 november 1982.
WAT ER TE WINNEN VALT...
Boven: De prijs. De Sinclair ZX-81 microcomputer (spreekt BASIC),
een lichtnetadapter en twee handboeken.