Il mio primo giorno di scuola con Erlang

Nell’ultimo periodo il nome di questo linguaggio di programmazione ha cominciato a comparire sul mio radar… un altro tra i numerosi linguaggi di programmazione esoterici?

Avendo studiato in un dipartimento di matematica, mi è capitato di avere amici entusiasti di OCaml, Haskell e qualche altro strano essere: so che di linguaggi buoni ma di nicchia ce ne sono tanti. Qualcuno insiste persino col Python…

Recente è la notevole dichiarazione di odio/amore di Damien Katz, autore di CouchDb che pur criticandone sintassi e diversi altri elementi continua a considerarlo affascinante. L’ultimo bip sul radar è venuto da Bob Ippolito, noto pythonista ma più genericamente esperto cavallerizzo di tecnologie eterogenee: (uno dei suoi lavori che preferisco è MochiKit, libreria che fa fare meno schifo al JavaScript (sic), ed è in effetti un’ottima libreria lightweight, di chiarissima ispirazione Python). Ultimamente Bob ha fondato MochiAds, una rete di advertisement per giochi Flash, ed ha presentato i suoi internals alla conferenza C4[1], dove ha rivelato… esatto: nel suo video il bravo ed agnostico Bob ci racconta di come sua compagnia poggi le fondamenta sull’Erlang.

Insomma sembra intrigante come un linguaggio di ricerca, ma scopro che invece ha origini industriali ben solide: è stato sviluppato dalla Ericsson con il preciso intento di costruire sistemi con affidabilità superiore ai cinque nove. Per me c’erano ormai abbastanza segnali per decidere di fare almeno un tutorial. E comprare un libro. E provare a scrivere il mio primo programma.

Gli esercizi dei tutorial sono sempre fondamentali per creare la memoria muscolare che rende l’utilizzo del linguaggio un dialogo con la macchina e non una sequenza di punizioni, ma il vero banco di prova consiste nello staccarsi dal bordo e provare a nuotare una vasca in autonomia. Quindi ho deciso di prendere un compito, del tipo che non avrei trovato difficoltà a svolgere in Python, e provare a risolverlo in Erlang.

Il problema

Il compito scelto per questo esperimento è il problema proposto da Marco Beri: il cubetto, ovvero la ricerca di tutte le possibili soluzioni di un puzzle tridimensionale. In particolare ho deciso di non prendere scorciatoie ma di implementare:

  1. parsing del file di input,
  2. ricerca delle soluzioni,
  3. stampa delle soluzioni.

Parsing dell’input

Una delle caratteristiche del runtime dell’Erlang è la possibilità di creare un gran numero di processi concorrenti, la cui possibilità di interazione è limitata al solo scambio di messaggi. Tali processi, per motivi sia di portabilità che di efficienza, non sono mappati né su processi né su thread del sistema operativo ospite: sono invece strutture leggere, con un footprint di poco più di 300 byte, veloci sia nello spawn che nel message passing. Numerosi processi Erlang possono essere eseguiti nello stesso processo ospite, ma possono anche girare in core diversi o addirittura su macchine diverse.

Ho pensato di far finta di avere un problema tale da rendere questa caratteristica utile, ad esempio un processo I/O bound da eseguire parallelamente a uno o più processi CPU bound. Quindi ho organizzato il codice in maniera da leggere le righe e, una volta ottenute righe a sufficienza per un pezzo, lanciare un parser per trasformarlo in una struttura di dati utile per la soluzione del problema.

parse_cubetto(FileName) ->
   {ok, File} = file:open(FileName, read),
    Row = io:get_line(File, ""),
    parse_cubetto(File, Row, [], 0),
    Faces = receive_faces(lists:seq(0,5), []),
    dict:from_list([ {Idx, sets:from_list(Face)} || {Idx, Face} <- Faces]).

La funzione è solo un entry point che comincia a leggere un file sequenzialmente: parte del lavoro è lasciata ad una omonima ma con diverso numero di parametri. Ottiene tutti i risultati in maniera sincrona dalla receive_faces e restituisce quanto il programma si aspetta: un dizionario dall’indice della faccia all’insieme di punti che la rappresenta. La lettura del corpo viene eseguita da:

parse_cubetto(_File, eof, Acc, Num) ->
    spawn(fun parse_face/0) ! {self(), {Num, Acc}};
parse_cubetto(File, "\n", []=Acc, Num) ->   % ignore consecutive eols
    Row = io:get_line(File, ""),
    parse_cubetto(File, Row, Acc, Num);
parse_cubetto(File, "\n", Acc, Num) ->
    spawn(fun parse_face/0) ! {self(), {Num, Acc}},
    Row = io:get_line(File, ""),
    parse_cubetto(File, Row, [], Num+1);
parse_cubetto(File, Row, Acc, Num) ->
    NewRow = io:get_line(File, ""),
    parse_cubetto(File, NewRow, [Row|Acc], Num).

Le caratteristiche salienti della versione con 4 parametri della funzione parse_cubetto sono:

  • è una funzione ricorsiva: in Erlang non esistono costrutti di iterazione ma il compilatore è in grado di effettuare l’ottimizzazione tail call, che rende la ricorsione una valida alternativa all’iterazione (esistono anche costrutti for each e list comprehension che sono probabilmente più familiari per chi proviene da linguaggi di alto livello).
  • È composta da diverse clausole: a runtime viene selezionata quella giusta effettuando il match degli argomenti. Per esempio la prima versione viene scelta quando la riga (secondo parametro) è l’atomo eof, la seconda quando la riga è vuota e l’accumulatore una lista vuota.

Il comportamento della funzione è il seguente: una riga viene estratta dal file: se è una riga di dati, questa viene aggiunta ad una lista di accumulazione; se è vuota, la lista di accumulazione passa al parsing. Come si diceva in precedenza, il parsing delle facce è asincrono: il costrutto:

spawn(fun parse_face/0) ! { self(), {Num, Acc}};

effettua la creazione di un nuovo processo (spawn()), che andrà ad eseguire la funzione parse_face, e l’invio al nuovo processo di un messaggio (tramite l’operatore !) contenente i dati da parsare e l’identità del processo (ottenuta con self()) a cui restituire il risultato.

La parse_face non prende argomenti, ma aspetta il da farsi come messaggio:

parse_face() ->
    receive
        {Pid, {Num, Face}} ->
            Pid ! {Num, parse_face_3d(lists:reverse(Face))}
    end.

quindi utilizza la parse_face_3d() (dettagli a seguire) per effettuare il lavoro di interpretazione in maniera sincrona per poi restituire il risultato al destinatario, la cui identità è anch’essa ricevuta nel messaggio. Si noti che la lista delle righe viene invertita: le righe lette dal file erano state infatti aggiunte alla testa della lista (con il costrutto [Row|Acc]) e quindi risultano invertite rispetto all’ordine di lettura.

Chi riceverà le strutture parsate? Una volta che l’intero file è stato letto, il processo di lettura passa alla receive_faces:

receive_faces([], Acc) ->
    Acc;
receive_faces(Faces, Acc) ->
    receive
        {Num, Face} ->
            receive_faces(Faces — [Num], [{Num, Face}|Acc])
    end.

che implementa un join, iterando e bloccando il processo finché non ha ricevuto tutte le facce attese, restituendo un risultato in maniera sincrona. Non esistono race condition tra questi processi: ogni processo ha infatti una mailbox dove vengono accumulati i messaggi in attesa del receive giusto (ovvero con un pattern correttamente abbinato). Quindi, se anche le prime strutture vengono passate (dal ! nella parse_face) prima che il primo processo raggiunga la receive del receive_faces, nessun messaggio viene perduto.

Questa versione relativamente pulita del parser non è stata la prima che ho scritto: non essendo abituato alla programmazione concorrente, ho penato un po’ per capire chi dovesse generare (spawn) chi, quali messaggi passarsi, individuare i passaggi inutili e ridurre al minimo le operazioni generate. All’inizio ad esempio avevo messo il join in un processo separato: eliminando tale processo la comunicazione dei pid di ritorno è risultata molto semplificata. Ho sbloccato la "sindrome da foglio bianco" scarabocchiando un diagramma di sequenza, ma non potrei dire che il parto sia stato indolore: questo è senz’altro uno dei punti in cui il cambio di paradigma fa sentire la sua fatica, ma probabilmente uno di quelli per cui più vale la pena affrontare lo sforzo, dati i risultati che ne possono conseguire.

Modello del problema

Ogni faccia del cubetto è formata da 6×6 elementi. Per risolvere il problema ho deciso di modellare ogni faccia del cubo come un insieme di punti in tre dimensioni, un punto per elemento. In questo modo il posizionamento delle facce può essere rappresentato da una sequenza di trasformazioni lineari, facilmente componibili attraverso moltiplicazioni tra matrici. Se due pezzi trasformati avranno qualche punto in comune, vuol dire che non si incastrano. Per usare trasformazioni lineari e non affini, e per usare solo numeri interi evitando arrotondamenti, ho disposto i punti lungo le coordinate [-5, -3, -1, 1, 3, 5].

side_ord() -> [ -5, -3, -1, 1, 3, 5].
plane_to_space(X, Y) -> {X, 5, Y}.
parse_face_3d({Row, Y}) when Y == -5; Y == 5 ->
    row_to_points(Row, side_ord(), Y);
parse_face_3d({[C1,_,_,_,_,C2,$\n], Y}) ->
    row_to_points([C1,C2], [-5,5], Y);
parse_face_3d(Face) ->
    lists:flatmap(fun parse_face_3d/1, lists:zip(Face, side_ord())).
row_to_points(Row, Xs, Z) ->
    [ plane_to_space(X, Z) || {X, C} <- lists:zip(Xs,
        [ C || C <- Row, ((C =:= $.) or (C =:= $#)) ]), C =:= $# ].

Solo gli elementi lungo i bordi delle facce sono necessari: questi vengono convertiti in punti disposti sulla faccia "superiore" del cubetto. L’ultima list comprehension prende in input una riga quale ##..##\n e filtra via i caratteri non interessanti, appaia una ascissa al carattere, elimina le coppie contenenti il carattere . e infine restituisce le coordinate 3D.

Soluzione del problema

Il problema è risolvibile effettuando esaustivamente tutti i tentativi di mettere i pezzi in una certa posizione su ogni faccia del cubo. Finché i pezzi si incastrano possiamo andare avanti a provare pezzi successivi. Se giungiamo ad un vicolo cieco, ovvero non è possibile incastrare nessun pezzo in una certa posizione, abbiamo senz’altro commesso un errore in una delle mosse precedenti. Non resta che tornare sui nostri passi ed effettuare una scelta diversa.

Un modo semplice di implementare questa strategia è quella di sfruttare lo stack di chiamata per memorizzare quello che abbiamo provato, invocando ricorsivamente la funzione di posizionamento del pezzo. Questa ricorsione non potrà essere tail, in quanto desideriamo mantenere in memoria tutti i livelli di chiamata (che saranno al più 6) e srotolare lo stack quando risulta necessario (backtrack). Ma contemporaneamente l’esplorazione di tutte le mosse deve essere una seconda ricorsione (questa volta tail, se possibile)… in breve tempo ho cominciato a non capirci niente tra ricorsioni, iterazioni, trasformazioni delle facce, memorizzazione dei pezzi usati…

Per superare l’impasse ho diviso il problema in due parti: una prima di risoluzione di un generico gioco del tipo "trova tutte le soluzioni", un secondo di risoluzione del gioco in questione.

Risolutore di giochi

Un problema più semplice risolvibile con la stessa strategia è quello di trovare tutti i cammini su una griglia: anche questo un problema già affrontato, anche se ne veniva chiesto solo il conteggio delle soluzioni.

Per trovare esplicitamente tutte le soluzioni descrivo il gioco usando tre funzioni:

  • generate_moves(State) prende lo stato del problema e genera la lista delle mosse possibili. Nel nostro caso lo stato è una coppia di numeri {X, Y} e le mosse possibili sono i due spostamenti in orizzontale ({1, 0}) e in verticale ({0, 1})
  • change_state(State, Move) prende uno stato e una mossa e genera un nuovo stato, rappresentante il sistema dopo la mossa, oppure l’atomo invalid se la mossa non è valida (nel caso della griglia di lato n non sono valide le mosse che portano una delle coordinate ad essere maggiore di n)
  • is_final_state(State) è un predicato che ci avverte se abbiamo trovato una soluzione.

In Erlang non ci sono classi ma, poiché le funzioni sono elementi di primo livello, posso creare strutture contenenti funzioni ed utilizzarle alla stregua di vtable. Dunque posso creare una struttura rappresentante un gioco:

-record(game, {
    generate_moves,
    change_state,
    is_final_state}).

e popolarla con le funzioni implementanti il gioco da risolvere:

manhattan(N) ->
    #game{
        generate_moves = fun(_State) -> [ {1, 0}, {0, 1} ] end,
        change_state = fun
            ({X, Y}, {MX, MY}) when ((X + MX) =< N), ((Y + MY) =< N) ->
                {(X + MX), (Y + MY)};
            (_State, _Move) ->
                invalid
        end,
        is_final_state = fun({X, Y}) -> {X, Y} =:= {N, N} end
    }.

La strategia di risoluzione prende in input il gioco e uno stato iniziale ed emette una lista di soluzioni, ognuna espressa come lista di mosse:

find_solutions(#game{}=Game, InitialState) ->
    Solution = [],
    Solutions = [],
    find_solutions(Game, InitialState, Solution, Solutions).
find_solutions(#game{}=Game, State, Sol, Sols) ->
    Moves = (Game#game.generate_moves)(State),
    find_solutions(Game, State, Moves, Sol, Sols).
find_solutions(#game{}, _State, [], _Sol, Sols) ->
    Sols;
find_solutions(#game{}=Game, State, [Move|Moves], Sol, Sols) ->
    case (Game#game.change_state)(State, Move) of
        invalid ->
            find_solutions(Game, State, Moves, Sol, Sols);
        NewState ->
            NewSols = case (Game#game.is_final_state)(NewState) of
                true ->
                    [lists:reverse([Move|Sol]) | Sols];
                false ->
                    find_solutions(Game, NewState, [Move|Sol], Sols)
            end,
            find_solutions(Game, State, Moves, Sol, NewSols)
    end.

nell’ultima clausola si vede la ricorsione "vera": se si è effettuata una mossa valida ma che non ci ha portato alla soluzione, aggiungiamo alla soluzione in elaborazione la mossa effettuata e ripartiamo dal nuovo stato. Utilizziamo ricorsione tail invece per iterare lungo le mosse possibili. Alla fine dell’esecuzione, le soluzioni riportate per la griglia di lato 2 sono:

[[{0,1},{0,1},{1,0},{1,0}],
 [{0,1},{1,0},{0,1},{1,0}],
 [{0,1},{1,0},{1,0},{0,1}],
 [{1,0},{0,1},{0,1},{1,0}],
 [{1,0},{0,1},{1,0},{0,1}],
 [{1,0},{1,0},{0,1},{0,1}]]

Soluzione del cubetto

A questo punto è sufficiente implementare le tre funzioni che descrivono il nostro gioco. Lo stato sarà una tripla {Pieces, World, Left} con Pieces il mapping dal numero di faccia all’insieme dei punti rappresentati (di sola lettura), World l’insieme dei punti posizionati, Left l’elenco degli indici delle facce ancora da posizionare. Lo stato finale è riconoscibile da avere Left vuoto:

is_final_state({_Pieces, _World, []})    -> true;
is_final_state({_Pieces, _World, _Left}) -> false.

Ogni mossa è rappresentata da una coppia {Idx, Xforms} con Idx l’indice della faccia da posizionare, Xforms la sequenza di trasformazioni. Ogni pezzo può essere trasformato combinando i tre elementi:

  • metti il pezzo sottosopra o no,
  • ruota il pezzo in passi di 90°,
  • posiziona il pezzo sulla faccia giusta.
generate_moves({_Pieces, _World, Left}) ->
    [ {Piece, Xform }
        ||  Piece <- Left,
            Xform <- generate_xforms(6 - length(Left)) ].
generate_xforms() ->
    [ [{rotate, y, Ang}, Xform]
        ||  Ang <- [0, 90, 180, 270],
            Xform <- [ ident, {flip, x} ]  ].
generate_xforms(Num) ->
    [ [{pos, Num} | Xforms] || Xforms <- generate_xforms() ].

Ad esempio le possibilità di mettere una faccia in posizione 2 sono le 8 successive:

> cubetto:generate_xforms(2).
[[{pos,2},{rotate,y,0},ident],
 [{pos,2},{rotate,y,0},{flip,x}],
 [{pos,2},{rotate,y,90},ident],
 [{pos,2},{rotate,y,90},{flip,x}],
 [{pos,2},{rotate,y,180},ident],
 [{pos,2},{rotate,y,180},{flip,x}],
 [{pos,2},{rotate,y,270},ident],
 [{pos,2},{rotate,y,270},{flip,x}]]

Il cambio di stato viene svolto effettuando la trasformazione dei punti del pezzo ed unendoli ai punti dei pezzi già posizionati, ma se i due insiemi hanno punti in comune, la mossa è considerata non valida.

get_face(Pieces, Idx) -> dict:fetch(Idx, Pieces).
change_state({Pieces, World, Left}, {Piece, Xforms}) ->
    MovedPiece = dot(
        mmult([ xform(Xform) || Xform <- Xforms ]),
        get_face(Pieces, Piece)),
    case sets:size(sets:intersection(World, MovedPiece)) of
        0 -> {Pieces, sets:union(World,  MovedPiece), Left — [Piece]};
        _ -> invalid
    end.

La trasformazione delle mosse simboliche in matrici:

xform(ident) -> {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
xform({flip, x}) -> {{-1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
xform({rotate, _Axis, 0}) -> xform(ident);
xform({rotate, x, 90}) -> {{1, 0, 0}, {0, 0, 1}, {0, -1, 0}};
xform({rotate, y, 90}) -> {{0, 0, -1}, {0, 1, 0}, {1, 0, 0}};
xform({rotate, z, 90}) -> {{0, 1, 0}, {-1, 0, 0}, {0, 0, 1}};
xform({rotate, Axis, 180}) ->
    mmult(xform({rotate, Axis, 90}), xform({rotate, Axis, 90}));
xform({rotate, Axis, 270}) ->
    mmult(xform({rotate, Axis, 180}), xform({rotate, Axis, 90}));
xform({pos, 0}) -> xform(ident);
xform({pos, 1}) -> xform({rotate, z, 270});
xform({pos, 2}) -> xform({rotate, z, 180});
xform({pos, 3}) -> xform({rotate, z, 90});
xform({pos, 4}) -> xform({rotate, x, 90});
xform({pos, 5}) -> xform({rotate, x, 270}).

e le loro composizioni e applicazioni a punti dello spazio:

dot({X1, X2, X3}, {Y1, Y2, Y3}) when is_integer(X1), is_integer(Y1) ->
    X1 * Y1 + X2 * Y2 + X3 * Y3;
dot({{E1X, E1Y, E1Z}, {E2X, E2Y, E2Z}, {E3X, E3Y, E3Z}}, {_,_,_}=V) ->
    {   dot({E1X, E2X, E3X}, V),
        dot({E1Y, E2Y, E3Y}, V),
        dot({E1Z, E2Z, E3Z}, V)};
dot(Base, Points) ->
    sets:from_list([ dot(Base, Point) || Point <- sets:to_list(Points) ]).
mmult([M1,M2|Tail]) ->
    mmult([mmult(M1,M2)|Tail]);
mmult([M]) ->
    M.
mmult(M,{{_,_,_}=V1,{_,_,_}=V2,{_,_,_}=V3}) ->
    {dot(M, V1), dot(M, V2), dot(M, V3)}.

sono semplici applicazioni di algebra lineare e di aerobica della computer graphics.

Per evitare di trovare le stesse soluzioni in tutti i possibili orientamenti, fissiamo una delle facce nello stato iniziale. Con tale vincolo, il problema risulta avere 6 soluzioni distinte.

La facilità con cui in Erlang si producono atomi (semplicemente, si utilizzano), che possono essere comparati per identità e sottoposti a match porta facilmente a creare algoritmi simbolici e a gestire elegantemente casi particolari. La seguente è la rappresentazione interna di una delle soluzioni (quella illustrata nella Figura 1):

[{0,[{pos,0},{rotate,y,0},ident]},
 {1,[{pos,1},{rotate,y,180},{flip,x}]},
 {3,[{pos,2},{rotate,y,90},ident]},
 {2,[{pos,3},{rotate,y,0},ident]},
 {4,[{pos,4},{rotate,y,270},ident]},
 {5,[{pos,5},{rotate,y,180},ident]}]

La mancanza di classi nel linguaggio non è un impedimento nell’applicazione di pattern tipicamente associati alla OOP (il risolutore è un template method pattern).

Stampa delle soluzioni

La stampa delle soluzioni non presenta grossi problemi: si rimanda al listato completo. Queste sono invece le soluzioni generate.

Visualizzazione 3D di una soluzione del cubetto.

Figura 1. Una delle soluzioni del cubetto.

Conclusioni

"Ha senso, per me, imparare Erlang?" Questa è la domanda che mi sono posto quando è diventato impossibile ignorare i bip sul radar, e prima di questo esercizio. Penso che una persona esperta sia di Python che di C/C++ abbia le spalle coperte per la stragrande maggioranza delle necessità di sviluppo: sia di sistemi grandi ed articolati che di sistemi che richiedono elevate prestazioni (chi è esperto del linguaggio e della piattaforma Java potrebbe pensarla allo stesso modo).

Erlang va a ricoprire una nicchia di utilizzo molto peculiare: quella dei sistemi fault-tolerant e distribuiti (che tipicamente sono distribuiti per essere fault-tolerant, ma potrebbero esserlo anche per necessità di bilanciamento del carico e di scalabilità): implementare una simile soluzione in qualunque altro linguaggio consisterebbe di fatto nel ricreare un sottoinsieme del runtime già disponibile e testato per Erlang, per creare ad esempio gli alberi di supervisione che invece in Erlang sono pattern fondamentali di architettura. La maniera pressoché nativa in cui è possibile effettuare distribuzione del carico è qualcosa di cui avrei beneficiato largamente in alcuni progetti a cui ho lavorato in passato, e che comunque sono stati costruiti in stile message passing proprio perché non è così facile distribuire lo stato: avere nel linguaggio stesso (e non nel framework di deploy) le primitive per far sì che un problema possa scalare in maniera semplice aumentando hardware è una cosa che mi farebbe dormire tranquillo anziché impazzire di micro-ottimizzazioni.

Accettato Erlang come linguaggio utile, lo si può definire facile? Probabilmente avvicinarsi ad Erlang è più difficile che avvicinarsi a qualunque altro linguaggio imperativo: ricorsione al posto dell’iterazione, pattern matching e clausole multiple come principale meccanismo di scelta… il salto di paradigma è davvero lungo, e non nego che aver studiato il Prolog mi abbia aiutato all’inizio. Ma visto che il message passing è un paradigma architetturale solido ed indipendente dal linguaggio, non mi sembra una cattiva occasione quella di sperimentarlo in un linguaggio che non accetta compromessi.

Per me è stato di stimolo anche un famoso aforisma di Alan Perlis:

un linguaggio che non influenzi il tuo modo di pensare alla programmazione non vale la pena di essere conosciuto.

Comments

  1. Azz… se questo era il tuo primo giorno di scuola che combini a fine quadrimestre? 🙂
    Pure io avevo letto il post di Damien Katz ma con risultati opposti: l’erlang tour è ancora sulla pila delle cose da fare…

Policy per i commenti: Apprezzo moltissimo i vostri commenti, critiche incluse. Per evitare spam e troll, e far rimanere il discorso civile, i commenti sono moderati e prontamente approvati poco dopo il loro invio.