Procedural and logic programming
Question 1: introduction to computer programming and commands
applied computer science
urbino worldwide campus
Question 1: introduction to computer programming
and Linux/gvim/gcc/make/gdb
What is a compiler? (2 points)
Cos’è un compilatore? (2 punti)
—————o—————
What is the Linux command man for? (2 points)
A cosa serve il comando man di Linux? (2 punti)
c 2015 Marco Bernardo
1/22
Procedural and logic programming
Question 1: introduction to computer programming and commands
applied computer science
urbino worldwide campus
A compiler is a software tool that translates a program written in a high level programming language
into an equivalent machine language program. It is composed of a lexical analyzer, a parser,
a static semantic checker (usually implementing a type system), an intermediate code generator,
a code optimizer, and a code generator.
Un compilatore è uno strumento software che traduce un programma scritto in un linguaggio di
programmazione ad alto livello di astrazione in un programma equivalente in linguaggio macchina.
Si compone di un analizzatore lessicale, un riconoscitore sintattico, un controllore semantico statico
(che di solito implementa un sistema di tipi), un generatore di codice intermedio, un ottimizzatore
di codice e un generatore di codice.
—————o—————
The Linux command man provides information about the command specified as argument.
Il comando man di Linux fornisce informazioni sul comando specificato come argomento.
c 2015 Marco Bernardo
2/22
Procedural and logic programming
Question 2: introduction to the language ANSI C
applied computer science
urbino worldwide campus
Question 2: introduction to the language ANSI C
What is the role of placeholders within format strings? (2 points)
Qual è il ruolo dei segnaposto all’interno delle stringhe formato? (2 punti)
c 2015 Marco Bernardo
3/22
Procedural and logic programming
Question 2: introduction to the language ANSI C
applied computer science
urbino worldwide campus
Placeholders stand for data to be read or to be written. In the case of a scanf-like function,
they represent data to be read and then to be assigned to the variables whose addresses are contained in the function invocation. In the case of a printf-like function, they represent data to
be written on the basis of the evaluation of the expressions contained in the function invocation.
The placeholders and the variables/expressions must coincide by number, order, and type.
I segnaposto stanno per dati da leggere o da scrivere. Nel caso di una funzione come scanf,
essi rappresentano dati da leggere e poi da assegnare alle variabili i cui indirizzi sono contenuti
nell’invocazione della funzione. Nel caso di una funzione come printf, essi rappresentano dati
da scrivere sulla base della valutazione delle espressioni contenute nell’invocazione della funzione.
I segnaposto e le variabili/espressioni debbono coincidere per numero, ordine e tipo.
c 2015 Marco Bernardo
4/22
Procedural and logic programming
Question 3: ANSI C expressions
applied computer science
urbino worldwide campus
Question 3: ANSI C expressions
Explain the difference between symbolic constants and literal constants. (2 points)
Spiegare la differenza tra costanti simboliche e costanti in senso letterale. (2 punti)
c 2015 Marco Bernardo
5/22
Procedural and logic programming
Question 3: ANSI C expressions
applied computer science
urbino worldwide campus
A symbolic constant is defined via a #define directive, which provides an int/double/char/string
value with a symbolic name that can be used wherever in the rest of the program. A literal constant is just an int/double/char/string value with no symbolic name associated with it. The use of
symbolic constants increases program readability and maintainability.
Una costante simbolica è definita attraverso una direttiva #define, la quale dota un valore di tipo
int/double/char/stringa di un nome simbolico che può essere usato ovunque nel resto del programma. Una costante in senso letterale è semplicemente un valore di tipo int/double/char/stringa
senza nessun nome simbolico associato ad esso. L’uso di costanti simboliche incrementa la leggibilità
e la mantenibilità dei programmi.
c 2015 Marco Bernardo
6/22
Procedural and logic programming
Question 4: ANSI C statements and correctness
applied computer science
urbino worldwide campus
Question 4: ANSI C statements
and correctness of procedural programs
Describe syntax and semantics of the multiple assignment statement. (2 points)
Descrivere sintassi e semantica dell’istruzione di assegnamento multiplo. (2 punti)
—————o—————
How is the meaning of a sequential program formalized? (2 points)
Come viene formalizzato il significato di un programma sequenziale? (2 punti)
c 2015 Marco Bernardo
7/22
Procedural and logic programming
Question 4: ANSI C statements and correctness
applied computer science
urbino worldwide campus
The syntax of this statement is “var 1 = var 2 = ... = var n = expr;”. The meaning is that first
expression expr is evaluated, then its value is stored into the memory locations associated with the
variables var n, ..., var 2, var 1 considered in this order.
La sintassi di questa istruzione è “var 1 = var 2 = ... = var n = espr;”. Il significato è che
prima viene valutata l’espressione espr, poi il suo valore viene collocato nelle locazioni di memoria
associate alle variabili var n, ..., var 2, var 1 considerate in questo ordine.
—————o—————
The meaning of a sequential program is formalized as a mathematical function that describes the
input/output effect of the execution of the program by ignoring the intermediate computation
states. By computation state we mean the memory contents at a certain point of the execution of
the program.
Il significato di un programma sequenziale viene formalizzato mediante una funzione matematica
che descrive l’effetto ingresso/uscita dell’esecuzione del programma ignorando gli stati intermedi
della computazione. Per stato della computazione si intende il contenuto della memoria ad un
certo punto dell’esecuzione del programma.
c 2015 Marco Bernardo
8/22
Procedural and logic programming
Question 5: ANSI C functions
applied computer science
urbino worldwide campus
Question 5: ANSI C functions
Explain the difference between argc and argv. (2 points)
Spiegare la differenza tra argc e argv. (2 punti)
c 2015 Marco Bernardo
9/22
Procedural and logic programming
Question 5: ANSI C functions
applied computer science
urbino worldwide campus
They represent the parameters of function main. While argc stores the number of strings (executable file name and possible options) occurring in the command given to start the execution of
the program, argv stores the strings themselves.
Essi rappresentanto i parametri della funzione main. Mentre argc contiene il numero di stringhe
(nome del file eseguibile ed eventuali opzioni) presenti nel comando dato per avviare l’esecuzione
del programma, argv contiene le stringhe stesse.
c 2015 Marco Bernardo
10/22
Procedural and logic programming
Question 6: ANSI C data types
applied computer science
urbino worldwide campus
Question 6: ANSI C data types
What is a type constructor? (2 points)
Cos’è un costruttore di tipo? (2 punti)
c 2015 Marco Bernardo
11/22
Procedural and logic programming
Question 6: ANSI C data types
applied computer science
urbino worldwide campus
A type constructor is a mechanism through which a new type can be constructed on the basis
of already existing types. The type constructors provided by the language ANSI C are enum,
[ ] (for array types), struct, union, and ∗ (for pointer types).
Un costruttore di tipo è un meccanismo tramite il quale un nuovo tipo può essere costruito sulla base
di tipi già esistenti.
I costruttori di tipo forniti dal linguaggio ANSI C sono enum,
[ ] (per i tipi array), struct, union e ∗ (per i tipi puntatori).
c 2015 Marco Bernardo
12/22
Procedural and logic programming
Question 7: propositional logic
applied computer science
urbino worldwide campus
Question 7: propositional logic
What is a proposition and how is it interpreted? (2 points)
Cos’è una proposizione e come viene interpretata? (2 punti)
c 2015 Marco Bernardo
13/22
Procedural and logic programming
Question 7: propositional logic
applied computer science
urbino worldwide campus
A proposition is a statement related to a single fact of which we can establish the truth. It is
interpreted through a truth assignment, which is a set of propositions. If that proposition belongs
to the truth assignment, then it is true, otherwise it is false.
Una proposizione è un’affermazione relativa ad un singolo fatto di cui può essere stabilita la verità.
Essa viene interpretata attraverso un assegnamento di verità, che è un insieme di proposizioni.
Se quella proposizione appartiene all’assegnamento di verità, allora è vera, altrimenti è falsa.
c 2015 Marco Bernardo
14/22
Procedural and logic programming
Question 8: predicate logic
applied computer science
urbino worldwide campus
Question 8: predicate logic
What is a predicate and how is it interpreted? (2 points)
Cos’è un predicato e come viene interpretato? (2 punti)
c 2015 Marco Bernardo
15/22
Procedural and logic programming
Question 8: predicate logic
applied computer science
urbino worldwide campus
A predicate is formed by a predicate symbol applied to a number of terms each composed of symbols
of constant, variable, and function. Given a domain, a predicate symbol is interpreted as a relation
over that domain and hence the application of a predicate symbol to a number of terms is true if
and only if the tuple of domain values resulting from the interpretation of the various terms belongs
to the relation.
Un predicato è formato da un simbolo di predicato applicato ad un numero di termini ciascuno
composto da simboli di costante, variabile e funzione. Dato un dominio, un simbolo di predicato
viene interpretato come una relazione su quel dominio e quindi l’applicazione di un simbolo di
predicato ad un numero di termini è vera se e soltanto se la tupla di valori del dominio derivanti
dall’interpretazione dei vari termini appartiene alla relazione.
c 2015 Marco Bernardo
16/22
Procedural and logic programming
Question 9: Prolog language and gprolog
applied computer science
urbino worldwide campus
Question 9: Prolog language and gprolog
What is a resolution strategy? (2 points)
Cos’è una strategia di risoluzione? (2 punti)
c 2015 Marco Bernardo
17/22
Procedural and logic programming
Question 9: Prolog language and gprolog
applied computer science
urbino worldwide campus
During the execution of a Prolog program, Robinson resolution method is used many times. In
order to limit the number of unimportant or redundant clauses that are produced along the process,
the Prolog interpreter resorts to a resolution strategy that suitably chooses at each step the clauses
from which to generate a resolvent.
Durante l’esecuzione di un programma Prolog, il metodo di risoluzione di Robinson viene utilizzato
parecchie volte. Al fine di limitare il numero di clausole irrilevanti o ridondanti che vengono man
mano prodotte, l’interprete Prolog ricorre ad una strategia di risoluzione che sceglie ad ogni passo
in modo mirato le clausole da cui generare una risolvente.
c 2015 Marco Bernardo
18/22
Procedural and logic programming
Exercise 1: ANSI C programming/verification
applied computer science
urbino worldwide campus
Exercise 1: ANSI C programming/verification
Write a recursive function in ANSI C that takes as input parameters a string and a character and
returns as result the number of occurrences of the character within the string. (6 points)
Scrivere una funzione ricorsiva in ANSI C che ha come parametri di ingresso una stringa e un
carattere e restituisce come risultato il numero di occorrenze del carattere all’interno della stringa.
(6 punti)
—————o—————
Prove that the following ANSI C function computes the maximum even number not greater than x.
(6 points)
int compute_max_even(int x)
{
int z;
if (x % 2 == 0)
z = x;
else
z = x - 1;
return(z);
}
Dimostrare che la precedente funzione ANSI C calcola il massimo numero pari non maggiore di x.
(6 punti)
c 2015 Marco Bernardo
19/22
Procedural and logic programming
Exercise 1: ANSI C programming/verification
applied computer science
urbino worldwide campus
int count(char *s,
char c)
{
int n;
if (s[0] == ’\0’)
n = 0;
else
{
n = (s[0] == c)?
1:
0;
n += count(s + 1,
c);
}
return(n);
}
—————o—————
Postcondition: z = max{n ∈ N | n = n0 · 2 ∧ n ≤ x}.
(x = x0 · 2 → (z = max{n ∈ N | n = n0 · 2 ∧ n ≤ x})z,x ) ≡
(x = x0 · 2 → (x = max{n ∈ N | n = n0 · 2 ∧ n ≤ x})) ≡ true.
(x = x0 · 2 + 1 → (z = max{n ∈ N | n = n0 · 2 ∧ n ≤ x})z,x−1 ) ≡
(x = x0 · 2 + 1 → (x − 1 = max{n ∈ N | n = n0 · 2 ∧ n ≤ x})) ≡ true.
(true ∧ true) ≡ true.
c 2015 Marco Bernardo
20/22
Procedural and logic programming
Exercise 2: propositional logic/predicate logic/Prolog
applied computer science
urbino worldwide campus
Exercise 2: propositional logic/predicate logic/Prolog
Establish whether the following propositional logic formula is a tautology. (6 points)
(p ∨ (p ∧ q)) ↔ p
Stabilire se la seguente formula di logica proposizionale è una tautologia. (6 punti)
(p ∨ (p ∧ q)) ↔ p
—————o—————
Write a predicate in Prolog that computes the maximum of a set of integer numbers. (6 points)
Scrivere un predicato in Prolog che calcola il massimo di un insieme di numeri interi. (6 punti)
c 2015 Marco Bernardo
21/22
Procedural and logic programming
Exercise 2: propositional logic/predicate logic/Prolog
applied computer science
urbino worldwide campus
It is a tautology because:
p
1
1
0
0
q
1
0
1
0
p ∧ q p ∨ (p ∧ q) (p ∨ (p ∧ q)) ↔ p
1
1
1
0
1
1
0
0
1
0
0
1
—————o—————
max([X], X) :- integer(X).
max([X | L], X) :- integer(X), max(L, Y), X >= Y.
max([X | L], Y) :- integer(X), max(L, Y), Y > X.
c 2015 Marco Bernardo
22/22