Visualizza il feed RSS

Titolo provvisorio...

zigzag =: $ [: /:@; [: <@|.`</. [: |. i.

Valuta questo inserimento
di pubblicato il 06-02-2012 alle 20:05 (4437 Visite)
Il titolo è inequivocabile: parliamo nuovamente di J, uno dei miei linguaggi preferiti in assoluto. Un valido spunto per tornare a parlare di questo potentissimo e sintetico linguaggio di programmazione è dato da questo thread nell'altra bottega: un esercizio molto comune nella didattica dei vari linguaggi, in tutte le sue varianti.

In questa occasione, vedremo come popolare una generica matrice mxn secondo lo schema indicativo qui riportato:

Formula LaTeX: \begin{array}{rrrr}3 & 8 & 9 & 11\\2 & 4 & 7 & 10\\0 & 1 & 5 & 6\end{array}

Poniamo, giusto per fissare le idee:

Formula LaTeX: 3 \leq m \leq n\ \ \ \text{con }m \in \mathbb{N} \text{ e }n \in \mathbb{N}

Convenendo di far partire gli indici da zero e di anteporre l'indice di riga, siano ai,j gli elementi della matrice. In riferimento allo schema 3x4 appena presentato, appare immediatamente chiaro che un ordinamento come quello richiesto corrisponde ad un "percorso" attraverso l'array che tocca, nell'ordine, le seguenti celle:

a2,0, a2,1, a1,0, a0,0, a1,1, a2,2, a2,3, a1,2, a0,1, a0,2, a1,3, a0,3

Sarebbe parimenti facile riportare, per ogni "mossa", la relativa regola applicata sotto forma di freccia direzionale e/o trasformazione da applicare alla coppia di indici correnti per ottenere la successiva, ottenendo così una rappresentazione operazionale adatta ad una soluzione per FSM o per trasformazioni successive.

Tuttavia, tra le numerose soluzioni disponibili (reticolari e modulari, algebriche, a stati finiti...) ritengo in questa sede di privilegiare quella algebrica, basata sulla seguente osservazione. Per comodità, riportiamo intanto in ogni cella i relativi indici di riga e colonna, secondo le nostre comode convenzioni informatichesi:

Formula LaTeX: \begin{array}{rrrr}0,0 & 0,1 & 0,2 & 0,3\\1,0 & 1,1 & 1,2 & 1,3\\2,0 & 2,1 & 2,2 & 2,3\end{array}

Provando a sommare gli indici contenuti di ciascuna cella, si nota qualcosa di decisamente banale, ma forse non ovvio, che aiuta a costruire un approccio destinato a risolvere con facilità tutti gli esercizi di questa categoria:

Formula LaTeX: {\color{red}\begin{array}{rrrr}0 & 1 & 2 & 3\\1 & 2 & 3 & 4\\2 & 3 & 4 & 5\end{array}}

Dunque la somma degli indici è costante per ciascuna antidiagonale, ed identifica in modo immediato l'antidiagonale stessa. Una volta notato che ciascuna antidiagonale è univocamente identificata dalla somma degli indici delle corrispondenti coordinate, il relativo programmino in C o in Python è in pratica già scritto.

Occorre solo mettere a fuoco un paio di dettagli oggettivamente meno interessanti, come il punto di partenza di ciascuna antidiagonale e la relativa lunghezza.
Ecco un paio di spunti in proposito, ovviamente ad usum delphini. Si osservi, intanto, che si ha:

Formula LaTeX: \begin{array}{rrrr}0&\nearrow&\nearrow&\nearrow\\1  &\nearrow&\nearrow&\nearrow\\2&3&4&5\end{array}

Nel seguente frammento di codice C, siano R e C rispettivamente i limiti superiori per gli indici di riga e colonna della matrice. Abbiamo esplicitato in modo assolutamente ridondante tutte le variabili necessarie alla generazione esaustiva degli indici per una copertura della matrice per antidiagonali, indicando anche con chiarezza la dimensione di ciascuna di quest'ultime - tra parentesi quadre nella printf() di controllo.
Il codice fornisce in output una lista ordinata, human-readable, delle coordinate di ciascuna cella appartenente ad ogni antidiagonale, dalla 0 alla R + C incluse, ossia - in ultima analisi - la sequenza in cui vengono "visitate" le singole celle della matrice.

codice:
    int ad, col;
    int diags = R + C + 1;

    for (ad = 0; ad < diags; ++ad)
    {
        int first = (ad <= R) ? 0 : ad - R;
        int last  = 1 + min(ad, C);
	printf("%2d [%d]: ", ad, last - first);
	for (col = first; col < last; ++col)
	{
            printf("(%d,%d)", ad - col, col);
	}
	puts("");
    }
Esempio di output per R = 4, C = 8:
codice:
 0 [1]: (0,0)
 1 [2]: (1,0)(0,1)
 2 [3]: (2,0)(1,1)(0,2)
 3 [4]: (3,0)(2,1)(1,2)(0,3)
 4 [5]: (4,0)(3,1)(2,2)(1,3)(0,4)
 5 [5]: (4,1)(3,2)(2,3)(1,4)(0,5)
 6 [5]: (4,2)(3,3)(2,4)(1,5)(0,6)
 7 [5]: (4,3)(3,4)(2,5)(1,6)(0,7)
 8 [5]: (4,4)(3,5)(2,6)(1,7)(0,8)
 9 [4]: (4,5)(3,6)(2,7)(1,8)
10 [3]: (4,6)(3,7)(2,8)
11 [2]: (4,7)(3,8)
12 [1]: (4,8)
Non dovrebbe essere necessario rimarcare che tutte le varianti del problemino sono ottenibili con banali rotazioni e trasposizioni della matrice iniziale, effettuate operando unicamente sugli indici. A questo punto, abbiamo praticamente già scritto una possibile soluzione in linguaggio C, sulla quale non mi soffermerei più di tanto: zigzag_c.txt.
L'input delle dimensioni da console è lasciato come (noioso, ma utile) esercizio per il lettore.
codice:
/* EOF: zigzag.c 95 lines 387 words 2667 characters */
Ecco uno snapshot dell'output, dopo avere compilato (ça va sans dire...) con BCC 5.5.1:
codice:
Creazione di una matrice a zig-zag: 5 x 9

10 19 20 29 30 38 39 43 44
 9 11 18 21 28 31 37 40 42
 3  8 12 17 22 27 32 36 41
 2  4  7 13 16 23 26 33 35
 0  1  5  6 14 15 24 25 34

Creazione di una matrice a zig-zag: 5 x 5

10 18 19 23 24
 9 11 17 20 22
 3  8 12 16 21
 2  4  7 13 15
 0  1  5  6 14
Passiamo alla parte maggiormente utile. Naturalmente in J non abbiamo alcuna necessità di impiastricciarci le mani con questi dettagliucci di bassa cucina. I banali vincoli sopra elencati vengono gestiti in modo trasparente ed efficiente dai potentissimi operatori e dalle ricche primitive del linguaggio.

L'espressione finale necessaria ad ottenere il risultato desiderato è la seguente, come da titolo, e consta di "ben" trentadue caratteri, inclusi gli spazi (opzionali) e le parentesi (idem):
codice:
   ($ [: /:@; [: <@|.`</. [: |. i.) 3 4
3 8 9 11
2 4 7 10
0 1 5  6
Come di consueto in letteratura, riporto qui le istruzioni J e il relativo output, riproducibile nell'ambiente interattivo J 6.02 (la versione 7 è leggermente più ostica per i neofiti).

La superiorità rispetto agli oltre duemilaseicento caratteri - "fuori tutto", come si dice in Marina - del programma C appena presentato è semplicemente schiacciante. Appare pressoché impossibile ottenere una concisione maggiore, eccetto forse con una macro entro qualche esotico ambiente di calcolo matriciale. Qui diviene tangibile l'enorme potenza di un linguaggio come J, nato appositamente per l'algebra lineare e la matematica discreta.

Il rovescio della medaglia appare altrettanto evidente. Mettete "quella roba" davanti al naso di un practitioner quadratico medio, diplomato o laureato che sia: per quanto "bravo" ed "esperto" nel 999,9 per mille dei casi vi dirà che "...non ha alcun senso, hai lasciato passeggiare il micio sulla tastiera...".

E invece J è anche relativamente facile da leggere (più del perl, tanto per dire), con un minimo di allenamento. Qui, usando come scusa il problema dello zig-zag, cercherò di trasmettervi il principio che lo scoglio principale, più che i digrafi e trigrafi, sono i concetti del linguaggio, decisamente controintuitivi per la maggioranza degli informatici.

Per questo vorrei tentare di spiegare più da vicino, spazio permettendo, "come funziona" l'espressione prodotta.
Dal punto di vista logico, l'espressione compie le seguenti operazioni:
1) Generazione di una matrice opportunamente popolata dai primi mxn interi;
2) Lettura per antidiagonali, in direzioni alternate;
3) Ordinamento dei valori per righe e colonne;
4) Presentazione del risultato.
Vediamole con maggiore dettaglio.

1) Generazione della matrice.
Occorre subito rimarcare che le espressioni in J vengono valutate DA DESTRA A SINISTRA, e come tali conviene leggerle, a meno ovviamente delle parentesi. Pertanto dovremo iniziare la nostra analisi da |.i., che peraltro è la parte più semplice: si tratta di un generatore di numeri interi non negativi, in grado con identica semplicità di generare sequenze e matrici multidimensionali.
codice:
   i.3
0 1 2
   i.5
0 1 2 3 4
   i.3 4
0 1  2  3
4 5  6  7
8 9 10 11
Semplice, vero? Allo stesso modo, con l'operatore |. possiamo invertire l'ordine di generazione.
codice:
   |.i.3
2 1 0
   |.i.3 4
8 9 10 11
4 5  6  7
0 1  2  3
2) Lettura per antidiagonali.
A noi occorre ora "passeggiare" sulle antidiagonali della matrice così popolata. Il problema è ovviamente molto comune nel calcolo matriciale, che è il vero e proprio terreno di coltura di J: dunque non deve stupire il fatto che esista un apposito operatore, /.
codice:
   </.|.i.3 4
+-------------------------+
¦8¦9 4¦10 5 0¦11 6 1¦7 2¦3¦
+-------------------------+
Il costrutto /. applica la funzione che lo precede (in questo caso il boxing <) alle antidiagonali di una matrice, per ottenere il bel risultato visibile sopra: l'input viene suddiviso, appunto, per antidiagonale.

Prima di procedere oltre, è però il caso di spiegare un altro paio di concetti fondamentali in J. In tale linguaggio non esiste priorità degli operatori, neppure di un limitato sottoinsieme (es. operazioni algebriche e logiche), per il semplice motivo che J riconosce circa duecentocinquanta operatori e un gran numero di loro combinazioni: una complessità che supera di gran lunga la capacità ragionevolmente gestibile da un interprete o compilatore - per non dire delle ancor più limitate capacità del bipede che sta seduto davanti alla tastiera.

Ciò implica che, ad esempio, i risultati di una sequenza di operazioni algebriche potrebbero sorprendervi, se non siete più che accorti nell'uso delle parentesi.

Quanto appena asserito ha rilevanza particolare in un caso che ci riguarda da vicino: la composizione di funzioni tramite il cosiddetto "gerundio". In effetti, in J la sintassi è specificata con una nomenclatura strettamente modellata attorno a quella del linguaggio naturale, e in particolare all'analisi grammaticale e quindi alle parti del discorso.
In realtà il gerundio, al di là dei casi degeneri (è applicabile anche ad una singola funzione, usando una sintassi particolare), può e deve interpretarsi come in linguaggio C si considera una lista di puntatori a funzione.
In effetti J ha la sorprendente capacità di iterare sui medesimi dati due o più funzioni, alternandole ed espandendole adeguatamente: tutto ciò grazie al costrutto detto, appunto, gerundio.
Vediamo un semplice esempio - e, di nuovo: attenzione alla mancanza di priorità degli operatori!
codice:
1)   2+i.4
2 3 4 5
2)   +/2+i.4
14
3)   */2+i.4
120
4)   +`*/2+i.4
29
5)   2+3*4+5
29
6)   ((5+4)*3)+2
29
7)   *`+/2+i.4
46
8)   2*3+4*5
46
9)   ((5*4)+3)*2
46
Gli esempi dovrebbero essere autoesplicativi, una volta ricordato che la composizione n/ interpone l'operatore n (nel nostro caso, + o *) tra gli elementi di una sequenza, e che la valutazione delle espressioni avviene, come già ricordato, DA DESTRA A SINISTRA. Ho aggiunto, per comodità referenziale, dei numeri di riga. In particolare, alla 9) e alla 6) ricostruiamo l'esatta sequenza di valutazione dell'espressione gerundiale espansa, che come vedete chiaramente alterna i due verbi (nel nostro caso, +/ e */ ovvero somma e moltiplicazione multiple) applicandoli opportunamente all'input fornito.

Naturalmente i lettori più smaliziati avranno già capito che questo excursus sul gerundio serve appunto ad introdurre l'operazione di scansione alternata delle antidiagonali, che nella nostra espressione è realizzata appunto tramite un bel gerundio:
codice:
   </. |. i. 3 4
+-------------------------+
¦8¦9 4¦10 5 0¦11 6 1¦7 2¦3¦
+-------------------------+
   <@|.`</. |. i. 3 4
+-------------------------+
¦8¦9 4¦0 5 10¦11 6 1¦2 7¦3¦
+-------------------------+

   <`(<@|.)/. |. i. 3 4
+-------------------------+
¦8¦4 9¦10 5 0¦1 6 11¦7 2¦3¦
+-------------------------+
Ho opportunamente evidenziato tutte le antidiagonali (incluse quelle di lunghezza unitaria, evidentemente invarianti) interessate dalla modifica rispetto alla lettura unidirezionale. Si nota benissimo come, nel secondo caso, l'ordinamento dei valori nei box risulta alternatamente invertito, come desiderato. Il terzo caso, riportato per riferimento, illustra come modificare il medesimo gerundio (massima attenzione alla sintassi!) per invertire la direzione dello zig-zag.

3) Ordinamento dei valori.
Siamo già molto prossimi al risultato desiderato, com'è evidente analizzando l'output dell'esempio precedente.
A questo punto, dobbiamo solo riordinare per righe e colonne gli elementi attualmente raggruppati per antidiagonali.
Il concetto di sorting in J, com'è lecito attendersi, offre qualche sorpresa rispetto ad altri linguaggi.
Come spesso accennato in passato, l'ordinamento di un array può essere validamente rappresentato come una applicazione biettiva che mappa gli indici dell'array di input su nuove posizioni. Ad esempio, dato l'array C Array[] = "ASORTINGEXAMPLE", ordinarlo alfabeticamente in senso ascendente significa, di fatto, effettuare le seguenti assegnazioni:
codice:
ASorted[0]  = Array[0];    /* 'A' */
ASorted[1]  = Array[10];   /* 'A' */
ASorted[2]  = Array[8];    /* 'E' */
ASorted[3]  = Array[14];   /* 'E' */
ASorted[4]  = Array[7];    /* 'G' */
...
In sostanza, per descrivere l'array ordinato è sufficiente fornire la sequenza degli indici che compaiono nelle espressioni a destra, la cui corrispondenza con i primi n naturali è implicita (posizionale).
Tale sequenza, in ultima analisi, è una permutazione degli indici e rappresenta in forma vettoriale (tabulare) l'applicazione che mappa l'array di partenza su un nuovo array, ordinato secondo un criterio specifico (in questo caso, lessicografico ascendente). Spero sia sufficientemente chiaro che la permutazione in oggetto rappresenta, di fatto, il criterio di ordinamento usato: se volessi un ordine antilessicografico, ad esempio, non avrei che da invertire la permutazione.

Il linguaggio J fornisce, con un uso monadico o diadico (ciò che in altri contesti chiamiamo unario e binario: in soldoni, l'arietà o molteplicità degli operandi ai quali si applica un operatore) del medesimo gruppo di operatori, sia il metodo per classificare un input (i.e. generare una permutazione degli indici), sia la funzione di ordinamento vera e propria, che prende in input una lista e un criterio di ordinamento - al limite, la lista di input medesima, come nel nostro esempio: il che produce il criterio di default, in questo caso lessicografico ascendente.
codice:
   A =: 'ASORTINGEXAMPLE'
   /: A
0 10 8 14 7 5 13 11 6 2 12 3 1 4 9
   /:~A
AAEEGILMNOPRSTX
   (/: A){A
AAEEGILMNOPRSTX
Tornando al nostro problema, occorre e basta unire l'azione dell'operatore "grade up" /: con il banale operatore di listing ; sull'output finora prodotto per ottenere il risultato desiderato:
codice:
   <@|.`</.|.i.3 4
+-------------------------+
¦8¦9 4¦0 5 10¦11 6 1¦2 7¦3¦
+-------------------------+
   ; <@|.`</.|.i.3 4
8 9 4 0 5 10 11 6 1 2 7 3
   /:@; <@|.`</.|.i.3 4
3 8 9 11 2 4 7 10 0 1 5 6

   3 4 $ /:@; <@|.`</.|.i.3 4
3 8 9 11
2 4 7 10
0 1 5  6
L'ultimo statement illustra come il nostro lavoro, a questo punto, sia praticamente terminato.

4) Presentazione del risultato.
Giunti a questo punto, è sufficiente ridare alla lista (ottenuta tramite l'operatore ;, a sua volta necessario per elaborare la lista multipla prodotta dall'output precedente) la forma originale di matrice mxn.
Data la peculiarità dell'operatore $ a ciò preposto, usiamo semplicemente le regole di composizione funzionale proprie di J, e l'apposito operatore cap [:.

codice:
   zigzag =: ($ [: /:@; [: <@|.`</. [: |.i.)

   zigzag 3 4
3 8 9 11
2 4 7 10
0 1 5  6

Note conclusive: al momento di andare in macchina, mi accorgo che la discussione originale su questo tema presentata molti anni fa nella mailing list del linguaggio J, che mi ha ispirato l'intero intervento, aveva a mia insaputa gemmato anche una pagina su Rosetta Code, che sostanzialmente non si discosta troppo dalla mia descrizione didattica, pur con vari distinguo.

Nella tardiva consapevolezza che avrei potuto risparmiare lo Sforzo, dedicando spazio e tempo ad altri linguaggi, mi consolo pensando al sorriso beffardo di Albert Einstein, il quale in una occasione del genere non mancherebbe di far notare il risvolto più paradossale e involontario del suo famoso aforisma "L'originalità è l'arte di nascondere le proprie fonti". Come vedi, caro Albert, al tempo di Internet è di gran lunga più facile che accada l'esatto contrario: sottovalutare o ignorare qualche "fonte" a causa della sua bassa qualità media e "nascondere" distrattamente a sé stessi qualche rara perla, per trovarsi così inconsapevolmente a reinventare la ruota.
Valga comunque la citazione del cuoco di Gian Burrasca: "...ormai l'è cotta, e ve la mangiate."

J Software, il sito ufficiale
J ML Archive (nov. 2006): matrici a zig-zag
La matrice a zig-zag su Rosetta Code
Thread "gemello" sui forum di IoProgrammo
• Su questo blog: strjoin=: #@[ }. <@[ ;@,.
• Il sorgente C allegato: zigzag_c.txt

Commenti