Linguaggi / Ruby

La magia di call/cc

Abstract
call-with-current-continuation, per gli amici call/cc, è una di quelle cose di cui non molti hanno sentito parlare e pochi comprendono davvero. Io non sono nella fascia del comprendono davvero, ma quel che ho capito spero di riuscire a spiegarlo, cancellando un po' di quell'aura magica che circonda questo meccanismo.

Data di stesura: 09/08/2004
Data di pubblicazione: 20/09/2004
Ultima modifica: 04/04/2006

di Gabriele Renzi

In collaborazione con Gruppo Utenti Ruby Italia

Contenuti

Conclusione

Uno dei problemi nella comprensione di call/cc è che questa funzionalità non è molto diffusa.
Pochi sono i linguaggi/piattaforme che la forniscono come base, tra questi Scheme, SML/NJ, e Ruby. Altri linguaggi, come CommonLisp o SmallTalk riescono in vari modi ad 'emularè questa caratteristica.
Altri linguaggi ancora, esistono su piattaforme che mettono a disposizione funzioni che permettono di manipolare le continuazioni, ad esempio StacklessPython^[1] (interprete python), o l'interprete JavaScript integrato in cocoon^[2], pur non avendole nella versione principale.
Questi sono buoni esempi del fatto che call/cc non dipende da costrutti sintattici particolari (come throws in java o lambda in python), ma viene invocata come una "normale" funzione di libreria.

[nota: in Scheme, ad esempio, le strutture di controllo sono implementate con call/cc, ma call/cc non rappresenta una forma particolare come define o lambda, bensì una semplice funzione]

Infine, va ricordato il linguaggio unlambda, che ha solo tre istruzioni, di cui una (k) dovrebbe corrispondere a call/cc. Dico dovrebbe perché il codice unlambda non è particolarmente comprensibile: la serie di fibonacci in unlambda si calcola così:

```s``s``sii``s`kk`ki`ki``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s``s`ks`

`s`kk`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`k

s``s`kk`kk``s`kk`kr``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s``s`ks``s`kk

`ks``s``s`ks``s`kk`kk`ki``s``s`ks``s`kk`kk``s`kk`k.*``s``s`ks``s`kk`kk

``s`kki``s``s`ks``s`kk`kk``s`kki``s`kk`ki``s``s`ks``s``s`ks``s`kk`ks``

s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s`kk`kk``s`kk`k``s``s`ks``s``s`ks`

`s`kk`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s`kk`kk``s`kk`ks``s``s`k

s``s``s`ks``s`kk`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s`kk`kk``s`kk

`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s`kk`kk``s`kk`kk``s``s`ks``s`

kk`kk``s`kki``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s`kk`kk``s`kk`kk``s`

kk`ki``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``

s`kk`kk``s`kk`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s``s`ks``s`kk`ks

``s``s`ks``s`kk`kk``s`kk`ks``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``s`kk`

kk``s`kk`kk``s``s`ks``s`kk`kk`ki``s``s`ks``s``s`ks``s`kk`ks``s``s`ks``

s`kk`kk``s`kk`kk``s`kk`ki``s``s`ks``s`kk`kk``s`kk`ki``s``s`ks``s`kk`kk

```
`ki``s`kk`ki 
```

Ad ogni modo, cos'è una continuazione?
Esistono molte definizioni ad effetto: una continuazione è uno stato. Una continuazione è il futuro di una computazione. Le continuazioni sono la versione matematica del goto. Le continuazioni sono eccezioni sotto steroidi. E altra roba così.

Ma probabilmente queste definizioni non vi aiutano a capire molto. Almeno finché non arrivate ad un epifania in cui tutti i pezzi vanno a posto e potete finalmente esclamare "ah, ma cavolo ...". Io proverò a farvi arrivare a quel punto, speriamo bene.

Un programma è composto di vari passi:

```
a=10 
```
```
b=20 
```
```
a=a+b 
```
```
print a 
```
```
=> 30 
```

In ogni passo, il programma è diviso in due: la parte già eseguita e la parte da eseguire. In un linguaggio dove esista il GOTO possiamo passare da un punto all'altro:

```
10: a=10 
```
```
20: b=20 
```
```
30: a=a+b 
```
```
40: print a 
```
```
50: GOTO 40 
```
```
=> 3030303030303030303030... 
```

Il problema nell'uso dei GOTO è che questi sono cittadini di seconda classe nel mondo della programmazione. Non si può prendere una label e mandarla in giro per il programma, ed in genere non si può saltare ad un indirizzo stabilito a runtime.
I GOTO sono qualcosa che esiste solo a livello di codice, non di programma.

Insomma, i goto sono cattivi. Le continuazioni invece, non lo sono.

La continuazione, come il goto, è un warp spaziotemporale, con la differenza che possiamo prenderlo e portarcelo in giro.
Ma ora, per una questione di correttezza verso chi lo ha già fatto dobbiamo sbattere la testa su un minimo di teoria.
In genere si è abituati a pensare che un "passo" nello svolgimento di un programma corrisponda grossomodo al concetto di "chiama una funzione F".
È facile visualizzare la cosa pensando in Scheme:

```
(+ 1 2) 
```
```
(display 1) 
```
```
(set! foo 10) 
```

un po' più strano in ruby:

```
1+2 
```
```
puts 1 
```
```
foo=10 
```

Ma sotto sotto il concetto è quello. In realtà i teorici hanno dimostrato che diventa molto più semplice parlare di informatica se un passo viene definito come:
"chiama una funzione F con la continuazione K"
Che in un certo modo equivale a dire "nel contesto K".
Dunque gli esempi di prima in Scheme sarebbero:

```
(+ 1 2 K1) 
```
```
(display 1 K2) 
```
```
(set! foo 10 K3) 
```

o in pseudo ruby:

```
1+2 in K1 
```
```
puts 1 in K2 
```
```
foo=10 in k3 
```

Ora, fin qui non c'è niente di strano, abbiamo delle variabili un po' inutili passata qua e là, ma il sistema è sempre quello.

A questo punto compare la magia di call/cc.
chiama-con-la-continuazione-attuale significa appunto che ad una funzione verrà passata una variabile che rappresenta la computazione corrente.
Esempio usando la console interattiva di ruby:

>> callcc do |k|
?>  puts 'ciao'
>> end
ciao
=> nil

Come vedete nulla di strano, c'è quella variabile inutile e basta. A questo punto proviamo a salvare quella variabile da qualche parte:

>> $kont=nil # le variabili con il $ sono globali
=> nil
>> callcc do |k|
?>  $kont=k
>> end
=> #<Continuation:0x401f76f0>
>> $kont
=> #<Continuation:0x401f76f0>

Ora, una continuazione funziona più o meno come una funzione, ed infatti ha un solo metodo utile, #call, che serve, appunto, a chiamarla.
Ma che succede se la chiamiamo? Proviamo da riga di comando:

[nickel@UltimaThule nickel]$ ruby
$kont=nil
callcc do |k|
    $kont=k
end
$kont.call


-:5: Interrupt

Se non avete ben chiaro quel che è successo, provate a guardare questo:

callcc do |k|
    $kont=k
end
puts 'sono nella continuazione k'
$kont.call


sono nella continuazione k
sono nella continuazione k
sono nella continuazione k
sono nella continuazione k
sono nella continuazione k
sono nella continuazione k
-:4: Interrupt

Quello che facciamo è dire all'interprete "esegui questa continuazione"
Ma la continuazione non è altro che la funzione puts e poi la chiamata della continuazione ("esegui questa continuazione").. e così via.
Potete notare anche una cosa importante. Usando le continuazioni in questo modo non c'è mai uno stack overflow.
Lo stack overflow esiste per le funzioni quando, ad esempio eseguiamo una funzione come questa:

```
def fact(n) 
```
```
    if n>1 
```
```
        fact(n-1)* n 
```
```
    else 
```
```
        1 
```
```
    end 
```
```
end 
```

Perché ad ogni esecuzione della funzione bisogna mantenere in memoria tutto lo stack delle chiamate, infatti ad un certo punto, avremo bisogno di restituire qualcosa alla funzione chiamante, e alla sua funzione chiamante e così via.
Una continuazione, invece, non ritorna mai.
Eseguire una funzione è come entrare in varie stanze in una casa.
Eseguire una continuazione è come entrare in varie stanze e trovarsi sempre all'ingresso.

Ouch, sono ricaduto nella trappola di parlare di callcc in modo magico.
Una spiegazione più semplice per chi ha una minima idea di come funzioni un computer è che quando salvate una continuazione fate una copia dello stack, dei registri e del program counter.
Quando la chiamate non fate altro che cancellare stack e registri correnti, ricopiarci sopra quelli salvati e ricominciare l'esecuzione.
In effetti la specifica C99 mette a disposizione due funzioni che fanno più o meno questo: setjmp() salva lo stack, e longjmp() lo ripristina.
Per mostrare il fatto che callcc non ritorna mai basta che guardiate questo esempio:

```
callcc do |k| 
```
```
   $kont=k 
```
```
end 
```
```
puts 'sono nella continuazione k' 
```
```
$kont.call 
```

abort "un drago ha incenerito il programma"

non raggiungerete mai la chiamata ad #abort.
Il che è positivo, perché evitiamo un po' di magia.

A questo punto dovreste aver chiara, bene o male, la potenza di callcc.
Avendo a disposizione questa funzione potete programmare qualsiasi struttura di controllo, dal'if-then-else alle eccezioni.
A proposito di eccezioni, una cosa semplice che potete fare con callcc in ruby è costruire eccezioni resumabili. Cos'è un'eccezione resumabile?
Si tratta di un meccanismo tipico di smalltalk, in cui una volta catturata un'eccezione è possibile usarla per riprendere la computazione dal punto esatto in cui è stata sollevata,piuttosto che ripetere l'intero blocco di codice.
Ruby non le supporta nativamente, ma possiamo implementarle facilmente.
Prima di tutto creiamo una sottoclasse di Exception chiamata ResumableException:

```
class ResumableException < Exception 
```
```
    def initialize (k,msg) 
```
```
        super msg 
```

        @kont=k # quelle con la @ sono variabili d'istanza

```
    end 
```
```
    def resume 
```
```
        @kont.call 
```
```
    end 
```
```
end 
```

L'unica differenza rispetto a una normale eccezione è che questa include una continuazione ed un metodo per chiamarla. Ora scriviamo un metodo che crei questo tipo di eccezione e la lanci, salvando la continuazione:

```
def resumeable_raise(msg) 
```
```
    callcc do |k| 
```

        raise ResumableException.new k, msg

```
    end 
```
```
end 
```

Ed infine un metodo di test:

```
def test 
```
```
    puts "pre-eccezione" 
```
```
    resumeable_raise "eccezione!!" 
```
```
    puts "post-eccezione" 
```
```
rescue Exception => e 
```
```
    p "recupero da "+ e.inspect 
```
```
    e.resume 
```
```
end 
```
```
 
```
```
test() 
```

Eseguendo dovreste avere un risultato di questo tipo:

pre-eccezione
"recupero da #<ResumableException: eccezione!!>"
post-eccezione

Piuttosto semplice no? Ora provate a farlo in Java!

A questo punto dovreste aver capito un minimo della logica di callcc.
E per rendere le cose più interessanti, mi permetto di scopiazzare senza alcuna vergogna "Teach Yourself Scheme in Fixnum Days" ^[6], proponendovi una semplice implementazione di operatore non deterministico.
Se qualcuno un giorno scriverà "Teach Yourself QualcosAltro in Fixnum Days" lo invito a copiare da qui.
L'importante è avere call/cc e i Fixnum.

Cosa si intende per operatore non deterministico?
Un qualcosa che sia in grado di scegliere la soluzione migliore o peggiore per il nostro programma, senza bisogno di indicargliela.
Ad esempio, potremmo scrivere:

```
amb=Amb.new 
```
```
x,y= amb.choose(1,2), amb.choose(1,2) 
```
```
x* 30 == y* 15 
```
```
puts x,y #=> 1, 2 
```

e l'operatore si preoccuperebbe di trovare x ed y al posto nostro.
Si tratta di un classico sistema di backtracking sullo stile dei linguaggi tipo prolog o mercury. Ovviamente ruby non è pensato come un linguaggio constraint based quindi sarà parecchio lento nel svolgere le operazioni, ma il concetto è comunque interessante.
Dunque, la prima cosa che facciamo è definire una classe Amb. Il nome viene dalla tradizione e sta per qualcosa tipo "ambivalente".
Definiamo una classe perché abbiamo bisogno di qualcosa che mantenga uno stato ed abbia delle funzioni, quindi la scelta è ovvia:

```
class Amb 
```
```
  def initialize 
```
```
      @paths = [] 
```
```
  end 
```

L'array (@paths)delle scelte conterrà tutte le varie continuazioni.
Poi aggiungiamo un metodo per "riempire" l'array dei possibili percorsi:

```
def choose *choices 
```
```
    choices.each do |choice| 
```
```
        callcc do |k| 
```
```
            @paths << k 
```
```
            return choice 
```
```
        end 
```
```
    end 
```
```
    fail 
```
```
end 
```

Questo metodo sembra complicato ma non lo è.
Anzitutto iteriamo sulle scelte passate in input.
Per ognuna creiamo una continuazione, la aggiungiamo all'array, e poi restituiamo la scelta. Cercate di capire bene: non riempiamo l'array con le possibili scelte! Quello che l'array contiene è una delle possibili continuazioni, e quello che il metodo restituisce è la scelta relativa a quella continuazione.
Scrivendo

```
x= amb.choose 1,2 
```

Otterremo che x vale 1 e che @paths è qualcosa tipo

[#<Continuation:0x401f4374>]

un array di un solo elemento, un oggetto continuazione. Quando la continuazione 0x401f4374 verrà richiamata eseguiremo un nuovo passo nell'iterazione, infilando un nuovo valore in @paths e rendendo x= 2.
Scrivendo:

x,y=amb.choose( 1,2), amb.choose( 1,2)

Otterremo che @paths diventi

[#<Continuation:0x401f4374>, #<Continuation:0x401f5a30>]

Ciò rappresenta chiaramente che le biforcazioni dei percorsi possibili sono due, e corrispondono all'assegnazione di x ed a quella di y.
Ma quando chiamiamo questa continuazione? Semplice, quando il nostro calcolo fallisce. Questo è appunto il metodo #fail.

```
def fail 
```
```
    if @paths.empty? 
```

        abort "Choice tree exhausted."

```
    else 
```
```
       @paths.pop.call 
```
```
    end 
```
```
  end 
```

Che tradotto passo passo significa: "se ci sono ancora continuazioni levane una dalla lista e richiamala, altrimenti termina dicendolo all'utente"
È importante notare che #fail. viene richiamato anche quando abbiamo finito di iterare sulle possibili scelte, per mostrare, appunto, che abbiamo fallito.
A questo punto vediamo di far funzionare il nostro esempio di prima:

```
amb=Amb.new 
```
```
x= amb.choose 1,2 
```
```
puts "x ora vale "+x.to_s 
```
```
puts "amb e' "+amb.inspect 
```
```
y= amb.choose 1,2 
```
```
puts "y ora vale "+y.to_s 
```
```
puts "amb e' "+amb.inspect 
```
```
 
```
```
if x* 30 == y* 15 
```

    puts "soluzione trovata per x="+ x.to_s + " ed y=" + y.to_s

```
else 
```
```
    amb.fail 
```
```
end 
```

che da questo output

x ora vale 1
amb e' #<Amb:0x401c4fe4
@paths=[#<Continuation:0x401c4f6c>]>
y ora vale 1
amb e' #<Amb:0x401c4fe4
@paths=[#<Continuation:0x401c4f6c>,#<Continuation:0x401c4e40>]>
y ora vale 2
amb e' #<Amb:0x401c4fe4 @paths=[#<Continuation:0x401c4f6c>,
#<Continuation:0x401c4d3c>]>
soluzione trovata per x=1 ed y=2

Simpatico vero?
Il nostro amb è piuttosto stupido, in quanto eaurisce tutto lo spazio delle soluzioni finché non ne trova una. Se volessimo trovarle tutte basterebbe aggiungere una condizione mai soddisfatta.
In questo modo amb continuerebbe a cercarne fino ad esaurire tutte le possibilità, e mostrandoci tutte le soluzioni possibili.
Vediamo un altro esempio:

```
tot = 315 
```
```
                                                                              
```
```
amb = Amb.new 
```
```
a=amb.choose 1,2,3,4,5,6,7  
```
```
b=amb.choose 1,2,3,4,5,6,7 
```
```
c=amb.choose 1,2,3,4,5,6,7 
```
```
d=amb.choose 1,2,3,4,5,6,7 
```
```
 
```
```
if tot == a * b * c * d 
```

    puts "#{tot} == #{a} * #{b} * #{c} * #{d}"

```
else 
```
```
    amb.fail 
```
```
end 
```

che da in output:

315 == 3 * 3 * 5 * 7

La cosa affascinante è che possiamo estendere la nostra classe Amb!
Ad esempio possiamo programmare una classe Amb per la soluzione del problema dei quattro colori (cioè, assegnare i colori alle nazioni su una mappa in modo che due nazioni confinanti non abbiano mai lo stesso):
Creiamo una classe Paese che abbia un nome, un colore ed una lista di paesi vicini:

```
class Paese 
```
```
    attr_accessor :colore, :vicini 
```

    def initialize nome, colore, *vicini

        @nome,@colore,@vicini=nome,colore,vicini

```
    end 
```
```
    def to_s 
```

        "#{@nome}: colore #{@colore}, colori vicini:  #{@vicini.join ","}"

```
    end 
```
```
end 
```

Poi subclassiamo Amb:

```
class ColorAmb < Amb 
```
```
    def choose_color 
```

        choose 'rosso', 'giallo', 'blu', 'verde'

```
    end 
```
```
end 
```

Poi facciamo una scelta di colori per ogni paese:

```
amb=ColorAmb.new 
```
```
po= amb.choose_color 
```
```
sp= amb.choose_color 
```
```
fr= amb.choose_color 
```
```
be= amb.choose_color 
```
```
ho= amb.choose_color 
```
```
ge= amb.choose_color 
```
```
lu= amb.choose_color 
```
```
it= amb.choose_color 
```
```
sv= amb.choose_color 
```
```
au= amb.choose_color 
```

e creiamo un array di paesi:

paesi=[ Paese.new( 'portogallo',    # nome

                   po,              # colore

                   sp),             # vicini

```
        Paese.new( 'spagna', 
```
```
                   sp, 
```
```
                   fr,po), 
```
```
        Paese.new( 'francia', 
```
```
                   fr, 
```

                   sp,it,sv,be,ge,lu),

```
        Paese.new( 'belgio', 
```
```
                   be, 
```
```
                   fr,ho,lu,ge), 
```
```
        Paese.new( 'olanda', 
```
```
                   ho, 
```
```
                   be,ge), 
```
```
        Paese.new( 'germania', 
```
```
                   ge, 
```

                   fr,au,sv,ho,be,lu),

```
        Paese.new( 'lussemburgo', 
```
```
                   lu, 
```
```
                   fr,be,ge), 
```
```
        Paese.new( 'italia', 
```
```
                   it, 
```
```
                   fr,au,sv), 
```
```
        Paese.new( 'svizzera', 
```
```
                   sv, 
```
```
                   fr,it,au,ge), 
```
```
        Paese.new( 'austria', 
```
```
                    au, 
```
```
                    it,sv,ge), 
```

Ora dichiariamo che la scelta non ha funzionato se il colore di un paese è uguale a quello dei vicini:

```
paesi.each do |p| 
```

    amb.fail if p.vicini.include?(p.colore)

```
end 
```

E visualizziamo il risultato:

```
puts paesi 
```

portogallo: colore italia: colore rosso, colori vicini:  giallo,rosso,verde,
colori vicini:  rosso
spagna: colore rosso, colori vicini:  giallo,italia: colore rosso, colori
vicini:  giallo,rosso,verde
francia: colore giallo, colori vicini:  rosso,rosso,verde,rosso,blu,verde
belgio: colore rosso, colori vicini:  giallo,giallo,verde,blu
olanda: colore giallo, colori vicini:  rosso,blu
germania: colore blu, colori vicini:  giallo,giallo,verde,giallo,rosso,verde
lussemburgo: colore verde, colori vicini:  giallo,rosso,blu
italia: colore rosso, colori vicini:  giallo,giallo,verde
austria: colore giallo, colori vicini:  rosso,verde,blu

Funziona che è un incanto.
In realtà avere la possibilità di gestire le continuazioni in questo modo apre delle possibilità illimitate. Possiamo costruire delle coroutine, dei sistemi di concorrenza, o possiamo trasformare degli iteratori interni (quelli classici di ruby) in esterni (quelli di Jave o c++).
E possiamo usarle per costruire dei web framework. Eh già, in effetti l'uso di maggior successo di callcc è quello nei cosiddetti web framework modali.
Il concetto di base è che l'interazione con un utente in una applicazione web viene visto come una sola lunga computazione, e mentre l'utente riempie form o clicca "indietro" nel browser noi non facciamo altro che saltare da un punto della computazione all'altro.
Questo approccio è molto molto potente, ed infatti molti lo hanno reinventato indipendentemente, in vari linguaggi e con virtù e difetti differenti. Seaside2^[3] per smalltalk, UncommonWeb^[4] per CommonLISP e Borges^[5] per ruby sono i framework che incarnano meglio questo concetto.
Ma cosa c'è di diverso in questo tipo di applicazioni? Citando Avi Bryant, l'autore di Seaside (ed inizialmente di Borges), la stessa differenza che c'è tar la programmazione strutturata ed i GOTO.
In un'applicazione web classica non abbiamo un flusso, ma una serie di salti da un punto all'altro del programma, incontrollabile. Grazie alla possibilità di gestire le continuazioni esplicitamente, possiamo linearizzare questo saltellio, e scrivere applicazioni in modo molti più semplice.

Conclusione

Certamente gli usi e le possibilità date da callcc non sono state esaurite in questo breve testo. Quello che spero è avervi dato la possibilità di capire un minimo quel che rappresenta questo meccanismo, e magari, avervi fatto venire un po' di curiosità. In fondo a tutti piace la magia, no?

Informazioni sull'autore

Gabriele Renzi, studente di Ingegneria Informatica, è un appassionato di programmazione e sistemi operativi. Scrive "hello world" in una dozzina di linguaggi ma non riesce ad andare oltre nemmeno in uno.
Collabora con il Progetto Documentazione Italiana FreeBSD ed è membro del Gruppo Utenti Ruby Italia.

È possibile consultare l'elenco degli articoli scritti da Gabriele Renzi.

Altri articoli sul tema Linguaggi / Ruby.

Risorse

Stackless è un fork di python che non usa lo stack C e fornisce continuazioni, coroutine e microthread (thread implementati con continuazioni)
http://www.stackless.com/
cocoon è usa un'interprete javascript modificato con oggetti di tipo continuazione per gestire il flusso di applicazioni web.
http://cocoon.apache.org
la versione più evoluta di web framework continuation based
http://beta4.com/seaside2
ispirato a seaside, UCW è scritto in common lisp, ed usa un continuation passing style transformer invece di callcc (CL non ha call/cc)
http://www.common-lisp.net/project/ucw/
un clone di Seaside2. È interessante che il primo Seaside è era un clone di un web framework per ruby chiamato IOWA.
http://borges.rubyforge.org
Teach Yourself Scheme in Fixnum Days
http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html

La magia di call/cc

Conclusione

Informazioni sull'autore

Risorse

Cosa ne pensi di questo articolo?

Discussioni

	Articoli Manifesto Tools Links Canali Libri Contatti ?
	Autori Temi Società e associazioni