Esercitazioni di Linguaggi di Programmazione

Formattazione del testo

ERRORE.Il linguaggio di specifica denotazionale non disponga di alcun operatore logico.Le tabelle di verità degli operatori binari logici si esprimono con quattro casi. Il problema più complicato è trovare l'espressione di cortocircuito sulla base della tabella. Consideriamo che Asia vero, il risultato concede con B. Quindi, if(A) then BAvendo l'espressione condizionale, abbiamo tutto. Se si applica il true, abbiamo true, altrimenti false. Se genera errore, da errore, se da true, abbiamo ritornare il valore di B, altrimenti è vero.

34Martina Contestabile Ingegneria Informatica - III Anno A.A. 2022/2023

ESPRESSIONI

Esercizio 1

Data la seguente tabella di operatori aritmetici, riscrivere la seguente espressione in forma parentetica:

a + b - c * d + e / f * g ** h ** i

Doppia stella è l'elevamento a potenza, altissima priorità. Dall'espressione all'albero è estremamente meccanico, ma come inseriamole parentesi?

alla base della tabella? Dobbiamo considerare la tabella dalla prima all'ultima riga, dobbiamo vedere le sotto espressioni contigue a quella riga. Come prima cosa troviamo g ** h, ma h non sappiamo se associarlo a destra o a sinistra: la tabella dice destra, quindi prima abbiamo h ** i e poi g ** h. D'ora in poi dobbiamo fare lo stesso discorso per la riga successiva, isoliamo le sequenze aventi operazione di moltiplicazione e divisione; l'associatività è sempre a destra. Infine, ragioniamo sull'ultima riga, addizione e sottrazione. Il fatto che ci siano precedenze significa che certe operazioni si svolgono prima e le parentesi vengono svolte prima. Una volta ottenuta l'espressione con le parentesi, è tutto chiaro.

Esercizio 3 Dall'espressione parentetica si può facilmente ricavare l'albero Specificare la semantica operazionale del seguente assegnamento, supponendo di valutare in corto circuito l'espressione di destra x := (a

b) or ((b++ / 3) < 2 and ++a = b-1);

Non essendoci la tabella degli operatori, dobbiamo fare assunzioni ragionevoli.

Quando si parla di valutare in corto circuito, si sta parlando degli operatori logici.

Essendo and e or in corto circuito, se uno dei due è vero o falso abbiamo subito il valore, ma non sap- piamo quale sia, quindi dobbiamo considerare tutti i casi.

Se a > b è vero, allora l’espressione è vera, quindi x è true.

L’and, a sua volta, è valutato da sinistra a destra, quindi valuto l’espressione di divisione. C’è l’incremento suffisso su b, quindi va incrementato a fine divisione. Se non è vero t1 < 2, x è false.

In caso affermativo, invece, bisogna valutare il secondo termine, è un and. Prima bisogna incrementare a, c’è l’incremento prefisso, poi decrementare b di 1 e, infine, confrontare l’uguaglianza. x, alla fine, è il risultato dell’uguaglianza,

in quanto se è vera l'and è soddisfatto e, quindi, anche l'or, altrimenti l'espressione non è soddisfatta.

35Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Esercizio 4

Assumendo la seguente tabella di operatori, in cui ogni operatore valuta i suoi operandi da sinistra a destra e la valutazione delle espressioni logiche è in corto circuito, specificare la semantica operazionale del seguente assegnamento

x = (++a + b <= c and a-- / 3 + c > ++d ? a++ : ++b / 2)

Si ricordi che il linguaggio di specifica non contempla gli operatori ++, --.

36Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

L'and confronta due espressioni in cui ci vuole poco per arrivare all'espressione parentetica. Dobbiamo sempre partire dalla prima riga della tabella, seguire le regole associative e poi stabilire dove mettere le parentesi per il resto ripetendo i passaggi appena enunciati. Se la prima espressione

dell'and è falsa, il risultato di x è ++b / 2, ossia false. I caso contrario, dobbiamo valutare la seconda d'espressione, dove prima si decrementa a, perché il suo valore originario è stato messo in sicurezza - il decremento posposto ha più importanza della divisione, lo dice la tabella - e, dopo la divisione, si somma tre. Incrementato d, possiamo fare il confronto fra t4 e d: se è vero, il risultato di x è a++, altrimenti bisogna assegnare ++b / 2.

Esercizio 5

Assumendo la seguente tabella di operatori (in cui ogni operatore binario valuta prima l'operando di destra e poi quello di sinistra, e la valutazione delle espressioni logiche è in corto circuito), specificare la semantica operazionale del seguente assegnamento della variabile logica vv := a + b * c > d ^ e ^ f + 1 or g < h/i

Si ricordi che il linguaggio di specifica operazionale contempla le seguenti limitazioni:

Non contiene gli operatori

logici and, or;

Contiene gli operatori ^, +, -, *, /, <, >, che però non possono essere applicati al risultato di altre operazioni, quindi è necessario l’introduzione di opportuni temporanei per i risultati intermedi…

La valutazione è da destra a sinistra quindi la prima operazione da fare è h / i, che poi si può confrontare con g. Se la condizione g < (h / i) è vera, allora v è true. In caso contrario, si valuta l’altro ramo dell’albero. Anche ^ si valuta a destra, quindi partiamo con e ^ f per poi risalire, proseguiamo con le foglie a sinistra e, infine, valutiamo il >.

Esercizio 11

È data la seguente tabella di operatori per la quale si assume priorità decrescente dall’alto verso il basso

37Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Sono stabilite le seguenti regole di corto-circuito:

expr1 ^ expr2 = 1 quando expr2 = 0.

expr1 * expr2 = 0 quando expr1 = 0.

Quindi,

data la seguente istruzione di assegnamento,

x := a + b – c + d – e * f * g ^ (h * i) ^ m

bisogna rappresentare l’albero della espressione di assegnamento e specificare la semantica operazionale dell’istruzione di assegnamento.

Si ricordi che il linguaggio di specifica operazionale è così caratterizzato:

• Contiene gli operatori aritmetici ^, *, +, -.
• Contiene gli operatori di assegnamento ‘=’ e di confronto di uguaglianza ‘==’.
• Ogni operatore non può essere applicato ad espressioni, ma solo a variabili o costanti.
• Contiene le istruzioni condizionali (if-then-endif ed if-then-else-endif) i cui predicati possono essere solo semplici confronti di uguaglianza.

38

Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Le frecce rappresentano l’ordine di valutazione. Non c’è nulla di complicato, serve stare solo attenti. In base all’ordinamento, la prima operazione da fare è a + b. Se e

Vale zero, allora il prodotto vale zero. Quando arriviamo a t4 dobbiamo applicare ancora il cortocircuito, perché se vale zero lo è anche t8. Altrimenti, dobbiamo vedere quanto vale m, perché se è zero la sua esponenziazione è sempre 1. Poi dobbiamo valutare h come abbiamo fatto per e. Infine, dobbiamo ragionare su t7.

Esercizio 13

È data la seguente tabella di operatori, per la quale si assume priorità decrescente dall'alto verso il basso, e la seguente espressione:

not a = b and c or d = e ? x and y : z

Bisogna rappresentare l'albero della espressione e specificare la semantica operazionale della espressione.

Si ricordi che il linguaggio di specifica operazionale è così caratterizzato:

Contiene gli operatori di negazione (!), disgiunzione (||), uguaglianza (==) ed assegnamento (:=).

Non contiene l'operatore di congiunzione, né l'operatore ?:, né le costanti logiche true, false.

Ogni operatore non può essere

applicato ad espressioni, ma solo a variabili. Contiene le istruzioni condizionali (if-then ed if-then-else) i cui predicati possono essere solo variabili. Contiene l'istruzione return il cui argomento è la variabile che contiene il valore dell'espressione. L'esecuzione della return termina immediatamente l'esecuzione del programma di specifica operazionale. Quando non c'è l'assegnamento, nella semantica denotazionale si fa il return.

Martina Contestabile Ingegneria Informatica - III Anno A.A. 2022/2023

SCHEME

Esercizio 1

Definire nel linguaggio funzionale Scheme la funzione reverse, che computa l'inverso di una lista di atomi in ingresso. Ecco alcuni esempi

Quali sono gli scenari di applicazione e, nel caso in cui sia ricorsiva, come avviene la ricorsione? Questo schema ricorsivo necessita di capire il mapping fra le due liste. Quella risultante, rispetto alla prima, ha che l'ultimo elemento passa da coda a testa, ma, analizzando anche

Gli altri elementi, vediamo che è il reverse della coda. Non possiamo però fare l'append della coda, perché è un atomo, si può fare per la lista della testa. La reverse di A ha due scenari: se vuota ritorna A, altrimenti si fa il reverse del cdr A e del list del car di A, per avere l'append della coda - lista di un solo elemento.

Esercizio 2

Definire nel linguaggio funzionale Scheme la funzione spec, avente in ingresso una lista L, che restituisce la lista speculare di L, come nei seguenti esempi:

Quando abbiamo la lista vuota, ritorniamo la lista vuota. Quando non lo è, in testa può esserci un atomo oppure una lista. Come per la reverse, si fa lo speculare della coda, ma se è un atomo rimane il car di L, altrimenti si fa la lista della speculare della L, ossia spec (car L).

Esercizio 3

Definire nel linguaggio funzionale Scheme la funzione natoms, avente in ingresso una lista L, che computa il numero di elementi atomici (non

• L. Ecco alcuni esempi
• Martina Contestabile Ingegneria Informatica — III Anno A.A. 2022/2023

Se la lista non è vuota bisogna dividere il caso in cui o c'è un atomo o una lista.

Se la testa della lista è un atomo, allora è 1 + atomi della coda, altrimenti bisogna computare il numero di atomi della L e sommarli al numero degli atomi della coda.

Esercizio 4

Definire nel linguaggio Scheme la funzione atomi, avente in ingresso una lista, che computa la lista degli elementi atomici (non liste) di lista. Ecco alcuni esempi

Se la lista non è vuota, abbiamo gli scenari della spec: atomo o lista? Se in testa c'è un atomo, nel risultato abbiamo in testa l'atomo e a seguire gli atomi della coda. In caso di lista, dobbiamo fare l'append