Scheme

Η Scheme είναι η μια από τις δύο βασικές διαλέκτους της γλώσσας προγραμματισμού Lisp. Σε αντίθεση με την Common Lisp, την άλλη βασική διάλεκτο, η Scheme ακολουθεί μια μινιμαλιστική φιλοσοφία σχεδίασης, ορίζοντας ένα μικρό βασικό πυρήνα με ισχυρά εργαλεία για επέκταση της γλώσσας. Λόγω του μικρού της μεγέθους και της κομψότητάς της είναι δημοφιλής ανάμεσα στους εκπαιδευτικούς, τους σχεδιαστές γλωσσών, τους προγραμματιστές και τους ερασιτέχνες, και αυτή η ευρεία της διάδοση θεωρείται τόσο πλεονέκτημά της, όσο και μειονέκτημα, λόγω της ποικιλίας ανάμεσα στις υλοποιήσεις της.

Η Scheme αναπτύχθηκε στο MIT AI Lab του MIT από τον Guy L. Steele και τον Gerald Jay Sussman, οι οποίοι την παρουσίασαν στην ακαδημαϊκή κοινότητα μέσα από μια σειρά σημειωμάτων (memos), τα οποία σήμερα ονομάζονται "Lambda Papers", κατά την περίοδο 1975-1980. Η γλώσσα Scheme προτυποποιήθηκε σε επίσημο πρότυπο της IEEE, και σε ένα ντε φάκτο πρότυπο που ονομάζεται Αναθεωρημένηⁿ Αναφορά πάνω στην Αλγοριθμική Γλώσσα Scheme (Revisedⁿ Report on the Algorithmic Language Scheme ή RnRS). Το πρότυπο που υλοποιείται πιο συχνά είναι το R5RS (1998), και το 2007 αναγνωρίστηκε το νέο πρότυπο R6RS.

Η Scheme ήταν η πρώτη διάλεκτος της Lisp που επέλεξε τη λεκτική εμβέλεια και η πρώτη που απαίτησε από τις υλοποιήσεις της να κάνουν βελτιστοποίηση κλήσης ουράς (tail-call optimization). Ήταν επίσης μια από τις πρώτες γλώσσες προγραμματισμού που υποστήριξαν συνέχειες πρώτης κλάσης. Επηρέασε σε μεγάλο βαθμό τις προσπάθειες που οδήγησαν στην ανάπτυξη της γλώσσας Common Lisp.

Προέλευση

Η Scheme ξεκίνησε σαν μια προσπάθεια να κατανοηθεί το μοντέλο Actor του Carl Hewitt, για αυτόν το λόγο οι Steele και Sussman έγραψαν έναν "μικρό διερμηνέα Lisp" χρησιμοποιώντας τη Maclisp και στη συνέχεια "πρόσθεσαν μηχανισμούς για τη δημιουργία actors και την αποστολή μηνυμάτων." Η Scheme αρχικά ονομαζόταν "Schemer", σύμφωνα με την παράδοση των άλλων γλωσσών που προήλθαν από τη Lisp, όπως η Planner και η Conniver. Το τρέχον όνομα προήλθε από τη χρήση από τους δημιουργούς της του λειτουργικού συστήματος ITS, το οποίο περιόριζε τα ονόματα αρχείων σε δύο μέρη των έξι χαρακτήρων το καθένα. Σήμερα, η λέξη "Schemer" συνήθως χρησιμοποιείται για να αναφερθεί κανείς σε έναν προγραμματιστή της Scheme.

Σημαντικά χαρακτηριστικά

Δείτε επίσης: Lisp

Η Scheme είναι κυρίως συναρτησιακή γλώσσα προγραμματισμού και μοιράζεται πολλά χαρακτηριστικά με άλλα μέλη της οικογένειας γλωσσών προγραμματισμού της Lisp. Η απλή σύνταξη της Scheme βασίζεται σε s-εκφράσεις, οι οποίες είναι λίστες με παρενθέσεις που αποτελούνται από έναν τελεστή στην αρχή τους ακολουθούμενο από τα ορίσματά του. Κατά αυτόν τον τρόπο, τα προγράμματα σε Scheme αποτελούνται από ακολουθίες από εμφωλευμένες λίστες. Οι λίστες είναι επίσης η βασική δομή δεδομένων στη Scheme, κάτι που οδηγεί σε μια στενή σχέση ισοδυναμίας μεταξύ του κώδικα και των δεδομένων (homoiconicity). Τα προγράμματα σε Scheme μπορούν εύκολα να δημιουργήσουν και να αποτιμήσουν κομμάτια κώδικα Scheme δυναμικά.

Η χρήση της λίστας σαν βασικής δομής δεδομένων είναι ένα χαρακτηριστικό που μοιράζονται όλες οι διάλεκτοι της Lisp. Η Scheme κληρονομεί ένα πλούσιο σύνολο από πρωτογενείς συναρτήσεις επεξεργασίας λιστών όπως οι cons, car και cdr, καθώς και συναρτήσεις πρώτης τάξης από τη Lisp. Η Scheme χρησιμοποιεί αυστηρά (strictly) μεταβλητές δυναμικού τύπου και υποστηρίζει συναρτήσεις πρώτης τάξης: οι συναρτήσεις μπορούν να αποδοθούν σε μεταβλητές σαν τιμές ή να δοθούν σαν ορίσματα σε συναρτήσεις.

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

Στα παραδείγματα, ο συμβολισμός "===> αποτέλεσμα" χρησιμοποιείται για να δείξει το αποτέλεσμα της αποτίμησης μιας έκφρασης που βρίσκεται στην αμέσως προηγούμενη γραμμή. Ο ίδιος συμβολισμός χρησιμοποιείται και στο R5RS.

Βασικά σχεδιαστικά χαρακτηριστικά

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

Μινιμαλισμός

Η Scheme είναι μια πολύ απλή γλώσσα και είναι πολύ πιο εύκολο να υλοποιηθεί από άλλες γλώσσες παρόμοιας εκφραστικής ισχύος. Αυτή η ευκολία οφείλεται στη χρήση του λ-λογισμού σαν πρωτογενούς φόρμας από την οποία προκύπτει το μεγαλύτερο μέρος της σύνταξης της γλώσσας. Για παράδειγμα, από τις 23 δομές που βασίζονται σε s-εκφράσεις που περιράφονται στο πρότυπο R5RS Scheme, οι 11 κατηγοριοποιούνται σαν παραγόμενες ή μορφές βιβλιοθήκης, οι οποίες μπορούν να γραφούν σαν μακροεντολές (macros) που περιέχουν βασικότερες (κυρίως) λ-μορφές.

Βασικές μορφές: define, lambda, if, quote, unquote, unquote-splicing, quasiquote, define-syntax, let-syntax, letrec-syntax, syntax-rules, set!

Μορφές βιβλιοθήκης: do, let, let*, letrec, cond, case, and, or, begin, named let, delay

Παράδειγμα: μια μακροεντολή που υλοποιεί τη let σαν έκφραση, χρησιμοποιώντας τη lambda για να εκτελεί τις δεσμεύσεις μεταλβητών (variable bindings).

(define-syntax let
  (syntax-rules ()
    ((let ((var expr) ...) body ...)
      ((lambda (var ...) body ...) expr ...))))

Κατά αυτόν τον τρόπο, χρησιμοποιώντας της let όπως ορίστηκε παραπάνω σε μια υλοποίηση Scheme θα ξαναέγραφε τον κώδικα "(let ((a 1)(b 2)) (+ b a))" σαν "((lambda (a b) (+ b a)) 1 2)", που μειώνει τις εργασίες της υλοποίησης, χρησιμοποιώντας στιγμιότυπα της κάθε διαδικασίας.

Το 1998 ο Sussman και ο Steele τόνισαν ότι ο μινιμαλισμός της Scheme δεν ήταν σχεδιαστικός στόχος που τον επιδίωξαν συνειδητά, αλλά προέκυψε από τη διαδικασία σχεδίασης.

Λεκτική εμβέλεια

Όπως οι περισσότερες σύγχρονες γλώσσες προγραμματισμού, και σε αντίθεση με τη Emacs Lisp και με προηγούμενες διαλέκτους της Lisp όπως η Maclisp, η Scheme έχει λεκτική εμβέλεια: όλες οι δυνατές δεσμεύσεις μεταβλητών σε μια μονάδα προγράμματος μπορούν να αναλυθούν διαβάζοντας το κείμενο της μονάδας αυτής χωρίς να πρέπει να ληφθούν υπόψη οι συνθήκες υπό τις οποίες μπορεί να κληθεί.

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

Η έρευνα του Sussman πάνω στην ALGOL τον ενέπνευσε να ενσωματώσει στη νέα έκδοση του της Lisp, στις αρχές της δεκαετίας του 1970, ένα ασυνήθιστο μοντέλο εμβέλειας. Θέση του ήταν ότι οι μηχανισμοί λεκτικής εμβέλειας όπως αυτοί της ALGOL, θα βοηθούσαν στον αρχικό τους στόχο της υλοποίησης του μοντέλου Actor στη Lisp.

Οι βασικές ιδέες για το πώς ενσωματώνεται η λεκτική εμβέλεια σε μια διάλεκτο της Lisp έγιναν γνωστές από το Sussman και το Steele στο Lambda Paper του 1975 με τον τίτλο "Scheme: An Interpreter for Extended Lambda Calculus", στο οποίο υιοθέτησαν την έννοια του λεκτικού κλείσιμου, το οποίο είχε περιγραφεί σε ένα "AI Memo" το 1970 από τον Joel Moses, ο οποίος με τη σειρά του, υποστήριξε ότι η ιδέα προέρχεται από τον Peter J. Landin.

λ-λογισμός

Ο μαθηματικός συμβολισμός του Alonzo Church που ονομάζεται λ-λογισμός, επηρέασε τη Lisp όσον αφορά τη χρήση της λέξης-κλειδί "lambda" για την εισαγωγή μιας διαδικασίας (procedure), ενώ σε αυτόν οφείλεται και η ανάπτυξη πολλών τεχνικών συναρτησιακού προγραμματισμού, όπως η χρήση συναρτήσεων υψηλής τάξης στη Lisp. Οι πρώιμες διάλεκτοι της Lisp δεν ήταν κατάλληλες για να εκφράσουν το λ-λογισμό λόγω του τρόπου με τον οποίο χειρίζονταν τις ελεύθερες μεταβλητές.

Η εισαγωγή της λεκτικής εμβέλειας έλυσε το πρόβλημα, εξισώνοντας κάποιες μορφές του λ-συμβολισμού και του πώς αυτός εκφράζεται πρακτικά σε μια πραγματική γλώσσα προγραμματισμού. οι Sussman και Steele έδειξαν ότι η νέα γλώσσα μπορούσε να χρησιμοποιηθεί για να προκύψουν με κομψό τρόπο κάθε προστακτική και δηλωτική σημασιολογία των άλλως γλωσσών προγραμματισμού, όπως της ALGOL ή της Fortran, και η δυναμική εμβέλεια των άλλων διαλέκτων της Lisp, με τη χρήση λ-εκφράσεων, όχι σαν απλά στιγμιότυπα διαδικασιών αλλά σαν δομές ελέγχου και τελεστές τροποποίησης του περιβάλλοντος. Εισήγαγαν το στυλ περάσματος συνεχειών μαζί με την πρώτη περιγραφή της Scheme στο πρώτο από τα Lambda Papers, και σε επόμενες δημοσιεύσεις έδειξαν το πόσο ισχυρή είναι αυτή χρήση στην πράξη του λ-λογισμού.

Δομή ενοτήτων

Η Scheme κληρονομεί τη δομή ενοτήτων της (block structure) από προγενέστερες γλώσσες δομημένες με ενότητες και κυρίως από την ALGOL. Στη Scheme οι ενότητες υλοποιούνται από τρεις δομές δέσμευσης (binding constructs): let, let* και letrec. Για παράδειγμα, η ακόλουθη δομή δημιουργεί μια ενότητα στην οποία ένα σύμβολο με το όνομα var δεσμεύεται στον αριθμό 10:

(define var "goose")
;; Κάθε αναφορά στη var εδώ δεσμεύεται στο "goose"
(let ((var 10))
  ;; οι εντολές βρίσκονται εδώ. Κάθε αναφορά στη var δεσμεύεται στην τιμή 10.
  )
;; Κάθε αναφορά στη var εδώ δεσμεύεται στο "goose"

Οι ενότητες μπορούν να είναι εμφωλευμένες (nested) με σκοπό τη δημιουργία πολύπλοκων δομών ενοτήτων σύμφωνα με τις ανάγκες του προγραμματιστή. Η δόμηση με ενότητες για τη δημιουργία τοπικών δεσμεύσεων περιορίζει τον κίνδυνο σύγκρουσης χώρων ονομάτων (namespace collision) που μπορεί να εμφανιστεί σε άλλες περιπτώσεις.

Μια παραλλαγή της let, η let*, επιτρέπει σε δεσμεύσεις να αναφέρονται σε μεταβλητές που ορίστηκαν νωρίτερα, όπως στον εξής κώδικα:

(let* ((var1 10)
      (var2 (+ var1 12)))
  ;; Αλλά ο ορισμός της var1 δε θα μπορούσε να αναφέρεται στη var2
  )

Η άλλη παραλλαγή, η letrec, είναι σχεδιασμένη ώστε να επιτρέπει σε αμοιβαία αναδρομικές διαδικασίες να δεσμεύονται η μια στην άλλη.

;; Στηλοθέτηση των ακολουθιών αντρών-γυναικών του Hofstadter
(letrec ((female (lambda(n)
                   (if (= n 0) 1
                       (- n (male (female (- n 1)))))))
         (male (lambda(n)
                 (if (= n 0) 0
                     (- n (female (male (- n 1))))))))
  (display "i male(i) female(i)")(newline)
  (do ((i 0 (+ i 1)))
      ((> i 8) #f)
    (display i) (display "   ")(display (male i))(display "         ")(display (female i))
    (newline)))

Όλες οι διαδικασίες που δεσμεύονται μέσα σε μια letrec μπορούν να αναφέρονται η μια στην άλλη με το όνομά τους, καθώς και σε τιμές μεταβλητών που ορίστηκαν νωρίτερα στην ίδια letrec, αλλά δε μπορούν να αναφέρονται σε τιμές που ορίζονται αργότερα στην ίδια letrec.

Μια παραλλαγή της let, η μορφή "ονομαστικό let", έχει ένα αναγνωριστικό μετά τη λέξη-κλειδί let. Αυτό δεσμεύει τις μεταβλητές του let στο όρισμα μιας διαδικασίας της οποίας το όνομα είναι το δοθέν αναγνωριστικό και το σώμα της είναι το σώμα της μορφής let. Το σώμα μπορεί να επαναληφθεί όσο είναι επιθυμητό με την κλήση της διαδικασίας. Το ονομαστικό let χρησιμοποιείται συχνά για την υλοποίηση της επανάληψης (iteration).

Παράδειγμα: ένας απλός μετρητής

(let loop ((n 1))
  (if (<= n 10)
    (begin
      (display n)(newline)
      (loop (+ n 1)))))

Όπως κάθε διαδικασία στη Scheme, η διαδικασία που δημιουργείται από το ονομαστικό let είναι αντικείμενο πρώτης τάξης.

Αναδρομή ουράς

Η Scheme έχει μια δομή επανάληψης, τη do, αλλά στη Scheme συνηθίζεται να χρησιμοποιείται η αναδρομή ουράς για την έκφραση της επανάληψης. Οι υλοποιήσεις της Scheme που συμφωνούν με το πρότυπο απαιτείται να βελτιστοποιούν τις κλήσεις ουράς (tail calls), ώστε να μπορούν να υποστηρίξουν άπειρες ενεργές κλήσεις ουράς (R5RS sec. 3.5)—μια ιδιότητα που το πρότυπο περιγράφει σαν σωστή αναδρομή ουράς (proper tail recursion)— με αποτέλεσμα ο προγραμματιστής να μπορεί να γράφει επαναληπτικούς αλγορίθμους με τη χρήση αναδρομής, κάτι που είναι ευκολότερο. Οι διαδικασίες που έχουν αναδρομή ουράς και η μορφή ονομαστικό let υποστηρίζουν την επανάληψη μέσω αναδρομής ουράς.

;; Στηλοθέτηση των τετραγώνων από το 0 έως το 9:
;; Το loop είναι απλά ένα σύμβολο που χρησιμοποιήθηκε σαν ετικέτα.
;; Οποιοδήποτε άλλο σύμβολο είναι επίσης κατάλληλο.
(let loop ((i 0))
  (if (not (= i 10))
     (begin
        (display i)(display " squared = ")(display (* i i))(newline)
        (loop (+ i 1)))))

Συνέχειες πρώτης τάξης

Οι συνέχειες στη Scheme είναι αντικείμενα πρώτης τάξης. Η Scheme παρέχει τη διαδικασία call-with-current-continuation (γνωστή και σαν call/cc) για να δεσμεύσει την τρέχουσα συνέχεια, πακετάροντάς τη σαν διαδικασία διαφυγής (escape procedure) που δεσμεύεται σε μια παράμετρο μιας διαδικασίας που όρισε ο προγραμματιστής. (R5RS sec. 6.4) Οι συνέχειες πρώτης τάξης επιτρέπουν στον προγραμματιστή να δημιουργεί μη-τοπικές δομές ελέγχου όπως οι επαναλήπτες (iterators), οι συρρουτίνες (coroutines), και η οπισθοδρόμηση (backtracking).

Στο επόμενο παράδειγμα, που είναι ένα κλασικό προγραμματιστικό πρόβλημα, φαίνεται πώς χειρίζεται η Scheme τις συνέχειες σαν αντικείμενα πρώτης τάξης, δεσμεύοντάς τις σε μεταβλητές και περνώντας τις σαν παραμέτρους σε διαδικασίες.

(let* ((yin
         ((lambda (cc) (display "@") cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display "*") cc) (call-with-current-continuation (lambda (c) c)))) )
    (yin yang))

Όταν εκτελεστεί, ο κώδικας εμφανίζει την εξής ακολουθία από μετρητές: "@*@**@***@****@*****@******@*******@********..."

Η έννοια της συνέχειας πρώτης τάξης επεκτάθηκε στο πρότυπο R5RS. Ένας περιορισμός της call/cc είναι ότι παράγει συνέχειες που μπορούν να χειριστούν μόνο μια παράμετρο. Το R5RS αναίρεσε αυτόν τον περιορισμό, ορίζοντας δύο νέες διαδικασίες: η values ορίζεται σαν τη διαδικασία που δίνει όλες της τις παραμέτρους στη συνέχειά της, και η call-with-values παράγει μια συνέχεια που απλά περνάει τα ορίσματά της σε μια διαδικασία. (R5RS sec. 6.4)

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

;; Μια διαδικασία που επιστρέφει το όνομα χρήστη και τον κωδικό
(define (credentials) (values "myuser" "mypassword"))

;; Μια διαδικασία που εκτελεί ταυτοποίηση ενός ονόματος χρήστη και ενός κωδικού
(define (login username password)
  ;; κώδικας ταυτοποίησης και εισόδου του χρήστη στο σύστημα
   )

;; Στέλνει τα δεδομένα στη διαδικασία ταυτοποίησης.
(call-with-values credentials login)

Με τη χρήση της σύνταξης receive που εμφανίστηκε στο SRFI 8, η παραπάνω call-with-values μπορεί να γραφεί ως εξής:

(receive (username password) (credentials) (login username password))

Η μορφή receive είναι ένα παράδειγμα δομής ενότητας όπως η μορφή let, και μπορεί να οδηγήσει σε καθαρότερο κώδικα.

Κοινός χώρος ονομάτων για διαδικασίες και μεταβλητές

Σε αντίθεση με την Common Lisp, όλα τα δεδομένα και οι διαδικασίες στη Scheme μοιράζονται έναν κοινό χώρο ονομάτων, ενώ στην Common Lisp οι συναρτήσεις και τα δεδομένα έχουν ξεχωριστούς χώρους ονομάτων, με αποτέλεσμα να είναι δυνατό μια συνάρτηση και μια μεταβλητή να έχουν το ίδιο όνομα, ενώ χρειάζεται ειδικός συμβολισμός για την αναφορά σε μια συνάρτηση σαν τιμή. Αυτό είναι γνωστό και σαν ο διαχωρισμός "Lisp-1/Lisp-2", που αναφέρεται στον ενιαίο χώρο ονομάτων της Scheme και στους ξεχωριστούς χώρους ονομάτων της Common Lisp.

Στη Scheme, οι ίδιες βασικές εντολές που χρησιμοποιούνται για το χειρισμό και τη δέσμευση δεδομένων μπορούν να χρησιμοποιηθούν για τη δέσμευση διαδικασιών. Δεν υπάρχει αντίστοιχη των εντολών defun, setf και #' της Common Lisp.

;; Μεταβλητή που δεσμεύεται σε αριθμό:
(define f 10)
f
===> 10
;; Τροποποίηση (mutation, αλλαγή της δεσμευμένης τιμής)
(set! f (+ f f 6))
===> 26
;; Ανάθεση μιας διαδικασίας στην ίδια μεταβλητή:
(set! f (lambda (n) (+ n 12)))
(f 6)
===> 18
;; Ανάθεση του αποτελέσματος μιας έκφρασης στην ίδια μεταβλητή:
(set! f (f 1))
f
===> 13
;; συναρτησιακός προγραμματισμός:
(apply + '(1 2 3 4 5 6))
===> 21
(set! f (lambda(n) (+ n 100)))
(map f '(1 2 3))
===> (101 102 103)

Εξωτερικοί σύνδεσμοι

• Η τελευταία έκδοση του προτύπου της Scheme: R6RS (Αγγλικά)
• Schemers.org (Αγγλικά)

Παραπομπές