Εθνικό Μετσόβιο Πολυτεχνείο
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών

Γλώσσες Προγραμματισμού ΙΙ

https://courses.softlab.ntua.gr/pl2/

Γλώσσες Προγραμματισμού ΙΙ

Κατ' επιλογήν υποχρεωτικό μάθημα ροής Λ, 9ου εξαμήνου, κωδικός 3.4.3320.9

Εξάμηνο:

Χειμερινό 2020

Διδάσκων:

Νίκος Παπασπύρου

()

γρ. 1.1.21

τηλ: 210-772-3393

Ανακοινώσεις | Υλικό: Γενικά, Moodle, MS Teams, Ασκήσεις, Διαφάνειες, Παλαιότερα έτη
Διαλέξεις: 7/10 | 14/10 | 21/10 | 4/11 | 11/11 | 18/11 | 25/11 | 2/12 | 9/12 | 16/12 | 23/12 | 13/1

Ανακοινώσεις

29/9/2021	Κατά το ακαδημαϊκό έτος 2021-22, το μάθημα δε θα διδαχθεί.
16/12/2020	Την Τετάρτη 23/12 θα γίνει το τελευταίο μάθημα της (ημερολογιακής) χρονιάς. Θα ακολουθήσει άλλο ένα την Τετάρτη 13/1, την τελευταία βδομάδα του εξαμήνου.
7/10/2020	ΠΡΟΣΟΧΗ: Συνδεθείτε στο συνεργατικό σύστημα ηλεκτρονικής μάθησης (Moodle) με τους κωδικούς σας του ΕΜΠ και εγγραφείτε στο μάθημα Γλώσσες Προγραμματισμού ΙΙ. Προσέξτε ότι το σύστημα αυτό είναι διαφορετικό από το Moodle που χρησιμοποιήθηκε τις προηγούμενες χρονιές (παλιό Moodle), το οποίο ίσως θα θέλατε επίσης να συμβουλεύεστε.
7/10/2020	Οι διαλέξεις του μαθήματος άρχισαν σήμερα. Θα διεξάγονται Τετάρτη, ώρα 11:45-14:30. Κάποιες από τις διαλέξεις θα δοθούν από τον Κωστή Σαγώνα που για τυπικούς λόγους δεν είναι επίσημα διδάσκων του μαθήματος. Λόγω των περιορισμών εξαιτίας του COVID-19, οι διαλέξεις θα γίνονται online μέσω της πλατφόρμας Microsoft Teams. Αν δεν είστε εξοικειωμένοι, ακολουθήστε τις οδηγίες σύνδεσης και χρήσης. Ο κωδικός του MS Teams για σύνδεση με το μάθημα είναι: ezu0g4i

Υλικό

Γενικά

Ενημερωτικό φυλλάδιο ( PDF).
Ώρες γραφείου διδάσκοντα: Παρασκευή 10:00–12:00.
Εκτενής βιβλιογραφία και υλοποιήσεις γλωσσών.

Ασκήσεις

Οι ασκήσεις πρέπει να παραδοθούν στους διδάσκοντες σε ηλεκτρονική μορφή μέσω του συνεργατικού συστήματος ηλεκτρονικής μάθησης Moodle. Η προθεσμία παράδοσης θα τηρείται αυστηρά. Έχετε δικαίωμα να καθυστερήσετε το πολύ μία άσκηση.

Αριθμός	Αντικείμενο	Προθεσμία παράδοσης	Εκφώνηση	Επιπλέον υλικό
1	Haskell για ενεργειακούς	29/11/2020	PDF
2	Περιγράμματα και δέντρα Fibonacci	29/11/2020	PDF	Υπόδειγμα προς συμπλήρωση.
3	Erlang για ραλλίστες	10/1/2021	PDF	rallyomatic.beam
4	Erlang και property-based testing	10/1/2021	PDF	vectors.beam
5	Παραλληλισμός σε Erlang ή Haskell	10/1/2021	PDF	reverse_grader.beam ή reverse_hash.hs
6	Συστήματα τύπων	10/1/2021	PDF
7	Εξαγωγή τύπων	14/3/2021	PDF	Διάβασμα της εισόδου, σε Haskell.
8	Αξιωματική σημασιολογία	14/3/2021	PDF
9	Εικονικές μηχανές και συλλογή σκουπιδιών	14/3/2021	PDF
10	Γλώσσες σεναρίων	14/3/2021	PDF
11	Στατική ανάλυση	14/3/2021	PDF

Διαφάνειες

Οι διαφάνειες που θα χρησιμοποιούνται στις διαλέξεις είναι διαθέσιμες από την παρούσα σελίδα για τη διευκόλυνση των σπουδαστών, ώστε αυτοί να μη χρειάζεται να κρατούν εκτενείς σημειώσεις κατά τη διάρκεια των μαθημάτων. Η ύλη των διαφανειών παρουσιάζεται αναλυτικά στις σημειώσεις του μαθήματος.

Η γλώσσα Haskell: PDF ή PDF
Παραλληλισμός και ταυτοχρονισμός στη Haskell: ( PDF και PDF) ή ( PDF και PDF)
Ο κώδικας και ένα εξαιρετικό σχετικό tutorial είναι διαθέσιμα από τον Simon Marlow, συγγραφέα και ενός σχετικού βιβλίου.
Η γλώσσα Erlang (σειριακό μέρος): PDF.
Η γλώσσα Erlang (ταυτόχρονισμός και κατανεμημένη εκτέλεση): PDF.
Έλεγχος προγραμμάτων με τη γλώσσα Erlang: PDF.
Συστήματα τύπων: PDF ή PDF
Παραλληλισμός στην Erlang και το σύστημα του χρόνου εκτέλεσής της: PDF.
Αξιωματική σημασιολογία: PDF ή PDF
Λάμβδα λογισμός και εξαγωγή τύπων: PDF ή PDF
Εισαγωγή στη στατική ανάλυση προγραμμάτων: PDF
Εικονικές μηχανές και οι διερμηνείς τους: PDF ή PDF
Δυναμική διαχείριση μνήμης: PDF ή PDF

Παλαιότερα έτη

Σελίδα του μαθήματος για τα ακαδημαϊκά έτη: 2019-20, 2018-19, 2017-18, 2016-17, 2015-16, 2014-15, 2013-14, 2012-13, 2011-12, 2010-11, 2009-10, 2008-09, 2007-08, 2006-07, 2005-06, 2004-05, 2003-04, 2002-03.

Διαλέξεις

Παράδοση 7/10/2020

H γλώσσα Haskell: σειριακό κομμάτι
- Εισαγωγή στη Haskell
- Τύποι, πολυμορφισμός και συμπερασμός τύπων της Haskell
- Συναρτήσεις υψηλής τάξης και ανώνυμες συναρτήσεις
- List comprehensions
- Προγραμματισμός με συναρτήσεις υψηλής τάξης
- Qualified types και κλάσεις τύπων (type classes)
- Οκνηρή αποτίμηση (lazy evaluation)
- Άπειρες λίστες και παραδείγματα χειρισμού τους
- Προγραμματισμός με άπειρες λίστες
Μαγνητοσκοπημένη διάλεξη

Παράδοση 14/10/2020

H γλώσσα Haskell: σειριακό κομμάτι (δεύτερο μέρος)
- Μια πιο βαθειά ματιά στην οκνηρή αποτίμηση
- Τρόποι ελέγχου της οκνηρίας με χρήση seq
- Space leaks και τρόποι αποφυγής τους
- Παράδειγμα, tree DFS traversal: dfs.hs
- Παράδειγμα, tree BFS traversal: bfs.hs
- Μια πιο βαθειά ματιά στα Monads
  - Tree DFS traversal, με State monad: dfm.hs
Μαγνητοσκοπημένη διάλεξη

Παράδοση 21/10/2020

Παραλληλισμός και ταυτοχρονισμός στη Haskell
- Εισαγωγή
- Παραλληλισμός
  - Evaluation strategies
  - Par monad
Μαγνητοσκοπημένη διάλεξη

Παράδοση 4/11/2020

Παραλληλισμός και ταυτοχρονισμός στη Haskell (δεύτερο μέρος)
- Ταυτοχρονισμός
  - IO monad και MVar
  - Software Transactional Memory
Μαγνητοσκοπημένη διάλεξη

Η γλώσσα Erlang: σειριακό κομμάτι
- Εισαγωγή στην Erlang
- Όροι και τύποι δεδομένων της Erlang
- List και bit string comprehensions
- Εξαιρέσεις και χειρισμός τους
- Το εργαλείο στατικής ανάλυσης Dialyzer
Μαγνητοσκοπημένη διάλεξη

Παράδοση 11/11/2020

Έλεγχος προγραμμάτων με τη γλώσσα Erlang
- Unit testing με χρήση του εργαλείου EUnit
- Property-based testing και PropEr
Η γλώσσα Erlang: ταυτοχρονισμός και κατανεμημένη εκτέλεση
- Διεργασίες και ταυτόχρονη εκτέλεση
- Ανταλλαγή μηνυμάτων
- Επιλεκτική λήψη μηνυμάτων
- Αλλαγή κώδικα κατά τη διάρκεια της εκτέλεσης
- Κατανεμημένη εκτέλεση προγραμμάτων
Μαγνητοσκοπημένη διάλεξη

Παράδοση 18/11/2020

Συστήματα τύπων
- Εισαγωγή
- Βασικοί τύποι
  - Σύνταξη
  - Λειτουργική σημασιολογία
  - Κανόνες τύπων
  - Ιδιότητες του συστήματος τύπων
- Τύποι συναρτήσεων
Μαγνητοσκοπημένη διάλεξη

Παράδοση 25/11/2020

Συστήματα τύπων (συνέχεια)
- Απλές επεκτάσεις
  - Ο τύπος μονάδας — Unit
  - Ακολουθιακή αποτίμηση
  - Απόδοση ονομάτων — δομή let
  - Ζεύγη
  - Αθροίσματα
  - Αναδρομή
    - Τελεστής fix
    - Δομή letrec
- Αναφορές
- Εξαιρέσεις
Μαγνητοσκοπημένη διάλεξη

Παράδοση 2/12/2020

Η γλώσσα Erlang: παραλληλισμός και το σύστημα του χρόνου εκτέλεσής της
- Παράλληλη εκτέλεση προγραμμάτων στην Erlang
- Τεχνικές βελτίωσης της επίδοσης παράλληλης εκτέλεσης
- Επισκόπηση του συστήματος χρόνου εκτέλεσης της Erlang
Μαγνητοσκοπημένη διάλεξη

Συστήματα τύπων (συνέχεια)
- Υποτύποι
- Αναδρομικοί τύποι
- Πολυμορφισμός 2ης τάξης
- Πολυμορφισμός υψηλής τάξης
- Υπαρξιακοί τύποι
- Εξαρτώμενοι τύποι
Μαγνητοσκοπημένη διάλεξη

Παράδοση 9/12/2020

Αξιωματική σημασιολογία και επαλήθευση προγραμμάτων
- Τριάδες Hoare
- Μια απλή προστακτική γλώσσα
- Frama-C
- Παραδείγμα: [εύρεση ελάχιστου στοιχείου]: findmin.cpp
- Παραδείγμα: ποιος βλέπει την πόρτα του κυλικείου
  - μέχρι εκεί που φτάσαμε: whocansee.cpp
  - (*) με αλγόριθμο O(n): kylikeio.c
- (*) Παραδείγμα: υπολογισμός παραγοντικού
  - με επανάληψη: fact.c
  - με επανάληψη, ξεκινώντας από i=2: fact2.c
- (*) Παράδειγμα: εύρεση δύο στοιχείων πίνακα με δοθέν άθροισμα
  - με αλγόριθμο Ο(n²): sumx2.c
- (*) Παράδειγμα: υπολογισμός ακέραιας δύναμης (άσκηση 2008-09)
  - με απλή επανάληψη: pow-simple.c
  - με διαδοχικό τετραγωνισμό: pow.c
- (*) Παράδειγμα: έλεγχος πρώτου αριθμού (άσκηση 2009-10)
  - με επανάληψη, διαιρώντας με όλους τους προηγούμενους: prime.c
- (*) Παράδειγμα: υπολογισμός μέγιστου κέρδους (άσκηση 2010-11)
  - με αλγόριθμο Ο(n²): profit2.c
  - με αλγόριθμο Ο(n): profit.c
Μαγνητοσκοπημένη διάλεξη

Παράδοση 16/12/2020

Εξαγωγή τύπων (type inference)
- Παραδείγματα σε OCaml
- Εξαγωγή τύπων στην πράξη
- Περιορισμοί και επίλυση
- Εφαρμογή στο λ-λογισμό
Μαγνητοσκοπημένη διάλεξη

Εισαγωγή στη στατική ανάλυση προγραμμάτων
- Εφαρμογές της στατικής ανάλυσης
- Η ανάγκη για στατική ανάλυση κατά προσέγγιση (approximation)
- Μη αποφασισιμότητα (undecidability) της ορθότητας προγραμμάτων
- Η σύνταξη της γλώσσας TIP και κάποια προγράμματα
- Τύποι της TIP
- Περιορισμοί τύπων και επίλυσή τους μέσω ενοποίησης
- Παραδείγματα ορθών προγραμμάτων που η στατική ανάλυση τύπων απορρίπτει
- Παραδείγματα προγραμμάτων με λάθη χρόνου εκτέλεσης αλλά χωρίς λάθη τύπων
Μαγνητοσκοπημένη διάλεξη

Παράδοση 23/12/2020

Εικονικές μηχανές και οι διερμηνείς τους
- Εικονικές μηχανές
  - Ορισμός και παραδείγματα
  - Πλεονεκτήματα και μειονεκτήματα
  - Επιλογές σχεδιασμού και συστατικά των εικονικών μηχανών
  - Τεχνικές υλοποίησης εικονικών μηχανών
- Διερμηνείς
  - Μορφές διερμηνέων
  - Δομή των bytecode interpreters
  - Άμεσα και έμμεσα νηματικοί διερμηνείς (threaded code interpreters)
  - Συγχώνευση και εξειδίκευση εντολών
- Μαγνητοσκοπημένη διάλεξη
Δυναμική διαχείριση μνήμης
- Γλώσσες προγραμματισμού με άμεση και έμμεση δέσμευση και αποδέσμευση μνήμης
- Συλλογή σκουπιδιών
- Ανακύκλωση μνήμης μέσω του αλγόριθμου mark-and-sweep
- Ανακύκλωση μνήμης μέσω μετρήματος αναφορών (reference counting)
- Ανακύκλωση μνήμης μέσω αντιγραφής – ο αλγόριθμος του Cheney
- Συλλογή σκουπιδιών σε γενεές (generational garbage collection)
- (*) Αυξητικοί, ταυτόχρονοι και συλλέκτες σκουπιδιών πραγματικού χρόνου (incremental, concurrent, and real-time garbage collection)
  - Μαρκάρισμα με τρία χρώματα (tricolor marking)
  - Φράγματα ανάγνωσης και γραφής (read and write barriers)
  - Ο αλγόριθμος του Baker
- Συνεργασία του συλλέκτη σκουπιδιών με τον compiler
- Συντηρητική συλλογή σκουπιδιών (conservative garbage collection)
- Μαγνητοσκοπημένη διάλεξη μέρος 1, από μάθημα μεταγλωττιστών
- Μαγνητοσκοπημένη διάλεξη μέρος 2

Παράδοση 13/1/2021

Γλώσσες σεναρίων
- Εισαγωγή
- Περιοχές εφαρμογών
- Περιήγηση με τη Ruby
- (*) Παραδείγματα
- Σενάρια στον παγκόσμιο ιστό
- Παραδείγματα
- (*) Απλό παιχνίδι με τετράγωνα αριθμών
- (*) Απλό παιχνίδι με πρώτους αριθμούς
- (*) Πρόγραμμα σε Python που διαβάζει λήμματα από τη wikipedia: terms.py και terms.txt
Μαγνητοσκοπημένη διάλεξη

Τελευταία αλλαγή: 13/10/2020, 11:08 UTC.