Εθνικό Μετσόβιο Πολυτεχνείο Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών Γλώσσες Προγραμματισμού ΙΙ https://courses.softlab.ntua.gr/pl2/

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

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

Ανακοινώσεις | Υλικό: Γενικά, Moodle, Ασκήσεις, Διαφάνειες, Παλαιότερα έτη
Διαλέξεις: 6/10 | 13/10 | 20/10 | 27/10 | 3/11 | 10/11 | 24/11 | 1/12 | 8/12 | 15/12 | 22/12 | 23/12 | 12/1 | 13/1 | 19/1

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

Υλικό

Γενικά

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

Ασκήσεις

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

Αριθμός	Αντικείμενο	Προθεσμία παράδοσης	Εκφώνηση	Επιπλέον υλικό
1	Haskell	17/11/2016	PDF (229KB)	Διάβασμα της εισόδου για παλιότερη άσκηση, με String και με ByteString.
2	Συστήματα τύπων	1/12/2016	PDF (230KB)
3	Αξιωματική σημασιολογία	22/12/2016	PDF (152KB)
4	Εξαγωγή τύπων	12/1/2017	PDF (148KB)	Διάβασμα της εισόδου, σε Haskell.
5	Δηλωτική σημασιολογία	12/1/2017	PDF (300KB)
6	Εικονικές μηχανές	19/3/2017	PDF (264KB)
7	Γλώσσες σεναρίων	19/3/2017	PDF (257KB)
8	Συλλογή σκουπιδιών	4/6/2017	PDF (133KB)

Διαφάνειες

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

• Η γλώσσα Haskell:
  • Μέρος 1ο: εισαγωγή:  PDF (181KB)
  • Μέρος 2ο: type classes, laziness, IO, modules:  PDF (256KB)
  • Μέρος 3ο: μια πιο βαθειά ματιά στην οκνηρή αποτίμηση:  PDF (162KB)
• Συστήματα τύπων:  PDF (406KB) ή  PDF (357KB)
• Αξιωματική σημασιολογία:  PDF (175KB) ή  PDF (169KB)
• Εξαγωγή τύπων:  PDF (251KB) ή  PDF (273KB)
• Δηλωτική σημασιολογία:  PDF (277KB) ή  PDF (256KB)
• Η γλώσσα Erlang
  • Μέρος 1ο: σειριακή εκτέλεση και property-based testing:  PDF (157KB) ή  PDF (151KB)
  • Μέρος 2ο: ταυτοχρονισμός, κατανεμημένη και παράλληλη εκτέλεση:  PDF (182KB) ή  PDF (175KB)
• Δυναμική διαχείριση μνήμης:  PDF (3.9MB) ή  PDF (3.4MB)
• Εικονικές μηχανές και οι διερμηνείς τους:  PDF (251KB) ή  PDF (273KB)

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

Σελίδα του μαθήματος για τα ακαδημαϊκά έτη: 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.

Διαλέξεις

Παράδοση 6/10/2016

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

Παράδοση 13/10/2016

• H γλώσσα Haskell: σειριακό κομμάτι (δεύτερο μέρος)
  • Προγραμματισμός με άπειρες λίστες
  • IO και Monads
  • Modules
  • Μια πιο βαθειά ματιά στην οκνηρή αποτίμηση
  • Lazy IO
  • Τρόποι ελέγχου της οκνηρίας με χρήση seq
  • Space leaks και τρόποι αποφυγής τους

Παράδοση 20/10/2016

• Η γλώσσα Haskell (τρίτο μέρος)
  • Άπειρες λίστες
    • Προγραμματισμός με οκνηρή αποτίμηση (συνέχεια)
    • Παράδειγμα, αρίθμηση σε διάσχιση κατά βάθος και κατά πλάτος: dfs-bfs.hs
  • Monads
    • Παράδειγμα, αρίθμηση σε διάσχιση κατά βάθος (ξανά)
    • Με ένα χειροποίητο state monad: dfs-m1.hs
    • Με το state monad της βιβλιοθήκης: dfs-m2.hs

Παράδοση 27/10/2016

• Συστήματα τύπων
  • Εισαγωγή
  • Βασικοί τύποι
    • Σύνταξη
    • Λειτουργική σημασιολογία
    • Κανόνες τύπων
    • Ιδιότητες του συστήματος τύπων
  • Τύποι συναρτήσεων
  • Απλές επεκτάσεις
    • Ο τύπος μονάδας — Unit
    • Ακολουθιακή αποτίμηση
    • Απόδοση ονομάτων — δομή let
    • Ζεύγη
    • Αθροίσματα
    • Αναδρομή
      • Τελεστής fix
      • Δομή letrec

Παράδοση 3/11/2016

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

Παράδοση 10/11/2016

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

Παράδοση 1/12/2016

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

Παράδοση 15/12/2016

• Σημασιολογία
• Δηλωτική σημασιολογία
  • Μια απλή γλώσσα δυαδικών συμβολοσειρών
  • Μια απλή προστακτική γλώσσα
    • Σημασιολογία αριθμητικών και λογικών εκφράσεων
    • Σημασιολογία εντολών
    • Μεταβλητές και αναθέσεις
    • Αόριστες επαναλήψεις, εντολή while
    • (*) Υλοποίηση σε Haskell: densem.hs
• Θεωρία πεδίων
  • Ορισμοί
  • Κατασκευές πεδίων
  • Μονότονες και συνεχείς συναρτήσεις
  • Θεώρημα ελάχιστου σταθερού σημείου
• Δηλωτική σημασιολογία (συνέχεια)
  • Μια απλή προστακτική γλώσσα (ξανά)
  • Σημασιολογία του λ-λογισμού

Παράδοση 22/12/2016

• Γλώσσες σεναρίων
  • Εισαγωγή
  • Περιοχές εφαρμογών
  • Περιήγηση με τη Ruby
  • Περιήγηση με την Python
  • Παραδείγματα

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

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

Παράδοση 12/1/2017

• H γλώσσα Erlang: σειριακό κομμάτι
  • Εισαγωγή στην Erlang
  • Όροι και τύποι δεδομένων της Erlang
  • List και bit string comprehensions
  • Εξαιρέσεις και χειρισμός τους
  • Το εργαλείο στατικής ανάλυσης Dialyzer
  • Unit testing με χρήση του εργαλείου EUnit
  • Property-based testing και PropEr
• H γλώσσα Erlang: ταυτοχρονισμός, κατανεμημένη και παράλληλη εκτέλεση
  • Διεργασίες και ταυτόχρονη εκτέλεση
  • Ανταλλαγή μηνυμάτων
  • Επιλεκτική λήψη μηνυμάτων
  • Αλλαγή κώδικα κατά τη διάρκεια της εκτέλεσης
  • Κατανεμημένη εκτέλεση προγραμμάτων

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

• Δυναμική διαχείριση μνήμης
  • Γλώσσες προγραμματισμού με άμεση και έμμεση δέσμευση και αποδέσμευση μνήμης
  • Συλλογή σκουπιδιών
  • Ανακύκλωση μνήμης μέσω του αλγόριθμου 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)

Παράδοση 19/1/2017

• Εικονικές μηχανές και οι διερμηνείς τους
  • Εικονικές μηχανές
    • Ορισμός και παραδείγματα
    • Πλεονεκτήματα και μειονεκτήματα
    • Επιλογές σχεδιασμού και συστατικά των εικονικών μηχανών
    • Τεχνικές υλοποίησης εικονικών μηχανών
  • Διερμηνείς
    • Μορφές διερμηνέων
    • Δομή των bytecode interpreters
    • Άμεσα και έμμεσα νηματικοί διερμηνείς (threaded code interpreters)
    • Συγχώνευση και εξειδίκευση εντολών