Pipeline programming

Monday, 12 March 07
Avete presente come funziona il sistema UNIX? Ci sono tanti comandi che possono essere utilizzati in pipe, ovvero l'output del primo diventa l'input del secondo che produrra' un output che diventa input del terzo e cosi' via.

Ad esempio se voglio ordinare una lista di nomi contenuti in un file e poi numerarli poteri scrivere:
cat nomi.txt | sort | cat -n
per produrre un output simile a questo:
% cat nomi.txt | sort | cat -n
     1  cane
     2  gatto
     3  lince
     4  orco
     5  panda
     6  topo


Se ci pensate un po' in molti programmi, specialmente se chi li ha scritti e' interessato alla programmazione funzionale o comunque non gradisce utilizzare variabili inutili e una programmazione troppo imperativa, questo tipo di costrutto e' implicitamente presente molto ma molto spesso:
renderhtml(sort(getmessages($db)));
L'output di una funzione viene dato in input a quella piu' esterna e cosi' via. Il metodo funzionale e' piu' generale della pipe di unix perche' non c'e' solo un input e un output per ogni componente della computazione, ma multipli. Ogni funzione puo' prendere piu' argomenti, e ogni funzione puo' restituirne piu' di uno (implicitamente ritornando un oggetto, una lista, un array, o esplicitamente nel caso di alcuni linguaggi).

Nonostante la sua maggiore potenza la sintassi che permette alle funzioni di essere piu' generale della pipe e' brutta da scrivere (bilanciare le parentesi a volte e' una rottura di scatole, aggiungi un nuovo step nella computazione e devi tornare indietro col cursore per racchiudere quanto gia' scritto tra due nuove parentesi) e specialmente da leggere.

Come se non bastasse in moltissimi dei casi in cui le funzioni vengono utilizzati in maniera annidata in realta' non utilizzano la loro potenza a pieno, ma una semantica che potrebbe essere riprodotta con una pipe. Nel caso di sopra:
renderhtml(sort(getmessages($db)));
Potrebbe essere reso come
getmessages($db) | sort | renderhtml
Mi piace tantissimo. Pero' sembra troppo limitativo il fatto che le funzioni devono essere tutte unarie (cioe' che accettano un solo argomento) quando magari e' solo uno dei tanti argomenti che la funzione riceve a provenire in realta' dalla computazione della pipe, ma si potrebbe banalmente usare una sintassi particolare per l'argomento che proviene dalla pipe se necessario.

Per fare un esempio concreto sort potrebbe prendere un secondo argomento che indica il modo in cui ordinare l'input. In tal caso potremmo scrivere cosi':
getmessages($db) | sort(*,DESC) | renderhtml
In questo caso * viene sostituito con l'output che proviene da getmessages che nel nostro ipotetico esempio prende una lista di messaggi da qualche parte (un DB?).

Ovviamente tale sintassi potrebbe benissimo essere utilizzata in contesti piu' complessi, come questo:
intersection($l | unique | trim, getsomedata | somefunc | somefunc(*,$somearg));
In questo caso abbiamo chiamato una funzione binaria che ha come argomenti due computazioni eseguite tramite la pipe.

Sarei davvero contento di vedere questa piccola ma utile astrazione comparire in qualche linguaggio di programmazione diffuso. C'e' un piccolo problema, la pipe | e' un simbolo gia' usato per il bitwise OR, ma qualche simbolo libero e facile da digitare ancora c'e' (ad esempio @).
4047 views*
Posted at 09:14:47 | permalink | 8 comments | print
Do you like this article?
Subscribe to the RSS feed of this blog or use the newsletter service in order to receive a notification every time there is something of new to read here.

Note: you'll not see this box again if you are a usual reader.

Comments

panta writes:
13 Mar 07, 13:37:47
L'idea e` interessante e va sicuramente approfondita.
Mi sembra pero' che per "mappare" bene il concetto di unix pipe ai linguaggi di programmazione si debba estendere la dimensionalita` dell'input/output tra le funzioni. Le pipe di unix offrono un collegamento "temporale", trasferendo dati temporalmente diversi ma morfologicamente dello stesso tipo (linee di un file con lo stesso formato ad esempio). Se pensiamo a portare il concetto ai linguaggi di programmazione dovremmo mantenere questo aspetto. Entra in gioco il fatto che le funzioni sono n-arie invece che 1-arie. Basta pensare allora a flussi bidimensionali di dati (un asse e` il tempo, l'altro la "n-arieta`" dei parametri). Possiamo anche pensare che un parametro non e` piu` un valore ma uno stream temporale di valori. Serve un operatore di slicing evoluto per selezionare una fetta o un sottoinsieme degli stream di parametri.
Ad esempio:

... | getparameters | multiply{1,3}

dove getparameters ipoteticamente fornisce un flusso di tuple a piu` di tre valori e multiply moltiplica due colonne del flusso in ingresso, in questo caso la prima e la terza.
Andando avanti con l'esempio ci si rende pero' subito conto dell'esigenza di un nuovo operatore, il "raccordo a T", rimanendo nell'analogia idraulica. Basta pensare a come estendere l'esempio per addizionare 1 al flusso di valori prodotto da multiply (o peggio addizionare un flusso derivante da qualche altra parte). Qui non saprei come trovare una sintassi soddisfacente.
Servirebbe qualcosa di questo tipo:

[... | getparameters | multiply{1,3}], /1/ -| sum{1,2}

L'operatore /1/ serve a creare un flusso a partire da una costante. All'inizio avevo scritto identity(1), ma ovviamente non si puo` piu` fare, perche' la funzione identity si aspetta comunque un flusso...

Direi che la cosa forse non e` nemmeno difficile da fare in Lisp o Scheme ricorrendo alla lazy evaluation.
Commenti?
pp writes:
15 Mar 07, 11:28:40
In haskell la cosa riesce particolarmente bene.
Con l'operatore di applicazione ($):
fun3 $ fun2 $ fun1 something
O con l'operatore di composizione (.):
(fun3 . fun2 . fun1) something

E l'applicazione parziale risulta comodissima in caso di funzioni con piu' di un argomento

(+ 10) . (* 2) . sum $ [1,2,3]

In python si potrebbe lavorare su __or__, ma ogni funzione "componibile" dovrebbe essere decorata e wrappata in un oggetto.

Forse in ruby (classi aperte) si potrebbe implementare comodamente, ma non conosco ruby :)

Comunque una combinazione di compose e partial per python non dovrebbe essere troppo scomoda.

fun = reduce(compose, (fun1, partial(fun2, 10), fun3))
fun(arg)
antirez writes:
15 Mar 07, 11:37:34
Ciao Marco!

Il tuo commento mette le cose in una luce completamente diversa. In realta' ci sono due semantiche distinte per la pipe ma lo sto realizzando solo ora leggendo il tuo commento. Una e' quella da me proposta ed implementata in Tcl qua (http://wiki.tcl.tk/17879), in cui ogni elemento della pipe prende il precedente input, lo elabora per intero, e lo passa al prossimo.

L'altra semantica e' invece quella in cui c'e' un flusso anche temporale, come accade nella pipe di unix, e i programmi in realta' vengono eseguiti simultaneamente aspettando uno l'input dell'altro.

La differenza puo' sembrare piccola, ma invece e' molto grande perche' da una parte la semantica a cui pensavo io e' molto piu' semplice da implementare, mentre quella che realizza il vero flusso tra una funzione e l'altra necessita le co-routine o qualche altra forma di continuazioni, ma ha anche il grande vantaggio che non deve tenere tutto in memoria ad ogni step!

Comunque per molti usi pratici sono convinto che la semantica da me proposta sia piu' pratica perche' piu' facile da implementare nei linguaggi comuni, permette il look ahead, e risolve il secondo problema... quello dell'innesto a T :)

Questa cosa della T in effetti l'avevo pensata, e anche se volgarmente imperativa una soluzione e' questa (in Tcl):

pipe a b c d > subtotal \
d1 $subtota e1 f1 > res1 \
d2 $subtota e2 f2 > res2
puts $res1 $res2

In pratica nella funzione Tcl che ho proposto nel wiki di Tcl un po' come accade nella shell di Unix il simbolo > seguito da un nome di variabile mette il risultato corrente della pipe in quella variabile. A quel punto avviare due diverse computazioni per simulare l'innesto a T diventa semplice.

Anche in questo caso e' solo una illusione rispetto alla reale semantica della pipe che giustamente necessiterebbe di un ben piu' complesso meccanismo.

Grazie del commento!
antirez writes:
15 Mar 07, 11:55:57
per pp: L'operatore di composizione di Haskell e' praticamente la pipe :) Molto bello. Inoltre si... hai perfettamente ragione, l'applicazione parziale e' il modo matematicamente corretto di evitare la sintassi dell'asterisco dove manca l'argomento. Grazie per il tuo interessante contributo.
panta writes:
16 Mar 07, 04:55:44
Ok, quindi tu pensi alle pipe come ad una semplice sintassi diversa per la "composizione" di funzioni? Se e` cosi` non sono sicuro di volerla in un linguaggio, perche' seppure sicuramente piu` leggibile e` poco DRY, per dirla come va di moda oggi, o in altri termini non e` ortogonale alla sintassi gia` esistente - e` zucchero sintattico...
Poi temo che la nuova sintassi troppo facilmente indurrebbe a dimenticarsi che l'output di un comando e` generato per intero prima di essere passato al successivo, poiche' uno e` portato a pensare alla pipe di unix. Si arriverebbe a facilmente a inefficienze. Banalizzando ed estremizzando, uno potrebbe essere tentato di scrivere un tool di masterizzazione dividendolo in una funzione "find" e una "makeiso". La prima creerebbe un array con forse decine di milioni di file...
Proprio per queste applicazioni invece, non immediate da scrivere altrimenti, sarebbe utile un supporto nativo che nasconda l'abbinata continuazione/lazy evaluation. Sarebbe utile anche in applicazioni numeriche tra l'altro.
antirez writes:
17 Mar 07, 06:39:49
per panta:
Esatto... io pensavo solo ad una sintassi alternativa per la composizione e implicitamente per l'applicazione parziale (sintassi dell'asterisco nell'argomento mancante). E' solo zucchero sintattico ma cattura delle due tecniche un caso di utilizzo cosi' specifico che permette quasi di ragionare in termini diversi anche se in fondo e' esattamente la stessa cosa.

La tua proposta e' assolutamente affascinante... e a questo punto oltre a continuazione e lazy evaluation perche' tale sintassi non dovrebbe addirittura (in tempi di processori con piu' core) nascondere l'elaborazione parallela? Anche se non in maniera perfetta scrivere degli algoritmi in termini di pipe potrebbe permettere di parallelizzare la computazione in maniera quasi trasparente su piu' thread.
panta writes:
19 Mar 07, 04:38:18
Si, l'elaborazione parallela a questo punto discende quasi naturalmente. L'accoppiata lightweight threads stile erlang, e parallelismo su posix threads darebbe notevole flessibilita` su architetture sia moderne che antiche. Come dici tu il pipe e` un meccanismo IPC che nasconde dall'utente i problemi di sincronizzazione. Niente locks o altri casini. Sarebbe un po' come portare il concetto di message passing di qnx dal sistema operativo al linguaggio.
riffraff writes:
02 Apr 07, 18:18:57
in effetti in haskell c'è una cosa che è più pipe del $, se non ricordo male.
Afaik, $ è solo un operatore di raggruppamento a bassa priorità, ergo
fun2 $ fun1 ()
è solo
fun2(fun1())

ma puoi usare le arrows...
non che ne sia sicuro ma mi pare che l'operatore apposito sia >>> quindi:
fun1 >>> fun2 >>> fun3
Con partial application inclusa :)

Anche in perl6 esiste una cosa analoga, e sempre affidandomi alla mia scarsa memoria...

fun1 ==> fun2 ==> fun3
comments closed