Programmazione funzionale, una semplice introduzione.

Di linguaggi di programmazione ne esistono a bizzeffe, come potete controllare nella lista e non completa, dei paradigmi di programmazione^4.1 in appendice. La cosa interessante di tutti questi è che rispecchiano il modo di pensare delle persone che li hanno ideati, la loro forma mentis.
Ogni linguaggio cerca, a suo modo, di risolvere al meglio alcune problematiche computazionali seguendo degli schemi. Questi possono essere più o meno flessibili ma nessuno è perfetto, alcuni sembrano più intuitivi di altri o più familiari ma non sempre a colpo d'occhio si è nel giusto.

Questo è il caso della programmazione funzionale che a prima vista pare una cosa aliena ed oltremodo complessa. Si è più propensi all'OOP (Object Oriented Programming) visto che ci hanno spiegato che con questo modello possiamo imitare gli oggetti reali (non vi vorrei tediare con le gerarchie padre-figlio di albero -> albero di pere o veicolo -> carretto -> automobile). All'OOP poi, la maggior parte dei programmatori associa la programmazione imperativa che piace a tutti. A chi non piace comandare? Ci fa sentire dei piccoli dio del computer: io ordino tu esegui pedissequamente: fai qui e fai là, se questo fai quello, loop!

I programmatori poi sono gente strana, mettono su discussioni interminabili, spesso sul nulla, peggio dei filosofi più noiosi. Si continua a girare il dito nella piaga per affermare che un editor di testo è migliore di un altro (io appartengo alla Church of Emacs, ovviamente), interminabili discussioni sul colore della evidenziazione della sintassi o sul è meglio questo di quest'altro.

Si perdono sui massimi sistemi della programmazione ma spesso non sono in grado di scrivere tre righe per un semplice FizzBuzz³.

Una delle guerre di religione che va per la maggiore (almeno da qualche anno) è quella tra OOP e FP (functional programming). Ognuno accusa l'altro dei peggiori crimini: OOP è responsabile di tutti i difetti del software odierno mentre FP è indecentemente complicata e con la puzza al naso oltre ad essere lenta in esecuzione. Si scontrano oggetti contro funzioni in duelli all'ultimo sangue ed all'arma bianca.

Ad onor del vero, gli sviluppatori FP un po' di puzza al naso ce l'hanno davvero in parecchi e capita di trovare codice scritto più per essere ganzi che per necessità. Molti linguaggi funzionali permettono di essere parecchio stringati e quindi di comporre codice decisamente oscuro, almeno a prima vista, anche per chi quel linguaggio lo conosce.

Cominciamo a levarci la puzza al naso.

Come ho detto sopra molti programmatori considerano OOP ed FP mutualmente esclusivi, immaginate due diverse fazioni che vivono nei loro castelli fortificati che si danno dell'esaltato o dello sfigato. Insomma una banda di tacchini schiamazzanti.

Molti di questi non hanno neanche capito di cosa parlano e si bombardano a colpi di parentesi (graffe per gli uni e tonde per gli altri).

FP, come dice il nome, ha le funzioni ed ogni programmatore ferrato vi dirà per prima cosa che le sue funzioni sono first-class object ed è cosa realmente vera, dimenticando o non sapendo che anche in Smalltalk (che è un linguaggio orientato agli oggetti e non funzionale) lo sono.

OOP ha gli oggetti e gli oggetti sono composti di dati e metodi (funzioni nel gergo OOP), ma gli oggetti non sono strutture dati, le usano semplicemente. Gli oggetti sono solo dei delimitatori di ambiente (namespace) e delle borse di funzioni. Le strutture contengono i dati mentre gli oggetti li usano (almeno dovrebbe essere così). In ogni caso qualunque programma è dati e funzioni. (Algoritmi+Strutture Dati=Programmi - Niklaus Wirth, 1987).

I metodi sono diversi dalle funzioni? C'è differenza estrema nello scrivere una chiamata a funzione con:

Se è solo una questione di sintassi è meglio andare a coltivare le cipolle.

La differenza reale è nella disciplina che le metodologie impongono, il resto è solo preferenza personale. Le due discipline non si sovrappongono e niente vieta di usarle insieme quando serve.

La forza di FP è che non ha stati mutevoli, le variabili non esistono e non ha assegnamenti. Ogni cosa è costante e prevedibile, matematicamente corretta e vedremo in seguito cosa significa.
Quindi non si possono fare cose come salvare un file? Certo, ma FP lo rende leggermente complicato e responsabile, ci obbliga a renderci conto di quello che stiamo facendo: la legge non ammette ignoranza.

La non mutabilità di stato rende pressoché impossibile che le variabili vengano sovrascritte o alterate da codice esecutivo concorrente rendendo un programma abbastanza sicuro in caso di più thread o core multipli.

OOP ha la sua forza nei puntatori a funzione.
OOP è nato dalla crisi della programmazione procedurale nel risolvere il problema del polimorfismo e cioè della invocazione della stessa funzione per tipi di dati diversi o con diversi argomenti. OOP fa questo ed a parte la fuffa degli oggetti del mondo reale o del programmare vicino a come si pensa, incapsula la complessità dei puntatori a funzione.
Chi ha programmato in C saprà di cosa si parla e dell'incubo terribile che sia gestirli al meglio.

Il polimorfismo ha un grosso beneficio: la possibilità di poter sostituire una funzionalità con un'altra. Questo ha permesso di sviluppare architetture del software a plug in o moduli inseribili. È la possibilità di disaccoppiare le dipendenze tra il codice sorgente ed il codice esecutivo.

Sono incompatibili? Non direi e ne è la prova come in questi ultimi anni si siano moltiplicati i linguaggi multi-paradigma, cioè quelli che sono in grado di usare più approcci alle soluzioni dei possibili problemi.

Nessun paradigma è migliore di un'altro, ma solo più adatto al caso specifico.

Oggi con l'affermazione del calcolo parallelo e dove anche i nostri telefoni sono equipaggiati con CPU multicore, la possibilità di avere linguaggi che non mutano il proprio stato è un grosso vantaggio, come vedremo in seguito.

Ora sappiamo che le funzioni del nostro linguaggio sono in relazione diretta con il concetto matematico di funzione. Quindi:

è una funzione che dato un valore \(x\) nel dominio dei numeri interi restituisce un nuovo valore che è pari alla somma di \(x + 1\).

Se lo scriviamo in Ocaml:

let addone x = x + 1

mentre in F#

let addone x = x + 1

è perfettamente uguale. Due identiche sintassi per due linguaggi diversi? In realtà non sono proprio diversi: F# (Fsharp) è un sottoinsieme di OCaml sviluppato nei Microsoft Labs e poi approdato come linguaggio mainstream nella linea Visual Studio (l'ambiente di sviluppo di Microsoft). Oggi l'F# è un linguaggio Open Source e multi piattaforma in conseguenza del progetto Mono⁵ (una implementazione del .NET Framework su piattaforme diverse da Microsoft Windows^tm).

Per correttezza va indicato che Mono è un progetto potenzialmente problematico a livello di licenza⁶ e la sua adozione, specialmente su Linux, è fonte di discussioni.

Questi altri esempi in diversi linguaggi funzionali:

Scala

def addone(x : Int) = x + 1

Clojure (un dialetto Lisp)

(def addone (fn [x] (+ x 1)))

Haskell (GHCi)

let addone x = x + 1

Tornando alla nostra funzione matematica, la sua caratteristica è che restituirà sempre lo stesso risultato in uscita per un dato valore in entrata e di conseguenza non avrà effetti collaterali.

Questo fatto ci permette di poter seguire e predire meglio il flusso dei dati. Nella programmazione imperativa si immagina che le funzioni facciano qualcosa e siano inerentemente delle procedure (in Pascal, un linguaggio imperativo, per esempio esiste una distinzione tra funzione e procedura), ci si aspetta che abbiano dei side effects.

La funzione matematica è invece un semplice mapping, un mappare un dominio in un altro correlato.

#include <stdio.h>

void main() {

  int add_one(int input) {
    switch (input) {
    case 0: return 1;
    case 1: return 2;
    case 2: return 3;
    // ... altri casi a seguire
    }
  }

  printf("%d\n", add_one(2));
}

Questo piccolo programma in C illustra come potrebbe essere un semplice mapping. La funzione è uno switch che mappa un valore in un altro valore: nel caso input sia 0 allora ritorna 1, se 1 ritorna due e così via. Non c'è calcolo ed solo una tabella di ispezione (lookup).
L'input e l'output sono logicamente due cose differenti e valutare la funzione non può in nessun modo portare ad effetti indesiderati su di loro.

Se torniamo alle espressioni matematiche:

non ci aspettiamo che \(a\) abbia un valore diverso da 10 e che \(b\) sia diversa da 11.

La funzione matematica è relazione piuttosto che computazione, perché matematicamente i domini esistono indipendentemente da tutto.

Questo tipo di funzioni vengono dette pure ed hanno delle caratteristiche interessanti:

1. Le si possono valutare in qualsiasi ordine.
2. La funzione può essere valutata una volta soltanto e mantenere solo il risultato (memoization).
3. La funzione può essere valutata a tempo di compilazione (inferenza di tipo o valore).
4. La funzione può essere valutata solo quando se ne ha bisogno (lazy) ed essere sicuri che si avrà quel risultato.
5. Possiamo fa calcolare quella funzione su tutti i processori che abbiamo senza preoccuparci di sovrascriverci i dati.

Ci sono senza dubbio, molti vantaggi.

A prima vista però ci sono anche degli svantaggi notevoli: un solo valore in entrata ed un solo valore in uscita, anche la immutabilità potrebbe creare problemi. In teoria tutto questo è molto bello ma se voglio avere funzioni che prendono più di un parametro? A volte c'è bisogno anche di alterare lo stato o di assegnare variabili. Vedremo poi come ovviare a queste problematiche e volgerle a nostro pro.

Questo testo non vuole essere un corso di programmazione, quanto una modesta introduzione ai concetti che pervadono il paradigma funzionale utilizzando dei piccoli esempi in un linguaggio che reputo estremamente potente ed espressivo, ma abbastanza pragmatico ed impuro, da impedire a chi cerca di avvicinarsi di perdersi nei concetti ed abbandonare l'impresa.

Riprendendo il semplice esempio di prima: let x = x + 1, abbiamo stabilito che è una funzione che accetta un valore da un dominio di input e che usa il nome x per rappresentarlo. Questo meccanismo viene chiamato binding e cioè collegamento e quindi il nome x è collegato al valore di input. È importante capire come non ci sia assegnamento, x non è una variabile ma solo un fattore mnemonico che rappresenta direttamente un valore, non potrà più cambiare una volta collegato al valore.

Per questo motivo non esistono variabili ma solo valori. Insomma pensatela come una costante di un linguaggio imperativo per farla più semplice.

Se estendiamo il concetto dei valori si può notare come anche il nome della funzione è un valore in sé. Il nome della funzione add_one è collegato ad una espressione che equivale a x -> x + 1 ed ha come firma (type signature):

val add_one : int -> int = <fun>

Questo è il tipo della funzione add_one, un valore (val) collegato ad una funzione che ha un valore in entrata nel dominio degli int e restituisce un valore in un codominio di int. È puro valore, un concetto che va ripetuto ad nauseam perché è uno dei fondamenti (forse il principale) della programmazione funzionale.

Se scriviamo:

let plus_one = add_one;;
(* signature: val plus_one : int -> int = <fun> *)

possiamo vedere come plus_one sia un nuovo nome collegato alla stessa funzione a cui era collegato add_one. Per semplificare, errando, possiamo dire che in un certo senso è come se il nome della funzione fosse un puntatore a funzione in C/C++ senza i problemi che questo comporterebbe.

plus_one 5;;
(* result: - : int = 6 *)

Per controllare molti degli esempi potete usare uno dei REPL (UTop¹⁰) disponibili per OCaml.

Per avere dei valori semplici possiamo scrivere:

let num = 5;;
(* signature: val num : int = 5 *)

ed avremo num che è collegato al valore 5, senza la freccia che indica il rapporto tra input ed output come nelle funzioni. Abbiamo definito una costante o valore.

Un semplice mapping su più valori può essere attuato in questa modo:

let (a,b) = 1,2;;
(* signature: val a : int = 1 *)
(* signature: val b : int = 2 *)

a;;
(* result: - : int = 1 *)

b;;
(* result: - : int = 2 *)

I valori semplici e le funzioni sono talmente uniti da poter essere quasi intercambiabili, sono ambedue valori collegati a nomi mnemonici tramite la parola chiave let (permettere).

Se traduciamo l'espressione let x = 5 in permetti che x sia collegata al valore 5 forse diventa tutto più chiaro.

La sottile differenza tra un valore ed una funzione è che la funzione è un valore intorno ad un dominio di input ed uno di output, ma per il resto è identica ed utilizzabile nella stessa maniera: una funzione può essere input per altre funzioni.

Il dominio di input deve essere sempre applicato all'argomento della funzione, per esempio se vogliamo definire una funzione costante:

let num = fun () -> 5;;
(* signature: val num : unit -> int = <fun> *)

o in maniera equivalente:

let num() = 5;;
(* signature: val num : unit -> int = <fun> *)

vediamo come il dominio di input sia questa volta chiamato unit e ciò comporta che la funzione deve essere risolta fornendo unit come argomento.

Invocare semplicemente:

num;;
(* result: - : unit -> int = <fun> *)

abbiamo come risultato la funzione stessa. Dobbiamo fornire l'argomento:

num ();;
(* result: - : int = 5 *)

unit è un tipo speciale e corrisponde a () e possiamo vederlo come il void dei linguaggi della famiglia C (C/C++/C#…). Al contrario di void però ha un valore ed un significato ben preciso: esso fa parte di un dominio di input o di uno di output (è un tipo reale ed un valore reale) mentre un void come valore di ritorno di una funzione C fa si che qualunque esso sia venga ignorato (di fatto in C è una indicazione per il compilatore che vogliamo trattare quella funzione come una procedure in Pascal, un routine con effetti collaterali mentre se usato come argomento di input indica esplicitamente l'assenza di parametri).

Abbiamo detto più volte che le funzioni sono valori e che possono essere utilizzati e passati come valori ad altre funzioni. Questo meccanismo è alla base della programmazione funzionale che sostanzialmente si basa sul creare piccole funzioni da collegare le une alle altre per svolgere un compito: il chaining. Come anelli di una catena le funzioni si passano valori in un flusso controllato.

Le funzioni che prendono funzioni come parametri sono dette higher-order function o functor (funtori). Un funtore in matematica è un tipo di mappa tra categorie (nella teoria delle categorie) che ne conserva le caratteristiche strutturali. In informatica è generalmente un oggetto che può essere usato come una funzione, Smalltalk¹³ fu uno dei primi linguaggi ad implementare i funtori. Il loro utilizzo è molto diffuso specialmente nel sistema di callback o delegati della programmazione ad eventi nelle interfacce grafiche. Molti linguaggi hanno costrutti più o meno semplici per poteri utilizzare e definire.

Nella programmazione funzionale è più o meno la norma utilizzarli e nel senso più matematico del termine. Un funtore è una funzione che accoglie una funzione come valore e la applica ad un tipo restituendo una relazione:

List.fold_left (+) 0 [1;2;3;4];;
(* result: - : int = 10 *)

Questo esempio usa la funzione fold_left per sommare tutti gli elementi di una lista. La funzione prende tre parametri: una funzione da applicare (in questo caso +) un accumulatore (inizializzato a zero) ed una lista ([1;2;3;4]). Inizierà applicando (+) all'accumulatore ed al primo elemento della lista, poi passerà al secondo e così via.

List.map (fun e -> "ciao " ^ e) ["max"; "ele"; "tom"];;
(* result: - : bytes list = ["ciao max"; "ciao ele"; "ciao tom"] *)

La funzione map un caposaldo delle funzioni che iterano sulle liste. In questo caso si è usata una funzione anonima utilizzando la parola chiave fun, si potrebbe anche scrivere definendo prima una funzione che concatena le stringhe:

let saluta s = "ciao " ^ s;;
(* signature: val saluta : bytes -> bytes = <fun> *)

List.map saluta ["max"; "ele"; "tom"];;
(* result: - : bytes list = ["ciao max"; "ciao ele"; "ciao tom"] *)

Le funzioni anonime sono molto utili quando servono piccole funzioni localmente da non giustificare binding di visibilità maggiore.

Definiamo una funzione che accetta un tipo funzionale:

(* definiamo una funzione che aggiunge uno ad un numero *)
let plus_one x = x + 1;;
(* signature: val plus_one : int -> int = <fun> *)

(* definiamo il funtore *)
let mult_by_fun_value fn x = fn x * x;;
(* signature: val mult_by_fun_value : (int -> int) -> int -> int = <fun> *)

mult_by_fun_value plus_one 3;;
(* result: - : int = 12 *)

(* usando una funzione annonima *)
mult_by_fun (fun x -> x + 1) 3;;
(* result: - : int = 12 *)

Credo che basti a questo punto lasciare andare la fantasia sulle possibili implicazioni.

Non è finita però. Una funzione essendo un tipo primitivo è restituibile da una funzione. Funzioni che prendono funzioni come parametri e restituiscono funzioni.

Definiamo una funzione che serva da generatore di somma:

let adder num_to_add = (+) num_to_add;;
(* signature: val adder : int -> int -> int = <fun> *)

La funzione adder prende un int come parametro e restituisce una funzione che lo mappa in una coppia di int.

Una cosa che si nota è (+), questo è un semplice operatore di somma come in tutti i linguaggi o nell'aritmetica elementare. In molti linguaggi è semplicemente una funzione speciale e può essere invocato funzionalmente. In OCaml si racchiude tra parentesi ed è in posizione prefissa come qualunque invocazione di funzione. Qui si entra anche in un'altra particolarità però: le funzioni parzialmente applicate che vedremo in seguito.

(+);;
(* result: - : int -> int -> int = <fun> *)
(* possible signature: val + : int -> int -> int = <fun>  *)

(+) 1 2;;
(* result: - : int = 3 *)

La funzione adder quindi restituisce una funzione parzialmente applicata e la possiamo usare in questo modo:

let add_one = adder 1;;
(* signature: val add_one : int -> int = <fun> *)

let add_ten = adder 10;;
(* signature: val add_ten : int -> int = <fun> *)

add_one 5;;
(* result: - : int = 6 *)

utop # add_ten 2;;
(* result: - : int = 12 *)

Ho detto prima che OCaml ha un supporto per la inferenza di tipo molto sofisticata e che quindi non sempre serve indicare quale sia il tipo di un valore. In questo caso il meccanismo di inferenza capisce cosa sia fn, è abbastanza chiaro che sia una funzione che prende un int e restituisce un int:

let eval_func_with_four_then_add_five fn = fn 4 + 5;;
(* signature: val eval_func_with_four_then_add_five : (int -> int) -> int = <fun> *)

Il problema potrebbe sorgere qui:

let eval_func_with_four fn = fn 4;;
(* signature: val eval_func_with_four : (int -> 'a) -> 'a = <fun> *)

Leggendo la signature del tipo si capisce che fn sia una funzione che pende un int ma cosa ritorna? Cosa è `a?

Questo è il modo con cui OCaml permette il polimorfismo di tipo, `a significa qualunque tipo. In questo caso però vorremmo essere un po' più espliciti e non ci serve che la funzione sia polimorfa, deve prendere un int e ritornare un int:

let eval_func_with_for_four (fn:int -> int) = fn 4;;
(* signature: val eval_func_with_for_four : (int -> int) -> int = <fun> *)

Usando la stessa annotazione di tipo dei valori indichiamo al compilatore cosa vogliamo che sia.

Qui prendiamo un int e ritorniamo un tipo string:

let eval_with_four_and_print (fn:int -> string) = print_string (fn 4);;
(* signature: val eval_with_four_and_print : (int -> bytes) -> unit = <fun> *)

let string_of_num x = string_of_int x;;
(* signature: val string_of_num : int -> bytes = <fun> *)

eval_with_four_and_print string_of_num;;
(* result: 4- : unit = () *)

eval_with_four_and_print (fun x -> string_of_int x);;
(* result: 4- : unit = () *)

Fino ad adesso si è detto che le funzioni sono come le funzioni matematiche: prendono un valore in input da un dominio e restituiscono un valore in output in un altro dominio. Nella vita reale però, servono spesso più parametri in input e quindi?

Molti linguaggi funzionali usano un metodo detto currying. Il nome viene da un matematico statunitense Haskell Curry¹⁴ che riprendendo i lavori di Moses Schönfinkel¹⁵ sulla logica combinatoria ne formulò la base teorica (un altro matematico che ne influenzò le idee fu Gottlob Frege¹⁶). I due linguaggi di programmazione Haskell e Curry sono intestati a suo nome.

Il meccanismo non è complicato ed è simile alla soluzione su carta di una funzione con parametri multipli:

Se vogliamo valutare \(f(4,8)\) cominciamo a sostituire \(a\) con 4 ottendo \(f(4,b)\) e cioè una funzione \(g(b)\) che è definita come:

Sostituendo 8 a \(b\) il gioco è fatto:

Insomma visto che le funzioni sono valori, una funzione con parametri multipli può essere ridotta ad un equivalente numero di funzioni con un solo parametro che applicano in sequenza il risultato della funzione precedente.

let multi_params a b c d e f = a + b + c + d + e + f;;
(* signature: val multi_params : int -> int -> int -> int -> int -> int -> int = <fun> *)

Abbiamo una funzione che in cascata somma valori decomponendosi in più funzioni con un input soltanto. Come lo calcolereste sulla carta questo: 2 + 2 + 2 + 2 + 2

\(2 + 2 → 4\)

\(4 + 2 → 6\)

\(6 + 2 → 8\)

\(8 + 2 → 10\)

Credo sia chiaro a questo punto.

Non tutti i linguaggi funzionali sono basati su questo meccanismo, lo consentono alcuni ma non ne sono basati. OCaml e Haskell si, ogni funzione con parametri multipli è decomposta tramite currying.

Non va confuso il currying con le funzioni parzialmente applicate che abbiamo citato prima. Sono due meccanismi diversi che coesistono, la differenza è che una funzione parzialmente applicata ritorna sempre un valore (sia esso puro o funzionale) mentre una funzione curried propone sempre una nuova funzione nella catena di currying.

Una funzione parzialmente applicata si riferisce solo al processo di formalizzare il valore di un certo numero di parametri fornendo una funzione con un numero di argomenti (arity) minore.

Guardiamo questo esempio:

let sum1 (a,b) = a + b;;
(* signature: val sum1 : int * int -> int = <fun> *)

let sum2 a b = a + b;;
(* signature: val sum2 : int -> int -> int = <fun> *)

Le due funzioni sum1 e sum2 sono definite in modo diverso. La prima, sum1, è definita in una maniera più convenzionale per chi proviene da linguaggi imperativi; ho usato le parentesi. Se la invoco:

sum1 1 2;;
(* Error: This function has type int * int -> int It is applied to too many arguments; maybe you forgot a `;'. *)

sum1 (1,2);;
(* result: - : int = 3 *)

nel primo caso, chiamandola come abbiamo fatto fino ad adesso, senza parentesi, il compilatore si lamenterà segnalando un errore. Nel secondo caso e con le parentesi eseguirà il compito.

Se guardiamo la signature del tipo notiamo che è int * int -> int e cioè una tupla (ennupla o n-upla: elenco ordinato di valori), quindi praticamente abbiamo detto che la nostra funzione sum1 non ha arity pari a due ma è soltanto a uno. Ha cioè, come argomento una coppia di valori e non più valori. Il currying è preservato.

L'errore dice questo: It is applied to too many arguments; per questo motivo sono richieste le parentesi.

Si possono usare i due approcci nelle definizioni, ma deve esserne compresa bene la differenza.

Si potrebbe pensare che il currying sia un procedura lenta e che impegni troppo calcolo; questo non è il caso di OCaml dove certi meccanismi sono particolarmente ottimizzati e le continue chiamate a funzione non hanno, per esempio, problemi di allocazione nello stack come nei linguaggi imperativi.

Ci sono alcune problematiche nelle funzioni curried, la prima è che se si forniscono meno parametri di quelli dichiarati non si hanno errori ma si otterrà una funzione parzialmente applicata in un contesto dove si aspetta un semplice valore:

let add x y = x + y ;;
(* signature: val add : int -> int -> int = <fun> *)

add 1;;
(* result: - : int -> int = <fun> *)

Un altro problema sono le funzioni che non accettano parametri. Le funzioni devono avere sempre un parametro in input quindi come abbiamo già incontrato dobbiamo dichiararla:

let one_plus_one () = 1 + 1;;
(* signature: val one_plus_one : unit -> int = <fun> *)

altrimenti non dichiarando un parametro unit avremmo, come visto in precedenza, un semplice valore.

Se invece forniamo più argomenti del necessario avremo un messaggio di errore: Error: ... It is applied to too many arguments ...

A parte Ocaml e Haskell dove il currying è la norma, altri linguaggi ne permettono l'uso come alternativa. In Scala le funzioni con parametri multipli non sono automaticamente curried:

// funzione normale con due argomenti
def sum (a:Int, b:Int) = a + b
// signature: sum: (a: Int, b: Int)Int

sum (1,2)
// result: res0: Int = 3

// funzione curried
def sum_curried (a:Int) (b:Int) = a + b
// signature: sum_curried: (a: Int)(b: Int)Int

sum_curried (1) (2);
// result: res1: Int = 3

// funzione curried
def sum_curried2 (a:Int) = (b:Int) => a + b
// signature: sum_curried2: (a: Int)Int => Int

sum_curried2 (1) (2);
// result: res1: Int = 3

In Scala le funzioni possono essere trasformate nell'uno o nell'altro tipo facilmente:

val sum_curried3 = (sum _).curried
// signature: sum_curried3: Int => (Int => Int) = <function1>

sum_curried3 (1)(2)
// result: res10: Int = 3

val sum_uncurried = Function.uncurried(sum_curried _)
// signature: sum_uncurried: (Int, Int) => Int = <function2>

sum_uncurried(1,2)
// result: res11: Int = 3

Il carattere _ (il segnaposto o placeholder) è necessario per indicare al compilatore di trattare la funzione come un valore e non come una invocazione. Per poterla convertire va trattata come una funzione parzialmente applicata. Bisogna notare che Scala è in grado di convertire le funzioni curried fino ad un numero di parametri pari a 5 (al compilatore versione 2.11.5).

def curried (a:Int)(b:Int)(c:Int)(d:Int)(e:Int)(f:Int)(g:Int)(h:Int)(i:Int) = a+b+c+d+e+f+g+h+i
// signature: curried: (a: Int)(b: Int)(c: Int)(d: Int)(e: Int)(f: Int)(g: Int)(h: Int)(i: Int)Int

val uncurried = Function.uncurried(curried _)
// signature: uncurried: (Int, Int, Int, Int, Int) => Int => (Int => (Int => (Int => Int))) = <function5>

uncurried(1,2,3,4,5)(6)(7)(8)(9)
// result: res20: Int = 45

uncurried(1,2,3,4,5,6,7,8,9)
/* error: <console>:10: error: too many arguments for method apply:
(v1: Int, v2: Int, v3: Int, v4: Int, v5: Int)Int => (Int => (Int => (Int => Int))) in trait Function5
uncurried(1,2,3,4,5,6,7,8,9) */

Scala deve far convivere mondi diversi: quello Java in OOP e quello funzionale. Però anche se sembra una limitazione, chi mai potrà fare una funzione (in un linguaggio funzionale) con più di cinque argomenti? Nel caso… Ripensate al vostro codice.

Scala ha anche numero massimo di parametri dichiarabili per una funzione: 22.

Sono e ne abbiamo già parlato, un modo che i linguaggi funzionali permettono per restringere il numero dei parametri cablandoli per l'uso locale. Il concetto è che cablando un certo numero di parametri si ottiene una funzione con i restanti.

let sum a b = a + b;;
(* signature: val sum : int -> int -> int = <fun> *)

let sum_four_to = sum 4;;
(* signature: val sum_four_to : int -> int = <fun> *)

sum_four_to 5;;
(* result: - : int = 9 *)

Guardiamo questo altro esempio per capire meglio la loro utilità:

[1;2;3] |> List.map sum_four_to;;
(* result: - : int list = [5; 6; 7] *)

Cosa succede? Abbiamo una lista di int poi un operatore detto pipe, una chiamata a List.map e la nostra funzione parzialmente applicata.

Vediamo di capire meglio. List.map sum_four_to è essa stessa una parziale applicazione di List.map dato che la sua signature è questa:

('a -> 'b) -> 'a list -> 'b list = <fun>

È una funzione che ha come primo argomento una funzione da applicare ad ogni elemento della lista che prende come secondo argomento. Il valore di ritorno sarà una nuova lista.

let sum_four_for_all = List.map sum_four_to;;
(* signature: val sum_four_for_all : int list -> int list = <fun> *)

[1;2;3] |> sum_four_for_all;;
(* result: - : int list = [5; 6; 7] *)

In questo esempio è stata esplicitamente creata una nuova funzione parzialmente applicata ed applicata alla lista. Come si vede il risultato è identico.

Esageriamo:

[1;2;3] |> sum_four_for_all |> sum_four_for_all;;
(* result: - : int list = [9; 10; 11] *)

Vediamo l'operatore |> (pipe). La pipe fa quello che deve fare e sarebbe di convogliare il valore di una funzione su un'altra in una sequenza definita. Seguendo il flusso dell'esempio precedente:

1. la lista viene passata alla prima funzione
2. la lista viene elaborata ed un nuova lista è in uscita
3. la nuova lista è passata alla seconda funzione.
4. una nuova lista elaborata è in uscita

Per convenienza visiva, quando le pipe sono molte possiamo anche scrivere:

[1;2;3]
|> sum_four_for_all
|> sum_four_for_all;;
(* result: - : int list = [9; 10; 11] *)

Possiamo così creare delle pipeline di elaborazione molto complesse mantenendo nel contempo un discreta facilità di lettura.

L'operatore pipe è definito in questa maniera (dalla versione 4.00 di OCaml è implementato nativamente):

let (|>) x fn = fn x;;
(* signature: val ( |> ) : 'a -> ('a -> 'b) -> 'b = <fun>  *)

Direi che è semplice: è una funzione che prende un valore ed una funzione applicando quella funzione a quel valore. Esiste anche una reverse pipe:

let (@@) fn x = fn x;;
(* signature: val ( @@ ) : ('a -> 'b) -> 'a -> 'b = <fun> *)

In F# le due pipe sono |> e <| rispettivamente. In OCaml sono diverse per un problema di associatività degli operatori: storicamente in OCaml il carattere | come iniziale nelle funzioni infisse fornisce associatività a sinistra mentre @ a destra.

La composizione di funzioni o function composition è una interessante applicazione delle funzioni parzialmente applicate.

In F# esistono degli operatori di composizione e sono: >> e <<. In OCaml non ci sono nella libreria standard ma occorre un supporto aggiuntivo tramite Batteries¹⁷ o Core⁷ (Batteries nel modulo BatStd come |- e -| mentre Core nel modulo Fn ha la funzione compose ).

Sono comunque facilmente definibili come:

let (>>) f g x = g(f(x));;
(* signature: val ( >> ) : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c = <fun> *)

let (<<) f g x = f(g(x));;
(* signature: val ( << ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun> *)

Vediamo come farle funzionare:

let sum a b = a + b;;
(* signature: val sum : int -> int -> int = <fun> *)

let times v n = v * n;;
(* signature: val times : int -> int -> int = <fun> *)

let sum_one_for_four_times = sum 1 >> times 4;;
(* signature: val sum_one_for_four_times : int -> int = <fun> *)

sum_one_for_four_times 2;;
(* result: - : int = 12 *)

Un altro esempio:

let sum_to_and_mult x = (+) x >> ( * );;
(* signature: val sum_to_and_mult : int -> int -> int -> int = <fun> *)

sum_and_mult 1 4 5;;
(* result: - : int = 25 *)

sum_to_and_mult 3 4 5;;
(* result: - : int = 35 *)

Interessante no? Il valore 3 è sommato al valore 4 e poi moltiplicato per il valore 5. Notare che si è scritto ( * ) e non (*) perché (* è l'inizio dei commenti in OCaml.

Le funzioni ricorsive sono molto importanti nella programmazione funzionale che ha dei supporti ottimizzati per utilizzarle. In linea di massima i costrutti imperativi per i cicli sarebbero superflui o quasi in un linguaggio funzionale.

Una funzione ricorsiva in OCaml deve essere esplicitamente dichiarata:

let rec factorial x =
  match x with
  | 0 -> 1
  | x -> x * factorial (x - 1)
;;
(* signature: val factorial : int -> int = <fun> *)

Con let rec si dichiara che una funzione è ricorsiva, nel caso si ometta rec il compilatore emetterà un errore:

let factorial x =
  match x with
  | 0 -> 1
  | x -> x * factorial (x - 1)
;;
(* Error: Unbound value factorial *)

Questo però potrebbe portare a strani comportamenti collegati allo shadowing:

let rec factorial x =
  match x with
  | 0 -> 1
  | x -> x * factorial (x - 1)
;;

let factorial x =
  match x with
  | 0 -> 1
  | x -> x * factorial (x - 1)
;;

in questa forma non saranno sollevati errori (all'inverso invece sì). Portate molta attenzione.

Si possono anche dichiarare funzioni mutualmente ricorsive tramite il costrutto let rec..and:

let rec is_even x =
  if x = 0 then true else is_odd (x - 1)
and is_odd x =
  if x = 0 then false else is_even (x - 1)
;;
(* signature: val is_even : int -> bool = <fun> *)
(* signature: val is_odd : int -> bool = <fun> *)  

Le funzioni ricorsive hanno delle importanti ottimizzazioni nei linguaggi funzionali e lo vedremo più avanti con la tail recursion^3.10.

Le funzioni anonime sono funzioni che, ovviamente, non hanno un nome a cui riferirsi. Nei codici presentati precedentemente sono state già incontrate, ma vediamole più in dettaglio. Sono chiamate anche lambda expression ed hanno due funzioni principali:

• Sono passate come argomento direttamente ad una funzione di ordine superiore.
• Si usano come valori di ritorno.

Hanno avuto origine dai lavori del matematico Alonzo Church¹⁸, il quale teorizzò nel suo lambda calculus nel 1936 come le funzioni siano di fatto tutte anonime.

Strutturalmente sono delle funzioni annidate che possono accedere a valori compresi nell'ambito di visibilità che contiene la funzione stessa. Questo significa che devono essere implementate come closure (chiusure). Essendo anonime non possono essere ricorsive a meno di non usare un fixpoint operator.

Un fixpoint operator o fixpoint combinator è matematicamente una funzione che soddisfa la relazione:

ed è chiamata così perché se si imposta \(x = y (f)\) rappresenta una soluzione per equazione a punto fisso. Per farla decisamente semplice e breve ed uscendo dalla matematica: se consideriamo il binding di una funzione su un nome il suo punto fisso, essa potrà ruotare intorno al suo nome. Si potrà avere quindi ricorsione.

Per risolvere questo problema si utilizza un cosiddetto Y combinator e cioè una funzione senza stato o pura che prenderà come argomento una funzione anch'essa pura trasformandola in ricorsiva.

type 'a b = Roll of ('a b -> 'a);;
(* signature: type 'a b = Roll of ('a b -> 'a) *)

(* Definizione con la direttiva rectypes (che permette tipi ricorsivi) attivata *)
(* let fixpoint f g = (fun x a -> f (x x) a) (fun x a -> f (x x) a) g *)
(* signature: val fixpoint : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> *)

let unroll (Roll x) = x;;
(* signature: val unroll : 'a mu -> 'a mu -> 'a = <fun> *)

let fixpoint f =
  (fun x a -> f (unroll x x) a) (Roll (fun x a -> f (unroll x x) a))
;;
(* signature: val fixpoint : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun> *)

let factorial f = function
  | 0 -> 1
  | x -> x * f (x - 1)
;;
(* signature: val factorial : (int -> int) -> int -> int = <fun> *)

let factorial2 x =
  fixpoint (fun f -> function
      | 0 -> 1
      | x -> x * f (x - 1)) x
;;
(* signature: val factorial2 : int -> int = <fun> *)

let () =

  Printf.printf "Recursion (fixpoint) with: fixpoint factorial 5\n";
  Printf.printf "%d" (fixpoint factorial 5);

  Printf.printf "\n";

  Printf.printf "Recursion (fixpoint) with: factorial2 5\n";
  Printf.printf "%d\n" (factorial2 5);

fixpoint è il nostro y-combinator che rende ricorsiva una funzione pura sia in forma anonima che non anonima.

Ogni linguaggio moderno offre un qualche modo per organizzare le funzioni in gruppi correlati. Un sistema di moduli più o meno sofisticato nella gestione delle relazioni tra di essi. Alcuni dei linguaggi funzionali sono anche di tipo ibrido o multiparadigma. Scala per esempio ha un supporto totale per la programmazione OOP: classi, interfacce (implementabili detti trait), package, ereditarietà e così via. OCaml ha una estensione per la programmazione orientata agli oggetti, anche se per un tradizionalista OOP può apparire leggermente strana.

I moduli sono la base per dare una correlazione logica ad un insieme di funzioni, una scatola con un nome che contiene altre piccole scatole. Un namespace.

Prima di dare una occhiata ai moduli va ricordato che generalmente in un linguaggio funzionale si possono definire funzioni dentro altre funzioni e questo semplicemente perché sono valori. Non hanno uno speciale trattamento come in molti linguaggi imperativi (alcuni comunque permettono la definizione di funzioni interne).

let sum_value_in_list n list =
  let plus = (+) n in
  List.map plus list

let () =
  [1;2;3;4;5]
  |> sum_value_in_list 5
  |> List.iter (fun el -> Printf.printf "%d\n" el)

Questo è un piccolo programma che evidenzia una funzione interna ad un'altra. Va notato come sia definita all'interno della struttura let...in. In questo semplice caso avremmo potuto scrivere semplicemente:

let sum_value_in_list n list =
  List.map ((+) n) list

In OCaml i moduli sono molto importanti. Ogni file è un modulo ed il nome del modulo è derivato dal nome del file con la prima lettera maiuscola. I moduli creano uno spazio per i nomi dei valori con la possibilità di avere una visibilità controllata.

Negli esempi abbiamo già utilizzato i moduli, per esempio List con List.map o List.iter.

Di un modulo se ne può controllare il cosa far vedere all'esterno tramite un file associato di interfaccia (i file in OCaml hanno estensione .ml e le interfacce lo stesso nome con estensione .mli).

Per il nostro programma di cui sopra il file .mli conterrà:

val sum_value_in_list : int -> int list -> int list

che è la signature della funzione sum_value_in_list. Il modulo principale (automaticamente creato dal nome del file) può inoltre contenere dei sotto moduli:

module ToolsSub : sig
  val sum_value_in_list : int -> int list -> int list
end = struct
  let sum_value_in_list n list = List.map ((+) n) list
end

let () =
  [1;2;3;4;5]
  |> ToolsSub.sum_value_in_list 5
  |> List.iter (fun el -> Printf.printf "%d\n" el)

Che si può esprimere, forse, in maniera più elegante:

module type ToolsSub_t = sig
  val sum_value_in_list : int -> int list -> int list
end

module ToolsSub : ToolsSub_t = struct
  let sum_value_in_list n list = List.map ((+) n) list
end

let () =
  [1;2;3;4;5]
  |> ToolsSub.sum_value_in_list 5
  |> List.iter (fun el -> Printf.printf "%d\n" el)

È come se avessimo la coppia di file toolsSub.ml e toolsSub.mli

OCaml inoltre estende i suoi moduli fino ad essere parametrizzati e diventare quindi dei functor come le funzioni. Un modulo funtore è parametrizzato con altri moduli che quindi ne sono l'argomento. Vengono utilizzati per risolvere problemi strutturali come per esempio:

• Iniezione delle dipendenze (implementazioni di componenti sostituibili).
• Estensione del modulo con nuove funzionalità (Mixin).
• Istanziare il modulo con uno stato.

Un esempio banale:

module type X_int = sig
  val x : int
end

module Increment (M : X_int) : X_int = struct
  let x = M.x + 1
end

module Three = struct
  let x = 3
end

module Four = Increment(Three)

let () =
  print_int (Four.x - Three.x)

Si è stabilita una relazione tra i moduli. Il modulo Increment ha come parametro un modulo di tipo X_int e gli viene passato Three che ha la stessa signature del tipo considerato. Possiamo quindi passargli ogni altro modulo la cui signature è allineata:

module type X_int = sig
  val x : int
end

module Increment (M : X_int) : X_int = struct
  let x = M.x + 1
end

module Three = struct
  let x = 3
end

module Four = Increment(Three)

module MoreAndText : sig
  val x : int
  val text : bytes
end = struct
  let x = 10
  let text = "ten"
end

module TenAndText = Increment(MoreAndText)

let () =
  Printf.printf "%d\n" (Four.x - Three.x);
  Printf.printf "%d\n" (TenAndText.x - Four.x);

I moduli funturi non ci sono in F# (ma in SML.NET si quindi non ci dovrebbero essere problemi tecnici, pare però che che a Don Syme²¹ non piacciano), come il sistema OOP di OCaml avendo quello .NET.

Un'altra caratteristica generalmente ritrovabile nei linguaggi funzionali è il pattern matching e la decomposizione da strutture complesse in valori semplici. Bisogna pensare sempre al mapping come concetto pervasivo ed alla gestione delle strutture dati, in particolare delle liste.

Il pattern matching si può vedere come una struttura switch..case dei linguaggi imperativi, ma parecchio pompata.

void print_num(int num) {
  switch(num) {
      case 1:
          printf("1");
          break;
      case 2:
          printf("2");
          break;
      case 3:
          printf("3");
          break;
      default:
          printf("default case.");
  }
}

In OCaml l'espressione match...with fa la stessa cosa:

let print_num num =
  match num with
  | 1 -> print_string "1"
  | 2 -> print_string "2"
  | 3 -> print_string "3"
  | _ -> print_string "default case"
;;
(* signature: val print_num : int -> unit = <fun> *)

print_num 2;;
(* result: 2- : unit = () *)

print_num 90;;
(* result: default case- : unit = () *)

Una delle differenze importanti è che quello che nei linguaggi imperativi è uno statement (dichiarazione) nei funzionali è una espressione e come espressione restituisce un valore.

let print_num1 num =
  print_string (
    match num with
    | 1 -> "1"
    | 2 -> "2"
    | 3 -> "3"
    | _ -> "default case")
;;
(* signature: val print_num1 : int -> unit = <fun>  *)

let print_num2 num =
  let n = match num with
    | 1 -> "1"
    | 2 -> "2"
    | 3 -> "3"
    | _ -> "default case"
  in
  print_string n;
;;
(* signature: val print_num2 : int -> unit = <fun>  *)

Le due impostazioni sono equivalenti.

L'espressione match..with ha molteplici usi come per esempio l'estrazione di dati da una lista. Questa funzione somma tutti gli elementi di una lista:

let rec sum list =
  match list with
  | [] -> 0
  | head :: tail -> head + sum tail
;;
(* signature: val sum : int list -> int = <fun> *)

sum [1;2;3;4];;
(* result: - : int = 10  *)

In queste poche righe sono evidenziate alcune cose importanti. La prima che di fatto l'espressione match..with è usata come un decostruttore per la lista, la seconda che si potrebbe ottimizzare.

Nel vedere il pattern matching ho presentato una funzione sum che usa la ricorsione come mezzo per sommare gli elementi di una lista di numeri, vediamo adesso come si potrebbe ottimizzare:

let rec sum_rec accumulator list =
  match list with
  | [] -> accumulator
  | head :: tail -> sum_rec (head + accumulator) tail
;;
(* signature: val sum_rec : int -> int list -> int = <fun> *)

let sum = sum_rec 0;;
(* signature: val sum : int list -> int = <fun> *)

sum [1;2;3];;
(* result: - : int = 6  *)

o in una forma più racchiusa:

let sum =
  let rec sum_rec accumulator list =
  match list with
  | [] -> accumulator
  | head :: tail -> sum_rec (head + accumulator) tail
  in
  sum_rec 0
;;
(* signature: val sum : int list -> int = <fun> *)

Qui ho usato una tail recursion. Ho modificato il codice per far si che la invocazione alla funzione ricorsiva sia alla fine della funzione stessa, in tail o coda cioè. Per fare questo ho avuto bisogno di un accumulatore come secondo parametro.

La tail recursion è un importante meccanismo nelle ricorsioni ed è spesso usata per esprimere i loop. Questo tipo di ricorsione (una funzione che internamente richiama sé stessa) è molto efficiente nei linguaggi funzionali (anche se non in tutti, Scala per esempio che deve fare i conti con la sottostante JVM). La sua caratteristica è che il compilatore non deve allocare lo stack e perdere tempo in una nuova invocazione per ogni chiamata (tail-call optimization). Sarà difficile se non impossibile in OCaml saturare lo stack con una chiamata ricorsiva in tail recursion.

Un effetto collaterale potrebbe essere un aumento della velocità di esecuzione (anche se questionabile ed estremamente dipendente dal codice e dal compilatore). Una funzione ricorsiva in tail recursion potrebbe in linea di principio essere leggermente più veloce a causa del fatto che vengono oltrepassate le numerose invocazioni a funzione che inevitabilmente comporterebbero codice da eseguire e allocazioni sullo stack (per contro le frequenti sovrascritture potrebbero invece introdurre rallentamenti).

La funzione fib che abbiamo incontrato prima ottimizzata in tail recursion sarà:

let fib x =
  let rec fib_rec x acc piv =
    match x with
    | 0 -> acc
    | _ -> fib_rec (x - 1) piv (acc + piv)
  in
  fib_rec x 0 1
;;
(* signature: val fib : int -> int = <fun> *)

Come vedrete in seguito^3.15 questa versione sarà anche notevolmente più veloce, anche per motivi non imputabili alla stessa tail call optimization.

L'uso sapiente della ricorsione a coda rende pressoché inutili i vari cicli dei linguaggi imperativi senza le problematiche delle funzioni ricorsive degli stessi.

La programmazione funzionale con i suoi costrutti rende praticamente inutili molte delle strutture cicliche dei linguaggi imperativi. Ogni ciclo può essere espresso in termini di funzioni ricorsive ed è anche per questo motivo che i linguaggi funzionali sono particolarmente ottimizzati per questo genere di cose. A parte la possibilità in sé della ricorsività, nelle librerie base sono presenti tutta una serie di funzioni utilizzabili per iterare all'interno di collezioni ed eseguire operazioni sugli elementi che le compongono.
Il folding è una operazione molto comune che consiste nel far avvolgere gli elementi di una collezione da una funzione ed accumularne il valore di questo avvolgimento.

List.fold_left (+) 0 [1;2;3;4;5];;
(* result: - : int = 15 *)

La funzione fold_left accetta una funzione con cui avvolgere ogni elemento della lista [1;2;3;4;5], un accumulatore e la lista stessa. L'applicazione di (+) sommerà i valori della lista ponendo il risultato nell'accumulatore. Come se visualmente, sostituisse il + (che è un operatore associativo) al separatore degli elementi della lista ;.

Utilizzando le caratteristiche imperative di OCaml, si potrebbe scrivere una sum_list in questo modo (anche se non direttamente analogo all'uso di fold_left):

let sum_list list =
  let acc = ref 0 in
  let length = (List.length list) - 1 in
  for index = 0 to length do
    let value = List.nth list index in
    acc := !acc + value
  done;
  !acc
;;
(* signature: val sum_list : int list -> int = <fun> *)

Ci sono delle cose interessanti da vedere (a parte quanto possa essere brutta): l'utilizzo della parola chiave ref e del !. Il ciclo for..to..do..done credo sia chiaro e simile a qualunque altro linguaggio che lo supporta.

Dichiarare una variabile (perché adesso è una variabile) come let acc = ref 0 significa fare questo (se dovessimo fare tutto a mano):

type 'a mut = { mutable contents : 'a };;
(* signature: type 'a mut = { mutable contents : 'a } *)

let mut x = { contents = x };;
(* signature: val mut : 'a -> 'a mut = <fun>  *)

let (!@) r = r.contents;;
(* signature: val ( !@ ) : 'a mut -> 'a = <fun> *)

let (<=) r x = r.contents <- x;;
(* val ( <= ) : 'a mut -> 'a -> unit = <fun> *)

let acc = mut 10;;
(* signature: val acc : int mut = {contents = 10} *)

acc <= 20;;
(* result: - : unit = () *)

!@acc;;
(* signature: - : int = 20 *)

Ho definito un tipo mut (nella libreria è definito ref) che è un record con un campo contents mutabile (mutable). Poi alcune funzioni per gestirlo.
La stessa identica cosa è nella libreria come:

type 'a ref = { mutable contents : 'a };;
(* signature: type 'a ref = { mutable contents : 'a; } *)

let ref x = { contents = x };;
(* signature: val ref : 'a -> 'a ref = <fun> *)

let (!) r = r.contents;;
(* signature: val ( ! ) : 'a ref -> 'a = <fun> *)

let (:=) r x = r.contents <- x;;
(* signature: val ( := ) : 'a ref -> 'a -> unit = <fun> *)

Se volessimo implementare sum_list con una struttura while..do..done:

let sum_list list =
  let acc = ref 0 in
  let index = ref 0 in
  let length = (List.length list) in
  while !index < length do
    acc := !acc + (List.nth list !index );
    incr index
  done;
    !acc 
;;
(* signature: val sum_list : int list -> int = <fun> *)

La funzione fold_left ha una sua analoga contraria come fold_right, il right e left si riferisce alla direzione del folding e la versione right è normalmente meno efficiente. Il fold è chiamato in molti modi: reduce, accumulate, aggregate, compress, inject. Lo troverete in tutti i linguaggi funzionali ma non solo in quelli.

Un altro metodo importantissimo è map, che applica una funzione ad ogni elemento della collezione restituendo una collezione di risultati.

List.map ((+) 2) [1;2;3;4;5];;
(* result: - : int list = [3; 4; 5; 6; 7] *)

Applicando una funzione parzialmente applicata ((+) 2) si sommerà il numero 2 ad ogni elemento della lista di interi.

Queste due funzioni: map e fold hanno delle importanti implicazioni se usate insieme. Forse avrete sentito parlare di Map-Reduce soprattutto in merito al motore di ricerca Google. Google tramite queste tecniche è riuscita ad aumentare a dismisura la frequenza dei risultati nell'unità di tempo. La caratteristica delle due funzioni di essere senza stato ed effetti collaterali fa in modo che grosse interrogazioni sui database possano essere eseguite in parallelo con conseguente aumento delle prestazioni.

Un esempio di come usare le due funzioni insieme:

let find_if_size_is size list =
  List.fold_left
    (fun acc tpl ->
       let name, wsize = tpl in
       if wsize = size then
         acc @ [name]
       else
         acc @ [])
    []
    (List.map (fun x -> (x, String.length x)) list)
;;
(* signature: val find_if_size_is : int -> bytes list -> bytes list = <fun> *)

find_if_size_is 5 ["pippo"; "paperino"; "topolino"; "qui"; "pluto"];;
(* result: - : bytes list = ["pippo"; "pluto"] *)

Giusto per esercizio di codifica, come si può notare sono tutti argomenti della funzione fold_left (il codice potrebbe essere scritto tutto su una linea).

I linguaggi si possono dividere anche in strict (severi e sono la maggior parte) o lazy (pigri). I derivati dal ML, come OCaml, sono strict mentre altri come Haskell sono lazy. I linguaggi funzionali puri sono normalmente pigri. La lazy evaluation o call by need (invocazione a richiesta) è una strategia di valutazione che rimanda il più possibile la computazione di una espressione, almeno finché il suo valore non sia richiesto.

Attraverso la valutazione lazy si hanno alcuni vantaggi teorici:

• Aumento delle performance limitando i calcoli al solo momento richiesto, le invocazioni di funzioni o le valutazioni di valori hanno sempre un certo carico.
• La possibilità di costruire strutture complesse praticamente infinite.
• Uso di astrazioni di strutture di controllo invece di primitive, ovvero il poterle organizzare in maniera più dichiarativa e meno a statement imperativi.

Al contrario, nella valutazione strict (detta anche eager o greedy), l'espressione è valutata all'assegnamento od al binding. Questo tipo di strategia è spesso associata ai linguaggi imperativi dove l'ordine di esecuzione rispecchia l'organizzazione strutturale del codice sorgente. Un vantaggio è che elimina il tracciamento e la schedulazione delle valutazioni delle espressioni permettendo una più facile predizione del flusso logico del codice. Uno svantaggio evidente è che ci saranno computazioni non necessarie a runtime e questo obbligherà il programmatore ad una organizzazione delle istruzioni del codice ottimale.

Oggi, comunque, la maggior parte dei compilatori sono in grado di riorganizzare l'ordine delle valutazioni o di eliminare codice non utilizzato; quindi la distinzione o i pregi dell'una o dell'altra strategia si è decisamente assottigliata.

Anche nei linguaggi strict molti statement sono valutati in maniera pigra, il blocco if a then b else c verrà valutato solo se a = true. La valutazione a corto circuito (short circuit evaluation) delle strutture di controllo booleane lo è nella stessa maniera. Se in una valutazione if a || b || c then d else e, a è true, b e c non saranno valutate perché non porterebbero ulteriore informazione.

Si può simulare la lazy evaluation in un linguaggio severo tramite l'uso di funzioni che non vengono valutate immediatamente ma solo alla loro invocazione (anche se non se ne può sapere esattamente la riuscita a meno di non conoscere intimamente il comportamento del compilatore. Alcuni hanno delle strategie interne nel caso in cui una funzione sia immediatamente valutabile in fase di compilazione, oltre al fatto che gli argomenti della funzione vengono valutati prima della funzione stessa. Potrebbe non esserci alcun vantaggio in ogni caso.).

In OCaml, che è un linguaggio strict, si può avere il supporto per la valutazione lazy tramite un modulo: Lazy.

let div_by_zero = 1/0;;
(* Exception: Division_by_zero. *)

let div_by_zero2 = lazy (1/0);;
(* signature: val div_by_zero2 : int lazy_t = <lazy> *)

Lazy.force div_by_zero2;;
(* Exception: Division_by_zero. *)

div_by_zero è valutata immediatamente ed ha scatenato una eccezione, mentre div_by_zero2 no. La seconda funzione è di tipo lazy_t e non viene valutata. Non finché non viene forzata esplicitamente con Lazy.force.

In OCaml quindi, abbiamo una valutazione lazy manuale.

In Scala il meccanismo è lo stesso e per avere dei valori pigri dobbiamo dichiararli lazy, anche se non c'è bisogno di forzarli venendo valutati alla chiamata:

lazy val div_by_zero = 1/0
/* signature: div_by_zero: Int = <lazy> */

div_by_zero
/* exception: java.lang.ArithmeticException: / by zero
  at .div_by_zero$lzycompute(<console>:7)
  at .div_by_zero(<console>:7)
  ... 33 elided */

val div_by_zero = 1/0
/* exception: java.lang.ArithmeticException: / by zero
  ... 33 elided */

La tecnica detta memoization (parola coniata nel 1968 da Donald Michie²³ dal latino memoro, -as, -avi, -atum, -are) è spesso utilizzata per aumentare le prestazioni immagazzinando i risultati di invocazioni a funzione per computazioni successive. La tecnica è particolarmente utile nei linguaggi lazy per i motivi specificati sopra, ma è interessante in molti casi come per esempio il parsing di strutture ricorsive o l'analisi sintattica.

Il concetto è quello di costruire una tabella di lookup di valori di input in relazione ai rispettivi valori di output.

Come si dice spesso, l'hello world della memoization è il calcolo dell'\(nth\) elemento della sequenza di Fibonacci²⁴.

let rec fib x =
    match x with
    | 0 -> 0
    | 1 -> 1
    | x -> (fib (x - 1)) + (fib (x - 2))
;;
(* signature: val fib : int -> int = <fun> *)

I tempi per una invocazione sono con argomento 20 e 40 per esempio sono notevolmente diversi. Sulla mia macchina questi sono i valori:

• fib 20 avrà dei tempi intorno a 0.0507832ms per un risultato di 6765
• fib 40 avrà dei tempi intorno a 632.199ms per un risultato di 102334155

La differenza è enorme.

Usando la memoization potremmo accorciare i tempi notevolmente. Per prima cosa va impostato un funtore che si occupi di impostare una tabella di lookup e di cercarci di dati.

let memoize f =
  let table = Hashtbl.Poly.create () in
  (fun x ->
     match Hashtbl.find table x with
     | Some y -> y
     | None ->
       let y = f x in
       Hashtbl.add_exn table ~key:x ~data:y;
       y
  );;
(* signature: val memoize : ('a -> 'b) -> 'a -> 'b = <fun>  *)

Un classico sistema è quello di usare una tabella Hash (in questo caso la implementazione disponibile nella libreria Core⁷) per memorizzare i dati. Una versione usando direttamente la libreria standard:

let memoize f =
  let table = Hashtbl.create 12 in
  (fun x ->
     try Hashtbl.find table x with Not_found ->
       let y = f x in
       Hashtbl.add table x y;
       y
  )
;;
(* signature: val memoize : ('a -> 'b) -> 'a -> 'b = <fun>  *)

La quantità 12 passata ad Hashtbl.create è la dimensione iniziale della tabella che però potrà ingrandirsi a richiesta. La versione standard di Hashtbl.find solleverà una eccezione Not_found in caso non trovi la chiave nella tabella, mentre quella contenuta in Core un None. I tipi Some e None sono dei tipi comuni nei linguaggi funzionali ed esprimono dei valori (Options) che possono o non possono contenere dati (praticamente la risposta funzionale e sicura al Null di molti linguaggi imperativi).

Il funzionamento non è complesso: memoize prende come argomento una funzione ed alloca una tabella hash restituendo una nuova funzione; questa quando invocata controlla se un valore sia preesistente, altrimenti chiama la funzione dell'argomento e ne immagazzina il valore.

Per valutare il tempo di invocazione abbiamo questa funzione un po' rudimentale:

let time f =
  (* =Time= è un modulo di Core. *)
  let start = Time.now () in
  let x = f () in
  let stop = Time.now () in
  printf "Time: %s\n" (Time.Span.to_string (Time.diff stop start));
  x
;;
(* signature: val time : (unit -> 'a) -> 'a = <fun> *)

A questo punto ecco il sorgente completo:

open Core.Std

let time f =
  let start = Time.now () in
  let x = f () in
  let stop = Time.now () in
  printf "Time: %s\n" (Time.Span.to_string (Time.diff stop start));
  x
;;
(* signature: val time : (unit -> 'a) -> 'a = <fun> *)

let rec fib x =
    match x with
    | 0 -> 0
    | 1 -> 1
    | x -> (fib (x - 1)) + (fib (x - 2))
;;
(* signature: val fib : int -> int = <fun> *)

let memoize f =
  let table = Hashtbl.Poly.create () in
  (fun x ->
     match Hashtbl.find table x with
     | Some y -> y
     | None ->
       let y = f x in
       Hashtbl.add_exn table ~key:x ~data:y;
       y
  );;
(* signature: val memoize : ('a -> 'b) -> 'a -> 'b = <fun>  *)

let fib_memoized = memoize fib;;
(* val fib_m : int -> int = <fun> *)

let () =
  printf "Called for 20 -> fib 20\n";
  let r = time (fun () -> fib 20) in
  printf "Value: %d\n\n" r;

  printf "Called for 40 -> fib 40\n";
  let r = time (fun () -> fib 40) in
  printf "Value: %d\n\n" r;

  printf "First call for 20 -> fib_memoized 20\n";
  let r = time (fun () -> fib_memoized 20) in
  printf "Value: %d\n\n" r;

  printf "First call for 40 -> fib_memoized 40\n";
  let r = time (fun () -> fib_memoized 40) in
  printf "Value: %d\n\n" r;

  printf "Second call for 20 -> fib_memoized 20\n";
  let r = time (fun () -> fib_memoized 20) in
  printf "Value: %d\n\n" r;

  printf "Second call for 40 -> fib_memoized 40\n";
  let r = time (fun () -> fib_memoized 40) in
  printf "Value: %d\n\n" r;
;;

Compilandolo ed eseguendolo si vedrà come le seconde chiamate saranno estremamente più veloci:

$  ./fib.native

Called for 20 -> fib 20
Time: 0.0419617ms
Value: 6765

Called for 40 -> fib 40
Time: 631.014ms
Value: 102334155

First call for 20 -> fib_memoized 20
Time: 0.0429153ms
Value: 6765

First call for 40 -> fib_memoized 40
Time: 626.977ms
Value: 102334155

Second call for 20 -> fib_memoized 20
Time: 0.000953674ms
Value: 6765

Second call for 40 -> fib_memoized 40
Time: 0s
Value: 102334155

Questo è un esempio (un po' fallato e che potrebbe essere ottimizzato ancora) di come le capacità multiparadigma di OCaml siano di ausilio nella soluzione di problemi pratici, come in questo caso in cui è servita una tabella hash modificabile.

L'esempio ha però un problema: la memoize infatti così come è non è efficiente con una funzione ricorsiva. Il motivo è abbastanza semplice da intuire: le susseguenti chiamate nella ricorsione non saranno memorizzate. Ce ne possiamo rendere conto modificando la memoize in questo modo:

let memoize f =
  let table = Hashtbl.create 12 in
  (fun x ->
     Printf.printf "find: %d\n" x;
     try
       let r = Hashtbl.find table x in
       Printf.printf "found - get: %d with value: %d\n" x r;
       r
     with Not_found ->
       let y = f x in
       Printf.printf "not found - store: %d with value: %d\n" x y;
       Hashtbl.add table x y;
       y
  )
;;

Lanciando il programma si potranno vedere dei commenti di questo tipo:

$  ./fib.native

First call for 40 -> fib_memoized 40
find?: 40
not found - store: 40 with value: 102334155
Time: 560.83ms
Value: 102334155

Second call for 40 -> fib_memoized 40
find?: 40
found - get: 40 with value: 102334155
Time: 0.000953674ms
Value: 102334155

La seconda chiamata ha trovato un solo valore immagazzinato e non è quello che cercavamo di fare: tutti i risultati dovrebbero essere considerati. Andrebbe ottimizzata meglio, ma non sarà così semplice.
La memoize, quindi, funzionerà solo se unita a funzioni non ricorsive a cui però non dobbiamo rinunciare. Innanzi tutto vediamo di eliminare la parola chiave rec dalla definizione:

let fib_nrec fn x =
    match x with
    | 0 -> 0
    | 1 -> 1
    | x -> (fn (x - 1)) + (fn (x - 2))
;;
(* signature: val fib_nrec : (int -> int) -> int -> int = <fun> *)

Quello che si è preparato è un cosiddetto pattern, ovvero un modello computazionale. Si è aggiunto inevitabilmente un ulteriore parametro fn che altro non è che la funzione che andremo poi ad invocare risorsivamente.
Per provare come tutto ciò sia vero basta:

let rec fib_rec x = fib_nrec fib_rec x;;

eseguendo fib_rec 20 vedremo che sarà la stessa cosa che aver dichiarato let rec fib_rec x. Questo modo di scrivere le funzioni ricorsive (funzione non rec e compagna) porta anche ad alcuni vantaggi, come per esempio la possibilità di scrivere funzioni compagne per iniettare messaggi informativi durante la ricorsione senza alterarne il codice principale:

let rec fib_rec x = 
  Printf.printf "x: %d\n" x;
  fib_nrec fib_rec x
;;
(* signature: val fib_rec : int -> int = <fun>   *)

Quello che però noi vogliamo è un modo per applicare una memoization alla ricorsività, fare in modo quindi, che il parametro fn di fib_nrec sia una funzione in grado di ricordare i valori calcolati.
Per alcune problematiche inerenti al meccanismo di risoluzione e identificazione dei tipi in maniera non ambigua del compilatore, non possiamo usare il rec come sopra, ma abbiamo bisogno di trasformare il nostro modello computazionale in una vera funzione ricorsiva.
Il problema è che la funzione da invocare dovrà essere conosciuta a priori e per far questo abbiamo bisogno di impostare un valore funzionale mutabile e fittizio che verrà sostituito in un secondo tempo.

(* funzione iniziale conosciuta a priori *)
let fn = ref (fun _ -> assert false);;
(* signature: val fn : ('_a -> '_b) ref = {contents = <fun>} *)

(* possiamo dichiarare adesso la funzione perché fn è conosciuto *)
let fib_rec x = fib_nrec !fn x;;
(* signature: val fib_rec : int -> int = <fun>*)

(* attiviamo la memorizzazione della funzione non ricorsiva *)
let fib_rec_memo = memoize fib_rec;;
(* signature: val fib_rec_memo : int -> int = <fun>  *)

(* sostituiamo la funzione nel valore mutabile *)
fn := fib_rec_memo
(* signature: - : unit = () *)

fib_rec_memo 20;;

Scriverà:

find: 20  
find: 18 
find: 16 
find: 14  
find: 12 
find: 10  
find: 8  
find: 6  
find: 4 
find: 2 
find: 0                                                                                                                 
not found - store: 0 with value: 0
find: 1
not found - store: 1 with value: 1
not found - store: 2 with value: 1
find: 3
find: 1
found - get: 1 with value: 1
find: 2
found - get: 2 with value: 1
not found - store: 3 with value: 2
not found - store: 4 with value: 3
find: 5
find: 3
found - get: 3 with value: 2
find: 4
found - get: 4 with value: 3
not found - store: 5 with value: 5
not found - store: 6 with value: 8
find: 7
find: 5
found - get: 5 with value: 5
find: 6
found - get: 6 with value: 8
not found - store: 7 with value: 13
not found - store: 8 with value: 21
find: 9
find: 7
found - get: 7 with value: 13
find: 8
found - get: 8 with value: 21
not found - store: 9 with value: 34
not found - store: 10 with value: 55
find: 11
find: 9
found - get: 9 with value: 34
find: 10
found - get: 10 with value: 55
not found - store: 11 with value: 89
not found - store: 12 with value: 144
find: 13
find: 11
found - get: 11 with value: 89
find: 12
found - get: 12 with value: 144
not found - store: 13 with value: 233
not found - store: 14 with value: 377
find: 15
find: 13
found - get: 13 with value: 233
find: 14
found - get: 14 with value: 377
not found - store: 15 with value: 610
not found - store: 16 with value: 987
find: 17
find: 15
found - get: 15 with value: 610
find: 16
found - get: 16 with value: 987
not found - store: 17 with value: 1597
not found - store: 18 with value: 2584
find: 19
find: 17
found - get: 17 with value: 1597
find: 18
found - get: 18 with value: 2584
not found - store: 19 with value: 4181
not found - store: 20 with value: 6765
- : int = 6765

Abbiamo così la nostra funzione ricorsiva in grado di memorizzare i propri valori.
Generalizzando per funzioni con un solo parametro:

let memoize_rec fn_nrec =
  let fn = ref (fun _ -> assert false) in
  let fn_rec_memo = memoize (fun x -> fn_nrec !fn x) in
  fn := fn_rec_memo;
  fn_rec_memo
;;
(* signature: val memoize_rec : ((int -> int) -> int -> int) -> int -> int = <fun> *)

let fib_memoized_rec = memoize_rec fib_nrec;;
(* signature: val fib_memoized_rec : int -> int = <fun> *)

La funzione per calcolare la progressione di Fibonacci però non è che sia un esempio poi così utile. Vediamo come lo stesso meccanismo sia invece interessante per calcolare altro come per esempio la distanza di Levenshtein. Il calcolo di questa distanza serve per determinare quanto due stringhe siano simili ed è stata formulata dal russo Vladimir Levenshtein nel 1965. Può essere applicata a varie problematiche che non siano solo le stringhe ma anche per controllare la similarità tra suoni, immagini o altro. È il numero minimo di cambiamenti base a livello di carattere per trasformare una stringa in un'altra:

• cancellazione
• inserimento
• sostituzione

Per esempio se vogliamo trasformare pippo in pappa dobbiamo sostituire:

• la prima i in a
• l'ultima o in a

quindi abbiamo una distanza di 2, perché due sono le operazioni da fare.

La formula di Levenshtein per calcolare la distanza di due stringhe a e b è espressa matematicamente in questo modo:

In sé e per sé non è particolarmente complessa ed esprime le tre possibilità indicate sopra: il primo elemento del min rappresenta la cancellazione, il secondo l'inserimento ed il terzo la sostituzione nel caso in cui la lettera sia diversa.
L'indicazione:

sta a significare che si dovrà aggiungere 1 nel caso in cui le lettere siano diverse o 0 altrimenti (questo viene detto costo, funzione indicatrice o funzione caratteristica e indica l'appartenenza o no di un elemento ad un dato insieme matematico).

Se volessimo implementarla, si potrebbe procedere semplicemente seguendo la formula data:

let lev2 a b =
  let minimum x y z = min x (min y z) in
  let cost i j = 
    if a.[i - 1] = b.[j - 1] then 0 else 1
  in
  let rec distance i j =
    match (i, j) with
    | (i, 0) -> i
    | (0, j) -> j
    | (i, j) ->
      let deletion = (distance (i - 1) j) + 1 in
      let insertion = (distance i (j - 1)) + 1 in
      let substitution = (distance (i - 1) (j - 1)) + (cost i j) in
      minimum deletion insertion substitution
  in
  distance (String.length a) (String.length b)

Si controlla inizialmente che una delle stringhe sia nulla (lunghezza zero) e quindi la distanza sarà inevitabilmente la lunghezza dell'altra. Dopo si applicheranno ricorsivamente le regole indicate per i tre casi, compreso il calcolo del costo nella possibile sostituzione.
Questa versione però per motivi abbastanza evidenti (surplus di calcolo anche in caso di lettere uguali) non è particolarmente performante:

utop # time (fun () -> lev "levenshtein" "levenshtain");;
Time: 4.502269s  
- : int = 1  

Migliorando l'implementazione:

let lev s t =
  let minimum a b c = min a (min b c) in
  let rec distance i j =
    match (i, j) with
    | (i, 0) -> i
    | (0, j) -> j
    | (i, j) when s.[i - 1] = t.[j - 1] -> distance (i - 1) (j - 1)
    | (i, j) -> 1 + (minimum (distance (i - 1) j) (distance i (j - 1)) (distance (i - 1) (j - 1)))
  in
  distance (String.length s) (String.length t)

Questa forma non è cambiata di molto ma il guadagno in velocità è notevole:

utop # time (fun () -> lev "levenshtein" "levenshtain");;
Time: 0.011653s   
- : int = 1   

Il nodo problematico era il calcolo del costo inserito nel minimo che adesso semplicemente evitiamo o meglio mascheriamo col penultimo caso: se le lettere sono uguali passeremo oltre visto che noi stiamo cercando le differenze.

Questa implementazione del calcolo della distanza di Levenshtein è un ottimmo candidato per la memoization, avendo numerose chiamate ricorsive che elaborano nella maggior parte cose già calcolate, quindi risultati noti in precedenza.
Applicando come abbiamo visto sopra, lo stesso meccanismo usato per la sequenza di Fibonacci, potremmo avere un codice di questo tipo:

let lev_memo s t =
  let minimum a b c = min a (min b c) in
  let distance fn i j =
    match (i, j) with
    | (i, 0) -> i
    | (0, j) -> j
    | (i, j) when s.[i - 1] = t.[j - 1] -> fn (i - 1) (j - 1)
    | (i, j) -> 1 + (minimum (fn (i - 1) j) (fn i (j - 1)) (fn (i - 1) (j - 1)))
  in
  let memo fn i j =
    let fn_ref = ref (fun _ -> assert false) in
    let f = memoize (fun i j -> fn !fn_ref i j) 12 in
    fn_ref := f;
    f i j
  in
  (memo distance) (String.length s) (String.length t)

Queste saranno le performance tra la versione normale e quella memoized:

utop # time (fun () -> lev "levenshtein" "levenshtain");;
Time: 0.009528s  
- : int = 1  

utop # time (fun () -> lev_memo "levenshtein" "levenshtain");;
Time: 0.001963s 
- : int = 1  

I tempi, indipendentemente da quello che valgono queste misurazioni, si commentano da soli.

Come suggerimento implementativo dove si è parlato di funzioni anonime si è accennato a y-combinator, qualche idea? Vediamo un esempio con la sequenza di Fibonacci:

type 'a b = Roll of ('a b -> 'a)
let unroll (Roll x) = x

let y f = ((fun g -> g (Roll g)) (fun x n -> f (unroll x x) n))

let memoize f' =
  let table = Hashtbl.create 12 in
  fun f x -> begin
      Printf.printf "find?: %d\n" x;
      try
        let r = Hashtbl.find table x in
        Printf.printf "found - get: %d with value: %d\n" x r;
        r
      with Not_found ->
        let r = f' f x in
        Printf.printf "not found - store: %d with value: %d\n" x r;
        Hashtbl.add table x r;
        r
    end

let fib' fib x =
  match x with
    | 0 -> 0
    | 1 -> 1
    | _ -> fib (x - 1) + fib (x - 2)

let fib_rec_memo x = y (memoize fib') x

Per amor di informazione, l'algoritmo di Levenshtein è implementabile anche in altri modi e sfruttando le caratteristiche imperative di OCaml si potrebbe scrivere una cosa simile (ed avrà prestazioni elevate rispetto anche alla forma memoized):

let lev_iter s t =
  let n = String.length s in
  let m = String.length t in
  let d = Array.make_matrix (n + 1) (m + 1) 0 in
  for i = 1 to n do d.(i).(0) <- i done;
  for j = 1 to m do d.(0).(j) <- j done;
  let minimum x y z = min x (min y z) in
  Array.iteri (fun i a ->
      if i > 0 then
        Array.iteri (fun j _ ->
            if j > 0 then
              begin
                let cost = if s.[i - 1] = t.[j - 1] then 0 else 1 in
                let deletion = d.(i - 1).(j) + 1 in
                let insertion = d.(i).(j - 1) + 1 in
                let substitution = d.(i - 1).(j - 1) + cost in
                d.(i).(j) <- minimum deletion insertion substitution
              end
          ) a;
    ) d;
  d.(n).(m)

Con questi tempi:

iter version
Execution time: 0.000006s
2
memo version
Execution time: 0.000037s
2
slow version
Execution time: 0.673041s
2

Le s-expressions ^{25 , 26} o sexpr sono un metodo per rappresentare in forma testuale dati strutturati (serializzazione dei dati ²⁷). Sono abbastanza comuni nel mondo funzionale specialmente nella famiglia dei vari LISP, il cui codice sorgente è esso stesso una s-expression. I vari dialetti LISP infatti hanno questa particolarità.

Sono meno comuni in altri linguaggi, specialmente con la disponibilità di XML ²⁸, JSON ²⁹ o YAML ³⁰, ma offono alcuni vantaggi rispetto a questi:

• Una sexpr è più semplice da leggere.
• Non c'è bisogno di generare parser appositi (usando lex o yacc).
• Possono essere usate per definire dei mini linguaggi LISP like da usare nei programmi.

Le sexpr possono essere dei semplici atomi (l'atomo in LISP è definito di base come: una sequenza di uno o più caratteri), elementi fondamentali come numeri o coppie espresse nella forma (a . b) dove a e b sono s-expression.

Vediamo la stessa struttura dati in vari modi.

JSON:

{"dict" : { 
    "name" : "Pico", 
    "surname" : "dePaperis", 
    "age" : 65,
    "tags" : ["personaggio","fumetti"]
    "locality" : {
        "address" : "via del Campo",
        "number" : 12,
        "city" : "Paperopoli"
        }
    }
}

XML:

<dict>
  <name>Pico</name> 
  <surname>dePaperis</surname>
  <age>65</age>
  <tags>
    <tag>personaggio</tag>
    <tag>fumetti</tag>
  </tags>
  <locality>
    <address>via del Campo</address>
    <number>12</number>
    <city>Paperopoli</city>
  </locality>
</dict>

YAML:

---
dict:
  name: Pico
  surname: dePaperis
  age: 65
  tags:
    - personaggio
    - fumetti
  location:
    address: via del Campo
    number: 12
    city: Paperopoli

s-expressions:

(dict
    (name "Pico") 
    (surname "dePaperis") 
    (age 65)
    (tags (personaggio fumetti))
    (locality (dict
      (address "via del Campo")
      (number 12)
      (city "Paperopoli"))))

A voi giudicare quale sia il sistema più semplice da leggere ad occhio, ma ricordate che una s-expression è soltanto una lista annidata. A mio parere la sexpr e la forma yaml sono quelle che hanno meno rumore sintattico. La sexpr è praticamente un sorgente LISP: dict sarà una keyword che denota un dizionario, le stringhe sono chiuse tra doppi apici, tags è una lista quotata di atoms, locality un ulteriore dizionario.

Per ricapitolare le regole:

• Un atom è un simbolo è essenzialmente un valore semplice (atomico appunto), come foo, a-bar, 12.
• Le liste sono tra parentesi tonde (..), possono essere vuote, contenere atomi separati da uno spazio o da un punto o altre liste.
• Le quote sono per gli atomi che contengono parentesi o spazi.
• Il backslash è il carattere per lo escape.
• Il punto e virgola introduce i commenti.

Molti linguaggi funzionali hanno delle librerie di supporto (interne od esterne) per le s-expressions, ma comunque non è complicato programmare un parser come potete anche vedere qui: Rosetta Code, s-expressions.

La libreria Core⁷ ha un modulo apposito Sexp per la loro gestione perché è utilizzato anche come serializzatore interno.

open Core.Std
open Sexplib.Std

type person_locality = {
  address : string;
  number : int;
  city : string;
} with sexp
;;
(*
type person_locality = { address : bytes; number : int; city : bytes; }                                                 
val person_locality_of_sexp : Type.t -> person_locality = <fun>                                                         
val sexp_of_person_locality : person_locality -> Type.t = <fun> 
*)

type person = {
  name : string;
  surname : string;
  age : int;
  tags : string list;
  locality : person_locality;
} with sexp
;;
(*
type person = { name : bytes; surname : bytes; age : int; tags : bytes list; locality : person_locality; }              
val person_of_sexp : Type.t -> person = <fun>
val sexp_of_person : person -> Type.t = <fun>  
*)

let person_to_sexp person =
  let atom x = Sexp.Atom x and list x = Sexp.List x in
  list [
    list [ atom "name"; String.sexp_of_t person.name  ];
    list [ atom "surname"; String.sexp_of_t person.surname];
    list [ atom "age"; Int.sexp_of_t person.age ];
    list [ atom "tags"; List.sexp_of_t String.sexp_of_t person.tags];
    list [ atom "locality";
           list [
             list [ atom "address"; String.sexp_of_t person.locality.address ];
             list [ atom "number"; Int.sexp_of_t person.locality.number ];
             list [ atom "city"; String.sexp_of_t person.locality.city];
           ];
         ];

  ]
;;
(* val person_to_sexp : person -> Type.t = <fun> *)

let sexp_source = "
  ((name \"Pico\") 
    (surname \"dePaperis\") 
    (age 65)
    (tags (personaggio fumetti))
    (locality (
      (address \"via del Campo\")
      (number 12)
      (city \"Paperopoli\"))))"
;;
let se1 = Sexp.of_string sexp_source;;
(*
val se1 : Type.t = 
 ((name Pico) 
  (surname dePaperis) 
  (age 65) 
  (tags (personaggio fumetti))
  (locality (
    (address "via del Campo") 
    (number 12) 
    (city Paperopoli)))) 
*)

let se2 = person_to_sexp {
    name = "Pico";
    surname = "dePaperis";
    age = 65;
    tags = ["personaggio"; "fumetti"];
    locality = {
      address = "via del campo";
      number = 12;
      city = "Paperopoli"
    }
  }
;;
(*
val se2 : Type.t = 
 ((name Pico) 
  (surname dePaperis) 
  (age 65) 
  (tags (personaggio fumetti))
  (locality (
     (address "via del campo") 
     (number 12) 
     (city Paperopoli))))  
*)

let person_data = {
  name = "Pico";
  surname = "dePaperis";
  age = 65;
  tags = ["personaggio"; "fumetti"];
  locality = {
    address = "via del campo";
    number = 12;
    city = "Paperopoli";
  }
}
;;
(*
val person_data : person = 
{
  name = "Pico"; 
  surname = "dePaperis"; 
  age = 65; 
  tags = ["personaggio"; "fumetti"]; 
  locality = {
    address = "via del campo"; 
    number = 12; 
    city = "Paperopoli"
    }
} 
*)

let se3 = sexp_of_person person_data;;
(*
val se3 : Type.t = 
 ((name Pico) 
  (surname dePaperis) 
  (age 65) 
  (tags (personaggio fumetti))
  (locality (
    (address "via del campo") 
    (number 12) 
    (city Paperopoli)))) 
*)

let se3_deser = person_of_sexp se3;;
(*
val se3_deser : person =
{
  name = "Pico"; 
  surname = "dePaperis"; 
  age = 65; 
  tags = ["personaggio"; "fumetti"]; 
  locality = {
    address = "via del campo"; 
    number = 12; 
    city = "Paperopoli"
    }
} 
*)

let () =

  printf "\nPerson data\n";
  printf "  name: %s\n" se3_deser.name;
  printf "  surname: %s\n" se3_deser.surname;
  printf "  age: %d\n" se3_deser.age;
  printf "  tags: %s\n" (String.concat ~sep:"," se3_deser.tags);
  printf "  locality\n";
  printf "    address: %s\n" se3_deser.locality.address;
  printf "    number: %d\n" se3_deser.locality.number;
  printf "    city: %s\n" se3_deser.locality.city;

  printf "==========================================0\n";

  printf "Sexp from source string:\n";
  printf "\n%s\n" (Sexp.to_string se1);
  printf "==========================================0\n";

  printf "Sexp programatically from struct:\n";
  printf "\n%s\n" (Sexp.to_string se2);
  printf "==========================================0\n";

  printf "Sexp Sexplib emitter from struct:\n";
  printf "\n%s\n" (Sexp.to_string (se3));

In questo esempio si è serializzata e deserializzata una struttura (struct) per dimostrarne il funzionamento.

./sexpr_test.native 

Person data
  name: Pico
  surname: dePaperis
  age: 65
  tags: personaggio,fumetti
  locality
    address: via del campo
    number: 12
    city: Paperopoli
==========================================0
Sexp from source string:

((name Pico)(surname dePaperis)(age 65)(tags(personaggio fumetti))
(locality((address"via del Campo")(number 12)(city Paperopoli))))
==========================================0
Sexp programatically from struct:

((name Pico)(surname dePaperis)(age 65)(tags(personaggio fumetti))
(locality((address"via del campo")(number 12)(city Paperopoli))))
==========================================0
Sexp Sexplib emitter from struct:

((name Pico)(surname dePaperis)(age 65)(tags(personaggio fumetti))
(locality((address"via del campo")(number 12)(city Paperopoli))))

Come ho specificato prima è stata usata Core⁷, ma Batteries¹⁷ per esempio ha un supporto analogo. Il modulo Sexplib è molto sofisticato e va molto al di là del semplice codice che potrete aver trovato su Rosetta Code; come si può vedere nelle signature delle varie parti Sexplib, per esempio, genera una buona quantità di funzioni helper che facilitano di molto il compito.

I linguaggi funzionali sono spesso accusati di essere lenti. Chi lo fa non lo dice generalmente a ragion veduta e si riferisce alle prime implementazioni arcaiche degli interpreti LISP. Linguaggi come OCaml, per esempio, sono estremamente efficienti nonostante la presenza di un garbage collector.

In questa sezione vi mostrerò varie versioni dello stesso codice con un benchmark casalingo. È chiaro che, come tutti i benchmark non abbia un valore assoluto e debba essere preso con le molle.

Vediamo una prima implementazione:

let time f =
  let start = Sys.time () in
  let x = f () in
  let stop = Sys.time () in
  Printf.printf "Time: %fs\n%!" (stop -. start);
  x
;;

let rec fib x =
  match x with
  | 0 -> 0
  | 1 -> 1
  | x -> (fib (x - 1)) + (fib (x - 2))
;;

let range a b =
  let rec aux a b =
    if a > b then [] else a :: aux (a + 1) b  in
  if a > b then List.rev (aux b a) else aux a b
;;

let fib_range range =
  let print_value value =
    let r = fib value in
    Printf.fprintf stdout "fib (%d): %d\n" value r;
    flush stdout
  in
  List.iter print_value range
;;

let () =
  time (fun () -> fib_range (range 0 39));
;;

In questo codice si cerca di mostrare quanto tempo serva per calcolare dei numeri di Fibonacci per quaranta interi in successione.
Compilando ed eseguendo il programma avremo questo risultato:

$  ./fib.native
fib (0): 0
fib (1): 1
fib (2): 1
fib (3): 2
fib (4): 3
fib (5): 5
fib (6): 8
fib (7): 13
fib (8): 21
fib (9): 34
fib (10): 55
fib (11): 89
fib (12): 144
fib (13): 233
fib (14): 377
fib (15): 610
fib (16): 987
fib (17): 1597
fib (18): 2584
fib (19): 4181
fib (20): 6765
fib (21): 10946
fib (22): 17711
fib (23): 28657
fib (24): 46368
fib (25): 75025
fib (26): 121393
fib (27): 196418
fib (28): 317811
fib (29): 514229
fib (30): 832040
fib (31): 1346269
fib (32): 2178309
fib (33): 3524578
fib (34): 5702887
fib (35): 9227465
fib (36): 14930352
fib (37): 24157817
fib (38): 39088169
fib (39): 63245986
Time: 1.039338s

Per ogni numero viene invocata la funzione fib e se ne stampa il valore, alla fine il tempo occorso.
Cambiamo adesso con una versione in cui fib, che è una funzione ricorsiva, è implementata in tail recursion usando un accumulatore:

let time f =
  let start = Sys.time () in
  let x = f () in
  let stop = Sys.time () in
  Printf.printf "Time: %fs\n%!" (stop -. start);
  x
;;

let fib x =
  let rec fib_rec x acc piv =
    match x with
    | 0 -> acc
    | _ -> fib_rec (x - 1) piv (acc + piv)
  in
  fib_rec x 0 1
;;

let range a b =
  let rec aux a b =
    if a > b then [] else a :: aux (a + 1) b  in
  if a > b then List.rev (aux b a) else aux a b
;;

let fib_range range =
  let print_value value =
    let r = fib value in
    Printf.fprintf stdout "fib (%d): %d\n" value r;
    flush stdout
  in
  List.iter print_value range
;;

let () =
  time (fun () -> fib_range (range 0 39));
;;

Il codice, come si può vedere, è pressoché identico a parte fib. Eseguendo e stupendoci:

$  ./fib.native        
fib (0): 0
fib (1): 1
fib (2): 1
fib (3): 2
fib (4): 3
fib (5): 5
fib (6): 8
fib (7): 13
fib (8): 21
fib (9): 34
fib (10): 55
fib (11): 89
fib (12): 144
fib (13): 233
fib (14): 377
fib (15): 610
fib (16): 987
fib (17): 1597
fib (18): 2584
fib (19): 4181
fib (20): 6765
fib (21): 10946
fib (22): 17711
fib (23): 28657
fib (24): 46368
fib (25): 75025
fib (26): 121393
fib (27): 196418
fib (28): 317811
fib (29): 514229
fib (30): 832040
fib (31): 1346269
fib (32): 2178309
fib (33): 3524578
fib (34): 5702887
fib (35): 9227465
fib (36): 14930352
fib (37): 24157817
fib (38): 39088169
fib (39): 63245986
Time: 0.000274s

Notato il tempo? Questa versione in tail call con accumulatore è decisamente più veloce.
Come nota vi dico che se avessi usato la libreria Core ⁷ avrei avuto prestazioni migliori (almeno nei miei test).

Vediamo OCaml rispetto ad altri linguaggi oggi di moda.

Go ³¹

package main

import (
  "fmt"
  "time"
)

func fib(n int) int {
  if n < 2 {
    return n
  }
  return fib(n - 1) + fib(n - 2)
}

func main() {
  start := time.Now()
  for n := 0; n < 40; n++ {
    fmt.Printf("fib (%d) = %d\n", n, fib(n))
  }
  fmt.Printf("Time %s\n", time.Since(start))
}

Dopo averlo compilato ed eseguito:

$  ./fib 
fib (0) = 0
fib (1) = 1
fib (2) = 1
fib (3) = 2
fib (4) = 3
fib (5) = 5
fib (6) = 8
fib (7) = 13
fib (8) = 21
fib (9) = 34
fib (10) = 55
fib (11) = 89
fib (12) = 144
fib (13) = 233
fib (14) = 377
fib (15) = 610
fib (16) = 987
fib (17) = 1597
fib (18) = 2584
fib (19) = 4181
fib (20) = 6765
fib (21) = 10946
fib (22) = 17711
fib (23) = 28657
fib (24) = 46368
fib (25) = 75025
fib (26) = 121393
fib (27) = 196418
fib (28) = 317811
fib (29) = 514229
fib (30) = 832040
fib (31) = 1346269
fib (32) = 2178309
fib (33) = 3524578
fib (34) = 5702887
fib (35) = 9227465
fib (36) = 14930352
fib (37) = 24157817
fib (38) = 39088169
fib (39) = 63245986
Time 1.505562721s

In questa versione con fib semplicemente ricorsiva OCaml è notevolmente più veloce. Va notata anche una cosa in OCaml non abbiamo un costruttore per dei tipi Range come in Go ed è più performante nonostante debba perdere tempo nella costruzione di una lista di interi.