View on GitHub

dituoi_agp

Αρχές Γλωσσών Προγραμματισμού

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

ΑΡΧΕΣ ΓΛΩΣΣΩΝ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ (R.W.Sebesta) - Κεφάλαιο 15

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) είναι μια συνάρτηση που παίρνει μια ή περισσότερες συναρτήσεις ως παραμέτρους, ή επιστρέφει μια συνάρτηση ως αποτέλεσμα ή και τα δύο.

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

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

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

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

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

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

John McCarthy 1959

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

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

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

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

(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 βασικές συναρτήσεις κατηγορημάτων για συμβολικά άτομα και λίστες.

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 διαθέτει διάφορους τελεστές λιστών όπως οι ακόλουθοι:

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 Σύγκριση συναρτησιακών και προστακτικών γλωσσών