Lisp – Gli operatori speciali – 1

dadi
Capitolo nuovo, questo.

I post precedenti che non mi erano piaciuti tanto in effetti, esordisce Peter (rockz!) possono essere riscritti in modo completamente diverso, grazie agli operatori speciali (il bello del Lisp) 😀

Di operatori speciali ne abbiamo già visto qualcuno ma conviene vederne altri sia perché alcuni dei meno usati sono meno usati perché le condizioni in cui servono sono rare ma serve conoscerli per quando s’incontrano e sia perché i 25 operatori speciali con le loro regole base per valutarne le funzioni chiamate e i tipi di dati built-in forniscono le basi per il resto del linguaggio e una familiarità con loro aiuta a capire come il linguaggio funziona.

Verranno pertanto discussi tutti gli operatori speciali, alcuni solo brevemente e verranno indicati quelli che si usano direttamente quando si scrive codice, che sono quelli alla base di costrutti, e quelli usati raramente che possono servire per costruire macros.

Controllare la valutazione

La prima categoria di operatori speciali è formata da tre elementi che forniscono la base per la valutazione delle forms. Sono quote, if e progn, già visti. Se non ci fosse if lo si potrebbe costruire come macro, usando, p.es. cond. In realtà anticamente…

Manipolare l’ambiente lessicale

Il gruppo più grande di operatori speciali è formato da quelli che manipolano l’accesso all’ambiente lessicale. let e let* che abbiamo già visto ne sono esempi visto che permettono di introdurre nuovi collegamenti lessicali alle variabili. Ogni costrutto come do o dotimes che collega variabili lessicali ha a che fare con let o let* (e lambda). L’operatore speciale setq è uno che accede all’ambiente lessicale visto che può essere usato per settare variabili i cui collegamenti sono creati da let e let*.

Le variabili tuttavia non sono la sola cosa che può essere nominata in uno scopo lessicale. Mentre la maggior parte delle funzioni sono definite con defun è altresì possibile crearne di locali con gli operatori speciali flet e labels e macro locali con macrolet e una macro locale speciale, chiamata symbol macro con symbol-macrolet.

Simili a let, flet e labels permettono di definire una funzione cui ci si può riferire solo dentro lo scopo della form di flet o labels. Questi operatori speciali tornano utili quando serve una funzione locale un po’ troppo complessa per definirla come espressione lambda o che s’intende usare più volte. Ma hanno la stessa forma, questa:

(flet (function-definition*)
  body-form*)

e similmente:

(labels (function-definition*)
  body-form*)

dove ogni function-definition ha la seguente forma:

(name (parameter*) form*)

La differenza tra flet e labels è che i nomi delle funzioni definite in flet possono essere usate solo nel corpo di flet mentre i nomi introdotti con labels si possono usare immediatamente, inclusi i corpi delle funzioni definite dalla labels. Quindi labels può definire funzioni ricorsive mentre flet no. Sembrerebbe una ridondanza ma, dice Peter, possono essere utili entrambe.

Dentro il corpo di una flet o di una labels si possono usare i nomi delle funzioni definite esattamente come ogni altra funzione, incluso l’operatore speciale function. Siccome si può usare function per accedere a oggetti funzione che rappresentano funzioni definite con flet o labels e siccome flet e labels possono essere nello scopo di altre binding forms come lets queste finzioni possono essere closures (non solo sono strane ma viene difficile anche parlarne 👿 ecco).

Siccome le funzioni locali possono riferirsi a variabili nello scopo racchiuso possono essere scritte con meno parametri delle equivalenti funzioni di supporto. Questo è particolarmente utile quando serve una funzione che prende un singolo argomento come parametro funzionale. Per esempio, come useremo in futuro, la funzione con flet count-version prende un singolo argomento come richiesto da walk-directory ma può anche usare la variabile versions, introdotta all’interno della let:

(defun count-versions (dir)
  (let ((versions (mapcar #'(lambda (x) (cons x 0)) '(2 3 4))))
    (flet ((count-version (file)
             (incf (cdr (assoc (major-version (read-id3 file)) versions)))))
      (walk-directory dir #'count-version :test #'mp3-p))
    versions))

Questa funzione può essere scritta usando una funzione anonima al posto della count-version flet-ata ma dando alla funzione un nome significativo la si rende più leggibile.

Poi quando la funzione di supporto richiede ricorsività le funzioni anonime non funzionano più (a meno di usare il Y combinator, una roba che chissà cos’è). In questo caso si usa labels, per esempio la funzione collect-leaves usa la funzione di supporto walk per precorrere un albero e raccogliere tutti gli atomi dell’albero in una lista che collect-leaves ritorna dopo averla invertita:

(defun collect-leaves (tree)
  (let ((leaves ()))
    (labels ((walk (tree)
               (cond
                 ((null tree))
                 ((atom tree) (push tree leaves))
                 (t (walk (car tree))
                    (walk (cdr tree))))))
      (walk tree))
    (nreverse leaves)))

Notare come dentro la funzione walk sia possibile riferirsi alla variabile leaves introdotta nella let.

flet e labels sono utili operazioni da usarsi nelle macro-expansions, una macro può espandere in codice che contiene flet o labels per creare funzioni che possono essere usate all’interno della macro. per esempio una funzione come la call-next-instance che può essere usata solo dentro a un metodo può essere definita in questo modo.

Parente stretta di flet e labels è l’operatore speciale macrolet che può essere usato per definire macros locali. Queste funzionano esattamente come quelle definite con defmacro ma senza alterare il namespace globale. Quando una form macrolet è valutata le forms del corpo sono valutate entro definizioni locali e possibilmente mascherando le funzioni e definizioni di macro globali o definizioni delle forme incluse. macrolet può essere usata direttamente ma è anche comoda in codice generato da macros per cose che vedremo in un lontano futuro (e per adesso incomprensibili, Peter!).

Infine l’operatore speciale symbol-macrolet che definisce la symbol macro. Le symbol macros sono come le macros normali ma prendono un solo argomento e sono riferite come simbolo semplice invece di lista. In altre parole dopo che se n’è definita una con un nome particolare qualsiasi uso di questo simbolo sarà espanso e la form risultante valutata sul posto. Questo è perché macro come with-slots e with-accessors sono capaci di definire variabili che accedono, sotto-sotto, allo stato di un oggetto particolare. Per esempio la seguente form with-slots:

(with-slots (x y z) foo (list x y z)))

può espandersi in questo codice che usa symbol-macrolet:

(let ((#:g149 foo))
  (symbol-macrolet
      ((x (slot-value #:g149 'x))
       (y (slot-value #:g149 'y))
       (z (slot-value #:g149 'z)))
    (list x y z)))

Quando l’espressione (list x y z) è valutata i simboli x, y e z sono sostituiti dalle loro espansioni, tipo (slot-value #:g149 'x).

Le symbol macros sono spesso locali, definite con symbol-macrolet ma c’è anche la macro define-symbol-macro che definisce una symbol macro globale. Una symbol macro definita con symbol-macrolet maschera altre symbol macros con lo stesso nome definite con define-symbol-macro o racchiudenti forms symbol-macrolet.

Flusso locale di controllo

I successivi quattro operatori alterano il flusso di controllo. Sono block, return-from, tagbody e go. block e return-from sono usati assieme per scrivere codice che ritorna immediatamente da una sezione di codice. tagbody e go forniscono un costrutto di basso livello che è alla base di costrutti di alto livello di loop, come già visto.

Lo schema base di block è:

(block name
  form*)

Dove name è un simbolo. le forms sono valutate in ordine e il valore dell’ultima è ritornata come valore del block a meno che un return-from venga usato per tornare prima. Un return-from consiste del nome del block da cui tornare e, opzionalmente, una form che fornisce il valore da ritornare. Se return-from viene chiamato con una form il block restituisce quel valore, altrimenti nil.

Un nome del block può essere anche un simbolo, incluso nil. Parecchie macro standard come do, dotimes e dolist generano espansioni consistenti di block chiamati nil. Questo consente di usare la macro return che è un po’ zucchero sintattico (sì, pare che si dica così anche in ‘taliano) per (return-from nil ...), per uscire da quei loops. Quindi il loop seguente scrive fino a dieci numeri random fermandosi quando ne trova uno maggiore di 50:

o0

Macros che definiscono funzioni come defun, flet e labels d’altra parte avvolgono il loro corpo in un block avente il nome della funzione. Ecco perché si può usare return-from per ritornare da una funzione.

tagbody e go hanno una relazione similare a block e return-from. Una form tagbody definisce un contesto nel quale sono definiti nomi che possono essere usati da go. Lo schema di un tagbody è il seguente:

(tagbody
  tag-or-compound-form*)

dove tag-or-compound-form è o un simbolo, chiamato tag, o una lista non vuota. Le forms sono valutate in ordine e i tags ignorati, tranne quel che vedremo a breve. Dopo che l’ultima form del tagbody è valutata tagbody ritorna nil. Dovunque nello scopo lessicale del tagbody si può usare go per saltare immediatamente a qualunque dei tags e la valutazione ripartirà con la form seguente il tag. Per esempio si può scrivere un banale ciclo infinito con tagbody e go così:

(tagbody
 top
   (print 'hello)
   (go top))

Notare che mentre i nomi dei tags debbono comparire a top-level del tagbody, non annidati entro altre forms l’operatore go può apparire ovunque dentro lo scopo del tagbody. Si può così scrivere un ciclo che scrive un numero random di volte così:

o1

Un esempio con tags multipli:

o2

Questa form salta su e giù finché l’ultima espressione random ritorna 1 e il controllo raggiunge la fine del tagbody.

tagbody viene usato raramente, esistono costrutti alternativi per i cicli. E sì, proprio come pensavo ricorda il Fortran delle origini (e il Basic, GW e affini).

Similmente tagbody e go fanno comodo per tradurre algoritmi descritti in prosa o flow-chart, per esempio in The Art of Computer Programming di Donald Knuth gli algoritmi vendono descritti unando questo formato di ricetta:  step 1, do this; step 2, do that; step 3, go back to step 2; and so on. Per esempio a p.142 del volume 2 descrive l’algoritmo S:
La descrizione può facilmente essere tradotta in una funzione dopo aver rinominato qualche variabile, così:

Algorithm S (Selection sampling technique). To select n records at random 
from a set of N, where 0 < n <= N.
S1. [Initialize.] Set t <-- 0, m <-- 0. (During this algorithm, m represents
    the number of records selected so far, and t is the total number of input
    records that we have dealt with.)
S2. [Generate U.] Generate a random number U, uniformly
    distributed between zero and one.
S3. [Test.] If (N - t)U >= n - m, go to step S5.
S4. [Select.] Select the next record for the sample, and
    increase m and t by 1. If m < n, go to step S2;
    otherwise the sample is complete and the algorithm 
    terminates.
S5. [Skip.] Skip the next record (do not include it in the
    sample), increase t by 1, and go back to step S2.

La descrizione può facilmente essere tradotta in una funzione dopo aver rinominato qualche variabile, così:

(defun algorithm-s (n max) ; max is N in Knuth's algorithm
  (let (seen               ; t in Knuth's algorithm
        selected           ; m in Knuth's algorithm
        u                  ; U in Knuth's algorithm
        (records ()))      ; the list where we save the records selected
    (tagbody
     s1
       (setf seen 0)
       (setf selected 0)
     s2
       (setf u (random 1.0))
     s3
       (when (>= (* (- max seen) u) (- n selected)) (go s5))
     s4
       (push seen records)
       (incf selected)
       (incf seen)
       (if (< selected n)
           (go s2)
           (return-from algorithm-s (nreverse records)))
     s5
       (incf seen)
       (go s2))))

Non è il codice migliore (a me lo dici!? sapessi…) ma è facile verificare che è l’esatta traduzione dell’algoritmo di Knuth.

Una soluzione migliore (sì…!):

(defun algorithm-s (n max)
  (loop for seen from 0
     when (< (* (- max seen) (random 1.0)) n)
     collect seen and do (decf n)
     until (zerop n)))

OK, personalmente non è una cosa nuova 😀 anzi :mrgreen:
Continua.

Posta un commento o usa questo indirizzo per il trackback.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: