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

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

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

Ανακοινώσεις | Υλικό: Γενικά, Moodle, Ασκήσεις, Διαφάνειες, Παλαιότερα έτη
Διαλέξεις: 4/10 | 11/10 | 18/10 | 25/10 | 1/11 | 8/11 | 22/11 | 29/11 | 13/12 | 20/12 | 10/1 | 17/1

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

Υλικό

Γενικά

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

Ασκήσεις

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

Αριθμός	Αντικείμενο	Προθεσμία παράδοσης	Εκφώνηση	Επιπλέον υλικό
1	Haskell για ηχολήπτες	1/11/2017	PDF	Διάβασμα της εισόδου για παλιότερη άσκηση, με String και με ByteString.
2, 3	Haskell, δέντρα, QuickCheck	19/11/2017	PDF
4	Συστήματα τύπων	29/11/2017	PDF
5	Εξαγωγή τύπων	13/12/2017	PDF	Διάβασμα της εισόδου, σε Haskell.
6	Εικονικές μηχανές	4/3/2018	PDF	Πρόχειρος assembler και το παράδειγμα της εκφώνησης.
7	Συλλογή σκουπιδιών	4/3/2018	PDF
8	Δηλωτική σημασιολογία	4/3/2018	PDF	Διάβασμα της εισόδου, σε Haskell.
9	Αξιωματική σημασιολογία	25/3/2018	PDF
10	Γλώσσες σεναρίων	25/3/2018	PDF

Διαφάνειες

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

• Η γλώσσα Haskell:  PDF ή  PDF
• Συστήματα τύπων:  PDF ή  PDF
• Λάμβδα λογισμός και εξαγωγή τύπων:  PDF ή  PDF
• Δυναμική διαχείριση μνήμης:  PDF ή  PDF
• Εικονικές μηχανές και οι διερμηνείς τους:  PDF ή  PDF
• Δηλωτική σημασιολογία:  PDF ή  PDF
• Αξιωματική σημασιολογία:  PDF ή  PDF

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

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

Διαλέξεις

Παράδοση 4/10/2017

• H γλώσσα Haskell: σειριακό κομμάτι
  • Εισαγωγή στη Haskell
  • Τύποι, πολυμορφισμός και συμπερασμός τύπων της Haskell
  • Συναρτήσεις υψηλής τάξης και ανώνυμες συναρτήσεις
  • List comprehensions
  • Προγραμματισμός με συναρτήσεις υψηλής τάξης
  • Λίγα λόγια για το IO monad
  • Λύσεις θεμάτων της εξέτασης του 1ου εξαμήνου σε Haskell: magic.hs και tp.hs

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

• H γλώσσα Haskell: σειριακό κομμάτι (δεύτερο μέρος)
  • Qualified types και κλάσεις τύπων (type classes)
  • Οκνηρή αποτίμηση (lazy evaluation)
  • Άπειρες λίστες και παραδείγματα χειρισμού τους
  • Προγραμματισμός με άπειρες λίστες
  • IO και Monads
  • Μια πιο βαθειά ματιά στα Monads
    • Tree DFS traversal: dfn.hs
    • Tree DFS traversal, με State monad: dfm.hs

Παράδοση 18/10/2017

• H γλώσσα Haskell: σειριακό κομμάτι (τρίτο μέρος)
  • Άπειρες και δομές δεδομένων
    • Tree BFS traversal: bfn.hs
  • Αγνές συναρτησιακές δομές δεδομένων
    • Αποδοτική υλοποίηση ουράς με κόστος O(1) amortized: queue.hs
  • Μια πιο βαθειά ματιά στην οκνηρή αποτίμηση
  • Lazy IO
  • Τρόποι ελέγχου της οκνηρίας με χρήση seq
  • Space leaks και τρόποι αποφυγής τους
  • Property based testing με το QuickCheck
    • Έλεγχος ορθότητας ταξινόμησης: sort-pbt.hs
    • Έλεγχος ορθότητας με δύο υλοποιήσεις: kylikeio.hs

Παράδοση 25/10/2017

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

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

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

Παράδοση 8/11/2017

• Λάμβδα λογισμός
  • Εισαγωγή
  • Διαισθητική περιγραφή
  • Σύνταξη, ελεύθερες μεταβλητές, αντικατάσταση
  • Μετατροπές α, β και η, αναγωγές και ισότητα
  • Κανονικές μορφές
  • Ιδιότητες του λ-λογισμού
  • Εκφραστική δύναμη του λ-λογισμού
• Εξαγωγή τύπων (type inference)
  • Παραδείγματα σε OCaml
  • Εξαγωγή τύπων στην πράξη
  • Περιορισμοί και επίλυση
  • Εφαρμογή στο λ-λογισμό

Παράδοση 22/11/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)

Παράδοση 29/11/2017

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

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

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

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

• Αξιωματική σημασιολογία και επαλήθευση προγραμμάτων
  • Τριάδες 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

Παράδοση 10/1/2018

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

Παράδοση 17/1/2018

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