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

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

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

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

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

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

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

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

Παράδειγμα (ορισμός της συνάρτησης του παραγοντικού):
(defun factorial (n)
        (if (equal n 0)
        1
        (* n (factorial (- n 1)))))

Λίστες

Παράδειγμα: 
'(1 2 3 4 42)
'word
'('Maria 'John 'Aliki)
Βασικές συναρτήσεις επεξεργασίας λιστών είναι οι παρακάτω:
(null list)
επιστρέφει αληθές αν η λίστα είναι κενή
(cons val list)
επιστρέφει τη λίστα list με πρώτο το στοιχείο val,
(car list)
επιστρέφει το πρώτο στοιχείο μιας λίστας,
(cdr list)
επιστρέφει τα υπόλοιπα (όλα εκτός από το πρώτο) στοιχεία μιας λίστας ή nil αν αυτά δεν υπάρχουν.
Με βάση τις συναρτήσεις αυτές μπορούμε να ορίσουμε πιο σύνθετες συναρτήσεις.

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))))

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

Το παρακάτω παράδειγμα συνθέτουμε τις έννοιες αυτές για να ορίσουμε τις συναρτήσεις 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)))))
Έτσι μπορούμε να ορίσουμε συναρτήσεις όπως τις:

Διερμηνευτής Lisp

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

Ασκήσεις

Άσκηση 9

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

Creative Commons License  Τελευταία αλλαγή: Πέμπτη, 5 Ιανουαρίου 2006 0:44 πμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».