Category Archives: How to

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…

Annunci

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.

Ottimizzare il codice

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Questa frase è stata attribuita a Donald E. Knuth, e se lo dice lui che ha scritto “The Art of Computer Programming”, ha inventato il TeX, e ha sviluppato la teoria della complessità degli algoritmi, potete stare certi che sia vero.

Il significato della frase è che bisognerebbe evitare di ottimizzare il codice prima di aver finito di scriverlo. Il modo di programmare “corretto” sarebbe:

  • primo, si scrive il codice nella maniera più semplice possibile, possibilmente in maniera elegante e leggibile
  • poi ci si accerta della sua correttezza (testing , debugging, e quello che pare a voi)
  • Infine, pensiamo alle performance, ottimizzando il codice dove necessario

Spesso invece il programmatore comincia fin dall’inizio a complicare il codice e la strrutra del programma, alla ricerca del programma già perfettamente ottimizzato. Nel fare così, spesso viene fuori codice molto complicato e probabilmente pieno di bug. Da qui la sentenza di Knuth: l’ottimizzazione prematura è la radice di tutti i mali!

L’osservazione chiave è che spesso il codice contiene alcuni (pochi) “colli di bottiglia”, ed è lì che l’ottimizzatore deve concentrarsi per far andare veloce il suo programma. Come identificare questi “colli di bottiglia”? Per esempio, funzioni chiamate molto frequentemente, strutture dati usate pesantemente in tutto il codice, ecc. I programmatori esperti ormai lo fanno ad occhio, ma per programmi molto grandi e complessi non è affatto facile. Sarebbe bene ci fosse qualche strumento di ausilio al programmatore.

oggi vediamo come fare analisi delle prestazioni con due tool disponibili su Linux con licenza GPL: valgrind e kcachegrind.

Il primo è una specie di “emulatore” del vostro PC. Prende in ingresso un file eseguibile, e lo esegue su un “processore virtuale”. Nel portare avanti l’esecuzione, però, è in grado di effettuare una serie di analisi sul codice. Valgrind è una piattaforma generica su cui sono stati sviluppati diversi strumenti. Il più famoso è memchek che serve a controllare l’uso della memoria, ed individuare possibili “memory leak“. Quello di cui ci occupiamo oggi, invece, è callgrind che serve a stimare le performance delle varie parti di codice del nostro programma.

Per installare questi tool, su Ubuntu si deve scrivere sul terminale:

sudo apt-get install valgrind
sudo apt-get install kcachegrind

e siamo pronti per i nostri esperimenti.

Proveremo ad utilizzarlo sui programmini che Juhan ci ha proposto per fare confronti fra il Fortran e vari altri linguaggi. Cominciamo dalla versione C/C++ di tale programma, che riporto qui per comodità (anche perché ho fatto due modifiche).

#include <stdio.h>
#include <math.h>

double f[14];

#define POW(x,y) pow(x,y)
//#define POW(x,y) mypow(x,y)

inline double mypow(double x, int y)
{
    double r = 1;
    for (int i=0; i<y; i++) r *= x;
    return r;
}

double fsin(double a) {
    return a - POW(a, 3) / f[3] + POW(a, 5) / f[5]
        - POW(a, 7) / f[7] + POW(a, 9) / f[9]
        - POW(a, 11) / f[11] + POW(a, 13) / f[13];
}

static double fcos(double a) {
    return 1.0 - POW(a, 2) / f[2] + POW(a, 4) / f[4]
        - POW(a, 6) / f[6] + POW(a, 8) / f[8]
        - POW(a, 10) / f[10] + POW(a, 12) / f[12];
}

static double myln(double x) {
    if (x == 0.0) {
        return -1.0e20;
    } else {
        double r = (x - 1.0) / (x + 1.0);
        return 2.0 * (r + POW(r, 3) / 3.0
                      + POW(r, 5) / 5.0
                      + POW(r, 7) / 7.0
                      + POW(r, 9) / 9.0);
    }
}

double mylog(double x) {
    static double ln10 = myln(10.0);

    return x / ln10;
}

int main(int argc, char **argv)
{

    int i, j;
    f[0] = 1.0;
    for (i = 1; i < 14; i++)
        f[i] = i * f[i - 1];
    int deg = 60;// * 60;
    int nsteps = 180 * deg;
    double step = M_PI / nsteps;
    double ssum;
    double csum;
    double a, s, c, t = 0.0;
    double ls, lc;
    for (j = 1; j < 11; j++)
    {
        ssum = 0.0;
        csum = 0.0;
        for (i = 0; i < nsteps; i++)
        {
            a = i * step;
            s = fsin(a);
            ls = mylog(myln(s));
            ssum += s;
            c = fcos(a);
            lc = mylog(myln(c));
            csum += c;
            if ((i % (10 * deg)) == 0)
            {
                if (c != 0.0)
                    t = s / c;
                printf("%3d %11.8f %11.8f %11.8f %15.8e\n", (i / deg), a, s, c, t);
                printf(" %15.8e %15.8e\n", ls, lc);
            }
        }
    }
    printf("%g\n", ssum);
    printf("%g\n", csum);
}

Le due modifiche fatte sono le seguenti: ho sostituito tutte le chiamate a pow() con la macro POW. Quest’ultima si traduce per il momento nella chiamata di libreria pow() (che, come discusso nel post precedente, è più lenta). Inoltre, ho diminuito il numero di cicli da svolgere per accorciare un po la durata dell’esecuzione: adesso il conto viene fatto per deg = 60 invece che per deg = 60*60 (vedi linea 54).

Salvate il programma qui su sul vostro HD con il nome prova.cpp, e poi compilatelo con il seguente comando:

g++ -g prova.cpp -o provacpp

Il flag -g serve per inserire i simboli di debug nel file eseguibile, e la qual cosa ci permetterà di associare il costo delle operazioni alle relative istruzioni nel codice sorgente.

Adesso siamo pronti per l’esecuzione, ecco il comando da dare:

valgrind --tool=callgrind ./provacpp

Questo manda in esecuzione il tool callgrind sul file eseguibile provacpp. Il quale viene eseguito a una velocità molto inferiore a quella normale (parliamo di un rallentamento di quasi 100 volte!) e vengono collezionati i dati di performance. L’output è un file che si chiama

callgrind.out.PID

Dove PID è l’ID del processo che è stato eseguito.
Per visualizzare i dati, date il comando:

kcachegrind callgrind.out.PID

(dove naturalmente avrete sostituito PID con il numero giusto), e si aprirà una finestra come questa:

La finestra principale di KCacheGrind

Questo tool ci visualizza i risultati dell’esecuzione. Faccio zoom sulla finesta a sinistra dove viene mostrato il “call graph” (ovvero il grafo delle chiamate):

Come vedete, il main() chiama le funzioni myln, fsin e fcos, e ciascuna chiama la funzione pow, la quale a sua volta chiama le funzioni interne per fare operazioni floating point. Subito sotto il nome delle funzioni viene riportato il tempo (in percentuale) speso dal programma dentro quella funzione. Questo programma ha speso il 95.73% del suo tempo dentro la funzione pow()! Notare anche una certa asimmetria: myln prende il 50% del tempo, mentre fsin e fcos ciascuna circa il 25%.

Adesso riproviamo utilizzando la funzione mypow() (quella che fa le moltiplicazioni per fare le potenze): basta commentare la linea 6 e scommentare la 7, e ricompilare. Se rifate tutto il percorso otterrete questo callgraph:

Come vedete, le cose sono un po’ cambiate. In particolare, mypow() non chiama alcuna funzione in floating point (come ci si aspetta), e inoltre le percentuali di myln, fsin e fcos sono un po’ cambiate.

È anche possibile mostrare questi numeri direttamente sul sorgente, cliccando sulla tab “Source Code”, ed ecco lo snapshot relativo:

Infine: si può fare una cosa del genera anche per il fortran? Ovviamente sì! Vi riporto semplicemente il comando di compilazione e di esecuzione:

gfortran -g m_c10l.f08 fc10l.f08 -o provaf
valgrind --tool=callgrind ./provaf

E poi tutto come prima. Ecco lo screenshot del callgraph per il fortran:

Qui notiamo che la funzione per la stampa a video (_gfortran_transfer_real_write) prende ben il 13% del tempo, ed è probabilmente lei la causa delle peggiori prestazioni del fortran rispetto al C/C++. Inoltre, notate come da nessuma parte ci sia una chiamata ad alcuna pow(), perché nel fortran l’elevazione a potenza per un numero intero è una operazione del linguaggio.

Ovviamente, questi tool funzionano bene per codice eseguibile, non funzionano affatto bene su Java e su Python. Ci sono però altri tool, più o meno professionali, che fanno cose analoghe. Semmai se ne parla un’altra volta!

Spero che questo post possa esservi utile nel vostro lavoro di “ottimizzatori!”, e ricordate le parole di Knuth!

Nota di Juhan: Mi ricordo il profiler id Borland; questo è molto più bello e anche il prezzo. Vero? Vero dikiyvolk?

Ancora su j – Autojump e source

Il post su Autojump  è piaciuto. E pensare che l’idea ce l’avevo da parecchio tempo, non so quante volte ho cominciato a scriverci e poi lo abbandonavo perché non mi piaceva 🙂


OK, postandolo ci sono stati i commenti con suggerimenti e precisazioni. E adesso è tutto molto più chiaro. Vorrei allora chiudere l’argomento con questa breve nota, approfittando della vostra pazienza 😉

Il suggerimento di Marco Delmastro (il suo blog, Borborigmi  è über-yotta-mitico) di usare source funziona, da approfondire.

Il prof Lipari, glipari ha indicato il metodo usato da Autojump, un post di StackOverflow. Era stato glipari che mi aveva fatto conoscere Autojump e sospendere i miei tentativi di ricreare j con Linux.

Il commento di bit3lux / Luigi dà una soluzione che funziona ma “non è elegante“, come illustrato nel commento di glipari. Si vede che Luigi è troppo giovane: quando non c’era l’ambiente grafico ormai pervasivo il terminale era tutto per la shell. E potevi (OK, anche adesso) avviare una sub-shell digitando sh (non bash o csh, non usare mai quei nomi). Non so se il termine è corretto ma da noi si diceva che attivavi una sessione ospite. Con ctrl-D o exit uscivi da questa sub-shell e tornavi a quella precedente. Nulla vietava di annidare sub-shell per più livelli anche se 1) non so bene a cosa potesse servire; e 2) consumava memoria. Con tanti ctrl-D quanti erano i processi attivati tornavi alla shell originale; se ne battevi uno in più ti slogavi (c’era una variabile da settare per evitare che ciò avvenisse, la usavano solo i niubbi che allora si chiamavano pivelli).

Autojump di Joël Schaerer è perfetto, auto impara quali sono le directory che vengono usate e dimentica quelle vecchie; usa un algoritmo per indovinare quello che vuoi impiegando una regular expression (RegEx, RE) da paura. E poi Python è un linguaggio di script trendy e simpa (i francesi come Joël dicono così). Certo, seguendo l’indicazione di Marco si potrebbe fare a meno di Python, magari coinvolgendo Perl per la RE 😉

Non credo che mi avventurerò per questa strada ma per source ho provato a googlare un pochino. Ecco cosa ho scovato.

source
Avendo a disposizione il SysV Command Reference di Apollo, novembre 1989 ho voluto indagare se source c’era già in Unix-SysV. Pare di no. Il manuale ha la Section 1 –quella che m’interessa– e la Section 6 –games. I comandi sono in ordine alfabetico. A p.1-511 (si apre automaticamente lì) inizia SH(1), la Bourne shell, occupa le pagine fino a 1-523 compresa. Rimanda a pagine di SysV Programmer’s Reference che non ho. Non cita source.

CSH(1), la c-shell inizia a p. 1-91 e arriva fino a p. 1-115 compresa.
E c’è source, a p. 1-108, copio:

source name
Read commands from name. You may nest source commands, but if you nest too many deeply, the shell may run out of file descriptors. An error in a source at any level terminates all nested source commands.

source -h name
Place commands in the history list without executing them. Normally, input during source commands is not placed on the history list.

KSH(1), la Korn shell è descritta nelle pagine da 1-295 a 1-323. Ebbene sì Apollo permetteva di usare la shell che volevi, bash non c’era ancora. Nessun riferimento a source.

Idea per il futuro: se a qualcuno interessa potrei mettere le scansioni di queste pagine e magari incorrere nelle ire di HP.

A p. 1-528 c’è SORT(1) e a p. 1-529 SPELL(1) che continua anche sulla successiva, niente source quindi.

OK! source è nato in BSD e SysV non ce l’aveva. Mistero il motivo per cui tutti (a quanto pare) usassero la Bourne shell quando c’era la Korn, più nuova, almeno a giudicare da com’è ridotto il manuale.

E per Linux? Tanti, credo, sanno che si può usare source quando si modifica ~/.bashrc ma solo quello. Tranne Marco 😀 e pochi altri.
La googlata per source è stata fruttuosa, ecco

http://www.cyberciti.biz/faq/linux-bsd-unix-source-command/
nixCraft è un sito da bookmarkare, imho. Toh! lo dice anche qui che è BSD.

http://bash.cyberciti.biz/guide/Source_command
stesso sito, altra pagina, Linux (credo).

http://webtools.live2support.com/linux/period.php
Web Tools, lo sapete che source può essere scritta come . (punto, dot)? Da bookmarkare anche questo, sempre imho.

http://ss64.com/bash/
An A-Z Index of the Bash command line for Linux. Già che ci siete  bookmarkate anche questo.

Ah questa non la sapevo:


Visto: source – Esegue comandi da un file nella shell corrente.
Nella shell corrente.

Quante cose ci sono da imparare! E quante cose so di non sapere (cit.).
Riuscirò mai a diventare quasi-geek o rimarrò per sempre un aspirante-geek? 😉

Autojump


Posso raccontarvi un po’ di storia personale? Sì?
OK, allora quando ho iniziato a lavorare mi sono trovato un minicopmuter (mini è fuorviante, pensate a un armadio grosso) tutto mio. Cioè no ma da gestire.
Era, l’ho già detto altre volte, un Prime, anzi PR1ME.
E era arrivato un Prime perché degli amici e colleghi avevano il Prime (il loro capo era appena tornato da MIT, vicino a Natick, dove c’era la fabbrica dei Prime –bei tempi, sigh!
Uno dei miei amici (anche se non ricordo chi) aveva deciso di semplificare il comando cd (sì, sul Prime non si chiamava cd ma attach, abbrevviabile in a; come per il VMS del Vax i comandi potevano essere abbreviati, basta che non ci fossero conflitti, ancora meglio del tab di Unix/Linux).
Per cui A LAVORI 1 2 poteva essere scritto J L. Bella comodità, l’avevo adottata al volo. E poi questo comando l’ho rifatto per MS-DOS, prima come batch command e poi con Turbo Pascal, antenato di Delphi.

Poi ho provato a farlo anche su Linux, e non ci sono riuscito. Adesso vi faccio vedere il perché.

Con Windows si può creare questo semplice script (loro non li chiamano script ma è uno script), j-t-w.bat

@echo off
c:
cd C:\DOCUME~1\Alice\IMPOST~1\Temp
echo sei in
cd
echo fatto.

eseguendolo nel Prompt dei comandi otteniamo

Come si vede al termine dello script la directory corrente è diventata Temp sul disco C:.
Proviamo a fare la stessa cosa con Linux, ecco lo script t.sh

#!/bin/sh
cd /tmp
echo sei in $(pwd)
echo fatto.

provo a eseguirlo

OPS! non funziona. Durante l’esecuzione dello script è effettivamente in /tmp ma quando lo script termina mi ritrovo nella directory di partenza. OK, la cosa è logica e naturale, Linux (e Unix prima) sono fatti meglio ma non fa quello che volevo. E non è facile farglielo fare.

La cosa all’inizio mi dava parecchio fastidio e ogni tanto riesumavo il progetto, senza concludere nulla. Cioè c’ero riuscito in un paio di modi ma non eleganti. Poi qualcuno (credo sia stato il prof Lipari ma non riesco a rintracciare il link) mi ha segnalato Autojump di joelthelionJoël Schaerer.

Dai, non era facile: bravo Noël, le lion! C’è riuscito con due script, uno tranquillo in Python e uno terribile in bash (e zsh, per chi usa questa shell). Noël è davvero un leone.

Autojump –in realtà si usa il comando j, proprio come facevamo su Prime, anche se allora j derivava da join– lo trovate nel Software Center di Ubuntu ma conviene installare l’ultima versione da github.

Per chi usa spesso il terminale è comodo, anche se ogni tanto mi fa ricadere nella tentazione di capire come funziona.

Era da un po’ che non mi capitava poi qualcuno ne ha parlato recentemente e mi sono deciso a prendere il toro per le corna: vediamo se questo post mi libera da questa ossessione.

Ah! visto che i miei amici Bit3Lux e Lightuono stanno portando avanti un corso di bash, questo post è dedicato a loro 😉

e ancora: bc, Python e newLISP

Continuo le prove iniziate in e Nepero e Eulero e il Fortran  anche se rischio commenti di Hon-ki-ton (no, dai, benvenuto! e benvenuti i commenti).

Allora il Fortran con la fama di number cruncher che si ritrova non mi sembra che si sia comportato benissimo. E se provassi con qualche altro linguaggio?

OK, c’è bc con la precisione che vuoi e 40 anni di servizio, una sintassi simile al C, anzi migliore, come il C dovrebbe essere, proviamo

scale = 15
m = 1000
eps = 1 / m
for (c = 0; c < 3; c++) { 	eps /= m } print "eps = ", eps, "\n" eprec =0. n = 1. delta = 10. i = 0 cm = 100 * m while(delta > eps) {
	e = (1 + 1 / n) ^ n
	print n, " ", delta, " ", e, "\n"
	n += cm
	i += 1
	if (e > eprec) {
		delta = e - eprec
	} else {
		delta = eprec - e
	}
	eprec = e
}
print "valore accettabile è stato raggiunto con ", i, " iterazioni\n"
print "con delta = ", delta, "\n"

quit

Una piccola precisazione: non mi va di correggere lo script; al momento di scriverlo non ricordavo la sintassi per i numeri esponenziali e il collegamento a internet era giù. Poco male, quattro righe quando ne bastava una.

L’esecuzione non è andata come previsto: l’ho interrotto dopo 12 ore perché il ‘puter (2 CPU a 2.4 GHz) aveva il fiatone e eravamo ben lontani dalla meta. Comunque ecco


Sconsolante! Ma aspetta: io sono affezionato a Python, chissà, proviamo dai

#!/usr/bin/env python
# -*- coding: utf-8 -*-

eps = 1e-12
print "eps =", eps

eprec = 0
n = 1.
delta = 10.
i = 0
cm = 100000
while (delta > eps) and (i < 1000):
	e = (1 + 1/n) ** n
	print i, n, delta, e
	n += cm
	i += 1
	delta = abs(e - eprec)
	eprec = e

print "valore accettabile è stato raggiunto con ", i, " iterazioni"
print "con delta = ", delta

Non ce la fa e allora metto un limite alle iterazioni, diciamo 1000, ecco, velocissimo


Dai, quasi buono, e soprattutto usabile al posto di bc. Ma un attimo ancora: chissà newLISP il linguaggio di scripting migliore in assoluto, quello che davvero preferisco e non mi ha mai deluso, tranne il modulo per la gestione dell’ambiente grafico ma quello è scritto in Java. Vediamo

(set-locale "C") ; l'abitudine
(set 'eps 1.e-12)

(set 'eprec 0.
	 'n 1.
	 'delta 10.
	 'i 0
	 'cm 100000)

(while (and (> delta eps) (< i 4000))
	(begin
		(set 'e (pow (add 1 (div 1 n)) n))
		(println i " " n " " delta " " e)
		(set 'n (add n cm)
			 'i (+ i 1)
			 'delta (abs (sub e eprec))
			 'eprec e
		)
	)
)

(println "valore accettabile è stato raggiunto con " i " iterazioni")
(println "con delta = " delta)

(exit)

Ho messo il limite a 4000 iterazioni, il risultato è simile a quello di Python. Anche lui velocissimo. Notare che dopo un po’ i numeri oscillano attorno al valore esatto; probabilmente erano sufficienti meno iterazioni.


Certo che una cosa così non me la sarei mai aspettata. Ma voglio dare un’ultima chance a bc

scale = 15
n = 5 * 10^5
ec = (1 + 1 / n) ^ n
print ec, "\n"
print e(1) - ec, "\n"
quit

Ho fatto un po’ di prove, aumentando via-via in valore di n, ecco il risultato dell’ultima, per n pari a mezzo milione; l’esecuzione ha richiesto qualche minuto.


Quindi?
Ho imparato una cosa: non usare la definizione per il calcolo di e. Ci sarà un motivo per cui esiste una ricca letteratura, per esempio ecco Wiki 😀


Non so se è il caso di preoccuparmi: cercando per qualche immagine Google propone le mie a partire da p.9 😉

Grafici istantanei grazie al Gatto Energico(TM), poi Giulia e Google

Un post che potrebbe essere giudicato troppo piccolo, un postino posticino minipost ma su un tool online davvero simpatico e altro ancora 8)

Tutto è nato da un tweet di Marco

che vi manda qui: The Physics of why the e-Cat’s Cold Fusion Claims Collapse. Il post è davvero bello e convincente ma non è di quello che voglio parlarvi. Quello che ha attratto la mia attenzione è il grafico a torta Natural Nickel Composition, la cui didascalia recita “(Image generated using this free software.)“. Ecco voglio parlarvi di questo free software.

click per accedere

Ecco, tutto qui. Con tante opzioni. Io –lo sapete che in queste cose non sono tanto bravo, vero?– sono riuscito a fare questo

ma si può fare molto di più. Al volo, senza installare niente 😀

Ma non è mica finito qui! No, al momento di postare salta fuori questo

che ci dice di andare qui; semplice, ecco


Per chi invece fosse interessato all’e-Cat ne parlano spesso gli amici di Query e Sylvie, che non viene mai invitata alle dimostrazioni 😦

Infine un consiglio per il dott. Rossi: secondo me ha sbagliato a rivolgersi all’Università di Bologna –non che abbia niente contro Bologna o la sua Università, non sia mai detto– ma per queste cose molto meglio la mia Università.

Qui non vale il detto di Carl Saganextraordinary claims require extraordinary evidence“, anzi 8)

Una pagina html con tutti i link che servono davvero


Alle volte un’idea semplicissima diventa, una volta sviluppata e realizzata, una di quelle cose che rendono la vita migliore –almeno un pochino.
Come quella di cui voglio parlare in questo post. L’idea non è mia –sia chiaro da subito– ma sapete come vanno le cose.
Anche Stefano Lavori ha copiato l’idea che ha cambiato il mondo dei ‘puter: scrivania, cartelle, documenti, topo e quant’altro li ha copiati dopo averli visti nel parco della collina del coyote. Bravo Stefano, che ha visto che era un’idea che acchiappava, ma, dico io, bravi quelli del parco che quelle cose le avevano immaginate.
Tutto questo per dire che chi è stato bravo davvero è Mattux (quello che in casa si ostinano a chiamare Matteo o, esagerando Matteo Pani)


Trovate tutto sul suo blog, nella pagina Startpage minimale che utilizza un menù. Quindi, dopo aver proposto a Matteo di brevettare il tutto, magari con il nome iMattux (Stefano insegna) il mio compito è finito. No! Aspettate un momentino, adesso vi racconto quelle che sono le mie personalizzazioni.

Al CSS di Matteo ho apportato un unica modifica: ho allargato il campo di destra. Nella riga (dovrebbe essere la n. 110)

ul.link { position:absolute; left:250px; top:50px; opacity:0; width:250px; visibility:hidden;

ho cambiato il valore di width sostituendo 250 con 400, altrimenti le descrizioni lunghe venivano spezzate su due linee. Il resto è tutto OK.

Nel file html le modifiche sono, ovviamente più numerose e personali.
Intanto il titolo, quello che appare sulla barra della finestra: è definito nelle prime righe, così <title>Tutti i link</title>.

La scritta grande in testa alla pagina è definita della divisione testata:

<div id="testata"> <h1>Tutti i link che servono davvero</h1> </div>

seguono tante div class=”contenuto_due” in cui vengono definite le scritte del menu e dei link. Qui io propongo una variazione rispetto alla versione di Matteo: la linea tipica per l’elenco della class=”link” è del tipo

<li><a href="https://plus.google.com/" target ="_blank">Google Plus</a></li>.
L’aggiunta di target =”_blank” aprirà la pagina indicata in un nuovo tab. Così questo menu si apre una volta sola e rimane aperto sempre nel tab più a sinistra, meglio no? 8)

Per inserire una riga vuota, non clickabile basta mettere
<li><a href="#">&nbsp;</a></li>

Attenzione che ogni div id=”gruppo” deve avere identificatori unici e consistenti per indice_# e lista_#; ma è facilissimo.

Tutto lì.
Funziona con Linux, Windows, Mac, _________. A meno che siate proprio speciali. Io l’ho testato con Firefox ma il codice è davvero standard, non dovrebbero esserci problemi. Per dire potreste usare anche Internet Explorer 8) –che sarebbe comunque una pessima idea.

Nel mio caso si vede che mancano le voci relative al Reader dei siti RSSati e per la mail. Ciò perché ho due estensioni che mi avvisano all’arrivo di nuovi documenti da leggere.

Oggi quello della mail non funziona 😦

Alcuni penseranno come direbbe il mio tutor a UCDB Gyro Gearloose

Troppo semplice, non capisco

ma a altri potrebbe piacere, e magari servire. Io per esempio lo sto usando. Sempre che Matteo non voglia farsi pagare le royalties 8)