Ορισμός και Ιστορική Αναδρομή

Ο όρος Συναρτησιακός Προγραμματισμός (ΣΠ) (Functional Programming), προσδιορίζει μια νέα κατηγορία γλωσσών προγραμματισμού, μια νέα γεννιά εργαλείων. Κέντρικη έννοια στον ΣΠ είναι αυτή της συνάρτησης από τα κλασικά μαθηματικά, όπως στο ΣΠ βήμα της οποίας αντιστοιχεί στην αντικατάσταση συμβόλων (symbol subsitution). H κίνηση αυτή υλοποιείται είτε πάνω σε χαρτί από το χέρι ενός μαθηματικού είτε πάνω στις πύλες ενός ηλεκτρονικού κυκλώματος. Η συνάρτηση

διαδικασία δηλώνει στη μηχανή που την «εκτελεί» τι είδους αντικαταστάσεις συμβόλων πρέπει να γίνουν μέχρι να προκύψουν σύμβολα πάνω στα οποία η μηχανή δεν έχει άλλες αντικαταστάσεις να κάνει. Πάνω στα αρχικό σύμβολα (πρόγραμμα και δεδομένα) λέμε ότι εφαρμόζουμε συναρτήσεις, μια μορφή «εντολών». Μια άλλη ονομασία για τον ΣΠ, που προκύπτει από την εφαρμογή συναρτήσεών, είναι Applicative Programming. Η εφαρμογή ή κάλεσμα της συνάρτησης πάνω σε ένα αντικείμενο έχει αποτέλεσμα κάποιο άλλο αντικείμενο, αν αυτό περιέχει κι άλλες εφαρμογές συναρτήσεων τότε προκύπτει νέο αντικείμενο κ.ο.κ. μέχρι το τέλος της διαδικασίας, εκτός βέβαια αν πρόκειται για διαδικασία με μη πεπερασμένο αριθμό βημάτων.

Πρώτη γλώσσα ΣΠ ήταν η LlSP (MacCarthy 1960), μια γλώσσα για υπολογισμό συμβόλων (symbolic computation) σε αντίθεση με τις τότε υπάρχουσες γλώσσες κατάλληλες για υπολογισμό αριθμών (numerical computation). Προβληματισμός για τις θεωρητικές βάσεις του φαινομένου των ηλεκτρονικών υπολογιστών και των γλωσσών προγραμματισμού των καθώς και ο σχεδιασμός «έξυπνων» εφαρμογών από τον τομέα της Τεχνητής Νοημοσύνης έδωσαν ώθηση στον ΣΠ. Είναι προφητικός ίσως ο τίτλος της μελέτης «οι επόμενες 700 γλώσσες προγραμματισμού» από το σχεδιαστή της γλώσσας ΣΠ ISWM (Landin 1966). Στη δεκαετία του 70 ο αριθμός των γλωσσών προγραμματισμού που εμφανίζονται σε ανεξόρτητες μελέτες από διάφορες χώρες αυξό- νει σημαντικό με πιο γνωστούς εκπροσώπους τις γλώσσες REFAL {Turchin ΕΣΣΔ}, ΗΟΡΕ (σχολή Εδιμβούργου}, SASL {Turner Αγγλία} κ.α. Επίσημη έναρξη στον ΣΠ θεωρείται η μελέτη του Backus (1978 ΗΠΑ) με τίτλο «είναι δυνατή η απελευθέρωση του προγραμματισμού από το στυλ του Von Neumann;» παρουσιάζοντας τη γλώσσα FP και σχετική άλγεβρα προγραμμάτων. Σημειωτέον ο Backus ήταν ο κατασκευαστής του πρώτου μεταγλωττιστή της FORTRAN.

Η διάδοση του ΣΠ καθυστέρησε σημαντικό λόγω της μεγάλης δαπάνης σε χώρο-χρόνο μηχανής που καταναλώνει η εκτέλεση προγραμμάτων σε γλώσσα ΣΠ καθώς και στην έλλειψη πείρας προγραμματισμού προβλημάτων. Αυτό είχε σαν αποτέλεσμα να ενσωματωθούν αρχικά στις «καθαρές» γλώσσες ΣΠ στοιχεία προγραμματισμού από τις κλασικές, όπως έγινε με τις εντολές SETQ KaLPROG (οι γνωστές := και GOTO) στη LISP. Οι εντολές αυτές χαρακτηρίζουν όλες τις γλώσσες του Προστακτικού Προγραμματισμού» (ΠΠ) (Imperative Programming). Ο όρος «προστακτικός» αναφέ- ρεται στο στυλ προγραμματισμού που επιβάλουν οι κλασι- κές γλώσσες FORTRAN, COBOL, ALGOL, PASCAL, C κ.α. Αυτή η δομή των γλωσσών προγραμματισμού προκύπτει από την αντίστοιχη δομή της μηχανής. Ονομάζεται Von Neumann (VN) παίρνοντας το όνομα του εφευρέτη του Η/Υ John νοη Neumann (1945) και που αποτελεί και σήμερα το βασικό οδηγό αρχιτεκτονικής των Η/Υ. Η δομή όμως των γλωσσών ΣΠ βρίσκεται σε πλήρη αναντιστοιχία με τη δομή νΝ, με αποτέλεσμα τη μεγόλη δαπόνη σε χώρο-χρόνο μηχανής που απαιτείται ώστε η μηχανή του Von Newmann να «προσαρμο- στεί» στην λογική του ΣΠ (θέμα του επόμενου κεφαλαίου).

Το 1975 ο Burge έκδοσε το βιβλίο Resursive programming techniques που έδειχνε πώς να προγραμματιστούν στη νέα μεθοδολογία του ΣΠ μια σειρό κλασικοί αλγόριθμοι (διατάξεις, μεταθέσεις, γράφοι, λεκτική και συνταχτική ανάλυση γλωσσών προγραμματισμού κ.α.). Σταδιακό αποκτήθηκε η πείρα, στη συλλογή όρθρων Applicative programming C.U.P. London 1982 (Henderson) για τον ΣΠ αναφέρθηκαν ακόμα και προσεγγίσεις σε προβλήματα του προγραμματισμού συστήματος. Παρόλη τη βελτίωση στις τεχνικές υλοποίησης της εγκατάστασης του ΣΠ πάνω στις μηχανές παραγωγής με τη γνωστή VΝ αρχιτεκτονική (μοναδιαίας κεντρικής μονάδας cpu) η δαπάνη σε χώρο-χρόνο μηχανής καθιστά τον ΣΠ, ακόμα και σήμερα, κατάλληλο μόνο για εργαστηριακή χρήση. Η πρόοδος σε αυτόν τον τομέα του ΣΠ αναμένεται από τις εξελίξεις στον τομέα υλικού όπου η τεχνική ολοκλήρωσης κυκλωμάτων σε μεγάλη κλίμακα VLSI επιτρέπει την κατασκευή μηχανών με μεγάλο αριθμό επεξεργαστών σε δίκτυο (μηχανές ροής δεδομένων -data flow machines). Για άλλους όπως ο Bauer [4] δεν αναμένεται τέτοια πρόοδος και δίνουν έμφαση στον ΣΠ από όλλη σκοπιά, αυτήν των πρoδιαγραφών (specification) προγράμματος.

Σημαντικός παράγοντας υπέρ του ΣΠ είναι το πρόβλημα που κυριαρχεί στον οικονομικό τομέα όπου το κόστους του λογισμικού συνεχώς αυξάνεται σε σχέση με το κόστος του υλικού (δες Σχήμα 1 ). Το κόστος συντήρησης ή τροποποίησης μεγάλων προγραμμάτων πλησιάζει το κόστος επαναπρογραμματισμού των. Η αυτοματοποίηση σύνθετων διαδικασιών συναντά εμπόδια λόγω του όγκου και της πολυπλοκότητας των προγραμμάτων που απαιτούνται. Η κατασκευή προγραμμάτων μέσω της σύνθεσης ήδη κατασκευασμένων είναι αδύνατη λόγω της δομής του μοντέλου VΝ. Ακόμη και σήμερα ο μέσος χρήστης της Πληροφορικής (λογιστής, επιχειρηματίας, επιστήμων, μηχανικός) χρειάζεται τον έμπειρο τεχνικό για τις πιο στοιχειώδεις εφαρμογές. Στη δεκαετία του '70 στις αναπτυγμένες χώρες επικρότησε η φράση «κρίση λογισμικού» (software crisis).

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

Από μια άλλη σκοπιά (Turchin 1972) ο ΣΠ αποτελεί την προσπάθεια μιας νέας επιστήμης, αυτής που στόχο έχει την κατασκευή "έξυπνων" μηχανών, να αποκτήσει μια κοινή γλώσσα, ένα καθολικό σύστημα αναφοράς όπως έχει γίνει με κάθε άλλη επιστήμη που έφτασε ορισμένο στάδιο ωριμότητας. Σε κάθε περίπτωση ο ΣΠ έχει γίνει το επίκεντρο αναζήτησης λύσεων στα προβλήματα που αναφέρθηκαν καθώς και πηγή δημιουργίας νέων ιδεών, το πιό γνωστό από όλα είναι το παράδειγμα της μεθοδολογίας της γλώσσας PROLOG και του Λογικού Προγραμματισμού. Χώρες όπως η Ιαπωνία (1980) έχουν ξεκινήσει προγράμματα Έρευνας και Ανάπτυξης με βασικό πυρήνα τις ιδέες του Συναρτησιακού και Λογικού Προγραμματισμού.

2. Οι συνέπειες της αρχιτεκτονικής VON NEUMANN.

Η ικανότητα του ανθρώπου να κατασκευάζει εργαλεία φαίνεται να ακολουθεί την εξής λογική: Όταν προκύπτουν προβλήματα για τα οποία τα υπάρχοντα εργαλεία δεν επαρκούν, η προσοχή στρέφεται στις μεθόδους που χρησιμοποιούνται, στα εργαλεία. Ακολουθεί περίοδος αναζήτησης νέων μεθόδων δηλ. ΜΕΤΑ-εργαλέιων που θα οδηγήσουν στην κατασκευή εργαλείων για την λύση των αρχικών προβλημάτων που είχαν ανασταλλεί. Ο λόγος που τα "νέα" εργαλεία γνωστά σαν Δομημένος Προγραμματισμός (Structured Programming) δεν απέδωσαν τα αναμενόμενα αποτελέσματα είναι ότι δεν άλλαξαν ριζικά τα υπάρχοντα εργαλεία προγραμματισμού. Πράγματι, ο Δομημένος Προγραμματισμός αντικατάστησε τον αδόμητο έλεγχο προγράμματος, μέσω της εντολής GOTO, με το Δομημένο των εντολών FOR, WHILE, IF, BEGIN, END, PROCEDURE, ώστε να επιβάλεται κάποια δομή στο πρόγραμμα. Όμως οι δυο βασικές έννοιες προγραμματισμού:

α. Απόδοση τιμής (Assignment) πχ. Κ:=Α+Β
β. Ακολουθιακή σειρά στην εκτέλεση εντολών (μη παράλληλη εκτέλεση πχ. του Α και Β)
διαπερνούν όλες τιε γλώσσες. Ποιά η προέλευση των α και β; Τα τελευταία 30 χρόνια παρόλες τις αλλαγές που συντελέστηνα στην κατασκευή Η/Υ το σχέδιο που παρουσίασε ο John Von Newmann το 1945 παρέμεινε το πρότυπο κάθε νέας μηχανής και γλώσσας:

Υλικό:

• Μία Κεντρική Μονάδα Επεξεργαστών (Central Processing Unit)
• σειρά θέσεων μνήμης με δυαδικές λέξεις (Store of Binary Words)
• Δίαυλος σύνδεσης ΚΜΕ-Μνήμης (Σχ.2)

Λογισμικό:

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

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

Στον τομέα του λογισμικού ο προγραμματιστής πρέπει να εκφράσει τον αλγόριθμο του σε "μονάδες" δυαδικών λέξεων και πράξεων με αυτές, μέσω των γνωστών μεταβλητών (στην ουσία πρόκειται για ονομασίες θέσεων αντί των μεταβλητών που συναντάμε στα μαθηματικά). Η μνήμη που καταγράφει την πορεία του υπολογισμού δεν επιδέχεται μεγαλύτερες αλλαγές από αυτές της μιας λέξης και στη σειρά ή μια αλλαγή μετά την άλλη. 'Όμως μεγάλα προγράμματα σ' αυτό το σύστημα αναφοράς δημιουργούν αχαλίνωτη πολυπλοκότητα. Το κάθε VN πρόγραμμα συσχετίζεται με ένα αντίστοιχο πλάνο που προσδιορίζει την θέση των δεδομένων στη μνήμη. Το πλάνο επιτρέπει στη δομή των δεδομένων να «καθίσει» ομαλό πάνω στην αδόμητη σειρά θέσεων της μνήμης. Η κατασκευή μεγάλων προγραμμάτων από μικρότερα είναι μόνο δυνατή όταν τα δεύτερα έχουν κοινό πλάνο μνήμης. Αυτό σημαίνει ότι όλα τα υποπρογράμματα πρέπει να σχεδιαστούν μαζί, με αποτέλεσμα να είναι αδύνατη η σταδιακή κατασκευή όλο και μεγαλύτερων προγραμμάτων από ήδη κατασκευασμένα σε χρήση προγράμματα. Ας πάρουμε ένα παράδειγμα από την επεξεργασία πινάκων. 'Έχουμε ένα πρόγραμμα που αντιστρέφει πίνακα και ένα που κάνει μετάθεση πίνακα. Τώρα αν ζητηθεί ένα νέο πρόγραμμα που βρίσκει την αντιστροφή της μετάθεσης ενός πίνακα φαίνεται ότι η λύση βρίσκεται απλό στην σύνθεση των δοσμένων προγραμμάτων. 'Όμως αυτό είναι δυνατόν μόνο όταν έχουν κοινό πλάνα μνήμης και συνήθως πλάνα αυτόνομων προγραμμάτων δεν συμπίπτουν. Βλέπουμε λοιπόν ότι ενώ ο σκοπός ενός προγράμματος είναι η απεικόνιση πινάκων σε πίνακες, αυτό το σύστημα προγραμματισμού εξαναγκάζει το χρήστη να τον μεταφράσει σε απεικόνιση μεταξύ πλάνων μνήμης έτσι ώστε οι θέσεις εξόδου του πρώτου προγράμματος να συμπίπτουν με τις θέσεις του δεύτερου. Αυτή την τάξη πραγμάτων που έχει καθιερωθεί με την ονομασία του δημιουργού της: το μοντέλο Von Neumann (VN) απειλεί ο ΣΠ.

3. Βασικές 'Έννοιες ΣΠ.

Η κάθε γλώσσα ΣΠ έχει τη δική της ιδιαίτερη φιλοσοφία η οποία εκφράζεται στο συντακτικό και στη σημαντική της γλώσσας (syntax/semantics). Η LlSP στα αντικείμενα επεξεργασίας περιλαμβάνει τα ίδια τα προγράμματα της πράγμα που διευκολύνει την κατασκευή προγραμμάτων που δρουν πάνω σε άλλα προγράμματα, παραδείγματος χάριν γεννήτριες προγράμματος (program generators) ή προγράμματα που έχουν στόχο την αυτόματη απόδειξη ιδιοτήτων ποu εξάγονται από δοσμένο πρόγραμμα (program provers). Η ΗΟΡΕ δίνει έμφαση στο μετασχηματισμό προγραμμάτων (program transformation) για λόγους βελτιστοποίησης αναγκαία για να βρεθεί γέφυρα ανάμεσα στην αναντιστοιχία των δομών αρχικού προγράμματος σε ΣΠ και τελικού προγράμματος μηχανής VΝ. ΟΙ γλώσσες SASL, KRC, ΜΙΑΑΝΟΑ, FP, OBJ δίνουν έμφαση στις δομές «υψηλού επιπέδου» που παρέχουν στο χρήστη επαυξημένη παραγωγικότητα, ιδιαίτερα στο σχεδιασμό σύνθετων προγραμμάτων. Τέλος, η REFAL (REcursive Function Aigorithmic Language) έχει σαν φιλοσοφία της την έκφραση καθολικών εννοιών προγραμματισμού (π.χ. αφαίρεση) με στόχο την μηχανοποίηση της διαδικασίας (είναι κι αυτή μια συνάρτηση ΣΠ) που γεννά νέα εργαλεία όπως μεταγλωττιστές, πρόγραμμα- τα που δρουν πάνω σε βάσεις δεδομένων, έμπειρα προγράμματα κ.α. 'Όλες αυτές οι γλώσσες ΣΠ διέπονται από κοινές βασικές αρχές, οι οποίες προκύπτουν κυρίως από την κριτική που κάνουν στον ΠΠ του Von Neumann.

Η διαχωριστική γραμμή για τον ΣΠ είναι η έκφραση αλγορίθμων χωρίς την χρήση της έννοιας καταχώρηση (assignment) σε θέση μνήμης και η μοναδική έννοια (εντολή) ελέγχου ροής προγράμματος είναι η εφαρμογή συνάρτησης πάνω σε αντικείμενο με αποτέλεσμα την τροποποίηση του (νέο αντικείμενο). Ο προγραμματιστής έχοντας αρχικό ορίσει τις διάφορες συναρτήσεις-διαδικασίες που απαρτίζουν το Πρόγραμμα του, πυροδοτεί την «εκτέλεσή» τους δίνοντας στο σύστημα ΣΠ μια έκφραση που περιέχει εφαρμογή συνάρτησης. Αν όχι το σύστημα απλό επαναλαμβάνει την έκφραση:

τα σύμβολα και δηλώνουν ένα και πολλά βήματα της μηχανής ΣΠ αντίστοιχα. Δεν έχουν όμως νόημα για τον ΣΠ.
Η συνάρτηση Ρ που υπολογίζει το παραγοντικό γινόμενο γράφεται με τις εξής δυο προτάσεις ΣΠ:

Ρ Ο = 1
ΡΝ=Ν*Ρ(Ν-1)

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

Το «διάβασμα» του προγράμματος ΣΠ δεν είναι και πολύ μακριά από την περιγραφή του αλγόριθμου στην φυσική μας γλώσσα.

Η έκφραση Ρ 4 θα οδηγήσει την «μηχανή» στα εξής βήματα

Βέβαια στη μηχανή εκτός της συνάρτησης Ρ έχουν δοθεί στοιχεία για την αριθμητική με ακέραιους, τι είδους αντικαταστάσεις θα κάνει για αυτό το είδος συμβόλων. Σε γλώσσα (μηχανή) με έλλειψη τέτοιας πληροφορίας οι ακέραιοι συμβολίζονταν σαν 0, 0', 0" κτλ. που είναι κώδικας για το 0, 1 , 2 κτλ. Η συνάρτηση που ακολουθεί παράγει όλους το ακέραιους:

Α Ν = Ν (Α Ν') όπου Ν δηλώνει μορφή συμβόλων

Η εφαρμογή της συνάρτησης Α πάνω στο αντικείμενο 0 (ένα σύμβολο της γλώσσας) πυροδοτεί τα εξής βήματα:

A 0—›0 (A 0')—›0 0' (A o'')—›0 0' 0'' (A 0''')—›κοκ

Βλέπουμε ότι η διαδικασία Α έχει άπειρο αριθμό βημάτων, ο ΣΠ δεν έχει πρόβλημα στο να χειριστεί και τέτοιου είδους αντικείμενα. Αυτό είναι δυνατόν γιατί η μηχανή ΣΠ, που εκτελεί τη γλώσσα, εφαρμόζει μια «στρατηγική» αντικατάστασης συμβόλων πάνω σε εκφράσεις ΣΠ που χαρακτηρίζεται από αναβλητικότητα όσον αφορά την αποκωδικοποίηση των συμβόλων .Για παράδειγμα στο δεύτερο βήμα της διαδικασίας Α, παραπάνω, πρώτα απαντάει στην έξοδο του συστήματος ότι πληροφορία του είναι δυνατόν, έστω ελλιπή (μια και δεν γνωρίζει το αποτέλεσμα της υποέκφρασης Α 0’) και κατόπιν προχωράει για περισσότερη πληροφορία προς ολοκλήρωση της απάντησης του. Η στρατηγική αυτή ονομάζεται αναβλητική εκτέλεση (Iazy evaluation). Μηχανιστικά μπορούμε να την περιγράψουμε σαν ΑΠΟ ΕΞΩ ΠΡΟΣ ΤΑ ΜΕΣΑ. Φυσικό αν η γλώσσα ΣΠ δεν κάνει χρήση αυτής της στρατηγικής τότε το σύστημα δεν «βγάζει» έξω καμιά πληροφορία,
κανένα σύμβολο, μια και η στρατηγική του ΑΠΟ ΜΕΣΑ ΠΡΟΣ ΤΑ ΕΞΩ ρίχνει τον εκτελούντα μηχανισμό σε βρόγχο (Ιοορ). Αυτό συμβαίνει γιατί το σύστημα πριν δώσει οτιδήποτε στην έξοδο του επιζητεί το αποτέλεσμα της υποέκφρασης Α 0'.
Μια συνάρτηση μπορεί να έχει περισσότερες παραμέτρους και συνθήκες επιλογής προτάσεων (γενίκευση της εντολής IF). Η συνάρτηση που ακολουθεί υπολογίζει το Μέγιστο Κοινό Διαιρέτη δυο ακεραίων

Το όνομα της συνάρτησης και οι παράμετροι παραλείπονται στις δυο τελευταίες προτάσεις, για λόγους συνταχτικής οικονομίας. Το «,» (διαβάζεται «εάν») δηλώνει επιλογή με συνθήκη την «τιμή» των παραμέτρων της συνάρτησης Μ. Ξεκινώντας τη Μ πάνω στους αριθμούς 4 και 6, για εύρεση του ΜΚΔ των θα έχουμε τα εξής βήματα:

Μερικές γλώσσες ΣΠ «ανεβαίνουν" το επίπεδο της αντικατάστασης συμβόλων και για διευκόλυνση των χρηστών προσφέρουν έννοιες όπως δομές πάνω στα αντικείμενα, τα οποία τώρα δεν είναι απλά σειρά συμβόλων αλλά λίστες ή δένδρα (αν και σε τελευταία ανάλυση μεταφράζονται στην βασική εντολή του ΣΠ).

Πιο γνωστή είναι η δομή λίστα, οι εκφράσεις:

είναι Λίστες με τέσσερα, τρία και καθόλου μέλη αντίστοιχα. Η έκφραση 22 : [17,2,4] δημιουργεί νέα τετραμελή λίστα [22,17 ,2,4]. Παρομοίως η πράξη « + + " με λίστες ορίζεται από τις προτάσεις που ακολουθούν με τη συνάρτηση ενδιάμεσα των παραμέτρων (infix operator):

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

ΑΝΤΙΣΤΡΟΦΗ [] = []
(κ : υπολ) = ΑΝΤΙΣΤΡΟΦΗ υπολ ++ [κ]

η εφαρμογή ΑΝΤΙΣΤΡΟΦΗ [3,4,5] —..—›[5,4,3] έχει αποτέλεσμα τη λίστα [5,4,3].

Η συνάρτηση ΔΙΑΤΑΞΗ υλοποιεί τον αλγόριθμο διάταξης ακεραίων κατά αύξουσα σειρά SIMPLE-SORT:

Ας παρακολουθήσουμε τα βήματα της μηχανής στη ταξη των ακεραίων 8 11 και 2:

η δεύτερη παράμετρος της συνάρτησης ΘΕΣΗ πρέπει να υπολογιστεί για να γίνει η επιλογή της κατάλληλης πρότασης:

Ο μηχανισμός της αναδρομής συνεπάγεται μεγάλο κόστος σε χώρο-χρόνο μηχανής. Η γλώσσα ΣΠ «ανεβαίνει», ένα επίπεδο (εκφραστικότητας) αφήνοντας την αναδρομή σε ειδικές «στάνταρ» συναρτήσεις του εμπεριέχουν την αναδρομή. Η FP καταργεί επίσης τις παραμέτρους συναρτήσεων. Η συνάρτηση ΜΗΚΟΣ πάνω σε λίστες ορίζεται συνήθως από δυο προτάσεις:

Η αντίστοιχη έκφραση στην FP είναι ΜΗΚΟΣ = / ο α 1 και η εφαρμογή της πάνω στην λίστα [8,9,2] πυροδοτεί τα εξής βήματα της μηχανής ΣΠ:

«F ο G x» σημαίνει εφαρμογή της F πάνω στο αντικείμενο που προκύπτει από την εφαρμογή της G στο δοσμένο αντικείμενο x. Στο παράδειγμα F και G είναι οι συναρτήσεις /+ και α1 και x είναι η λίστα [8,9,2].

«α 1» σημαίνει εφαρμογή της συνάρτησης 1 σ' όλα τα μέλη της λίστας, η συνάρτηση 1 μετατρέπει κάθε αντικείμενο στον ακέραιο 1.

«/ +» σημαίνει τοποθέτηση της πράξης «+», μεταξύ των μελών της λίστας, πάνω στην οποία εφαρμόζεται.

Στο παραπάνω παράδειγμα ο μηχανισμός της αναδρομής περιέχεται στις στάνταρ συναρτήσεις της FP «α» και «/>, που είναι δοσμένες για το χρήστη της γλώσσας FP καθώς και η συνάρτηση «ο». Το συντακτικό της τελευταίας διαφέρει στο ότι γράφεται στο ενδιάμεσο των δυο παραμέτρων της (infix notation).

Οι στάνταρ συναρτήσεις 0, /, α εφαρμόζονται σε αντικείμενα που τα ίδια είναι συναρτήσεις. Το αποτέλεσμα της εφαρμογής τους είναι μια νέα συνάρτηση π.χ. η F ο G. Στον ΣΠ ονομάζονται συναρτήσεις Μεγαλύτερης Τάξης (ΜΤ) (Ηίgher Order Functions).

Η σημασία των συναρτήσεων ΜΤ βρίσκεται στη μεθοδολογία προγραμματισμού που εισάγουν. Μια συνάρτηση ΜΤ είναι στην ουσία ένα πακέτο συναρτήσεων παραμετροποιημένο. Η μεταβολή παραμέτρων του πακέτου οδηγεί στην αυτόματη παραγωγή της ζητούμενης συνάρτησης.

Η θεώρηση των συναρτήσεων σαν προγραμμάτων δείχνει την πραγματική αξία της μεθοδολογίας στο παράδειγμα που ακολουθεί η συνάρτηση ΜΤ ονομάζεται FOLDR και ορίζεται από τις δυο προτάσεις:

Ο έλεγχος των παραμέτρων ορ και k οδηγεί σ' όλες τις γνωστές συναρτήσεις πάνω σε λίστες:
FOLDR ( + ) 0 είναι η συνάρτηση που βρίσκει το άθροισμα λίστας FOLDR (•) 1 είναι η συνάρτηση που βρίσκει το γινόμενο λίστας.

Παρατηρούμε ότι οι δυο προηγούμενες συναρτήσεις είναι ανώνυμες και οι δυο εφαρμόζονται (παίρνουν σαν παράμετρο) σε λίστες π.χ. FOLDR (+) Ο [1,2,3]—..—› 6. Επίσης ότι δεν έχουν περιορισμούς στη χρήση τους. Μπορούν να γίνουν παράμετροι ή αποτέλεσμα άλλων συναρτήσεων, να είναι μέλη λίστας.

Αρχικά το κόστος της υλοποίησης συναρτήσεων ΜΤ περιόριζε την σημασία τους. 'Όμως ένα σπουδαίο αποτέλεσμα του Turner στη θεωρία συνδυαστικής έκανε το κόστος σε χώρο-χρόνο μηχανής μηδέν μετά από το πρώτο κάλεσμά τους και αυτό γιατί η μηχανή απλά εκτελεί τα βήματα που θα ακολουθούσε ο προγραμματιστής να ορίσει συναρτήσεις π.χ. για άθροισμα και γινόμενο στο παραπάνω παράδειγμα. 'Όταν γίνει αυτό δεν μεσολαβεί κανένα άλλο κόστος λόγω χρήσης της FOLDR αντί των συναρτήσεων ΑΘΡΟΙΣΜΑ και ΓΙΝΟΜΕΝΟ «χειροκίνητης» προέλευσης:

Στο παράδειγμα που ακολουθεί ορίζεται ο τύπος δένδρο ακέραιων στην γλώσσα SASL

Δενδ : : = ΚενοΔενδ Ι Κομβ integer Δενδ Δενδ

Η εξίσωση δηλώνει τρία νέα ονόματα, «Δενδ» το όνομα του τύπου, «ΚενοΔενδ» και «Κομβ» που είναι ειδικά σύμβολα κατασκευής τύπων (type constructors). Το Δενδ είναι κενό ή έχει τη δομή που αποτελείται από έναν ακέραιο και δυο Δενδ. Η έκφραση που ακολουθεί χτίζει ένα μικρό δέντρο:

Κομβ 11 (Κομβ 3 ΚενονΔ ΚενονΔ) (Κομβ 8 ΚενονΔ ΚενονΔ)

Για να βρεθεί ο τύπος κάποιου αντικειμένου ο ΣΠ χρησιμοποιεί τον ένθετο μηχανισμό (pattern atching) πάνω στις παραμέτρους συναρτήσεων όπως στο παράδειγμα της συνάρτησής ΣΥΜ που κατασκευάζει το συμμετρικό -είδωλο ενός Δένδρου (Σχ. 3).

Η εισαγωγή του μηχανισμού των τύπων στο ΣΠ εξασφαλίζει μεγαλύτερη ασφάλεια από λάθη. Η συνάρτηση ΣΥΜ είναι τύπου (•—›•) δηλαδή συνάρτηση από αντικείμενα τύπου • σε αντικείμενα του ίδιου τύπου, όπου • είναι μια μεταβλητή τύπων.

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

Σε άλλες γλώσσες όπως στη ΗΟΡΕ ο χρήστης δίνει τον τύπο των συναρτήσεων που χρησιμοποιεί:

dec reverse : list (alpha) —› list (alpha)

Εδώ, ορίζεται η συνάρτηση reverse (αντιστροφή, ορίστηκε προηγούμενα από λίστες αντικειμένων τύπου alpha σε παρόμοιες λίστες). Έτσι αν η συνάρτηση εφαρμοστεί σε αντικείμενο διαφορετικού τύπου, το σύστημα θα εντοπίσει τέτοιο λάθος και θα προειδοποιήσει τον χρήστη. Η ΗΟΡΕ στην κατεύθυνση αυτή ορίζει την έννοια του module:

module Κ
publype W
uses mname
end

Τύποι που ορίζονται εντός του Κ δεν είναι προσιτοί στο υπόλοιπο πρόγραμμα. Αν κάτι πρέπει να μην κρυφτεί τότε ορίζεται μέσα στο Κ σαν pubtype W δηλαδή ο τύπος W είναι κοινός. Επίσης μέσα στο Κ τίποτε δεν φαίνεται από το υπόλοιπο πρόγραμμα, πέρα από τα όριά του, εκτός εάν κάτι έχει δηλωθεί με την φράση uses mname οπότε το αντικειμενο mname εισάγεται μέσα στο Κ.

4. Ορθότητα /πιστοποίηση προγραμμάτων.

Ένα από τα πιο βασικά προτερήματα του ΣΠ είναι ότι επιτρέπει την ανάπτυξη τεχνικής ορθότητας προγραμμάτων (program proving). Οι ιδιότητες τις οποίες πρέπει να υπακούει το πρόγραμμα εκφράζονται στη ίδια την γλώσσα των «εξισώσεων». Έστω ότι δίδονται δυο διαφορετικό προγράμματα για το παραγοντικό γινόμενο αριθμού n:
ΡΟ = 1
Ρ n = n Ρ (n -1 )
For = r
F ο r = F (n -1) (n • r)

Το ζητούμενο είναι να αποδειχτεί η πρόταση Ρ n = F n 1 κάνοντας χρήση των προτάσεων. Θέτοντας n=3 έχουμε:

Ρ 3 —›3 • Ρ 2 —..—›6
F 3 1—›F 2 3—›f 1 6—›f 0 6—›6

Πράγματι για n=3 ισχύει η πρόταση Ρ 3 = F 3 1. Για να αποδειχτεί για κάθε αριθμό n, χρειάζεται ένας κανόνας μέσω του οποίου να εξάγουμε «άπειρα» συμπεράσματα χωρίς να , εφαρμόζουμε τον κανόνα άπειρες φορές. Τέτοιος κανόνας μας είναι γνωστός από τα σχολικά μαθηματικά σαν μαθηματική επαγωγή: Για να αποδείξουμε ότι ισχύει Π (χ) πρώτα αποδείχνουμε ότι ισχύει Π (0) και ύστερα αποδείχνουμε ότι ισχύει Π (k+1) χρησιμοποιώντας την υπόθεση ότι ισχύει Π (k). Φυσικά αυτός ο κανόνας ισχύει για αντικείμενο με τύπο ακέραιος. Παρόμοιοι κανόνες ισχύουν και για άλλα «άπειρα» αντικείμενα με τύπο λίστα, δένδρο κ.α. Θα χρησιμοποιήσουμε τον κανόνα αυτό για να αποδείξουμε την παραπάνω πρόταση αλλά σε πιο γενική μορφή: F n r = r Ρ n η οποία προκύπτει προφανώς για r = 1.
1) για n=O.
F O r = r = r • 1 = r • P 0
2) για n+1:
F (n+1) r = F n ( (n+1) • r ) = ( (n+1) • r) • Ρ n υπόθεση τώρα μέσω απλής άλγεβρας αναδιοργανώνουμε την τελευταία έκφραση σε r • ( (n+ 1 ) • Ρ n) που βάσει ορισμού της Ρ είναι ίση με την έκφραση Ρ (n+1). Άρα έχουμε:

F (π+1) ρ = r • Ρ (n+1) που είναι και το ζητούμενο.

Το τρικ της γενίκευσης της αρχικής πρότάσης προς απόδειξη είναι ένα από τα παράξενα, όμως είναι συχνό φαινόμενο και ονομάζεται ο κανόνας «εύρηκα». Το προτέρημα , του ΣΠ που επιτρέπει εφαρμογή τεχνικών απόδειξης ή πιστοποίησης προγραμμάτων (πιστοποίηση κάποιας ιδιότητός τους, εκφρασμένη σε σύμβολα) βρίσκεται στην απουσία εννοιών του ΠΠ, πράγμα που επιτρέπει την χωρίς εξαιρέσεις ισχύ την ισότητας (=) μεταξύ συμβόλων. Στο παράδειγμα του συμβολισμού με έννοιες ΠΠ:

παρατηρούμε ότι το πρώτο WRITE τυπώνει 10 και το δεύτερο 8, πράγμα που σημαίνει Α+Β είναι διαφορετικό του Β+Α, και οι πιο βασικές αλγεβρικές ιδιότητες δεν ισχύουν σ' αυτόν τον συμβολισμό λόγω του ρόλου που παίζει η φράση ΠΠ S := ΤRUΕ.

5. Σχέση με το Λογικό Προγραμματισμό (ΛΠ).

Οι θεωρητικές βάσεις του ΣΠ είναι τα μοντέλα υπολογισμού λ-λογισμός, Μηχανές Turing, Διαδικασίες Markov. Ο ΛΠ έχει σαν βάση του την Πρωτάξια Κατηγορηματική Λογική. Οι αντικαταστάσεις συμβόλων πάνω σε μια έκφραση του ΛΠ μπορούν και να αναιρεθούν γυρίζοντας πίσω το χρόνο της διαδικασίας που εκτελείται. Αντίθετα η πορεία των αντικαταστάσεων συμβόλων στο ΣΠ είναι μονόδρομος χωρίς επιστροφή. Αυτό είναι απόλυτα χρήσιμο στην περιγραφή αλγοριθμικών διαδικασιών ενώ ο μηχανισμός, μη ντετερμινιστικός, του ΛΠ είναι κατάλληλος για κατασκευή «έξυπνων» συστημάτων διερεύνησης βάσεων δεδομένων. Στον ΛΠ ο χρήστης ορίζει σχέσεις μεταξύ
αντικειμένων, έννοια πιο γενική της συνάρτησης (με την κλασική έννοια). Στον ΛΠ (της PROLOG τουλάχιστον), οι εκφράσεις του περιγράφουν σχέσεις και ιδιότητες που επιθυμούμε για το στόχο (goal) του προγράμματος. Αντίθετα στον ΣΠ ορίζουμε μια διαδικασία, μια σειρά από απόλυτα προσδιορισμένα βήματα. Σίγουρα κανένα σύστημα δεν είναι υποσύνολο του άλλου. Με την υλοποίηση της PROLOG σε μικροϋπολογιστές και την ευρεία διάδοσή της, έχει δημιουργηθεί η εντύπωση ότι αποτελεί τη γλώσσα του μέλλοντος, ότι αποτελεί την καθολική γλώσσα της Τεχνητής Νοημοσύνης (ΤΝ), στόχος μάλλον μακρινός για τις μη αλγοριθμικές δυνάμεις της, μια και η έννοια του αλγόριθμου παραμένει στη βάση της ΤΝ. Η υποχρεωτική κωδικοποίηση του αλγορίθμου σαν σύστημα σχέσεων δεν φαίνεται
να είναι απαραίτητη σε κάθε περίπτωση. Βέβαια η χρήση της PROLOG σαν γλώσσα για «έξυπνες» βάσεις δεδομένων δεσπόζει χωρίς συναγωνισμό. Αρκετές μελέτες έχουν ξεκινήσει για τον συνδυασμό αυτών των δυο αρκετά διαφορετικών συστημάτων.

6. Προοπτική του ΣΠ.

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

Βιβλιογραφία

1. Applicative Programming C.U.P., London 1982.
2. Backus J., Α Functional Style and its AIgebra of Programs, Comm. ACM 21, 613-41, 1978.
3. Landin Ρ., The next 700 Programming Ianguages, Comm. ACM 9, 157-66, 1966.
4. Tumer D., Α new implementation technique for applicative Ian- guages. SPE 1979.
5. MacCarthy J., Symbolic Expressions and their computation by machine. Comm. ACM 7, 184-95, 1060.
6. Burge W.. Recursive programming technique, Wesley, Reading, Mass. 1975.
7. Burstall R., ΗΟΡΕ: Απ experimental apρΙίcatίνe language, CSR-62-80 University of Edinburgh.
8.Turchin V., A supercompiler system based on the language REFAL, SIGPLAN Notices 14, 2 46-54, 1979.