Θεωρία πεδίων

Η θεωρία πεδίων (αγγλ. domain theory) είναι κλάδος των μαθηματικών που μελετά είδη μερικά διατεταγμένων συνόλων (partially ordered sets ή posets), τα οποία ονομάζονται πεδία (domains). Για αυτό το λόγο η θεωρία πεδίων μπορεί να θεωρηθεί σαν κλάδος της θεωρίας διάταξης (order theory). Έχει σημαντικές εφαρμογές στη θεωρητική πληροφορική, όπου χρησιμοποιείται για τον ορισμό της δηλωτικής σημασιολογίας, ειδικά για τις συναρτησιακές γλώσσες προγραμματισμού. Η θεωρία πεδίων εκφράζει με τυπικό τρόπο τις ιδέες της προσέγγισης (approximation) και της σύγκλισης (convergence) με γενικό τρόπο και έχει στενή σχέση με την τοπολογία. Στην επιστήμη υπολογιστών χρησιμοποιούνται εναλλακτικά οι μετρικοί χώροι.

Εισαγωγή

Το βασικό κίνητρο για τη μελέτη των πεδίων, που άρχισε στα τέλη της δεκαετίας του 1960 από τον Dana Scott, ήταν η αναζήτηση δηλωτικής σημασιολογίας για το λ-λογισμό. Σε αυτό το τυπικό σύστημα, οι "συναρτήσεις" ("functions") ορίζονται από συγκεκριμένους όρους της γλώσσας. Μπορεί κανείς να μεταβεί από απλές συναρτήσεις σε συναρτήσεις που δέχονται σαν ορίσματα άλλες συναρτήσεις, με πλήρως συντακτικό τρόπο. Κάνοντας χρήση μόνο των συντακτικών μετασχηματισμών που παρέχονται, μπορεί κανείς να φτάσει στους λεγόμενους συνδυαστές σταθερού σημείου (fixed point combinators), με γνωστότερο παράδειγμα το συνδυαστή-Υ (Y combinator) - οι συνδυαστές αυτοί έχουν εξ ορισμού την ιδιότητα f(Y(f)) = Y(f) για κάθε συνάρτηση f.
Για τον τυπικό ορισμό δηλωτικής σημασιολογίας, πρέπει πρώτα να κατασκευαστεί ένα μοντέλο του λ-λογισμού, στο οποίο μια πλήρης (total) συνάρτηση αντιστοιχίζεται σε κάθε λ-όρο. Ένα τέτοιο μοντέλο θα τυποποιούσε τη σχέση μεταξύ του λ-λογισμού σαν πλήρως συντακτικού συστήματος, και του λ-λογισμού σαν σύστημα σημειογραφίας για το χειρισμό μαθηματικών συναρτήσεων. Δυστυχώς, τέτοιο μοντέλο δε μπορεί να υπάρξει, γιατί αν υπήρχε θα έπρεπε να περιέχει μια πλήρη συνάρτηση που να αντιστοιχεί στο συνδυαστή Y, δηλαδή μια συνάρτηση που να υπολογίζει το σταθερό σημείο (fixed point) οποιασδήποτε συνάρτησης f.  Για την περίπτωση του Y δε μπορεί να υπάρξει τέτοια συνάρτηση γιατί κάποιες συναρτήσεις (όπως η συνάρτηση επόμενο, αγγλ. successor function) δεν έχουν σταθερό σημείο. Στην καλύτερη περίπτωση, η συνάρτηση που θα αντιστοιχούσε στον Y θα έπρεπε να είναι μερική συνάρτηση (partial function), δηλαδή να μην ορίζεται για κάποιες τιμές της εισόδου.
Ο Scott απέφυγε αυτή τη δυσκολία τυποποιώντας μια έννοια "μερικής" ("partial") ή "ημιτελούς" ("incomplete") πληροφορίας για την αναπαράσταση υπολογισμών που ακόμα δεν έχουν επιστρέψει αποτέλεσμα. Αυτό μοντελοποιήθηκε θεωρώντας για κάθε πεδίο υπολογισμών (όπως οι φυσικοί αριθμοί), ένα επιπλέον στοιχείο που αναπαριστά τη μη ορισμένη (undefined) έξοδο, δηλ. το "αποτέλεσμα" ενός υπολογισμού που ποτέ δεν τερματίζει. Επιπλέον, το πεδίο των υπολογισμων εφοδιάζεται με μια σχέση διάταξης (ordering relation), στην οποία το "μη ορισμένο αποτέλεσμα" είναι το ελάχιστο στοιχείο (least element).
Το βασικό βήμα για την εύρεση ενός μοντέλου για το λ-λογισμό είναι να εξετάζονται μόνο οι συναρτήσεις (στο μερικά διατεταγμένο σύνολο) που εγγυημένα έχουν ελάχιστα σταθερά σημεία. Το σύνολο αυτών των συναρτήσεων, μαζί με την κατάλληλη διάταξη, είναι το "πεδίο" κατά τη θεωρία. Ο περιορισμός όμως σε ένα υποσύνολο από όλες τις διαθέσιμες συναρτήσεις έχει άλλο ένα θετικό αποτέλεσμα: μπορούν να υπάρξουν πεδία που περιέχουν τον ίδιο το χώρο συναρτήσεών τους (function space), δηλαδή με συναρτήσεις που να μπορούν να εφαρμοστούν στον εαυτό τους.
Εκτός από τις παραπάνω επιθυμητές ιδιότητες, η θεωρία πεδίων είναι ελκυστική σαν ερμηνεία. Όπως προαναφέρθηκε, τα πεδία των υπολογισμών είναι πάντα μερικά διατεταγμένα. Αυτή η διάταξη αναπαριστά μια ιεραρχία πληροφορίας ή γνώσης. Όσο ψηλότερα είναι ένα στοιχείο στη διάταξη, τόσο πιο συγκεκριμένο είναι και τόσο περισσότερη πληροφορία περιέχει. Τα κατώτερα στοιχεία αναπαριστούν μερική γνώση ή ενδιάμεσα αποτελέσματα.
Οι υπολογισμοί τότε μοντελοποιούνται από την επαναληπτική εφαρμογή μονότονων συναρτήσεων σε στοιχεία του πεδίου μέχρι να φτάσει σε κάποιο αποτέλεσμα. Ο τερματισμός του υπολογισμού είναι ισοδύναμος με την κατάληξη σε σταθερό σημείο. Τα πεδία αποτελούν βολικό εργαλείο για αυτές τις ιδέες, επειδή τα σταθερά σημεία μονότονων συναρτήσεων μπορούν να αποδειχθούν ότι υπάρχουν και, υπό κάποιους περιορισμούς, μπορούν να εκτιμηθούν.

Οδηγός για τους τυπικούς ορισμούς

Σε αυτήν την ενότητα εισάγονται οι βασικές έννοιες και ορισμοί της θεωρίας πεδίων. Η θεώρηση των πεδίων σαν διατάξεων πληροφορίας (information orderings) είναι η βάση στην οποία στηρίζεται η μαθηματική τυποποίηση που ακολουθεί. Οι ακριβείς τυπικοί ορισμοί βρίσκονται στα άρθρα για κάθε έννοια. Το λεξιλόγιο θεωρίας διάταξης (order theory glossary) περιέχει μια λίστα από γενικούς ορισμούς της διάταξης, που περιλαμβάνουν έννοιες της θεωρίας πεδίων.
Ακολουθούν οι βασικότερες έννοιες της θεωρίας πεδίων.

Κατευθυνόμενα σύνολα σαν συγκλίνουσες προδιαγραφές

Όπως έχει ήδη αναφερθεί, η θεωρία πεδίων ασχολείται με μερικά διατεταγμένα σύνολα για να μοντελοποιήσει το πεδίο των υπολογισμών. Ο στόχος είναι να ερμηνευτούν τα στοιχεία αυτών των πεδίων σαν κομμάτια πληροφορίας ή (μερικά) αποτελέσματα του υπολογισμού, όπου τα στοιχεία που βρίσκονται ψηλότερα στη διάταξη επεκτείνουν την πληροφορία των στοιχείων που βρίσκονται από κάτω τους, με συνεχή τρόπο. Από αυτήν την ιδέα προκύπτει ότι συχνά τα πεδία δεν έχουν κάποιο μέγιστο στοιχείο, αφού κάτι τέτοιο θα σήμαινε ότι υπάρχει ένα στοιχείο που περιέχει την πληροφορία όλων των άλλων στοιχείων, κάτι που δεν έχει πάντα ενδιαφέρον.
Μια έννοια που παίζει σημαντικό ρόλο στη θεωρία πεδίων είναι αυτή του κατευθυνόμενου υποσυνόλου (directed subset) ενός πεδίου, δηλαδή ενός μη κενού υποσυνόλου της διάταξης, στο οποίο οποιαδήποτε δύο στοιχεία έχουν κάποιο άνω φράγμα που είναι στοιχείο του υποσυνόλου. Με βάση τις ιδέες σχετικά με τα πεδία, αυτό σημαίνει ότι κάθε δύο κομμάτια πληροφορίας στο κατευθυνόμενο υποσύνολο επεκτείνονται με συνεπή τρόπο από κάποιο άλλο στοιχείο του υποσυνόλου. Επομένως τα κατευθυνόμενα σύνολα μπορούν να θεωρηθούν σαν συνεπείς προδιαγραφές (consistent specifications), δηλαδή σαν σύνολα από μερικά αποτελέσματα, των οποίων τα στοιχεία ποτέ δε διαφωνούν μεταξύ τους. Αυτή η ερμηνεία μπορεί να συγκριθεί με τις συγκλίνουσες ακολουθίες της μαθηματικής ανάλυσης, όπου κάθε στοιχείο είναι πιο συγκεκριμένο σε σχέση με το προηγούμενό του. Στη θεωρία των μετρικών διαστημάτων οι ακολουθίες παίζουν ρόλο συχνά ανάλογο με αυτόν τον κατευθυνόμενων συνόλων στη θεωρία πεδίων.
Όπως και στην περίπτωση των ακολουθιών, ενδιαφερόμαστε για το όριο (limit) ενός κατευθυνόμενου συνόλου. Σύμφωνα με όσα έχουν ήδη αναφερθεί, αυτό θα ήταν κάποιο στοιχείο που να αποτελεί τη γενικότερη πληροφορία που επεκτείνει την πληροφορία όλων των στοιχείων του κατευθυνόμενου συνόλου, δηλαδή το μοναδικό στοιχείο που περιέχει ακριβώς την πληροφορία που υπήρχε στο κατευθυνόμενο σύνολο και τίποτα άλλο. Στον τυπικό ορισμό της θεωρίας διάταξης, αυτό είναι απλά το ελάχιστο άνω όριο (least upper bound) του κατευθυνόμενου συνόλου. Όπως και στην περίπτωση των ορίων ακολουθιών, δεν είναι πάντα σίγουρο ότι υπάρχει ελάχιστο άνω φράγμα σε κάποιο κατευθυνόμενο σύνολο.
Συνήθως ενδιαφερόμαστε ιδιαίτερα για τα πεδία υπολογισμών στα όποια όλες οι συνεπείς προδιαγραφές συγκλίνουν, δηλ. για διατάξεις όπου όλα τα κατευθυνόμενα σύνολα έχουν ένα ελάχιστο άνω όριο. Η ιδιότητα αυτή ορίζει την κλάση των κατευθυνόμενων πλήρων μερικών διατάξεων (directed complete partial orders ή dcpo). Πράγματι, συχνά η θεωρία πεδίων εξετάζει διατάξεις που να είναι τουλάχιστον κατευθυνόμενες και πλήρεις.
Μια άλλη ιδιότητα που προκύπτει από τη βασική ιδέα των μερικά ορισμένων αποτελεσμάτων σαν τμήμα γνώσης είναι η ύπαρξη ενός ελάχιστου στοιχείου (least element). Ένα τέτοιο στοιχείο μοντελοποιεί την κατάσταση χωρίς πληροφορία, που αντιστοιχεί στο σημείο που αρχίζουν οι περισσότεροι υπολογισμοί. Μπορεί επίσης να θεωρηθεί σαν η έξοδος ενός υπολογισμού που δεν επιστρέφει κάποιο αποτέλεσμα.

Υπολογισμοί και πεδία

Με τους παραπάνω βασικούς τυπικούς ορισμούς διαθέσιμους, οι υπολογισμοί πρέπει να είναι συναρτήσεις, που παίρνουν είσοδο από κάποιο πεδίο υπολογισμών και επιστρέφουν έξοδο στο ίδιο ή σε άλλο πεδίο. Η έξοδος μιας συνάρτησης θα πρέπει να περιέχει περισσότερη πληροφορία όσο αυξάνεται η πληροφορία της εισόδου, δηλαδή η συνάρτηση πρέπει να είναι μονότονη.
Στην περίπτωση των πλήρων μερικών διατάξεων, είναι επιθυμητή η συμβατότητα των υπολογισμών με την κατασκευή των ορίων στο κατευθυνόμενο σύνολο. Τυπικά αυτό σημαίνει ότι, για κάποια συνάρτηση f, η απεικόνιση f(D) ενός κατευθυνόμενου συνόλου D (δηλαδή το σύνολο από απεικονίσεις κάθε στοιχείου του D) είναι κατευθυνόμενο σύνολο και έχει σαν ελάχιστο άνω όριο την απεικόνιση του ελάχιστου άνω ορίου του D. Η f τότε διατηρεί τα κατευθυνόμενα μέγιστα (preserves directed suprema). Επίσης, θεωρώντας κατευθυνόμενα σύνολα από δύο στοιχεία, μια τέτοια συνάρτηση πρέπει να είναι μονότονη. Από τις ιδιότητες αυτές προκύπτει η έννοιας μια συνάρτησης συνεχούς κατά Scott (Scott-continuous), που συχνά αποκαλείται και απλά συνεχής συνάρτηση.

Προσέγγιση και πεπερασμένα σύνολα

Η θεωρία πεδίων είναι μια πλήρως ποιοτική προσέγγιση όσον αφορά τη μοντελοποίηση της δομής καταστάσεων πληροφορίας. Κάτι μπορεί να θεωρηθεί ότι έχει περισσότερη πληροφορία, χωρίς να ορίζεται πόση είναι η διαφορά σε σχέση με πριν. Υπάρχουν όμως περιπτώσεις που πρέπει να χειριστούμε στοιχεία που είναι κατά μια έννοια απλούστερα (ή λιγότερο πλήρη) από μια δεδομένη κατάσταση πληροφορίας. Για παράδειγμα, στη φυσική διάταξη των υποσυνόλων που περιέχονται σε άλλα, σε κάποιο δυναμοσύνολο (powerset), κάθε άπειρο στοιχείο (δηλ. σύνολο) παρέχει περισσότερη "πληροφορία" σε σχέση με οποιοδήποτε από τα πεπερασμένα υποσύνολά του.
Αν πρέπει να μοντελοποιηθεί μια τέτοια σχέση, πρέπει πρώτα να εξεταστεί η αυστηρή διάταξη < ενός πεδίου με διάταξη ≤. Όμως, αν και είναι χρήσιμη έννοια στην περίπτωση των ολικών διατάξεων, δεν είναι πολύ χρήσιμη στην περίπτωση των μερικά διατεταγμένων συνόλων. Εξετάζοντας πάλι τη διάταξη "περιέχεται-σε" των συνόλων, ένα σύνολο είναι αυστηρά μικρότερο από ένα άλλο (που μπορεί να είναι και άπειρο) σύνολο, αν περιέχει ένα λιγότερο στοιχείο. Αυτό βέβαια δεν ανταποκρίνεται πάντα στην έννοια του να είναι ένα σύνολο "πολύ απλούστερο".

Βάσεις των πεδίων

Προκύπτει η εξής ερώτηση: μπορεί να εγγυηθεί κανείς ότι όλα τα στοιχεία ενός πεδίου προκύπτουν σαν όρια από απλούστερα στοιχεία; Αυτό είναι σημαντικό στην πράξη, γιατί δε μπορούμε να υπολογίσουμε άπειρα αντικείμενα αλλά μπορούμε να προσπαθήσουμε να τα προσεγγίσουμε με όση ακρίβεια θέλουμε.
Γενικότερα, θα θέλαμε να βρούμε έναν περιορισμό του υποσυνόλου αυτού που έχει στοιχεία που αρκούν για να προκύψουν όλα τα άλλα στοιχεία σαν ελάχιστα άνω όρια (least upper bounds). Επομένως, ορίζεται η βάση (base) ενός μερικά διατεταγμένου συνόλου P σαν το υποσύνολο B του P, τέτοιο ώστε, για κάθε x στο P, το σύνολο των στοιχείων του B που είναι κάτω από το x να περιέχει ένα κατευθυνόμενο σύνολο με μέγιστο στοιχείο το x. Το μερικά διατεταγμένο σύνολο P είναι συνεχές μερικά διατεταγμένο σύνολο (continuous poset) αν έχει κάποια βάση. Ειδικότερα, το ίδιο το P αποτελεί βάση σε αυτήν την περίπτωση. Σε πολλές εφαρμογές, το βασικό αντικείμενο μελέτης είναι τα συνεχή (κατευθυνόμενα) μερικά διατεταγμένα σύνολα.
Τέλος, ένας ισχυρότερος περιορισμός σε ένα μερικά διατεταγμένο σύνολο δίνεται από την απαίτηση να υπάρχει μια βάση από συμπαγή στοιχεία. Ένα τέτοιο μερικά διατεταγμένο σύνολο αποκαλείται αλγεβρικό (algebraic poset). Από την πλευρά της δηωτικής σημασιολογίας, τα αλγεβρικά μερικά διατεταγμένα σύνολα έχουν πολύ καλή συμπεριφορά, επειδή επιτρέπουν την προσέγγιση όλων των στοιχείων, ακόμα και όταν αυτό περιορίζεται στα πεπερασμένα στοιχεία. Όπως αναφέρθηκε και πιο πριν, κάθε πεπερασμένο στοιχείο δεν είναι απαραίτητα "πεπερασμένο" κατά την κλασική μαθηματική έννοια και τα πεπερασμένα στοιχεία μπορεί να αποτελούν ένα μη αριθμήσιμο (uncountable) σύνολο.
Υπάρχουν περιπτώσεις που η βάση ενός μερικά διατεταγμένου συνόλου είναι αριθμήσιμη. Σε αυτήν την περίπτωση, το μερικά διατεταγμένο σύνολο ονομάζεται ω-συνεχές (ω-continuous). Όμοια, αν το αριθμήσιμο σύνολο αποτελείται εξολοκλήρου από πεπερασμένα στοιχεία, προκύπτει μια διάταξη που είναι ω-αλγεβρική (ω-algebraic).

Ειδικοί τύποι πεδίων

Μια ειδική περίπτωση πεδίων είναι το στοιχειώδες (elementary) ή επίπεδο πεδίο (flat domain). Αυτό αποτελείται από ένα σύνολο από μη συγκρίσιμα στοιχεία, όπως οι ακέραιοι, μαζί με ένα μοναδικό στοιχείο ("bottom") που θεωρείται μικρότερο από όλα τα άλλα στοιχεία.
Υπάρχουν αρκετές ειδικές περιπτώσεις διατεταγμένων δομών που μπορούν να είναι κατάλληλες σαν "πεδία". Ήδη αναφέρθηκαν τα συνεχή και τα αλγεβρικά μερικά διατεταγμένα σύνολο. Ειδικότερες περιπτώσεις και των δύο είναι οι συνεχείς και αλγεβρικές πλήρεις μερικές διατάξεις  (complete partial orders, cpos). Η προσθήκη περισσότερων ιδιοτήτων πληρότητας οδηγεί στα συνεχή δικτυωτά (continuous lattices) και στα αλγεβρικά δικτυωτά (algebraic lattices), τα οποία είναι απλά πλήρη δικτυωτά με τις αντίστοιχες ιδιότητες. Για την αλγεβρική περίπτωση, υπάρχουν ευρύτερες κλάσεις από μερικά διατεταγμένα σύνολα που μπορούν να μελετηθούν: ιστορικά, τα πεδία Scott ήταν οι πρώτες δομές που μελετήθηκαν στη θεωρία πεδίων. Ακόμα πιο ευρείς κλάσεις πεδίων αποτελούνται από τα πεδία SFP (SFP-domains), τα πεδία L (L-domains), και τα bifinite domains.
Όλες αυτές οι κλάσεις διατάξεων μπορούν να τοποθετηθούν σε διάφορες κατηγορίες από dcpos, με τη χρήση συναρτήσεων που είναι μονότονες, συνεχείς κατά Scott, ή ακόμα πιο εξειδικευμένες, σαν μορφισμούς (morphisms). Τέλος, ο ίδιος ο όρος πεδίο δεν είναι ακριβής και χρησιμοποιείται μόνο για συντομία όταν έχει προηγηθεί κάποιος τυπικός ορισμός, ή όταν οι λεπτομέρειες μπορούν να παραλειφθούν.

Σημαντικά αποτελέσματα

Ένα μερικά διατεταγμένο σύνολο D είναι dcpo αν και μόνο αν κάθε αλυσίδα (chain) στο D έχει μέγιστο στοιχείο. Τα κατευθυνόμενα σύνολα είναι γνήσια πιο ισχυρά από τις αλυσίδες.
Αν η f είναι συνεχής συνάρτηση σε ένα μερικά διατεταγμένο σύνολο D τότε έχει ένα ελάχιστο σταθερό σημείο (least fixed point), που δίνεται σαν το ελάχιστο άνω οριο όλων των πεπερασμένων επαναλήψεων της f στο ελάχιστο στοιχείο 0: Vₙ ∈ N f ⁿ(0).