Un’altra breve introduzione a Racket con figure (e Adrian Frutiger)
1 Introduzione
2 Prima tavola
3 Liste
4 Ricorsione
5 Semplifichiamo combine
6 Costruiamo la tavola
7 Tutto il codice per la prima tavola
8 La seconda tavola
6.1

Un’altra breve introduzione a Racket con figure (e Adrian Frutiger)

1 Introduzione

In questo breve tutorial useremo Racket per riprodurre le tavole morfologiche (1 e 2) del libro di Adrian Frutiger Segni e Simboli. In queste tavole i segni sono costruiti combinando un numero ristretto di linee. Vedremo in che modo, usando un procedimento ricorsivo, possiamo produrre queste combinazioni.

In questo breve percorso vedremo alcune cose, come strutture di dati e procedure ricorsive, funzioni come map che ci consentono di fare a meno del ciclo for e altre cose più o meno divertenti. L’approccio è non rigorosamente funzionale, se siete interessati, in giro si trova parecchia roba sulla functional programming. I nomi in azzurro sono in genere cliccabili e rimandano alla documentazione di Racket, che vi invito ad esplorare, perché è fatta molto bene.

2 Prima tavola

image

Questa è la tavola più semplice, realizzata a partire da sei tratti (tre orizzontali e tre verticali), le diverse combinazioni si ottengono includendo o escludendo alcuni di questi tratti dal segno. Il segno più pieno conterrà quindi tutti e sei i tratti (in basso a destra), quello più vuoto non ne conterrà nessuno (in alto a sinistra). Nel libro Frutiger include solamente i segni con almeno un tratto orizzontale e uno verticale, escludendo quindi la prima riga e la prima colonna della figura riportata sopra; per semplicità noi includeremo tutti i segni. Tutti i segni occupano un quadrato

Per iniziare dobbiamo impostare il linguaggio slideshow nella prima riga del nostro file.

#lang slideshow

Un’espressione in Racket può essere un valore, come un numero 5 o una stringa "wow", oppure può essere una forma più complessa messa tra parentesi (+ 1 2). Spostiamoci nella parte bassa della finestra e scriviamo:
> 5

5

> "wow"

"wow"

Quando inseriamo un’espressione Racket la valuta e risponde con un risultato, nel caso di valori, come quelli inseriti sopra, il risultato non è particolarmente interessante. Nel caso di espressioni più complesse, messe tra parentesi, come per esempio le chiamate alle funzioni, Racket ’valuta’ l’espressione e produce un risultato

> (+ 1 2)

3

In questo caso si tratta della somma. Se vi state domandando perché il segno + è davanti ai numeri invece che tra i numeri, probabilmente non avete familiarità con lisp. La spiegazione è semplice, l’espressione tra parentesi chiama una funzione, la funzione è la prima parte dopo la parentesi aperta, le parti che seguono sono gli argomenti (qui sono i numeri 1 e 2), quindi possiamo leggere (+ 1 2) così: applica la funzione somma agli argomenti 1 e 2. Basta prendere un po’ l’abitudine e poi si può apprezzare questa sintassi.

Scrivere ogni volta i valori può essere molto noioso, ed è fonte di errori, per questo possiamo dare un nome ai valori:

> (define wow (+ 1 2))
> wow

3

Abbiamo definito wow con il risultato dell’espressione (+ 1 2) quindi, ogni volta che scriviamo wow, otteniamo 3.

Un genere di valori che ci sarà utile è quello delle immagini. Ne vedremo alcune, ma ecco qui un cerchio di 20 pixel di diametro:

> (circle 20)

image

Torniamo al nostro compito: possiamo definire alcune costanti che ci torneranno utili in avanti:il lato del quadrato occupato da ogni segno (che definisce la sua dimensione), lo spessore dei tratti e un quadrato vuoto (crate con blank)che ci servirà come base per assemblare i segni (notiamo che il quadrato vuoto usa la costante size definita poco prima per il lato). Come si vede possiamo dare un nome al risultato di qualsiasi espressione, in questo caso il quadrato vuoto:

> (define size 50)
> (define line-width 3)
> (define empty-square (blank size size))

Abbiamo anche bisogno dei due tratti base, verticale e orizzontale, usiamo per questo la funzione filled-rectangle che produce un rettangolo nero.

> (define horizontal (filled-rectangle size line-width))
> (define vertical (filled-rectangle line-width size))

Per creare i segni compositi, useremo un metodo di composizione che crea nuovi simboli a partire da vecchi. Questa parte è abbastanza importante: noi abbiamo i tratti orizzontale e verticale e li assembliamo con una funzione che produce un nuovo oggetto senza modificare gli oggetti di partenza. Le diverse procedure usate per queste composizioni sono lt-superimpose, cc-superimpose, ecc., Un esempio può aiutare:
> (cc-superimpose horizontal vertical)

image

Questa espressione ha prodotto un nuovo oggetto dalla sovrapposizione al centro di horizontal e vertical. Il primo obiettivo è quello di creare delle immagini quadrate con i tratti orizzontali disposti in alto, al centro e in basso e delle immagini quadrate con i tratti verticali disposti a sinistra, al centro e a destra. Per fare questo usiamo il quadrato vuoto come riferimento e creiamo delle immagini composte allineando i tratti al quadrato nella posizione desiderata (alto, basso, centro, destra, sinistra).

> (define h1
   (lt-superimpose
    empty-square
    horizontal))
> (define h2
    (cc-superimpose
     empty-square
     horizontal))
> (define h3
    (lb-superimpose
     empty-square
     horizontal))
> (define v1
    (lt-superimpose
     empty-square
     vertical))
> (define v2
    (cc-superimpose
     empty-square
     vertical))
> (define v3
    (rt-superimpose
     empty-square
     vertical))

Per vederli insieme in una linea usiamo hc-append per creare una nuova immagine:

> (hc-append 10 h1 h2 h3 v1 v2 v3)

image

Avendoli messi tutti all’interno di un quadrato di uguali dimensioni (con uno sfondo trasparente dato dal quadrato vuoto) sarà molto comodo creare simboli composti a partire da questi. Per esempio, per creare il simbolo composto da h1 e v2:

> h1

image

> v2

image

> (cc-superimpose h1 v2)

image

Adesso dobbiamo creare la procedura che produrrà le combinazioni; per capire come impostarla possiamo ragionare in questo modo: le combinazioni possibili di tutti i tratti possono essere divise in due, quelle che non includono il primo tratto e quelle che lo includono, le prime sono le combinazioni di tutti i tratti tranne il primo, le seconde sono ottenute aggiungendo il primo tratto alle combinazioni di tutti i tratti tranne il primo (le prime, chiaro no?).

Un esempio con tre tratti ci può aiutare(il bordo intorno ai segni ci serve per distinguerli).

image

I primi quattro segni non includono il tratto superiore, gli altri quattro sono uguali ai primi con il tratto superiore aggiunto.

Rimane da capire come otteniamo le combinazioni di tutti i tratti tranne il primo, ma la risposta è semplice, le otteniamo come abbiamo ottenuto le combinazioni di tutti i tratti!

3 Liste

Dobbiamo fare una breve digressione sulle liste per poter procedere. La funzione che produce una lista è semplicemente list e si usa così:

> (list 1 2 3 4)

'(1 2 3 4)

Dobbiamo però sapere che una lista è formata in modo bizzarro (e bellissimo), per esempio, la lista di prima è formata da due parti: la prima è il numero 1, la seconda è la lista (list 2 3 4). E come è fatta la lista (list 2 3 4)? ovviamente è formata da due parti, il numero 2 e la lista (list 3 4), e così via. Eh, ma, "e la lista (list 4)?" Anche quella. È formata dal numero 4 e dalla lista vuota null (questa è rappresentata con l’espressione '()).

La domanda allora è, come accedo alle due parti delle liste? Con le funzioni car (per la prima parte) e cdr (per la seconda). C’è da notare che questo vale anche per la costruzione delle liste, attraverso cons: (cons 1 (list 2 3 4)) è come dire (list 1 2 3 4). Vediamo se quello che ho detto è vero:

> (define l (list 1 2 3 4))
> (car l)

1

> (cdr l)

'(2 3 4)

> (cdr (cdr l))

'(3 4)

> (cdr (cdr (cdr l)))

'(4)

> (cdr (cdr (cdr (cdr l))))

'()

Prendiamo un po’ di tempo per vedere anche come funzionano le espressioni e le funzioni: l’ultima riga chiama la funzione cdr con un argomento che è a sua volta il risultato di un’espressione (che è anche questa una chiamata a cdr con un argomento ..., ci siamo capiti).

> (list 1 2 3 4)

'(1 2 3 4)

> (cons 1 (list 2 3 4))

'(1 2 3 4)

> (cons 1 (cons 2 (cons 3 (cons 4 null))))

'(1 2 3 4)

Producono tutte la stessa lista.

4 Ricorsione

Per tornare a Frutiger, quello che volevamo fare è creare una funzione in grado di produrre tutte le combinazioni dei tratti. Chiameremo questa funzione combine, ma prima vediamo come definire una funzione.

(define (nome-funzione argomento-1 argomento-2)
  espressioni ...)

In questo modo si definisce una funzione chiamata nome-funzione che accetta due argomenti. Le espressioni ... sono il ’corpo’ della funzione e vengono valutate quando la funzione è chiamata. La chiamata della funzione produce il risultato dell’ultima espressione. Un esempio:

> (define (aggiungi-1 n)
    (+ n 1))
> (aggiungi-1 2)

3

> (aggiungi-1 100)

101

Il corpo della funzione aggiungi-1 è costituito da una sola espressione, che somma 1 all’argomento; il risultato di questa espressione è anche il risultato della funzione. Le persone abituate con altri linguaggi potrebbero chiedersi dov’è il return, e la risposta è che non c’è nessun return, semplicemente l’espressione (aggiungi-1 100) vale (+ 100 1).

Sulle funzioni ci sarebbero più cose da dire, ma voglio evitare di complicare troppo l’argomento.

Ok, adesso torniamo davvero al nostro compito. Dato che il numero di elementi da combinare può variare (nella prima tavola sono 6, nella seconda 12), ha senso pensare di passare alla funzione una lista di tratti. Questa procedura, inoltre, produrrà una lista di tutte le combinazioni. Possiamo quindi cominciare a scrivere:

(define (combine lst)
  ...)

Tornando alla descrizione del problema vediamo che le combinazioni di tutti i tratti tranne il primo si possono ottenere con (combine (cdr lst)), infatti cdr produce il resto dei tratti e combine li combina. Alle combinazioni così ottenute dobbiamo aggiungere quelle che includono il primo tratto che, come abbiamo detto, sono costruite aggiungendo il primo tratto alle prime (nel fare questo immaginiamo di avere già una funzione put-stroke-on-each, che dovremo scrivere, che fa questa operazione. Questa funzione riceve due argomenti, il tratto da aggiungere e una lista di combinazioni, e produce una lista di combinazioni):

(put-stroke-on-each (car lst) (combine (cdr lst)))

Il risultato di combine sarà una lista di combinazioni, che dobbiamo concatenare alla lista delle combinazioni prodotta aggiungendo il primo tratto. Per concatenare una lista a un’altra lista possiamo usare append

(append (combine (cdr lst))
        (put-stroke-on-each (car lst)
                            (combine (cdr lst))))

Questa espressione fa questo: prende la ’coda’ della lista con cdr e trova tutte le combinazioni di questa, poi aggiunge a queste le combinazioni che hanno anche il primo tratto.

Quindi combine diventa simile a:

(define (combine lst)
  (append (combine (cdr lst))
          (put-stroke-on-each (car lst)
                              (combine (cdr lst))))
  ...)

Quello che abbiamo fatto è stato richiamare la stessa funzione su una lista più corta. A sua volta questa la chiamerà su una lista più corta e così via, riducendo di volta in volta la complessità del problema. Ma cosa succede quando (cdr lst) è null? combine viene chiamata con null, e a sua volta tenterebbe di chiamare cdr con null producendo un errore.

Dobbiamo indicare una condizione per terminare prima! Quasi sempre, se si usa una lista, questa codizione è la lista vuota.

Ma che combinazioni otteniamo da una lista vuota di tratti? Pensiamo prima a una lista di un solo tratto. Le combinazioni possibili sarebbero il quadrato vuoto e il tratto stesso. La cosa più logica è quindi che (combine null) produca una lista che contiene il quadrato vuoto.

Ora, per aggiornare la nostra funzione, dobbiamo poter dire: se la lista è vuota: produci una lista che contiene il quadrato vuoto, altrimenti usa l’espressione che abbiamo scritto sopra.

Questa condizione si può esprimere con un’espressione un po’ speciale: if. if non è una funzione, ma una ’forma speciale’ ed è costituita da tre parti

(if condizione se-è-vera altrimenti)

(define (combine lst)
  (if (null? lst)
      (list empty-square)
      (append (combine (cdr lst))
              (put-stroke-on-each (car lst)
                                  (combine (cdr lst))))))

Tutto questo funziona ed è bellissimo.

Questa versione di combine ha un problema: calcola due volte (combine (cdr lst)), e questo spreca parecchie risorse, possiamo eliminare la ripetizione salvando localmente il risultato di questa operazione, e questo con un’altra forma speciale che è let.

> (define (combine lst)
    (if (null? lst)
        (list empty-square)
        (let ([cmbs (combine (cdr lst))])
          (append cmbs
                  (put-stroke-on-each (car lst)
                                      cmbs)))))

Abbiamo lasciato in sospeso put-stroke-on-each. Prenderemo prima una strada lunga e poi una strada breve.

Sappiamo già quali sono gli argomenti:

(define (put-stroke-on-each strk cmbs)
  ...)

Anche qui abbiamo una lista e possiamo usare la stessa strategia di decomposizione e di composizione (ricordiamoci di cons!)

(define (put-stroke-on-each strk cmbs)
  (if (null? cmbs)
     null
     (cons (cc-superimpose strk (car cmbs))
           (put-stroke-on-each strk (cdr cmbs)))))

Il procedimento è semplice, prendiamo il primo elemento (car) di cmbs e ci sovrapponiamo strk, il risultato lo aggiungiamo in testa a una nuova lista costruita chiamando put-stroke-on-each sul resto di cmbs. Quando raggiungiamo la fine della lista la procedura ci restituisce la lista vuota. Questa tecnica è molto usata tanto che esiste una procedura (map) che fa questo: transforma ogni elemento di una lista applicando una funzione.

> (define (put-stroke-on-each strk cmbs)
    (define (my-superimpose c) (cc-superimpose strk c))
    (map my-superimpose cmbs))

Analizziamo quello che ho scritto: la prima riga del corpo della funzione usa define per definire un nome (my-superimpose) ’locale’ (questo nome esiste solo dentro a put-stroke-on-each); la seconda riga usa la funzione map che prende come primo argomento una funzione e come secondo una lista.

Ehi!, ma una funzione può essere passata come se fosse un qualsiasi valore? Si, perché le funzioni sono valori come tutti gli altri.

Come funziona map? Applica la funzione (in questo caso my-superimpose) a ogni elemento della lista e produce una nuova lista con i risultati. Notiamo bene che my-superimpose produce un risultato, quindi la lista che otteniamo sarà lunga come la lista originale ma fatta con i risultati di my-superimpose.

È come se ogni elemento della lista fosse trasformato dalla funzione, ma il risultato è una lista nuova.

Possiamo finalmente provare a usare combine

> (combine (list h1 h2 v2))

'(image image image image image image image image)

(Notiamo le parentesi! Il risultato di combine è una lista.)

5 Semplifichiamo combine

In questa sezione cercheremo di semplificare combine, ma vedremo anche altre cose.

In primo luogo in put-stroke-on-each abbiamo usato una definizione interna per avere una funzione da passare a map, ma questo non è necessario. Possiamo creare una funzione anonima ’al volo’, con la forma lambda.

Come si vede, questa è come la funzione definita con define, ma senza un nome; viene creata solamente per essere passata a map.

(map (lambda (c) (cc-superimpose strk c)) cmbs)

A questo punto, possiamo sostituire put-stroke-on-each all’interno di combine con la riga appena scritta:

(define (combine lst)
  (if (null? lst)
      (list empty-square)
      (let ([cmbs (combine (cdr lst))])
        (append cmbs
                (map (lambda (c) (cc-superimpose (car lst) c))
                     cmbs)))))

Vediamo finalmente tutti i risultati di combine
> (combine (list  h1 h2 h3 v1 v2 v3))

'(image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image

  image)

Ma stampare la lista dei risultati non è molto bello, la sezione che segue costruirà la tavola in un formato più elegante.

6 Costruiamo la tavola

Per costruire la tavola useremo impileremo le righe una sull’altra, e ogni riga sarà ottenuta accostando otto segni. A leggerla sempbra un po’ più complicata per via di take e drop, ma queste funzioni servono solamente a prendere otto simboli per volta.

> (require racket/list)
> (define (make-first-table signs)
    (if (> (length signs) 8)
        (vc-append 10
                   (apply hc-append 10 (take signs 8))
                   (make-first-table (drop signs 8)))
        (apply hc-append 10 signs)))
> (make-first-table (combine (list h1 h2 h3 v1 v2 v3)))

image

7 Tutto il codice per la prima tavola

(require racket/list)
 
(define size 50)
(define line-width 3)
(define empty-square (blank size size))
 
(define horizontal (filled-rectangle size line-width))
(define vertical (filled-rectangle line-width size))
 
(define h1
 (lt-superimpose
  empty-square
  horizontal))
 
(define h2
  (cc-superimpose
   empty-square
   horizontal))
 
(define h3
  (lb-superimpose
   empty-square
   horizontal))
 
(define v1
  (lt-superimpose
   empty-square
   vertical))
 
(define v2
  (cc-superimpose
   empty-square
   vertical))
 
(define v3
  (rt-superimpose
   empty-square
   vertical))
 
(define (combine lst)
  (if (null? lst)
      (list empty-square)
      (let ([cmbs (combine (cdr lst))])
        (append cmbs
                (map (lambda (c) (cc-superimpose (car lst) c))
                     cmbs)))))
 
(define (make-first-table signs)
 (if (> (length signs) 8)
     (vc-append 10
                (apply hc-append 10 (take signs 8))
                (make-first-table (drop signs 8)))
     (apply hc-append 10 signs)))

8 La seconda tavola

La seconda tavola presentata da Frutiger è molto più grande (contiene più di 4000 segni), quindi non è molto pratico visualizzarla intera. Creeremo un meccanismo per ottenere il segno che si trova alla riga i e alla colonna j, inoltre, data la grandezza, invece di assemblare tutte le combinazioni in una garnde tavola, cercheremo di rimandarne il calcolo fino a quando non sono richieste. Per fare questo useremo stream.

> (require racket/stream)

Uno stream funziona un po’ come una lista, ma ha le sue procedure:

stream-cons al posto di cons

stream-first al posto di car

stream-rest al posto di cdr

stream-map al posto di map

Possiamo provare a scrivere l’equivalente di combine con gli streams.

> (define (stream-combine lst)
    (if (null? lst)
        (stream empty-square)
        (let ([cmbs (stream-combine (cdr lst))])
          (stream-append cmbs
                         (stream-map
                          (lambda (c) (cc-superimpose (car lst) c))
                          cmbs)))))

Adesso dobbiamo definire i nuovi tratti e provare a usare stream-combine.

> (define horizontal/2
    (filled-rectangle
     (/ (+ size line-width) 2)
     line-width))
> (define vertical/2
    (filled-rectangle
     line-width
     (/ (+ size line-width) 2)))
> (define hb1
    (lt-superimpose
     empty-square
     horizontal/2))
> (define hb2
    (rt-superimpose
     empty-square
     horizontal/2))
> (define hb3
    (lc-superimpose
     empty-square
     horizontal/2))
> (define hb4
    (rc-superimpose
     empty-square
     horizontal/2))
> (define hb5
    (lb-superimpose
     empty-square
     horizontal/2))
> (define hb6
    (rb-superimpose
     empty-square
     horizontal/2))
> (define vb1
    (lt-superimpose
     empty-square
     vertical/2))
> (define vb2
    (ct-superimpose
     empty-square
     vertical/2))
> (define vb3
    (rt-superimpose
     empty-square
     vertical/2))
> (define vb4
    (lb-superimpose
     empty-square
     vertical/2))
> (define vb5
    (cb-superimpose
     empty-square
     vertical/2))
> (define vb6
    (rb-superimpose
     empty-square
     vertical/2))
> (define cmbs2
    (stream-combine
     (list hb1 hb2 hb3 hb4 hb5 hb6
           vb1 vb2 vb3 vb4 vb5 vb6)))

Per accedere ai vari elementi di questo stream, vogliamo creare un’interfaccia usabile. La possiamo realizzare con una funzione a cui passare il numero di riga e il numero di colonna e produce l’elemento desiderato:

> (define (table-accessor r c)
    (define size 64)
     (if (and (< c size) (< r size)
              (> c 0) (> r 0))
         (stream-ref cmbs2 (+ (* r size) c))
         (error "Index out of bounds")))
> (table-accessor 2 4)

image

> (table-accessor 7 10)

image

> (table-accessor 5 60)

image

Quest’ultima funzione potevamo renderla migliore, ma questo complicherebbe un po’ il lavoro.