Γλώσσες Προγραμματισμού ΙΙ
Κατ' επιλογήν υποχρεωτικό μάθημα ροής Λ, 9ου εξαμήνου, κωδικός 3.4.58.9
Εξάμηνο: Χειμερινό 2010
Διδάσκοντες:
Κωστής Σαγώνας
(kostis (AT) cs (DOT) ntua.gr )
γρ. 1.1.21
τηλ: 210-772-2487
Νίκος Παπασπύρου
(nickie (AT) softlab (DOT) ntua.gr )
γρ. 1.1.21
τηλ: 210-772-3393
Ανακοινώσεις
| Υλικό: Γενικά , Moodle , Ασκήσεις , Διαφάνειες , Παλαιότερα έτη Διαλέξεις: 6/10 | 13/10 | 20/10 | 22/10 | 27/10 | 10/11 | 17/11 | 24/11 | 1/12 | 2/12 | 8/12 | 15/12 | 22/12 | 12/1 | 19/1
19/1/2011 Οι διαλέξεις του μαθήματος ολοκληρώθηκαν σήμερα.
1/12/2010 Η προθεσμία της 3ης άσκησης (υλοποίηση συναρτησιακών γλωσσσών) παρατείνεται μέχρι τις 8/12/2010.
30/10/2010
Το μάθημα της Τετάρτης 3/11 δε θα γίνει , λόγω υποχρέωσης των διδασκόντων στο εξωτερικό.
30/10/2010 Η προθεσμία της 2ης άσκησης (εξαγωγή τύπων) παρατείνεται κατά μία εβδομάδα.
7/10/2010
ΠΡΟΣΟΧΗ: συνεργατικό σύστημα ηλεκτρονικής μάθησης (Moodle ). Αν δεν έχετε ήδη κωδικό , θα χρειαστεί να φτιάξετε έναν (επί τόπου). Για το σκοπό αυτό, θα χρειαστεί να δώσετε μια διεύθυνση e-mail, στην οποία θα σας αποσταλεί (αυτόματα) μήνυμα απαραίτητο για την ενεργοποίηση του κωδικού σας. Στη συνέχεια εγγραφείτε στο μάθημα Γλώσσες Προγραμματισμού ΙΙ.
6/10/2010 Οι διαλέξεις του μαθήματος αρχίζουν σήμερα. Θα διεξάγονται κάθε Τετάρτη,
ώρα 11:45-14:30 , στην Αίθουσα 07 του Νέου Κτιρίου Ηλεκτρολόγων.
Υλικό
Οι ασκήσεις πρέπει να παραδοθούν στους διδάσκοντες σε ηλεκτρονική
μορφή μέσω του συνεργατικού συστήματος ηλεκτρονικής μάθησης Moodle .
Η προθεσμία παράδοσης θα τηρείται αυστηρά.
Έχετε δικαίωμα να καθυστερήσετε το πολύ μία άσκηση.
1
Haskell για ενεργειακούς
3/11/2010 PDF (130KB)PDF (81KB)
2
Εξαγωγή τύπων
3/11/2010 10/11/2010 PDF (117KB)PDF (129KB)
3
Υλοποίηση συναρτησιακών γλωσσών
2/12/2010 8/12/2010
PDF (65KB)
4
Δηλωτική σημασιολογία
28/11/2010 PDF (97KB)
5+6
Συστήματα τύπων
29/12/2010 PDF (109KB)
7
Αξιωματική σημασιολογία
26/1/2011 PDF (105KB)
8
Εικονικές μηχανές
27/3/2011 PDF (101KB)
9
Γλώσσες σεναρίων
27/3/2011 PDF (126KB)
Οι διαφάνειες που θα χρησιμοποιούνται στις διαλέξεις είναι διαθέσιμες από την παρούσα σελίδα για τη διευκόλυνση των σπουδαστών, ώστε αυτοί να μη χρειάζεται να κρατούν εκτενείς σημειώσεις κατά τη διάρκεια των μαθημάτων. Η ύλη των διαφανειών παρουσιάζεται αναλυτικά στις σημειώσεις του μαθήματος.
Η γλώσσα Haskell: (PDF και PDF (317KB)) ή (PDF (85KB) και PDF (104KB))
Εξαγωγή τύπων: PDF (251KB) ή PDF (273KB)
Υλοποίηση γλωσσών συναρτησιακού προγραμματισμού: PDF (129KB)
Δυναμική διαχείριση μνήμης: PDF (3.9MB) ή PDF (3.4MB)
Δηλωτική σημασιολογία: PDF (277KB) ή PDF (256KB)
Συστήματα τύπων: PDF (406KB) ή PDF (357KB)
Ταυτοχρονισμός: PDF (478KB)
Εικονικές μηχανές και οι διερμηνείς τους: PDF (251KB) ή PDF (273KB)
Αξιωματική σημασιολογία: PDF (175KB) ή PDF (169KB)
Σελίδα του μαθήματος για τα ακαδημαϊκά έτη: 2009-10 , 2008-09 , 2007-08 , 2006-07 , 2005-06 , 2004-05 , 2003-04 , 2002-03 .
Διαλέξεις
Θέματα διεξαγωγής του μαθήματος
Η γλώσσα Haskell
Ορισμοί, συναρτήσεις, εκφράσεις και τιμές
Αυστηρό σύστημα τύπων με αυτόματη εξαγωγή τύπων
Δηλώσεις νέων τύπων και αναδρομικές δομές δεδομένων
Συναρτήσεις υψηλής τάξης
Διαφάνεια αναφοράς
Κλάσεις τύπων (type classes)
Οκνηρή αποτίμηση
Παράδειγμα, γενίκευση αριθμών Fibonacci: genfib.hs
Η γλώσσα Haskell (συνέχεια)
Οκνηρή αποτίμηση
Παράδειγμα, κόσκινο του Ερατοσθένη: sieve.hs
Παράδειγμα, αρίθμηση σε διάσχιση κατά βάθος: dfn.hs
Quiz: μπορείτε να κάνετε το ίδιο για διάσχιση κατά πλάτος;
Παρενέργειες στη Haskell και μονάδες (monads)
Εξαγωγή τύπων (type inference)
Παραδείγματα σε OCaml
Εξαγωγή τύπων στην πράξη
Περιορισμοί και επίλυση
Εφαρμογή στο λ-λογισμό
Υλοποίηση γλωσσών συναρτησιακού προγραμματισμού
Υλοποίηση συναρτήσεων μέσω closures
Απουσία παρενεργειών και αναθέσεων σε μεταβλητές
Inline expansion
Closure conversion
Αποδοτική υλοποίηση αναδρομής ουράς
Υλοποίηση και βελτιστοποίηση προγραμμάτων σε οκνηρές γλώσσες
Deforestation
Strictness analysis
Δυναμική διαχείριση μνήμης
Γλώσσες προγραμματισμού με άμεση και έμμεση δέσμευση και αποδέσμευση μνήμης
Ανακύκλωση μνήμης μέσω του αλγόριθμου mark-and-sweep
Ανακύκλωση μνήμης μέσω μετρήματος αναφορών (reference counting)
Ανακύκλωση μνήμης μέσω αντιγραφής &ndash ο αλγόριθμος του Cheney
Συλλογή σκουπιδιών σε γενεές (generational garbage collection)
Αυξητικοί, ταυτόχρονοι και συλλέκτες σκουπιδιών πραγματικού χρόνου
(incremental, concurrent, and real-time garbage collection)
Μαρκάρισμα με τρία χρώματα (tricolor marking)
Φράγματα ανάγνωσης και γραφής (read and write barriers)
Ο αλγόριθμος του Baker
Συνεργασία του συλλέκτη σκουπιδιών με τον compiler
Σημασιολογία
Δηλωτική σημασιολογία
Μια απλή γλώσσα δυαδικών συμβολοσειρών
Μια απλή προστακτική γλώσσα
Σημασιολογία αριθμητικών και λογικών εκφράσεων
Σημασιολογία εντολών
Μεταβλητές και αναθέσεις
Αόριστες επαναλήψεις, εντολή while
Θεωρία πεδίων
Ορισμοί
Κατασκευές πεδίων
Μονότονες και συνεχείς συναρτήσεις
Θεώρημα ελάχιστου σταθερού σημείου
Δηλωτική σημασιολογία (συνέχεια)
Μια απλή προστακτική γλώσσα (ξανά)
Σημασιολογία του λ-λογισμού
Συστήματα τύπων
Εισαγωγή
Βασικοί τύποι
Σύνταξη
Λειτουργική σημασιολογία
Κανόνες τύπων
Ιδιότητες του συστήματος τύπων
Τύποι συναρτήσεων
Απλές επεκτάσεις
Ο τύπος μονάδας — Unit
Ακολουθιακή αποτίμηση
Απόδοση ονομάτων — δομή let
Ζεύγη
Αθροίσματα
Αναδρομή
Ταυτοχρονισμός
Διαμοιραζόμενα δεδομένα και συγχρονισμός
Ιδιότητες ασφάλειας και ζωτικότητας
Αμοιβαίος αποκλεισμός
Το πρόβλημα του παραγωγού-καταναλωτή
Το πρόβλημα των αναγνωστών-συγγραφέων
Δυσκολίες του παράλληλου προγραμματισμού
Ο νόμος του Amdahl
Εικονικές μηχανές και οι διερμηνείς τους
Εικονικές μηχανές
Ορισμός και παραδείγματα
Πλεονεκτήματα και μειονεκτήματα
Επιλογές σχεδιασμού και συστατικά των εικονικών μηχανών
Υλοποίηση των εικονικών μηχανών
Διερμηνείς
Μορφές διερμηνέων
Δομή των bytecode interpreters
Άμεσα και έμμεσα νηματικοί διερμηνείς (threaded code interpreters)
Συγχώνευση και εξειδίκευση εντολών
Συστήματα τύπων (συνέχεια)
Αναφορές
Εξαιρέσεις
Υποτύποι
Αναδρομικοί τύποι
Πολυμορφισμός 2ης τάξης
Πολυμορφισμός υψηλής τάξης
Υπαρξιακοί τύποι
Εξαρτώμενοι τύποι
Αξιωματική σημασιολογία και επαλήθευση προγραμμάτων
Τριάδες Hoare
Μια απλή προστακτική γλώσσα
Παραδείγμα:
υπολογισμός παραγοντικού στο Frama-C
Παράδειγμα: έλεγχος πρώτου αριθμού (άσκηση 2009-10)
με επανάληψη, διαιρώντας με όλους τους προηγούμενους: prime.c
Παράδειγμα: υπολογισμός ακέραιας δύναμης
(άσκηση 2008-09)
με διαδοχικό τετραγωνισμό: pow.c
Γλώσσες σεναρίων
Εισαγωγή
Περιοχές εφαρμογών
Περιήγηση με τη Ruby
Παραδείγματα
Γλώσσες σεναρίων
(συνέχεια)
Τελευταία αλλαγή: 14/11/11, 11:11.
webmaster (AT) courses (DOT) softlab.ntua.gr
PDF, 120KB)
PDF (85KB) και