Le avventure di un Pythonista in Schemeland/4

Nelle puntate precedenti non ho fatto altro che parlare male di
Scheme. In questa puntata cercherò di riequilibrare la situazione,
parlando di performance e dei vantaggi di un compilatore
ottimizzante. Sarà però necessario superare un paio di difficoltà
prima di poter scrivere qualche benchmark portabile. La prima difficoltà è la
mancanza del ciclo for, che è tipica dei linguaggi funzionali;
la seconda difficoltà è che non esiste un modo completamente portabile
per scrivere un modulo, anche se l’R6RS ci arriva vicino.


Prima difficoltà: non ci sono i cicli for in Scheme

Il ciclo for manca perché in un linguaggio come Scheme,
che garantisce la cosiddetta ottimizzazione di tail call, è inutile.
Se avete studiato il concetto di tail call all’università sapete
già di cosa parlo; d’altra parte, se ve lo siete dimenticato o se siete
degli autodidatti come il sottoscritto vale la pena di dire due parole.
Per maggiori dettagli vi rimando alla voce di Wikipedia corrispondente.

Ouroboros.png

Il punto di principio è che è sempre possibile convertire un ciclo for in una
funzione ricorsiva in forma di tail call, ovverossia in una funzione
ricorsiva che ritorna o un risultato o una chiamata a sé stessa.
Per esempio il ciclo Python

# a loop printing 1 2 3
for i in range(1,4):
print i,

può essere convertito nella forma ricorsiva

def print_up_to_3(i):
if i == 4: return
print i,
return print_up_to_3(i+1)

print_up_to_3(1)

in cui l’ultima istruzione della funzione (la coda) è una chiamata alla
funzione stessa, da cui tail call.

La tail call optimization è un’ottimizzazione garantita
dal linguaggio Scheme. Essa assicura che il compilatore sia
in grado di riconoscere le funzioni ricorsive in forma tail call
e di calcolarle efficientemente riconvertendole internamente in cicli for.
In pratica questo significa che il programmatore non ha più bisogno del for
e non deve fare altro che scrivere funzioni ricorsive. Il nostro
esempio diventerebbe

(define (print-up-to-3 i)
(unless (= i 4) (display i) (display " ") (print-up-to-3 (+ i 1))))

(print-up-to-3 1)

Il metodo funziona, ma non è esattamente leggibile; per migliorare
le cose Scheme fornisce un pò di zucchero sintattico nella
forma del costrutto named let:

(let loop ((i 1))
(unless (= i 4) (display i) (display " ") (loop (+ i 1))))

Tradizionalmente la funzione nel named let si chiama loop per
rendere chiaro che si sta emulando un ciclo imperativo. In questo
esempio la funzione loop è esattamente equivalente a
print-up-to-3.

Due note prima chiudere questo paragrafo:

1) esiste anche un’altra forma di let, che è
usata per definire variabili locali:

> (let ((a 1)(b 2)) (+ a b)) ; => 3

Lo scope di a e b è limitato al blocco corrente; se a e b sono definite anche
in un blocco esterno, all’interno del blocco let le variabili a e b nascondono
(shadow) le variabili esterne.

2) esiste anche un ciclo do nel linguaggio, ma è
complicato, con una sintassi difficile da ricordare e del tutto
ridondante perché il named let permette di fare tutto quello che
fa il do; in pratica nessuno lo usa. È un’esempio di un costrutto
inutile in un linguaggio che vorrebbe essere minimalista ma non lo è
veramente.

Seconda difficoltà: non c’è un module system veramente portabile

Se vogliamo scrivere dei benchmark sulle performance di
Scheme conviene introdurre una funzione in grado di calcolare n
volte un’espressione. Siccome tale funzione verrà utilizzata in tutti i benchmark
ha senso includerla in una libreria. E qui cominciano i dolori.
Come ho già detto più volte, il punto dolente di Scheme sono le
librerie: il problema non è soltanto il fatto che ci sono poche librerie
disponibili, il problema è che è anche difficile scrivere librerie portabili!

Scheme è un linguaggio che alterna idee geniali ad errori madornali:
tra questi, il più grave in assoluto è l’assenza di un sistema di
moduli standardizzato. In pratica tutte le implementazioni di Scheme non
conformi all’R6RS (ovverossia tutte le implementazioni attuali) hanno
un proprio sistema di moduli inconsistente con tutti gli altri.

Per capire il motivo di questa carenza gravissima bisogna considerare
la filosofia che sta dietro a Scheme, la cosiddetta filosofia del MIT:
o le cose si fanno bene o non si fanno. In trent’anni la comunità
di Scheme non è riuscita a mettersi d’accordo su un module system
fatto bene e quindi lo standard ha taciuto sull’argomento. Soltanto
l’anno scorso un sistema di moduli standard è stato sancito ufficialmente,
ma con molte proteste (molti implementatori hanno detto che non
supporteranno mai l’R6RS). Questo significa
che finora c’è stata l’anarchia più completa.

Come conseguenza se qualcuno scrive una libreria per l’implementazione X di
Scheme, usando il sistema di moduli di X, poi deve fare un sacco di
lavoro noioso e odioso per portare la libreria alle implementazioni Y,
Z, W, … (ci sono letteralmente decine di
implementazioni diverse). In più alcune implementazioni non hanno
neppure un sistema di moduli, e quindi si è costretti a risolvere i
problemi sempre in agguato di conflitto di nomi (name clashes)
a mano, cambiando il
nome alle funzioni della nostra libreria, se queste vanno a
coprire i nomi di qualche libreria di terze parti (!) Questo è
uno dei motivi principali per cui non ho mai scritto niente
di serio in Scheme: non ha senso scrivere codice che quasi
nessuno potrà utilizzare. Adesso con l’R6RS le cose potrebbero
cambiare e non escludo di poter pubblicare qualche libreria,
se mi convinco che il problema della portabilità è stato
risolto. Il problema più che tecnico è sociologico, perché
molti non amano l’R6RS; dal punto di vista puramente
tecnico esistono già delle soluzioni per usare moduli scritti
per l’R6RS in implementazioni conformi solo con l’R5RS:
si veda per esempio psyntax che però devo ancora provare.

A discolpa di Scheme, c’è da dire che il problema di
implementare un sistema di moduli in un linguaggio con una macrologia sofisticata,
volendo mantenere la possibilità di compilare i diversi
moduli separatamente non è affatto banale.

Siccome c’è la speranza che il sistema di moduli standardizzato
dall’R6RS si diffonda,
ne farò uso in questi articoli. Come primo esempio definirò un modulo repeat
che exporta una funzione call che chiama una procedura n volte. Ecco il
sorgente, che dovrebbe essere autoesplicativo:

(library (repeat)
(export call)
(import (rnrs))

(define (call n proc . args)
(let loop ((i 0))
(when (< i n) (apply proc args) (loop (+ 1 i))))))

La dichiarazione di export corrisponde all’ __all__ che si
può trovare nei moduli Python: vengono esportati tutti e e soli i nomi
elencati in export, in questo caso la sola funzione (call n proc
. args)
. Si noti l’uso del punto nella lista di argomenti (call n
proc . args)
: il punto (.) indica che la funzione accetta un
numero variabile di argomenti in ingresso, che vengono automaticamente
raggruppati nella lista args. In altre parole, . args è
moralmente simile a *args in Python, anche se vi sono delle
differenze che vedremo in una delle prossime puntate. La funzione
apply applica la lista di argomenti alla procedura in ingresso.
La procedura proc viene chiamata da call in continuazione fino
a che l’indice i non raggiunge il valore n. L’uso del modulo
è banale: se il file repeat.ss è nel path di Ikarus (controllato
dalla variabile di ambiente IKARUS_LIBRARY_PATH) lo potete
importare come segue:

$ rlwrap ikarus
Ikarus Scheme version 0.0.2
Copyright (c) 2006-2007 Abdulaziz Ghuloum
> (import (rnrs) (repeat))
> (call 3 (lambda () (display "hello!\n")))
hello!
hello!
hello!

Di default (import (repeat)) importa tutti i nomi esportati dal modulo
repeat, cosa che dovrebbe far rabbrividire qualunque Pythonista,
visto che equivale ad un import * from repeat; per fortuna è anche
possibile esplicitare i nomi da importare oppure importarli con un prefisso:

> (import (only (repeat) call)); import call from repeat
> (import (prefix (repeat) repeat:)); import all with prefix repeat:
> repeat:call
#<procedure call>

Un semplice benchmark

clessidra.gif

Il vantaggio principale di Scheme rispetto a Python è la performance.
Per illustrare le differenze di performance
riprenderò l’esempio del fattoriale introdotto nella puntata scorsa
e confronterò il seguente programma Python:

# fact.py
import sys, timeit

def fact(x):
if x == 0: return 1
else: return x * fact(x-1)

if __name__ == '__main__':
n = int(sys.argv[-1])
t = timeit.Timer('fact(%d)' % n, 'from fact import fact')
print t.repeat(1, number=10000000)
print fact(n)

con il seguente programma in Ikarus Scheme:

; fact.ss
(import (rnrs) (repeat) (ikarus))

(define (fac x)
(if (= x 0) 1
(* x (fac (- x 1)))))

(define n
(string->number (car (reverse (command-line)))))

(time (call 10000000 (lambda () (fac n))))
(display "result:") (display (fac n)) (newline)

Osserverò due cose:

  1. Python riesce a calcolare fino al fattoriale di 995, prima di
    incontrare il muro dello stack e fermarsi con un
    RuntimeError: maximum recursion depth exceeded mentre Scheme
    non ha problemi;
  2. Per calcolare il fattoriale di 995 diecimila volte Python impiega
    15.2 secondi, mentre Ikarus impiega 7.2 secondi.

Chiaramente va notato è che il fattoriale di 995 è
un numero molto grande, quindi di fatto tutto il tempo di calcolo
viene speso in moltiplicazioni di numeri molto grandi, che sono
implementate in C. Python usa una propria implementazione dei
long integers, mentre Ikarus usa la GNU Multiprecision library (gmp):
i tempi misurati qui stanno ad indicare che l’implementazione
dei numeri a precisione infinita di gmp funziona meglio di quella
di Python e non dicono nulla sulla performance relative dei
due linguaggi. È più significativo vedere che succede per
numeri piccoli. Per esempio, per calcolare il fattoriale di 7
10 milioni di volte, Python impiega 30.5 secondi, mentre Ikarus
impiega 3.08 secondi e quindi è quasi esattamente dieci volte
più veloce di Python. Quindi non è affatto sorprendente, perché
le chiamate a funzione sono particolarmente lente in Python mentre
sono ottimizzate in Scheme. Inoltre Ikarus compila a codice
nativo.

Incidentalmente, anche il REPL di Ikarus funziona compilando le espressioni
in codice nativo, mentre il REPL di Python compila a bytecode.
La tecnologia utilizzata si chiama compilazione incrementale, ed
è comunemente impiegata nei linguaggi derivati dal Lisp da decenni,
anche se può sembrare fantascienza a chi viene dal C/C++.
L’esempio del fattoriale è volutamente poco pratico, ma è significativo,
nel senso che è ragionevole aspettarsi delle performance molto buone
in Scheme.

Dedicheremo la prossima puntata ai pericoli dei benchmark, non mancate!

Comments

  1. Perche’ hai scritto la call con argomenti variabili senza usarli, invece di:

    (time (call 10000000 fac n))

    vuoi far apparire scheme piu’ verboso di quanto sia? .)

    Se accetti la verbosita’ di passare una closure alla call ti conviene scrivere la call senza varargs: da una breve prova che ho fatto con R5RS larceny, questo dovrebbe aumentare l’efficenza di un 10% circa, con le ottimizzazioni standard.

  2. Michele Simionato says:

    Perche’ in una versione precedente call voleva un thunk!
    Avrei dovuto scrivere

    (call 3 display “hello!\n”)

    e

    (call 10000000 fact n)

    ma invece ho postato la versione vecchia. Oops!

  3. Scusa la curiosita`. A cosa serve l’

    (import (rnrs))

    che utilizzi con cotanta frequenza?

  4. Michele Simionato says:

    (import (rnrs)) significa importa tutte le librerie
    della versione corrente del “Revised Report
    on Scheme” ovvero l’R6RS. E’ anche possibile
    importare sottosezioni. Per esempio
    (import (rnrs base)) importa solo le librerie di base,
    (import (rnrs io)) importa solo le librerie di I/O, eccetera.

Policy per i commenti: Apprezzo moltissimo i vostri commenti, critiche incluse. Per evitare spam e troll, e far rimanere il discorso civile, i commenti sono moderati e prontamente approvati poco dopo il loro invio.