Monday, January 15, 2007 

Leaky Abstractions and Tacit Infrastructures

It's official: some of my readers are quite smart :-). While writing my previous post, I left out some ideas, as it was already too long. The material that didn't make it was about an apparent inconsistency with an old post, The perils of abstraction, where I stated "We can safely abstract away what we know, not what we don't know". The excellent reference to Joel's The Law of Leaky Abstractions points exactly in the same direction!
Although Joel's law ("All non-trivial abstractions, to some degree, are leaky") is not exactly the same as mine, the consequences of what we said are remarkably similar.

Now, there seems to be a contradiction between the idea that abstractions are leaky, and therefore you have to know what's below them anyway, and the idea that a true infrastructure must completely hide what's below. I could simply call H.L. Mencken to the rescue :-), but I'll try to dig a little deeper on the subject.

I believe an abstraction can leak in 3 fundamental ways (with some middle ground I'll cover later).

1) Functional leak
It's when you reasonably expect something to work, but it doesn't. Joel's example of a string class in C++, not allowing "foo" + "bar", is obviously about a functional leak.

2) Non-functional leak
It's when through the use of an abstraction, you change some non-functional property, like performance. My example of virtual memory (which I still consider a good abstraction/infrastructure) surely has non-functional leaks. When Joel talks about iterating over a matrix, or using the best SQL statement, that's again about non-functional leaks.

3) Debugging leak
It's when you can forget about the internals of an abstraction/infrastructure as long as it's working, but you have to know what's going on under the hood to understand faulty code. Joel's examples of ASP, VB, COM, etc. all fall here, and it's indeed a very common kind of leakage. Code generators are prime candidates for debugging leaks.

Now, in most cases, non-functional leaks are to be expected even in good abstractions/infrastructures. Ideally, they will be documented. Ideally, we would have a quantitative model for performance figures and so on (even a coarse one would do). In practice, they are often undocumented but still accepted in many modern systems.

Functional leaks are different. From the "Listen to your Tools and Materials" perspective, a functional leak is your material telling you "fix me". If you can't, maybe it's your tool telling you "fix me". For instance, there is no conceptual (or even practical) barrier that prevents C++ to be extended, by relaxing some constraints on operator overloading, so that

std::string operator +( const char*, const char* )

could be made legal (of course, that's not legal C++ today)

Debugging leaks are the main reason behind my "We can safely abstract away what we know, not what we don't know". They are by far the most common leak.

Where is the middle ground? Quality of service issues are difficult to classify as functional or non-functional, so you'll need some judgment call there.

Note that some of Joel's examples (TCP, the file system) do not really look like leaky abstractions to me. In both cases, the abstraction is actually promising you to do something OR give you back an error. Of course, you have to handle the error :-).

To recap:

- Even a good abstraction can be leaky. However, it's still useful to have those abstractions, because they will lower your cognitive load in many cases.

- Some leaks are worse than other. Functional leaks add to your cognitive load while coding. Non-functional leaks, depending on your application domain, can be quite harmless or may add to your cognitive load during design AND coding (I've more to say on this, but it will have to wait). Debugging leaks add to your cognitive load while debugging, and in a sense while testing too.

- Back to the idea of infrastructure, we want a real infrastructure to go largely unnoticed. Therefore, functional leaks are bad, and debugging leaks are bad too. Depending on the infrastructure, some non-functional leaks can be tolerated, or even expected.
Comments:
Gentile Dr.Pescio,
mi scuso in anticipo per la lunghezza di questo commento, ma la seguo da molti anni e questa e' la prima occasione di corrispondere con Lei.
Premetto che non mi occupo di programmazione a livello professionale: sono un giovane neurologo che trova nella programmazione, oltre ad un hobby, una ricca sorgente di stimoli su tematiche epistemico-cognitive.

Venendo al tema delle "leaky abstractions": ho una buona familiarita' con il lavoro di Bertrand Meyer e pertanto la mia discussione ne e' chiaramente influenzata.
1) Functional leak. Dal punto di vista della ADT theory, i functional leaks semplicemente non esistono: un'astrazione e' definita unicamente dalle operazione applicabili ad essa e dalle regole di consistenza semantica specificata (asserzioni, assiomi, invarianti, pre/postcondizioni...).
2) Non-functional leaks: il problema e' reale, benche' alcuni lavori di Meyer sembravano indicare un tentativo di ricondurli al primo punto. Per esempio ricordo che nella serie "trusted components for the industry" (se ritiene posso cercare il riferimento bibliografico esatto) Meyer proponeva "advanced contracts" che per esempio esprimessero anche vincoli su complessita' computazionale, memory usage, prestazioni, etc. Certo, rimane il fatto che anche ad un livello unicamente strutturale i contratti non hanno TUTTA la potenza espressiva che vorremmo... Ma mi pare comunque un buon spunto di ricerca.
3) Debugging leak: questo e' certamente il punto piu' ostico, sul quale in tutta sincerita' non ho nulla da aggiungere a quanto gia' detto con grande chiarezza e competenza da Lei.

Con grande stima,
Guido Marongiu
guidomarongiu@yahoo.it
skgtgum@ucl.ac.uk
 
Ottimi spunti, che mi permettono di chiarire meglio il concetto di functional leak.

Parto pero' dal punto (2) che e' piu' facile :-)

Su molti aspetti computazionali la teoria e' molto ben consolidata a livello di ADT. Si "sa" come caratterizzare un algoritmo rispetto all'ordine di complessita' nel caso medio e pessimo, lo stesso si "sa" fare per quanto riguarda l'occupazione di memoria, ecc.

Diventa gia' piu' difficile gestire la composizione di queste conoscenze. Se nel mio algoritmo uso qualcosa che N * Ln( N ), ma dentro un loop in cui entro solo se non ho trovato un elemento in una mappa ecc ecc, non e' affatto semplice (per il caso medio - piu' facile per il caso pessimo) trovare [e dimostrare] l'ordine di complessita' risultante. Non e' neppure un processo automatizzabile piu' di tanto (soliti tentativi con theorem prover).

Ma fino qui e' ancora tutto facile. Diventa improvvisamente piu' complicato quando arriviamo a parlare di concorrenza. Qui saltano subito fuori modelli markoviani piuttosto complicati. In alcuni vecchi post accennavo a "quantitative methods" che invariabilmente si dividono tra quelli semplici e molto approssimati, e quelli che cercano maggior precisione a scapito di una complessita' interna davvero notevole.

Trascurando ancora alcuni elementi reali (che poi emergono) abbiamo comunque gia' dei problemi ad estrarre da tutto questo dei numeri utili/realistici. La teoria degli ordini di complessita' si focalizza (giustamente) sugli andamenti asintotici. Tutto il resto finisce in "trascurabili" :-) costanti il cui valore non e' noto (e non definibile a livello di algoritmo/componente, perche' dipende ad es. dalla CPU reale su cui gira il codice, ad es. dall'efficacia del branch predictor). Pero' nella pratica queste costanti ci servono, per dire ad es. quante operazioni al secondo sapremo gestire. Qui si ricorre tipicamente al test, con tutti i limiti del caso.

In realta' qui c'e' proprio un problema di fondo. Per quanto la teoria della complessita' sia assolutamente fondamentale per programmare / progettare bene, non si puo' sperare che sia un rimedio ai non-functional leak, perche' la teoria stessa e' soggetta a non-functional leak!
Lo spiego meglio :-), anche perche' la cosa si applica ad ogni tentativo model-based.
Nei casi concreti, le prestazioni reali di un sistema dipendono da una miriade di fattori. Uno, come dicevamo, e' la CPU con tutte le sue strategie sempre piu' complesse. Uno e' il compilatore, e la qualita' del codice che genera. Uno sono i pattern di utilizzo della memoria, con conseguente cache hit/miss. Su un sistema multiprocessore, uno e' la collocazione della cache di primo/secondo livello, incrociato con i pattern di uso della memoria e gli eventuali problemi di invalidazione della cache line. Poi salta fuori il problema della memoria virtuale, con swapping o persino thrashing. Anche rimanendo dentro ad un programma monolitico, abbiamo problemi se lo heap viene troppo frammentato. Ecc ecc, e sto trascurando tutto quanto non e' strettamente computazionale (quindi tutta la complessita' aggiuntiva di interrupt vari, I/O su disco, su rete, su dispositivi di vario tipo, l'influenza del processore grafico in certe applicazioni, ecc).
La realta' e' che per necessita' il programmatore lavora ad un livello piu' astratto, ma che tutte queste cose prima o poi finiscono per saltare fuori (banalmente, come prestazioni del risultato finale).
Il problema e' che un modello realistico di un sistema cosi' complesso sarebbe a sua volta troppo complesso per essere utile. E quindi ogni tentativo modellistico si basa su delle astrazioni [piuttosto grossolane]. Che sono leaky, perche' poi in pratica la realta' diverge in modo anche molto forte (se ad es. non usiamo bene la cache, molto codice numerico ad alte prestazioni diventa a basse prestazioni :-).

Provo a dire qualcosa sui functional leak, dove la questione e' piu' sottile. Riprendo la definizione che ho dato (che forse andrebbe migliorata):
"It's when you reasonably expect something to work, but it doesn't."
Ora tutto sta a vedere cosa significa "reasonably expect". Se significa "rispetta il contratto della classe" allora, ovviamente, i functional leak non esistono. Ovviamente, in pratica, non e' cosi'. Le astrazioni sono functionally leaky perche' sono incomplete e/o sbagliate, e quindi anche il loro contratto e' incompleto e/o sbagliato. In questi casi mi tocca capire qualcosa in piu', l'astrazione non mi basta, ed e' cosi' che si scopre il functional leak.
Incomplete rispetto a cosa? Qui sta il punto delicato. Incomplete rispetto a quello che il programmatore e' portato ad assumere, dovrei forse dire rispetto ad una non ben specificata "astrazione ideale" del concetto.
L'esempio di Joel su "foo" + "bar" e' abbastanza rappresentativo. Posso fare "foo" + bar o foo + "bar" (se foo e bar sono variabili di tipo string) perche' nel contratto c'e' quell'operatore +. Ma il contratto e' incompleto (per colpa del linguaggio, ma la cosa e' tutto sommato irrilevante in senso generale). L'astrazione si rivela incompleta, arrivata ad un certo punto si rompe e mi fa vedere che sotto ci sono dei const char* che non volevo vedere...
 
Una presentazione di Alex Martelli sulle astrazioni:
Abstraction as Leverage
http://www.aleax.it/accu_abst.pdf
 
Post a Comment

<< Home