La Sintassi del Linguaggio WHILE

Calcolabilità e Linguaggi di Programmazione

6.1 11 linguaggio WHILE

In questo capitolo presenteremo un nuovo possibile modo di accostare la computa-bilità: stavolta, infatti, la introdurremo attraverso i moderni linguaggi di program-mazione. In effetti, la ricerca di linguaggi ad alto livello, capaci cioè di esprimere tutte le funzioni effettivamente computabili, risale già agli anni sessanta e ha pro-dotto una vasta famiglia di linguaggi come ALGOL e PASCAL, progenitori dei più moderni C, C++ e Java.

Noi però concentreremo qui la nostra attenzione su un semplice linguaggio di pro-grammazione imperativo chiamato WHILE. Si tratta di un linguaggio adeguato a rappresentare tutte le funzioni calcolabili, povero in confronto ad altri linguaggi di alto livello come il PASCAL o il FORTRAN, ma, proprio in virtù della sua semplicità descrittiva, capace di sottolineare in maniera più diretta e immediata il collegamento con la computabilità.

6.2 La Sintassi del Linguaggio WHILE

L'insieme dei caratteri di base del linguaggio WHILE contiene nomi per le varia-bili, simboli per gli operatori di base che modificano il valore delle variavaria-bili, un operatore per confrontare valori di coppie di variabili e un simbolo di programma.

La sintassi del linguaggio WHILE è specificata in accordo alle regole di produzio-ne di una grammatica libera dal contesto (presentate produzio-nel Capitolo 5) ed è definita come segue.

PROGRAM begin end I begin SEQCOMMANDS end

SEQCOMMANDS COMMAND SEQCOMMANDS ; COMMAND

COMMAND ASSIGNEMENT while TEST do COMMAND

I

PROGRAM ASSIGNMENT VAR : =O VAR : =

s (

VAR)

I

VAR : =pd (VAR)

TEST VAR VAR

VAR ••— LETTERA VAR LETTERA VAR CIFRA

LETTERA A B ...

CIFRA

0111

... 9

Si noti che le variabili sono formate da stringhe finite arbitrarie di lettere maiu-scole

A, B, . . Z

e di cifre decimali 0, 1, ..., 9 che hanno l'unico obbligo di iniziare con una lettera maiuscola come accade, per esempio, a X e A ma anche a

PIPP01,CASA3

e P55.

Definizione. Un programma WHILE è una sequenza ordinata finita (eventual-mente vuota) di

comandi,

separati da punti e virgole, preceduta da begin e seguita da end. I comandi sono definiti induttivamente nel modo che adesso mostriamo.

• AI livello più elementare abbiamo i

comandi di assegnamento,

quelli della forma

(Zero):

X := O (s): X :=

s(Y) (pd): X :=

pd(Y)

dove O è il numero naturale zero,

s

è la funzione successore

(s(n) = n +

1 per ogni naturale n) e

pd è

la funzione predecessore

(pd(n) = n — i

se n > O e

pd(0) =

0). 0,

s

e

pd

costituiscono gli operatori base del linguaggio. Si noti che

nei programmi WHILE i valori assegnati alle variabili saranno sempre numeri naturali.

Si definiscono poi per induzione gli altri comandi, suddivisi tra

comandi composti

e

comandi

whi le.

• Un

comando composto è

un' istruzione della forma begin Cl; ; CN end

con

N

naturale e indica che le istruzioni C 1, CN devono essere eseguite in successione, secondo l'ordine assegnato. Ammettiamo anche il caso

N =

O,

che si riduce sostanzialmente ad un'istruzione che lascia inalterato il valore di tutte le variabili.

• Finalmente un

comando

whi l e ha la forma

whi le X Y do ^COMMAND;

la sua semantica consiste nel ripetere l'esecuzione del comando descritto in COMMAND per tutto il tempo in cui la variabile x assume un valore diverso dal valore della variabile Y.

In particolare, l'unico operatore di confronto tra variabili in un linguaggio WHILE è, almeno inizialmente,

Quindi il linguaggio WHILE mette a disposizione del programmatore solo po-chissimi operatori e comandi. Tuttavia mostriamo adesso come definire varie ma-croistruzioni che possono agevolare la stesura di un programma; cerchiamo così di convincere il lettore che, proprio grazie a queste macro, il potere espressivo dei programmi WHILE non è inferiore a quello di altri usuali linguaggi di program-mazione, almeno per quanto concerne l'aspetto computazionale. In particolare i linguaggi WHILE riescono a rappresentare tutte le familiari operazioni aritmeti-che.

La prima macro che consideriamo riguarda il problema di assegnare il valore di una variabile Y a un'altra variabile

X .

Il nostro linguaggio di programmazione non ha, al momento, alcun comando primitivo a questo proposito. E' facile tutta-via convincersi che il programma:

begin X := s(Y) ; X := pd(X) end

permette il passaggio del valore della variabile Y alla variabile

X .

Nel seguito, quindi, potremo usare il comando

X :=

Y per denotare sinteticamente la prece-dente macrodefinizione.

Un'altra operazione usuale in programmazione è quella di assegnare il valore di una costante n > O ad una variabile U, U:= n. La macro che la effettua consiste nella seguente lista di comandi elementari:

begin U := O ; U := s(U); ...; U := s(U) end dove il comando U := s(U) è ripetuto n volte.

Se si vuole sommare il valore della variabile Y alla variabile

X, X := X +

Y, si può invece usare la macro:

begin U. 0;

while U Y do

begin X := s(X); U := s(U) end

Usando le macro già definite si può poi scrivere il programma:

begin Z := X ; Z:=Z+X end

che corrisponde alla istruzione

Z := X + Y ,

e dunque alla addizione. Anche l'al-tra familiare operazione numerica della moltiplicazione si esprime nel linguaggio WHILE tramite un'opportuna macro (che il lettore può provare a definire da solo per esercizio).

Le funzioni descrivibili in WHILE tramite opportune macro includono anche la differenza, la differenza aritmetica, il quoziente, il resto e così via. Consideriamo per esempio il caso della

differenza aritmetica Z := X e

^{Y di}

^X

e Y; ricordiamo che si conviene che X e Y è X — Y se

X

> Y, O altrimenti. La macro che la esprime (e del resto corrisponde alla caratterizzazione di

e

data in § 4.3) è la seguente:

begin

Z:=X ; U:=Y; V:=0

whi le U 7 V do begin Z := pd(Z); U := pd(U) end end

Di uso frequente in programmazione sono anche gli operatori di confronto. Tut-tavia l'unico di essi disponibile almeno inizialmente nel linguaggio WHILE è

X

Y. Ma è spesso necessario considerare anche test del tipo:

X <

Y,

X >

5,

X

Y,

X =

Y e via dicendo. Il linguaggio WHILE garantisce queste opportu-nità se non direttamente almeno tramite macro. Per esempio

X <

Y può essere coinvolto mediante (Y

e ^X) e ^pd(Y e ^X),

nel senso che

X < Y è

vera se e soltanto se (Y

e X) e ^pd(Y e ^{X) =}

1, mentre

X <

Y è falsa se e soltanto se ( 7

e x) e ^pd(Y e x) =

^0.

Anzi, questo esempio ci mostra come coinvolgere nei linguaggi WHILE gli usuali connettivi della logica elementare - --i

(non),

A

(e),

V (o) e quindi esprimere condi-zioni come quella appena considerata --1(X < Y), oppure

(X < Y)

V

(X = Y)

(cioè

X <

Y),

(X Y)

A —1(X < Y) (cioè

X > Y)

e altre più elaborate come

(-1(X < Y) A

(X = Y)) V (X Y),

in definitiva tutte quelle condizioni che possono ottenersi come

espressioni Booleane

di altre che già conosciamo. Così facendo,

X =

Y può essere ottenuta come semplice espressione Booleana per Y). Basta associare a ciascuna di queste espressioni E una condizione di test

n

tra variabili in modo tale che

n

ha O e 1 come unici valori ammissibili e

• TE =

1 se e soltanto se

E è

vera, e quindi

• n =

O se e soltanto se

E è

falsa.

Le regole per costruire questi termini sono facili da stabilire; per esempio, usando l'operatore pd e le macro + e

e,

possiamo scriverle come segue.

• T-,E

= i e n

(dunque 1 se TE = O e viceversa),

• Te Aei = pd(Te Tal) (dunque 1 se

n = = 1,

0 altrimenti),

• Te v e/ = TE

+n, epd(Te + Te')

(dunque 1 se

n = i

o TEI = 1, 0 altrimenti).

Il lettore può provare a usare anche la moltiplicazione per ottenere espressioni più semplici per A e V, ricordando situazioni analoghe nel Capitolo 4.

In modo simile possiamo catturare nel nostro linguaggio estensioni del comando whi 1 e come

while EXPRBOOL do COMMAND

dove EXPRBOOL è una generica espressione Booleana g, e non soltanto X Y.

Per costruire la macroistruzione che corrisponde a questo comando, assumiamo per semplicità che in EXPRB OOL compaiano solo variabili e non costanti (del re-sto espressioni Booleane con costanti si possono ottenere da quelle che hanno solo variabili assegnando le costanti alle variabili nel modo sopra descritto). Allora la macro che ci serve è:

begin

U:= TExPRBooL V:=0

while U V do begin COMMAND ; U:= TExpRBooL ^end end

dove T _EXPRBOOL indica, come sappiamo, la condizione di test associata all'e-spressione Booleana EXPRBOOL.

Un'altra istruzione non direttamente disponibile nel linguaggio dei programmi WHILE, ma assai comune in altri linguaggi di programmazione, è il comando

i f EXPRBOOL then COMMAND 1 else COMMAND2

che fa eseguire la sequenza di istruzioni che segue then, e cioè COMMAND1, se l'espressione Booleana EXPRBOOL ^è vera, e la sequenza di comandi dopo e lse, e cioè COMMAND2, se l'espressione Booleana EXPRBOOL è falsa. La macro per questo operatore condizionale è la seguente:

begin

U:= T^{EXPRB OOL}

V:=0

while (U = 1) A (V = O) do begin COMMANDi ; V:= 1 end while (U = 0) A (V = 0) do begin COMMAND2 ; V:= 1 end end

Con l'utilizzo di queste macroistruzioni, il linguaggio WHILE raggiunge sostan-zialmente l'espressività del PASCAL. Le macro sono quindi di grande aiuto nella stesura di programmi per computazioni complesse; ma quando il nostro obietti-vo si sposta a dimostrare proprietà astratte dei programmi, allora la semplicità dell'originario contesto WHILE torna utile per abbreviare e snellire la trattazione.

Nel documento Carlo Toffalori Flavio Corradini Stefano Leonesi Stefano Mancini. Teoria della computabilità e della complessità. McGraw-Hill (pagine 106-111)