Skip to content

15. Γλώσσες συναρτησιακού προγραμματισμού

  • Οι γλώσσες συναρτησιακού προγραμματισμού στηρίζονται σε βασικές ιδέες των μαθηματικών συναρτήσεων.
  • Γλώσσες συναρτησιακού προγραμματισμού: Lisp, Scheme, Racket, ML, OCaml, Haskell, F#.
  • Υποστήριξη για συναρτησιακό προγραμματισμό από προστακτικές γλώσσες.
  • Εφαρμογές γλωσσών συναρτησιακού προγραμματισμού.

15.1 Εισαγωγή

Το προστακτικό στυλ προγραμματισμού παρουσιάζει μεγάλη εξάρτηση από την επικρατούσα αρχιτεκτονική των Η/Υ.

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

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

15.2 Μαθηματικές συναρτήσεις

Μια μαθηματική συνάρτηση είναι μια αντιστοίχιση των μελών ενός συνόλου (του πεδίου ορισμού) σε ένα άλλο σύνολο (το πεδίο τιμών).

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

Οι μαθηματικές συναρτήσεις δεν έχουν παράπλευρες συνέπειες (side-effects).

15.2.1 Απλές συναρτήσεις

Ο συμβολισμός εκφράσεων λάμδα διατυπώθηκε από τον A. Church το 1941 και αποτελεί έναν τρόπο ορισμού συναρτήσεων χωρίς ονόματα. Μια έκφραση λάμδα καθορίζει τις παραμέτρους και την αντιστοίχιση μιας συνάρτησης. Ο Church όρισε τον λογισμό λάμδα που αποτελεί ένα επίσημο μοντέλο υπολογισμών που χρησιμοποιεί εκφράσεις λάμδα. Η συναρτησιακές γλώσσες προγραμματισμού βασίζονται στον λογισμό λάμδα.

λ(x) x*x*x

Πριν την αποτίμησή της μια παράμετρος αναπαριστά οποιοδήποτε μέλος του πεδίου ορισμού, αλλά κατά τη διάρκεια της αποτίμησης δεσμεύεται σε ένα συγκεκριμένο μέλος του πεδίου ορισμού.

(λ(x) x*x*x)(2)

15.2.2 Συναρτησιακές μορφές

Μια συναρτησιακή μορφή ή συνάρτηση υψηλής τάξης (high-order function) είναι μια συνάρτηση που παίρνει μια ή περισσότερες συναρτήσεις ως παραμέτρους, ή επιστρέφει μια συνάρτηση ως αποτέλεσμα ή και τα δύο.

Παραδείγματα συναρτησιακών μορφών

  • Σύνθεση συναρτήσεων (composition)
  • Εφαρμογή σε όλα (apply-to-all)

15.3 Βασικά στοιχεία των γλωσσών συναρτησιακού προγραμματισμού

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

Η εκτέλεση μιας συνάρτησης με τις ίδιες παραμέτρους παράγει το ίδιο αποτέλεσμα (αναφορική διαφάνεια = referential transparency). Συνεπώς ο έλεγχος της ορθότητας συναρτήσεων μπορεί να γίνεται χωριστά για κάθε συνάρτηση.

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

15.4 Η πρώτη συναρτησιακή γλώσσα προγραμματισμού: Lisp

John McCarthy 1959

Οι σύγχρονες διάλεκτοι της Lisp περιλαμβάνουν χαρακτηριστικά προστακτικών γλωσσών, όπως μεταβλητές προστακτικού τύπου, προτάσεις εκχώρησης και επανάληψη.

15.4.1 Τύποι και δομές δεδομένων

Δύο βασικές κατηγορίες αντικειμένων δεδομένων στη Lisp είναι τα άτομα και οι λίστες.

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

Παραδείγματα λιστών

(A B C D)

(A (B C) D (E (F G)))

15.4.2 Ο πρώτος διερμηνευτής της Lisp

Η κλήση συνάρτησης γίνεται ως εξής:

(όνομα_συνάρτησης παράμετρος1 παράμετρος2 ... παράμετροςn)

S-εκφράσεις

EVAL: καθολική συνάρτηση αποτίμησης όλων των συναρτήσεων. Τα προγράμματα ερμηνεύονται από την καθολική συνάρτηση EVAL.

15.5 Scheme

Lisp -> Scheme -> Racket

15.5.1 Η προέλευση της Scheme

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

15.5.2 Ο διερμηνευτής της Scheme

H Scheme διαθέτει REPL (Read Evaluate Print Loop).

15.5.3 Βασικές αριθμητικές συναρτήσεις

15.5.4 Ορισμός συναρτήσεων

Ένα πρόγραμμα Scheme είναι μια συλλογή από ορισμούς συναρτήσεων.

Μια ανώνυμη συνάρτηση περιλαμβάνει τη λέξη lambda και ονομάζεται έκφραση lambda.

15.5.5 Συναρτήσεις εξόδου

15.5.6 Αριθμητικές συναρτήσεις κατηγορημάτων

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

15.5.7 Ροή ελέγχου

(if predicate then_expression else_expression)

(cond cond-clause ...)
cond-clause     =       [test-expr then-body ...+]
        |       [else then-body ...+]
        |       [test-expr => proc-expr]
        |       [test-expr]

15.5.8 Συναρτήσεις λιστών

Τα δεδομένα και ο κώδικας έχουν την ίδια μορφή.

Συνάρτηση QUOTE

Επιστρέφει την παράμετρο χωρίς μεταβολή.

Συνάρτηση CAR

Επιστρέφει την κεφαλή της λίστας.

Συνάρτηση CDR

Επιστρέφει την ουρά της λίστας.

Συνάρτηση CONS

Κατασκευάζει μια νέα λίστα από δύο ξεχωριστά τμήματα λίστας.

Συνάρτηση LIST

Κατασκευάζει μια λίστα από μεταβλητό αριθμό παραμέτρων.

15.5.9 Συναρτήσεις κατηγορημάτων για συμβολικά άτομα και λίστες

Διατίθενται 3 βασικές συναρτήσεις κατηγορημάτων για συμβολικά άτομα και λίστες.

  • EQ? πραγματοποιεί σύγκριση δεικτών
  • EQV? πραγματοποιεί σύγκριση τιμών
  • NULL? επιστρέφει #Τ αν το όρισμά της είναι κενό
  • LIST? επιστρέφει #Τ αν το όρισμά της είναι λίστα

To EQ? λειτουργεί σωστά για συμβολικά άτομα αλλά όχι απαραίτητα για αριθμητικά άτομα. Για τα αριθμητικά άτομα μπορεί να χρησιμοποιηθεί το κατηγόρημα =.

15.5.10 Παράδειγμα συναρτήσεων Scheme

Παραδείγματα επεξεργασίας λιστών

Παράδειγμα 1

Επίλυση προβλήματος ιδιότητας μέλους ενός δεδομένου ατόμου σε μια δεδομένη λίστα που δεν περιλαμβάνει υπολίστες (απλή λίστα).

(define (my_member atm a_list)
    (cond
        ((null? a_list) #f)
        ((eq? atm (car a_list)) #t)
        (else (my_member atm (cdr a_list)))
))

> (my_member 'a '(a b c))
#true

Παράδειγμα 2

Διαπίστωση του εάν δύο δεδομένες απλές λίστες είναι ίσες.

(define (equalsimp list1 list2)
    (cond
        ((null? list1) (null? list2))
        ((null? list2) #f)
        ((eq? (car list1) (car list2))
            (equalsimp (cdr list1) (cdr list2)))
        (else #f)
    )
)

> (equalsimp '(a b) '(a b))
#true

Παράδειγμα 3

Κατασκευή μιας νέας λίστας που περιέχει όλα τα στοιχεία δύο δεδομένων ορισμάτων λιστών.

(define (my_append list1 list2)
    (cond 
        ((null? list1) list2)
        (else (cons (car list1) (my_append (cdr list1) list2)))
    )
)

> (my_append '(a b) '(c d e))
(list 'a 'b 'c 'd 'e)

15.5.11 LET

Η LET είναι μια συνάρτηση που δημιουργεί μια τοπική εμβέλεια στην οποία τα ονόματα φράσσονται προσωρινά σε τιμές εκφράσεων.

 #lang racket

(define (quadratic_roots a b c)
    (let (
        (root_part_over_2a (/ (sqrt (- (* b b) (* 4 a c))) (* 2 a)))
        (minus_b_over_2a (/ (- 0 b) (* 2 a)))
    )
    (list (+ minus_b_over_2a root_part_over_2a)
            (- minus_b_over_2a root_part_over_2a))
))

> (quadratic_roots 2 5 3)
'(-1 -1.5)

15.5.12 Αναδρομή ουράς στη Scheme

Μια συνάρτηση εκτελεί αναδρομή ουράς (tail recursion) αν η αναδρομική κλήση της είναι η τελευταία πράξη στη συνάρτηση. Αυτές οι συναρτήσεις μπορούν να μετατραπούν αυτόματα από έναν μεταγλωττιστή έτσι ώστε να μην χρησιμοποιείται αναδρομή, αλλά επανάληψη με αποτέλεσμα την ταχύτερη εκτέλεση τους.

15.5.13 Συναρτησιακές μορφές

15.5.13.1 Συναρτησιακή σύνθεση

Η συναρτησιακή σύνθεση δέχεται δύο συναρτήσεις ως παραμέτρους και επιστρέφει μια συνάρτηση που εφαρμόζει πρώτα τη συνάρτηση της δεύτερης παραμέτρου στην παράμετρο της και κατόπιν τη συνάρτηση της πρώτης παραμέτρου στην τιμή επιστροφής της συνάρτησης της δεύτερης παραμέτρου. Δηλαδή, η συνάρτηση σύνθεσης των f και g είναι η h(x) = f(g(x))

(define (compose f g) (lambda (x) (f (g x))))

> ((compose car cdr) '((a b) c d))                                                                                      'c 
'c

15.5.13.2 Η συναρτησιακή μορφή apply-to-all

H map είναι παραλλαγή της apply-to-all που δέχεται δύο παραμέτρους, μια συνάρτηση και μια λίστα.

> (map (lambda (num) (* num num num)) '(3 4 2 6))                                                                       
'(27 64 8 216)

15.5.14 Συναρτήσεις που κατασκευάζουν κώδικα

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

15.6 Common Lisp

H Common Lisp (1990) δημιουργήθηκε προκειμένου να συνδυαστούν τα χαρακτηριστικά πολλών διαλέκτων της Lisp (συμπεριλαμβανομένης της Scheme). Είναι αρκετά μεγάλη και πολύπλοκη ως γλώσσα. Υποστηρίζει στατική και δυναμική εμβέλεια. Ο στόχος της Common Lisp ήταν να χρησιμοποιηθεί ως γλώσσα προγραμματισμού εφαρμογών του εμπορίου.

15.7 ML

15.8 Haskell

Η Haskell είναι μια αμιγής συναρτησιακή γλώσσα. Οι εκφράσεις στην Haskell δεν έχουν παράπλευρες συνέπειες.

Συνάρτηση παραγοντικού (με αντιστοίχιση μοτίβων - pattern matching) 1η έκδοση

fact 0 = 1
fact 1 = 1
fact n = n * fact (n - 1)

Συνάρτηση για υπολογισμό του νιοστού όρου fibonacci (0, 1, 1, 2, 3, 5, 8, 11, 19, ...)

fib 0 = 1
fib 1 = 1
fin (n + 2) = fib (n + 1) + fib n

Υπάρχει η δυνατότητα να προστεθούν φρουροί (guards) σε γραμμές του ορισμού μιας συνάρτησης, ώστε να προσδιορίζεται πότε μπορεί να εφαρμοστεί ο ορισμός.

Συνάρτηση παραγοντικού - 2η έκδοση

fact n
    | n == 0 = 1
    | n == 1 = 1
    | n > 1 = n * fact (n - 1)

Λίστες

colors = ["blue", "green", "red", "yellow"]

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

5:[2, 7, 9] δίνει [5, 2, 7, 9]
[1, 3..11] δίνει  [1, 3, 5, 7, 9, 11]
[1, 3, 5] ++ [2, 4, 6]  δίνει  [1, 3, 5, 2, 4, 6]
Συνάρτηση υπολογισμού του γινομένου των στοιχείων μιας λίστας

product [] = 1
product (a:x) = a * product x

Συνάρτησης παραγοντικού (με χρήση της product) - 3η έκδοση

fact n = product [1..n]

Η δομή let

quadratic_root a b c =
    let minus_b_over_2a = -b / (2.0 * a)
        root_part_over_2a = sqrt(b ^ 2 - 4.0 * a * c) / (2.0 * a)
    in 
        minus_b_over_2a - root_part_over_2a,
        minus_b_over_2a + root_part_over_2a

Περιφραστικές λίστες (list comprehensions)

Λίστα όλων των n*n*n ώστε το n να βρίσκεται στο διάστημα 1 έως και 50.

[n * n * n | n <- [1..50]]

Υπολογισμός των παραγόντων ενός αριθμού n.

factors n =  [i | i <- [1..n `div` 2], n `mod` i == 0]

Υλοποίηση της quicksort στην Haskell

sort [] = []
sort (h:t) = sort [b | b <- t, b <= h ]
             ++ [h] ++
             sort [b | b <- t, b > h ]

Οκνηρή αποτίμηση (lazy evaluation)

Οι εκφράσεις αποτιμώνται μόνο όταν οι τιμές τους είναι απαραίτητες.

Ατέρμονες δομές δεδομένων

positives = [0..]
evens = [2, 4..]
squares = [n * n | n <- [0..]]

15.9 F#

15.10 Υποστήριξη συναρτησιακού προγραμματισμού σε κυρίως προστακτικές γλώσσες

Στοιχεία συναρτησιακού προγραμματισμού έχουν προστεθεί σε γλώσσες κυρίως προστακτικού προγραμματισμού. Ένα παράδειγμα είναι οι ανώνυμες συναρτήσεις που μοιάζουν με εκφράσεις λάμδα και συναντώνται στις C++, Java, Python, C#, JavaScript, Ruby.

JavaScript

Java

Python

lambda a,b: 2 * a - b

H Python έχει τις συναρτήσεις υψηλής τάξης filter και map που χρησιμοποιούν ως πρώτη παράμετρο εκφράσεις λάμδα, ως δεύτερη παράμετρο έναν τύπο ακολουθίας (λίστα, πλειάδα ή συμβολοσειρά) και επιστρέφουν τον ίδιο τύπο ακολουθίας.

map(lambda x: x**3, [2,4,6,8])

θα επιστρέψει

[8, 64, 216, 512]

Επιπλέον, η Python υποστηρίζει εφαρμογές μερικών συναρτήσεων (partial functions).

from operator import add
add5 = partial(add,5)
print(add5(15))

θα εμφανίσει την τιμή 20.

C++

15.11 Σύγκριση συναρτησιακών και προστακτικών γλωσσών

  • Οι συναρτησιακές γλώσσες μπορούν να έχουν πιο απλή συντακτική δομή και απλούστερη σημασιολογία.
  • Τα συναρτησιακά προγράμματα δεν έχουν παράπλευρες συνέπειες (side effects).
  • Τα συναρτησιακά προγράμματα έχουν μικρότερο μέγεθος σε σχέση με τα αντίστοιχα προστακτικά προγράμματα.
  • Τα προτασιακά προγράμματα είναι ταχύτερα από τα αντίστοιχα συναρτησιακά προγράμματα.
  • Οι συναρτησιακές γλώσσες διευκολύνουν την ανάγνωση του κώδικα.
  • Η ταυτόχρονη εκτέλεση στις προστακτικές γλώσσες παρουσιάζει διάφορες δυσκολίες. Λόγω της απουσίας παράπλευρων συνεπειών στον αμιγή συναρτησιακό προγραμματισμό καθίσταται ευκολότερη η ταυτόχρονη εκτέλεση συναρτήσεων.
  • Η πλειοψηφία των προγραμματιστών μαθαίνουν προγραμματισμό σε προστακτικές γλώσσες και κατά συνέπεια τα συναρτησιακά προγράμματα φαίνονται περίεργα και δυσνόητα.