søndag 18. desember 2011 Julekalender Polyglot Forth
Er du klar for noe veldig anderledes? Si hei til Forth, et stack-basert programmeringsspråk. Forth har røtter helt tilbake til 1958, men er fortsatt i bruk i dag. Og om du aldri kommer til å benytte et stack-basert språk i jobben din, vil det å lære Forth likevel gi deg verdifull kunnskap og alternative måter å tenke problemløsning på.
Til å begynne med var Forth det personlige programmeringsmiljøet til en fyr som heter Charles H. Moore. Først tidlig på 70-tallet fikk andre utviklere innblikk i hva Moore holdt på med. I løpet av en tiårsperiode ble språket portet til mange ulike platformer.
Charles skiftet ofte jobb, tok med seg Forth, og siden det var et lett språk å porte brukte han og andre det blant annet for å komme i gang med programmering for ny hardware: De første programmene som kjørte på Intel's 8086-chip i 1978 var skrevet i Forth, og MacFORTH var det første utviklingsmiljøet på den første Apple Machintosh'en i 1984.
I dag brukes Forth fortsatt til mye rart som for eksempel boot-loadere (som Open Firmware), i noen kritiske systemer hos NASA, og i andre "embedded"-systemer.
Forth kan sees på både som et programmeringsspråk og et operativsystem. Men det er ikke alt; det er også implementasjonen av en filosofi. Forth står for enkelthet! Språket har minimalt med syntaks, og det eneste du egentlig har å jobbe med er en LIFO-kø, altså en stack. Likevel er det ekstremt fleksibelt.
Jeg skal vise deg to ulike løsninger på Euler-problem nummer 1 – hvordan man finner summen av alle tall under 1000 som er multipler av 3 eller 5. I begge løsningene trenger jeg å kunne sjekke om et tall er et multippel av 3 eller 5, så vi begynner med å definere prosedyrer for det:
1 : multiple-of-3 dup 3 mod 0 = ; 2 : multiple-of-5 dup 5 mod 0 = ;
I Forth sier vi egentlig ikke prosedyrer – vi kaller det bare "ord". Ordet multiple-of-3 består av fem instruksjoner. Først dupliserer det det øverste elementet på stacken med ordet dup. Deretter putter det et 3-tall på stacken. Mod plukker så de to øverste elementene av stacken, og erstatter dem med modulo-verdien. Hvis det opprinnelige elementet på stacken f.eks. var tallet 6 vil stacken nå innholde 6 og 0.
Videre pusher multiple-of-3 tallet 0 på stacken, som nå vil inneholde 6, 0 og 0. Til slutt brukes "=" til å poppe de to øverste elementene, sjekke om de er like, og pushe resultatet (true) tilbake.
Det ble litt mye detaljer, men jeg håper du nå begynner å forstå prinsippet med hvordan Forth fungerer. Nå følger resten av løsningen. Syntaksen virker nok rar og uvandt, men i praksis er dette en loop fra 1 til 999, hvor hvert tall sjekkes og enten plusses på tallet på stacken eller droppes.
10 : euler1 11 0 \ Starting with a sum of 0 12 1000 1 ?do i \ Loop from 1 to 999 13 multiple-of-3 if \ if multiple of 3 14 + \ add to sum 15 else 16 multiple-of-5 if \ else if multiple of 5 17 + \ add to sum 18 else 19 drop \ else discard it 20 then 21 then 22 loop 23 . cr \ print sum and carriage return 24 ; 25 26 euler1 \ "call" euler1
Koden ser sikkert veldig baklengs ut. Det krever litt erfaring før du kan begynne å lese algoritmer som dette. Men jeg lover det kommer til å gi mening etterhvert om du jobber litt med det..
Det er vanskelig å forklare hvorfor, men å bruke en loop som i løsningen over føles litt som å jukse. Jeg lagde derfor også en rekursiv løsning på oppgaven. Den er litt mere komplisert, men illustrerer også flere aspekter ved stack-basert programmering.
Om du har problemer med å følge med på denne koden kan du scrolle litt ned og sammenligne med en identiske løsningen implementert i C#.
30 : next-is-zero dup 0 = ; 31 : keep-number dup ; 32 33 : keep-number-if-multiple-of-3-or-5 34 multiple-of-3 if 35 keep-number 36 else 37 multiple-of-5 if 38 keep-number 39 then 40 then 41 1- \ Decrement by one to prepare next number 42 ; 43 44 : generate-numbers 45 next-is-zero invert if 46 keep-number-if-multiple-of-3-or-5 47 recurse 48 then 49 ; 50 51 : sum-numbers \ Sums numbers until next number is 0 52 + 53 swap next-is-zero if drop else swap recurse then 54 ; 55 56 0 999 generate-numbers drop sum-numbers . cr ;
Denne algoritmen bygger først opp en stack med alle tallene som er delelige på 3 eller 5. Nedenfor ser du hvordan stacken bygger seg opp i løpet av de 16 første iterasjonene:
59 \ Stack dump from running generate-numbers: 60 <2> 0 999 61 <3> 0 999 998 62 <3> 0 999 997 63 <3> 0 999 996 64 <4> 0 999 996 995 65 <5> 0 999 996 995 994 66 <5> 0 999 996 995 993 67 <6> 0 999 996 995 993 992 68 <6> 0 999 996 995 993 991 69 <6> 0 999 996 995 993 990 70 <7> 0 999 996 995 993 990 989 71 <7> 0 999 996 995 993 990 988 72 <7> 0 999 996 995 993 990 987 73 <8> 0 999 996 995 993 990 987 986 74 <8> 0 999 996 995 993 990 987 985 75 <9> 0 999 996 995 993 990 987 985 984 76 osv...
Det første tallet i klammer på hver linje er antall elementer på stacken. Toppen av stacken er lengst til høyre.
Etter at alle tallene er samlet opp, brukes ordet sum-numbers til å "slå dem sammen". Her ser du hvordan stacken utvikler seg, og til slutt står igjen med svaret:
78 \ Stack dump from running sum-numbers: 79 <467> 20 18 15 12 10 9 6 5 3 80 <466> 21 20 18 15 12 10 9 6 8 81 <465> 24 21 20 18 15 12 10 9 14 82 <464> 25 24 21 20 18 15 12 10 23 83 <463> 27 25 24 21 20 18 15 12 33 84 <462> 30 27 25 24 21 20 18 15 45 85 ... 86 <7> 0 999 996 995 993 990 228195 87 <6> 0 999 996 995 993 229185 88 <5> 0 999 996 995 230178 89 <4> 0 999 996 231173 90 <3> 0 999 232169 91 <2> 0 233168
Som lovet følger til slutt samme løsning "oversatt" til C#. Kommentarene i koden viser hva koden mapper til i Forth:
10 using System; 11 using System.Collections.Generic; 12 13 namespace Euler1.RecursiveStackSolution 14 { 15 class Program 16 { 17 static Stack<int> stack = new Stack<int>(); 18 19 static bool MultipleOf3 { 20 get { 21 return stack.Peek() % 3 == 0; // dup 3 mod 0 = 22 } 23 } 24 25 static bool MultipleOf5 { 26 get { 27 return stack.Peek() % 5 == 0; // dup 5 mod 0 = 28 } 29 } 30 31 static bool NextIsZero { 32 get { 33 return stack.Peek() == 0; // dup 0 = 34 } 35 } 36 37 static void KeepNumber() { 38 stack.Push(stack.Peek()); // dup 39 } 40 41 static void KeepNumberIfMultipleOf3or5() { 42 if (MultipleOf3) // multiple-of-3 if 43 KeepNumber(); 44 else if ((MultipleOf5)) // multiple-of-5 if 45 KeepNumber(); 46 stack.Push(stack.Pop() - 1); // 1- 47 } 48 49 static void GenerateNumbers() { 50 if (!NextIsZero) { // next-is-zero invert if 51 KeepNumberIfMultipleOf3or5(); 52 GenerateNumbers(); 53 } 54 } 55 56 static void Swap() { // swap 57 int a = stack.Pop(); int b = stack.Pop(); 58 stack.Push(a); stack.Push(b); 59 } 60 61 static void SumNumbers() { 62 stack.Push(stack.Pop() + stack.Pop()); // + 63 Swap(); 64 if (NextIsZero) 65 stack.Pop(); // drop 66 else { 67 Swap(); 68 SumNumbers(); 69 } 70 } 71 72 static void Main() { 73 stack.Push(0); // 0 74 stack.Push(999); // 999 75 GenerateNumbers(); 76 stack.Pop(); // drop 77 SumNumbers(); 78 Console.WriteLine(stack.Pop()); // . cr 79 } 80 } 81 }
Som du ser blir det "mye mer syntaks" i C# for å få til det samme som jeg har gjort i Forth.
GForth er en open source-implementasjon av Forth. Last den ned! Så leser du online-boken Starting Forth. Resten kommer av seg selv!
Forth er anderledes, og lærer deg derfor nye måter å tenke på. Denne forklaringen på hvorfor du skal se på et bestemt språk begynner å bli en gjenganger nå.
I starten sa jeg at Forth representerer en filosofi. Denne filosofien er forklart i boken Thinking Forth (pdf her), publisert første gang i 1984. Det er verdt å lære seg Forth bare fordi det lar deg lese og forstå denne boken, som regnes som en klassiker blant bøker ment for utviklere.
Følgende utdrag (..mener jeg..) er hentet fra innledningen:
Our most essential tools and techniques are mental. We need a consistent and practical methodology for thinking about software problems. That is what I have tried to capture in this book. Thinking Forth is meant for anyone interested in writing software to solve problems. It focuses on design and implementation; deciding what you want to accomplish, designing the components of the system, and finally building the program.
The book stresses the importance of writing programs that not only work, but that are also readable, logical, and that express the best solution in the simplest terms.
I følge forfatteren korresponderer Forth-programmering bra med måten vi mennesker tenker på. Forth er enkelt, elegant og fleksibelt.