Συναρτησιακός προγραμματισμός στη Lisp

Διομήδης Σπινέλλης
Τμήμα Διοικητικής Επιστήμης και Τεχνολογίας
Οικονομικό Πανεπιστήμιο Αθηνών
dds@aueb.gr

Συναρτησιακός προγραμματισμός και η γλώσσα Lisp

Ο συναρτησιακός προγραμματισμός (functional programming) βασίζεται στην αποτίμηση συναρτήσεων αντί για την εκτέλεση εντολών. Προγράμματα βασισμένα στο συναρτησιακό προγραμματισμό είναι γραμμένα με βάση συναρτήσεις που αποτιμούν βασικές τιμές. Μια συναρτησιακή γλώσσα προγραμματισμού υποστηρίζει και ενθαρρύνει το συναρτησιακό προγραμματισμό.

Βασικά χαρακτηριστικά του συναρτησιακού προγραμματισμού είναι:

οι συναρτήσεις ως παράμετροι,
o ράθυμος υπολογισμός (lazy evaluation),
η αναφορική διαφάνεια (referential transparency).

Ορισμένες γνωστές συναρτησιακές γλώσσες προγραμματισμού είναι οι:

Erlang
Haskell
Hope
Lisp
Miranda
ML
Scheme

Οι βασικές ιδέες της γλώσσας Lisp αναπτύχθηκαν από τον John McCarthy το 1956 σε ένα ερευνητικό πρόγραμμα για τεχνητή νοημοσύνη. Στόχος του McCarthy ήταν η ανάπτυξη μιας αλγευρικής γλώσσας επεξεργασίας λιστών για έρευνα στην τεχνητή νοημοσύνη. Ανάμεσα στα έτη 1960 και 1965 υλοποιήθηκε η διάλεκτος Lisp 1.5 η οποία τη δεκαετία του 1970 είχε οδηγήσει στις διαλέκτους MacLisp και InterLisp. Στα μέσα της δεκαετίας του 1970 οι Sussman και Steele Jr. ανέπτυξαν τη διάλεκτο Scheme με βάση ιδέες από τη σημασιολογία των γλωσσών προγραμματισμού. Στη δεκαετία του 1980 έγινε προσπάθεια για ενοποίηση των διαλέκτων της Lisp κάτω από το πρότυπο της Common Lisp.

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

Συναρτήσεις στη Lisp ορίζονται με τη σύνταξη:
```
(defun όνομα_συνάρτησης (παράμετροι) τιμή)
```
Υπολογισμός της τιμής μιας συνάρτησης στη Lisp γίνεται με τη σύνταξη:
```
(όνομα_συνάρτησης παράμετροι)
```
Ορισμένες χρήσιμες συναρτήσεις είναι οι:

(if e tv fv)
επιστρέφει tv αν η e είναι αληθής (t) και fv αν είναι ψευδής (nil).
(+ a b)
επιστρέφει a + b.
(- a b)
επιστρέφει a - b.
(* a b)
επιστρέφει a * b.
(/ a b)
επιστρέφει a / b.
(equal a b)
επιστρέφει αληθές (t) αν a = b.

Παράδειγμα (ορισμός της συνάρτησης του παραγοντικού):

(defun factorial (n)
	(if (equal n 0)
	1
	(* n (factorial (- n 1)))))

Λίστες

Στη Lisp μπορούμε να ορίσουμε μια λίστα (list) από τιμές με τη σύνταξη '(τιμή1 τιμή2 τιμή3 ...)
Η ειδική τιμή nil παριστάνει την κενή λίστα.
Μπορούμε να αναφερθούμε σε σύμβολα με τη σύνταξη 'όνομα.

Παράδειγμα:

'(1 2 3 4 42)
'word
'('Maria 'John 'Aliki)

Βασικές συναρτήσεις επεξεργασίας λιστών είναι οι παρακάτω:

(cons val list)
(car list)
(cdr list)

Με βάση τις συναρτήσεις αυτές μπορούμε να ορίσουμε πιο σύνθετες συναρτήσεις.

Length

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

(defun mylength (a) 
	(if (null a) 
		0 
		(+ (mylength (cdr a)) 1)))

Append

Ενώνει δύο λίστες.

(defun myappend (a b)
	(if (null a)
		b
		(cons (car a) (myappend (cdr a) b))))

Reverse

Αντιστρέφει μια λίστα.

(defun myreverse (a)
	(if (null a)
		nil
		(myappend (myreverse (cdr a)) (cons (car a) nil))))

Συναρτήσεις ανωτέρου βαθμού

Μπορούμε να ορίσουμε μια συνάρτηση ανωτέρου βαθμού (higher order function) ορίζοντας ως ένα όρισμα της συνάρτησης μια άλλη συνάρτηση.
Τη συνάρτηση-όρισμα μπορούμε να την εφαρμόσουμε πάνω σε κάποιες τιμές με τη συνάρτηση apply η οποία λαμβάνει ως όρισμα μια συνάρτηση και μια λίστα με το όρισμά της και επιστρέφει το αποτέλεσμα της συνάρτησης εφαρμοσμένο στο όρισμα αυτό.
Μπορούμε ακόμα να ορίσουμε δυναμικά μια τιμή τύπου συνάρτησης με τη σύνταξη:
```
(lambda όνομα_συνάρτησης (όρισμα) τιμή)
```

Το παρακάτω παράδειγμα συνθέτουμε τις έννοιες αυτές για να ορίσουμε τις συναρτήσεις map και reduce.

Map

Η συνάρτηση map μετατρέπει μια λίστα σε μια άλλη με βάση μια συνάρτηση που έχει δοθεί ως όρισμα.

(defun mymap (f lst)
	(if (null lst) 
		nil 
		(cons (apply f (cons (car lst) nil)) (mymap f (cdr lst)))))

Έτσι μπορούμε π.χ. να διπλασιάσουμε να στοιχεία της λίστας '(1 2 3) με την κλήση:

(mymap (lambda (x) (* 2 x)) '(1 2 3))      
(2 4 6)

Reduce

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

(defun myreduce (f v lst)
	(if (null lst) 
		v 
		(apply f (cons (car lst) (cons (myreduce f v (cdr lst)) nil)))))

Έτσι μπορούμε να ορίσουμε συναρτήσεις όπως τις:

sum επιστρέφει το σύνολο των τιμών μιας λίστας
```
(defun mysum (lst) (myreduce '+ 0 lst))
```
product επιστρέφει το γινόμενο των τιμών μιας λίστας
```
(defun myproduct (lst) (myreduce '* 1 lst))
```
alltrue επιστρέφει αληθές αν όλες οι τιμές μιας λίστας είναι αληθείς
```
(defun alltrue (lst) (myreduce 'and t lst))
```
anytrue επιστρέφει αληθές αν τουλάχιστον μια τιμή μιας λίστας είναι αληθής
```
(defun anytrue (lst) (myreduce 'or nil lst))
```

Μεταγλωττιστής Lisp

Διερμηνευτή συμβατό με τα παραδείγματα των σημειώσεων μπορείτε να βρείτε εδώ.
Τεκμηρίωση για το διερμηνευτή μπορείτε να βρείτε εδώ.
Η πιο εύκολη διαδικασία για τη χρήση του μεταγλωττιστή είναι:
- File - Open / Load το αρχείο με τις ορισμένες συναρτήσεις
- Δοκιμή της συνάρτησης μέσα στο παράθυρο.
Ο πηγαίος κώδικας του διερμηνευτή και υλοποιήσεις για άλλες πλατφόρμες υπάρχουν στη διεύθυνση ftp://ftp.cs.cmu.edu/user/ai/lang/lisp/impl/xlisp.

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

Ellis Horowitz Βασικές αρχές γλωσσών προγραμματισμού. Δεύτερη αμερικάνικη έκδοση. σ. 367-398 Εκδόσεις Κλειδάριθμος, 1984.

Harold Abelson, Gerald Jay Sussman, and Jullie Sussman. Structure and Interpretation of Computer Programs. MIT Press, 1990.
Anthony J. Field and Peter G. Harrison. Functional Programming. Addison-Wesley, 1988.
John Hughes. Why functional programming matters. In David A. Turner, editor, Research Topics in Functional Programming, chapter 2, pages 17–42. Addison-Wesley, 1990. Also appeared in the April 1989 issue of The Computer Journal.
Peter H. Salus, editor. Handbook of Programming Languages, volume III: Functional and Logic Programming Languages. Macmillan Technical Publishing, 1998.

Ασκήσεις

Άσκηση 11

Οι δύο πρώτοι αριθμοί της ακολουθίας Fibonacci είναι 0 και 1. Κάθε επόμενος αριθμός είναι το άθροισμα των δύο προηγούμενων. Γράψτε τη συνάρτηση που επιστρέφει τον νοστό αριθμό Fibonacci. (Οι αριθμοί Fibonacci απαντώνται συχνά στη φύση π.χ. στον αριθμό πετάλων των λουλουδιών και στις σπείρες από τα κουκουνάρια και τις αχιβάδες).
Γράψτε τη συνάρτηση (member list val) που επιστρέφει αληθές αν η τιμή val περιέχεται στη λίστα list.

Περιεχόμενα