Δηλωτική σημασιολογία

Στην επιστήμη των υπολογιστών, η δηλωτική σημασιολογία (denotational semantics) είναι μια προσέγγιση για την τυποποίηση της σημασίας των γλωσσών προγραμματισμού μέσω της κατασκευής μαθηματικών αντικειμένων (που ονομάζονται δηλώσεις, denotations), τα οποία περιγράφουν τις σημασίες των εκφράσεων των γλωσσών. Άλλες προσεγγίσεις της τυπικής σημασιολογίας των γλωσσών προγραμματισμού είναι η αξιωματική σημασιολογία (axiomatic semantics) και η λειτουργική σημασιολογία (operational semantics).
Η δηλωτική σημασιολογία, γενικά, ασχολείται με την εύρεση μαθηματικών αντικειμένων που ονομάζονται πεδία (domains), που αναπαριστούν αυτό που κάνει ένα πρόγραμμα. Για παράδειγμα, κάποια προγράμματα (ή φράσεις από προγράμματα) μπορούν να αναπαρασταθούν από μερικές συναρτήσεις, από σενάρια διαγραμμάτων συμβάντων από Actors ή από παίγνια (games) μεταξύ του περιβάλλοντος και του συστήματος: όλα αυτά είναι γενικά παραδείγματα πεδίων.
Μια σημαντική αρχή της δηλωτικής σημασιολογίας είναι ότι η σημασιολογία πρέπει να είναι συνθετική: η σημασιολογία μιας φράσης του προγράμματος πρέπει να κατασκευάζεται από τις δηλώσεις των υποφράσεών της.

Ανάπτυξη της δηλωτικής σημασιολογίας

Η δηλωτική σημασιολογία προήλθε από το έργο του Christopher Strachey και του Dana Scott κατά τη δεκαετία του 1960. Όπως αρχικά αναπτύχθηκε από αυτούς, η δηλωτική σημασιολογία έδινε τη δήλωση (σημασία) ενός προγράμματος υπολογιστή ως μια συνάρτηση που αντιστοιχίζει είσοδο σε έξοδο. Για να δοθούν οι δηλώσεις των αναδρομικά ορισμένων προγραμμάτων, ο Scott πρότεινε την εργασία με συνεχείς συναρτήσεις μεταξύ πεδίων, και ειδικότερα πλήρεις σχέσεις μερικής διάταξης (complete partial orders). Όπως θα περιγραφεί στη συνέχεια, το έργο αυτό συνεχίστηκε προς την έρευνα πάνω στην κατάλληλη δηλωτική σημασιολογία που αφορά πλευρές των γλωσσών προγραμματισμού, όπως η αλληλουχίες εντολών (sequentiality), ο ταυτοχρονισμός, ο μη-ντετερμινισμός και η τοπική κατάσταση (local state).
Έχουν αναπτυχθεί δηλωτικές σημασιολογίες για σύγχρονες γλώσσες προγραμματισμού που χρησιμοποιούν capabilities όπως ο ταυτοχρονισμός και οι εξαιρέσεις, π.χ. η ActorScript, η Concurrent ML, οι CSP, και η Haskell. Οι σημασιολογίες αυτών των γλωσσών υπακούουν στον κανόνα της σύνθεσης γιατί η δήλωση μιας φράσης εξαρτάται από τις δηλώσεις των υποφράσεών της. Για παράδειγμα, η σημασία της έκφρασης f(E1,E2) ορίζεται με βάση τη σημασιολογία των υποφράσεών της f, E1 και E2. Σε μια σύγχρονη γλώσσα προγραμματισμού, οι E1 και E2 μπορούν να αποτιμώνται ταυτόχρονα και η εκτέλεσης της μιας από αυτές μπορεί να επηρεάζει την άλλη μέσω κοινών αντικειμένων, με αποτέλεσμα οι σημασιολογία τους να πρέπει να ορίζεται αμοιβαία. Επίσης η E1 ή η E2 μπορεί να προκαλέσουν μια εξαίρεση, η οποία προκαλεί τον τερματισμό της άλλης. Οι παρακάτω ενότητες περιγράφουν ειδικές περιπτώσεις της σημασιολογίας αυτών των σύγχρονων γλωσσών προγραμματισμού.

Δηλωτική σημασιολογία μη ντετερμινιστικών προγραμμάτων

Η έννοια των power domains αναπτύχθηκε για δοθεί μια δηλωτική σημασιολογία των μη ντετερμινιστικών ακολουθιακών προγραμμάτων. Αν P είναι ένας κατασκευαστης power domain, το P(D) είναι το πεδίο των μη ντετερμινιστικών υπολογισμών με τύπο που δηλώνεται από το D.
Υπάρχουν κάποιες δυσκολίες όσον αφορά τη δικαιοσύνη (fairness) και τις μη φραγμένες συμπεριφορές σε πεδιο-θεωρητικά μοντέλα του μη ντετερμινισμού.  Δείτε επίσης Power domains.

Δηλωτική σημασιολογία του ταυτοχρονισμού

Αρκετοί ερευνητές θεωρούν ότι τα πεδιο-θεωρητικά μοντέλα που δόθηκαν παραπάνω δεν αρκούν για τη γενική περίπτωση του ταυτόχρονου υπολογισμού. Για αυτόν το λόγο έχουν προταθεί διάφορα νέα μοντέλα. Στις αρχές του 1980, το στυλ της δηλωτικής σημασιολογίας άρχισε να χρησιμοποιείται για την απόδοση σημασιολογίας σε γλώσσες ταυτοχρονισμού. Παραδείγματα είναι η δουλειά του Will Clinger στο μοντέλο Actor, η δουλειά του Glynn Winskel σε δομές συμβάντων (event structures) και δίκτυα petri, και η δουλειά των Francez, Hoare, Lehmann, και de Roever (1979) στα trace semantics για CSP. Αυτές οι κατευθύνσεις της έρευνας συνεχίζουν να προχωρούν.
Πρόσφατα, ο Winskel και άλλοι πρότειναν την κατηγορία των profunctors ως θεωρία πεδίων για τον ταυτοχρονισμό.

Δηλωτική σημασιολογία της κατάστασης

Η κατάσταση (όπως ο σωρός) και απλά χαρακτηριστικά των προστακτικών γλωσσών προγραμματισμού μπορούν να μοντελοποιηθούν με ευθύ τρόπο στη δηλωτική σημασιολογία που προαναφέρθηκε. Τα βιβλία περιέχουν περισσότερες πληροφορίες. Η βασική ιδέα είναι η θεώρηση μιας εντολής σαν μιας μερικής συνάρτησης σε κάποιο πεδίο από καταστάσεις. Τότε η δήλωση του "x:=3" είναι η συνάρτηση που από μια κατάσταση σε μια κατάσταση με την τιμή 3 να έχει ανατεθεί στην x. Ο τελεστής ακολουθιών εντολών ";" δηλώνεται με σύνθεση συναρτήσεων. Οι κατασκευές σταθερού σημείου χρησιμοποιούνται στη συνέχεια για να δώσουν σημασιολογία στους βρόχους, όπως στην εντολή "while".
Η μοντελοποίηση προγραμμάτων με τοπικές μεταβλητές είναι δυσκολότερη. Μια προσέγγιση είναι να μη χρησιμοποιούνται πια πεδία, αλλά να ερμηνεύονται οι τύποι ως functors από κάποια κατηγορία από κόσμους σε μια κατηγορία από πεδία. Οι δηλώσεις τότε των προγραμμάτων προκύπτουν από φυσικός μετασχηματισμός φυσικές συνεχείς συναρτήσεις ανάμεσα σε αυτούς τους functors.

Δηλωτική σημασιολογία προγραμμάτων περιορισμένης πολυπλοκότητας

Λόγω της ανάπτυξης γλωσσών προγραμματισμού βασισμένων στη γραμμική λογική, έχει αποδοθεί δηλωτική σημασιολογία σε γλώσσες που περιλαμβάνουν γραμμική χρήση (π..χ proof nets, coherence spaces) και πολυπλοκότητα πολυωνυμικού χρόνου.

Δηλωτική σημασιολογία για ακολουθιακά προγράμματα

Το πρόβλημα της αφαίρεσης για την ακολουθιακή γλώσσα προγραμματισμού PCF αποτέλεσε για μεγάλο χρονικό διάστημα, ένα μεγάλο ανοιχτό ερώτημα της δηλωτικής σημασιολογίας. Το πρόβλημα της PCF είναι ότι είναι πολύ ακολουθιακή ως γλώσσα. Για παράδειγμα, δεν υπάρχει τρόπος να οριστεί η συνάρτηση παράλληλη-διάζευξη (parallel-or) στην PCF. Για αυτόν το λόγο, η παραπάνω τεχνική με τη χρήση πεδίων, έχει ως αποτέλεσμα δηλωτική σημασιολογία που δεν είναι πλήρως αφηρημένη.
Αυτό το ανοιχτό ερώτημα απαντήθηκε σε μεγάλο βαθμό κατά τη δεκαετία του 1990 με την ανάπτυξη των game semantics και με τεχνικές που περιλάμβαναν λογικές σχέσεις. Για περισσότερες λεπτομέρειες, βλ. PCF.

Η δηλωτική σημασιολογία ως μετάφραση από κώδικα σε κώδικα

Συχνά είναι χρήσιμο να μεταφράζεται μια γλώσσα προγραμματισμού σε μια άλλη. Για παράδειγμα, μια ταυτόχρονη γλώσσα προγραμματισμού θα μπορούσε να μεταφραστεί σε λογισμό διεργασιών (process calculus) ενώ μια γλώσσα προγραμματισμού υψηλού επιπέδου θα μπορούσε να μεταφραστεί σε κώδικα byte (byte-code). Η κλασική δηλωτική σημασιολογία μπορεί να θεωρηθεί ως η ερμηνεία γλωσσών προγραμματισμού ως η εσωτερική γλώσσα της κατηγορίας των πεδίων.
Σε αυτά τα πλαίσια, οι ιδέες της δηλωτικής σημασιολογίας, όπως η πλήρης αφαίρεση, βοηθούν στην ικανοποίηση απαιτήσεων ασφαλείας.

Συνδέσεις με άλλες περιοχές της επιστήμης υπολογιστών

Υπάρχει έργο στη δηλωτική σημασιολογία που ερμηνεύει τους τύπους ως πεδία όπως η θεωρία πεδίων (domain theory), η οποία μπορεί να θεωρηθεί παρακλάδι της θεωρίας μοντέλων (model theory), οδηγώντας στη θεωρία τύπων και στη θεωρία κατηγοριών. Μέσα στην επιστήμη των υπολογιστών, υπάρχουν σχέσεις με την αφηρημένη διερμηνεία, την τυπική επαλήθευση (formal verification) και τον έλεγχο μοντέλων.
Οι μονάδες (monads) εισήχθηκαν στη δηλωτική σημασιολογία για την οργάνωση της σημασιολογίας, και οι ιδέες αυτές έχουν προκαλέσει σημαντικό αντίκτυπο στο συναρτησιακό προγραμματισμό.