-+  Documenti
 |-  Bibliografia
 |-  Articoli
 |-  Perlfunc
 |-  F.A.Q.
 |-  F.A.Q. iclp
-+  Eventi
-+  Contatti
-+  Blog
-+  Link
R: Tags
hop (3)



 

Versione stampabile.


Stefano Rodighiero
Programmatore Perl per lavoro e per passione, non sempre in quest'ordine. Il suo blog.

Alla sospirata pubblicazione di "Higher-Order Perl" (HOP, d'ora in poi) non è ancora seguita alcuna recensione. Tanto entusiasmo che sparisce così improvvisamente è strano.

Non conosco i motivi per cui gli altri possessori del libro non abbiano ancora scritto, ma provo ad avanzare qualche ipotesi, che sono poi le ragioni per cui io non ho scritto nulla.

HOP non è un testo che si possa sfogliare come un cookbook: ritengo che i concetti esposti siano nuovi per il programmatore Perl tipico, quindi il libro va letto, studiato, assimilato. Questo dà una misura di quanto sia interessante: come infatti dice Damian Conway nella sua breve presentazione:

As a programmer, your bookshelf is probably overflowing with books that did nothing to change the way you program... or think about programming. You're going to need a completely different shelf for this book.
(Se siete programmatori, probabilmente il vostro scaffale straripa di libri che non hanno avuto alcuna influenza sulla vostra maniera di programmare... o sulla maniera di pensare alla programmazione. Avrete bisogno di uno scaffale del tutto diverso per questo libro)

Poi sì, c'è il fatto che il genere della recensione mi è ostile, e questo ha avuto il suo peso per il mio ritardo, ma è un altro paio di maniche.

E` un libro da digerire, dicevo, ma non è un libro che porta a scrivere codice concettuoso o difficile: Dominus si è anzi impegnato per fare in modo che il codice prodotto con le tecniche da lui insegnate apparisse naturale. Come dice a proposito di un certo brano di codice "di passaggio":

Although this works well, it has one big defect: it appears to have required cleverness
(Benchè funzioni bene, ha un grande difetto: sembra aver richiesto furbizia)

Cercherò di avvalorare tutte queste considerazioni con un esempio concreto di applicazione delle tecniche spiegate nel libro.

Come al solito, si parte da un problema reale: moz, uno degli avventori abituali del canale #nordest.pm, sta scrivendo un CGI che tra le altre cose deve produrre dinamicamente una query SQL secondo uno schema di questo genere:

SELECT * FROM tabella
 WHERE field1 = $valore1 $bool_op1
       field2 = $valore2 $bool_op2
       field3 = $valore3

Se $bool_op1 fosse stato un valore fisso, allora la soluzione sarebbe stata quasi banale: si usa join(), dopo aver preparato la lista delle clausole (anche questo era un problema, ma non lo tratterò), e via. Purtroppo però join() non va bene, ne servirebbe uno tipo questo:

ejoin [ $bool_op1, $bool_op2 ]
    , @clausole;

Ovvero un join speciale che accetti come parametro anche la sequenza dei separatori da usare. Si tratta di un tipico problema che si può risolvere con la cassetta degli attrezzi che si acquisisce leggendo HOP. Arriviamoci per gradi.

Per prima cosa scriviamo myjoin(), equivalente a join(): servirà ad acquisire una tecnica fondamentale per procedere. Cosa fa join? Piglia un separatore, una lista di stringhe e restituisce una stringa unica costituita da tutte le stringhe concatenate e "inframmezzate" dal separatore.

Tutte le volte che da una lista di valori se ne vuole ottenere uno solo, è molto probabile che il compito possa essere espresso in termini della funzione reduce. Si tratta di un costrutto tipico dei linguaggi funzionali, che si aspetta una sequenza di valori e la funzione da applicare a questi ultimi per ottenere il risultato. Ad esempio, la sommatoria è un esempio di reduce: i numeri da sommare sono la sequenza di valori, e la funzione è la somma.

reduce-sum.png

max() o min() sono ulteriori esempi di funzioni esprimibili in questi termini. Anche join(), come dicevo, è pensabile in termini di reduce: basta usare la funzione che concatena i valori mettendoci in mezzo il separatore.

Non difficile implementare reduce in Perl (dopo aver letto HOP, o per meglio dire copiando da HOP: si trova a pagina 344). Eccola:

sub reduce 
{
    my $code = shift;
    my $val  = shift;
    for (@_) { $val = $code->( $val, $_ ) }
    return $val;
}

reduce accetta come primo parametro una reference a codice, e usa il primo dei restanti parametri come accumulatore per il risultato finale. Poi, finchè ci sono altri valori, viene chiamata la sub referenziata da $code, passandole l'accumulatore e il prossimo valore. Applichiamo subito reduce per fare una sommatoria:

$somma = reduce( sub { $_[0] + $_[1] }
               , (1 .. 5) );

E lui da bravo restituisce 15. Bene. Tutta questa manfrina però era per riscrivere join(). E` presto fatto:

sub myjoin
{
    my $sep = shift;
    reduce( sub { $_[0] . $sep . $_[1] }, @_ );
} 

Ci stiamo avvicinando alla soluzione al problema iniziale. E` sufficiente fare in modo che $sep non sia sempre lo stesso, ma provenga da una sequenza passata alla procedura. Per farlo, adopereremo un altro arnese della cassetta messa a disposizione da HOP: gli iteratori.

Un iteratore è un ente che è capace di restituire il prossimo elemento di una sequenza: esso quindi conosce la sequenza e la posizione raggiunta all'interno di quest'ultima. A richiesta, fornirà il prossimo elemento e aggiornerà la posizione. Come molte altre cose in HOP, gli iteratori possono essere implementati con una closure. Ecco uno dei primi esempi che compaiono nel libro (si trova a pagina 121):

sub upto
{
  my ($m, $n) = @_;
  return sub {
    return $m <= $n ? $m++ : undef;
  };
}
my $it = upto( 3, 5 );

Per chiedere i valori all'iteratore è sufficiente richiamare la subroutine restituita da upto():

print $it->(); # 3
print $it->(); # 4
print $it->(); # 5

HOP suggerisce (a pagina 123) un idioma alternativo per evidenziare sintatticamente che si sta lavorando con un iteratore:

sub Iterator(&) { return $_[0] }

In maniera tale da poter scrivere

sub upto
{
  my ($m, $n) = @_;
  return Iterator {
    return $m <= $n ? $m++ : undef;
  };
}

Non è fondamentale, ma ne faremo uso. Anzi, ne facciamo subito uso per scrivere una piccola sub che da una lista produce un iteratore per quella lista (anche in questo caso sto copiando, per la precisione da pagina 161):

sub list_iterator
{
    my @items = @_;
    return Iterator {
        return shift @items;
    }
}

Ora abbiamo tutti i pezzi per risolvere il problema:

sub ejoin 
{
    my $seps = shift;
    my $it = list_iterator( @$seps );
    reduce( sub { $_[0] . $it->() . $_[1] }, @_ );
}

Sono due linee di codice. Ancora più importante, il codice non riserva sorprese e dovrebbe risultare semplice, purchè recepiti i meccanismi della funzione reduce e dell'iterator.

HOP è bello (e ve ne consiglio l'acquisto, anche se sta per essere pubblicato online integralmente) proprio per questo: fornisce un vasto insieme di nuove idee da applicare ai propri programmi. Per renderli più semplici, non più "furbi".


Ti è piaciuto questo articolo? Iscriviti al feed!


Inviato da frodo72 il July 23, 2005 7:28 PM

Ammetto che sto aspettando la versione on-line di HOP :)

La funzione reduce() compare già in List::Util, implementata secondo lo stesso principio ma con un paio di accorgimenti che la rendono un po' più intuitiva - viene chiamata come map, sort e grep, compreso l'utilizzo di $a e $b.

La funzione è XS, quindi codificata in C per maggiore velocità di esecuzione, ma ne esiste una versione "Pure Perl" nel modulo per poter essere utile anche laddove il compilatore non è disponibile - List::Util fa parte infatti dell'insieme CORE dei moduli, ossia quel gruppo di moduli che vengono distribuiti unitamente a Perl stesso, ragion per cui la portabilità del modulo è un requisito fondamentale. Per inciso, se volete vedere il codice potete farlo rapidamente con perldoc -m List::Util

Un'interessante applicazione di reduce() la dà Randal Schwartz (quello di "Learning Perl") su PerlMonks - si tratta in pratica di trovare l'elemento di una Hash-of-Hash-of-Hash... data una lista di chiavi intermedie. Purtroppo in questo caso l'uso di require inibisce l'utilizzo stile sort/map/grep.

Inviato da verbat il July 24, 2005 12:31 PM

Da notare che reduce è anche nota come "foldl" (LISP, Haskell, ML) ed inject (Smalltalk, Ruby) e che in realtà è il più generale dei meccanismi di manipolazione di sequenze.

A proposito di usi di reduce, è interessante il pacchetto di test per il metaoperatore apposito che c'è in perl6:
http://svn.openfoundry.org/pugs/t/builtins/lists/reduce.t

Inviato da dada il July 25, 2005 2:36 PM

Innanzitutto complimenti a larsen per l'articolo :-)

Volevo però fare un appunto, non per polemica quanto per spirito di discussione.

Per il compito che ci si propone di assolvere, quello proposto da moz, mi pare che la programmazione funzionale in genere (nonché il Perl 6) metta a disposizione uno strumento ancora più specifico: l'operatore/funzione zip. Se la sintassi non è cambiata ultimamente, credo che in P6 la cosa si possa scrivere:

  my $query = "SELECT * FROM tabella WHERE " ~ zip(@condizioni, @operatori);
  # oppure
  my $query = "SELECT * FROM tabella WHERE " ~ @condizioni ¥ @operatori;

Una possibile (e propriamente "funzionale") implementazione in Perl 5 della funzione zip sarebbe:

  sub zip(\@\@) {
    my($a, $b) = @_;
    return @$a ? (shift(@$a), shift(@$b), zip($a, $b)) : ();
  }

  # da usare così:
  my $query = "SELECT * FROM tabella WHERE " . zip(@condizioni, @operatori);

Tale funzione, tuttavia, ha il grosso difetto di distruggere gli array passati (per via dello shift): dopo la chiamata, @condizioni e @operatori risultano vuoti.

Per ovviare, non mi viene in mente niente di meglio che questa versione (per la quale immagino che Dominus storcerebbe non poco il naso :-):

  sub zip (\@\@) {
    my($a, $b) = @_;
    my($i, $j) = (0, 0);
    my @r;
    while(exists $a->[$i]) {
      push(@r, $a->[$i++], $b->[$j++]);
    }
    return @r;
  }

Infine, riguardo all'affermazione di verbat (reduce è il più generale dei meccanismi di manipolazione di sequenze), mi ero chiesto se questo fosse effettivamente vero: nello specifico, se fosse possibile implementare la funzione "map" in termini di "reduce".

Ad una prima occhiata la cosa non sembra possibile, almeno in Perl: questo perché non esiste una "funzione" (intesa come first-class function) che sia equivalente all'operatore "," (costruttore di lista). Ergo, map e reduce sembrano due "primitive" che hanno lo stesso grado di genericità.

Però, grazie al prezioso aiuto di larsen, ho scoperto che la cosa è invece possibile:

  sub mymap(&@) {
    my $code = shift;
    my $r = reduce( 
      sub {
        local $_ = $_[1];
        push @{$_[0]}, $code->();
        return $_[0];
      }, 
      [], 
      @_
    );
    return @$r;
  }

  print mymap { $_ ** 2 } ( 1 .. 10 );

Non bellissima, sicuramente non efficiente, ma da un punto di vista puramente accademico, non impossibile. Non mi resta quindi che dare ragione a verbat :-)

cheers,
Aldo

Inviato da verbat il July 25, 2005 7:41 PM

eheh beh non è che fosse un'ìdea mia, lettura interessante a riguardo è :
http://www.cs.nott.ac.uk/~gmh/fold.pdf

Tra l'altro un'altra curiosità è il meccanismo gather/take in perl6 che è un po' un reduce più leggibile, perché in pratica nasconde l'accumulatore dietro una funzione.

Una domanda sul codice: imho è più chiara una versione della closure più interna come:

sub {
  my $acc = shift;
  push @{$acc}, $code->(@_);
  $acc;
}, 

Ci sono motivi particolari per preferire l'uso di local?

PS
ed ovviamente mi ero scordato di fare i complimenti per un articolo di piacevole lettura :)

Inviato da dada il July 25, 2005 9:14 PM

Ciao verbat.

A dire il vero non ho capito cosa intendi per closure "più interna"; temo che dal tuo codice siano saltati alcuni caratteri (a occhio e croce, i caratteri "@").

Se ho ben capito, tu proponi questa versione di mymap:

  sub mymap(&@) {
    my $code = shift;
    my $r = reduce( 
      sub {
        my $acc = shift;
        push @{$acc}, $code->(@_);
        $acc;
      }, 
      [], 
      @_
    );
    return @$r;
  }

Ora, questa versione sembra funzionare, ma per un malaugurato incidente!

L'utilizzo di local serve fondamentalmente ad "emulare" il comportamento del map standard del Perl, che imposta $_ ad ogni iterazione con il valore corrente della lista che si sta elaborando (infatti l'argomento con cui avevamo chiamato mymap era "$_ ** 2").

Il funzionamento della tua versione, quindi, avviene solo per via della definizione di reduce:

  sub reduce {
    my $code = shift;
    my $val  = shift;
    for (@_) { $val = $code->( $val, $_ ) }
    return $val;
  }

Qui viene usato $_ per iterare sui valori passati a reduce, e in mancanza di ulteriori definizioni, lo stesso $_ arriva alla closure $code di mymap.

Basta modificare reduce usando un iteratore esplicito:

  sub reduce {
    my $code = shift;
    my $val  = shift;
    for my $item (@_) { $val = $code->( $val, $item ) }
    return $val;
  }

...e la tua versione non funziona più :-)

In ogni caso, non è concettualmente corretto invocare la $code di mymap passandogli l'intero array @_; ogni invocazione di $code deve lavorare su un singolo elemento.

Si possono sicuramente utilizzare dei nomi più espliciti per le variabili in $code, e usare shift invece di accedere all'array @_ direttamente, ma si perde qualcosa in efficienza.

Spero di aver reso più chiara la cosa, e mi scuso per non aver commentato a sufficienza il codice precedentemente postato :-)

cheers,
Aldo

Inviato da larsen il July 25, 2005 9:18 PM

In realtà verbat non aveva dimenticato dei caratteri, è che di default per i commenti usiamo Textile, che si è confuso con i sigil e tutto il resto. Ho comunque corretto il post di verbat affinchè si veda bene. Grazie a tutti per l'interessante discussione.

Inviato da verbat il July 26, 2005 12:03 AM

sottoscrivo, discussione interessante e grazie mille della spiegazione










Devo ricordare i dati personali?