Le avventure di un Pythonista in Schemeland /6

Dopo cinque puntate introduttive è finalmente arrivato il momento
di fare sul serio. In questa puntata e nella prossima getteremo le basi
per capire cosa stia dietro al celebre motto del Lisp code is data,
che molti considerano il cuore e l’anima del Lisp.
Come sempre, capire richiede qualche preliminare. In questa puntata
descriveremo due tipi di dati fondamentali del Lisp (e quindi
di Scheme): i simboli e le liste. Nella prossima discuteremo
l’operazione di quoting che permette di trasformare un frammento di
codice in una lista di simboli e valori primitivi (cioè converte
codice in dati) e l’operazione di eval che permette di eseguire una
qualunque lista di simboli e valori primitivi corrispondente a codice valido
(cioè converte dati in codice).

Simboli

symbols.jpg

Scheme e Lisp possiedono un tipo di dato che non esiste nei linguaggi
tradizionali (con l’eccezione di Ruby): il simbolo.
Grammaticalmente un simbolo non è altro che un identificatore
quotato, ovvero una serie di lettere che costituisce un identificatore
valido preceduta da un apice.
Per esempio 'a, 'b e 'c sono dei simboli.
Sull’insieme dei simboli è definita l’operazione di identità eq?
che permette di determinare se due simboli sono identici oppure no:

> (define sym 'a)
> (eq? sym 'b)
#f
> (eq? sym 'a)
#t

#f e #t sono i valori booleani False e True, come avrete
capito. L’operazione di identità sui simboli è molto efficiente,
perché il compilatore associa ad ogni simbolo un numero intero (questa
operazione è chiamata hashing) e se lo segna in un registro interno
(questa operazione viene chiamata interning): quando controlla
l’identità di due simboli in realtà controlla l’uguaglianza di due
numeri in memoria che è un’operazione velocissima. Potete controllare
voi stessi usando la funzione builtin symbol-hash, che ritorna il
numero associato al simbolo:

> (symbol-hash sym)
117416170
> (symbol-hash 'b)
134650981
> (symbol-hash 'a)
117416170

I simboli in Scheme sono quindi
diversissimi dalle stringhe che invece vengono
paragonate carattere per carattere. La situazione è diversa
in Python dove il concetto di simbolo non serve in quanto le stringhe
corrispondenti a nomi di oggetti Python e chiavi di dizionario
sono di fatto trattate come simboli. Rimando
chi vuole sapere esattamente come funziona il confronto di stringhe
in Python a questo post; consiglio inoltre di leggersi la documentazione
delle funzioni builtin hash e intern, in cui si legge
testualmente: normally, the names used in Python programs are
automatically interned, and the dictionaries used to hold module,
class or instance attributes have interned keys
.

È sempre possibile convertire una stringa in un simbolo e viceversa con le
funzioni string->symbol e symbol->string. Come esempio d’uso, ecco
una funzione di utilità che permette di appendere due o più simboli:

(define (symbol-append . symbols)
(string->symbol (apply string-append (map symbol->string symbols))))

> (symbol-append 'x ': 'y)
x:y

In Scheme quasi qualunque cosa può essere un simbolo, visto
che i caratteri validi negli identificatori sono molti di più dei
caratteri validi in Python (a-zA-Z-0-9_). Per convenzione i
simboli che terminano per ? sono associati a valori booleani o a
funzioni che ritornano valori booleani, mentre i simboli che finiscono
per ! sono associati a funzioni o macro con effetti collaterali
(side effects).

Concludo il paragrafo con una nota sulla funzione eq?, che è polimorfa
e funziona su oggetti generici, ma può avere un comportamento
inaspettato, tipo il seguente:

> (eq? "pippo" "pippo")
#f

Il motivo è che eq? (che corrisponde a is in Python) controlla
se due oggetti sono lo stesso identico oggetto a livello di puntatori,
non se hanno lo stesso contenuto.
Incidentalmente, sulla mia macchina con Python 2.5 "pippo" is "pippo"
ritorna True, ma questo è solo un accidente, perché l’implementazione
corrente tratta diversamente le stringhe “corte” dalle stringhe “lunghe”:

>>> "a"*10 is "a"*10 # a short string
True
>>> "a"*100 is "a"*100 # a long string
False

Per controllare se due oggetti hanno lo stesso contenuto c’è la funzione
equal? che corrisponde a == in Python:

> (equal? "pippo" "pippo")
#t

Se siete sicuri che i due oggetti da confrontare sono stringhe, è
più efficiente usare string=?, mentre per i numeri si usa
semplicemente =:

> (string=? "pippo" "pippo")
#t

> (= 42 42)
#t

Liste

LISP significava originariamente List Processing poiché le liste erano il
tipo di dati fondamentale del linguaggio. Al giorno d’oggi i linguaggi derivati
dal Lisp implementano tutti i tipi di dati che potete immaginare, ma è vero
che le liste hanno ancora una posizione privilegiata.
Una lista in Scheme è una struttura ricorsiva siffatta:

  1. è la lista vuota '()
  2. è ottenuta componendo un elemento ed una lista con l’operazione di cons
    (che è un’abbreviazione di constructor): (cons elem lst).

Per esempio le liste con un solo elemento sono ottenute componendo l’elemento
con la lista vuota:

> (cons 'x1 '())
(x1)

Le liste con due elementi sono ottenute componendo un elemento con una lista
contenente un solo elemento:

> (cons 'x1 (cons 'x2 '()))
(x1 x2)

E così via, ricorsivamente:

> (cons 'x1 (cons 'x2 (cons 'x3 ..... (cons 'xN '()))) ...)
(x1 x2 x3 ... xN)

L’espressione (x1 ... xN) non è altro che un’abbreviazione (zucchero
sintattico) per l’espressione in termini dei costruttori.

Esistono anche quelle che si chiamano liste improprie, che si ottengono
quando il secondo argomento del costruttore cons
non è una lista. In tal caso la rappresentazione letterale contiene un punto:

> (cons 'x1 'x2) ; improper list
(x1 . x2)

La cosa importante da ricordare è che le liste improprie non sono liste,
quindi le operazioni tipo map, filter e compagnia bella non
funzionano su di esse.

Come abbiamo visto nella terza puntata, il primo elemento di una lista
(propria o impropria) si estrare con la funzione car; la coda
della lista invece si estrae con la funzione cdr; se la lista è
propria, il cdr stesso è una lista propria.

> (cdr (cons 'x1 'x2))
x2

> (cdr (cons 'x1 (cons 'x2 '())))
(x2)

A basso livello le liste di
Scheme possono essere implementate come linked list, ovvero come
come coppie (valore, puntatore a sotto-lista) fino a che si arriva
al puntatore nullo. Chi ha studiato informatica sicuramente ha già
visto il grafico qui sotto in qualche corso:

ll.gif

Qualche esercizio

Tanto per dare un esempio di come si maneggiano le liste in Scheme, vi
mostro come si può definire una funzione range analoga al
range di Python:

(define range 
(case-lambda
((n) (range 0 n 1))
((n0 n) (range n0 n 1))
((n0 n s) (let ((cmp (if (> s 0) >= <=)))
(let loop ((i n0) (acc '()))
(if (cmp i n) (reverse acc)
(loop (+ i s) (cons i acc))))))))

La macro case-lambda permette di
definire funzioni con comportamento diverso a seconda del numero di
argomenti passati.
Il trucco usato nel loop è assolutamente tipico: si incrementa una
lista usata come accumulatore ad ogni ciclo (cons i acc) ed alla fine
si rovescia l’accumulatore (reverse acc). Il primo let definisce
una funzione di comparazione che può essere >= se lo step è
positivo oppure <= se lo step è negativo; il motivo è che se lo
step è positivo ad un certo punto l’indice i avrà un valore
maggiore di n, mentre se è negativo ad un certo punto i
diventerà minore di n.
Potete verificare che tutto funziona:

> (range 5)
(0 1 2 3 4)
> (range 1 5)
(1 2 3 4)
> (range 1 10 2)
(1 3 5 7 9)
> (range 10 0 -2)
(10 8 6 4 2)
> (range 5 1); meaningless range
()

In realtà la funzione range appena definita è più potente dell’equivalente
Python, in quanto funziona anche per numeri in virgola mobile:

> (range 1.3 2.5 .25)
(1.3 1.55 1.8 2.05 2.3)

La cosa notevole dell’idioma utilizzato qui è che sia il contatore che l’accumulatore
non vengono mai modificati: ad ogni ciclo un nuovo contatore
ed un nuovo accumulatore vengono generati ex-novo e passati alla funzione
di loop. Questo è un tipico loop funzionale; i loop non-funzionali (ovvero
imperativi) in cui l’indice di loop viene incrementato ad ogni ciclo sono
considerati cattivo stile in Scheme ed in tutti i linguaggi funzionali.
Per contrasto, in Common Lisp sono perfettamente accettabili ed esiste
anche una avanzatissima macro
LOOP che permette di fare di tutto con i loop imperativi.

Come sempre, l’unico modo per capire veramente come funzionano le liste in Scheme è
quello di usarle: vi consiglio quindi di svolgere i seguenti due esercizi:

  1. implementare l’enumerate di Python;
  2. implementare lo zip di Python.

Potete postare le vostre soluzioni come commenti. A chi è pigro e vuole una
libreria già fatta, consiglio l’SRFI-1, che è una libreria molto ricca di
funzionalità, oltre che standard e disponibile in pratica per tutte le
implementazioni di Scheme. Molte delle funzionalità dell’ SRFI-1 sono
state incluse in core Scheme con l’R6RS, ma molte altre restano disponibili
soltanto nell’SRFI-1 che rimane una libreria indispensabile per qualunque
programmatore Scheme.

Comments

  1. Ottimo articolo! Come sempre del resto…

    Bravo!

  2. Ottimo articolo! Come sempre del resto…

    Bravo!

  3. Pietro e Tiziano says:

    Grazie Michele per questa serie interessantissima!

    Abbiamo passato questo pomeriggio pasquale a scrivere le nostre prime righe in Scheme. Questa e’ la nostra soluzione… Abbiamo il sospetto che esista una soluzione vagamente piu’ elegante, ogni commento e’ benvenuto!

    Buona pasqua!
    Pietro e Tiziano

    (ATTENZIONE SPOILER)

    define (enumerate x)
      (let loop ((rest x)(i 0)(acc '()))
        (if (eq? rest '())
          (reverse acc)
          (loop (cdr rest)
                (+ i 1)
                (cons (cons i (cons (car rest) '())) 
                      acc))
          )
        )
      )
    
    ; return two lists: one with the car of all the
    ; lists and one with the cdr of the lists
    (define (first-and-rest lists)
      (let loop ((rest lists)(acc '())(lists-cdr '()))
        (if (eq? rest '())
            (cons (reverse acc) (cons (reverse lists-cdr) '()))
            (loop (cdr rest)
                  (cons (car (car rest)) acc)
                  (cons (cdr (car rest)) lists-cdr))))
      )
    
    ; return true if one of the lists is '()
    (define (any-void lists)
      (let loop ((rest lists))
        (if (eq? rest '())
            #f
            (if (eq? (car rest) '())
                #t
                (loop (cdr rest)))))
      )
    
    
    (define (zip . lists)
      (let loop ((rest lists)(acc '()))
        (if (any-void rest)
            (reverse acc)
            (let ((x (first-and-rest rest)))
              (loop (car (cdr x))
                    (cons (car x) acc))))
      ))
    
    ;(first-and-rest '((a b 1) (c d 2) (e f 3)))
    
    ; test enumerate
    (enumerate '())
    (enumerate '(a))
    (enumerate '(a b c))
    
    ; test zip
    (zip '(a b 1) '(c d 2) '(e f 3))
    (zip '(a b 1) '(c d) '(e f 3))
    
  4. Pietro e Tiziano says:

    Ooops… Tutte le indentazioni sono scomparse…
    Ecco un link al file pulito:
    http://itb.biologie.hu-berlin.de/~zito/avventure6_submission.txt

  5. Michele Simionato says:

    Bravi, siete stati gli unici ad avere avuto il coraggio di rispondere alla sfida! Per non perdere l’indentazione
    dovete usare il tag pre nel commento.
    L’implementazione di ‘enumerate’ e’ buona,modulo
    qualche errore di gioventu’ (si usa null? invece
    di eq? ‘() ). Per quanto riguarda zip avete ragione,
    c’e’ una soluzione molto piu’ elegante della vostra:

    
    (define (enumerate lst)
      (let loop ((i 0) (ls lst) (acc '()))
        (if (null? ls) (reverse acc)
            (loop (+ 1 i) (cdr ls) (cons `(,i ,(car ls)) acc)))))
    
    (define (zip . lists)
     (apply map (lambda x x) lists))
    
    
  6. Pietro e Tiziano says:

    Effettivamente questa implementazione di zip e’ leggermente piu’ elegante 🙂 A nostro discapito possiamo dire che ci eravamo sforzati di rispettare una particolarita’ dell’implementazione Python che accetta liste di diversa lunghezza. Ecco il nostro secondo tentativo (incrociando le dita per l’indentazione):

    (define (zip . lists)
        (let loop ((i (apply min (map length lists)))
                   (rest lists)
                   (acc '()))
          (if (zero? i)
              (reverse acc)  
              (loop (- i 1)
                    (map cdr rest)
                    (cons (map car rest) acc)))))
    
    
    (zip '(a b c) '(d e f) '(g h i))
    (zip '(a b c) '(d e) '(g h i))
    
  7. Michele Simionato says:

    Bravi! A dire la verita’ avevo ignorato bellamente il
    fatto che zip in Python puo’ prendere liste di lunghezza diversa, perche’ e’ una “feature” che non uso mai. La vostra implementazione e’ ottima, io
    toglierei soltanto la variabile i, che non serve:

    (define (zip . lists)
      (let loop ((rest lists) (acc '()))
        (if (zero? (apply min (map length rest)))
            (reverse acc)  
            (loop (map cdr rest) (cons (map car rest) acc)))))
    

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.