Αρχές Γλωσσών Προγραμματισμού και Μεταφραστών — Σεπτέμβριος 2022¶
Μεταγραφή από τις φωτογραφίες IMG_1681.jpg και IMG_1684.jpg. Τα αντίγραφα IMG_1682.jpg και IMG_1685.jpg χρησιμοποιήθηκαν για επιβεβαίωση.
IMG_1681.jpg¶
[Λείπει από τη φωτογραφία: επικεφαλίδα και αρχή του ΘΕΜΑΤΟΣ 1]
…δυαδικούς αριθμούς μήκους τουλάχιστον 5 ψηφίων, οι οποίοι αρχίζουν με 01 και τελειώνουν με 10. Ενδιαμέσως των δύο ζευγαριών υπάρχει ακολουθία δυαδικών ψηφίων οποιουδήποτε μήκους (τουλάχιστον ένα). Π.χ. 01010, 01110110. Παρουσιάστε και μια αντιστοιχη κανονική έκφραση.
ΘΕΜΑ 2 – Μεταβλητές και Διαχείριση Μνήμης (20%)¶
(α) Που δεσμεύεται και πόση μνήμη (σε bytes) χρησιμοποιεί κάθε μεταβλητή στον παρακάτω κώδικα C; Περιγράψτε τον τρόπο πρόσβασης στη μνήμη του πίνακα κατά την αρχικοποίησή του. Αναφέρετε πιθανά ζητήματα απόδοσης.
#define N 1024
static double A[N][N];
void init() {
int i, j;
for (j = 0; j < N; ++j)
for (i = 0; i < N; ++i)
A[i][j] = (i*j)/(i+j+1);
}
int *p;
*p = 15;
ΘΕΜΑ 3 – Python (10%)¶
(α) Ποιο το αποτέλεσμα της εκτέλεσης του τμήματος προγράμματος:
for x in range(12, 2, -2):
print(x+2, end = ' ')
if x == 4 :
break
x=4
for x in "12345678":
print (x*x, end = ' ')
i=5
while i > 0:
i=i+1
if i < 7: continue
if i > 12: break
print (i, end = ' ')
[συμπληρώθηκε από IMG_1682.jpg· το κάτω μέρος του τμήματος (γ) είναι κομμένο στο IMG_1681.jpg]
IMG_1684.jpg¶
ΘΕΜΑ 4 – Εμβέλεια και Μεταβίβαση Παραμέτρων (20%)¶
Δίνεται το παρακάτω πρόγραμμα σε μια γλώσσα τύπου Pascal που χρησιμοποιεί το στατικό κανόνα εμβέλειας:
program MAIN;
var i, a: integer;
function P(j: integer): integer;
function Q(k: integer): integer;
begin
if k < 4
then i:= P(k);
Q:= k
else write(k);
Q:= 0
end;
begin
j:= j + j;
P:= Q(j);
end;
BEGIN
i:= 1;
a:= P(i);
write(i, a);
END.
write, στις παρακάτω περιπτώσεις τρόπου μεταβίβασης παραμέτρων; Παρουσιάστε τις αλλαγές τιμών όλων των μεταβλητών κατά τη διαδικασία υπολογισμού στις δύο περιπτώσεις.
i. Κλήση με τιμή (call by value).
ii. Κλήση με αναφορά (call by reference).
ΘΕΜΑ 5 – Συναρτησιακός Προγραμματισμός (20%)¶
(α) Στον λ-λογισμό, μπορούμε να αναπαραστήσουμε τις λογικές τιμές true και false ως εξής: $\(\text{true} = \lambda x.\ \lambda y.\ x\)$ $\(\text{false} = \lambda x.\ \lambda y.\ y\)$ Η αναπαράσταση του λογικού τελεστή not με την έκφραση \(\text{not} = \lambda z.\ z\ \text{false}\ \text{true}\), επιφέρει το επιθυμητό αποτέλεσμα; (Σημείωση: αρκεί να αποδείξετε ότι \(\text{not true} = \text{false}\) και \(\text{not false} = \text{true}\).)
(β) Σε μία γλώσσα συναρτησιακού προγραμματισμού, θεωρείστε τους κάτωθι κανόνες αναγωγής (reduction rules). - Built-in rules: addition, substraction, multiplication, division - User supplied rules:
square x = x * x
double x = x + x
sum [ ] = 0
sum (x:xs) = x + sum [x+1:xs]
square (sum [1:100]) με πρόθυμη (eager evaluation) και οκνηρή (lazy evaluation) στρατηγική αποτίμησης. Πόσα βήματα (reductions) απαιτεί η κάθε στρατηγική; Ποια είναι η πιο αποδοτική;
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (antigravity-gemini, gemini-3.7-flash, sonnet), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2022-09¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: λύθηκε με βάση τις φωτογραφίες του θέματος· μία λύση AI
Στη φωτογραφία IMG_1681.jpg, η αρχή του Θέματος 1 καλύπτεται από την εργαλειοθήκη του επεξεργαστή κειμένου και διακρίνεται μόνο το εξής κείμενο:
«…δυαδικούς αριθμούς μήκους τουλάχιστον 5 ψηφίων, οι οποίοι αρχίζουν με 01 και τελειώνουν με 10. Ενδιαμέσως των δύο ζευγαριών υπάρχει ακολουθία δυαδικών ψηφίων οποιουδήποτε μήκους (τουλάχιστον ένα). Π.χ. 01010, 01110110. Παρουσιάστε και μια αντίστοιχη κανονική έκφραση.»
Υποθέτουμε ότι ζητείται η κανονική έκφραση (και ενδεχομένως αυτόματο/γραμματική) για τη συγκεκριμένη γλώσσα επί του αλφαβήτου \(\Sigma = \{0, 1\}\).
Κανονική Έκφραση (Regular Expression)¶
Η γλώσσα απαιτεί:
1. Πρόθεμα μήκους 2: 01
2. Ενδιάμεση συμβολοσειρά οποιουδήποτε μήκους τουλάχιστον 1: \((0 \mid 1)^+\) ή ισοδύναμα \((0 \mid 1)(0 \mid 1)^*\)
3. Επίθεμα μήκους 2: 10
Επομένως, το συνολικό μήκος είναι \(2 + (\ge 1) + 2 \ge 5\) ψηφία.
Η κανονική έκφραση είναι: $\(01(0 \mid 1)^+ 10 \quad \text{ή} \quad 01(0 \mid 1)(0 \mid 1)^* 10\)$
Επαλήθευση¶
01010: Πρόθεμα01, ενδιάμεσο0(μήκος 1), επίθεμα10. Μήκος 5 \(\ge 5\). Αποδεκτή.01110110: Πρόθεμα01, ενδιάμεσο1101(μήκος 4), επίθεμα10. Μήκος 8 \(\ge 5\). Αποδεκτή.0110: Μήκος 4, δεν διαθέτει ενδιάμεσο ψηφίο (απαιτείται τουλάχιστον ένα). Απορρίπτεται.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
(α) Ο πίνακας A είναι static και καθολικός στο αρχείο ⇒ δεσμεύεται στη στατική περιοχή δεδομένων (αρχικοποιημένα στο μηδέν, .bss), όχι στη στοίβα ούτε στο σωρό, και υπάρχει σε όλη τη διάρκεια του προγράμματος. Μέγεθος: \(1024\cdot1024\cdot8 = 8\,388\,608\) bytes = 8 MiB. Οι i, j είναι τοπικές (automatic): στη στοίβα (ή σε καταχωρητές), από 4 bytes (τυπικά) η καθεμία, δηλ. 8 bytes. Το N είναι μακροεντολή (δεν δεσμεύει μνήμη).
Πρόσβαση: η C αποθηκεύει τους πίνακες κατά γραμμές (row-major): το \(A[i][j]\) βρίσκεται στη διεύθυνση βάσης \(+ (i\cdot N + j)\cdot 8\). Στον βρόχο ο εσωτερικός δείκτης είναι ο i (πρώτη διάσταση), άρα διαδοχικές προσβάσεις απέχουν \(N\cdot8 = 8192\) bytes.
Απόδοση: η πρόσβαση με μεγάλο βήμα καταστρέφει τη χωρική τοπικότητα (κάθε πρόσβαση σε νέα γραμμή cache, πολλά cache και TLB misses, δεν αξιοποιείται η prefetch). Λύση: εναλλαγή των βρόχων (εξωτερικός i, εσωτερικός j) ώστε οι προσβάσεις να είναι διαδοχικές. Παρατήρηση: η (i*j)/(i+j+1) είναι ακέραια διαίρεση (και τα δύο μέλη int) και μετά μετατρέπεται σε double, οπότε τα αποτελέσματα είναι ακέραια.
(β) Ο δείκτης p είναι μη αρχικοποιημένος και δείχνει σε τυχαία διεύθυνση (αν η μεταβλητή είναι τοπική· αν ήταν καθολική θα ήταν NULL). Η *p = 15 είναι απροσδιόριστη συμπεριφορά (undefined behavior): τυπικά σφάλμα τμηματοποίησης (segmentation fault) ή, χειρότερα, αθόρυβη φθορά άλλων δεδομένων. Δεν υπάρχει έξοδος. Σωστά: int x; int *p = &x; ή p = malloc(sizeof(int)); πριν από την εκχώρηση.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
(α) Το range(12, 2, -2) δίνει 12, 10, 8, 6, 4. Τυπώνεται x+2, και όταν x==4 τυπώνεται και γίνεται break. Έξοδος: 14 12 10 8 6.
(β) Η x παίρνει τιμές τις συμβολοσειρές '1', '2', … Η x*x είναι πολλαπλασιασμός συμβολοσειράς με συμβολοσειρά, που δεν ορίζεται ⇒ TypeError στην πρώτη επανάληψη (μήνυμα «can't multiply sequence by non-int of type 'str'»), χωρίς καμία έξοδο.
(γ) Ξεκινά \(i=5\). Στην πρώτη επανάληψη \(i=6<7\) ⇒ continue. Μετά \(i=7,8,\dots,12\): δεν ισχύει i<7 ούτε i>12 ⇒ τυπώνονται. Για \(i=13\) ισχύει i>12 ⇒ break. Έξοδος: 7 8 9 10 11 12.
Θέμα 4¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν
Ο κώδικας της Q όπως δίνεται (then i:= P(k); Q:= k else …) δεν είναι έγκυρη Pascal (το ; πριν το else και χωρίς begin…end). Ερμηνεύουμε: αν \(k<4\): i:=P(k); Q:=k, αλλιώς: write(k); Q:=0.
(α) Περιβάλλοντα αναφοράς (στατικός κανόνας): - MAIN: τοπικά {i, a, P}· μη τοπικά κανένα· καθολικά {i, a, P}. - P: τοπικά {j, Q}· μη τοπικά {i, a, P}. - Q (δηλωμένη μέσα στην P): τοπικά {k}· μη τοπικά {j, Q (από την P), i, a, P}.
(β) Στοίβα εκτέλεσης στην τελευταία (δεύτερη) κλήση της Q (το αποτέλεσμα είναι ίδιο και στις δύο μεταβιβάσεις ως προς τη δομή· οι τιμές διαφέρουν):
AR-MAIN(i,a) -> AR-P#1(j) -> AR-Q#1(k) -> AR-P#2(j) -> AR-Q#2(k)
Static chain: P#1, P#2 → AR-MAIN· Q#1 → P#1, Q#2 → P#2 (κάθε Q δείχνει στο P που την κάλεσε, γιατί είναι δηλωμένη μέσα σε αυτή). Η αλυσίδα κλήσεων (dynamic chain) είναι η σειρά της στοίβας.
Τιμές (κλήση με τιμή): i=1, P#1.j=2, Q#1.k=2, P#2.j=4, Q#2.k=4.
(γ)
i. Κλήση με τιμή: a:=P(i): \(j=1\), \(j:=2\), Q(2): \(k=2<4\) ⇒ i:=P(2): \(j=2\), \(j:=4\), Q(4): \(k=4\), όχι \(<4\) ⇒ write(4), \(Q:=0\), άρα \(P:=0\) και i:=0. Επιστρέφοντας στην Q#1: \(Q:=k=2\), \(P:=2\), a:=2. Τελικό write(i,a) ⇒ 0 2. Εκτυπώνεται: 4 και μετά 0 2 (δηλ. 4 0 2).
ii. Κλήση με αναφορά: j≡i. \(j:=j+j\) ⇒ \(i=2\). Q(j): \(k\)≡\(i\) (2<4) ⇒ i:=P(k): νέο \(j'\)≡\(k\)≡\(i\), \(j':=j'+j'\) ⇒ \(i=4\). Q(j'): \(k'\)≡\(i=4\) ⇒ write(4), \(Q:=0\), \(P:=0\). Η ανάθεση i:=0 ⇒ \(i=0\). Τώρα η Q#1 κάνει \(Q:=k\), αλλά το \(k\) είναι ψευδώνυμο του \(i=0\) ⇒ \(Q:=0\), \(P:=0\), a:=0. write(i,a) ⇒ 0 0. Εκτυπώνεται: 4 και μετά 0 0 (δηλ. 4 0 0).
Θέμα 5¶
Αξιοπιστία: 2 από 3 ανεξάρτητες λύσεις συμφωνούν (η άλλη διαφωνούσε) · εμπιστοσύνη λύτη: υψηλή
(α)¶
Δίνονται: - \(\text{true} = \lambda x.\ \lambda y.\ x\) - \(\text{false} = \lambda x.\ \lambda y.\ y\) - \(\text{not} = \lambda z.\ z\ \text{false}\ \text{true}\)
-
Υπολογισμός \(\text{not true}\): $\(\begin{aligned} \text{not true} &= (\lambda z.\ z\ \text{false}\ \text{true})\ \text{true} \\ &\to_\beta \text{true}\ \text{false}\ \text{true} \\ &= (\lambda x.\ \lambda y.\ x)\ \text{false}\ \text{true} \\ &\to_\beta (\lambda y.\ \text{false})\ \text{true} \\ &\to_\beta \text{false} \end{aligned}\)$
-
Υπολογισμός \(\text{not false}\): $\(\begin{aligned} \text{not false} &= (\lambda z.\ z\ \text{false}\ \text{true})\ \text{false} \\ &\to_\beta \text{false}\ \text{false}\ \text{true} \\ &= (\lambda x.\ \lambda y.\ y)\ \text{false}\ \text{true} \\ &\to_\beta (\lambda y.\ y)\ \text{true} \\ &\to_\beta \text{true} \end{aligned}\)$
Επομένως, ο τελεστής επιφέρει πλήρως το επιθυμητό αποτέλεσμα.
(β)¶
Δίνεται η έκφραση square (sum [1:100]) (όπου [1:100] συμβολίζει τη λίστα των αριθμών \(1, 2, \dots, 100\), με άθροισμα \(S = \sum_{k=1}^{100} k = 5050\)). Ο υπολογισμός του αθροίσματος της λίστας απαιτεί 100 αναγωγές πρόσθεσης και μία για την κενή λίστα (σύνολο 101 βήματα αναγωγής για το sum).
1. Πρόθυμη αποτίμηση (Eager Evaluation / Call-by-value / Applicative Order)¶
Στην πρόθυμη αποτίμηση, αποτιμάται πρώτα το όρισμα της συνάρτησης και στη συνέχεια εφαρμόζεται ο ορισμός της συνάρτησης:
$\(\begin{aligned}
\text{square } (\text{sum } [1:100])
&\to^* \text{square } (5050) \quad (\text{μέσω των κανόνων του sum: 101 βήματα}) \\
&\to 5050 * 5050 \quad (\text{εφαρμογή του κανόνα square: 1 βήμα}) \\
&\to 25.502.500 \quad (\text{built-in multiplication: 1 βήμα})
\end{aligned}\)$
- Συνολικά βήματα: \(101 + 1 + 1 = 103\) αναγωγές.
- Το όρισμα sum [1:100] αποτιμάται μόνο μία φορά.
2. Οκνηρή αποτίμηση (Lazy Evaluation)¶
- Χωρίς διαμοιρασμό (Call-by-name / Normal Order): Αναπτύσσεται πρώτα η εξωτερική συνάρτηση: $\(\text{square } (\text{sum } [1:100]) \to (\text{sum } [1:100]) * (\text{sum } [1:100])\)$ Στη συνέχεια, για να εκτελεστεί ο πολλαπλασιασμός, πρέπει να αποτιμηθούν και τα δύο ορίσματα ξεχωριστά: $\(\begin{aligned} &\to^* 5050 * (\text{sum } [1:100]) \quad (101 \text{ βήματα}) \\ &\to^* 5050 * 5050 \quad (101 \text{ βήματα}) \\ &\to 25.502.500 \quad (1 \text{ βήμα}) \end{aligned}\)$
-
Συνολικά βήματα: \(1 + 101 + 101 + 1 = 204\) αναγωγές (διπλάσιος υπολογισμός του
sum). -
Με διαμοιρασμό (Lazy evaluation με Graph Reduction / Call-by-need): Η αντικατάσταση του
square x = x * xδημιουργεί δύο δείκτες στον ίδιο κόμβο γραφήματος της έκφρασηςsum [1:100]: $\(\text{square } (\text{sum } [1:100]) \to x * x \quad (\text{όπου } x = \text{sum } [1:100])\)$ Κατά την αποτίμηση του πρώτου \(x\), υπολογίζεται το \(5050\) (101 βήματα) και το αποτέλεσμα αποθηκεύεται στον κοινό κόμβο (memoization/sharing). Το δεύτερο \(x\) διαβάζει απευθείας την τιμή \(5050\) (0 επιπλέον βήματα αναγωγής τουsum). - Συνολικά βήματα: \(1 + 101 + 1 = 103\) αναγωγές (συν το κόστος διαχείρισης των δεικτών γραφήματος).
Σύγκριση Αποδοτικότητας¶
Η πρόθυμη αποτίμηση (eager evaluation) είναι πιο αποδοτική: - Αποφεύγει τον διπλό υπολογισμό του ορίσματος που εμφανίζεται στην αποτίμηση κατ' όνομα (normal order/call-by-name). - Ακόμα και σε σύγκριση με την πλήρη οκνηρή αποτίμηση με διαμοιρασμό (graph reduction), η πρόθυμη είναι ταχύτερη, καθώς δεν επιβαρύνεται με το επιπλέον υπολογιστικό κόστος (overhead) κατασκευής των αναστολών (thunks/closures), διαχείρισης του γραφήματος και έμμεσης προσπέλασης δεικτών στη μνήμη.