Du var kanskje ikke klar over det, men Common Lisp er et objektorientert språk. Det påstås faktisk at det har det kraftigste og mest fleksible objekt-systemet av alle språkene vi har, og gjennom å implementere Template Method pattern i Common Lisp håper jeg å gi deg en grei introduksjon til noen av språkets muligheter. Du vil også få se at multippel arv løser utfordringen jeg hadde med den klassiske implementasjonen i del 1.

Pass på at du har designet fra del 1 klart for deg når du ser på denne løsningen.. Og husk at parantesene ikke er farlige :D

(PS: Jeg ser bort fra diskusjonen om det faktisk er gyldig å kalle det jeg presenterer i denne serien for Template Method pattern – delta i debatten her.)

Først trenger jeg å lage selve templaten – noe som definerer skjelettet til algoritmen, men overlater detaljene til en konkret rapport-implementasjon. Templaten opprettes ikke i en klasse som i del 1 og del 2, men heller ikke som en høyereordens funksjon som jeg brukte i del 3. logReport er en prosedyre som tar et rapport-objekt som parameter, og typen av dette rapport-objektet vil avgjøre detaljene i loggfil-prosesseringen.

 2 (defun log-report (report)
 3   "A template for reporting from log files"
 4   (log-report-init report)
 5   (loop for line in (log-report-read report)
 6         do (log-report-process-line report line))
 7   (log-report-cleanup report))

Når jeg i den tredje linjen sier (log-report-init report) så er det det samme som å kalle metoden log-report-init på objektet report. Det neste jeg skal gjøre er å opprette disse metodene. Jeg bruker en makro som heter DEFGENERIC – du kan gjerne se på det som om jeg bruker dem til å opprette abstrakte metoder, slik jeg gjorde i LogProcessor i del 1. Metodene henger derimot ikke direkte på en klasse – klasser i Common Lisp har bare properties, mens metodene defineres for seg:

10 (defgeneric log-report-init (report))
11 (defgeneric log-report-read (report))
12 (defgeneric log-report-process-line (report line))
13 (defgeneric log-report-cleanup (report))

Så bruker jeg DEFMETHOD til å lage noen fornuftige default-implementasjoner av de abstrakte metodene. For initialisering og cleanup lager jeg bare noen tomme metoder, mens metoden som prosesserer en linje bare skriver den ut.

17 (defmethod log-report-init (report))
18 (defmethod log-report-process-line (report line)
19   (format t "~a~%" line))
20 (defmethod log-report-cleanup (report))

Jeg kan også lage en konkret variante av metoden som leser en fil, og jeg mocker fillesingen slik jeg har gjort i de andre delene i denne bloggserien:

28 ; Faking reading the file as usual..
29 (defmethod log-report-read (report)
30   (list "20120125180000000 DEBUG Tick!"
31   "20120125180100000 DEBUG Tick!"
32   "20120125180132112 ERROR Some error occurred"
33   "20120125180133056 ERROR Some other error..."
34   "20120125180200000 DEBUG Tick!"))

Nå kunne jeg ha kjørt koden ved å skrive for eksempel (log-report nil). Nil er nemlig også et objekt i Common Lisp – alt er objekter – og jeg har laget default implementasjoner av metodene som vil fungere for alle typer objekter! Alle linjene fra filen vil bli skrevet ut.

Opprette en klasse

Det er på tide å se hvordan man definerer en ny klasse. Jeg vil nå opprette en klasse for å rapportere errors fra loggfiler, sånn som jeg gjorde i del 1. Til det bruker jeg DEFCLASS:

36 (defclass error-report () ())

Klassen arver ikke fra noe spesielt, og den har ingen properties, så den ble ganske minimal. Men som du vil se er den viktig likevel.

Jeg kan nå opprette nye metoder for de stegene i algoritmen/templaten som er interessante for error-rapporten. Disse metodene vil bli brukt i tilfeller hvor report-objektet er en instans av error-report.

42 (defmethod log-report-init :before ((report error-report))
43   (format t "Errors:~%")) ; Printing a header..
44 
45 (defmethod log-report-process-line ((report error-report) line)
46   (let ((log-type (subseq line 18 23)))
47     (if (equal log-type "ERROR")
48       (format t "~a: ~a~%"
49         (subseq line 0 17)
50         (subseq line 24)))))

Metoden som prosesserer linjene vil erstatte default-implementasjonen, siden den ikke “kaller base/super” (i Common Lisp ville jeg gjort det ved å kalle en funksjon som heter CALL-NEXT-METHOD). Initialisering-metoden vil derimot bli lagt til i tillegg til eventuelt andre initialiseringsmetoder. I dette tilfellet skjer det fordi jeg har brukt :before-nøkkelordet. Before-metoder kaller i forkant av de virkelige metodene, og er bare en av mange måter man kan opprette metoder på.

Hvis jeg nå kjører koden (LOG-REPORT (MAKE-INSTANCE ‘ERROR-REPORT)) så vil den skrive ut headeren og error-linjene fra filen jeg har mocket.

En klasse for FTP-stegene

Nå oppretter jeg en ny klasse for FTP-stegene jeg trenger. Denne klassen arver heller ikke fra noen spesiell klasse, men inneholder én slot (property) for å holde på URLen til loggfilen.

58 (defclass ftp-report ()
59   ((url :initarg :url)))
60 
61 (defmethod log-report-init :before ((report ftp-report))
62   (format t "Fetching ~a~%" (slot-value report 'url)))
63 
64 (defmethod log-report-cleanup :after ((report ftp-report))
65   (format t "Deleting ~a~%" (slot-value report 'url))
66   (format t "Archiving local copy"))

Om jeg nå hadde evaluert (LOG-REPORT (MAKE-INSTANCE ‘FTP-REPORT :URL “some url..”)) ville metodene for å hente og slette FTP-loggen bli brukt, og default metoder for lesing og prosessering hadde også blitt brukt, slik at hele innholdet av filen hadde blitt vist. Men det er ikke det jeg er ute etter…

Multippel arv

Jeg skal nemlig nå lage en ny klasse som arver fra både error-report og ftp-report:

68 (defclass ftp-error-report (ftp-report error-report) ())

Når jeg oppretter en instans av denne klassen, og så kjører log-report, vil metodene for klassene som arves bli kombinert:

71 (log-report (make-instance 'ftp-error-report
72          :url "ftp://foobar.com/logs/my.log"))

Dette gir altså følgende output:

Fetching ftp://foobar.com/logs/my.log
Errors:
20120125180132112: Some error occurred
20120125180133056: Some other error...
Deleting ftp://foobar.com/logs/my.log
Deleting local copy as well

Et UML-diagram over denne modellen, om den hadde vært gjort i et mere klassisk OO-språk, ville sett ut som dette:

Konklusjon

Jeg har altså brukt multippel arv til å gjøre Template Method mindre rigid enn løsningen jeg kom opp med i C# i del 1; nå kan jeg kombinere de ulike klassene på ulike måter i stedet for å ha en fastlåst arverekkefølge. Dette gjør denne løsningen mer utvidbar.

Jeg har ikke jobbet mye med objektorientering i Common Lisp, men synes systemet med de generiske funksjonene som ikke er knyttet direkte til klassene er ganske elegant. Det er kanskje ikke lett å se hvor fleksibelt dette er uten å forsøke litt selv, spesielt ikke om man er vandt til typisk klasse-basert objektoerientering fra språk som C#, Java eller C++, men det finnes nok av folk som skryter hemningsløst av Common Lisp’s objektsystem. Dette er noe jeg må eksperimentere mer med.

Ønsker du en innføring i Common Lisp + objekter kan du ta en titt på Practical Common Lisp (online bok), kapittel 16 og 17.

I løpet av denne serien har du sett at et objektoerientert designpattern kan ha svært ulike implementasjoner. Et designpattern er ikke noe man kan pugge, og bare bruke igjen og igjen på samme måte. Man må tilpasse det omstendighetene, og hele tiden være klar over hvilke begrensninger det har. Jeg håper koden min har gitt deg noen ideer, og at du vil eksperimentere videre med hvordan du løser lignende problemer.

I del 1 og del 2 har du sett meg implementere Template Method pattern i C# – først i en tradisjonell, objektorientert variant, og så i en mere fleksibel variant inspirert av funksjonell programmering. Nå er det på tide å se hvordan det samme kan gjøre kun med funksjoner. Det er på tide å finne frem F#.

Først trenger vi selve templaten, eller algoritme-skjelettet om du vil. processLog er en funksjon som har fire andre funksjoner som parametre, og bruker disse til å prosessere loggfilen. En slik funksjon kalles en høyereordens funksjon.

10 let processLog init read processLine cleanup =
11     init()
12     for line in read() do
13         processLine line
14     cleanup()

Deretter oppretter jeg et par funksjoner for å finne og rapportere errors i loggfiler:

22 let errorInit() = printfn "Errors:"
23 
24 let errorLineProcessor line =
25     let m = Regex("^(\\d{17})\\s(\\w+)\\s(.+)$").Match(line)
26     if m.Success then
27         if m.Groups.Item(2).Value = "ERROR" then
28             printfn "%s: %s"
29                 (m.Groups.Item(1).Value)
30                 (m.Groups.Item(3).Value)

Det neste jeg trenger er FTP-stegene. Nedenfor oppretter jeg en funksjon som tar som innput en URL og returnerer to funksjoner – en for Initialize-steget i algoritmen og en for Cleanup-steget. Disse to funksjonene er lexical closures, fordi de har tilgang til URL-variabelen (mer om dette mange andre steder i bloggen).

33 (* Evaluates to a tuple of two closures *)
34 let makeFtpSteps url =
35     let setup = fun () -> printfn "Fetching log file from %s" url
36     let teardown = fun () ->
37         printfn "Archiving local log copy..."
38         printfn "Deleting log file %s" url
39     (setup, teardown)

Så kan jeg bruke funksjone jeg nettopp laget til å opprette de to closure’ene:

42 let (ftpFetch, ftpCleanup) =
43     makeFtpSteps "ftp://foobar.com/logs/my.log"

Å komponere funksjoner..

Jeg har nå to forskjellige funksjoner som skal kalles i Initialize-steget i templaten: ftpFetch og errorInit. I del 1 løste jeg dette ved at FTP-initialiseringsmetoden kalte baseklassens Initialize. I del 2 løste jeg det ved å ha en builder-klasse som kunne kombinere flere Action-delegater. Nå befinner jeg meg derimot i et funksjonelt språk, og da er det ingen sak å slå sammen to funksjoner til én:

48 (* Using forward composition operator to compose two functions *)
49 let errorInitWithFtpFetch = ftpFetch >> errorInit

errorInitWithFtpFetch er nå en ny funksjon som først evaluerer ftpFetch og deretter evaluerer errorInit. Om ftpFetch hadde hatt parametre ville den nye funksjonen også hatt det. Om ftpFetch hadde returnert noe, ville dette blitt sendt inn som argumenter til errorInit. Og om errorInit hadde hatt en returverdi så hadde dette vært returverdien til den nye metoden.

På tide å teste programmet

Da gjenstår det bare å mocke lesing av fil:

55 (* Faking it as usual... *)
56 let read() = [
57     "20120125180000000 DEBUG Tick!";
58     "20120125180100000 DEBUG Tick!";
59     "20120125180132112 ERROR Some error occurred";
60     "20120125180133056 ERROR Some other error...";
61     "20120125180200000 DEBUG Tick!"]

… og å kjøre selve programmet ved å kalle processLog-funksjonen med de riktige argumentene:

64 processLog
65     errorInitWithFtpFetch
66     read
67     errorLineProcessor
68     ftpCleanup

Output er identisk med løsningene fra del 1 og del 2.

Konklusjon

Løsningen jeg har kommet opp med her er betydelig enklere enn det du har sett før – her har vi ingen klasser som pakker inn koden og bestemmer hva vi kan og ikke kan gjøre. Løsningen er ekstremt fleksibel, og vil la meg kombinere funksjoner akkurat slik jeg ønsker. Objektene har vist seg å være helt overflødige – dette fordi Template Method i objektorientert design egentlig er et forsøk på å gjøre det samme som higher-order funksjons allerede gjør mye bedre.

Det eneste det kan se ut som om jeg har mistet er det å ha en LogProcessor-instans/objekt som jeg kan sende rundt og eksekvere når jeg måtte ønske. Men det løser vi selvsagt også lett. Å pakke inn et funksjonskall i en ny funksjon uten parametre slik som jeg gjør her kalles thunking:

71 (* Creating a thunk *)
72 let logProcessor() =
73     processLog
74         errorInitWithFtpFetch
75         read
76         errorLineProcessor
77         ftpCleanup
78 
79 (* Evaluating the thunk *)
80 logProcessor()

logProcessor er nå i prinsippet et objekt.

I del 4 vil jeg avslutte serien om Template Method ved å se på hvordan jeg kan bruke multippel arv til å gjøre en objektorientert implementasjon like fleksibel som som den løsningen du nå fikk se.

I del 1 så du et ganske typisk, objektorientert design som kalles Template Method. I denne oppfølgeren vil jeg forsøke å gjøre designet mer fleksibelt uten å miste det jeg ønsket å oppnå – nemlig å definere skjelettet til algoritmen kun én gang.

Om du ikke har lest gjennom del 1 allerede bør du gjøre det først..

Fra abstrakt til konkret

Den første endringen jeg gjør er å endre LogProcessor fra å være en abstrakt klasse til å bli en konkret klasse jeg kan opprette instanser av. C# har noen delegat-typer som heter Action og Func, og jeg bytter du de abstrakte metodene i LogProcessor med private felt av tilsvarende delegattype. Til slutt legger jeg til en konstruktør som lar meg opprette LogProcessor med alle de manglende bitene til templaten:

 10 public class LogProcessor
 11 {
 12     public void Execute()
 13     {
 14         Initialize();
 15         IEnumerable<string> log = ReadLog();
 16         foreach (var line in log)
 17             ProcessLine(line);
 18         Cleanup();
 19     }
 20 
 21     private readonly Action Initialize;
 22     private readonly Func<IEnumerable<string>> ReadLog;
 23     private readonly Action<string> ProcessLine;
 24     private readonly Action Cleanup;
 25 
 26     public LogProcessor(
 27         Action initializer,
 28         Func<IEnumerable<string>> logReader,
 29         Action<string> lineProcessor,
 30         Action cleanuper)
 31     {
 32         Initialize = initializer;
 33         ReadLog = logReader;
 34         ProcessLine = lineProcessor;
 35         Cleanup = cleanuper;
 36     }
 37 }

Builder Pattern

For å gjøre det enklere å opprette en fornuftig LogProcessor har jeg så brukt et annet pattern som kalles Builder: LogProcessorBuilder er en klasse som steg-for-steg lar meg definere hvordan en LogProcessor skal fungere.

Studer Initialize-propertien nøye – den gav flere personer en aha-opplevelse under NNUG-foredraget mitt som koden er hentet fra. Her gjør jeg det mulig å sette propertien flere ganger, noe som vil føre til at Action-delegatene vil bli kombinert. Jeg burde gjort det samme for de andre propertiene også, men lar være for å spare litt plass.

 39 // More pattern fun: Adding a Builder
 40 public class LogProcessorBuilder
 41 {
 42     private Action _Initialize;
 43     public Action Initialize
 44     {
 45         get
 46         {
 47             return _Initialize;
 48         }
 49         set
 50         {
 51             if (_Initialize != null)
 52             {
 53                 var temp = _Initialize;
 54                 _Initialize = () =>
 55                 {
 56                     value.Invoke();
 57                     temp.Invoke();
 58                 };
 59             }
 60             else
 61                 _Initialize = value;
 62         }
 63     }
 64 
 65     public Func<IEnumerable<string>> ReadLog { get; set; }
 66     public Action<string> ProcessLine { get; set; }
 67     public Action Cleanup { get; set; }
 68 
 69     public LogProcessor GetProcessor()
 70     {
 71         if (   Initialize  == null
 72             || ReadLog     == null
 73             || ProcessLine == null
 74             || Cleanup     == null)
 75             throw new Exception("Some step has not been defined!");
 76 
 77         return new LogProcessor(
 78             initializer: Initialize,
 79             logReader: ReadLog,
 80             lineProcessor: ProcessLine,
 81             cleanuper: Cleanup);
 82     }
 83 }

Utfylling av templaten

Selve programmet nedenfor består av tre metoder. Den første tar en LogProcessorBuilder og legger til funksjonaliteten for å rapportere errors fra loggfilen. Den neste legger til funksjonaliteten for FTP-overføringene. Selve Main-metoden oppretter en builder, kaller de to foregående metodene for å klargjøre templaten, oppretter LogProcessor-instansen, og utfører.

 85 class Program
 86 {
 87     static void SetErrorReporting(LogProcessorBuilder processor)
 88     {
 89         processor.Initialize = () => Console.WriteLine("Errors:");
 90 
 91         processor.ProcessLine = line =>
 92         {
 93             var regex = new Regex("^(\\d{17})\\s(\\w+)\\s(.+)$");
 94             var match = regex.Match(line);
 95             if (match.Success && match.Groups[2].Value == "ERROR")
 96             {
 97                 Console.WriteLine("{0}: {1}",
 98                     match.Groups[1].Value,
 99                     match.Groups[3].Value);
100             }
101         };
102     }
103 
104     static void AddFtpReportingSteps(LogProcessorBuilder processor,
105                                         string url)
106     {
107         processor.Initialize = () =>
108         {
109             Console.WriteLine("Fetching log file from {0}", url);
110         };
111 
112         processor.Cleanup = () =>
113         {
114             Console.WriteLine("Archiving local log copy...");
115             Console.WriteLine("Deleting log file on {0}", url);
116         };
117     }
118 
119     static void Main(string[] args)
120     {
121         var builder = new LogProcessorBuilder();
122         SetErrorReporting(builder);
123         AddFtpReportingSteps(builder, "ftp://foobar.com/logs/my.log");
124 
125         // faking out log reading
126         builder.ReadLog = () => new[] {
127                 "20120125180000000 DEBUG Tick!",
128                 "20120125180100000 DEBUG Tick!",
129                 "20120125180132112 ERROR Some error occurred",
130                 "20120125180133056 ERROR Some other error...",
131                 "20120125180200000 DEBUG Tick!",
132             };
133 
134         builder.GetProcessor().Execute();
135 
136         Console.ReadLine();
137     }
138 }

Konklusjon for del 2

Dette er fortsatt Template Method pattern, men designet er ikke lenger så rigid. Bruk av Action og Func lar meg legge til funksjonalitet i LogProcessor uten å måtte arve eller definere konkrete typer for denne funksjonaliteten. Jeg sender i prinsippet funksjoner til LogProcessor, som den så kan bruke når den skal prosessere loggfilen. Dermed kan jeg enkelt definere nye LogProcessor-instanser med kun små endringer i funksjonalitet – blande stegene fritt, uten at antall klasser i løsningen eksploderer. Og designet er fortsatt ganske rent, ryddig og forståelig.

Det jeg har gjort er å tenke som en funksjonell programmerer, og i del 3 vil jeg ta steget fullt ut og implementere en løsning i F# som kun baserer seg på funksjoner.

I foredraget mitt på NNUG Bergen i januar tok jeg for meg noen utvalgte design patterns, viste noen objektorienterte eksempelimplementasjoner i C#, for så å sammenligne dette med tilsvarende løsninger i F# hvor jeg kun brukte funksjoner. Dette er første blogpost i en serie på fire hvor jeg vil gå gjennom ett av mønstrene jeg brukte – nemlig Template Method design pattern.

(Koden er noe endret i forhold til det som ble vist i foredraget.)

I denne første blogposten vil jeg vise en typisk løsning implementert i C# – designet er slik du ofte finner det i statisk typede språk. I del 2 vil jeg gjøre visse endringer i C#-løsningen for å vise hvordan jeg kan gjøre designet mere fleksibelt ved å bevege meg mot en funksjonell tankegang.

I del 3 vil du få se min F#-løsning. Da vil du forhåpentligvis se hvor mye enklere og mere fleksibel koden blir når man dropper de tyngste abstraksjonene og bare bruker funksjoner. I den siste delen vil jeg vise en implementasjon i Common Lisps fleksible objektsystem, hvor jeg blant annet vil utnytte multippel arv.

Poenget her er altså å studere ulike måter å løse et problem rent designmessig – og hvordan ulike programmeringsspråk tilbyr ulike hjelpemidler.

En “klassisk” løsning

Problemet jeg skal modellere ved hjelp av Template Method pattern dreier seg om prosessering av loggfiler. Template Method er en mønster hvor man definerer skjelettet til en algoritme, men gir andre (sub-klasser) mulighet til å definere eller endre enkelte av stegene i algoritmen. Jeg har identifisert at jeg alltid prosesserer loggfiler omtrent på samme måte, men at enkelte av stegene endrer seg fra gang til gang. Template Method er altså en god kandidat å bruke her.

Nedenfor ser du koden som definerer selve templaten. Det er en abstrakt klasse, hvor definisjonen av detaljene i hvert steg av algoritmen er overlatt til en fremtidig, konkret implementasjon:

 10 public abstract class LogProcessor
 11 {
 12     public void Execute()
 13     {
 14         Initialize();
 15         IEnumerable<string> log = ReadLog();
 16         foreach (var line in log)
 17             ProcessLine(line);
 18         Cleanup();
 19     }
 20 
 21     protected abstract void Initialize();
 22     protected abstract IEnumerable<string> ReadLog();
 23     protected abstract void ProcessLine(string line);
 24     protected abstract void Cleanup();
 25 }

Hvis jeg så har behov for å f.eks. skrive ut alle linjene i en loggfil som inneholder feilmeldinger så kan jeg lage en ErrorReporter som arver fra LogProcessor-templaten min:

 30 public class ErrorReporter : LogProcessor
 31 {
 32     protected override void Initialize()
 33     {
 34         Console.WriteLine("Errors:"); // just a header for the report
 35     }
 36 
 37     protected override IEnumerable<string> ReadLog()
 38     {
 39         // Simulating reading a file:
 40         yield return "20120125180000000 DEBUG Tick!";
 41         yield return "20120125180100000 DEBUG Tick!";
 42         yield return "20120125180132112 ERROR Some error occurred";
 43         yield return "20120125180133056 ERROR Some other error...";
 44         yield return "20120125180200000 DEBUG Tick!";
 45     }
 46 
 47     protected override void ProcessLine(string line)
 48     {
 49         var regex = new Regex("^(\\d{17})\\s(\\w+)\\s(.+)$");
 50         var match = regex.Match(line);
 51         if (match.Success && match.Groups[2].Value == "ERROR")
 52         {
 53             Console.WriteLine("{0}: {1}",
 54                 match.Groups[1].Value,
 55                 match.Groups[3].Value);
 56         }
 57     }
 58 
 59     protected override void Cleanup() // No cleanup needed
 60     {
 61     }
 62 }

Som du ser gjør jeg eksempelet litt enklere ved å lure meg unna selve lesingen av loggfilen.

ErrorReport-klassen kan brukes direkte, men i tillegg ønsker jeg at programmet mitt skal hente loggfilen fra en FTP-server når rapporten skal kjøres. Når jeg er ferdig skal filen arkiveres, og filen på FTP-serveren skal slettes. Derfor lager jeg et nytt nivå – en klasse som arver fra ErrorReport, som re-definerer Initialize- og Cleanup-stegene:

 66 public class FtpErrorReporter : ErrorReporter
 67 {
 68     private readonly string _url;
 69     public FtpErrorReporter(string url)
 70     {
 71         _url = url;
 72     }
 73 
 74     protected override void Initialize()
 75     {
 76         Console.WriteLine("Fetching log file from {0}", _url);
 77         base.Initialize();
 78     }
 79 
 80     protected override void Cleanup()
 81     {
 82         base.Cleanup();
 83         Console.WriteLine("Archiving local log copy...");
 84         Console.WriteLine("Deleting log file on {0}", _url);
 85     }
 86 }

Designet jeg har laget ser altså ut som dette:

Med følgende program kan jeg teste ut koden min:

 90 public class Program
 91 {
 92     public static void Main()
 93     {
 94         LogProcessor errorReporter =
 95             new FtpErrorReporter("ftp://foobar.com/logs/my.log");
 96 
 97         errorReporter.Execute();
 98     }
 99 }

Og output ser slik ut:

Fetching log file from ftp://foobar.com/logs/my.log
Errors:
20120125180132112: Some error occurred
20120125180133056: Some other error...
Archiving local log copy...
Deleting log file on ftp://foobar.com/logs/my.log

En foreløpig konklusjon

Designet jeg har valgt løser oppgaven på en tilsynelatende grei måte. De tre klassene har fått hvert sitt tydelig definerte ansvarsområde: LogProcessor definerer en generell algoritme som kan gjenbrukes. ErrorReporter definerer hvordan jeg finner feilene i loggfilen og skriver dem ut. FtpErrorReporter håndterer henting og sletting av loggfiler over FTP.

Dette er altså del 1 i min behandling av Template Method, og er som en introduksjon å regne. Men det er allerede nå verdt å legge merke til at at template method har gjort designet mitt ganske så regid. Hva må jeg f.eks. gjøre om jeg vil rapportere på andre ting enn errors, men fortsatt hente filene over FTP? Skal jeg følge designet må jeg opprette to nye klasser, hvor den ene stort sett vil være en kopi av FtpErrorReporter. Det er ikke bra! Jeg står heller ikke fritt til å gjenbruke bare deler av enten ErrorReporter eller FtpErrorReporter.

I del 2 vil du få se hva jeg kan gjøre med dette.

Prolog er et såkalt logisk programmeringsspråk. Jeg snakket om det nylig i posten Hvem bor hvor?. Mens man i nord-amerika først og fremst tenker på Lisp når man snakker om kunstig intelligens og implementasjon av lingvistiske løsninger, bruker man i Europa og andre steder oftere nettopp Prolog.

Prolog er deklerativt: Et program er et sett med relasjoner representert gjennom regler og fakta. Å kjøre et prolog-program er å kjøre spørringer mot disse relasjonene. Språket er som en ultra-smart fyr som kan finne alle logiske slutninger basert på det du forteller den.

Da det ble implementert tidlig på 70-tallet var Prolog et av de aller første logiske programmeringsspråkene, og det er fortsatt et av de mest populære. Det finnes en rekke implementasjoner, og språket er flittig brukt innen forskning og utdanning.

Til å begynne med trodde mange at Prolog kom til å få stor utbredelse, og at det var et steg i retning av en helt ny type programmeringsspråk. Men utenfor forskningsmiljøene – i industrien forøvrig – har Prolog og logisk programmering hatt liten gjennomslagskraft.

Den eneste språket som “minner om” Prolog, som de fleste utviklere har et tett forhold til, og som også ble skapt tidlig på 70-taller, er SQL.

En Prolog-intro

Vi vil begynne med å definere en slektsdatabase i Prolog. Først deklarerer vi noen fakta: Adam er en mann, Peter er en mann, osv..

27 man(adam).
28 man(peter).
29 man(paul).
30 
31 woman(marry).
32 woman(eve).

Så kan vi legge til noen relasjoner:

34 parent(adam,peter). % means adam is parent of peter
35 parent(eve,peter).
36 parent(adam,paul).
37 parent(marry,paul).

Relasjonene var også fakta, men nå er det på tide med noen regler. Følgende regler bruker de definerte faktaene til å si hva det innebærer å vare en far eller mor:

39 father(F,C) :- man(F),   parent(F,C).
40 mother(M,C) :- woman(M), parent(M,C).

F, C og M er variabler – alt som begynner med stor bokstav er variabler i Prolog. En far (F) må altså både være en mann og forelder til sitt barn (C).

Nå kan vi bruke det vi har definert til å spørre Prolog hvem som er faren til Paul:

?-father(X,paul).

Prolog vil svare X = adam.

Videre kan vi definere regler for andre familierelasjoner:

44 son(S,P)      :- man(S),   parent(P,S).
45 daughter(D,P) :- woman(D), parent(P,D).
46 
47 siblings(A,B) :- parent(P,A), parent(P,B), A\=B.
48     % siblings have at least one common parent
49     % the test A\=B ensures siblings are different persons
50 
51 uncle(U,N) :- man(U),   siblings(U,P), parent(P,N).
52 aunt(A,N)  :- woman(A), siblings(A,P), parent(P,N).
53 
54 grand_parent(G,N) :- parent(G,X), parent(X,N).

Det var en smakebit. Nå skal vi se noe litt mere avansert..

Euler1 i Prolog

Euler-oppgaven jeg løser i denne julekalenderen er ikke en typisk oppgave for Prolog – i alle fall ikke så langt jeg kan se. Jeg er kun en nybegynner i dette språket. Men jeg måtte nesten lage en løsning likevel, og med litt hjelp har jeg kommet frem til en løsning.

10 interesting_number(N) :- N rem 3 =:= 0.
11 interesting_number(N) :- N rem 5 =:= 0.
12 
13 euler1(0, 0) :- true, !.
14 euler1(N, Answer) :-
15     N > 0, interesting_number(N),
16     Next is N-1,
17     euler1(Next, SubAnswer),
18     Answer is SubAnswer + N, !.
19 euler1(N, Answer) :-
20     N > 0,
21     Next is N-1,
22     euler1(Next, Answer).

I de to første linjene beskriver jeg regelen for hvilke numre jeg er interessert i: de som er delelige på 3 og de som er delelige på 5. Den neste tre-delte regelen er rekursiv, og hakket for kompleks til at jeg forsøker meg på en beskrivelse her og nå.

Det finnes som sagt en rekke implementasjoner av Prolog, og mange støtter ulike ekstra-funksjoner som filter og reduce, slik at oppgaven i praksis kan løses omtrent som i et hvilket som helst annet språk. Løsningen over er derimot en minimal løsning i “ren” Prolog.

Hvorfor bruke tid på Prolog, og hva er alternativet?

Logisk programmering er en veldig interessant løsningsmodell, og utviklere bør kjenne til muligheten. Når det dukker opp et problem som egner seg for dette, vil det være fordelaktig å ha litt erfaring.

Nok en gang er det også et språk som vil lære deg nye måter å tenke på, og vil kunne gi deg ideer du kan dra nytte av i mere konvensjonelle språk.

Men det kan kanskje være urealistisk å lære seg en ny plattform og et litt sært språk for noe man kun skjelden har bruk for. Heldigvis kan man ved hjelp av bibloteker benytte logisk programmering i mange andre språk også. I prinsippet har man som regel da en komponent som implementerer en slags Prolog for den plattformen man jobber på, og et API for å deklerativt angi fakta og regler – i en syntaks man er kjent med.

Eksempler på dette er core.logic i Clojure, og ruby-prolog, en Prolog-lignende DSL for Ruby. De kan være litt vanskelige å finne!

Ellers finner du også støtte for logisk programmering i Oz. Og programmeringsspråket Mercury er en slags moderne arvtager av Prolog, som også støtter funksjonell programmering inspirert av Haskell.

Hvordan komme igang

Jeg startet med GNU Prolog. Et kanskje enda bedre alternativ er SWI Prolog, som har støtte for multi-threading, http request/response, og har et rikere støttebiblotek. Begge er open source og tilgjengelige for Windows, Mac og Unix.

Og så er det viktig å finne en god læringsressurs. LearnPrologNow.org er én mulighet. Sjekk også ut Prolog in Examples.

Ellers er det en bok jeg har hatt lyst til å lese en stund, og det er The Reasoned Schemer. Den  handler ikke om Prolog direkte, men om hvordan man utvider Scheme (en Lisp) til å støtte logisk programmering. Boken vil gi deg en dyp forståelse for sammenhengen mellom funksjonell og logisk programmering.

Dagens programmeringsspråk heter rett og slett D. Og det er jo et greit navn på et språk som blant annet kan erstatte C. Egentlig er det vel mest sammenlignbart med C++, men D har også latt seg påvirke av språk som Java og C#, og dynamiske språk som Python og Ruby.

D forsøker å kombinere ytelsen til C++, sikkerheten og minnehåndteringen i de mest moderne, kompilerte språkene, og de dynamiske språkenes evne til å la utvikleren uttrykke seg så enkelt og effektivt som mulig.

Effektivitet, enkelhet og kraft

D kompileres til effektiv maskinkode. Ideomatisk D-kode er både rask og sikker. Men utvikleren har mulighet til å “sku av” typesikkerhet, og bruke pekere, direkte tilgang til C-funksjoner, og til og med inline assembly, om han ønsker det.

D lar deg skrive ganske mye kode uten unødvendige typedeklarasjoner – kompilatoren finner ut av det. Språket har også god og fleksibel, automatisk minnehåndtering.

Dessuten støtter språket “de fleste” programmeringsparadigmene, og har god samtidighets-støtte. Noen stikkord som bør være kjente for dem som leser denne bloggen er immutable state og message passing. D tillater ikke deling av state på tvers av tråder “by default”, men tilbyr kontrollert deling av data som kan endres (mutable state) når det er påkrevd. Her skiller altså D seg kraftig ut fra de fleste andre, imperative språkene.

Hvem D er laget for

D er laget for utviklere som ikke trives med objektorienteringen i C++ fordi den er for kompleks. D er laget for utviklere som liker kraften i C++, men som er frustrerte over å måtte bruke det meste av tiden sin på eksplisitt minnehåndtering og på å lete etter pointer-bugs.

D er også laget for utviklere som programmerer én del av løsningene sine i skripspråk som Python eller Ruby, og en annen del i C++. D kombinerer mange av styrkene fra begge sider, og gjør at du kan holde deg i ett språk.

Og sist men ikke minst: D er et praktisk språk. Det er laget for å få jobben gjort.

Litt kode

Syntaksen i D ser stort sett ut som C/C++. Løsningen av euler-oppgave nummer 1 inneholder derfor ingen overraskelser:

10 import std.stdio;
11 
12 bool includeNumber(int x)
13 {
14   return x % 3 == 0 || x % 5 == 0;
15 }
16 
17 void main()
18 {
19   int sum = 0;
20   for (int i = 0; i < 1000; i++)
21     if(includeNumber(i))
22       sum += i;
23   writeln(sum);
24 }

Vil du se mer D-kode er jeg redd du må ta turen til d-programming-language.org.

Noen flere detaljer

Merk at D ikke er bakoverkompatibelt med C. D har heller ingen preprosessor, og støtter ikke multippel arv. D støtter derimot templates, men disse skal være enklere å bruke enn varianten man finner i C++ (jeg kan ikke nok C++ til å uttale meg om dette selv).

D støtter også kodekontrakter / Design By Contract, som beskrevet i artikkelen om språket Cobra. Og det har innebygde muligheter for enhetstester.

En liten detalj med D som jeg virkelig setter pris på er at alle metoder er virtuelle. Jeg har alltid sagt at C# burde ha virtuelle metoder by default, men D har tatt det enda lengre. Torbjørn liker dette!

Konklusjon

Av og til kan det virke som om C og C++ har et absolutt monopol på visse områder. Da er det interessant når det kommer et språk som forsøker å erstatte og overgå dem. Selv om utbredelsen foreløpig er begrenset har jeg stor tro på D.

Ta turen innom www.d-programming-language.org – en behagelig side med mye informasjon – og bli inspirert du også!

I tilfelle du ikke synes det er nok med én blogpost hver dag har jeg her en knøttliten bonus til deg. Jeg har jo nå vist deg Euler 1 løst på forskjellige måter i et utall språk. Blant annet har jeg vist hvordan oppgaven kan løses ved hjelp av pattern matching – dette gjorde jeg i F# og i Nemerle, og Kråkelefse delte også en lignende løsning i Haskell.

Når jeg da nylig kom over et matching-biblotek for Clojure måtte jeg nesten teste denne muligheten ut også i det språket. Måtte leke meg litt. Man kan trygt si at multiplene av 3 og 5 har gjort meg litt ensporet. Anyways, here goes…

10 (ns euler1CljMatch.core
11     (:use [clojure.core.match :only [match]]))
12 
13 (let [mod-zero? #(zero? (mod %2 %1))]
14   (def mod-zero-3? (partial mod-zero? 3))
15   (def mod-zero-5? (partial mod-zero? 5)))
16 
17 (defn mult3or5? [x]
18   (match [x]
19     [(_ :when mod-zero-3?)] true
20     [(_ :when mod-zero-5?)] true
21     :else                   false))
22 
23 (defn euler-1 []
24   (loop [n 0, sum 0]
25     (match [n]
26       [ 1000 ]              sum
27       [(_ :when mult3or5?)] (recur (inc n) (+ sum n))
28       [ _    ]              (recur (inc n)    sum))))
29 
30 (println (euler-1))

Det er langt fra optimalt å bruke match til dette her, og det illustrerer heller ikke hva pattern matching er godt for. Men jeg måtte bare få det ut! Viktig å test nye muligheter.

For ordens skyld: I slike situasjoner (som det jeg har rotet meg opp i ved å forsøke å bruke match) foretrekker Lisp’ere å bruke en makro som heter cond. I dette tilfellet gir det mye renere syntaks:

17 (defn mult3or5? [x]
18   (cond (mod-zero-3? x) true
19         (mod-zero-5? x) true
20         :else           false))
21 
22 (defn euler-1 []
23   (loop [n 0, sum 0]
24     (cond (= n 1000)    sum
25           (mult3or5? n) (recur (inc n) (+ sum n))
26           :else         (recur (inc n)    sum))))

Og så var det fire dager igjen til Jul :D

I 1993 satte Chris Pressey seg som mål å lage et programmeringsspråk som var vanskeligere å kompilere enn alle andre språk. Resultatet ble Befunge, et språk du aldri har sett maken til. Om du finner et praktisk bruksområde for Befunge så er du god, men språket er uansett underholdende, og stimulerer hjernen til å tenke tanker du aldri har hatt før.

Gjør deg klar for litt orntlig trylling med tekst!

Befunge skiller seg klart fra alle konvensjonelle språk. Som Forth og Factor er det et stack-basert, men måten man skriver programmer på i Befunge er helt anderledes.

Et Befunge-program er et todimensjonalt grid. Alle kommandoer er representert ved ett tegn. Program-counteren starter på kommandoen øverst til venstre i kildefilen, og så beveger den seg normalt ett og ett tegn mot høyre. Men man kan bruke spesielle kommandoer for å endre retningen, og programmet vil i praksis bevege seg på kryss og tvers i 2D-verdenen som kildekoden representerer.

La det synke inn litt… Et program i et tradisjonelt programmeringsspråk er en sekvens med instruksjoner. Man kan hoppe fra sted til sted – f.eks. ved hjelp av metodekall – men i metodene er det igjen en vanlig sekvens med instruksjoner. I Befunge kan programmet bevege seg til høyre, til venstre, oppover og nedover. Instruksjonspekeren kan til og med gå ut over en av kantene i kildekoden, og dukke opp igjen på den motsatte siden!

Euler-oppgave 1

Jepp, du har sett det før: en algoritme for å finne summen av alle multipler av 3 eller 5 mindre enn 1000.

 1  9872***9- v    Euler Problem #1
 2        >   v
 3            :                   >\         v
 4            !
 5            _   v               |  :  \+   <$
 6                :
 7        -       3
 8        1       %               $
 9                !               .
10        ^  \:<  _  v            @
11                   :
12                   5
13                   %
14                   !
15             ^     _     v
16        ^                <  - By Torbjørn Marø

Ahhhhhh, what a rush!! Det var kanskje den kjekkeste koden jeg har skrevet til denne julekalenderen. Jeg utfordrer deg til å forsøke selv, for dette er både stimulerende hjernetrim og underholdende morro.

Når du har begynt å tenke stack-basert, og vært innom andre ett-tegn-baserte språk som Betterave, så er løsningen egentlig ganske “rett frem”. Det mest utfordrende er å holde orden på koden, å strukturere den riktig og godt.

Nedenfor har jeg forsøkt å forklare programmet gjennom et diagram. Diagrammet speiler strukturen i koden – sammenligner du dem så vil du begynne å se det.

Har du noengang spilt et spill hvor du må plassere objekter i et rom får å få en laserstråle eller en ball til å lyse/sprette fra start til mål? Befunge er mye av det samme. Du kan også sammenligne det med workflow-baserte systemer; jeg ser på Befunge som en enkel ASCII-basert versjon av Windows Workflow Foundation eller tilsvarende prosessdesigner-verktøy, bare med et litt begrenset sett med byggeklosser.

Algoritmen jeg har brukt er forresten den samme som den rekursive algoritmen jeg løste oppgaven med i Forth. Men i Befunge har jeg laget en visuell utgave. Med litt fantasi kan jeg se for meg hvordan programmet kjører rundt i koden og bygger opp stacken, før den slår alle tallene sammen og skriver ut svaret.

Hvordan komme igang

Esolangs-wikien gir deg en god introduksjon til språket og alle kommandoene du kan benytte. Det finnes en rekke tolkere til Befunge, skrevet i blant annet Python, JavaScript og Java. Selv har jeg brukt en kompilator skrevet i C, men jeg klarer av en eller annen grunn ikke å finne eller huske hvor jeg fikk den fra. Men om noen er interessert i den kan jeg gjøre koden tilgjengelig.

Forth var et spennende og anderledes språk – men det er forferdelig gammelt, og virker ikke spesielt praktisk til større og mer komplekse oppgaver. Factor er den moderne arvtageren til Forth; et stack-basert programmeringsspråk med et rikt biblotek, ulike datatyper og til og med objekter, makroer, databasedrivere, et GUI-rammeverk, og med mulighet for å kommunisere med programmer skrevet i C, Objective-C og Fortran.

Forth var en søt liten filosof som kunne lære deg noe grunnleggende om problemløsning. Factor er en orntlig kraftkar som kan løse de utfordringene du har i den virkelige verden!

Utviklingsmiljøet

Factor er på samme måte som Smalltalk et image-basert språk og utviklingsmiljø. Når man starter det opp får man et vindu hvor man interaktivt kan skrive kode, inspisere datastacken, osv. Miljøet har ulike måter å hjelpe utvikleren, og inkluderer blant annet en hyperlink-basert browser hvor man kan studere biblotekene man har til rådighet, og lære Factor gjennom ulike tutorials.

I skjermbildet nedenfor ser du hovedvinduet til venstre, hvor jeg har laget en ny definisjon og testet den. Vinduet jeg har åpnet til høyre er hjelpe-browseren.

Jeg ble ganske imponert av miljøet egentlig. Det er noe helt annet enn IDE’ene jeg er vandt til, men virker perfekt for oppgaven.

Litt kode

Nå skal vi løse oppgaven vår igjen: finne summen av alle multipler av 3 eller 5 som er mindre enn 1000. Som du vil se ligner definisjonene i struktur svært på de du så i artikkelen om Forth.

10 USING: math kernel sequences math.ranges prettyprint ;
11 IN: euler1
12 
13 : mult? ( x y -- ? ) rem 0 = ;
14 
15 : mult3? ( x -- ? ) 3 mult? ;
16 : mult5? ( x -- ? ) 5 mult? ;
17 
18 : mult3or5? ( x -- ? ) dup mult3? swap mult5? or ;
19 
20 : sumMultsOf3or5 ( seq -- n ) [ mult3or5? ] filter sum ;
21 
22 : solveEuler1 ( -- ) 0 1000 (a,b) sumMultsOf3or5 . ;

Hovedforskjellen fra løsningen i Forth er at jeg her har tilgjengelig en funksjon som oppretter en range for meg på stacken, en annen funksjon som filtrerer, og til slutt en funksjon som summerer hele stacken. Factor har altså et rikere biblotek med kraftigere definisjoner og rikere datatyper enn det Forth har.

Det du ser i parantes mellom definisjonsnavnet og selve implementasjonen er dokumentasjon av hvilke effekter definisjonen vil ha på datastacken. ( x y – ? ) betyr at mult? forventer to elementer på stacken, at disse vil bli “poppet” bort, og at et nytt, boolsk element vil bli pushet tilbake. Du kan godt velge å se på det som en funksjonssignatur, som spesifiserer inn-parametre og ut-parametre.

Koden forklart i detalj

I figurene nedenfor har jeg forsøkt å illustrere hvordan enkelte av ordene jeg har opprettet gjør jobben sin på stacken..

Over ser du hvordan man kan bruke mult? til å finne ut om 8 er et multippel av 5. Da må 8 og 5 først være på stacken. Rem-kommandoen vil poppe begge tallene, og pushe resten etter divisjon – altså 3 – tilbake på stacken. Deretter pusher vi 0, og så = (erlik-kommandoen), som igjen popper to tall og pusher svaret, som i dette tilfellet er False: 8 er ikke et multippel av 5.

Over ser du den litt mer kompliserte mult3or5?, som sjekker ett tall som ligger øverst på stacken – i dette tilfellet 20. Først dupliseres det, fordi jeg trenger å teste det to ganger. Deretter kalles mult3?, som spiser ett tall, og pusher om det var et multippel av 3 eller ikke. Så må jeg kjøre swap for å få det andre 20-tallet på toppen, før jeg kaller mult5?.

Til slutt bruker jeg or-kommandoen til å avgjøre om ett av de to øverste elementene er True. Resultatet blir liggende igjen på stacken.

Til slutt ser du hvordan sumMultsOf3or5 gjør jobben sin (figuren lyver litt, en sekvens ligger faktisk bare som ett element på stacken, men jeg tror ikke det spiller noen rolle for deg akkurat nå).

Input på stacken er altså en sekvens med tall. Deretter pushes det en kodeblokk som inneholder et kall til mult3or5?. Når filter så blir kalt vil den poppe første element (blokken) og kalle den for hvert element i sekvensen. Hvis blokken returnerer True vil tallet bli beholdt. Til slutt kalles sum, som summerer sekvensen, og vi står tilbake med svaret på stacken.

Hvordan komme igang

Factor finner du på factorcode.org. Last det ned for din plattform, og sett igang. På concatenative.org-wikien finner du en rekke tips til hvordan du begynner å lære språket.

Og så var det bare fem dager igjen til Jul. Lykke til!

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.

På tide med litt kode

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..

En rekursiv variant

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.

Hvordan komme i gang med Forth

GForth er en open source-implementasjon av Forth. Last den ned! Så leser du online-boken Starting Forth. Resten kommer av seg selv!

Hvorfor bruke tid på Forth

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.