Babbage e la sua macchina analitica.

Spesso si dá per scontato che tutti i calcolatori siano essenzialmente simili fra loro e di conseguenza si immagina che l'Intelligenza Artificiale (o la mente) corrisponda a un solo schema fondamentale. Al contrario, i calcolatori differiscono in modo notevole l'uno dall'altro, anche nella struttura di base e nell'organizzazione. In questo capitolo esamineremo varie architetture generali, osservandole quel tanto che basta per mettere in luce le particolari caratteristiche di ciascuna di esse. L'obiettivo non é quello di vagliare possibili ipotesi di psiche (non siamo ancora pronti ad affrontare obiettivi cosí elevati), bensí quello di mostrare in quale misura le macchine possono essere diverse l'una dall'altra e di vedere qualche rudimento della teoria sottostante.

A quanto si sa oggi, il calcolatore digitale automatico fu inventato verso il 1623 da un astronomo tedesco pressoché dimenticato, Wilheim Schickard (1592-1635). Dico "a quanto si sa oggi", perché, cosí come fino a poco tempo fa nessuno era a conoscenza dell'invenzione di Schickard, forse sono esistite altre realizzazioni di cui si é persa la notizia.

Il primo calcolatore la cui esistenza divenisse di pubblico dominio fu costruito una ventina d'anni piú tardi, dal filosofo francese Biaise Pascal (1623-62). Il dispositivo suscitó un interesse notevolissimo, nonostante fosse in grado di eseguire soltanto somme e sottrazioni, e, per di piú, in modo alquanto goffo. Come prevedibile, a tempo debito seguirono vari miglioramenti, fra cui soprattutto la possibilitá di eseguire anche la moltiplicazione e la divisione, concretizzatasi negli anni settanta di quello stesso secolo grazie al filosofo tedesco Gottfried Leibniz (1646-1716), ma per un paio di secoli non ci furono importanti progressi.

L'inglese Charics Babbage (1792-1871), il primo informatico che la storia ricordi, fu anche una tipica figura di genio eccentrico, famoso, fra l'altro, per il suo odio ossessivo per i suonatori di organetto. Dopo avere studiato matematica, fu per nove anni professore lucasiano di matematica (tenne cioé la cattedra che era stata di Newton a Cambridge), ma non fece mai realmente lezione, né‚ si spostó da Londra all'universitá. Dotato di somma versatilitá intellettuale e di un pari gusto per l'esplorazione di nuovi campi, diede contributi originali non solo in matematica, ma anche nelle lavorazioni meccaniche di precisione (il suo laboratorio fu tra i migliori d'Europa) e in quella che oggi chiamiamo ricerca operativa (scrisse uno dei primi trattati sistematici sull'argomento). Babbage, peró, é ricordato soprattutto per le sue macchine calcolatrici.

In effetti, progettó due macchine molto diverse. La prima (circa 1823-33), chiamata difference engine, ovvero "macchina alle differenze", non é molto importante, anche se rappresentó sicuramente un'innovazione e fu potenzialmente utile. Furono costruiti molti suoi componenti, furono realizzati addirittura dei prototipi, ma non fu mai effettivamente completata una macchina alle differenze, e questo per vari motivi. In primo luogo, l'elevata precisione delle lavorazioni meccaniche richieste ne rendeva molto costosa la costruzione (ecco dunque la ragione che spinse Babbage ad attrezzare un'officina meccanica di precisione); in secondo luogo, Babbage continuó ad apportare cambiamenti al progetto che richiedevano modifiche e ricostruzioni parziali; in terzo luogo, in un momento non meglio precisato, negli anni intorno al 1833, il suo interesse si rivolse a un progetto piú elegante e di gran lunga piú imponente.

La nuova analytical engine ("macchina analitica") occupó Babbage per il resto della vita e fu il maggiore dei suoi successi. Il progetto incorpora due idee straordinariamente profonde e innovative, che insieme costituiscono il fondamento di tutta l'informatica:

1) il funzionamento é completamente programmabile;

2) i programmi possono contenere salti condizionati.

Come la macchina alle differenze (e per motivi analoghi) anche la macchina analitica non vide mai il completamento, ma fu approntato un migliaio di disegni tecnici, di diagrammi di sincronizzazione e di diagrammi di flusso, insieme con seimila o settemila pagine di note esplicative. Inoltre furono effettivamente costruite molte delle parti componenti, e quando Babbage morí (a 79 anni) era in costruzione un modello effettivo.'

Per molti anni, peró, l'unica descrizione pubblicata della nuova macchina rimase una breve "memoria", che ha a sua volta una storia interessante. Nel 1842, L. F. Menabrea, un ingegnere italiano, pubblicó (in francese, ma su una rivista svizzera) un riassunto di alcune lezioni che Babbage aveva tenuto privatamente a Napoli. L'anno successivo, Ada Augusta, giovane e intelligente allieva di Babbage (e in seguito contessa Lovelace), lo tradusse in inglese, aggiungendo, sotto l'egida del maestro, alcune note esplicative. Queste "note" sono in effetti tre volte piú lunghe e notevolmente piú approfondite dell'articolo originale. L'inventore stesso probabilmente forní parte del materiale, ma sembra certo che Lady Lovelace capisse il lavoro di Babbage meglio di chiunque altro in quel momento; per renderle onore é stato dato il nome "Ada" a un potente linguagoo di programmazione, formulato recentemente.

La macchina analitica ha tre componenti principali: il mill ("mulino" o "tamburo": l'unitá aritmetica di elaborazione), lo store ("magazzino": l'unitá di memoria dei dati) e un'unitá di controllo e di sincronizzazione, a cui Babbage non diede un nome specifico. Gli elementi manipolati dal sistema sono numerali dotati di segno, e il campo di gioco é essenzialmente l'unitá di memoria. L'unitá aritmetica puó eseguire le quattro operazioni aritmetiche fondamentali, sfruttando, per gli operandi e i risultati, qualunque posizione indicata nella memoria. Quindi, usando la nostra terminologia, possiamo pensare all'unitá di elaborazione come a una squadra di quattro "giocatori interni" molto limitati, uno per ciascuna abilitá primitiva. L'unitá di controllo, poi, é il giudice interno, che non manipola in prima persona gli elementi, ma si limita a dire ai giocatori quando e dove mettere in moto i rispettivi talenti: li chiama, cioé, uno alla volta, dicendo con quali numerali debbono lavorare e dove debbono riporre la risposta. Ogni mossa é completamente determinata.

Ma qual é il "'gioco" praticato dalla macchina analitica? quali sono le regole? che cosa determina le istruzioni che il giudice impartisce ai giocatori? Queste domande, in realtá, sono una sola, e la risposta é la chiave di tutta la brillante concezione di Babbage. Entro certi limiti, la macchina analitica giocherá qualunque gioco le si insegni. Cioé, siamo noi a definire le regole (in un modo particolare), e il giudice fará in modo che i giocatori le rispettino. Cosí, semplicemente dando al giudice "definizioni" diverse si puó trasformare la macchina analitica nel sistema formale automatico che si desidera (entro i limiti della macchina).

Questa attivitá, veramente notevole, di creare un sistema automatico specifico semplicemente descrivendolo in modo opportuno entro un sistema di uso generale, si chiama programmazione. É una delle idee piú feconde di tutta la storia della tecnologia, e fu Babbage a inventarla.

Prendiamo per confronto una normale calcolatrice tascabile. Sa eseguire le stesse quattro operazioni, ma bisogna inserire manualmente ogni comando, ogni passo del procedimento. Se vogliamo calcolare l'espressione [ 3 (x + y) - 51, per x e y dati, dobbiamo prima sommare i due dati, poi moltiplicare la loro somma per tre, e infine sottrarre cinque dal prodotto. Se dobbiamo effettuare il calcolo per piú dati, occorre ripetere ogni volta tutta la sequenza, passo per passo. Una calcolatrice tascabile é essenzialmente costituita di quattro dispositivi indipendenti dedicati, ciascuno dei quali sa effettuare una sola operazione; qualunque combinazione o ripetizione di operazioni deve essere realizzata manualmente. Ovviamente si puó costruire una macchina dedicata, piú complessa, in grado di calcolare non la somma o il prodotto di due numeri, ma (poniamo) "tre volte la loro somma meno cinque"; ma sarebbe un'assurditá.

Molto preferibile sarebbe una macchina per cui si potesse definire in precedenza una successione arbitraria qualsiasi di operazioni fondamentali (su variabili qualsiasi predeterminate). Una macchina del genere potrebbe calcolare qualunque formula da,noi voluta, date le istruzioni del caso; e, date quelle istruzioni, si comporterebbe come una macchina dedicata e. personalizzata per quella stessa formula. Sotto ogni aspetto, essa sarebbe quella macchina speciale, finché‚ le istruzioni non fossero cambiate. Come si sará giá capito, questo é proprio il modo in cui funziona la macchina analitica e le "istruzioni" sono il programma.

La seconda grande invenzione incorporata da Babbage nella macchina analitica é il salto condizionato: una direttiva, impartita al giudice, di passare a un'altra parte del programma, a seconda del risultato di una qualche verifica. Abbiamo giá visto l'importanza dei salti condizionati nei nostri algoritmi per la chiave e la serratura; in effetti, i programmi di Babbage sono essenzialmente dei piani con salti condizionati, proprio come i nostri algoritmi. Questi salti sono necessari in molti calcoli numerici, come Babbage ben sapeva (cfr. scheda 20 per un esempio). Il controllo condizionato é cruciale anche in altri manipolatori generali di simboli, compresi quelli che ci interessano nell'intelligenza artificiale.

Nella misura in cui é un sistema formale automatico, la macchina analitica é strettamente indipendente dal sistema con cui é realizzata. Un secolo e mezzo fa, peró, la realizzazione fisica costituiva un ostacolo considerevole, e vale la pena di descrivere brevemente lo straordinario progetto di Babbage. I numerali sono di 40 cifre decimali (non binarie), piú un segno. (Sembra che Babbage avesse molte idee diverse per tenere conto delle frazioni, ma non ne scelse mai una in particolare.) Ogni cifra é rappresentata dalla rotazione di una ruota di ottone, del diametro di qualche centimetro, e le quaranta ruote di ciascun numerale sono montate, a pochi centimetri di distanza l'una dall'altra, su un'asta d'ottone alta circa tre metri.

L'unitá aritmetica era costituita da oltre un centinaio di queste aste, disposte in una configurazione circolare del diametro di un metro e mezzo circa. L'unitá di memoria conteneva un altro centinaio circa di aste, disposte in doppia fila su un lato dell'unitá aritmetica. Il tutto, ovviamente, era completato da un groviglio di leve e arresti, pignoni e innesti, perché, il tutto girasse quando (e solo quando) doveva, e comprendeva sistemi assai sofisticati per evitare l'usura e i giochi. Analisi recenti fanno pensare che i componenti fabbricati nell'officina di Babbage fossero precisi e robusti a sufficienza perché la macchina potesse funzionare. Una volta completato, il tutto doveva avere le dimensioni e il peso di una piccola locomotiva, anche se doveva essere assai piú complicato e costoso.

I programmi della macchina analitica non erano conservati nell'unitá di memoria, ma erano codificati su serie di schede perforate, collegate tra loro da nastri. I nastri permettono alla macchina di tornare indietro per ripetere indefinite volte un gruppo di istruzioni, la qual cosa é essenziale per realizzare cicli. Questa disposizione fondamentale era stata ispirata a Babbage da un sistema usato per comandare i telai Jacquard che producevano i broccati, il che, a sua volta, ispiró a Lady Lovelace una famosa analogia: "Possiamo dire assai opportunamente che la macchina analitica tesse disegni algebrici, cosí come il telaio Jacquard tesse fiori e foglie." E in modo analogo una mente intesse figure simboliche generali, se l'intelligenza artificiale é nel giusto.

Macchine di Turing e universalitá.

Alan Turing (1912-54), matematico inglese al pari di Babbage (ma non altrettanto stravagante), ha un posto di primo piano nella storia dell'informatica per varie ragioni. Abbiamo giá parlato del famoso "test di Turing", da lui proposto nel 1950 in una disamina dell'intelligenza delle macchine destinata ad avere una grande influenza. In precedenza, durante la seconda guerra mondiale e subito dopo, Turing diede contributi fondamentali per lo sviluppo dei primi calcolatori elettronici in Inghilterra.' Cosa ancor piú importante, prima del conflitto (quando in effetti era ancora uno studente diplomato), Turing enunció la prima teoria della computazione matematicamente precisa, in cui sono comprese alcune sorprendenti scoperte sulle possibilitá delle macchine. Per questi risultati teorici fu necessaria l'invenzione di un nuovo tipo di calcolatore (una nuova architettura fondamentale) in cui erano incluse quelle che oggi chiamiamo macchine di Turing. Esiste un'infinitá di (possibili) macchine di Turing specifiche, nessuna delle quali ha un grande significato presa da sola; importanti sono la categoria complessiva di questi dispositivi e i vari teoremi generali che Turing dimostró in proposito.

Prima di proseguire, dobbiamo accennare al fatto che anche Turing, come i suoi predecessori, non costruí mai effettivamente una delle sue macchine; ma nel suo caso i motivi sono del tutto diversi. La macchina analitica di Babbage era straordinariamente grande e complicata, vicino ai limiti di quel che poteva essere capito, per non dire costruito, a quell'epoca. Le macchine di Turing, invece, sono estremamente semplici; inoltre, potrebbero essere arbitrariamente grandi, ma in genere sono abbastanza piccole. Questo contrasto é ovviamente dovuto a una differenza profonda negli obiettivi essenziali. Mentre Babbage voleva che le sue macchine fossero utilizzabili a fini pratici, Turing era interessato solo a problemi teorici astratti e di conseguenza i suoi progetti di macchine permettono descrizioni eleganti e facilitano le dimostrazioni, ma sono del tutto privi di utilizzabilitá pratica. Costruirne una, quindi, sarebbe facile, ma del tutto inutile.

Una macchina di Turing é costituita di due parti: una testina e un nastro. Il nastro é semplicemente un mezzo di archiviazione passivo: é diviso in celle quadrate nel senso della lunghezza, e ciascuna cella puó contenere un elemento (tratto da un alfabeto finito, indicato in precedenza). Si ipotizza che il numero delle celle disponibili sia illimitato, ma che in qualsiasi dato istante sia occupato solo un segmento finito di nastro; tutte le altre celle, cioé, sono vuote o contengono solo uno speciale elemento vuoto. Il nastro é usato anche per l'ingresso e l'uscita: vi si scrivono elementi prima che la macchina parta e poi, quando la macchina si ferma, si legge quel che vi resta.

La testina é la parte attiva della macchina: scorre avanti e indietro lungo il nastro (oppure é il nastro a scorrere avanti e indietro sotto di una cella alla volta, leggendo e scrivendo elementi durante il suo passaggio. Ad ogni passo dato, la testina "esplora" una qualche cella particolare sul nastro, e quella é l'unica cella da cui puó leggere o su

cui puó scrivere, finché non passa a un'altra. Ad ogni passo, inoltre, la testina stessa si trova in un particolare stato interno (che é uno di un repertorio finito di stati indicati in precedenza). Questo stato in genere cambia, nella transizione da un passo al successivo; in condizioni particolari, peró, la testina entra in uno stato speciale di "arresto", nel qual caso la macchina si ferma, lasciando il suo risultato sul nastro.

Ció che la testina fa ad ogni passo é determinato completamente da due fattori:

· gli elementi che incontra nella cella che esplora;

· lo stato interno in cui si trova in quel momento.

Questi due fattori determinano tre conseguenze:

· quale elemento deve essere scritto sulla cella attuale (sostituendo qualunque elemento vi si trovasse in precedenza);

· quale cella esplorare al passo successivo (la stessa, oppure l'adiacente a destra o a sinistra); c) in quale stato interno deve trovarsi la testina al passo successivo (oppure se deve fermarsi).

Quindi, tutto il funzionamento di una macchina di Turing (cioé della testina) puó essere definito in un'unica matrice bidimensionale, dove le righe rappresentano gli elementi che la testina puó incontrare e le colonne rappresentano di stati in cui la testina puó trovarsi. Ogni incrocio della matrice definisce semplicemente le tre azioni appena elencate, determinate dall'elemento e dallo stato.

É facile descrive le macchine di Turing come "GIochi automatici". Il nastro, chiaramente, é il campo di gioco, e gli elementi che si trovano su di esso sono gli elementi del gioco. I vari stati interni corrispondono a giocatori intemi, ciascuno molto limitato. Un giocatore puó leggere l'elemento attuale, e, in funzione di quel che trova, sostituirlo con un altro elemento (dello stesso o di un altro tipo), quindi dire al

giudice di gara come spostare il nastro, e quale sia il giocatore a cui tocca la mossa successiva. Il giudice interno é ancor meno brillante: si limita a dare inizio al gioco con il giocatore 1, poi sposta il nastro e chiama i giocatori come essi richiedono, finché qualcuno dice STOP.

Utilizzando il concetto della macchina di Turing, possiamo descrivere una pietra miliare della storia della matematica, un'idea avanzata in vari modi da Turing e da altri negli anni attorno al 1936. Si ricordi il problema della giocabilitá in modo finito: in un sistema formale, le regole debbono essere tali da poter "essere seguite da giocatori indiscutibilmente finiti". Purtroppo questa condizione é un po' vaga: quindi non é del tutto chiaro quali sistemi o quali regole la soddisfino. Verso la metá degli anni trenta, molti matematici si erano posti il problema, ed erano stati suggeriti numerosi crteri molto diversi fra loro, ciascuno rigoroso e intuitivamente plausibile; inoltre, presto si era stabilito che tutti erano equivalenti sotto l'aspetto teorico, cosicché la plausibilitá di ciascuno rafforzava quella deoi altri. Per di piú, si sono dimostrati equivalenti anche tutti i criteri plausibili proposti dopo di allora

Di conseguenza, virtualmente tutti i matematici accettano la tesi enunciata da Turing e da Alonzo Church, secondo cui tali criteri che si sostengono a vicenda catturano davvero in modo rigoroso l'idea intuitiva di giocabilitá in modo finito.

Ci sono altrettanti modi di formulare questa tesi quanti sono i criteri espliciti; ne abbiamo delineato uno nel nostro esame degli algoritmi. Un'altra formulazione (piú rigorosa) é la seguente:

Tesi di Turing. Per ogni sistema formale automatico deterministico esiste una macchina di Turing ad esso formalmente equivalente.

In altre parole, nessun sistema formale automatico puó fare qualcosa (non a caso) che le macchine di Turing non possano fare; in linea di principio, le macchine di Turing sono gli unici sistemi automatici di cui abbiamo bisogno. Si badi bene che si parla qui di "tesi" (e non di teorema") perché non é qualcosa di dimostrabile: in senso stretto, si tratta di una proposta sul significato reale della frase "sistema formale automatico deterministico" (in particolare della clausola relativa alla "giocabditá in modo finito").

Fin qui non abbiamo parlato di programmazione, ma alcune macchine di Turing possono essere programmate in modo da simularne altre. Il nocciolo dell'idea sta nel codificare una descrizione della macchina di cui si vuole imitare il comportamento e usarla come (parte dell'ingresso per l'imitatrice. Quest'ultima leggerá la descrizione, eseguirá tutte le elaborazioni necessarie e di tanto in tanto (in una parte riservata del suo nastro) fará una mossa esattamente equivalente alla mossa che avrebbe fatto la macchina imitata. (L'equivalenza puó richiedere qualche traslitterazione, ovviamente, se le due macchine non usano lo stesso alfabeto.) La descrizione codificata della prima macchina quindi funziona come programma della seconda.

Supponiamo, per esempio, che il nastro di una certa macchina chiamiamola MAMI - abbia le celle di colore alternativamente rosa e azzurro. (E solo per nostra comoditá: MAMI in sé é cieca ai colori.) Poi codifichiamo la descrizione di qualche altra macchina, che chiameremo BIMBO, in una successione di celle rosa solamente.

Questa descrizione é sostanzialmente la matrice bidimensionale di BIMBO (descritta

in precedenza), disposta su una sola linea, con l'aggiunta di qualche segno di interpunzione per evitare che sorgano confusioni. Pertanto, quel che BIMBO farebbe per ogni stato dato e per ogni elemento letto é elcanato esplicitamente in qualche punto di questa successione sui quadrati rosa di MAMI. Le celle azzurre sono riservate come sostituto del nastro di BIMBO. Ora tutto quel che deve fare MAMI é tener conto delle posizioni successive del nastro di BIMBO e dei suoi stati interni (usa, per farlo, qualche altra cella rosa come blocco per appunti), leggere la cella azzurra corrispondente, consultare l'elenco per trovare la risposta di BIMBO ed eseguirla.

Ovviamente, dobbiamo ancora dimostrare che qualche macchina possa davvero essere una MAMI di questo genere. Turing, peró, fece qualcosa di piú: dimostró che certe macchine di Turing sono SUPER-MAMI, cioé, secondo la sua terminologia meno colloquiale, sono macchine universali:

Dimostrazione di Turing. Esistono macchine di Turing universali che possono imitare, mossa per mossa, qualunque altra macchina di Turing,

Se si ha anche una sola macchina di Turing universale (e una pazienza da certosino), in linea di principio non c'é bisogno di alcuna altra macchna di Turing, qualunque sia l'obiettivo che si vuole raggiungere. Supponiamo infatti che si abbia bisogno di qualche altra macchina di Turing: si puó semplicemente prendere la sua descrizione standard (la matrice), traslitterare l'alfabeto, codificare il tutto per la SUPER-MAMI che si ha a disposizione, e poi prestare attenzione solo alle sue celle azzurre.

Le mosse eseguite su quelle celle sono esattamente le mosse (a meno di traslitterazioni) che l'altra macchina avrebbe fatto sul suo nastro; cosí, in effetti, si ha giá anche l'altra macchina.

Va da sé che la tesi e la dimostrazione di Turing si completano a vicenda. Secondo la prima, le macchine di Turing sono gli unici sistemi formali automatici che occorrono, e, secondo l'altra, occorre solo una macchina di Turing, una macchina universale. Sposiamo tra loro le due idee, e un'unica SUPER-MAMI puó svolgere tutto il lavoro di tutti i possibili sistemi formali automatici (deterministici). Si potrebbe pensare che questi sistemi generali, con la loro potenza, debbano essere molto complicati, ma non é vero. Il loro difetto é che sono lente. La descrizione codificata di una macchina di Turing (per esempio, di BIMBO) in realtá é solo una trascrizione di molte regole primitive in una forma fortemente regolata. MAMI quindi ha bisogno solo di poche capacitá di base, che le permettano di decodificare e seguire

regole arbitrarie in questa forma specifica, e di una grande quantitá di tempo.

Dopo che Turing diede la sua dimostrazione, si é scoperto che esistono molte altre architetture possibili per i sistemi formali universali, compresa, in effetti, anche quella di Babbage. Nel resto di questo capitolo, prenderemo in considerazione tre altre architetture programmabili universali, molto diverse l'una dall'altra (e dalle macchine di Turing), che oggi sono ampiamente usate nella pratica.

L'onnipresente macchina di von Neumann.

John von Neumann (1903-57) nacque e studió in Ungheria, ma si trasferí negli Stati Uniti da giovane,-fatto che puó essere preso a simbolo di molti analoghi trasferimenti che si incontrano nella nostra storia. Fin qui i nostri protagonisti sono sempre stati europei, ma da questo punto in poi saranno americani; inoltre, l'interesse di von Neumann per i calcolatori sbocció piú o meno nello stesso tempo in cui cominció il predominio statunitense in questo campo, fondamentalmente dopo il secondo conflitto mondiale. Tale periodo vide anche la realizzazione pratica dei primi calcolatori non dedicati, risultato al cui raggiumgimento von Neumann (e gli Stati Uniti) hanno dato un contributo notevole.

Infine, quelli furono anche i giorni in cui cominció a crescere a valanga la stessa informatica, prima con decine e presto con centinaia di persone che lavoravano piú o meno di concerto. Di conseguenza, attribuire le singole idee alle singole persone diventa sempre piú difficile.

Babbage, per esempio, fu davvero un eroe solitario, e le sue idee furono soltanto sue; e le macchine di Turing sono l'invenzione di un solo uomo, anche se numerosi sistemi inventati contemporaneamente si rivelarono poi matematicamente equivalenti. Quella che oggi chiamiamo "architettura di von Neumann", invece, si sviluppó nell'arco di alcuni anni, con molti contributi individuali che non sempre sono chiaramente separabili. Questa tendenza diventerá sempre piú evidente con il procedere della nostra storia.

Von Neumann, al pari di molti altri pionieri del calcolatore, aveva studiato matematica, ma, a differenza degli altri, rimase sempre principalmente un matematico. (Anche se riuscí a trovare il tempo per alcuni lavori brillanti e originali nella meccanica quantistica e in economia, come la famosa "teoria dei giochi".) Il suo interessamento per il calcolatore nacque in modo quasi casuale, allorché venne scelto come consulente per il progetto ENIAC, che, all'epoca, era probabilmente il piú grande calcolatore del mondo. Le riflessioni (di von Neumann e di altri) sulle debolezze dell'ENIAC portarono alla costruzione del calcolatore dell'Institute for Advanced Study di Princeton che, sebbene piú piccolo, era piú potente e piú facile da programmare, e che si dimostró un'ottima base per molti progetti successivi.

Una macchina di von Neumann richiede per prima cosa una memoria di grandi dimensioni, a cui si possa accedere in due modi diversi: relativo o assoluto. Accedere alla memoria significa trovare una posizione particolare al suo interno, in modo da poter leggere o sostituire qualunque elemento. I due modi di accesso sono analoghi a due modi di indicare un particolare edificio di una cittá.

L'accesso relativo si ha definendo la nuova posizione in rapporto a quella attuale. Cosí, se si danno indicazioni a una persona non pratica del luogo, spesso ci capita di dire cose come: "Vada avanti due isolati, poi giri a sinistra, ed é il secondo portone alla sua destra." Questo insegna al nostro interiocutore come trovare il luogo cercato partendo dal punto in cui si trova , cioé in modo relativo. Analogamente, nella memoria di un calcolatore, si puó indicare dove si trovi la successiva posizione da utilizzare (per leggere o scrivere) servendosi del suo rapporto con quella che ha appena finito di utilizzare. Per esempio, il nastro di una macchina di Turing é accessibile (solo) in modo relativo: la successiva cella da esplorare é definita sempre in rapporto a quella attuale (é lo stesso portone, o quello adiacente). Si badi che, per l'accesso relativo, le posizioni di memoria debbono essere organizzate in qualche modo regolare (come l'ordinamento lineare di un nastro di Turing) e in ogni momento la macchina deve essere in qualche posizione particolare (per esempio sulla cella che

ha esplorata).

L'accesso assoluto (chiamato anche accesso casuale) consiste nell'indicare una posizione particolare tramite un nome univoco (o un numero).

L'ufficio postale, per esempio, identifica gli edifici mediante un indirizzo univoco (viaManzoni 27, Bergamo); analogamente, le chiamate telefoniche sono instradate in modo assoluto, mediante numeri telefonici univoci. L'accesso assoluto non richiede una struttura organizzata o una posizione "attuale", in quanto ogni possibile obiettivo puó essere raggiunto con sicurezza grazie al suo nome. L'unitá di memoria della macchina analitica di Babbage, per esempio, é accessibile (solo) in modo assoluto: tutte le colonne delle variabili hanno nomi propri (che di fatto sono numerali), ma non esiste fra esse alcuna relazione utilizzabile.

Oltre a essere accessibile in ambedue questi modi, la memoria principale di una macchina di von Neumann é anche usata per due compiti assai diversi e questo é assai importante. In primo luogo, la memoria contiene gli elementi su cui si deve operare: i dati iniziali (se ce ne sono), i valori intermedi, e quindi i risultati finali, pronti per l'uscita. Cosí se il sistema fosse programmato per disporre elenchi in ordine alfabetico, inizialmente in memoria sarebbe caricato l'elenco oriffinale, poi essa conterrebbe gli elenchi parzialmente ordinati, e alla fine l'elenco conclusivo in ordine alfabetico. É come l'unitá di memoria di Babbage, che peró era progettata principalmente per accogliere dati numerici e non permetteva l'accesso relativo. L'accesso relativo é utile se i dati stessi sono strutturati (come nel caso di una lista o di una matrice): la macchina puó recarsi (in modo assoluto) all'inizio dei dati e poi spostarsi fra essi elemento per elemento (in modo relativo).

L'altro uso della memoria principale é quello di contenere il programma che la macchina esegue. I programmi di von Neumann sono piani condizionati, fondamentalmente analoghi a quelli di Babbage, che peró erano codificati su sequenze di schede perforate, anziché essere conservati in memoria insieme con le variabili. Alle schede si poteva accedere (solo) in modo relativo: cioé si poteva andare avanti o indietro nella sequenza di un certo numero di schede (per esempio per i cicli di ripetizione) ma non c'era modo di accedere per nome a una scheda qualunque. Una macchina di von Neumann in genere accede in modo relativo anche al suo programma, o passo per passo seguendo un piano lineare, oppure saltando avanti e indietro di un prescritto numero di passi (nei cicli).

Dove l'architettura di von Neumann mostra davvero la sua superioritá, peró, é nell'uso dell'accesso assoluto per realizzare i sottoprogrammi.

Un sottoprogramma (o subroutine) é un "miniprogramma " che un programma di maggiori dimensioni puó chiamare in qualunque punto del suo svolgimento come se fosse un singolo passo. Supponiamo, per esempio, che il programma principale (un sistema di gestione di documenti, per esempio) debba disporre in ordine alfabetico vari elenchi in momenti diversi. Si puó inserire nel programma una routine di ordinamento alfabetico completa in ciascun punto dove potrebbe essere necessaria; ma si tratterebbe chiaramente di uno spreco. Una strategia migliore é quella di includere solo una copia della routine, in un punto prestabilito, dove possa essere reperita in qualunque momento. Ogni qualvolta il programma deve disporre qualche dato in ordine alfabetico, salta a questo comodo sottoprogramma, dal quale esce poi, a ordinamento concluso, con un altro salto,

L'artificio, ovviamente, sta nei due salti, in particolare nel secondo. Dal momento che il sottoprogramma stesso rimane in una posizione costante (assoluta) ma é chiamato (cioé si salta ad esso) da parti diverse del programma, la cosa piú semplice é chiamarlo con un nome (un indirizzo). Cosa altrettanto importante, la routine, quando é conclusa, deve tornare (sal tare di nuovo) al punto da cui é stata chiamata, in modo che l'esecuzione possa riprendere da dove é stata sospesa. Sorge un problema delicato: come fa il sottoprogramma a sapere dove deve saltare, dato che potrebbe essere stato chiamato da un punto qualunque del programma p. La soluzione sta nell'usare un'altra posizione prestabilita per conservare l'indirizzo di ritorno: allora il programma, ogni qualvolta chiama un sottoprogramma, prima di saltare deposita il suo indirizzo attuale in questa posizione speciale. Quando ha concluso il suo compito, il sottoprogramma automaticamente ricava l'indirizzo del programma da questa posizione prestabilita e lo usa per il salto (assoluto).

La macchina analitica di Babbage non puó utilizzare questa utile tecnica dei sottopr<\s>grammi, per due motivi diversi. In primo luogo, puóaccedere a parti del suo programma (le sequenze di schedé) solo in modo relativo, mentre i salti da sottoprogramma impiegano l'accesso assoluto. In secondo luogo, gli indirizzi di ritorno debbono poter essere diversi in occasioni diverse (perché i sottoprogrammi possono essere chiamati da punti diversi del programma). Questo significa che debbono essere modificabili dalla macchina (devono poter essere riscritti) durante l'esecuzione del programma. Le schede di Babbage invece erano perforate permanentemente: i programmi potevano essere modificati solo perforando nuove schede e collegandole di nuovo fisicamente. Altri sistemi, fra i primi costruiti (per esempio l'ENIAC), erano simili alla macchina di Babbage sotto questo aspetto. Una macchina di von Neumann invece puó leggere, scrivere e usare indirizzi (non solo dati) che sono archiviati nella memoria e che, in quanto tali, sono modificabili facilmente dalla macchina stessa mentre il programma é in esecuzione. Di conseguenza, le chiamate assolute a sottoprogrammi (e i relativi ritorni dai sottoprogrammi) sono facilmente realizzabili: in effetti questo é il principale progresso architettonico del progetto di von Neumann. Quando si descrivono le macchine di Babbage e di Turing come giochi formali automatici, d ruolo del giudice interno é piuttosto limitato. Le macchine di von Neumann invece hanno una struttura piú complessa e pertanto il ffiudice ha compiti piú importanti, consistenti nel dire ai giocatori interni a chi tocca muovere e quali sono gli elementi con cui possono giocare, cioé quali sono le operazioni primitive da eseguire e su che cosa debbono essere eseguite. Poiché le direttive di salto (comprese le chiamate a sottoprogrammi e i relativi ritorni) controllano il flusso dell'esecuzione, esse rientrano nel campo del giudice. In altre parole, i salti non sono operazioni (manipolazioni di elementi) eseguite dai locatori, ma scostamenti che d ffiudice compie nel determinare quale giocatore chiamare. In questi tennini, quindi, é compito del giudice tenere conto di tutte le chiamate a sottoprogrammi e di tutti i ritorni perchél'esecuzione riprenda dal punto in cui era stata lasciata; pertanto l'archivio speciale dell'indirizzo di ritorno (la "catasta") in effetti é una piccola memoria privata che appartiene esclusivamente al giudice.

I sottoprogrammi sono importanti non solo perché svolgono il loro compito in modo efficace, ma anche perché permettono una maggiore modularitá dei programmi. Cioé, una volta che si é scritto un sottoprogramma per un compito particolare e lo si é "messo a punto" (corretto in modo che funzioni perfettamente), lo si puó usare in qualunque momento senza ulteriori ritocchi. Il risultato é che il problema di scrivere un programma di grandi dimensioni, composto principalmente di un gran numero di sottoprogrammi diversi, puó essere articolato in molti sottoproblemi piú piccoli e meglio affrontabili, facendo fare quindi ai vari sottoprogrammi separatamente quel che devono fare. Inoltre, una volta che sono stati scritti e messi a punto per un programma, i sottoprogrammi possono essere presi in blocco per essere usati in altri programmi, senza che sia necessario perdere tempo a scriverli e metterli a punto di nuovo.

Quest'idea sta a sua volta alla base di un'altra, che é forse la spina dorsale di tutta la programmazione moderna: le macchine di livello superiore (i cosiddetti "linguaggi di programmazione"). Si puó raccogliere insieme una serie di sottoprogrammi di larga utilitá, formando una sorta di "biblioteca" da cui ogni programmatore puó in seguito ricavare ció che gli serve: si risparmia molto lavoro. Poi tutto quello che serve é un bibliotecario automatico che si occupi delle chiamate e di altri compiti di gestione della biblioteca, e i sottoprogrammi stessi vengono a corrispondere a nuove operazioni primitive, ciascuna delle quali puó essere chiamata con un'unica istruzione (diventano nuovi "giocatori" in un gioco piú vasto). In effetti si ha un nuovo calcolatore, piú potente. Questa é la sostanza di sistemi familiari come il Basic, il Pascal, il Fortran, il Cobol ecc.

Queste particolari macchine virtuali (i linguaggi) sono tutte approssimativamente di von Neumann, per quanto riguarda l'architettura: i loro programmi sono tutti piani con salti condizionati, con cicli, con sottoprogrammi chiamati per nome e via dicendo. Ma questa é solo una coincidenza. Infatti, sarebbe ugualmente possibile scrivere sottoprogrammi e bibliotecari-giudici che dessero alla nuova macchina un'architettura molto diversa. Per esempio, si potrebbe facilmente scrivere un programma per una macchina di von Neumann che simulasse esattamente una macchina di Babbage o di Turing. A quel punto, a tutti i fini pratici, la macchina simulata sarebbe quella per cui si lavora (scrivendo programmi per essa ecc.), se, per qualche motivo strano, lo si volesse fare. É recisamente la situazione che abbiamo incontrato in precedenza con le macchine SUPER-MAMI di Turing: in effetti anche le macchine di von Neumann (con una memoria illimitata) sono macchine universali, nello stesso identico senso in cui lo sono alcune delle macchine di Turing.

L'universalitá di von Neumann, peró, é di gran lunga piú importante (nel mondo reale) dell'universalitá di Turing. Per prima cosa, le macchine di von Neumann sono molto piú facili da programmare; per seconda cosa, sono molto piú veloci (non debbono cercare avanti e indietro lungo il nastro, una cella alla volta). Inoltre, le architetture di von Neumann possono essere costruite facilmente con componenti elettronici molto semplici. Qui il confronto é meno con le macchine di Turing (che sono estremamente facili da costruire) che con altre architetture universali che, sebbene facili da programmare e abbastanza veloci, sono difficili da realizzare. La conclusione é che praticamente tutti i calcolatori (programmabili) attualmente in produzione hanno, a livello di struttura fisica, un'architettura che é fondamentalmente quella di von Neumann.

Nei prossimi due paragrafi prenderemo in considerazione due architetture molto diverse che sono assai usate nella ricerca di intelligenza

Teoricamente, com'é ovvio, non é importante come siano costruite o realizzate, purché compiano sempre mosse lecite in posizioni lecite (ancora l'indipendenza dal mezzo); ma puó essere interessante ricordare che (almeno al momento) sono tutte simulate su SUPER-MAMI di von Neumann.

Scheda di approfondimento: La catasta dell'indirizzo di ritorno

Il problema del ritorno da un sottoprogramma é piú complesso di quel che possa sembrare. Innanzitutto, se c'é solo una posizione predisposta per archiviare l'indirizzo

di ritorno, si puó chiamare un solo sottoprogramma alla volta; in particolare, un sottoprogramma non potrebbe chiamare a sua volta un ulteriore "sotto-sottoprogramma il che invece spesso risulterebbe molto comodo. Una soluzione parziale (ed era il metodo comune ai tempi di von Neumann) consiste nel riservare una posizione distinta per l'indirizzo di ritorno di ciascun sottoprogramma; poi ciascuno puó trovare la sua strada di ritorno indipendentemente dagli altri.

É ancora una soluzione limitante, peró, perché ogni dato sottoprogramma puó essere chiamato ancora solo una volta; cioé, un sottoprogramma non puó chiamare sé stesso come sotto-sottoprogramma. (Puó sembrare un'idea bizzarra, ma in realtá é cosa fattibile e utile: si veda la discussione della ricorsione nel prossimo paragrafo.) Una soluzione generale del problema (inventata alla metá degli anni cinquanta da Newell e Shaw) sta nell'uso di un tipo particolare di memoria, cui si dá il nome di stack, pila o catasta.

Si tratta di una memoria del tipo "ultimo dentro, primo fuori" (LIFO), come una pila

di corrispondenza sulla scrivania, a cui si acceda solo dalla cima. Cosí, ogni volta che si riceve una lettera a cui si deve rispondere, la si mette in cima alla pila; e ogni volta che si ha il tempo di scrivere una risposta, si prendono le lettere dalla cima della pila. Per la corrispondenza non é un metodo splendido, perché il poveretto che ha scritto per primo riceve una risposta per ultimo; per i ritorni dai sottoprogrammi, peró, ha un pregio importante.

Ecco com'e funziona. Ogni qualvolta una parte del programma chiama un sottoprogramma, innanzitutto pone l'indirizzo di ritorno in cima alla catasta, poi salta. Ogni qualvolta un sottoprogramma finisce il suo compito, recupera l'indirizzo che si trova in cima alla catasta e ritorna a quel punto. Il risultato é che qualunque sottoprogramma torna automaticamente alla chiamata piú recente a cui non sia stata ancora data una risposta. Poiché ogni indirizzo di ritorno é tolto dalla catasta quando é usato, l'indirizzo di ritorno che resta in cima (se ce n'é ancora almeno uno) é automaticamente quello che vi é stato depositato per il sottoprogramma che ha chiamato il sottosottoprogramma che ha appena finito d suo compito. Cosí le chiamate a sottoprogrammi possono essere annidate (sottoprogrammi che chiamano sotto-sottoprogrammi e via di questo passo) arbitrariamente e senza restrizioni. (Si noti che la memoria a catasta usa a sua volta un tipo particolare di accesso relativo.)

Il LISP di McCartby.

Nella nostra rassegna degli architetti del calcolatore, John McCarthy (nato nel 1927) é il primo che sia nato in America e l'ultimo che abbia compiuto studi di matematica. Professionalmente, peró, i suoi interessi si concentrarono presto sugli automi di calcolo, e nel 1956 aveva giá coniato il termine "intelligenza artificiale" e organizzato il primo convegno scientifico del neonato campo di ricerca. Nel 1958, con Marvin Minsky, fondó d laboratorio di IA del MIT e nel 1963 ne organizzó un altro a Stanford: tutti e due oggi sono centri mondiali della ricerca in IA. Nel frattempo ha sviluppato anche i primi sistemi operativi "a partizione di tempo" (quella disposizione ingegnosa, é oggi ormai comune, grazie alla quale un unico calcolatore centrale puó servire contemporaneamente molti utenti indipendenti.

Il nostro interesse, peró, va all'invenzione, da parte di McCarthy, nel 1959, di un tipo del tutto nuovo di calcolatore, chiamato LISP.

Le macchine di McCarthy (potremmo chiamare cosí i sistemi LISP) hanno una struttura semplice ed elegante, notevolmente flessibile e al tempo stesso assai diversa da quella delle macchine di Turing o di von Neumann. Rispetto ai suoi predecessori, il LISP si distingue per due aspetti principali: la sua organizzazione di memoria e la sua struttura di controllo. Né l'una né l'altra sono particolarmente difficili da capire, ma sono abbastanza caratteristiche perché valga la pena di dedicare loro un po' di spazio.

Memoria. Immaginiamo di avere una lunga fila di tazzine legate a una corda in modo da formare una catena, e una buona scorta di simboli (per esempio, di elementi atomici) da mettere nelle tazzine, uno per tazzina. Ovviamente si tratta di un dispositivo di "memoria". Funziona come un nastro di macchina di Turing, se ipotizziamo che le tazzine possano essere indicate solo in base alla loro posizione relativa e che la testina possa spostarsi lungo la catena solo di una tazzina alla

volta. Invece, se ogni tazzina ha anche un'etichetta univoca (un "indirizzo") e se l'elaboratore puó saltare in un unico passo a qualunque distanza, abbiamo una memoria di von Neumann. Si noti che in tutti e due i casi la memoria é organizzata sempre nello stesso modo, e la differenza sta nell'ulteriore modalitá di accesso possibile per la macchina di von Neumann; in particolare, la struttura é sempre:

· lineare: la catena non ha biforcazioni o incroci;

· unitaria: c'é solo una catena;

· fissata in anticipo: la catena é sempre uguale.

Queste caratteristiche strutturali sono essenziali per la memoria di un calcolatore? Niente affatto. Si immagini, al posto delle tazzine, un'enorme quantitá di connettori a Y, ammucchiati a caso. Un connettore a Y é un dispositivo a forma di forcella, con una base o spina a un'estremitá e due prese, che tra loro formano un angolo, all'altra estremitá. Un tipo comune di questi connettori permette di mettere due lampadine in un unico portalampade; ce ne sono di molti altri tipi, per collegare canne per innaffiare, cavi elettrici e via elencando. Il punto importante é che la base di un connettore a Y puó essere inserita o avvitata sulla presa di un altro; e questo processo puó continuare finché si vuole, costruendo curiosi alberi di connettori . Ogni albero avrá una base libera al fondo (la sua radice) e un numero qualunque di prese libere alla cima oppure annidate lungo i suoi rami. A questo punto basta immaginare che ci siano etichette alle radici di tutti gli alberi e simboli atomici infilati in tutte le prese libere (come "foglie") e si ha l'idea di base della memoria LISP.

I connettori a Y (sdoppiatori) in un albero LISP sono chiamati nodi. Anche gli elementi atomici situati nelle prese terminali dell'albero sono nodi (e specificamente nodi terminali); in effetti, un elemento atomico da solo puó costituire un albero a un solo nodo (come un virgulto, con una foglia e senza rami). In un albero LISP, le prese non possono mai essere vuote, ma esiste un elemento atomico speciale, NIL, che funge da "vuoto" o "nulla", utilizzabile quando é necessario. La realtá non corrisponde alla nostra analogia in un punto importante: i nodi LISP non sono simmetrici, poiché i rami (le prese) sono indicati esplicitamente come "sinistro" e "destro". Pertanto, un nodo qualunque in un albero qualunque puó essere definito mediante una combinazione di accesso assoluto e relativo: prima il nome dell'albero, e quindi un percorso (una successione di svolte a sinistra e a destra) che porti dalla radice a quel nodo.

La distinzione fra rami sinistri e destri permette anche di definire le liste come alberi speciali costruiti come segue: si prendono tanti connettori a Y quanti sono gli elementi da inserire nella lista, li si dispone in fila e si inserisce la base di ciascuno nella presa destra del predecessore, si infilano gli elementi della lista nelle prese sinistre (nell'ordine, partendo dalla base) e infine si inserisce NIL nell'ultima presa destra.

Le differenze rispetto alle memorie a catene di tazzine sono notevoli. Gli alberi LISP chiaramente non sono lineari (benché le liste possano rappresentare strutture lineari, se necessario). Inoltre, poiché in uno stesso momento possono essere attivi molti alberi, neanche la struttura complessiva é unitaria. Ma, e questa é la cosa piú importante, le "forme" degli alberi LISP non sono fissate in anticipo: essi sono costruiti secondo necessitá (e ributtati nel mucchio quando non servono piú). Ne derivano due conseguenze, sottili ma significative.

In primo luogo, poiché gli alberi non sono tutti della stessa forma ma variano di caso in caso, le forme stesse devono far parte di quello che il sistema "ricorda". Quindi le memorie a catene di tazzine conservano solo il contenuto delle tazzine, mentre gli alberi LISP conservano non solo i loro elementi terminali, ma anche i particolari collegamenti fra tutti i nodi. Ne segue che sono particolarmente utili quando si deve tenere conto di relazioni strutturali complesse.

In secondo luogo, poiché gli alberi sono costruiti su misura, secondo la necessitá, durante l'esecuzione del programma, non c'é bisogno di sapere in anticipo esattamente la loro forma o la loro dimensione; questi particolari possono essere affrontati e risolti al momento, in funzione di come si sviluppa la situazione. Ne segue che i programmi LISP possono essere straordinariamente flessibili nella loro risposta a condizioni molto diverse fra loro.

Controllo. Per spiegare la particolare struttura di controllo del LISP, dobbiamo passare a un'altra analogia. Controllare vuol dire stabilire chi fa che cosa e quando lo fa. Prendiamo ad esempio la prima colazione: succo d'arancia ghiacciato e due uova all'occhio di bue.

Qui il problema

non sono le capacitá culinarie di base (i "cuochi primitivi"), ma il modo in cui possono essere organizzate. In altre parole, siamo interessati soprattutto al capocuoco, il giudice di gara della cucina. Nella cucina di vonNeumann, il giudice chiama gli specialisti secondo un certo piano:

ARANCIA

SPREMERE quell'arancia;

METTERE IN FRIGORIFERO il succo;

UOVO

UOVO

ROMPERE quelle uova;

PADELLA

FRIGGERE le uova rotte nella padella;

SERVIRE il succo ghiacciato e le uova fritte.

Le lettere maiuscole indicano gli specialisti da chiamare: la prima riga attiva ARANCIA, lo specialista nel procurare arance; la seconda poi chiama SPREMERE, specialista nella preparazione di spremute, perché svolga la sua attivitá caratteristica (qualunque sia l'ARANCIA su cui deve esercitarla); e via di questo passo. Si osservi che il procedimento é fondamentalmente lineare, e che l'ordine riflette la prioritá nel tempo.

Che cosa succede nella cucina di McCarthy? Sono eseguite le stesse azioni primitive, e nello stesso ordine; ma sono disposte, per cosí dire, a partire dall'estremitá opposta. Il giudice di McCarthy parte sempre da un risultato richiesto e procede a ritroso verso i prerequisiti. Cosí comincia chiedendo a SERVIRE di servire succo d'arancia ghiacciato e due uova all'occhio di bue, quindi aspetta di vedere se SERVIRE ha bisogno di qualcosa. E cosí é: ha bisogno per l'esattezza di succo d'arancia, proveniente da METTERE IN FRIGORIFERO, e di due uova, provenienti da FRIGGERE. Dunque accetta questi come nuovi requisiti (sussidiari) e chiama METTRE IN FRIGORIFERO e FRIGGERE, quindi aspetta nuovamente per vedere di che cosa hanno bisogno (in questo caso, arancia da SPREMERE, uova da ROMPERE ecc.) Fin qui non si fa altro che passarsi gli ordini l'uno con l'altro e non succede in realtá nulla. Ma quando (su richiesta di SPREMERE) é finalmente chiamato ARANCIA, la trasmissione di ordini termina: ARANCIA é un semplice magazziniere che non ha bisogno di ulteriori preparativi: si limita a prendere un'arancia e a passarla. Quando questo succede, peró, il giudice puó cominciare a soddisfare richieste precedenti: ricordando chi voleva l'arancia, la dá a SPREMERE, che ora puó svolgere la sua attivitá e restituire succo d'arancia. Poi, ricordando chi voleva il succo, lo passa a METTERE IN FRIGORIFERO, e via di questo passo, finché SERVIRE ha tutto ció che aveva richiesto e puó portare al COMMITTENTE la prima colazione. Questa é l'essenza del controllo LISP.

Esempio: Un procedimento LISP.

METTERE IN

FRIGORIFERO SPREMERE ARANCIA

SERVIRE UOVO

ROMPERE

UOVO

FRIGGERE

PADELLA

Si badi che la struttura fondamentalmente non é lineare, ma gerarchica, e che l'ordinamento principale non é in base al tempo, ma in base a risultati e prerequisiti: quando uno specialista é chiamato al lavoro, non puó consegnare il suo prodotto senza prima chiamarne al lavoro altri che gli preparino i materiali. Il procedimento si rappresenta meglio in due dimensioni (Esempio precedente).

Nell'esempio, l'ordine di chiamata al lavoro é da sinistra verso destra, mentre l'ordine di consegna é da destra verso sinistra; l'incolonnamento verticale si limita a elencare i preparatori impegnati, quando sono piú di uno.

Nella terminologia matematica, gli specialisti che interagiscono in questo modo sono chiamati funzioni, i loro prerequisiti (se esistono) sono chiamati argomenti, e i risultati sono chiamati valori. Le funzioni che non hanno argomenti sono costanti: danno sempre lo stesso valore. Per i matematici, gli argomenti e i valori delle funzioni possono essere qualsiasi, purché sia soddisfatta la seguente condizione essenziale:

Funzioni. Per ogni argomento permesso (o per ogni combinazione di argomenti permessa) esiste un unico valore (assegnato permanentemente).

Per esempio, MADRE[xl é una funzione perfettamente accettabile (con persone come argomenti) perché ogni persona ha esattamente una madre (che é sempre quella). ZIO[xl invece non é una funzione accettabile, perché alcuni non hanno zii e altri ne hanno molti. Le primitive (e i programmi) LISP sono funzioni, ma si differenziano dai loro corrispettivi matematici per due aspetti fondamentali: sono giocatori attivi che valutano automaticamente sé stessi quando sono chiamati, e i loro argomenti e valori (non interpretati) debbono sempre essere alberi LISP.

Ogni qualvolta una funzione LISP prende un argomento, dá come assunto che sia effettivamente definito attraverso un'altra funzione, che pertanto deve essere valutata per prima. Nella cucina abbiamo chiamato "passare l'ordine" questo processo, ma un esempio illustrerá meglio che cosa succede in realtá:

LAQUARTALETTERADELLA[PRIMAPAROLADELTITOLODI QUESTO LIBRO]]

Qual é il valore di questa funzione per questo argomento? L'argomento é:

PRIMA PAROLA DEL (TITOLO DI QUESTO LIBRO]

la sua quarta lettera, "M"? No, perché l'argomento effettivo non é quell'espressione, ma ció che specifica: nella fattispecie, il valore della funzione PRIMAPAROLADELI[]

quando sia applicata all'argomento:

TITOLODIQUESTOLIBRO

Allora la parola é 'I'ITOLO (e la quarta lettera "0")? No, per la stessa ragione: anche TITOLODIQUESTOLIBRO é una funzione, che specifica un valore. Fortunatamente, peró, é una funzione costante, senza argomenti. Quindi, a differenza di quel che é successo con le prime due funzioni, questa puó essere valutata direttamente, senza valutare prima nient'altro. (La quarta lettera della prima parola del suo valore é "h".)

Come si programma una macchina LISP? Certo non scrivendo un piano sequenziale, come si faceva con una macchina di von Neumann, bensí definendo nuove funzioni mediante altre funzioni giá definite. L'idea ci é giá nota dall'algebra; il quadrato di un numero, per esempio, puó essere definito sotto forma di moltiplicazione:

QUADRATO[x] = def PRODOTTO[x, x]

Oppure, per tornare alla nostra cucina, si potrebbe definire una funzione COLAZIONE in termini di SERVIRE, FRIGGERE, PADELLA ecc. Le funzioni definite sono specialisti di "gestione": come tutte le funzioni, danno i valori di argomenti dati, ma arrivano a questo risultato semplicemente dicendo al giudice chi deve chiamare, senza apportare alcun (altro) contributo proprio. Ovviamente, non tutte le funzioni possono essere definite in termini di altre: debbono esistere alcune funzioni primitive con cui si possa cominciare. I sistemi LISP reali offrono grandi quantitá di primitive comode, comprese molte funzioni (che vengono interpretate naturalmente come) aritmetiche standard ecc. Un LISP ridotto all'osso, da cui si puó costruire tutto il resto, comprende peró solo sei funzioni primitive:

CAR[x] CDR[xl CONS[x, y]

EQ[x, y] ATOM[x] IF[x, y,z]

Ciascuna di queste funzioni prende come argomenti solo alberi LISP e restituisce come valori solo alberi LISP (si ricordi che i singoli elementi atomici sono considerati "germogli" di alberi). Con queste primitive é possibile manipolare (costruire, modificare, distruggere) alberi LISP di complessitá qualunque, in qualsiasi modo algoritmicamente definibile; quindi é possibile definire un'unica funzione complessa che restituisca come valore una qualunque trasformazione di questo genere, per qualsiasi argomento. Il LISP pertanto é universale.

Le prime tre primitive sono usate per montare e smontare alberi qualsiasi. Il valore di CAR[X] é la cosa che é infilata nella presa sinistra del connettore a Y che si trova alla base (del valore) di x: dá cioé la metá sinistra del suo argomento. Se l'argomento non ha una metá sinistra (perché é solo un germoglio atomico), CAR[x] comunica un errore e si ferma. CDR[xl fa lo stesso, ma con la metá destra. CONSlx, y] prende

due argomenti e li concatena: piú precisamente, prende un nuovo connettore a Y, inserisce i (valori dei) due argomenti, primo e secondo, rispettivamente nella presa sinistra e destra, e dá come valore il nuovo albero cosí costruito.

Le altre tre funzioni costituiscono le alternative LISP al controllo e al salto. EQ[x, y] dá come risultato l'elemento speciale TRUE (vero) se i (valori dei) suoi due argomenti sono uguali; altrimenti dá valore FALSE.

ATOM[x] dá TRUE se il (valore del) suo argomento é un singolo elemento atomico; altrimenti dá FALSE.

IF[x, y, z] puó risultare piú chiara se la scriviamo come

IF[x, (THEN)y, (ELSE)zI

ossia:

SE[x, (ALLORA)y, (ALTRIMENTI)z

perché dá il valore del suo secondo o terzo argomento, a seconda che il (valore del) primo argomento sia TRUE o FALSE. Quindi IF[-, -, -] non fa "saltare" il LISP a parti diverse di un piano di istruzioni (non esiste un siffatto piano in cui saltare da una parte all'altra), bensí determina quale funzione debba essere valutata chiedendo al giudice il valore del suo secondo o del suo terzo a mento (ma non di tutti e due).

LISP si distingue per la sua organizzazione di memoria dinamica, ad albero, e per il suo schema di controllo ad applicazione di funzioni, due caratteristiche peraltro strettamente collegate fra loro a formare un'unitá interna: la struttura gerarchica, di funzioni applicate ad argomenti che sono a loro volta funzioni ecc., é essenzialmente un albero. Piú specificamente, LISP rappresenta le funzioni con i loro argomenti come liste, con il nome della funzione come primo elemento della lista e gli argomenti che seguono in ordine. Poiché questi argomenti sono a loro volta chiamate di funzioni, anch'essi saranno rappresentati come liste, e via di questo passo, cosicché la struttura complessiva appare come una lista di liste di liste... e cioé un albero. In altre parole, i programmi LISP e le unitá di memoria LISP ("strutture di dati") hanno esattamente la stessa forma.

I sistemi di produzione di Newell.

Allen Newell (nato nel 1927) si proponeva di occuparsi di matematica, ma poi cambió idea. La Rand Corporation, un "serbatoio di cervelli" di altissimo livello in California, gli apparve molto piú affascinante dell'Universitá del New Jersey, e vi si trasferí. Vi incontró Cliff Shaw, lungimirante pioniere dell'informatica (che era entrato alla Rand nello stesso anno, il 1950) e Herbert Simon, stella nascente dell'economia e della scienza manageriale (in visita dal Carnegie Institute of Technology nell'estate del 1952). Nel periodo fra il 1952 e il 1955, i tre inventarono i manipolatori generali di simboli, la ricerca euristica e l'intelligenza artificiale. Solo negli anni sessanta, peró, dopo che Simon lo riportó nel mondo accademico, Newell cominció a pensare ai sistemi di produzione, particolari calcolatori che si potrebbero chiamare "macchine di Newell"."

In un sistema di produzione, i giocatori attivi (i cuochi della cucina di Newell) si chiamano produzioni. Come i loro corrispettivi di Turing e di von Neurbann (ma diversamente dalle funzioni LISP) tutte le produzioni operano su una memoria lineare comune, chiamata spazio di lavoro. Si differenziano peró dalle loro controparti per il modo in cui determinano chi lavora, dove e quando. Ogni cuoco di Newell passa in rassegna costantemente tutto lo spazio di lavoro, alla ricerca di una determinata configurazione di ingredienti predeterminati; ogni qualvolta trova la sua particolare configurazione, la raggiunge e prepara la sua specialitá (con quegli ingredienti). Per esempio, un esperto poco abile puó cercare esclusivamente mezzo litro di panna da montare, con vicino un frullino e un recipiente refrigerato. Finché queste cose non compaiono, non fa nulla, ma appena si presentano, scatta, monta la panna nel recipiente e poi mette da parte il frullino. La maggior parte di queste azioni puó modificare le configurazioni presenti nello spazio di lavoro, che poi magari possono "soddisfare" qualche altro specialista, per esempio il decoratore di torte, che stava aspettando pazientemente una ciotola di panna montata. E cosí il processo continua.

Due cose sono da notare, a proposito di questa procedura. In primo luogo, le posizioni nello spazio di lavoro non sono definite né in modo assoluto (per "nome") né in modo relativo (come passare da una all'altra); invece, sono identificate in base ai loro contenuti, cioé in termini di ció che vi é conservato in quel momento. Se dunque il paradigma dell'accesso assoluto é un indirizzo cittadino (via Manzoni 2 7) e quello dell'accesso relativo é un'indicazione di percorso (sei isolati a nord, poi due a est), il paradigma dell'accesso basato sui contenuti sarebbe una descrizione della destinazione: trova un edificio in mattoni gialli, al seminterrato e con le tendine rosa alle finestre, dovunque sia. In un sistema di produzione, ovviamente, questi contenuti descritti altro non sono che le configurazioni che i vari specialisti cercano.

In secondo luogo, nessuno dice alle produzioni quando devono operare: aspettano finché le condizioni non siano mature, poi si attivano da sole. I cuochi delle altre cucine invece si limitano a eseguire ordini: le unitá di Turing sono chiamate al lavoro dai loro predecessori, le operazioni di von Neumann sono totalmente prestabilite, e le funzioni LISP sono chiamate da altre funzioni. li lavoro di gruppo di un sistema di produzione fa pensare piuttosto al laissez-faire: ogni produzione agisce

di propria iniziativa, quando e dove sono soddisfatte le sue specifiche condizioni. Non c'é un controllo centrale, e le singole produzioni non interagiscono mai direttamente. Tutte le comunicazioni e tutti gli influssi hanno luogo attraverso configurazioni dello spazio di lavoro comune, come avvisi rivolti in modo anonimo "a tutti gli interessati" in una bacheca situata in luogo aperto al pubblico. Corrispondentemente, una direzione complessiva emerge solo come effetto generale di molte decisioni indipendenti: il che ricorda un po' il libero mercato, guidato dalla ``mano invisibile" di cui parlava Adam Smith.

I lettori piú attenti avranno notato probabilmente un paio di punti poco chiari. Che cosa succede, per esempio, se due produzioni vedono contemporaneamente soddisfarsi le loro condizioni? Supponendo che non possano agire in uno stesso momento, é necessaria una procedura di arbitrato (un giudice). La soluzione piú semplice é quella di attribuire un ordine ai giocatori e di scegliere sempre il candidato con la prioritá piú alta. Possiamo immaginare che siano disposti tutti in fila: il primo controlla se sia presente la sua configurazione e, se puó, agisce; se il primo non puó agire, comincia la sua verifica il secondo, e cosí via. Quando una produzione é stata soddisfatta e ha agito, si ricomincia di nuovo dall'inizio della fila. Analogamente, che cosa accade se, nello spazio di lavoro, la configurazione richiesta da un certo cuoco é presente due volte? Quale dovrá usare? Anche in questo caso la soluzione piu semplice é un ordinamento per prioritá: per esempio, le produzioni potrebbero sempre esplorare lo spazio di lavoro da sinistra verso destra, fermandosi non appena trovano una configurazione soddisfacente."

Come si "programma" un sistema di produzione? Costruendo (definendo) produzioni; le produzioni sono il programma. Un sistema di produzione non programmato é formato solamente da uno spazio di lavoro vuoto, un giudice e un repertorio di primitive, che si possono usare per costruire produzioni. li compito del programmatore é quello di assembiare un insieme di produzioni (ciascuna delle quali sía in grado di eseguire una determinata azione in determinate circostanze) d cui comportamento collettivo sar<\`> quello del sistema desiderato. Le "primitive" del repertorio corrispondono all'incirca alle operazioni primitive di von Neumann o alle funzioni primitive del LISP, ma il modo in cui sono montate a formare un sistema composito é del tutto diverso.

Ogni produzione ha due parti fondamentali: una condizione e un'azione. La definizione di una produzione é essenzialmente una regola (imperativa) che dice:

OGNI QUALVOLTA (condizione) É SODDISFATTA,

ESEGUI (azione)

o, in modo piú schematico:

(condizione) --> (azione)

La condizione é una configurazione che puó presentarsi nello spazio di lavoro, e l'azione é di solito una qualche modifica di tale configurazione (ma a volte é un risultato in uscita). Le capacitá primitive richieste sono quindi vari tipi di riconoscimento di forme e la Possibilitá di modificare le configurazioni riconosciute.

Per esempio, un sistema che abbia il compito di semplificare equazioni algebriche potrebbe contenere una regola come questa:

``A + B = C + D'' --> sostituisci con: "A = C"

Qui le virgolette evidenziano il contenuto dello spazio di lavoro stesso e le lettere maiuscole (A, B, C) devono essere intese come segnaposto per stringhe arbitrarie di effettivi elementi dello spazio di lavoro; pertanto l'equazione

2 x + 4y(z - 14) = w - 3 + 4y(z - 14)

verrebbe semplificata in

2x = w- 3

con un'unica applicazione della regola. Questo esempio presuppone elevate capacitá di riconoscere le classi e di metterle in corrispondenza fra loro: per esempio, la capacita di mettere in corrispondenza l'espressione complessa "4y(z - 14)" e ``B" in ambo i membri dell'equazione. Questi strumenti sono peró comuni nei sistemi di produzione e, grazie ad essi, molte produzioni utili (comprese altre semplificazioni algebriche) sono facili da progettare e facili da capire.

In un certo senso, le macchine di Newell ci riportano alle macchine di Turing. Infatti, a differenza di quel che accade nelle macchine LISP o in quelle di von Neumann, le macchine di Turing e Newell non usano un "IF..." esplicito, bensí hanno la condizionalizzazione incorporata nell'architettura stessa: ogni passo é condizionale. Cosí, il successore di una unitá di Turing dipende sempre dall'elemento che quell'unitá trova sul nastro; analogamente, una produzione si autoattiva solo a condizione che trovi la sua configurazione speciale nello spazio di lavoro.

Si puó vedere la cosa anche sotto forma di sequenze: le macchine di von Neumann e quelle di McCarthy non hanno bisogno di prendere una decisione ad ogni passo, perché hanno un ordine "naturale" di esecuzione "innato". Una macchina di von Neumann segue automaticamente il suo piano, e il LISP valuta automaticamente gli argomenti di ogni funzione prima di valutare la funzione stessa. I salti condizionati quindi sono necessari solo di tanto in tanto, per ridirigere il flusso in certi punti critici. Le macchine di Turing e di Newell, invece, non hanno un flusso predisposto, e pertanto ad ogni passo deve essere presa una decisione esplicita.

Le macchine di Newell peró sono ben lontane dall'essere semplicemente una rispolveratura delle macchine di Turing: lo spirito con cui sono state proposte é del tutto diverso. L'obiettivo di Turing era quello di rendere la macchina in sé quanto piú semplice possibile (pochissime unitá primitive, che agiscono solo su elementi atomici), senza preoccuparsi poi se i programmi erano lunghi e noiosi. I sistemi di produzione, invece, tendono ad avere "primitive" molto potenti e raffinate - come la ricerca e il confronto automatici di configurazione complesse (con componenti variabili) - che si accompagnano bene all'accesso basato sulle forme e ai giocatori che si autoattivano. Di conseguenza, i programmi di Newell sono relativamente brevi ed eleganti: ogni riga svolge molto lavoro. I sistemi di produzione favoriscono un livello di "modularitá" che non ha paragoni nelle altre architetture. Un modulo é un sottosistema indipendente che esegue un compito ben definito e che interagisce con il resto del sitema solo in certi modi restrittivamente defmiti. Ad esempio, il registratore, il preamplificatore ecc. di un sistema di riproduzione stereofonica sono dei moduli. In LISP, le funzioni definite dall'utente si comportano come moduli di programma separati, ma non sono indipendenti come le singole produzioni." Perché una qualunque funzione LISP si valuti, essa deve essere chiamata esplicitamente; chi la chiama non solo deve sapere quando chiamarla, ma anche che nome abbia, quali argomenti deve fornirle e che tipo di valore puó aspettarsi di ritorno. 0, meglio, il programmatore deve tener conto di tutte queste entitá in ogni situazione in cui una particolare. funzione puó (o deve) essere chiamata.

Una produzione, invece, si attiverá da sola quando e dove le condizioni saranno quelle ffiuste, indipendente da quel che sanno o da quel che decidono le altre produzioni. Possiamo prendere un esempio immaginario. Stiamo progettando un tassista robot e tutto sarebbe finito, se non ci fossimo dimenticati delle sirene. Di conseguenza dobbiamo aggiungere una nuova funzione: quando il robot sente una sirena, deve tirarsi di lato finché il pericolo non sia passato. A seconda dell'architettura, saranno necessari un nuovo sottoprogramma, una nuova funzione o una nuova produzione che controllino nella memoria se il segnale (riferito dalle "orecchie") é quello di SIRENA e che, quando é davvero quel segnale, emettano un avviso TIRARSI DI LATO.

Come si puó inserire questa nuova unitá armonizzandola con il resto del sistema? Presumibilmente il guidatore dovrebbe rispondere a una sirena (ammesso che ce ne sia in funzione una) prima di immettersi in un incrocio, prima di uscire da un parcheggio, prima di cambiare corsia e via dicendo, ma anche mentre guida lungo la strada. Pertanto in una macchina di von Neumann o di McCarthy ciascuna delle routine o delle funzioni che eseguono queste attivitá dovrebbe essere modificata, in modo da poter chiamare la nuova unitá SIRENA nei momenti opportuni. In una macchina di Newell, invece, é sufficiente aggiungere alla fila la produzione SIRENA, assegnandole una prioritá opportunamente elevata; non c'é bisogno di toccare un'altra produzione. La nuova arrivata se ne stará lí tranquilla, senza far nulla e senza disturbare nessuno, finché non giungerá un suono di sirena: a quel punto emetterá autonomamente il segnale TIRARSI DI LATO.

Ci sono due limitazioni, tuttavia, che vanno a scapito degli ovvi pregi della modularitá delle produzioni. In primo luogo, non tutti i compiti si possono facilmente scindere in componenti gestibili autonomamente; talvolta, cioé, i sottocompiti debbono essere coordinati in modo esplicito e particolari informazioni o particolari istruzioni debbono essere inviate a unitá particolari in momenti particolari. Un'organizzazione di questo genere non é impossibile nei sistemi di produzione, ma risulta priva di agilitá, rispetto alle chiamate "centralizzate" di sottoprogrammi o di funzioni.

In secondo luogo, la modularití delle produzioni é di un singolo livello: in un sistema di produzione, cioé, non si costruiscono moduli di livello superiore a partire da moduli di livello inferiore, costruiti a loro volta con moduli di livello ancor piú basso ecc. Tutte le produzioni sono alla pari, a parte il diverso grado di prioritá. Le definizioni LISP, invece, sono di per sé stesse gerarchiche, e lo sono spesso anche i programmi di von Neumann.

Conclusione

In questo capitolo ci siamo soprattutto proposti di fornire una prospettiva piú ampia del modo in cui possono essere costituiti i calcolatori. Troppo spesso si pensa che i calcolatori siano essenzialmente macchine Basic, Fortran o addirittura macchine di Turing. Non appena si capisce che possono esistere architetture di pari potenza (cioé universali), ma profondamente diverse, si spalanca un orizzonte illimitato. L'intelligenza artificiale non sostiene affatto che la mente sia una macchina di Turing o un programma in Basic, o uno qualunque degli altri tipi di macchina che abbiamo considerato. É vero che, per motivi di comoditá e flessibilitá, la magoor parte dei programmi di IA é scritta in LISP, ma le macchine virtuali cosí realizzate non sono macchine LISP; in linea di principio, potrebbero essere qualunque cosa. É vero anche che alcuni ricercatori pensano che la mente stessa sia organizzata probabilmente come un sistema di produzione, anche se di complessitá e raffinatezza molto maggiori rispetto alla struttura elementare che abbiamo esaminato in questa sede. La cosa importante, peró, é un'altra: la mente potrebbe avere un'architettura elaborativa tutta sua. In oltre parole, nella prospettiva deil'IA, l'architettura mentale stessa diventa una nuova "variabile" teorica, da studiare e definire mediante ricerche effettive di scienza

cognitiva.