risorse | funny code
Ho seguito – su YouTube – l'intervento “Funny Code” che Matteo Baglini ha tenuto alla NoSlidesConf di Bologna a inizio dicembre 2016[1]. In quell'occasione Matteo ha mostrato come implementare la funzione di valutazione della lunghezza di una lista, e la lista stessa, per mezzo di sole funzioni. Lo fa per passi, partendo da un'implementazione di tipo imperativo/procedurale in JavaScript. Poiché certi passaggi mi sono risultati ostici, ho voluto ripercorrerne le orme. Ho usato il C++14 e il compilatore GCC v. 6.1.0 della distribuzione nuwen di MinGW (v. 14.0) su una macchina Windows 7 Pro 64 bit.
Ho cercato di rimanere il più fedele possibile al percorso seguito da Matteo, ma a causa delle differenze tra i due linguaggi e delle rispettive librerie, in alcune (poche) occasioni si sono resi necessari interventi ad-hoc.
Si parte da una soluzione di tipo procedurale:
#include <iostream>
#include <list>
const std::list<int> empty_list = {};
const std::list<int> one_item_list = { 1 };
const std::list<int> many_items_list = { 1, 2, 3 };
template <class T>
int length(T list) {
int count = 0;
auto i = std::begin(list);
while (i != std::end(list)) {
++i;
++count;
}
return count;
}
int main() {
std::cout
<< length(empty_list) << " "
<< length(one_item_list) << " "
<< length(many_items_list) << "\n";
}
// output: 0 1 3
Il primo passo verso un'implementazione puramente funzionale è quello di sostituire il ciclo con una chiamata ricorsiva:
template <class T>
int length(T list) {
int count = 0;
auto i = std::begin(list);
while (i != std::end(list)) {
++i;
++count;
}
return count;
return list == empty_list
? 0
: 1 + length(T(++std::begin(list), std::end(list)));
}
...
// output: 0 1 3
L'obiettivo successivo è quello di eliminare la segmentazione esplicita della lista introducendo un'implementazione a oggetti della stessa in forma di struttura di dati persistente, tipica dei linguaggi funzionali:
#include <iostream>#include <list>#include <memory> struct Node; using List = std::shared_ptr<Node>; struct Node { int first; List rest; Node (int first_, List rest_) : first(first_), rest(rest_) {} };const std::list<int> empty_list = {};const List empty_list;const std::list<int> one_item_list = { 1 };const List one_item_list = std::make_shared<Node>(1, empty_list);const std::list<int> many_items_list = { 1, 2, 3 };const List many_items_list = std::make_shared<Node>(1, std::make_shared<Node>(2, std::make_shared<Node>(3, empty_list))); template <class T> int length(T list) { return list == empty_list ? 0 : 1 + length(T(++std::begin(list), std::end(list))list->rest); } ... // output: 0 1 3
Questo passo avrebbe potuto essere affrontato più tardi, in modo da risolvere il problema della ricorsione una volta per tutte anziché ritornarci subito dopo.
Ciò che a prima vista potrebbe sembrare una contraddizione in termini è in realtà un modo alternativo di realizzare una ricorsione: anziché dare luogo ad una serie di chiamate annidate che viene risolta all'indietro una volta raggiunto il caso base (ovvero un linear recursive process), si passa lo stato della computazione da una chiamata all'altra, realizzando un linear iterative process (la procedura è ricorsiva, perché invoca sé stessa, non lo è il processo sottostante – cfr. [2] per dettagli). Lo stato in questo caso è costituito dalla lunghezza della porzione di lista già considerata e la porzione di lista rimanente:
template <class T>
int length(T list, int acc) {
return list == empty_list
? 0 acc
: 1 + length(list->rest, 1 + acc);
}
Questa implementazione ha il vantaggio di abilitare la tail-call optimization, che garantisce l'esecuzione della procedura ricorsiva utilizzando una quantità di memoria indipendente dal numero di chiamate, scongiurando il rischio di uno stack overflow.
Avendo modificato la signature della funzione length, è necessario ripristinare l'interfaccia originale:
template <class T>
int length(T list, int acc) {
return list == empty_list
? acc
: length(list->rest, 1 + acc);
}
template <class T>
int length(T list) {
return length(list, 0);
}
...
// output: 0 1 3
Il passo successivo consiste nel realizzare il contenitore in termini di funzioni. Occorre a questo punto aprire un breve inciso. Un valore costante può essere facilmente reso come funzione:
#include <iostream>
const auto zero = []{ return 0; };
int main() {
std::cout << zero() << "\n";
}
// output: 0
Non è certo pratico definire una funzione per ogni valore possibile; conviene utilizzare una funzione per creare le funzioni costanti che di volta in volta si rendono necessarie:
#include <iostream>
const auto zero = []{ return 0; };
const auto wrap = [](auto x) { return [x]() { return x; }; };
const auto one = wrap(1);
int main() {
std::cout << zero() << " " << one() << "\n";
}
// output: 0 1
Lo scopo finale è quello di costruire due funzioni che mimino l'accesso ai membri first e rest dell'oggetto Node. Aggiungendo un parametro alla funzione ritornata dalla factory wrap si ottiene immediatamente il primo:
#include <iostream>const auto zero = []{ return 0; };const auto wrap = [](auto x) { return [x](auto) { return x; }; };const auto one = wrap(1);int main() { std::cout <<zero()wrap(0)(1) << " "one()wrap(1)(0) << "\n"; } // output: 0 1
wrap ritorna il primo dei due argomenti passati, e può quindi essere considerato un accessor per il membro first. Usando la notazione JavaScript, la definizione di wrap è la seguente:
wrap = (x) => (y) => x
A conferma di quanto appena detto:
wrap(a)(b) = [(y) => a](b) = a
Per recuperare il secondo argomento, Matteo compone wrap con l'identità, che in questo contesto denomina delay per il fatto che ritarda l'applicazione di wrap al secondo parametro. Sempre in notazione JavaScript:
delay = (x) => x
L'effetto di delay è il seguente:
wrap(delay)(a)(b) = [(y) => delay](a)(b) = delay(b) = b
In C++ diventa:
#include <iostream>
const auto wrap = [](auto x) { return [x](auto) { return x; }; };
const auto delay = [](auto x) { return x; };
int main() {
std::cout
<< wrap(0)(1) << " "
<< wrap(1)(0) << " "
<< wrap(delay)(0)(1) << " "
<< wrap(delay)(1)(0) << "\n";
}
// output: 0 1 1 0
Dichiarando esplicitamente i due combinatori:
...
const auto first = wrap;
const auto rest = wrap(delay);
int main() {
std::cout
<< wrap first(0)(1) << " "
<< wrap first(1)(0) << " "
<< wrap(delay) rest(0)(1) << " "
<< wrap(delay) rest(1)(0) << "\n";
}
// output: 0 1 1 0
Resta a questo punto da definire una funzione che impacchetti i due argomenti e al cui valore di ritorno possa essere applicato uno tra first/rest al fine di estrarre la componente desiderata all'occorrenza. In prima istanza si può definire una funzione pair che accetta due argomenti e ritorna una funzione che prende a sua volta il selettore da applicare alla coppia appena creata:
...
const auto pair = [](auto x, auto y) {
return [x, y](auto select) {
return select(x)(y);
};
};
int main() {
std::cout
<< first(0)(1) pair(0, 1)(first) << " "
<< first(1)(0) pair(1, 0)(first) << " "
<< rest(0)(1) pair(0, 1)(rest) << " "
<< rest(1)(0) pair(1, 0)(rest) << "\n";
}
// output: 0 1 1 0
Gunti a questo punto, Matteo opta per una funzione pair costruita su funzioni unarie:
const auto pair = [](auto x, auto y) { return [x](auto y) { return [x, y](auto select) { return select(x)(y); }; }; }; int main() { std::cout << pair(0,)(1)(first) << " " << pair(1,)(0)(first) << " " << pair(0,)(1)(rest) << " " << pair(1,)(0)(rest) << "\n"; } // output: 0 1 1 0
Si può ora procedere alla sostituzione della lista:
#include <iostream>#include <memory>struct Node; using List = std::shared_ptr<Node>;struct Node { int first; List rest; Node (int first_, List rest_) : first(first_), rest(rest_) {} };const auto wrap = [](auto x) { return [x](auto) { return x; }; }; const auto delay = [](auto x) { return x; }; const auto first = wrap; const auto rest = wrap(delay); const auto pair = [](auto x) { return [x](auto y) { return [x, y](auto sel) { return sel(x)(y); }; }; };const List empty_list;const auto empty_list = pair(-1)(-1);const List one_item_list = std::make_shared<Node>(1, empty_list);const auto one_item_list = pair(1)(empty_list);const List many_items_list = std::make_shared<Node>(1, std::make_shared<Node>(2, std::make_shared<Node>(3, empty_list)));const auto many_items_list = pair(1)(pair(2)(pair(3)(empty_list))); template <class T> int length(T list, int acc) { return list(first) ==empty_list-1 ? acc : length(list->(rest), 1 + acc); // <--- ERROR! } template <class T> int length(T list) { return length(list, 0); } int main() { std::cout << length(empty_list) << " " << length(one_item_list) << " " << length(many_items_list) << "\n"; }
Il codice in questione, oltre ad essere poco elegante – vedi ad esempio l'uso del terminatore arbitrario -1 –, contiene un errore alla linea indicata, perché evidentemente il compilatore tenta di istanziare la funzione con T pari a int che ovviamente non supporta l'operatore function call. Fortunatamente il problema si risolve proprio con l'ultima trasformazione proposta da Matteo.
L'if nascosto nell'operatore ternario è l'ultimo retaggio non funzionale del programma. Come eliminarlo? Anche in questo caso si ricorre a una dependency injection, fornendo dall'esterno l'operazione da compiere in funzione del contesto nel quale si sta operando. Dovendo discriminare tra lista vuota e lista non vuota, utilizziamo delle funzioni binarie. Il primo argomento verrà valutato in corrispondenza di una lista vuota:
const auto empty_list = [](auto when_empty, auto) { return when_empty(); };
Il secondo argomento viene invece nel caso di una lista non vuota. Per semplicità, introduciamo una nuova funzione, node, che rappresenta un elemento di una lista:
const auto node = [](auto, auto unless_empty) { return unless_empty(...); };
unless_empty opera sulle componenti della lista:
const auto node = [](auto, auto unless_empty) { return unless_empty(pair(x)(y)); };
Le componenti x e y sono passate con una catena di funzioni unarie, come già fatto per pair:
const auto node = [](auto x) {
return [x](auto y) {
return [x, y](auto, auto unless_empty) {
return unless_empty(pair(x)(y));
};
};
};
node è dunque una combinazione di una factory di oggetti pair e di una trasformazione degli stessi. Nel caso di length, la trasformazione consiste nel ricavare il rest della lista originale:
#include <iostream>
const auto wrap = [](auto x) { return [x](auto) { return x; }; };
const auto delay = [](auto x) { return x; };
const auto first = wrap;
const auto rest = wrap(delay);
const auto pair = [](auto x) {
return [x](auto y) {
return [x, y](auto sel) {
return sel(x)(y);
};
};
};
const auto empty_list = [](auto when_empty, auto) { return when_empty(); };
const auto node = [](auto x) {
return [x](auto y) {
return [x, y](auto, auto unless_empty) {
return unless_empty(pair(x)(y));
};
};
};
const auto one_item_list = node(1)(empty_list);
const auto many_items_list = node(1)(node(2)(node(3)(empty_list)));
template <class T>
int length(T list, int acc) {
return list(first) == -1
? acc
: length(list(rest), 1 + acc);
return list(
[acc]() { return acc; }, // when_empty
[acc](auto pair) { return length(pair(rest), 1 + acc); }); // unless_empty
}
template <class T>
int length(T list) {
return length(list, 0);
}
int main() {
std::cout
<< length(empty_list) << " "
<< length(one_item_list) << " "
<< length(many_items_list) << "\n";
}
// output: 0 1 3
Qui si conclude l'intervento di Matteo.
Giunti a questo punto potrebbe aver senso mostrare che l'infrastruttura ottenuta consente di sviluppare altre funzionalità con poca fatica, come ad esempio la stampa dei valori in lista:
template <class T>
void print(T list) {
return list(
[]() {},
[](auto pair_) { std::cout << pair_(first) << " "; print(pair_(rest)); });
}
int main() {
...
print(many_items_list);
}
// output: 1 2 3
Con altrettanta facilità si può applicare una trasformazione a tutti gli elementi della lista:
template <class T>
T timesTwo(T list) {
return list(
[]() { return empty_list; },
[](auto pair_) { return node(pair_(first)*2)(timesTwo(pair_(rest))); });
}
int main() {
...
print(timesTwo(many_items_list));
}
// output: 2 4 6
Pagina modificata il 03/02/2017