Una macchina di Turing in CML 18 December 2010

Le macchine di Turing, ad oggi …hanno scarse applicazioni nella programmazione pratica. O meglio …lavorano così a basso livello che è estremamente difficile riuscire a programmarci qualcosa senza diventare pazzi!
Nonostante questo sono ancora il fulcro di tutta la teoria della calcolabilità su cui si basano gli attuali calcolatori.
E sono anche un modo simpatico per dimostrare la potenza di un linguaggio: se riuscite a creare una macchina di Turing con un linguaggio, allora quel linguaggio è Turing completo, e significa che può potenzialmente calcolare tutte le cose che sono calcolabili da mostri sacri come C o Java.
Certo, tra realizzare un programma in Java o in Assembler c’è una gran bella differenza, ma è solo una questione di espressività. Ovvero, di ciò che possiamo tralasciare. Ma questa è un’altra storia…

Vediamo ora come è possibile realizzare nel linguaggio CML una macchina di Turing.
Una macchina di Turing è definita dalla quintupla composta da:

• S: elenco degli stati,
• S0: stato iniziale,
• F: insieme degli stati finali,
• A: alfabeto del nastro,
• b: segno della casella vuota,
• d: funzione di transizione degli stati.

Per implementare in CML il concetto di stato, verrà usata un’emozione. Gli stati saranno identificati da un numero che varia da 0 a “max_state”. Lo stato iniziale sarà considerato senza perdita di generalità “0”.

<EMOTION
	name			= "state"

	initialValue	= "0"
	minValue		= "0"
	maxValue		= "max_state"

	decay			= "0"	/>

Quando l’emozione “state” assumerà il valore “x” affermeremo che la macchina di Turing si trova nello stato rappresentato dal codice “x”.

Dovendo materialmente definire il nastro sul quale la computazione avrà luogo, ci limiteremo ad un insieme finito di celle disponibili. Tuttavia sarà sempre possibile modificare il programma per prevederne un numero arbitrariamente grande e potenzialmente non limitato.
Ogni cella del nastro è rappresentata da una singola emozione che potrà assumere valori numerici tra zero e la cardinalità dell’insieme “A“, con la seguente semantica: quando l’emozione “cell_xx” assume il valore “x”, la cella numero “xx” conterrà l’”x”-esimo simbolo dell’alfabeto .

<EMOTION
	name			= "cell_xx"

	initialValue	= "0"
	minValue		= "0"
	maxValue		= "max_symbols"

	decay			= "0"	/>

Il puntatore alla cella corrente sarà rappresentato da un’emozione, esattamente come fatto per lo stato.

<EMOTION
	name			= "cell"

	initialValue	= "0"
	minValue		= "0"
	maxValue		= "max_cells"

	decay			= "0"	/>

Per convenzione, la testina della macchina di Turing sarà posizionata sulla prima cella, con indice “0”.

Il punto cruciale è realizzare il programma, definito dalla funzione di transizione “d“, nel seguente formato:
d : S x A → S x A x { -1, 0, +1 }

Quando la macchina di Turing si trova nello stato “s1” e legge “a1” dalla cella “c1” , passa allo stato “s2”, scrive “a2” nella cella corrente e decide come spostare il nastro (avanti, indietro o fermarsi) arrivando alla cella “c2”.

Per ogni combinazione della tripletta composta da uno stato non terminale, da una cella e dal suo valore presente, sarà creata una regola come segue:

	<!-- Siamo nello stato “s1” -->
	<REQUIRED
		emotion	= "state"
		type	= "EQUALS"
		value	= "s1"
	>
		<!-- Siamo nella cella “c1” -->
		<REQUIRED
			emotion	= "cell"
			type	= "EQUALS"
			value	= "c1"
		>
		<!-- Il valore della cella “c1” è “a1” -->
		<REQUIRED
				emotion	= "cell_c1"
				type	= "EQUALS"
				value	= "a1"
		>
			<!--	Questa regola si attiva sempre:
				ogni messaggio ricevuto manda la computazione
				avanti di un passo. -->
			<RULE regexp = "">
				<!-- Trace dell'elaborazione -->
				<ANSWER text = "<s1 X a1 @ c1> → <s2 x a2 @ c2>" />
				<!-- Cambia stato -->
				<UPDATE emotion = "state"	value = "=s2"	postpone = "true"	/>
				<!-- Aggiorna il valore della cella -->
				<UPDATE emotion = "cell_c1"	value = "=a2"	postpone = "true"	/>
				<!-- Sposta il nastro -->
				<UPDATE emotion = "cell"		value = "=c2"	postpone = "true"	/>
			</RULE>
		</REQUIRED>
		</REQUIRED>
	</REQUIRED>

Per gli stati terminali possono essere create regole molto più semplici, poiché non richiedono alcuna computazione.

<!-- Siamo nello stato terminale “st” -->
<REQUIRED
	emotion	= "state"
	type	= "EQUALS"
	value	= "st"
>
	<!--	Questa regola si attiva sempre:
	ogni messaggio ricevuto manda la computazione
	avanti di un passo. -->
	<RULE regexp = "">
		<ANSWER text = "Stato terminale st raggiunto." />
	</RULE>
</REQUIRED>

Partendo una macchina di Turing con “s” stati (di cui “f” terminali), “a” simboli ed un nastro finito di “c” celle, abbiamo ottenuto un programma CML composto da:

• c+3 emozioni (una per lo stato corrente, una per la cella corrente, “c” per il valore delle celle ed “unknown” obbligatoria in CML),
• (s – f) x c x a + f regole (“f” per gli stati terminali e le restanti per la funzione di transizione degli stati non terminali),
• 1 categoria (“UNKNOWN”, obbligatoria in CML).

Varianti più significative di questa macchina di Turing potrebbero essere realizzate leggendo gli input dall’utente, invece che direttamente dal nastro, o effettuando calcoli aritmetici incrementando e decrementando le emozioni come avviene nel linguaggio Brainfuck.

Come detto all’inizio …una macchina di Turing in CML è sostanzialmente inutile.
Ma è la dimostrazione pratica che anche il CML è Turing completo. Alla faccia di chi pensa che ci si possano fare solo bot!

Posted in cml, programming | No Comments »

Priority Executor 23 October 2010

Chi ha esperienza di programmazione C o C++ si sarà spesso trovato, se non a dover reinventare la ruota, quantomeno a programmare uno spinterogeno.
La politica di Java su questo è stata chiara fin dall’inizio: una libreria per ogni cosa.
Java non è più un linguaggio. Java È le sue librerie.

Per questo mi ha stupito la totale assenza di un componente che, a mio avviso, sarebbe dovuto essere di serie.
Il package “concurrent“, per quanto non brilli per eleganza e facilità di utilizzo, contiene una miriade di classi dall’utilizzo non ben precisato. Per questo non è stato facilissimo realizzare che quello di cui avevo bisogno non era nascosto tra le classi, ma non c’era proprio!

Seguendo la nomenclatura Java, il componente in questione si chiama “PriorityExecutor“. Alla parola “pool di thread” c’è sempre qualcuno che ha un sobbalzo, e proprio per questo ho deciso di pubblicare un piccolo pacchetto già pronto all’utilizzo.

Immaginatevi di avere un pool di thread. Ed ora immaginatevi che i vostri thread abbiano una proprità. Non mi riferisco alla “Priority” nativa del package “concurrent“, ma al fatto che alcuni debbano essere eseguiti prima degli altri, e per più tempo. Ma ovviamente con l’assunzione che tutti possano passare in esecuzione, evitando spiacevoli deadlock o fenomeni di starvation.

Ecco, questa classe non esiste. O almeno, non esisteva. “PriorityExecutor” realizza proprio quanto descritto, in maniera semplice anche se non sempre elegantissima.

Tutti i thread che vogliono schedulare con questo meccanismo devono estendere la classe “FairyFIFOPriorityRunnable“. Il nome riassume perfettamente le caratteristiche che sono garantite:

• Fairy: tutti i thread passano in esecuzione, evitando deadlock e starvation,
• FIFO: a parità di priorità, la precedenza è data a chi è arrivato per primo,
• Priority: ai thread con priorità maggiore è garantito un accesso più frequente all’esecuzione.

Vediamo come usarla:

class TestThread extends FairyFIFOPriorityRunnable {
	/* Costruttore */
	public TestThread (final int currentPriority) {
		super(currentPriority);
	}

	/* Il corpo del metodo */
	@Override
	public void run () {
		...
	}
}

Sarà sufficiente creare un “PriorityExecutor” e riempirla con un’istanza di questo thread:

	/* Due thread possono essere in esecuzione contemporanea */
	final PriorityExecutor pool = new PriorityExecutor(2);

	pool.execute( new TestThread(10)	);
	pool.execute( new TestThread(5)	);
	pool.execute( new TestThread(1)	);

Il funzionamento è facile. Ad ogni thread è associata una doppia priorità: quella “nominale”, scelta dall’utente, e quella “attuale” che viene incrementata o decrementata automaticamente per garantire le fairyness. Quando un thread è in esecuzione, ci resta fino alla fine del suo “run“. Una volta terminato, la sua priorità attuale viene decrementata. Una volta che la priorità è scesa a zero, viene rimessa al massimo.
Quindi, se un thread ha priorità doppia rispetto ad un altro, verrà mediamente schedulato il doppio delle volte.
È compito dell’utente inserire nuovamente il thread nella lista se vuole che questo concorra di nuovo all’esecuzione. In tal caso comunque, tutte le strutture dati sono già preparate in modo adeguato per gestire il reinserimento ed i cambiamenti di priorità.
Possiamo ottenere questo effetto con facilità sovrascrivendo il metodo “afterExecute” della classe “FairyFIFOPriorityRunnable“:

	/* Lo rimette in coda */
	@Override
	public void afterExecute (final Throwable t) {
		/* Senza questa riga, il meccanismo di priorità non funzionerà più! */
		super.afterExecute(t);

		/* Si rimette in coda */
		pool.execute(this);
	}

Il pacchetto completo con binari, sorgenti e test può essere scaricato qui: PriorityExecutor .

Posted in java, programming | No Comments »

Premio Web Italia 2010 16 July 2010

Posted in Uncategorized | No Comments »