Archivio autore: shintakezou

Developer. I do software stuffs using computers. IT consultant. I do also other things.

Un’altra rapida e semplice incursione nel mondo di Maxima

Continuo la panoramica di Maxima, iniziata proprio con Maxima: panoramica iniziale.

Limiti

Naturalmente Maxima può anche calcolare limiti. Per esempio:

lim1

Questo è un limite notevole. In certi casi il limite “venendo da destra” è diverso dal limite “venendo da sinistra”: possiamo aggiungere un altro argomento a limit che specifica come deve essere fatto il limite, se da destra (plus) o da sinistra (minus).

lim2

Quando c’è questo tipo di ambiguità e non specifichiamo come vada fatto il limite, otteniamo und (undefined).

Naturalmente possiamo far tendere x all’infinito, inf, o meno infinito, minf.

lim3

Come risposta potete ottenere anche infinity (infinito complesso) o ind, indefinito ma limitato (come per esempio è il caso del seno e del coseno). Per qualche altra cosetta rimando al manuale.

Serie di Taylor/Laurent

A Maxima possiamo anche chiedere l’espansione (troncata) in serie di Taylor. Potete sperimentare con le espansioni più note, che ovviamente Maxima gestisce, o con altre cosucce come per esempio la seguente:

taylor1

La lettera γ è la costante di Eulero-Mascheroni. Esce fuori perché il fattoriale è stato espresso (diciamo per forza di cose… ma non dettaglio) in termini della funzione Γ, e infatti otteniamo lo stesso risultato se al posto di x! scriviamo gamma(x+1). Se calcoliamo la derivata dobbiamo ottenere, come potete leggere su Wikipedìa, ψ0(x + 1)Γ(x + 1). Se la calcoliamo a x=0, otteniamo -γ; Maxima “sa“ anche tutto questo:

taylor2

(Ho preso l’ultimo risultato tramite % e poi gli ho detto di considerare x=0.) Con ciò abbiamo sfiorato un paio di funzioni speciali, che naturalmente Maxima conosce.

Una volta che abbiamo l’espansione in serie (troncata) in un intorno di un punto, possiamo usarla per calcolare la funzione in quell’intorno; naturalmente otteniamo un’approssimazione. Ne approfittiamo per vedere che Maxima è anche un linguaggio di programmazione e può fare pure grafici (tipicamente è gnuplot in realtà a farli)…

Vogliamo avere un’idea di come migliora l’approssimazione della funzione gamma man mano che tronchiamo la sua espansione in serie di Taylor sempre più tardi (ma mi fermo presto perché già intorno al termine alla 11 comincia a metterci un po’ troppo… non aspettiamoci che Maxima abbia performance stratosferiche.)

Grafici (e Turing…)

Potremmo anche abbandonare l’ambiente interattivo, aprire un editor, e scrivere il codice come siamo abituati; questo magari sarà effettivamente più comodo in qualche puntata successiva (se ci arrivo!:-D). Per ora continuo ad usare wxmaxima.

L’obiettivo che mi sono posto alla fine del paragrafo precedente è in pratica questo: graficare un po’ di espansionsioni in serie (troncate) di Taylor della Γ, e la Γ medesima, per vedere cosa cambia man mano che aggiungiamo termini.

La Γ è definita per valori positivi della variabile; la funzione che stiamo sviluppando è in realtà Γ(x+1) (siamo partiti dal fattoriale), e la stiamo sviluppando intorno a x=0, per cui non ha senso andare più lontano di 1. Insomma il nostro intervallo sarà [0, 1].

Il codicillo che andiamo ad eseguire ha il seguente aspetto:

code0

(Ricorda: se abbiamo pasticciato un po’ e vogliamo pulire un po’ il nostro ambiente, eseguiamo reset()$ e kill(all)$.)

Abbiamo prima inizializzato una lista vuota; poi abbiamo usato un ciclo for per popolarla, tramite append. Il for parte da 2 e non supera 10 a passi di 3, cioè insomma calcoliamo taylor per 2, 5, 8. Alla fine appendiamo anche la gamma(x+1) che è la funzione “giusta e vera” e gli diciamo di fare un grafico 2D usando come intervallo per la variabile x [0, 1]. Dopo un po’ compare il nostro grafico.

Se vogliamo salvarlo invece che vederlo, possiamo scrivere qualcosa come:

plot2d(t, [x, 0, 1], [gnuplot_term, 'png], [gnuplot_out_file,"graph0.png"])$

Controllando un po’ meglio gnuplot è possibile ottenere grafici “migliori”; senza fronzoli il file generato è questo:

graph0

Se rimaniamo nell’intorno (positivo) del punto in cui abbiamo sviluppato la serie riusciamo a ottenere approssimazioni migliori man mano che aumentiamo i termini della serie; allontanandoci notiamo invece che le cose vanno diveramente e capita che il verde (che ha più termini) va persino peggio del blu (n=2)… Se giocate un po’ vi accorgete che lontano dallo zero avvengono oscillazioni piuttosto consistenti man mano che aggiungiamo termini. Del resto nessuno ci dice che abbia senso allontanarsi dallo zero…

Le possibilità grafiche di Maxima non si esauriscono qui, naturalmente, e nemmeno la capacità di esprimere algoritmi.

Vettori e matrici

Potevano mancare? Possiamo inserire matrici e calcolarne il determinante; come al solito possiamo mettere variabili (simboli) invece di numeri:

dett2x2

Se definiamo matrici più grandi possiamo dedurre la regola usata, che è proprio una di quelle che (forse) abbiamo imparato.

dett3x3

Provate da voi invert(m2), detout; per invertire la matrix 3×3. Noterete che al denominatore c’è proprio il determinante (detout serve per metterlo a fattore comune). Non a caso. Provate

invert(m2), a=0, b=0, c=0;

Quelle imposizioni rendono il determinante nullo, per cui Maxima vi risponde con un errore che può essere un po’ criptico (0 to a negative exponent), ma che dovrebbe farvi capire che c’è una divisione per 0 di mezzo o almeno questo: la matrice non è invertibile.

Possiamo calcolare il prodotto tra due matrici, e “scopriamo” che il prodotto matriciale non commuta:

AB-BA

Eccetera: anche qui ciò che possiamo fare è veramente tanto e potete esplorare e sperimentare con il capitolo del manuale Matrices and linear algebra. Magari proverò ad approfondire tramite qualche applicazione concreta (esercizi?)

Alla prossima

Nella prossima parte proverò ad utilizzare Maxima in modo un po’ più creativo (o forse mi ributto su qualche esercizietto, dipende). Nel frattempo spero che già abbiate iniziato a divorare il manuale e fare i vostri esperimenti.

Maxima: panoramica iniziale

(Questo post potrebbe essere il primo di una serie, ispirato da questo commento; ma il futuro è sempre incerto, il tempo scarso e troppe le cose che sarebbe bello fare o sperimentare.)

Esploriamo “brevemente” Maxima, un CAS, cioè Computer Algebra System. Secondo Wikipedía un CAS è

un software che permette il calcolo di espressioni matematiche in un modo simile al calcolo manuale che farebbero matematici e scienziati.

Poniamo il caso che ci venga chiesto di calcolare la frazione risultante dal prodotto di altre frazioni. Per esempio 4/7 × 7/3. Ci hanno insegnato a semplificare per arrivare a 4/3, un bel numero razionale la cui rappresentazione decimale non è finita. Per poter arrivare a scrivere la frazione 4/3 ci basta sapere un paio di regolette ed applicarle: “manipoliamo” simboli e il fatto che quei simboli siano dei numeri è irrilevante, a questo livello. Tanto che saremmo giunti allo stesso risultato anche se ci avessero chiesto di calcolare 4/a × a/3 (specificando che a≠0).

Proviamo a farlo in C:

printf("%lf\n", (4.0/7)*(7.0/3));

Un approccio del tutto diverso: il C non manipola simboli ma calcola numeri, quindi svolge le moltiplicazioni e le divisioni e produce un numero. Il numero restituito è chiaramente un razionale e dunque esprimibile come frazione, che però non è la nostra frazione (4/3), bensì qualcosa di “abbastanza vicino”. Se prendiamo quel risultato e lo moltiplichiamo per 3 (a mano), non otteniamo 4. Dunque il risultato è un’approssimazione, per forza di cose.

La frazione 4/3 può essere scritta come 1.\overline{3}. Sapete dire al volo quanto fa 1.\overline{3} × 1.5? Fa quanto fa 4/3 × 3/2, cioè 2. Questo dà l’idea di almeno un buon motivo per tenersi il 4/3 nella formula del volume di una sfera, per dirne una.

Quindi teniamoci le frazioni, almeno finché non sia necessario produrre un numero “esatto” come 1.33: sappiamo che è solo un’approssimazione del “numero vero”, ma forse per gli usi pratici che abbiamo in mente può andare benissimo e persino 1.33333 potrebbe avere una precisione inutilmente alta per i nostri scopi. Il meglio che possiamo fare è dire che il “numero vero” è compreso tra due numeri esprimibili in modo finito: per esempio il “vero π” è certamente compreso tra 3.140 e 3.142. Queste approssimazioni si ripercuotono su tutti i conti e…

Torniamo ai computer e facciamo degli esperimenti. I pythonisti nei paraggi con il loro REPL sempre pronto possono provare:

pythonscr

Se pensiamo a 1.3333333333333333 come risultato di 4.0/3, ci pare normale e anzi necessario che 1.3333333333333333*3 faccia 4. Tuttavia dovremmo rimanere un po’ perplessi: matematicamente 1.3333333333333333×3 fa 3.9999999999999999 e 3.9999999999999999 è 3.9999999999999999, non 4. Sappiamo che 3.(9) (tre punto nove periodico) è matematicamente uguale a 4, ma quello che abbiano noi è un numero finito di 9… 1.3333333333333333×3 ≠ 4, e sarà sempre così, anche se aggiungessimo tantissimi 3 (ma sempre in numero finito). Possiamo dire che 3.9999999999999999 è sufficientemente vicino a 4 da poterlo sostituire proprio con 4… A titolo esemplificativo ho anche mostrato altri casi borderline.

Ci stiamo solo confrontando con l’IEEE 754 binary64 e i suoi limiti, che a volte è necessario tenere a mente.

Finché si tratta di conti con delle frazioni in cui numeratore e denominatore sono numeri interi, poco male: possiamo risolvere in tutti i linguaggi, scrivendo a mano quanto ci serve o usando una libreria. Per esempio vedi Arithmetic/Rational su RosettaCode. (In alternativa per il C possiamo usare la GNU multiprecision library, in particolare le Rational Number Functions.)

Tutto molto bello ma di qualcosa come 4/a × a/3 (a≠0) non sappiamo che farne. Né Smalltalk, né C++, né Python e loro affini possono fare nulla al cospetto di quella variabile incognita — a meno di non salvarla dal suo stato incognito assegnandole un valore arbitrario (p.es. ponendo a=7…)… in questo caso funzionerebbe, ma ci vuole poco a classificarlo come espediente: b/a × a/3.

Maxima

Era tutto per convincervi della superiorità dell’approccio umano, fondamentalmente simbolico, al calcolo. Stiamo però da tempo provando a far fare alle macchine alcune cose a mo’ d’umano (the human way); con gli scacchi è stato un po’ un fallimento e, affinché la macchina batta l’uomo, sono necessarie forza bruta e grande memoria “infallibile” (ma non sono aggiornatissimo sugli ultimi sviluppi).

Sul versante dei calcoli e della manipolazione simbolica invece andiamo meglio.

A Maxima possiamo dire di calcolare b/a × a/3! Maxima fa quello che fareste voi: non sa cosa siano a e b, però sa la regoletta per semplificare il prodotto di due frazioni. (Da qualche parte qualcuno terrà a mente che a ≠ 0…)

Faccio una panoramica di alcune funzionalità base di Maxima (nella modalità interattiva).

Per questa (ipotetica) serie userò il frontend wxmaxima: maxima ha di base un’interfaccia testuale, però offre la possibilità di “parlare” con un frontend che lo pilota e pensa lui alla visualizzazione. Inoltre è possibile chiedere l’output (La)TeX… Insomma un fronted può mostrare i risultati in modo più accattivante.

Parto dalla mia risposta alla questione dell’arcotangente iperbolica di -2.

maxima1

Abbiamo il numero complesso espresso in forma polare in modo analitico invece che numerico, perché Maxima preferisce tenersi frazioni e simboli invece di dare numeri che, per forza di cose, sono approssimazioni.

Esercizi: derivate, razionalizzazioni e semplificazioni

Online ho trovato questo PDF di esercizi. Facciamo svolgere qualche esercizio a Maxima…

maxex1

Invece di derivative possiamo usare diff. L’esempio mostra come calcolare la derivata prima rispetto ad una variabile. Il ; segnala la fine dell’input. Maxima lo valuta e ci mostra il risultato della valutazione. Naturalmente l’espressione di cui stiamo calcolando la derivata può contenere anche altri parametri/variabili, oltre alla variabile su cui stiamo derivando.

maxex1b

Possiamo far riferimento all’ultimo risultato tramite %, oppure a un risultato specifico scrivendo per esempio %o20. Il % precede anche alcune costanti, come %pi, %e e %i (nell’output con wxmaxima non le vedete, e %pi diventa π).

Tornando al primo esercizio di derivazione, lo ripetiamo e poi chiediamo di applicare la ratsimp, razionalizzazione e semplificazione.

maxex2

Proviamo con l’esercizio 3.

maxex3

Ho usato fullratsimp, che «applies ratsimp followed by non-rational simplification to an expression until no further change occurs». In questo caso non fa molta differenza.

Esercizi: formule/funzioni e integrali

Calcoliamo il volume di una sfera di un certo raggio.

maxex4

Usiamo := per definire una funzione; il $ è come ; ma sopprime l’output: lo usiamo se siamo interessati solo agli effetti della valutazione ma non vogliamo che l’espressione sia visualizzata, oppure se è un risultato intermedio che non ci interessa “vedere”. Con il ; Maxima avrebbe mostrato la funzione:

maxex5

Vediamo se riusciamo a ricavare le formule per l’area di un cerchio e per il volume di una sfera. Partiamo dalla circonferenza, 2πr. Come forse sapete, “basta” integrare 2πr×dr. In Maxima è un attimo:

maxex6

Per il volume possiamo lavorare a fette (dischi)… (I dettagli li trovate altrove, per esempio su Wikipedía.)

maxex8

Nell’esempio vedete pure un’altra cosa: se mettete un ', state dicendo a Maxima di non calcolare l’espressione, ma di tenerla così com’è. In questo modo viene visualizzata l’espressione con l’integrale (però come vedete ha “capito” che il π può stare fuori e l’ha messo fuori). Un altro caso d’uso dell’apostrofo è per definire le equazioni differenziali.

Per arrivare alla formula del volume di una sfera possiamo usare le coordinate sferiche per calcolare un elemento di volume e poi integrare. Vediamo come se la cava Maxima…

maxex7

Esercizi: sistemi di equazioni lineari

Un classico degli esercizi della scuola secondaria sono i sistemi di equazioni. Prendo spunto da questo PDF. Vediamo l’esercizio 6 a pagina 6:

syseq1

Ho “definito” le due equazioni (a e b) per comodità; poi ad algsys (cfr. algsys) ho dato un array delle equazioni e uno delle incognite. I : sono usati per assegnare a un simbolo una certa espressione; p.es. x:5$ assegna a x il numero 5, e a:x=y$ assegna ad a l’equazione x=y. L’= in Maxima ha il significato matematico, per cui x = x + 1 è proprio l’equazione che ci porta a dire che 0 è uguale a 1…

Vediamo che succede con l’esercizio 9 a pagina 7.

syseq2

Il libro dice “indeterminato”, ma Maxima invece ci fornisce un risultato. Che vuol dire? Il sistema è indeterminato nel senso che non possiamo determinare dei valori unici per le incognite. Però le soluzioni esistono. Maxima ci dà le formule (con il parametro %r1) per avere dei valori di x e y che soddisfano le equazioni; al variare di %r1 avremo tutte le coppie (x,y) che soddisfano il sistema.

Vediamo l’esercizio 13, a pagina 7, per il quale non ci sono soluzioni.

syseq3

Maxima ci ritorna una lista vuota, [].

Restano comunque casi che richiedono l’intervento di un po’ più di cervello e conoscenza. Per esempio nell’esercizio 62 a pagina 13, Maxima fornisce la soluzione parametrizzata (con %r…, come prima), ma non ci dà indicazioni sui valori di x da evitare. Si vede ad occhio che -1 e -5 portano ad una divisione per zero. Per quanto riguarda 6x+x²+5, possiamo usare solve.

solve1

In caso di N equazioni in M incognite, basta aggiungere elementi alle rispettive liste passate a algsys. Inoltre, come dovrebbe essere ormai chiaro, non è affatto necessario che nelle equazioni ci siano solo le incognite e dei numeri: possiamo metterci dei parametri.

L’algsys «solves the simultaneous polynomials […] or polynomial equations […]». La “funzione” solve, quando chiamata con delle liste come argomento, a sua volta usa algsys oppure linsolve, che «solves the list of simultaneous linear equations for the list of variables».

Morale: algsys può risolvere anche sistemi di grado superiore al primo e quando abbiamo il dubbio se usare linsolve o algsys, usiamo solve e dovrebbe andare “sempre” bene. Proviamo con il sistema proposto qui

eq2g

(Avevo già inserito le due equazioni in un ordine non adatto per fare lo screenshot, sicché ho digitato a; e b; solo per rivisualizzarle prima di invocare solve.)

Esercizi: sistemi di disequazioni lineari

Un po’ diverse e un po’ più complicate le cose con le disequazioni. Proviamo, a scopo illustrativo, fourier_elim, che non è precaricato, per cui lo carichiamo; dopodiché procediamo. Prendo gli esempi da questo PDF.

ineq1

Ok. Ora vediamo l’esercizio 19:

ineq2

Il risultato non è proprio quello dato nel PDF: occurerà approfondire…

Voglio il numero!

L’output di Maxima, come abbiamo visto, preferisce i numeri razionali (rappresentati tramite frazioni); inoltre, se ci sono irrazionali di mezzo, mantiene la forma simbolica. Se ci serve il numero, anche se approssimato, della radice quadrata di 2, possiamo dirgli di fornircelo.

sqrt2

Possiamo tenere l’impostazione fissa scrivendo numer:true$; da questo momento calcoli come sqrt(2) o anche il nostro 4/3 daranno lo stesso risultato che darebbe per esempio il Python.

numer

Ma Maxima può fare calcoli a precisione arbitraria. Impostiamo fpprec a quanto vogliamo, per esempio fpprec:30$, e usiamo bfloat(espressione) per avere il numerello.

prec30

Equazioni differenziali

Come ultimo esempio prendiamo la classica equazione differenziale del moto armonico. Maxima ci chiede se il coefficiente omega è diverso da zero. Dopodiché, ci dà il risultato atteso.

ode2

Possiamo risparmiarci la domanda dando un’informazione in più: assume(omega>0)$. Un’ultima cosa: usiamo bc2 per avere il risultato una volta fissate le condizioni al contorno.

ode2p1

Alla prossima

Come primissima panoramica penso che possa bastare. Preciso che il mio uso di Maxima è sempre stato molto pragmatico e limitato (per cose un pochetto più complicate degli esempi fatti, ma nemmeno poi troppo).

Una riga sola (ma a volte un po’ lunga)

mineentrance_sepia_

A volte sono un collezionista di dati e scavo scavo e scarico scarico e leggo o analizzo o studio sì e no l’1% di quel che scarico, sicché a volte la notte mi prende l’ansia, non essendo immortale, di non riuscire ad assorbire tutto ciò che ho accumulato. Una certezza, visto che il tasso di consumo è decisamente inferiore al tasso di produzione.

Mi avvalgo dei soliti strumenti che non dovrebbero mai mancare nella scatola degli attrezzi dello scavista e del collezionatore (oltre ad una shell come bash e a un browser): wget, curl, awk, perl, lynx… Quali usare dipende dalla difficoltà dell’obiettivo e anche dalla fantasia del momento; ma spesso mi bastano lynx, awk e wget.

Visto che su questo blog la parola one-liner già compare (per esempio qui, ma anche altrove), la userò: si tratta di fare semplici one-liner.

Tanto per battere un colpo e per fare degli esempi, gli ultimi one-liner fatti oggi.

Prima il più “complicato”. Le directory e i file sono visibili grazie al fatto che non è proibito il directory listing. Però chi ha organizzato il materiale ha creato una cartella per ogni lezione, e in ciascuna cartella troviamo due PDF, SlidesNN.pdf e SmallNN.pdf, dove NN corrisponde al nome della cartella che a sua volta corrisponde al numero della lezione (suppongo) scritto sempre con due cifre. È bastata una sbirciatina a due cartelle diverse per stabilire questo schema; naturalmente ciò non garantisce che sia valido per tutte… ma per induzione diciamo che sia così. (Alla fine si scopre che la 29 fa eccezione: poco male, si fa una wget mirata e buona notte.)

for i in `seq 0 1 29`; do k=$(printf "%02d" $i); \
  wget http://BASE/$k/Small$k.pdf ; \
done

(Oppure si può scrivere for((i=0; i < 30; i++)). Ho scritto BASE e sono andato accapo per non far venire la riga troppo lunga… ma comunque resta un one-liner :-D)

Non ho potuto usare curl perché http://.../[00-29]/Small[00-29].pdf avrebbe generato molte richieste GET che sarebbero state un buco nell’acqua. Di solito è cosa buona e giusta mettere delle pause (sleep); alle volte è anche necessario aggiungere header HTTP vari per fare in modo che wget non sia bloccato… Non è fair play e dicono che bisogna rispettare il robots.txt, quindi lo dico pure io.

Però certe volte un po’ di user agent spoofing è irrinunciabile per poter accedere a certe risorse, cioè per evitare l’user agent sniffing: per esempio in alcuni casi se vi fingete un crawler di Google potete accedere a più cose, perché il vostro compito è di indicizzarle in modo che gli utenti le trovino, clicchino e generino un po’ di traffico — per scoprire che per accedere alla risorsa completa dovete iscrivervi…

Un altro approccio poteva essere l’uso di wget con la sua funzionalità di mirror; dopo aver scaricato tutto avrei dovuto spostare i vari PDF per metterli in una sola cartella — così volevo — e cancellare tutto il resto.

L’altro esempio sfrutta un trucchetto preso direttamente da un classico (penso che si possa definire tale); finisce tutto così:

lynx -dump BASE | \
awk '/.pdf$/ && !/Lexical/ {print $2}' | \
xargs -n1 wget

(Come prima, ho scritto BASE e sono andato accapo per non sformattare il blog…)

Perché !/Lexical/? Solo perché alcune slide già le avevo scaricate — avrei potuto togliere l’esclusione ma l’ho voluta tenere come esempio di filtro leggermente più elaborato della sola regexp /.pdf$/.

Naturalmente i dettagli vanno di volta in volta adattati al caso specifico, che deve essere studiato… Non si fa prima a scaricare i file dal browser? No. Non si fa prima a scaricare i file dal browser usando un download manager, un’estensione, un plug-in o qualcosa del genere? Quando ciò è effettivamente possibile, forse sì… ma è anche meno divertente.

L’approccio via script (one-liner o che) permette di automatizzare il download di risorse da pagine il cui contenuto viene aggiornato (mantenendo lo “schema” invariato).

Per esempio il giornale Metro permette di scaricare i PDF; si potrebbe fare uno script che parte ad un orario stabilito e controlla se il PDF del giorno corrente è scaricabile; se sì lo scarica…

Sul Java che batteva il C (compiler strikes back again)

coffee-309981_640

Il caso trattato nell’articolo Compilati VS interpretati passo 2 (The compiler strikes back) è intrigante: siamo davvero di fronte a uno di quei pochi casi in cui un linguaggio che non viene compilato riesce a battere uno compilato?

Sembrerebbe proprio di sì.

Però ricordiamoci che non è che la JVM realmente interpreta i bytecode in modo “stupido”: c’è la compilazione Just In Time (JIT) e la JVM è tanto ben fatta da poter profilare il codice a runtime per poter migliorare le ottimizzazioni in fase di compilazione JIT…

Questo potrebbe spiegare perché Java sembra battere il C. (Non prendo in considerazione il Python, e nemmeno l’Objective-C per il quale, comunque, si può fare un discorso simile a quello del C).

Passo passo, sperimentando e provando, andiamo a scoprire come stanno le cose…

Elucubrazioni e ipotesi

Intanto nel codice C ho cambiato long double in double: il double in Java è un “64-bit IEEE 754 floating point”, come il double del C. Invece il long double può essere di più. Comunque non cambia praticamente nulla: le performance continuano ad essere inferiori a quelle del Java.

Quello che ho pensato è questo: in Java l’ottimizzatore in qualche modo si accorge che tutti i calcoli da un certo punto in poi non possono che dare infinito (si va oltre le possibilità del double), per cui il ciclo più interno può essere prematuramente interrotto. Oppure: è inutile eseguire la moltiplicazione se f è già diventanto “infinito”.

Se aggiungiamo a mano questa ottimizzazione, il C torna a brillare (dovete includere math.h):

        for(a = 1; a <= i; a++)
        {
            f *= a;
            if (isinf(f)) break;
        }

sh01

Si comincia a ragionare…

Oppure

        for(a = 1; a <= i; a++)
        {
            if (!isinf(f)) {
                f *= a;
            }
        }

Non l’ho provata ma possiamo dire che molto probabilmente sarà più lenta della versione con il break. Il vantaggio di questa versione è che permette l’esecuzione di altro codice nel caso in cui il corpo del ciclo non fosse costituito solo da f *= a.

(Ho fatto anche un’altra modifica: ho usato difftime per avere il numero di secondi… però non serve a molto quando il tutto dura meno di un secondo, e perciò ho messo time sulla linea di comando)

Si può fare di meglio: interrompere il ciclo esterno. Infatti, raggiunto un certo valore di i (chiamiamolo iMax), tutti quelli maggiori faranno in modo che il ciclo interno porti f a “inf”. Un essere umano ci arriva facilmente; ci può arrivare anche un ottimizzatore? Il codice ottimizzato avrebbe, come equivalente di alto livello C, l’aspetto seguente:

    for (i = 0; i <= iMax; i++) {
        double f = 1;
        int a;
 
        for(a = 1; a <= i; a++)
        {
            f *= a;
        }

        nArray[i] = i * f;
    }
    for (i = iMax + 1; i < MAXLOOP; i++) {
        nArray[i] = INFINITY;
    }

Intermezzo: un’idea sciocca

La JVM è stack based. Può essere che un modello simile in certe circostanze risulti più efficiente di uno register based? L’idea è sciocca perché non c’è modo che del codice ben ottimizzato eseguito da un hardware possa essere battuto da un interprete software (che gira sullo stesso hardware).

Ma non è proprio il caso che stiamo analizzando? No. Infatti stiamo cercando il trucco perché la tesi è che ci sia; poiché non lo vediamo, ci sembra che Java vada meglio… Ma in realtà è come se stessimo paragonando le performance del bubble sort scritto in C e Java, senza sapere che Java dietro le quinte lo sostituisce con un quick sort… (Il C non farebbe mai di questi scherzi:-D)

È possibile che le CPU stack based permettano ottimizzazioni migliori di quelle register based? Secondo questo post no:

Another advantage of the register based model is that it allows for some optimizations that cannot be done in the stack based approach. One such instance is when there are common sub expressions in the code, the register model can calculate it once and store the result in a register for future use when the sub expression comes up again, which reduces the cost of recalculating the expression.

Quindi non è che partendo dai bytecode Java si possa generare codice migliore… altrimenti i compilatori userebbero una rappresentazione intermedia stack based nella fase di ottimizzazione.

Comunque, prima di arrivare a realizzare quanto l’idea fosse sciocca, mi sono cimentato nel gioco che vedete nell’immagine.

sh02

Il disassemblato della classe (a destra nell’immagine) si ottiene con javap -c. Tutte le funzioni che vedete a sinistra hanno inline e lavorano su uno “stack” (un array) di strutture contenenti un enum che specifica il tipo (intero, double, array…) e una union.

Inutile dire che i tempi peggiorano…

real        0m6.052s
user        0m6.028s

Il codice lo potete trovare sul mio repository. (Prima o poi cambierà un po’: devo aggiungere un riferimento al post, riordinare e ripulire e commentare ecc.)

gcj

Proviamo ad usare gcj per generare un vero e proprio eseguibile da sol01.java1.

gcj -O3 --main=sol01 sol01.java

sh03

I tempi sono più o meno quelli del C. A questo punto togliamo --main e mettiamo -S per vedere il codice generato. Nessuna sorpresa: a meno di un controllo sull’indice dell’array (per poter throware BadArrayIndex) e qualche altro dettaglio, assomiglia tremendamente a quello generato dalla versione C… del resto il compilatore sotto il cofano è lo stesso.

Dubbio: possibile che il gcc non implementi delle ottimizzazione che invece una VM è in grado di fare a runtime al momento della compilazione JIT?

(Per cercare di essere breve non lo metto :-D, ma ho fatto pure la prova con --profile-generate / esecuzione / --profile-use, giro di giostra che dovrebbe permettere al gcc di fare alcune ottimizzazione eventuali in più… Se non ho sbagliato qualcosa… Niente da fare…)

Sembra quasi che altri marchingegni che compilano Just In Time riescano a capire qualcosa che il gcc non capisce.

Tuttavia, non abbiamo finito di esplorare le possibilità…

clang!

Non ci stiamo dimenticando di qualcosa? gcc è un ottimo compilatore, ma non è l’unico. Proviamo con clang.

sh04

Sorpresa!

E uno sguardo al codice assembly generato rivela qual è il trucco della JVM (e di clang e di pypy e di…): sfruttare meglio le possibilità del processore della macchina che eseguirà materialmente il codice compilato JIT!

Sembra che il gcc di default preferisca generare codice “generico”.

Torniamo a gcc, ma questa volta aggiungiamo qualche opzione di compilazione e riproviamo:

sh05

Bingo.


  1. Per non so quale motivo avevo salvato il file come sol01.java; poi, invece di rinominarlo in base al nome della classe, ho rinominato la classe… Quando si fanno le cose con criterio…

C++, Objective-C, Smalltalk: “estendere” una classe

byte_1981_08

Qualche anno fa (sicuramente meno di 10) scoprii l’Objective-C e mi piacque molto. Ci sono almeno due cose da considerare: ① non sono mai stato un amante del C++ (potendo ho sempre provato ad evitarlo; ho iniziato ad usarlo per me stesso giusto con il C++11); ② per non ricordo quale motivo mi ero imbattuto già nello Smalltalk.

Continua a leggere

Template specializzati

Queen_Street_Mill_Warping_5369

In un commento al post Breve paragone tra l’“overloading” in C++, C(11) e Fortran(90) Orlando chiedeva:

cosa cambia con i template?

La risposta in due commenti (1 e 2)

Con i template il C++ “capisce” quali funzioni servono, in base all’uso, e “genera” le funzioni apposite; nello specifico double+double, int+int, double,int. (che queste siano le “deduzioni” del C++ lo puoi vedere usando l’opzione -fdump-rtl-all del gcc e guardando il file .final generato)

p.s. tutto il resto, per lo scopo dell’articolo, è invariato: la differenza è che non siamo stati noi a scrivere esplicitamente le funzioni. Del resto se non vogliamo creare stranezze come quelle della mia miafunz (che calcola di fatto cose diverse) o se abbiamo “solo” l’esigenza della “genericità”, i template tornano utili e ci evitano copia-incolla e copertura di tutti i possibili casi (che siano effettivamente usati o no…)

Nel codice d’esempio avevo esplicitamente definito due funzioni diverse, non tanto nella signature, quanto nella loro funzionalità. Questo escludeva l’uso dei template… In realtà, non proprio… Ed è quello che volevo mostrare in questo post.

Ma prima, qualche ulteriore osservazione.

Quando la miafunz viene chiamata con argomenti il cui tipo non corrisponde a nessuno dei due casi gestiti esplicitamente, il compilatore può applicare le regole di conversione implicita e vedere se riesce a trovare qualcosa di accettabile.

Quando fate di questi esperimenti attivate un po’ di warning accessori. Compilate con

g++ -Wall -Wextra -Wconversion file.cpp -o file

oppure, per gli esempi che usano feature del C++11, con

g++ -std=c++11 -Wall -Wextra -Wconversion file.cpp -o file

Tutte le conversioni che possono potenzialmente dare problemi vengono annunciate con un bel warning. Il codice dell’articolo già citato vi darà un warning su

    return 2.0*a + 2.5*b;

Precisamente:

warning: conversion to ‘int’ from ‘double’ may alter its value [-Wfloat-conversion]

Come ovvio: il conticino lo facciamo con double (2.5*b fa sì che b sia promosso a double) ma poi restituiamo un int. Per far sapere al compilatore che sappiamo cosa accade, possiamo mettere un cast esplicito e così salutiamo il warning.

Potete provare un’altra cosa: rendete d0 un float, invece di un double. Vi accorgerete che il compilatore è perfettamente contento: il float può essere promosso a double senza problemi, e abbiamo una versione di miafunz che accetta un double e un int come argomenti.

Provate il contrario, cioè lasciate che d0 sia double e cambiate miafunz(double,int) così:

int miafunz(float a, int b)
{
    std::cerr << "double, int\n";
    return static_cast<int>(2.0*a + 2.5*b);
}

(Il cast è stato aggiunto per non avere il warning cui accennavo sopra).

Succede una cosa strana: il compilatore ci dice che la chiamata a miafunz(double,int) è ambigua. In pratica sembra che non sappia decidersi se usare miafunz(float,int) o miafunz(int,int). Voi potreste pensare che la scelta sia ovvia (float), ma in realtà in tutte e due i casi la conversione può perdere qualcosa: come può il compilatore decidere? In un certo senso le intenzioni del programmatore non sono chiare: vorrebbe che fosse chiamato miafunz(float,int) perché sa che il d0 contiene un valore tranquillo per un float? O voleva troncare il numero e chiamare miafunz(int,int)?

Anche qui possiamo risolvere l’ambiguità con un cast, se siamo sicuri che non succedano cose brutte con i valori d’ingresso usati…

Template e specializzazioni

Il codice di Orlando di fatto calcola sempre a+b sugli argomenti, mentre con l’overloading esplicito dell’esempio, nel caso di int miafunz(double,int) facciamo proprio un calcolo diverso.

Ora supponiamo che ci vada bene che miafunz possa essere chiamata con tanti tipi diversi, però vogliamo che non sia a+b se viene chiamata con double e int.

Cioè vogliamo un template generico, ma con una specializzazione.

Il C++ ci permette di fornire delle specializzazioni:

#include <iostream>

template<typename T1, typename T2>
int miafunz(T1 a, T2 b)
{
    return a + b;
}

template<>
int miafunz(double a, int b)
{
    std::cerr << "double, int\n";
    return static_cast<int>(2.0*a + 2.5*b);
}

int main()
{
    double d0 = 1.0;
    int di = 2;
    std::cout << miafunz(d0, di) << "\n";
    std::cout << miafunz(5, di) << "\n";
}

Se compilate ed eseguite, l’output sarà

double, int
7
7

Cioè miafunz(d0, di) chiama la versione specializzata per double e int, l’altra chiama uno dei template generati dal compilatore.

Un po’ di introspezione

Con il C++11 abbiamo accesso ad alcune informazione sui tipi dei template. In pratica i template sono diventati ancora più potenti e il programmatore ha ora nuove possibilità all’atto della compilazione.

Come esempio vediamo che è possibile controllare il tipo degli argomenti, sempre a compile time, e decidere di fare cose diverse… senza specializzare il template. (Nel caso dell’esempio direi che è un no-no-no: meglio usare la specializzazione!)

Nell’esempio che segue ho anche usato typeinfo (ok anche pre-C++11), che invece usa informazioni a runtime (cfr. p.es. su Wikipedia, RTTI), che di solito servono per il dynamic_cast.

#include <iostream>
#include <type_traits>
#include <typeinfo>

template<typename T1, typename T2>
int miafunz(T1 a, T2 b)
{
    std::cout <<
        typeid(T1).name() << ", " <<
        typeid(T2).name() << "\n";
    
    if (std::is_same<T1,double>::value &&
        std::is_same<T2,int>::value) {
        std::cout << "cosa?\n";
        return static_cast<int>(2.0*a + 2.5*b);
    }
    
    return static_cast<int>(a + b);
}


int main()
{
    double d0 = 1.0;
    int di = 2;
    std::cout << miafunz(d0, di) << "\n";
    std::cout << miafunz(5, di) << "\n";
}

L’output dell’esecuzione è:

d, i
cosa?
7
i, i
7

Come si può intuire, d sta per double, i per int. Ma i nomi restituiti da typeid(…).name() sono specifici dell’implementazione, cioè del compilatore usato, quindi non vi ci affezionate.

Invece std::is_same è nello standard C++11 e permette di sapere se il tipo T1 è lo stesso di double (nell’esempio specifico), o qualunque altra cosa. Da type_traits abbiamo altre cosucce utili per sapere se il tipo del template ha alcune caratteristiche (provate a dare un’occhiata qui).

Nel nostro caso potremmo volere che T1 e T2 siano tipi aritmetici, perché restituiamo un int e vogliamo che + e * sia interpretabili proprio come ci aspettiamo che lo siano quando di mezzo ci sono solo numeri. In questo caso usiamo std::is_arithmetic<T>::value e nel caso la condizione non sia soddisfatta la compilazione verrebbe bloccata.

A questo scopo possiamo usare static_assert, che mettiamo come primo statement nella funzione:

    static_assert(std::is_arithmetic<T1>::value &&
                  std::is_arithmetic<T2>::value, "non aritmetici");

Se in fase di compilazione l’assertion è falsa, il compilatore dà errore:

error: static assertion failed: non aritmetici

Fibonacci con i template

I template comportano la generazione di codice nel momento della compilazione. In un certo senso sono come le macro, solo che queste non hanno vincoli sintattici (rispetto alla sintassi del C/C++) e sono type-agnostic… anche se si possono usare dei trucchi con typeof — che gcc supporta — e poi abbiamo visto _Generic, che rende una macro non più tanto type-agnostic.

Ma niente di tutto ciò è integrato per bene con le fasi in cui il compilatore conosce il tipo di ogni “oggetto” (che è ciò che ci permette di usare auto, decltype, sizeofstd::is_arithmetic, std::is_same…) Dunque i template sono più intimamente connessi con il compilatore.

Poiché il codice dei template è generato al momento della compilazione, possiamo sfruttarlo per fare un po’ di calcoli che è inutile fare a run-time? La risposta è sì e uno degli esempi classici e tipici può essere quello della successione di Fibonacci. Esiste una definizione ricorsiva molto semplice (quella che vedete su Wikipedia).

Scrivere una funzione che calcoli l’ennesimo termine della successione è qualcosa che dovrebbe risultare semplice. Precisiamo che la ricorsione, in linguaggi che usano lo stack ad ogni chiamata di funzione e non ottimizzano il caso della tail recursion, impone dei limiti (quanto “profonda” può essere la ricorsione prima che lo stack si esaurisca?) e perciò in linguaggi come C/C++ e altri un’implementazione decente della funzione per l’ennesimo termine della successione di Fibonacci cercherà evitare la ricorsione.

Comunque. Vediamo come calcolare un numero della successione al momento della compilazione, usando i template.

#include <iostream>

template<unsigned long long N>
unsigned long long fibo()
{
    static_assert(N > 1, "ops");
    return fibo<N-1>() + fibo<N-2>();
}

template<>
unsigned long long fibo<0>()
{
    return 0;
}

template<>
unsigned long long fibo<1>()
{
    return 1;
}

int main()
{
    std::cout << fibo<89>() << "\n";
}

Lo potete compilare in modo normale, ma in questo caso incappiamo nella stessa trappola della ricorsione. Però è facile, per l’ottimizzatore, “capire” come andrà finire: tutto è già lì, non c’è nessuna informazione che sia presente solo a runtime. Se aggiungete l’opzione -O2 non c’è alcuna chiamata da fare a runtime: il calcolo del numero l’ha fatto in realtà il compilatore! In pratica il codice generato si riduce a qualcosa come:

std::cout << 1779979416004714189ULL << "\n";

Infatti con l’opzione -S potete sbirciare il codice assembly generato:

    subl    $8, %esp
    pushl   $414433753
    pushl   $511172301

Ora lo stack (esp) punta a due parole lunghe (long word; la l della push sta per long), ovvero una quadword (robo a 64bit). L’intel x86 è un processore little endian e questo significa che “scorrendo” la memoria dagli indirizzi più piccoli a quelli più grandi, incontriamo per primi i byte, le word o le long word meno significative.

Dunque il numero a 64 bit a cui ora punta esp (lo stack) è:

414433753 ⋅ 232 + 511172301

Il numero di Fibonacci alla posizione 89 è vicino al limite per un unsigned long long. Se provate ad aumentarlo, vedrete che inizierete a non avere risultati attendibili.

Penso di dovermi fermare qui: ho fatto un post forse un po’ troppo denso.

Post scriptum

Sono uno di quegli sfigati che di default preferisce i 32bit… Compilando l’esempio con -m64 potete vedere che il codice assembly generato è un po’ più chiaro:

    movabsq $1779979416004714189, %rsi

In questo modo è ancora più palese che tutti i conti sono stati fatti veramente a compile time

Programmazione (pro)logica

3675792814_b629626a57

Tra i commenti al post Liste infinite1 leggo un commento di zar che chiede:

E di prolog non ne parla più nessuno? Esiste ancora qualcuno che lo usa?

Segue la risposta di glipari.

Di sicuro il Prolog non è uno di quei linguaggi popolari di cui c’è grande richiesta e che fanno trovare lavoro appena usciti dall’università. Non è il Java, con tutto il suo fantastico ecosistema di framework, application server, rule engine

A proposito di rule engine: il Prolog integrato con il C sarebbe perfetto… ma non è roba trendy, non piace, è troppo esotica (ieri si faceva così, continuiamo a fare così), non è roba che dà sicurezza e certezze ai project manager (o chi deve scegliere di adottare una soluzione tecnologica al posto di un’altra), non ci sono colossi che spingono soluzioni del genere, non c’è un know-how diffuso, capillare o centralizzato, non c’è forza lavoro (mentale) a buon mercato…

Una scelta fuori dal coro potrebbe essere la marcia in più per una start-up, ma potrebbe anche segnarne il fallimento… se ciò è ancora accettabile per una start-up, non lo è per chi ha un business in qualche modo già consolidato: questi non vogliono sorprese, ma hanno solo bisogno di “tranquillità”.

Il discorso non vale sempre e ovunque: ogni realtà ha le sue peculiarità. Se il core business di un’azienda non dipende criticamente (almeno secondo quelli che stanno in alto…) dalla tecnologia scelta, stare sullo “spigolo” tecnologico per fare il salto più lungo delle concorrenti non ha senso, perché il terreno di gioco è affatto diverso. Perciò vai di Java e tutto il mondo che ci ruota intorno, così si trovano facilmente competenze per tutte le tasche (e livelli) e supporto eccellente dei prodotti che contano e servono.

Un po’ di tempo fa (tre anni fa) mi ero divertito ad usare il (GNU) Prolog per modellare delle relazioni sociali. Da qui nacque l’idea di un progetto più ampio, un servizio di partner matching (sì, partner matching e non pattern matching) che naturalmente è rimasto su carta, abbozzato in una scarna paginetta A4 (che nemmeno più so che fine abbia fatto). L’engine (brr) che avrebbe eseguito gli algoritmi di ricerca delle corrispondenze ottimali sarebbe stato scritto proprio in un misto di C e Prolog.

Il Prolog è anche ottimo per risolvere alcuni tipi di problemi, perché permette di impostarli con facilità e al resto pensa lui. Per esempio l’ho usato per risolvere un Quesito con la Susi — perdonate l’ennesimo link ad uno dei miei blog…

% gprolog: nth
% swi prolog: nth0
vicino(List, A, B) :-
    nth(IndexA, List, A),
    nth(IndexB, List, B),
    abs(IndexA - IndexB) =:= 1.
 
chi(Luca, Aldo, Berto) :-
    vicino([4, 0, 2, 1, 3], Luca, Aldo),
    vicino([1, 2, 3, 0, 4], Berto, Aldo),
    \+ vicino([4, 0, 2, 1, 3], Luca, Berto), 
    Luca =\= 0,
    Aldo =\= 0,
    Berto =\= 0,
    Luca =\= Aldo,
    Luca =\= Berto,
    Aldo =\= Berto.

Come vedete si legge con facilità (credo): la procedura vicino/3 ci dice se A e B della lista List sono vicini: lo sono se la differenza tra gli indici della loro posizione nella lista è pari ad 1. nth/3 assegna a IndexA (IndexB) la posizione di A (B) nella lista List. Viene calcolata la differenza (assoluta) tra i due indici e si “dichiara” che debba essere pari a 1. La vicino/3 è vera se sono soddisfatte le tre “dichiarazioni” (la virgola è un and logico). Poiché IndexA in nth(IndexA, List, A) è “libera”, il Prolog le assegna il valore necessario per soddisfare la dichiarazione. Quindi le prime due righe di vicino sono vere, posto che gli elementi si trovino nella lista.

La procedura chi/3 “modella” il problema. Diverse “dichiarazioni” vengono messe in “and”. Il Prolog cerca di assegnare i valori in modo che siano tutte soddisfatte. Quindi, per dire, assegnerà a Luca e Aldo i numeri tali che

vicino([4, 0, 2, 1, 3], Luca, Aldo),

sia vero. Se considerate solo questa riga da sola, i possibili valori di Luca e Aldo che la soddisfano sono svariati: 4 e 0, 0 e 2, 2 e 1, 1 e 3 (e le stesse coppie con valori scambiati); però ci sono tre righe che dicono che Luca, Aldo e Berto non possono avere valore 0; quindi ci restano solo 2 e 1, 1 e 3 (1 e 2, 3 e 1). E così via. Attraverso algoritmi come il backtracking, è possibile trovare la soluzione che soddisfa tutti i diversi vincoli (le “dichiarazioni”): questi vincoli restringono lo spazio dei valori delle “variabili libere” che li soddisfano… Se i vincoli non sono sufficienti a determinare una soluzione unica (cioè ogni “variabile” può avere un solo valore possibile per soddisfare i vincoli), il Prolog non si scompone e ci propone le varie soluzioni.

gprologrun

Una volta “consultato” il file (che ho chiamato susi0.prolog), possiamo “interrogarlo”. In un certo senso quel file rappresenta la conoscenza che ha il sistema. Un file di conoscenza Prolog è una collezione di fatti e regole. Nel nostro caso abbiamo due regole, una che stabilisce il criterio secondo il quale diciamo che due “cosi” sono vicini, e l’altra che risolve il problema (la lettura del quesito può aiutare la comprensione generale).

In questo esempio abbiamo solo delle regole che stabiliscono delle “relazioni”.

Tanto per mostrare che non c’è legame tra i nomi usati nelle regole e quelli passati quando “chiamiamo” la regola, ho rieseguito il goal usando Mario, Unno e Alice. Notare che il goal è un fatto: sto dicendo che tra Mario, Unno e Alice (o Luca, Aldo e Berto) deve valere la relazione chi/3. Questo è l’obiettivo e il Prolog lavora per trovare i valori che rendono vero il “fatto”.

Vediamo qualche altra cosa che possiamo scrivere:

| ?- chi(1, 0, 3).

no

Qui facciamo una precisa affermazione, con numeri che assegniamo noi. In realtà va letta più come un’ipotesi. E il Prolog ci dice no: quei numeri non soddisfano la regola né corrisponde a un fatto noto (stiamo asserendo qualcosa di falso, cioè la nostra ipotesi, stando ai fatti e alle regole note, non può essere vera).

| ?- chi(3, 1, 2).

true ? 

yes

Qui ho messo i valori giusti e il Prolog dice “vero”. Quando scrive ? il Prolog è fermo in attesa di input, utile nel caso ci fossero soluzioni multiple (non è questo il caso). Digitando ? ottengo un aiuto:

true ? ?
Action (; for next solution, a for all solutions, RET to stop) ? 

Quindi se voglio vedere la soluzione successiva devo premere ;, se voglio che me le scodelli tutte devo premere a; se voglio che si fermi, premo return. In questo caso è un po’ come se dicessi che la soluzione data mi sta bene. Visto che la soluzione è una, se premo qualcosa di diverso da return in questo caso non mi viene presentata nessun’altra soluzione (ovviamente) e scrive no, e con ciò intende semplicemente che non ci sono altre soluzioni.

| ?- chi(p, a, s).

no

In quest’ultimo esempio ho usato gli atomi p, a, s (cfr. Prolog syntax and semantics). Di questi atomi il sistema non sa nulla: nel knowledge (data) base non c’è nessun fatto che li riguardi. Perciò non potrà mai dirci che quel goal è compatibile con i fatti noti.

Per ora è tutto.


  1. Post del 2011… dovreste aver capito che sto scavando un po’ in questo blog agganciandomi a discorsi fatti o accennati e che per un motivo o per l’altro stimolano i miei interessi.

Sulla steganografia

Immagino che siate in trepidante attesa del seguito di Macchine a stati finiti e pattern matching, o dovete ancora digerire quel malloppo… tranquilli, perché devo trovare il tempo di impegnarmi a scriverlo (suspense…) e su due piedi non mi viene.

Quindi, nel frattempo…

flowersex

Scavo un po’ questo blog e trovo Due immagini identiche non proprio uguali…. A me la steganografia è sempre piaciuta un sacco; purtroppo quando se ne parla popolarmente spesso e volentieri si fa confusione e si dicono sciocchezze. E poi si fa sempre e solo il classico esempio di “qualcosa” nascosto dentro un’immagine.

Ma perché un’immagine? Forse perché è qualcosa di più “spendibile” in un film o in un racconto? Fa più scena, insomma. Come Nella morsa del ragno.

In quel mio articolo racconto la storiella del «greco [che] scrisse un messaggio sulla testa rasata di un suo schiavo, aspettò che gli crescessero i capelli e gli ordino di recarsi nella città del suo amico destinatario», solo che la ricordavo diversa. Ma il succo è lo stesso ed è ciò che conta.

Qualche giochetto steganografico e molte altre cose si possono apprendere anche da qui. È un gioco e se vi va di giocare non ve ne pentirete. Tanto per capirci (forse), dietro c’è Davide Eynard; parliamo di pezzettini di certa storia. E a proposito, Lore updated 6 years, 5 months and 6 days ago, dice… questo mi mette un po’ di nostalgia (perché 8 anni fa ero più giovane e pensavo che quel sito mi avrebbe fornito materiale nuovo fino all’eternità).

Torniamo in tema: sempre se la memoria non mi tradisce, è lì (giocando su 3564020356) che appresi e la storiella e del libro di Trithemius sulla steganografia… È anche su archive.org. Dovete ripassare un po’ di latino (ma non è il latino di Cicerone, si legge un po’ più facilmente… ehm). Trovate anche cose come Solved: The Ciphers in Book iii of Trithemius’s Steganographia. Sempre per capirci, Trithemius è l’autore di Polygraphia, «the first printed book on cryptography» (lo trovate scansionato su Books Google, se vi interessa).

polytrit

Naturalmente non poteva non parlarne pure l’NSA, che ci dà anche altri titoli che val la pena leggere nelle fredde serate infernali.

Steganografare

Dicevamo appunto che la steganografia non deve per forza nascondere “qualcosa” in un’immagine, come dimostra la storia del greco.

Oh,     tremenda    tormenta     /
che  mi   bloccò sul     monte!    /
Così  forte    il  vento che    pure /
Harry   Potter, con      gli incantesimi     /
e   le     pozioni  e    /
i   suoi amici   e   la   sua     fortuna,   /
poteva rimanerci secco!    /
Ancora  non capisco    come   riuscii    a   resistere, /
né      donde  venissero  /
i soccorsi     tanto   sperati,      /
che   mi   presero per     i    capelli!  /
Ora    posso      dire d'esser     vivo!   /

Banale ma rende l’idea (o no?). Il seguente programmino può codificare un testo in un testo usando gli spazi. Scusate se ho usato il Perl ma, nonostante sia arrugginito, lo trovo sempre più pratico per fare al volo certe cose!

use strict;
my @frags = ();
my @msg = grep /[A-Z]/, split('',$ARGV[0]);
foreach my $c (@msg) {
    my $a = ord($c) - ord("A");
    push @frags, ($a & 0x1C) >> 2;
    push @frags, ($a & 0x03);
}
my @lines = ();
while (<STDIN>) {
    my @w = split /\s+/;
    my $s = "";
    foreach my $l (@w) {
        my $n;
        if (@frags > 0) {
            $n = shift @frags;
        } else {
            $n = 0;
        }
        $s .= $l . (" "x($n+1));
    }
    print $s . "/\n";
}
print STDERR "left: ".@frags."\n" if @frags>0;

Ora a voi sta scrivere il programma di decodifica (poi lo farò pure io per verificare di aver scritto bene quello di codifica:-D…) Dunque c’è la poesia, che non è il messaggio, ma il messaggio non è nemmeno «occheipanico»… c’è ancora un altro livello. E se ce ne fosse un altro ancora (a parte quello allegorico, che avrete notato…)? …

A proposito… il programmino lo potete usare così:

perl encospace.pl "TESTO" <contenitore.txt

(potete usare solo le lettere maiuscole).

trituso

Macchine a stati finiti e pattern matching (parte 2)

fsm_img

Nell’articolo precedente vi ho fatto ricordare dell’Amiga, vi ho rivelato che aveva le sue espressioni regolari per fare pattern matching, vi ho indotto a (ri)leggere tre articoli di questo blog, e… (questo non lo sapete, ma) prima di pubblicarlo ho tagliato un paio di lunghi paragrafi che discettavano un po’ di linguaggi, metalinguaggi e divagazioni annesse e (s)connesse. Ora forse si capiscono meglio certe affermazioni che ho lasciato e che non si adattano benissimo al testo pubblicato; però vanno sempre bene come “scuse” anticipate per il futuro.

Dimenticavo: avevo anche detto che avremmo affrontato la prima fase: “fare” una macchina a stati finiti (FSM). Mi sono seduto e ho buttato giù un po’ di codice che ora rivediamo assieme. Lo trovate nel mio “parco giochi” su github, precisamente qui.

Le classi necessarie al gioco vivono nel namespace mFSM: visto che ho usato nomi molto poco particolari come State, Connection, Rule… non è una brutta idea metterli in un namespace ad hoc.

Introduzione

L’idea guida alla base è come viene di solito rappresentata una FSM; qualcosa come

FSM
FSM

Ogni stato è un cerchio con un “nome” (un’etichetta) e poi degli archi in uscita e in entrata. La freccia che non ha un’origine indica lo stato iniziale della macchina. Su ogni arco è indicato l’“evento” (nel nostro caso, la ricezione di un carattere) che fa passare la macchina dallo stato da cui esce l’arco allo stato in cui tale arco è entrante (insomma, nella direzione della freccia). Lo stato “a doppio cerchio” è uno stato “finale”: se la macchina, terminato il suo lavoro, si trova in uno di questi stati finali (accepting states, «stati che accettano [l’input e lo riconoscono come facente parte del linguaggio]»), significa che la stringa processata è una stringa corretta del linguaggio.

La macchina dirà allora: io, Macchina, accetto te come legittima stringa

Vi siete già imbattuti in questa roba:

soluzione

Sarebbe bello poter dire: lo stato S1 è uno stato finale, la macchina passa dallo stato S1 a S2 quando riceve uno 0, ma resta sullo stato S1 quando riceve 1, ecc.

In effetti basterebbe poter descrivere il graf(ic)o così: lo stato S1 va a S2 tramite l’arco 0, va a sé stesso tramite l’arco 1; lo stato S2 va a S1 tramite l’arco 0, va a sé stesso tramite l’arco 1; infine, lo stato S1 è uno stato finale accettabile.

Stati

Quindi per noi lo stato è un cerchio singolo o doppio con un’etichetta inscritta. Questi elementi fanno parte della sua identità e sono “passivi” e “statici”. Farne una classe è semplice

class State
{
public:
    State(const std::string& name, bool final=false);
    bool accept() const;
    const std::string& name() const;
    void setFinal(bool final=true);
protected:
    std::string name_;
    bool final_;
};

La maggior parte degli stati non sono final, da cui il default sul costruttore; ci sono due getter (per il nome e final) e un setter, nel caso volessimo cambiare final dopo aver creato l’istanza. (Se creiamo noi gli stati, serve a poco; ma vedrete dopo che la creazione degli stati può essere fatta implicitamente da un’altra classe).

Uno stato ha anche degli archi uscenti; potremmo farne uno stato consapevole del fatto che, quando riceve un certo messaggio, può dover passare il cerino ad un altro stato. Dal punto di vista della macchina nel suo insieme, lo stato con il cerino è quello in cui si trova la macchina (lo stato corrente). Con questa metafora posso dire che gli archi descrivono la “dinamica”, e ogni stato conosce la parte che gli compete, cioè i suoi archi che vanno (se valgono certe condizioni) verso un altro stato.

La classe AwareState, derivata da State1, aggiunge due cose: un metodo per stabilire un arco (onRule) e uno per iterare sugli archi. Quest’ultimo metodo è usato dal “supervisore”, cioè dal codice che fa girare la macchina: lo stato è sì “consapevole” delle sue relazioni regolate, ma non è lui a tenere traccia di chi ha il cerino e a decidere cosa farne se la regola si rivela valida o no.

Però lo stato deve fornire gli elementi affinché il “supervisore” possa decidere, e lo fa senza esporre i dettagli sul come mantiene le connessioni2: il chiamante invoca il metodo overConnectionsDo fornendo come argomento una funzione che riceve una regola (Rule) e lo stato di destinazione. Il “supervisore” applica la regola sull’input (di cui lo stato non è aware) che sta elaborando e decide se mantenere lo stato corrente o passare a quello di destinazione.

Non è un design entusiasmante… però ci permette di buttare in pentola una cosa del C++11: l’header functional ci dà std::function<...> tramite il quale è facile specificare il “prototipo” della funzione che ci aspettiamo come argomento… e che potrà essere — e sarà — una closure

bool AwareState::overConnectionsDo(
        std::function<bool(const Rule*,
                       const std::string& stateName)> action) const
{
    for (auto& c : connections_) {
        if (action(c.rule, c.destState)) {
            return true;
        }
    }
    return false;
}

Usando altre due comodità del C++11 (ovvero auto e il for each che ci permette di iterare sugli elementi di una classe itarabile) passiamo in rassegna le “connessioni”; se l’action ritorna vero, usciamo a nostra volta con vero; altrimenti proseguiamo con la “connessione” successiva. Se per nessuna delle connessioni l’action ha restituito true, allora ritorniamo al chiamante con false. (Nel codice ho messo una versione alternativa di cui parlo alla fine.)

Praticamente ci aspettiamo che il chiamante usi action per segnalarci quando ha trovato una regola soddisfacente (solo il chiamante sa qual è l’input!) Se abbiamo più regole che danno true, la nostra FSM è malfatta. Non c’è nessun controllo nel codice per impedire ciò: sta a chi la costruisce non creare situazioni strane.

L’ordine delle regole va considerato arbitrario, cioè non dobbiamo far affidamento su un ordine preciso di controllo per fare magari qualche trucchetto strano. Nella specifica implementazione le regole ordinate in base alla dimensione dell’insieme di caratteri che possono soddisfarla. Quindi any, che è l’unica regola che acchiappa tutto (dunque 256 codici…), starà sempre in fondo.

AwareState& AwareState::onRule(const Rule* rule, const AwareState* dest)
{
    Connection con{rule, dest->name()};
    connections_.push_front(con);
    connections_.sort([](const Connection& a, const Connection& b)->bool {
            return a.rule->size() < b.rule->size();
        });
    return *this;
}

L’ordinamento è fatto passando una funzione anonima (di fatto una lambda function) al metodo sort gentilmente offerto da list, che è la classe di connections_.

Per capire qual è il problema che l’ordinamento risolve, consideriamo le regole a, any, ~b controllate in quest’ordine. Non hanno molto senso: se l’input è a (1) prendiamo la prima; in tutti gli altri casi si applica any (256) e mai ~b (255). Se l’ordine fosse a, ~b, any, l’input a verrebbe catturato dalla prima, c dalla seconda e b, infine, dalla terza. I numeri tra parentesi contano i caratteri per i quali la regola è valida (un ottetto ha 256 possibili valori).

Connection

AwareState mantiene le connessioni tramite una lista (list) in cui mettiamo le coppie 〈regola, nome dello stato di destinazione〉 (struttura Connection). Ho usato il nome invece del puntatore (passato in onRule) perché c’era un meccanismo che distruggeva e ricreava gli stati e in questo modo si evitavano puntatori ballerini (dangling pointer). Naturalmente i nomi vanno risolti, e questo è a carico della classe FSM che mantiene un’anagrafe di stati e regole.

Le regole (Rule)

Un arco parte da uno stato (che è quello che lo mantiene, nella lista connections_ di AwareState) e finisce in un altro (Connection.destState) “tramite” una regola, modellata dalla classe Rule. Con “tramite” intendo dire che c’è (o ci dovrebbe essere…) una relazione tra l’avvenuta o mancata transizione e la validità dell’input rispetto alla regola in questione (e dirò anche, in alternativa, che la regola è valida per quell’input).

La regola è espressa tramite una stringa e si applica a un singolo carattere in input (passato come int). Quando dico carattere intendo in realtà byte: il codice non gestisce stringhe in codifiche multibyte. Il metodo satisfiedBy ritorna vero se il carattere soddisfa la regola, falso altrimenti.

Dal codice per satisfiedBy si capisce che le regole sono pochine: match esatto, qualunque carattere e infine match con tutto tranne un carattere specifico. Possiamo espanderle a piacere anche con l’intento di semplificare la macchina3.

Cosa accade se la regola è soddisfatta dipende dalla funzione action passata a overConnectionsDo. Il metodo viene invocato da FSM::feed.

Le regole possono venir usate più volte da diversi stati: la regola che accetta la a è sempre la stessa, sia che la usi lo stato X sia che la usi lo stato Y. Questo fatto viene sfruttato dalla classe FSM, che ha un magazzino di regole.

FSM

La classe FSM mette insieme un po’ tutte le altre classi, usandole in modo opportuno. È la classe che “rappresenta” la macchina a stati finiti ed è contemporaneamente la classe che la fa “girare”.

Per costruire la nostra macchina usiamo principalmente connect, che crea implicitamente gli stati di cui non conosce il nome; tuttavia crea stati non-final di default, per cui gli stati final vanno creati esplicitamente a parte.

m.state("S1", true);
m.connect("S1", "S2", "0");
m.connect("S1", "S1", "1");
m.connect("S2", "S1", "0");
m.connect("S2", "S2", "1");
m.first("S1");

L’ultima riga definisce lo stato di partenza; in questo caso non serviva perché il primo stato creato è anche quello di partenza.

La macchina m così creata è quella dell’esempio di wikipedia e serve per vedere se un numero ha un numero pari di 0.

Come usiamo questa macchina? Abbiamo due modalità principali.

Una è quella passo-passo: le diamo in pasto dei caratteri (tramite il metodo feed) e lei si comporta di conseguenza, cambiando il suo stato (oppure no…). Quando abbiamo finito possiamo sapere se la macchina è in uno stato final usando il metodo accepted(). Se vogliamo riusare la macchina per un’altra sequenza, dobbiamo riportarla allo stato iniziale (metodo rewind).

L’altra modalità prevede di far girare la macchina su una stringa (run). Questo metodo parte sempre dallo stato iniziale, ma al termine lascia la macchina nello stato dove l’input l’ha condotta; perciò dovete chiamare rewind se dopo un run volete usare feed con la macchina nello stato iniziale.

Il metodo run ha due modi diversi di funzionamento: uno strict, in cui l’assenza di una regola che gestisca l’input interrompe il processamento e restituisce false (però la macchina potrebbe essere ferma su uno stato final… sta al chiamante decidere che fare…); un altro in cui ogni carattere per il quale non c’è una regola lascia la macchina indifferente (si passa al carattere successivo rimanendo nello stesso stato). Il default è la versione “rilassata”; si può cambiare chiamando il metodo strict(true).

Il metodo feed è un po’ il cuore dell’esecuzione. Dopo un breve preambolo per assicurarsi che ci sia uno stato iniziale e quello corrente, abbiamo una bella closure passata al metodo overConnectionsDo dello stato corrente.

    const AwareState* next_current = current_;
    bool matched = current_->overConnectionsDo(
        [c,&next_current,this](const Rule* r, const std::string& s)->bool {
            if (r->satisfiedBy(c)) {
                if (this->states_.count(s) > 0) {
                    next_current = states_[s];
                }
                return true;
            }
            return false;
        });
    current_ = next_current;    

Se andate a vedere il codice di overConnectionsDo, vedete che è un ciclo sulle “connessioni”, cioè sulle coppie 〈regola, stato destinazione〉. È quello che la funzione riceve in ingresso (r e s). Oltre agli argomenti, la funzione “cattura” c, next_current e this. Poiché abbiamo bisogno di cambiare next_current, lo catturiamo per riferimento (this è un puntatore e quindi automaticamente con this->states_ facciamo riferimento all’istanza e non ad una sua copia).

Se il carattere c soddisfa la regola che lo stato ci ha passato, allora il prossimo stato sarà quello specificato da s, posto che esista. Alla fine della giostra matched sarà vero se c soddisfa almeno una delle regole r, e sarà falso altrimenti (se nessuna regola è stata soddisfatta).

Verifichiamo!

Il codice testFSM.cpp crea alcune FSM e le mette alla prova. In particolare ho creato la FSM corrispondente al pattern #?.info… Il pattern non richiede che dopo .info non ci sia altra roba. Sapete modificare la FSM in modo che la stringa da verificare debba finire esattamente con .info? (Con le RE ciò equivale a .*\.info$4).

Trovate anche la macchina per la grammatica a(ab)n e quella per riconoscere i codici 12A45 o 22B48 (cfr. Macchine a stati 2). Potete aggiungere tutti i test che volete per verificare che si comporti come vi aspettate… Se trovate un bug, sono qui per schiacciarlo… sempre tempo permettendo!

Sul codice

Non ci dovrebbero essere cose particolarmente difficili.

Ho cercato di mettere un minimo di enfasi su ciò che personalmente trovo più interessante nel C++11, ovvero le funzioni che stanno guadagnando il posto di cittadini di prima classe e ci permettono di adottare un po’ del paradigma funzionale. A tal scopo, oltre a functional, ho incluso algorithm per riscrivere il codice di overConnectionsDo usando std::any_of, che restituisce vero se per uno qualunque degli elementi il predicato ritorna vero (qui il predicato è data dalla nostra action, che dobbiamo però wrappare in un’altra closure per “adattare” gli argomenti5).

bool AwareState::overConnectionsDo(
    std::function<bool(const Rule*,
                       const std::string& stateName)> action) const
{
    return std::any_of(connections_.begin(),
                       connections_.end(),
                       [&](decltype(connections_.front()) c) {
                           return action(c.rule, c.destState);
                       });
}

Un’altra cosa che torna comoda è poter demandare al compilatore l’ingrato compito di “capire” il tipo giusto di un dato, visto che lui può dedurlo; alle volte non è solo ingrato, ma anche piuttosto complicato (non è il caso del codice della FSM, ma il discorso è generale). Su questo versante ho usato due novità: auto e decltype, che vedete nel frammento sopra. Sconsiglio l’uso di decltype come l’ho usato io: l’ho fatto solo per farvi vedere che, volendo, si può fare… (a mano avremmo scritto const Connection&).

Infine, tutto vive in due file soltanto, FSM.cpp e FSM.hpp. In teoria sarebbe più carino se avessimo State.cpp, AwareState.cpp, Connection.cpp, Rule.cpp, FSM.cpp e relativi .hpp. Ma viste le dimensioni del tutto, non credo che sia un peccato troppo grande aver fatto un nunico malloppo.

Compilazione

Per divertirvi con i test, la compilazione è

g++ -I src/ -std=c++11 src/FSM.cpp src/testFSM.cpp -o testFSM.cpp

Questo se state nella root del progettino (un livello sopra src). Forse ci aggiungerò un Makefile in futuro.


  1. Poteva esserci anche una sola classe State, che fosse già anche consapevole, visto che State normale non è usata… Potete provare come esercizio ad eliminare State incorporandola direttamente in AwareState (poi potete rinominarla in State). È andata così perché prima è uscita la classe, piuttosto ovvia, State e solo dopo mi sono trovato a dover scegliere come rappresentare le “connessioni” tra i diversi stati. Dalla scelta fatta è nato l’AwareState

  2. Questo perché per progetto le “connessioni” sono informazioni che lo stato tiene con sé, diventando “stato consapevole”, AwareState. Si poteva fare diversamente, forse meglio: una classe che descriveva tutta la FSM: dallo stato Si si va allo stato Sj quando la regola Rn è valida… ecc. Il “supervisore” non avrebbe fatto altro che leggere questa descrizione e agire basandosi su di essa e sull’input. Invece per ciascuno stato l’informazione che serve al “supervisore” è nello stato stesso, per cui c’erano almeno due opzioni: un getter per ottenere la lista degli archi uscenti (connections_), o un metodo che invoca una funzione su ciascuna connessione trovata — ogni “connessione” è una “regola” e uno stato destinazione.

  3. Per esempio: se il carattere è in un elenco (immaginate [0-9]), salta allo stato Sn. Dobbiamo fare un arco per ciascun carattere; se la Rule consentisse il match con un elenco, ci risparmieremmo un po’ di archi.

  4. Invece nel caso dei pattern Amiga è implicito, nel senso che il match è sempre esatto; con le RE è come se scrivessimo sempre ^...$ (dove ... rappresenta il resto della RE); quindi in realtà il pattern che la FSM implementa è #?.info#? e non #?.info.

  5. Si potrebbe usare std::function<bool(const Connection&)> e risparmiarci un livello: il predicato sarebbe direttamente action.

Macchine a stati finiti e il pattern matching amighista (parte 1)

amirex

Sono un Amighista, lo confesso. L’Amiga era un computer molto serio, a dispetto di ciò che tanti credono dal momento che il suo successo commerciale era dovuto principalmente ad alcune capacità che lo rendevano assai appetibile nel mondo ludico. Oltre all’hardware custom (che oggi fa sorridere ma all’epoca era incredibile…) c’era un sistema operativo straordinario.

Non voglio parlarvi dell’AmigaOS in generale: mi aggancio ad alcuni vecchi articoli di questo blog che parlano di regular expression e macchine a stati finiti, e con il pretesto cerco di implementare il pattern matching usando le regex nella variante messa a disposizione dall’Amiga tramite la libreria di sistema dos.library.

Sull’Amiga si parlava proprio di pattern matching: vedete per esempio la sezione 7-31 del manuale Using the System Software v2.05, che potete trovare su archive.org in vari formati tra cui DJVU.

Rileggere questi post (o leggerli se non li avete mai letti) non vi farà male:

Spero che le mie scarse capacità didattiche e la mia prolissità non vi ammorbino troppo. Se notate errori di varia natura (che non siano frutto di necessarie semplificazioni) o avete suggerimenti, li ascolterò… tempo permettendo.

Questo articolo è solo di apertura e non c’è veramente carne al fuoco.

Pattern matching su Amiga

Pare che ci siano circa 7000 linguaggi nel mondo, ma quelli che siamo in grado di elencare e di cui sappiamo l’esistenza sono una misera frazione.

Le regular expression più note sono in pratica tre e sembrano varianti/estensioni di una base comune: POSIX semplici, estese e PCRE (Perl Compatible Regular Expression).

Ma un tempo c’era pure l’Amiga e anche lì c’era l’esigenza di avere delle regular expression per fare del pattern matching (chiaro, no?) Un uso caratteristico era nei file requester1.

Un file requester della libreria di sistema asl.library
Un file requester della libreria di sistema asl.library

Il file requester nell’immagine è dell’AmigaOS4, ma comunque c’era pure nelle versioni precedenti (fornito allora come “ora” dalla libreria di sistema asl.library), anche se magari meno gratificante esteticamente; per i più esigenti c’erano altre possibilità fornite da toolkit come MUI o ReAction.2

Il punto comunque è che in questi file requester tipicamente si metteva di default il pattern per nascondere i file .info, che sono dei file del Workbench (il “desktop” e l’explorer o il finder dell’Amiga) contenenti l’icona ed eventualmente alcune metainformazioni associate. Niente che di solito l’utente voglia vedere quando richiede l’elenco dei file contenuti in una cartella, che su Amiga si chiamava drawer (cassetto) o directory (schedario).

Per questi scopi il glob è più popolare, è un po’ più alla portata di tutti (mentre moltissimi utenti non sanno nulla delle regular expression): se una finestra di dialogo di un programma di grafica ci chiede di scegliere un file, molto probabilmente applicherà diversi “glob”, uno per ogni formato che capisce: *.jpg, *.png ecc.3

Il pattern (Amiga) per nascondere i .info è, come potete vedere dall’immagine, ~(#?.info): il pattern #?.info selezionerebbe tutti i file terminanti in .info. Il ~ nega e le parentesi raggruppano, sicché ~(#?.info) seleziona tutti i file che non soddisfano il pattern #?.info, cioè che non terminano con .info.

Avrete intuito (forse) che #?, espresso nella lingua delle regular expression più note, è .*. Su Amiga ? significa “qualunque carattere”, dunque equivale al punto, e # è il quantificatore (ciò che segue compare 0 o più volte), dunque equivale all’asterisco. Notiamo anche che l’ordine è invertito: su Amiga diciamo prima quante volte compare ciò che segue, mentre nelle RE il quantificatore viene dopo.

Il problema che ci poniamo non è la traduzione tra sintassi diverse di RE o pattern “equivalenti”: vogliamo costruire una macchina a stati finiti per matchare una stringa a partire dai pattern in stile Amiga.

Notate una cosa: una volta che abbiamo la nostra macchina a stati finiti, ci possiamo disinteressare delle sue origini, cioè da dove siamo partiti per generarla: siamo partiti da #?.info? O da .*\.info? O da *.info? O l’abbiamo scritta a mano?

Ora potete studiarvi il pattern matching dell’Amiga, se proprio volete…

Nella prossima puntata

Per incuriosirvi… (spero di avere il tempo e la voglia: che non diventi del vaporware, insomma!)

Il problema può essere decomposto in due parti. La prima è poter definire programmaticamente una macchina a stati finiti, ed è quello che volevo provare a fare nella prossima puntata. Fatto ciò, dovremo risolvere l’altro problema: generare la macchina a partire dal pattern4.

L’idea che voglio seguire per la FSM è questa: definire gli stati e poi “unirli” tra di loro, specificando in quale circostanza (ovvero in seguito a quale “evento”) si passa da uno stato all’altro — l’esempio terrà sempre a mente l’uso specifico delle espressioni regolari e affini, sicché gli “eventi” sono in realtà i caratteri letti dall’input. Potremo poi dare in pasto alla macchina a stati così definita la stringa da controllare.

Una volta che abbiamo questi mattoncini, dovremo implementare un algoritmo che ci consenta di generare la macchina a stati a partire dal pattern: tornerà in gioco il pattern matching Amiga, tanto per prendere le distanze dalle RE note, troppo famose… e anche perché sennò che ne ho parlato a fare?

Due cosette che è bene tenere a mente:

  • non ho alcuna pretesa di rigore formale teorico (non ne sarei nemmeno capace) — se avete rimostranze sulla terminologia, suggerimenti per evitare fraintendimenti con il mondo accademico e/o settoriale, o perle di saggezza in generale, elargitele, ma tenete a mente che semplificare e comunicare alle volte significa mentire consapevolmente…;
  • alcuni aspetti (anche pratici) non saranno curati, per questioni di tempo e proporzioni — insomma, non vi aspettate del codice perfetto, con un design ben pensato, ecc… tuttavia, se mi fate notare o se noterò da me erroracci e/o antipattern vergognosi, proverò a trovare il tempo di coprire le tracce correggerle.

Dubitate, pensate, esplorate, non vi fermate, ricominciate.

Qui metterò il link alla prossima puntata non appena avrò avuto il tempo di scriverla:


  1. «I requester sono delle sottofinestre temporanee usate per confermare azioni o selezionare opzioni» (tradotto da ASL Library, About Requesters. Sono insomma delle finestre modali.

  2. Nelle versioni più recenti del sistema (ma prima di AmigaOS4), Amiga aveva introdotto il BOOPSIBasic Object Oriented Programming System for Intuition — negli “ingranaggi” di Intuition (appunto). Questo facilitò la nascita di toolkit che si integravano bene con Intuition, sia dal punto di vista dell’utente quanto del programmatore (che comunque, come al solito, ha vita sempre un po’ più difficile…) Potete pensare a BOOPSI come alle fondamenta per la costruzione delle classi di oggetti dell’interfaccia.

  3. Seguendo l’incauta consuetudine secondo la quale ciò che viene dopo l’ultimo punto del nome di un file sia sufficiente ad identificarne il formato.

  4. Cfr. Thompson’s construction algorithm e, per esempio, questa risposta su StackOverflow.