-module(life). %% %% http://www.iki.fi/kartturi/erlang/life_erl.txt %% %% life.erl - Yksinkertainen Erlang-toteutus John Conwayn Life-soluautomaatista %% Tämä versio käyttää yksinkertaista ASCII-grafiikkaa tulostukseen. %% %% http://www.iki.fi/kartturi/erlang/life_gs_erl.txt %% on gs-grafiikkakirjastoa käyttävä versio. %% %% Copyright (C) 2005 by Antti Karttunen %% Lisätietoja: AnttiKarttunen (at) gmailcom %% Erlang-kääntäjä löytyy osoitteesta: http://www.erlang.org/ %% Kuvaus: %% Ohjelman lähtökohtana on jakaa ohjelman suoritus osiin, niin että kunkin %% yksittäisen Life-solun laskenta tapahtuu omassa prosessissaan. Kunkin %% solun seuraava tila riippuu, paitsi sen omasta tilasta sillä hetkellä, %% niin myös sen kahdeksan naapurin tilasta. Solut välittävät oman %% tilansa naapureilleen Erlang-kielen send-käskyllä (!) ja vastaanottavat %% naapuriensa viestit receive-käskyllä. Soluprosessien keskinäistä %% viestintää ei tarvitse synkronoida. %% Solujen toimintaa kokonaisuudessan valvoo ja synkronoi erillinen %% valvojaprosessi, jolle solut myös lähettävät kulloisenkin tilansa %% tulostusta varten. %% Funktio cell laskee kunkin solun tilan %% %% Ohjelman ydin on funktio cell, joka laskee ja ylläpitää kunkin solun %% tilaa. Se jakautuu kolmeen eri haaraan, joita kutsutaan laskennan eri %% vaiheissa. Ensimmäistä haaraa kutsutaan kun solut on käynnistetty %% valvojaprosessista funktiolla spawn_cell. Tässä haarassa solu lähettää %% valvojalle oman tilatietonsa Erlangin send-käskyllä. Käsky koostuu %% huutomerkistä, jonka vasemmalla puolella annetaan sen prosessin nimi %% (tai ID-numero), jolle viesti lähetetään, ja oikealla puolella itse %% lähetettävä viesti. %% %% Viestinlähetyksen jälkeen jäädään odottamaan receive-käskyllä %% valvojaprosessin "next"-viestiä. (Sen valvojaprosessi lähettää kaikille %% vasta sitten, kun se on saanut nykyiset tilatiedot kaikilta soluilta). %% Kun "next"-viesti tulee, lähetetään oma tila funktiolla send_state_to_all %% myös kaikille kahdeksalle naapurisolulle (joiden rekisteröidyt %% nimet löytyvät listasta Neighbours), jonka jälkeen siirrytään %% cell-funktion kolmanteen haaraan odottelemaan samoilta naapurisoluilta %% saapuvia viestejä. %% %% Viestit ovat muotoa {NName,NState}, joista parin ensimmäinen jäsen %% kertoo lähettävän naapurisolun nimen, ja toinen sen tilan (0=kuollut, %% 1=elossa). Kolmannessa haarassa pyöritään niin kauan kuin viestit %% kaikilta kahdeksalta naapurilta ovat saapuneet, jonka jälkeen %% päädytään cell-funktion toiseen haaraan, jossa voidaan laskea solun %% uusi tila, jonka jälkeen voidaankin siirtyä takaisin ensimmäiseen %% haaraan, jossa sykli alkaa alusta. %% Valvojaprosessi synkronoi solujen laskennan %% %% Valvojaprosessi käynnistetään start-funktiolla, joka silmukoi %% supervise-funktion kolmiparametrisen haaran omaksi prosessikseen ja %% rekisteröi sen nimellä "valvoja". Siinä puolestaan silmukoidaan omiksi %% aliprosesseikseen (spawn_all_cells ja spawn_cell funktioiden avulla) %% kaikki ruudukon Size x Size solua, jonka jälkeen niille kaikille %% lähetetään next-viesti, merkkinä siitä, että ne voivat aloittaa. %% %% Sen jälkeen siirrytään supervise-funktion kolmanteen haaraan %% odottelemaan soluprosessien viestejä. Vasta kun kaikki solut ovat %% lähettäneet tilatietonsa päädytään keskimmäiseen haaraan, jossa %% lähetetään next-viesti kaikille, ja samalla tulostetaan ruudulle %% solusimulaation uusi tilanne. %% %% Koska viestit soluilta voivat tulla missä järjestyksessä tahansa, %% niin valvojaprosessin pitää tallettaa niiden tila väliaikaisesti %% "dictionaryyn", joka on Perl-kielen hasheja vastaava assosiatiivinen %% taulukko. Sitä käsitellään OTP-kirjaston mukana tulevassa %% "dict"-modulissa määritellyillä dict:new, dict:store ja dict:fetch %% kutsuilla. %% Pino ei vuoda yli cell- ja supervise-funktioissa, sillä kaikki %% rekursiokutsut niissä ovat ns. "häntärekursiivisia", eli %% tavukoodikääntäjä optimoi ne tavallisiksi silmukoiksi. %% Talleta tämä tiedosto nimellä life.erl vaikkapa hakemistoon /my/erlang %% (tai vastaavaan...), ja Erlang-shellin käynnistettyäsi siirry %% samaan hakemistoon komennolla cd("/my/erlang"). %% jonka jälkeen voit ladata ohjelman Erlang-tulkkiin komennolla c(life). %% Simulaation voi käynnistää esimerkiksi komennolla life:start_spaceship(). %% Simulaatio lopetetaan komennolla life:stop(). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% %% Varsinainen ohjelmakoodi alkaa. %% %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% export-lauseessa luetellaan niiden funktioiden nimet, %% joiden halutaan olevan muista moduuleista (tai komentoriviltä) %% kutsuttavissa: -export([make_cellname/2,list_of_cellnames/1,cells_neighbours/2, spawn_cell/3,cell/6,nextgen/1,liferule/2, supervise/3,start/1,stop/0,start_glider/0,start_spaceship/0]). %% import-lauseessa luetellaan sellaisia muissa moduuleissa %% esiintyviä funktioita, joihin halutaan viitata lyhyesti. %% Esimerkiksi tässä annetun käskyn jälkeen riittää että sanotaan %% append, foreach, jne. sen sijaan, että kirjoitettaisiin %% lists:append, lists:foreach, jne. -import(lists,[append/1,foreach/2,map/2,nth/2,seq/2]). %% Tällä luodaan rivillä ROW, sarakkeessa COL sijaitsevalle %% solulle uniikki nimi. Nimi koostuu pienestä c-kirjaimesta %% sekä argumentteja ROW ja COL vastaavista numeroista. %% Esimerkiksi life:make_cellname(3,5) palauttaa solun nimenä %% atomin 'c35'. make_cellname(ROW,COL) -> list_to_atom([99,48+ROW,48+COL]). %% Funktiolla list_of_cellanems tuotetaan lista nimiä, joita %% käytetään soluprosessien rekisteröimiseen. %% Esimerkiksi life:list_of_cellnames(3). %% palauttaa listan: [c00,c01,c02,c10,c11,c12,c20,c21,c22] %% Huomaa "list comprehension" -rakenteen käyttö. list_of_cellnames(Size) -> [make_cellname(ROW,COL) || ROW <- seq(0,Size-1), COL <- seq(0,Size-1)]. %% Funktio cells_neighbours palauttaa annetun solun naapurit. %% Se tarvitsee myös solumaailman koon argumenttinaan, %% jotta se osaisi "wräpätä" ruudukon reunojen ympäri. %% Esimerkiksi life:cells_neighbours(c36,8). %% palauttaa listan: [c25,c26,c27,c35,c37,c45,c46,c47] %% ja life:cells_neighbours(c07,8). %% palauttaa listan: [c76,c77,c70,c06,c00,c16,c17,c10] %% %% 'c07' on siis 8x8-ruutuisen maailman oikeassa yläkulmassa %% oleva solu, jolla on naapurinaan esimerkiksi vasemmassa %% alakulmassa oleva solu c70 ja oikeassa alakulmassa %% oleva c77. %% %% Huomaa "list comprehension"-rakenteessa filtterin %% (abs(X)+abs(Y))/=0 käyttö, joka takaa että X ja Y %% käyvät läpi kaikki muut -1:n, 0:n ja +1:n yhdistelmät %% paitsi 0,0:n. (Solu ei ole itsensä naapuri!) cells_neighbours(Cellname,Size) -> ROW = nth(2,atom_to_list(Cellname))-48, COL = nth(3,atom_to_list(Cellname))-48, [make_cellname(((Size+ROW+X) rem Size),((Size+COL+Y) rem Size)) || X <- [-1,0,+1], Y <- [-1,0,+1], (abs(X)+abs(Y))/=0]. %% Funktio liferule kertoo solun oman nykyisen tilan (argumentti C) %% ja sen elossa olevien naapurien määrän (argumentti NAlive) %% perusteella, onko solu seuraavassa sukupolvessa %% elossa (1) vai kuollut (0). %% Edellinen toteutuu vain silloin kuin solu on joko %% valmiiksi elossa, ja sillä on joko 2 tai 3 elossa %% olevaa naapuria, tai silloin kuin se on kuollut, %% mutta sillä on tasan kolme elossa olevaa naapuria. %% Tämä ehto on ytimekkäintä testata 'bor' eli binary-or %% -operaatiolla: liferule(C,NAlive) -> if (3 == (NAlive bor C)) -> 1; true -> 0 end. %% Funktio sendstate lähettää prosessille Proc lähettävän %% solun nimestä (Name) ja tilasta (State) koostuvan %% viestin, Erlangin sisäänrakennetulla viestinvälityskäskyllä !: sendstate(Proc,Name,State) -> Proc ! {Name,State}. %% Funtio send_state_to_all lähettää viestin {Name,State} %% kaikille listassa Procnames luetelluille prosesseille. %% Se käyttää listan yli iteroimiseen monista muistakin %% ohjelmointikielistä tuttua foreach-funktionaalia. send_state_to_all(Name,State,Procnames) -> foreach(fun(P) -> sendstate(P,Name,State) end,Procnames). %% Funktion cell ensimmäinen haara. Lähettää valvojaprosessille %% oman tilansa (tulostusta varten) ja jää receive-käskyllä %% odottelemaan siltä 'next'-viestiä. Viestin saapumisen jälkeen %% lähettää oman tilansa kaikille kahdeksalle naapurilleen %% ja siirtyy cell-funktion kolmanteen haaraan. cell(Name,Gen,State,0,0,Neighbours) -> valvoja ! {Name,State}, receive next -> send_state_to_all(Name,State,Neighbours), cell(Name,Gen,State,0,1,Neighbours) end; %% Funktion cell toinen haara. Kun viestit kaikilta kahdeksalta %% naapurisoluprosessilta ovat saapuneet (eli neljäs argumentti %% on kasvanut 8:ksi), lasketaan tämän solun uusi tila ja siirrytään %% takaisin ensimmäiseen haaraan. cell(Name,Gen,State,8,NAlivePlus1,Neighbours) -> Newstate = liferule(State,NAlivePlus1 - 1), cell(Name,Gen+1,Newstate,0,0,Neighbours); %% Funktion cell kolmas haara. Tässä pyöritään niin kauan, %% kunnes viestit kaikkien kahdeksan naapurin tilasta %% on otettu vastaan. cell(Name,Gen,State,NMsgs,NAlivePlus1,Neighbours) -> receive {NName,NState} -> cell(Name,Gen,State,NMsgs+1,NAlivePlus1+NState, Neighbours) end. %% Funtio spawn_cell silmukoi uuden soluprosessin ja käynnistää %% sen cell-funktion ensimmäisessä haarassa, jossa se lähettää %% heti kuittauksen tilastaan valvojaprosessille ja jää %% odottelemaan siltä 'next'-viestiä, ennen kuin varsinainen %% "laskenta" alkaa. Käyttämällä spawn-funktion linkittävää %% muotoa spawn_link varmistetaan se, että järjestelmään ei %% jää pyörimään soluprosesseja "haamuina", mikäli niitä %% valvova valvojaprosessi lopetetaan. spawn_cell(Cellname,Size,InitState) -> register(Cellname, spawn_link(?MODULE, cell, [Cellname,0,InitState,0,0, cells_neighbours(Cellname,Size)])). %% Funktio spawn_all_cells(Solujen_nimet,Koko,Tilat) %% silmukoi kaikki tarvittavat Koko x Koko soluprosessia, %% alustaen niiden tilat kolmantena argumenttina annetussa %% listassa olevilla alkutilan tiedoilla. %% Tässä listojen yli iteroimiseen on käytetty Erlangille %% tyypillistä häntärekursiivista rakennetta. spawn_all_cells([],_,_) -> ok; % Lopetusehto, lista lopussa. spawn_all_cells([Cellname|CRest],Size,[InitState|SRest]) -> spawn_cell(Cellname,Size,InitState), spawn_all_cells(CRest,Size,SRest). %% Apufunktio joka lähettää soluprosessille "next"-viestin: nextgen(Cellname) -> Cellname ! next. %% supervise-funktion ensimmäinen haara. Valvojaprosessi %% käynnistetään siten, että se alkaa tästä haarasta. %% Ensiksi silmukoidaan Size x Size soluprosessia, %% jonka jälkeen kullekin lähetetään "next"-viesti %% (merkiksi siitä, että voivat aloittaa), %% jonka jälkeen valvojaprosessi siirtyy supervise-funktion %% kolmanteen haaraan odottelemaan solujen tilatietoja. supervise(Size,Cellnames,InitialStates) -> spawn_all_cells(Cellnames,Size,InitialStates), foreach(fun(Cell) -> nextgen(Cell) end,Cellnames), supervise(Size,Size*Size,0,0,Cellnames,dict:new()). %% Tätä haaraa kutsutaan silloin kun tilatiedot %% kaikilta soluilta on vastaanotettu. %% Lähettää kaikille soluille "next"-viestin, %% jotta voivat aloittaa keskinäisen viestimisensä %% uudestaan, seuraavan sukupolven tilanteen laskemiseksi. %% Sillä välin näyttää nykyisen tilanteen konsolilla %% funktiota show_cells käyttäen. supervise(Size,NCells,Gen,NMsgs,Cellnames,CStates) when NMsgs == NCells -> foreach(fun(Cell) -> nextgen(Cell) end,Cellnames), show_cells(Cellnames,CStates,Size,0), supervise(Size,NCells,Gen+1,0,Cellnames,dict:new()); %% Tässä haarassa pyöritään niin kauan kunnes kaikkien %% soluprosessien tilatiedot ovat saapuneet (jonka %% tapahduttua siirrytään automaattisesti edelliseen haaraan), %% tai kunnes käyttäjä tahtoo pysäyttää koko simulaation %% lähettämällä valvojaprosessille "stop"-viestin. %% Mikäli jotkut soluprosesseista hyytyvät jostain syystä, %% tämä havaitsee sen receive-käskyyn liittyvällä %% after-lauseella, joka on Erlang-kieleen %% lisätty juuri timeout:tien toteuttamista varten. supervise(Size,NCells,Gen,NMsgs,Cellnames,CStates) -> receive {CellName,CellState} -> supervise(Size,NCells,Gen,NMsgs+1,Cellnames, dict:store(CellName,CellState,CStates)); stop -> exit(life_stopped) after 10000 -> exit(life_timedout) end. %% Funktio show_cells näyttää assosiatiiviseen CStates-taulukkoon %% kerätyn simulaation tilan konsolilla yksinkertaisena ASCII-grafiikkana. show_cells([],_,_,_) -> io:format("~n",[]); % Lopetusehto. Tulosta rivinvaihto. show_cells([Cell|Cellnames],CStates,Size,Colind) -> State = dict:fetch(Cell,CStates), % Tulosta kunkin rivin lopussa rivinvaihto: if (0 == (Colind rem Size)) -> io:format("~n",[]); true -> ok end, io:format("~s",[nth(1+State,[".","*"])]), show_cells(Cellnames,CStates,Size,Colind+1). pattern2state("*") -> 1; % Asteriskit olkoon eläviä soluja, pattern2state(_) -> 0. % ja kaikki muut kuolleita. start(InitPattern) -> SquareSize = length(InitPattern), Pattern2state = fun(X) -> pattern2state(X) end, Cellnames = list_of_cellnames(SquareSize), InitStates = map(Pattern2state,append(InitPattern)), register(valvoja, spawn(?MODULE, supervise, [SquareSize,Cellnames,InitStates])). stop() -> valvoja ! stop. % Pyytää valvojaprosessia lopettamaan simulaation. %% Esimerkkejä siitä, kuinka funktiota start kutsutaan: start_glider() -> start([[" "," "," "," "," "," "," "," "], [" "," ","*"," "," "," "," "," "], [" "," "," ","*"," "," "," "," "], [" ","*","*","*"," "," "," "," "], [" "," "," "," "," "," "," "," "], [" "," "," "," "," "," "," "," "], [" "," "," "," "," "," "," "," "], [" "," "," "," "," "," "," "," "]]). start_spaceship() -> start( [[" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 1 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 2 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 3 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 4 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 5 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 6 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 7 [" "," "," "," "," "," "," ","*"," "," "," "," "," "," "," "], % 8 [" "," "," "," "," "," "," "," ","*"," "," "," "," "," "," "], % 9 [" "," "," "," ","*"," "," "," ","*"," "," "," "," "," "," "], % 10 [" "," "," "," "," ","*","*","*","*"," "," "," "," "," "," "], % 11 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 12 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 13 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "], % 14 [" "," "," "," "," "," "," "," "," "," "," "," "," "," "," "]] % 15 ).