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

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

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

Ανακοινώσεις | Υλικό: Γενικά, Moodle, Ασκήσεις, Διαφάνειες, Παλαιότερα έτη
Διαλέξεις: 3/10 | 10/10 | 17/10 | 24/10 | 31/10 | 7/11 | 19/11 | 21/11 | 5/12 | 12/12 | 19/12 | 9/1 | 16/1

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

Υλικό

Γενικά

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

Ασκήσεις

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

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

Διαφάνειες

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

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

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

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

Διαλέξεις

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

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

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

• H γλώσσα Haskell: σειριακό κομμάτι (δεύτερο μέρος)
  • IO και Monads
    • Παράδειγμα, πρόγραμμα επεξεργασίας κειμένου: tp.hs
  • Μια πιο βαθειά ματιά στα Monads
    • Tree DFS traversal, με State monad: dfm.hs

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

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

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

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

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

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

Παράδοση 7/11/2018

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

Παράδοση 19/11/2018

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

Παράδοση 21/11/2018

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

Παράδοση 5/12/2018

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

Παράδοση 12/12/2018

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

Παράδοση 19/12/2018

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

Παράδοση 9/1/2019

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

Παράδοση 16/1/2019

• Παραλληλισμός και ταυτοχρονισμός στη Haskell
  • Εισαγωγή
  • Παραλληλισμός
    • Evaluation strategies
    • Par monad
  • Ταυτοχρονισμός
    • IO monad και MVar
    • Software Transactional Memory