<< pagina principale < ······················ << articoli < ······················
di Roberto Ricci, Liceo Scientifico "A. Righi", Bologna
Per contare il numero di oggetti raggruppati in una pluralità (finita) occorre evidentemente essere in grado di distinguere, in qualsiasi pluralità, un elemento dagli altri. Questa capacità di destrutturare qualsiasi pluralità di oggetti, unita a quella di applicarla ricorsivamente pluralità, permette anche di ristrutturarla per realizzare un elenco, dei nomi propri di quegli oggetti, oppure per metterli in fila. Il concetto di lista, acquisito in maniera particolarmente chiara, operativamente, nell'ambito dell'Informatica, è legato a tali ristrutturazioni. Tutte e solo le istanze di tale concetto hanno in comune la essenziale, appunto, ed unica proprietà di apparire immediatamente distinguibili in un elemento, quando ve ne sono, e in una parte rimanente che è ancora una lista. Tali parti, in gergo informatico, si chiamano rispettivamente testa e coda.
Il concetto di <lista>, che dunque o è nulla oppure è una qualsiasi entità composta da un elemento e da una lista, può essere descritto in modo preciso e sintetico nel pratico formalismo B.N.F., un metalinguaggio proposto da Bakus-Naur come schema lineare per descrivere altri linguaggi, nel modo seguente:
<lista> ::= <nulla> / <elemento><lista>
dove il metasimbolo '::=' si legge 'è definito come' e il metasimbolo '/' si legge 'aut'. Inoltre, in particolare, possiamo definire il concetto <nulla> come:
<nulla> ::=
mentre il concetto <elemento> potrà essere assunto intuitivamente o definito a sua volta ad esempio come <elemento> ::= l quando si voglia descrivere in particolare il concetto di lista di aste.
Questa definizione ricorsiva del concetto <lista> è corretta nel senso che permette di riconoscere in un numero finito di passi se un certo oggetto è una lista oppure no.
Potrebbe venire il dubbio che i concetti di pluralità (o insieme) e di lista fossero la stessa cosa, pensando di poter definire una pluralità come un ente nullo o composto da un elemento ed un resto che sia ancora una pluralità. Tuttavia non è così in quanto, diversamente dalle pluralità, in una lista sono previste ripetizioni. Dare in B.N.F. una definizione di <pluralità> è certamente complesso e per questo si può probabilmente affermare che tale concetto è più complesso di quello di lista.
Nel linguaggio Prolog, come in generale nei linguaggi per l'Intelligenza Artificiale, la lista è una delle strutture più importanti; addirittura nel linguaggio Lisp ( da List processor, ovvero: elaboratore di liste) la forma stessa delle espressioni del linguaggio è quella di lista.
I seguenti sono due esempi di liste Prolog:
[1,4,9,16,25,36,49]
oppure
[questa,lista,di,parole].
In questa scrittura gli elementi della lista sono separati da una virgola e racchiusi tra due parentesi quadre, una per segnalare l'inizio e una per segnalare la fine della scrittura. L'automa Prolog può inoltre distinguere la testa di una qualsiasi lista dalla coda. Infatti interrogando l'automa, ad esempio, nel modo seguente
?- [Testa|Coda]=[questa,lista,di,parole].
si otterrebbe la risposta:
Testa=questa
Coda=[lista,di,parole]
La capacità di distinguere un primo elemento dal resto, anche se è sufficiente per ristrutturare una pluralità e darle forma di lista non è la sola capacità indispensabile per poter contare quegli oggetti. Tuttavia contare in maniera primitiva servendosi di aste non è molto più complesso. E` facile anche insegnare questa abilità all'automa Prolog, ad esempio nel modo seguente:
enumInAste([],[]). enumInAste([_|Resto],[l|N]):- enumInAste(Resto,N).
dove il primo argomento del predicato 'enumInAste' può essere l'elenco dei nomi propri degli oggetti da contare ovvero una lista di simboli, e il secondo elemento è il numero di quegli oggetti espresso in 'l', qui usato come asta. Interrogando l'automa Prolog, ad esempio, nel modo seguente:
?- enumInAste([a,b,c,d,e,f],N).
si otterrebbe la risposta
N=[l,l,l,l,l,l]
Così si può dire che un numero naturale è ciò che rimane da una pluralità di elementi dopo che essi sono stati riorganizzati in forma di lista e spogliati da ogni diversità. Il fatto che né una pluralità di aste né una lista di aste sono modi abbastanza pratici di rappresentare il numero di elementi di una qualsiasi pluralità fu di stimolo, nella storia del pensiero umano, per la realizzazione di nuovi metodi di rappresentazioni. L'ultimo stadio in questa evoluzione, a cui gli occidentali giunsero soltanto nel Trecento dopo aver appreso i risultati a cui erano già pervenuti gli Arabi, conduce alla rappresentazione posizionale in base dieci, particolarmente comodo ed efficace in quanto a potenza di calcolo. Con questo metodo di rappresentazione un numero decimale è una lista di simboli, le cifre, definibile in B.N.F. come:
<numero naturale> ::= <cifra>/<cifra><numero naturale> <cifra> ::= 0/1/2/3/4/5/6/7/8/9
Ricordando che gli argomenti i quali iniziano con lettera maiuscola rappresentano variabili, potremmo insegnare anche all'automa Prolog a contare una qualsiasi pluralità con questo nuovo metodo di rappresentazione.
enum([],[0]). enum([l],[1]). enum([l,l],[2]). enum([l,l,l],[3]). enum([l,l,l,l],[4]). enum([l,l,l,l,l],[5]). enum([l,l,l,l,l,l],[6]). enum([l,l,l,l,l,l,l],[7]). enum([l,l,l,l,l,l,l,l],[8]). enum([l,l,l,l,l,l,l,l,l],[9]). enum([l,l,l,l,l,l,l,l,l,l|Lista],N):- var(N), divisiInDecine(Lista,ListaDecine,ListaUnita), enum([l|ListaDecine],Decine), enum(ListaUnita,Unita), concatenate(Decine,Unita,N). divisiInDecine([l,l,l,l,l,l,l,l,l,l|Lista],[l|ListaDecine],ListaUnita):- !, divisiInDecine(Lista,ListaDecine,ListaUnita). divisiInDecine(Lista,[],Lista).
Interrogando allora l'automa Prolog nel modo seguente
?- enum([l,l,l,l,l,l,l,l,l,l,l,l,l,l,l,l],N).
si otterrebbe la risposta: N=[1,6].
Il predicato 'concatenate' è definibile come:
concatenate([],L,L). concatenate([T|C],L,[T|CL]) :- concatenate(C,L,CL).
in modo che interrogando l'automa Prolog con
?- concatenate([a,b,a],[x,y],L).
si otterrebbe la risposta:
L=[a,b,a,x,y]
Il concetto di concatenazione di liste è alla base del concetto di somma tra numeri naturali, siano essi rappresentati con aste, e ciò risulta banale, o nel sistema posizionale in base dieci, come si può vedere nella descrizione seguente che rappresenta un metodo usuale basato anziché sull'uso della tabellina pitagorica su quello delle dita
calcola(A + [],A) :- !. calcola([] + B,B) :- !. calcola(A + B,N):- concatenate(DecineA,[UnitA],A), concatenate(DecineB,[UnitB],B), enum(DitaA,[UnitA]), enum(DitaB,[UnitB]), concatenate(DitaA,DitaB,Dita), enum(Dita,[Unit]), !, calcola(DecineA + DecineB,Decine), concatenate(Decine,[Unit],N). calcola(A + B,N):- concatenate(DecineA,[UnitA],A), concatenate(DecineB,[UnitB],B), enum(DitaA,[UnitA]), enum(DitaB,[UnitB]), concatenate(DitaA,DitaB,[l,l,l,l,l,l,l,l,l,l|Dita]), enum(Dita,Unit), calcola(DecineA + [1],DecineAA), calcola(DecineAA + DecineB,Decine), concatenate(Decine,Unit,N).
Interrogando l'automa Prolog nel modo seguente:
?- calcola([9,3,9] + [1,9,1],S).
si otterrebe la risposta:
S=[1,1,3,0]