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

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

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

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

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

Εξάμηνο:

Χειμερινό 2014

Διδάσκοντες:

Κωστής Σαγώνας		()		γρ. 1.1.21		τηλ: 210-772-2487
Νίκος Παπασπύρου		()		γρ. 1.1.21		τηλ: 210-772-3393

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

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

15/10/2014

ΠΡΟΣΟΧΗ: Εγγραφείτε στο συνεργατικό σύστημα ηλεκτρονικής μάθησης (Moodle). Αν δεν έχετε ήδη κωδικό, θα χρειαστεί να φτιάξετε έναν (επί τόπου). Για το σκοπό αυτό, θα χρειαστεί να δώσετε μια διεύθυνση e-mail, στην οποία θα σας αποσταλεί (αυτόματα) μήνυμα απαραίτητο για την ενεργοποίηση του κωδικού σας. Στη συνέχεια εγγραφείτε στο μάθημα Γλώσσες Προγραμματισμού ΙΙ.

15/10/2014

Οι διαλέξεις του μαθήματος αρχίζουν σήμερα. Θα διεξάγονται κάθε Τετάρτη, ώρα 11:45-14:30, στην Αίθουσα 002 του Νέου Κτιρίου Ηλεκτρολόγων. Κατόπιν ανακοίνωσης, ενδέχεται κάποια μαθήματα (αναπλήρωσης και μη) να γίνονται Παρασκευή, ώρα 15:00-18:00, στην ίδια αίθουσα.

Υλικό

Γενικά

Ενημερωτικό φυλλάδιο ( PDF, 116KB).
Ώρες γραφείου διδασκόντων: Τετάρτη 14:30–16:00.
Εκτενής βιβλιογραφία και υλοποιήσεις γλωσσών.

Ασκήσεις

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

Αριθμός	Αντικείμενο	Προθεσμία παράδοσης	Εκφώνηση
1	Συστήματα τύπων	8/11/2014	PDF (101KB)
2	Εξαγωγή τύπων	17/12/2014	PDF (97KB)
3	Γλώσσες σεναρίων	23/12/2014	PDF (194KB)
4	Συλλογή σκουπιδιών	22/3/2015	PDF (194KB)
5	Haskell #1: Τα δέντρα και πώς να τα διπλώνετε, με μονάδες και χωρίς	22/3/2015	PDF (194KB)
6	Haskell #2: Το πουλί, το άπειρο δέντρο και οι γρήγορες δοκιμές	22/3/2015	PDF (194KB)
7	Αξιωματική σημασιολογία	11/10/2015	PDF (99KB)
8	Erlang #1	11/10/2015	TBA
9	Erlang #2	11/10/2015	TBA

Διαφάνειες

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

Συστήματα τύπων: PDF (406KB) ή PDF (357KB)
Εξαγωγή τύπων: PDF (251KB) ή PDF (273KB)
Γλώσσες σεναρίων: ( PDF (72KB) και PDF (354KB)) ή ( PDF (63KB) και PDF (230KB))
Η γλώσσα Erlang (σειριακό μέρος) και property-based testing: PDF (157KB) ή PDF (151KB)
Η γλώσσα Erlang (μέρος ταυτοχρονισμού, κατανεμημένης και παράλληλης εκτέλεσης): PDF (182KB) ή PDF (175KB)
Η γλώσσα Haskell (2 διαλέξεις): PDF (448KB) ή PDF (441KB)
Εικονικές μηχανές και οι διερμηνείς τους: PDF (251KB) ή PDF (273KB)
Δυναμική διαχείριση μνήμης: PDF (3.9MB) ή PDF (3.4MB)
Δηλωτική σημασιολογία: PDF (277KB) ή PDF (256KB)
Αξιωματική σημασιολογία: PDF (175KB) ή PDF (169KB)

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

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

Διαλέξεις

Παράδοση 15/10/2014

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

Παράδοση 22/10/2014

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

Παράδοση 29/10/2014

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

Παράδοση 5/11/2014

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

Παράδοση 12/11/2014

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

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

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

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

H γλώσσα Erlang: ταυτοχρονισμός, κατανεμημένη και παράλληλη εκτέλεση
- Διεργασίες και ταυτόχρονη εκτέλεση
- Ανταλλαγή μηνυμάτων
- Επιλεκτική λήψη μηνυμάτων
- Αλλαγή κώδικα κατά τη διάρκεια της εκτέλεσης
- Κατανεμημένη εκτέλεση προγραμμάτων
- Παράλληλη εκτέλεση προγραμμάτων
- Τεχνικές βελτίωσης της επίδοσης παράλληλης εκτέλεσης

Παράδοση 3/12/2014

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

Παράδοση 10/12/2014

Η γλώσσα Haskell (συνέχεια)
- Άπειρες λίστες
- Προγραμματισμός με οκνηρή αποτίμηση
  - Παράδειγμα, αρίθμηση σε διάσχιση κατά βάθος: dfn.hs
  - Παράδειγμα, αρίθμηση σε διάσχιση κατά πλάτος: bfn.hs
- Lazy IO
- Strictness
- Space leaks και τρόποι αποφυγής τους

Παράδοση 17/12/2014

Η γλώσσα Haskell (συνέχεια)
- Monads
  - Παράδειγμα, αρίθμηση σε διάσχιση κατά βάθος (ξανά)
  - Με ένα χειροποίητο state monad: dfm1.hs
  - Με το state monad της βιβλιοθήκης: dfm2.hs
- Pretty printing
- Parsing
- Αποτίμηση μίας απλής γλώσσας υπολογισμών
  - Παράδειγμα: eval.hs

Παράδοση 7/1/2015

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

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

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

Παράδοση 14/1/2015

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

Παράδοση 21/1/2015

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

Τελευταία αλλαγή: 21/7/15, 17:39.