Σενάρια και scheme

Θυμάστε τα σενάρια; Ένας τρόπος να αναπαρασταθεί διαδικαστική γνώση που χρειάζεται να γνωρίζει κάποιος πράκτορας (agent) προκειμένου να δράσει σε ένα καθορισμένο περιβάλλον (πχ σενάριο του εστιατορίου). Έγραψα σε scheme ένα πρόγραμμα που υλοποιεί το σενάριου του κουρείου.

Το πρόγραμμα συντάχθηκε σε DrScheme, version 4.1.

Το πρόγραμμα έχει τρία επίπεδα εννοιολογικής αφαίρεσης. Αρχικά ορίζεται ένα γενικό μοντέλο που περιγράφει την κίνηση (μεταφορά, θέση σώματος) agents μέσα σε ένα χώρο. Ο agent αναπαριστά μια οντότητα που μπορεί να δρα με άλλες οντότητες. Ο χώρος ορίζεται να είναι τριών ειδών : εξωτερικός, κτίριο (με ένα δωμάτιο) και συγκεκριμένο μέρος μέσα στο δωμάτιο. Οι agents μπορούν να είναι 2 ειδών : client και server με τον τελευταίο να έχει επιπλέον σαν ιδιότητα μια λίστα από τις υπηρεσίες που παρέχει. Ακόμα ορίζονται οι γενικές κλάσεις υπηρεσία (service), και συναλλαγή (transaction) που αναπαριστούν βασικές δράσεις που μπορούν να πραγματοποιήσουν οι agents. Αντίστοιχα ορίζονται οι συναρτήσεις TRANS, MOVE, COMM, EXEC που μετακινούν, αλλάζουν τη θέση του σώματος, ζητούν μια δράση από άλλο agent, και εκτελούν μια δράση αντίστοιχα.

Σε δεύτερο επίπεδο ορίζεται το συγκεκριμένο σενάριο (script) του κουρείου. Ορίζονται δηλαδή στιγμιότυπα των παραπάνω κλάσεων :
agent: customer (client) , barber (server),
place: outsidePlace (outside), barbershop (building), desk (interior), workingSeat (interior), waitingSeat (interior),
service: shave, hairwash, haircut,
transaction: payment,
που αρχικοποιούνται σε default τιμές. Ακόμα ορίζονται σκηνές (scenes), δηλαδή συναρτήσεις που αναπαριστούν διαδικαστική γνώση για το συγκεκριμένο σενάριο σε μορφή βημάτων που εκτελούνται σειριακά:
1.entering,
2.movingToWorkingSeat
3.ordering,
4.servicing,
5.billing,
6.paying,
7.exiting.

Τέλος τρέχει ένα συγκεκριμένο στιγμιότυπο του σεναρίου, δηλαδή δύο πελάτες μπαίνουν στο κουρείο και ζηούν συγκεκριμένες υπηρεσίες (scene3) (τα scenes 4-7 εκτελούνται αυτόματα όταν εκτελεστεί το scene3).
Μετά την εκτέλεση ο κόσμος του προγράμματος βρίσκεται σε μια κατάσταση όπου ο κουρέας περιμένει στο γραφείο τον επόμενο πελάτη, έχοντας παράσχει την ζητούμενη υπηρεσία και έχοντας πληρωθεί το αντίτιμο, ο πελάτης στέκεται έξω από το κουρείο φρεσκαρισμένος και κατά τι φτωχότερος, και ο κύκλος είναι έτοιμος να ξανά-αρχίσει. Παράλληλα το πρόγραμμα είναι σε θέση να απαντήσει αν χρησιμοποιήθηκε το τάδε ή το δείνα εργαλείο ή ποιο ήταν το κόστος της υπηρεσίας, ή ο χρόνος που χρειάστηκε.

Παραθέτω τον κώδικα:

;typoi
(define-struct service;parexomeni ipiresia
(name
instruments ;ergaleia poy xreiazontai gia tin ilopoiisi tis ipiresias
cost ;kostos
time) )

(define-struct transaction ;sinalagi
(money ;xrimata
reason ;logos
) )

(define-struct agent
(name
currentPlace ;meros pou vriskete
currentPosition ;Thesi swmatos
nextAction ;Epomeni drasi
nextActionTarget ;Stoxos (agent/place) epomenis drasis
lastAction ;proigoumeni drasi
lastActionTarget ;Stoxos proigoumenis drasis
acceptedAction ;Drasi pou dexthike
acceptedActionSource ;Pigi drasis pou dex8ike
money) ;xrimata
)

(define-struct (server agent) ;eksipiretis
{services} ;ipiresies pou parexei
)

(define-struct (client agent) ;eksipiretoumenos
() )

(define-struct place ;meros
(name places) ;lista me geitonika meri
)

(define-struct (outside place) ;ekswterikos xwros
( ) )

(define-struct (building place) ;ktirio
( ) )

(define-struct (interior place) ;eswterikos xwros
(positionC ;8esi swmatos tou client
positionS ;8esi swmatos tou server
occupied) ;kateilimeno (true/false)
)

;general functions
(define (memberOf item list)
(if (empty? list)
false
(if (equal? (car list) item)
true
(memberOf item (cdr list))
)
)
)

(define (TRANS person placeToGo) ;metafora agent se place
(if (equal? (agent-currentPosition person) "standing")
(if (interior? placeToGo) ;an 8elei na paei se eswteriko xwro
(if (client? person) ;an einai eksipiretoumenos
(if (not (interior-occupied placeToGo)) ;an to meros pou 8elei na paei den einai kateilimeno
(begin
(if (interior? (agent-currentPlace person)) ;an itan se eswteriko xwro
(set-interior-occupied! (agent-currentPlace person) false)
)
(set-agent-currentPlace! person placeToGo) ;pigene sto meros
(set-interior-occupied! placeToGo true) ;kane to occupied=true
)
(begin
(display "Error: TRANS:")
(display (agent-name person))
(display "the place ")
(display (place-name placeToGo))
(display "is occupied ")
(display "\n")
)
)
(begin ;an einai eksipiretis
(set-agent-currentPlace! person placeToGo) ;pigene sto meros
)
)
(begin ;an 8elei na paei se ekswteriko xwro h se ktirio
(if (client? person) ;an einai eksipiretoumenos
(if (interior? (agent-currentPlace person)) ;an itan se eswteriko xwro
(set-interior-occupied! (agent-currentPlace person) false) ;kane ton occupied=false
)
)
(set-agent-currentPlace! person placeToGo) ;pigene sto meros
)
)
(begin
(display "Error: TRANS:")
(display (agent-name person))
(display " is not standing")
(display "\n")
)
)
(display "TRANS: ")
(display (agent-name person))
(display " : ")
(display (place-name (agent-currentPlace person)))
(display "\t")
(display (agent-currentPosition person))
(display "\n")
)

(define (MOVE person positionToTake) ;allagi thesis swmatos
(set-agent-currentPosition! person positionToTake)
(display "MOVE: ")
(display (agent-name person))
(display " : ")
(display (place-name (agent-currentPlace person)))
(display "\t")
(display (agent-currentPosition person))
(display "\n")
)

(define (COMM agent1 actionToPerform agent2) ;epikoinwnia mia drasis pou zita o agent1 na tou efarmosei o agent2
(set-agent-nextAction! agent2 actionToPerform)
(set-agent-nextActionTarget! agent2 agent1)
(display "COMM: ")
(display (agent-name agent1))
(display " to ")
(display (agent-name agent2))
(display " : ")
(if (or (transaction? (agent-nextAction agent2)) (service? (agent-nextAction agent2)))
(begin
(if (service? (agent-nextAction agent2))
(display (service-name (agent-nextAction agent2)))
)
(if (transaction? (agent-nextAction agent2))
(begin
;(display (service-name (transaction-reason (agent-nextAction agent2))))
(display "\t")
(display (transaction-money (agent-nextAction agent2)))
)
)
)
(display (agent-nextAction agent2))
)
(display "\n")
)

(define (EXEC currentAgent) ;ektelesi tou nextAction ston nextActionTarget oi draseis mporei na einai services transactions (draseis me stoxo) h draseis xeris stoxo pou anaparistountai me strings (px waiting leaving)
(display "EXEC: ")
(display (agent-name currentAgent))
(display " : ")
(set-agent-acceptedAction! (agent-nextActionTarget currentAgent) (agent-nextAction currentAgent))
(set-agent-lastAction! currentAgent (agent-nextAction currentAgent))
(set-agent-lastActionTarget! currentAgent (agent-nextActionTarget currentAgent))
(display (agent-lastAction currentAgent))
(if (service? (agent-nextAction currentAgent))
(display (service-name (agent-acceptedAction (agent-nextActionTarget currentAgent))))
)
(if (equal? (agent-nextAction currentAgent) "waiting")
()
)
(if (transaction? (agent-nextAction currentAgent))
(begin
(set-agent-acceptedAction! (agent-nextActionTarget currentAgent) (agent-nextAction currentAgent))
(set-agent-money! (agent-nextActionTarget currentAgent) (+ (agent-money (agent-nextActionTarget currentAgent)) (transaction-money payment)))
(set-agent-money! currentAgent (- (agent-money currentAgent) (transaction-money payment)))
(set-transaction-reason! payment (agent-acceptedAction currentAgent))
(display (service-name (transaction-reason (agent-nextAction currentAgent))))
(display "\t")
(display (transaction-money (agent-nextAction currentAgent)))
)
)
(display "\n")
(set-agent-nextAction! currentAgent "null")
(set-agent-nextActionTarget! currentAgent "null")
)

;To Senario tou Koureiou

;stigmiotipa anaparistoun enoiologiki gnwsi
;ipiresies
(define shave ;ksirisma (make-service "shave" '("foam" "razor" "shavingMachine") 5 10) )

(define hairwash ;lousimo (make-service "hairwash" '("conditioner" "shampoo") 8 15) )

(define haircut ;kourema (make-service "haircut" '("scissors" "shavingMachine") 15 30) )

;sinalages
(define payment ;plirwmi (make-transaction 0 "null") )

;merh
(define desk ;grafeio
(make-interior "Grafeio" '(barbershop) "standing" "null" true) )

(define waitingSeat ;8esi anamonis
(make-interior "Thesi Anamonis" '(barbershop) "sitting" "null" false) )

(define workingSeat ;8esi ergasias
(make-interior "Thesi Ergasias" '(barbershop) "standing" "sitting" false) )

(define barbershop ;koureio
(make-building "Koureio" '(desk waitingSeat workinSeat outsidePlace)) )

(define outsidePlace ;eksw
(make-outside "Eksw" '(barbershop)) )

;agents
(define customer ;pelatis
(make-client "Kwstas" outsidePlace "standing" "entering" barbershop "null" "null" "null" "null" 20) )

(define customer2 ;pelatis
(make-client "giwrgos" outsidePlace "standing" "entering" barbershop "null" "null" "null" "null" 30) )

(define barber ;koureas
(make-server "Aggelos" desk "standing" "waiting" "null" "null" "null" "null" "null" 20 '(shave hairwash haircut)) )

;skines anaparistoun diadikastiki gnwsi
;Scene 1: Entering
(define (entering C barbershop)
(display "entering")
(display "\n")
(TRANS C barbershop)
(if (not (interior-occupied workingSeat)) ;an einai adeia i 8esi ergasias
(begin
(TRANS C workingSeat) ;pigene ekei
(MOVE C "sitting") ;katse
(set-agent-nextAction! C "null") ;oloklirwses tin drasi kai den exeis epomeni
(set-agent-nextActionTarget! C "null")
)
(if (not (interior-occupied waitingSeat)) ;alliws an einai adeia i 8esi anamonis
(begin
(TRANS C waitingSeat) ;pigene
(MOVE C "sitting") ;katse
(set-agent-nextAction! C "waiting") ;nea drasi: perimene
(set-agent-nextActionTarget! C "null") ;drasi xwris stoxo
)
)
)
)

;Scene 3: Ordering
(define (ordering C S servic) ;paragelia mias service apo ton server
(display "ordering")
(display "\n")
(TRANS S workingSeat) ;o server pigenei sti 8esi ergasias
(COMM C servic S) ;o client zita tin ipiresia
(servicing C S servic) ;epomeno scene
)

;Scene 4: Servicing
(define (servicing C S servic) ;paroxi tis ipiresias
(display "servicing")
(display "\n")
(EXEC S) ;ektelesi tis nextAction tou server (pou einai i service pou ziti8ike apo ton client sto proigoumeno scene)
(billing C S servic) ;epomeno scene
)

;Scene 5: Billing
(define (billing C S servic) ;xrewsi
(display "billing")
(display "\n")
(set-transaction-money! payment (service-cost servic)) ;xrewsi oso to kostos tis parexomenis ipiresias
(set-transaction-reason! payment (service-name servic))
(COMM S payment C) ;o server zita drasi tipou transaction apo ton client
(paying C S servic) ;epomeno scene
)

;Scene 6: Paying
(define (paying C S servic) ;eksoflisi
(display "paying")
(display "\n")
(MOVE C "standing") ;o pelatis se or8ia 8esi
(TRANS C barbershop) ;apomakrinete apo ti 8esi ergasias
(EXEC C) ;ektelei tin drasi tou (pou einai transaction apo to proigoumeno scene)
(TRANS S desk) ;o server paei sto grafeio gia na 3anaarxisei o kiklos
(set-agent-nextAction! S "waiting")
(exiting C) ;epomeno scene
)

(define (exiting C) ;o pelatis feygei
(display "leaving")
(display "\n")
(TRANS C outsidePlace)
(set-agent-nextAction! C "leaving")
(set-agent-nextActionTarget! C "null")
(if (interior-occupied waitingSeat)
(movingToWorkingSeat customer2)
)
)

(define (movingToWorkingSeat C) ;metafora apo 8esi ergasias se 8esi anamonis
(display "moving to working seat")
(display "\n")
(MOVE C "standing")
(if (not (interior-occupied workingSeat)) ;an einai adeia i 8esi ergasias
(begin
(TRANS C workingSeat) ;pigene ekei
(MOVE C "sitting") ;katse
(set-agent-nextAction! C "null") ;oloklirwses tin drasi kai den exeis epomeni
(set-agent-nextActionTarget! C "null")
(ordering customer2 barber haircut)
)
(if (not (interior-occupied waitingSeat)) ;alliws an einai adeia i 8esi anamonis
(begin
(TRANS C waitingSeat) ;pigene
(MOVE C "sitting") ;katse
(set-agent-nextAction! C "waiting") ;nea drasi: perimene
(set-agent-nextActionTarget! C "null") ;drasi xwris stoxo
)
)
)
)

(begin
(display "arxiki katastasi")
(display "\n")
(display (agent-name customer))
(display " : ")
(display (place-name (agent-currentPlace customer)))
(display "\t")
(display (agent-nextAction customer))
(display "\n")
(display (agent-name customer2))
(display " : ")
(display (place-name (agent-currentPlace customer2)))
(display "\t")
(display (agent-nextAction customer2))
(display "\n")
(entering customer barbershop)
(entering customer2 barbershop)
(if (equal? (agent-currentPlace customer) workingSeat)
(begin
(ordering customer barber hairwash)
)
(exiting customer)
)
)


Μετά την εκτέλεση το πρόγραμμα εκτυπώνει τα παρακάτω :

Welcome to DrScheme, version 4.1 [3m].Language: Pretty Big; memory limit: 128 megabytes.
arxiki katastasi
Kwstas : Eksw entering
giwrgos : Eksw entering
entering
TRANS: Kwstas : Koureio standing
TRANS: Kwstas : Thesi Ergasias standing
MOVE: Kwstas : Thesi Ergasias sitting
entering
TRANS: giwrgos : Koureio standing
TRANS: giwrgos : Thesi Anamonis standing
MOVE: giwrgos : Thesi Anamonis sitting
ordering
TRANS: Aggelos : Thesi Ergasias standing
COMM: Kwstas to Aggelos : hairwash
servicing
EXEC: Aggelos : #hairwash
billing
COMM: Aggelos to Kwstas : 8
paying
MOVE: Kwstas : Thesi Ergasias standing
TRANS: Kwstas : Koureio standing
EXEC: Kwstas : #hairwash 8
TRANS: Aggelos : Grafeio standing
leaving
TRANS: Kwstas : Eksw standing
moving to working seat
MOVE: giwrgos : Thesi Anamonis standing
TRANS: giwrgos : Thesi Ergasias standing
MOVE: giwrgos : Thesi Ergasias sitting
ordering
TRANS: Aggelos : Thesi Ergasias standing
COMM: giwrgos to Aggelos : haircut
servicing
EXEC: Aggelos : #haircut
billing
COMM: Aggelos to giwrgos : 15
paying
MOVE: giwrgos : Thesi Ergasias standing
TRANS: giwrgos : Koureio standing
EXEC: giwrgos : #haircut 15
TRANS: Aggelos : Grafeio standing
leaving
TRANS: giwrgos : Eksw standing>

Επιπλέον το πρόγραμμα μπορεί να απαντήσει σε μια σειρά από ερωτήσεις του τύπου :

(agent-money barber) πόσα χρήματα έχει ο κουρέας
(agent-lastActionTarget barber) ποιά ήταν η τελευταία δράση του κουρέα
(agent-name (agent-lastActionTarget barber)) ποιος ήταν ο στόχος της τελευταίας δράσης του κουρέα
(agent-currentPlace customer) που βρίσκεται τώρα ο 1ος πελάτης
(place-name (agent-currentPlace customer)) ποιο το όνομα του μέρους που βρίσκεται τώρα ο 1ος πελάτης
(agent-nextAction customer)
(agent-lastAction customer)
(transaction-reason (agent-lastAction customer))
(service name (transaction-reason (agent-lastAction customer)))
(transaction-money (agent-lastAction customer))
(agent-money customer)
(agent-lastActionTarget customer)
(agent-name (agent-lastActionTarget customer))

Scheme: Μάθημα Δευτέρας 26/11/2007

Μεταφέρω τις ασκήσεις που κάναμε την περασμένη Δευτέρα.

1.

(define (oura x y)
   (cond   ((> x y)
        'End)
   ((<= x y)     
       (display " ")     
       (display x)     
       (oura (+ 1 x) y)))) 

που μας δίνει (για x=1 και y=20):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20End


2.

(define (oura2 x y)  
  (cond     ((> x y)
        'End)
  ((<= x y)     
      (oura2 (+ 1 x) y)     
      (display " ")     
      (display x)))) 

που μας δίνει (για x=1 και y=20):
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

*Από εδώ και κάτω αλλάξαμε το 'End με => (display "End")

3.

(define (oura3 x y)
   (cond   ((> x y)
        (display "End"))
     ((<= x y)     
       (oura3 (+ 1 x) y)     
       (display " ")     
       (display x)))) 

που μας δίνει (για x=1 και y=20):
End 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

4.

(define (oura4 x y)  
  (cond     ((> x y)
       (display "End"))
  ((<= x y)     
        (oura4 (+ 1 x) y)     
        (display " ")     
        (display x)    
        (oura4 (+ 1 x) y)))) 

που μας δίνει (για x=1 και y=20):
άλλ' αντί άλλων (αλλά το κάνουμε για εκπαιδευτικούς σκοπούς)

5.

(define (oura5 x y)  
   (cond     ((> x y)
        (display "End"))
     ((<= x y)
          (display " ")
          (display x)
          (oura5 (+ 1 x) y)
         (display " ")
          (display x))))

που μας δίνει (για x=1 και y=20):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20End 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

Αυτά από μένα.
Για περεταίρω εξήγηση του τι σημαίνουν όλα αυτά θα μπορούσα να προσπαθήσω να τη δώσω, αλλά το αφήνω στους πληροφορικάριους ;)

Scheme 2: η IF και η φρικαλέα αναδρομή

IF:

Η δομή if-then-else είναι μία από τις πιο κοινές εκφράσεις στις γλώσσες προγραμματισμού. Η ακριβής σύνταξή της μπορεί να διαφέρει από γλώσσα σε γλώσσα, αλλά τα βασικά της στοιχεία είναι σχεδόν πάντα τα ίδια. Αποτελείται από τρία βασικά κομμάτια:

if [συνθήκη] then
        [κάνε κάτι]
else
        [κάνε κάτι άλλο]

τα οποία στη Scheme γράφονται λιγάκι διαφορετικά:

(if (συνθήκη)
   (κάνε κάτι)
   (κάνε κάτι άλλο)
)

Όταν η γλώσσα προγραμματισμού συναντήσει κάποιο if, περιμένει να ακολουθήσει μια boolean έκφραση, δηλαδή μια λογική πράξη που θα έχει ως αποτέλεσμα την τιμή ΑΛΗΘΕΣ ή ΨΕΥΔΕΣ. Αυτή τη λογική πράξη τη λέμε και συνθήκη της if. Λογικές πράξεις είναι η σύγκριση αριθμών, η σύγκριση μεταβλητών μεταξύ τους για ισότητα ή κάτι πιο πολύπλοκο όπως πχ το αν μια λίστα περιλαμβάνει ένα συγκεκριμένο στοιχείο. Το (3>5) είναι μια λογική πράξη με αποτέλεσμα ΨΕΥΔΕΣ. Το (x=y) είναι μια λογική πράξη που θα δώσει αποτέλεσμα ΑΛΗΘΕΣ αν το x είναι ίσο με το y και ΨΕΥΔΕΣ αν δεν είναι.

Αν η συνθήκη είναι αληθής, τότε θα εκτελεστεί το 'κάνε κάτι', αλλιώς θα εκτελεστεί το 'κάνε κάτι άλλο'. Για παράδειγμα:

(if ( < degree 5) 
 (display “Δεν περάσατε το μάθημα”) 
 (display “Περάσατε το μάθημα”) 
)

Αν η μεταβλητή degree είναι μικρότερη του 5, εκτελείται η πρώτη εντολή (και δεν περνάτε), αλλιώς εκτελείται η δεύτερη εντολή (και περνάτε). Αν δεν έγινε κατανοητό το παράδειγμα, μάλλον θα εκτελεστεί η πρώτη εντολή. :P

Πάνω σε αυτή τη λογική μπορούμε να χτίσουμε πιο πολύπλοκες εκφράσεις. Αντί να εκτελέσουμε μόνο μια εντολή σε κάθε περίπτωση, μπορούμε να εκτελέσουμε περισσότερες με χρήση του begin. Το begin ομαδοποιεί πολλές εντολές έτσι, ώστε το if (ή άλλες δομές) να τις εκτελέσει ως μία εντολή. Για παράδειγμα:

(if (< degree 5) 
 (begin 
  (display “Δεν περάσατε το μάθημα.”)
  (display “Δοκιμάστε ξανά του χρόνου.”)
 )  
 (begin 
  (display “Περάσατε το μάθημα.”) 
  (display “Για πτυχίο θέλετε ακόμα....”)
 ) 
)

Επίσης, μπορούμε να βάλουμε μία ή περισσότερες if μέσα σε μια άλλη if. Δηλαδή:

(if (< degree 5) 
 (display “Δεν περάσατε το μάθημα”) 
 (if (< degree 8)
  (display “Περάσατε με βαθμό: Καλώς”)
  (display “Περάσατε με βαθμό: Άριστα”)  
 ) 
)

Αν η degree είναι μικρότερη του 5, θα τυπωθεί το “Δεν περάσατε το μάθημα” και θα σταματήσει η εκτέλεση του προγράμματος. Αν η degree δεν είναι μικρότερη του 5, θα εκτελεστεί το δεύτερο σκέλος της if (αυτό που είναι στις γραμμές 3-6), το οποίο περιέχει μια δεύτερη if, η οποία θα τυπώσει το κατάλληλο μήνυμα ανάλογα με το αν η degree είναι μικρότερη ή όχι του 8.

Κάτι το οποίο αξίζει να προσέξετε στην προκειμένη περίπτωση είναι το ότι αν εκτελεστεί η δεύτερη if (γραμμή 3), αυτό σημαίνει ότι ΣΙΓΟΥΡΑ η degree είναι μεγαλύτερη ή ίση του 5, αφού βρισκόμαστε στην περίπτωση που η συνθήκη της πρώτης if (γραμμή 1) έχει δώσει ΨΕΥΔΕΣ.

Φυσικά, μπορούμε να βάζουμε όσες if θέλουμε τη μία μέσα στην άλλη.

Αναδρομή (recursion)

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

ΕΚΠΑΙΔΕΥΤΗΣ: Λοιπόν, τα κατάλαβες; Πηδάς από το αεροπλάνο στα 4000 μέτρα και το αλεξίπτωτο θα ανοίξει μόνο του.

ΝΕΟΣ: Εντάξει, αλλά τι γίνεται αν δεν ανοίξει και βρίσκομαι στα 3000 μέτρα;

Ε: Δε θα γίνει κάτι τέτοιο, αλλά αν γίνει θα τραβήξεις το σκοινί του αλεξίπτωτου και θα ανοίξει.

Ν: Και αν δεν ανοίξει και είμαι στα 2000 μέτρα;

Ε: Θα πατήσεις το κουμπί ασφαλείας του αλεξίπτωτου και θα ανοίξει.

Ν: Και αν δεν ανοίξει και είμαι στα 1000 μέτρα;

Ε: Θα τραβήξεις το σκοινί του εφεδρικού αλεξίπτωτου και θα ανοίξει το εφεδρικό.

Ν: Και αν δεν ανοίξει και είμαι στα 200 μέτρα;

Ε: Θα πατήσεις το κουμπί ασφαλείας του εφεδρικού και θα ανοίξει.

Ν: Και αν δεν ανοίξει και είμαι στα 2 μέτρα;

Ε: Καλά, ρε φίλε, είσαι σοβαρός; Δεν μπορείς να πηδήξεις από 2 μέτρα;

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

Ας πούμε ότι πρέπει να χτίσουμε έναν τοίχο με 10 σειρές τούβλα. Η μία προσέγγιση είναι να ξεκινήσουμε να βάλουμε την πρώτη σειρά τούβλα, μετά τη δεύτερη, μετά την τρίτη, μέχρι να φτάσουμε στη δέκατη. Η αναδρομική προσέγγιση είναι να κάνουμε την πάπια και να αρνηθούμε να κοιτάξουμε το πρόβλημα κατάματα. Αντ' αυτού, ανακοινώνουμε υπερήφανα με στεντόρεια φωνή: “Ένας τοίχος με 10 σειρές τούβλα; Παιχνιδάκι: παίρνουμε έναν τοίχο με 9 σειρές τούβλα και απλά προσθέτουμε μια σειρά τούβλα”. Με τον τρόπο αυτό, (ψευτο)λύσαμε το αρχικό πρόβλημα με το να επέμβουμε ελάχιστα (βάλαμε μια σειρά τούβλα) σε ένα κατά ελάχιστα λιγότερο πολύπλοκο πρόβλημα (ένας τοίχος με 9 σειρές τούβλα). Επειδή όμως οι εργοδότες μας δεν έμειναν ικανοποιημένοι και ρωτάνε από πού ξεφύτρωσε ο τοίχος με τα 9 τούβλα, τους κάνουμε τη χάρη και απαντάμε: “Θα πάρουμε έναν τοίχο με 8 τούβλα και θα προσθέσουμε μία σειρά ακόμα. Έλεος!”. Επειδή έχουμε μπλέξει με ηλίθιους που δεν καταλαβαίνουν, οι εργοδότες επιμένουν και εμείς απαντάμε με την ίδια συλλογιστική. Με τα πολλά, φτάνουμε να μας ρωτάνε πού θα βρούμε έναν τοίχο με μία σειρά τούβλα. Η απάντηση είναι πλέον τόσο στοιχειώδης που δεν αξίζει να ασχολούμαστε άλλο μαζί τους.

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

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

Μερικά από τα (καμμένα) ακρωνύμια της πληροφορικής είναι επίσης αναδρομές. Η γλώσσα προγραμματισμού PHP σημαίνει “PHP: Hypertext Preprocessor”. Η οικογένεια λειτουργικών συστημάτων GNU σημαίνει "GNU's Not Unix". Ναι, εντάξει, ξέρω, είμαστε τελείως κατεστραμμένοι!

Αναδρομή υπάρχει και στα μαθηματικά. Για παράδειγμα, το παραγοντικό ενός θετικού ακεραίου αριθμού n ορίζεται ως το γινόμενο:

n! = n(n-1)(n-2)...1

ή αλλιώς

Το f(n) ισούται με το n επί το f(n-1). Για να βρούμε, δηλαδή το παραγοντικό του 5, το 5! ή αλλιώς f(5) έχουμε:

f(5) = 5 * f(4)

= 5 * 4 * f(3)

= 5 * 4 * 3 * f(2)

= 5 * 4 * 3 * 2 * f(1)

= 5 * 4 * 3 * 2 * 1

Δοκιμάστε να το κάνετε συνάρτηση στη Scheme (χωρίς να κοιτάτε τη λύση που ακολουθεί)

(define (f n)
   (if (= n 0)
       1
       (* n (f (- n 1)))
   )
)

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

Αυτό, λοιπόν, είναι στην ουσία η αναδρομή: μια συνάρτηση που καλεί τον εαυτό της (καλά, εντάξει, αυτός δεν είναι ακριβής ορισμός. Αν θέλετε ακριβή ορισμό κοιτάξτε εδώ ή εδώ καλύτερα). Το σημείο κλειδί είναι αυτό που ονομάζουμε σημείο εξόδου ή σημείο τερματισμού, δηλαδή, εκείνη την απλή περίπτωση όπου η λύση είναι συγκεκριμένη και δεν είναι αναδρομή, εκεί που θα σταματήσει η διαδικασία να αναφέρεται στον εαυτό της. Στον υπολογισμό του παραγοντικού, σημείο εξόδου είναι το f(0)=1. Αν μια συνάρτηση δεν έχει σημείο εξόδου θα συνεχίσει να καλεί τον εαυτό της επ' άπειρον (ή μέχρι να τελειώσει η μνήμη). Για δοκιμάστε να τρέξετε το:

(define (f n)
     (* n (f (- n 1)))
)

Θα χρειαστεί να πατήσετε το STOP αν το τρέξετε γιατί δεν πρόκειται να σταματήσει. Σε εμένα κόλλησε και έκλεισε η Scheme μόνη της. Γι'αυτό το λόγο, ΠΑΝΤΑ ΒΑΖΟΥΜΕ ΣΗΜΕΙΟ ΕΞΟΔΟΥ.

Ένα άλλο παράδειγμα από τα μαθηματικά είναι η ακολουθία fibonacci.

Μπορείτε να τη φτιάξετε στη Scheme; Περιμένω την απάντηση στα σχόλια.

Μια άλλη εφαρμογή της αναδρομής είναι οι πύργοι του Ανόι. Μπορείτε να βρείτε μια σχετική εφαρμογή του εδώ.

Αυτά. Αν έχω κάνει κανένα λάθος πουθενά, δικαιολογούμαι λόγω της ώρας.

Περιμένω απορίες και/ή τις λύσεις των παραπάνω ερωτήσεων.

Scheme *UPDATED*

Ύστερα από προτροπή της Αμαλίας, θα προσπαθήσω να περιγράψω, σύντομα και χωρίς ιδιαίτερη ακρίβεια, μερικά από τα βασικά στοιχεία της Scheme που έχουμε πει στο μάθημα. Σκοπός μου ΔΕΝ είναι να δώσω ένα ολοκληρωμένο manual ή tutorial, τέτοια υπάρχουν αρκετά στο Internet. Ούτε αυτά που γράφω είναι 100% σωστά, άλλωστε τώρα τη μαθαίνω και εγώ τη Scheme. Απλά, επιχειρώ να φτιάξω ένα quick and dirty σημείο αναφοράς και μερικές οδηγίες, μόνο και μόνο για να ξεκινήσουμε.

Αν και ελπίζω ότι θα λύσω κάποιες απορίες, είμαι σίγουρος ότι θα προσπεράσω άθελά μου τις περισσότερες, ενώ δεν αποκλείεται να δημιουργήσω και νέες. Γι'αυτό, κάντε τις ερωτήσεις σας στα σχόλια για να τις απαντήσω, ώστε να μπορούν όλοι να τις διαβάσουν και ΙΣΩΣ χρησιμοποιήσουμε για πρώτη φορά το blog για το σκοπό που το φτιάξαμε αρχικά (και όχι για εικόνες και βιντεάκια :P ).

Μετά το disclaimer, βαθιά ανάσα και βουτάμε στα βαθιά:

Βασικές έννοιες:

μεταβλητή: μια συμβολική αναπαράσταση που αναφέρεται σε μια ποσότητα ή μια έκφραση. Είναι ένα μέρος στη μνήμη του υπολογιστή που έχουμε δεσμεύσει για να βάζουμε δεδομένα (πχ αριθμούς ή χαρακτήρες). Η μεταβλητή είναι σαν ένα συρτάρι στο οποίο αποθηκεύουμε διάφορα αντικείμενα (τα δεδομένα).

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

(define (f x) (+ x 2) )

αυτό που κάνουμε είναι ότι ορίζουμε τη συνάρτηση f, η οποία δέχεται το όρισμα x, δηλαδή το x είναι η είσοδος της συνάρτησης. Το τι θα κάνει η f όταν θα πάρει το x καθορίζεται στο σώμα της συνάρτησης. Στην προκειμένη περίπτωση, το σώμα είναι (+ x 2), δηλαδή θα προσθέσει στο x το 2. Συνήθως, το κομμάτι κώδικα αυτό, υπάρχει στο περιθώριο και εκτελείται μόνο όταν το καλέσουμε. Αυτό λέγεται κλήση συνάρτησης. Για να καλέσουμε μια συνάρτηση χρειαζόμαστε (εκτός από το όνομά της, φυσικά) να της δώσουμε όσα ορίσματα απαιτεί. Άρα, για να καλέσουμε την f με είσοδο το 5 θα δώσουμε:

(f 5)

λίστα: ένα σύνολο αντικειμένων. Κάτι σαν πολλές μεταβλητές στη σειρά που έχουν ένα όνομα.

προθεματική σύνταξη: Η εκνευριστική σύνταξη των αριθμητικών πράξεων στη Scheme, όπου πρέπει πρώτα να γράφουμε το σύμβολο της πράξης και μετά τους αριθμούς (με κενά μεταξύ τους). Για παράδειγμα, το 3+5 στη Scheme γράφεται (+ 3 5), το 4*2*8 γράφεται (* 4 2 8).

σύνταξη: το πώς πρέπει να γράφεται μια εντολή για να δουλέψει. Πχ, η define συντάσσεται:

(define μεταβλητή τιμή) ή

(define (συνάρτηση ορίσματα) (σώμα))

Μερικές βασικές εντολές:

define: η πιο ευρέως χρησιμοποιούμενη εντολή ως τώρα (να συλληφθεί ο Εβραίος!), η define μπορεί να ορίσει την τιμή μιας μεταβλητής, να ορίσει τα περιεχόμενα μιας λίστας και να ορίσει μια συνάρτηση (δηλαδή ΤΙ κάνει η συνάρτηση). Γενικά, όλα τα σφάζει, όλα τα μαχαιρώνει, χωρίς τη define δε φαίνεται να κάνουμε βήμα.

eval: η πιο ψυχανώμαλη εντολή. Σύμφωνα με το manual, αξιολογεί (evaluates) ό,τι ακολουθεί μέσα στο συγκεκριμένο πλαίσιο στο οποίο ανήκει. Με άλλα λόγια, προσπαθεί να κάνει κάτι έξυπνο. Μερικές φορές τα καταφέρνει. Έτσι, αν έχουμε ορίσει τις σχέσεις

(define George 'Athens)

(define Athens 'Greece)

και δώσουμε

(eval George)

θα απαντήσει: Greece. Σε αυτή την περίπτωση δηλαδή, θα ακολουθήσει τη σειρά των συσχετίσεων που του έχουμε δώσει.

set!: αλλάζει την τιμή μιας μεταβλητής (ή λίστας). Η διαφορά από τη define είναι ότι η set! απλά αλλάζει την τιμή, ενώ η define καταστρέφει ό,τι υπήρχε και δημιουργεί μια καινούρια μεταβλητή με το ίδιο όνομα. Η διαφορά γίνεται εμφανής με τις λίστες.

display: μια απλή εντολή! τυπώνει ό,τι ακολουθεί. Αν αυτό που ακολουθεί είναι μέσα σε διπλά εισαγωγικά (“) το τυπώνει ως είναι, αν είναι χωρίς εισαγωγικά υποθέτει ότι είναι μεταβλητή και προσπαθεί να τυπώσει την τιμή της.

car: τυπώνει το πρώτο στοιχείο μιας λίστας.

cdr: τυπώνει τη λίστα από το δεύτερο στοιχείο και μετά.

first, second, third,...: τυπώνει το πρώτο, δεύτερο, τρίτο, κλπ στοιχείο της λίστας, αντίστοιχα.

cons: προσθέτει ένα στοιχείο στην αρχή μιας λίστας.

Ένα από τα προβλήματα που παρουσιάζονται από νωρίς είναι το ότι πρέπει να συνδυάσετε πολλές συναρτήσεις. Έτσι, έχουμε ένα μακρινάρι μια συνάρτηση να καλεί μια άλλη, η οποία καλεί μια άλλη, η οποία με τη σειρά της καλεί μια άλλη, κλπ. Είναι εύκολο να χαθείτε μέσα στις πολλές παρενθέσεις και τις απανωτές εντολές. Γι' αυτό, 1) αποφύγετε να γράφετε πολλές εντολές στην ίδια γραμμή και 2) σιγουρευτείτε ότι η δομή του μακριναριού (το έχει το λεξικό! Απίστευτο!) είναι σωστή πριν γράψετε το περιεχόμενό του. Τι θέλω να πω: Αν προσπαθήσετε να γράψετε σε μία γραμμή και με τη μία το

(define (f x y) (+ (* (expt x y) x) (/ (- x y) 4)))

είναι σίγουρο ότι θα κάνετε λάθος. Αντί αυτού, προσπαθήστε να το δομήσετε βήμα-βήμα και σε πολλές σειρές, βάζοντας την παρένθεση που κλείνει ένα κομμάτι κάτω από την παρένθεση που το ανοίγει. Ας πούμε, το παραπάνω μακρινάρι σε 6 βήματα:

1.
(define (συνάρτηση)
      (σώμα)
)

2.
(define (f x y)
      (+  (κάτι) (κάτι άλλο)  )
)

3.
(define (f x y)
      (+
         (κάτι)
         (κάτι)
      )
)

4.
(define (f x y)
      (+
         (* (κάτι) (κάτι) )
         (/ (κάτι) (κάτι) )
      )
)

5.
(define (f x y)
      (+
         (*
             (κάτι)
             (κάτι)
          )
         (/
             (κάτι)
             (κάτι)
          )
      )
)

6.
(define (f x y)
      (+
         (*
             (expt x y)
             x
          )
         (/
             (- x y)
             4
          )
      )
)

Αυτά τα ολίγα προς το παρόν. Περιμένω απορίες. Και να θυμάστε: δεν υπάρχουν ηλίθιες ερωτήσεις (μόνο ηλίθιοι άνθρωποι) :DDDDDDD

UPDATE 1/11/07:

Όπως σωστά μου επισημάνθηκε στο μάθημα (αλλά όχι στο blog! γιατί; Τι τα έχουμε τα σχόλια;!), ξέχασα να αναφερθώ στο μυστηριώδες quote ( ' ).
Η Scheme δείχνει μια ασυνήθιστη προθυμία να θεωρεί σχεδόν τα πάντα ονόματα μεταβλητών ή συναρτήσεων. Αν συναντήσει μια λέξη, θα προσπαθήσει να βρει ποια μεταβλητή είναι ή κάτι αντίστοιχο. Για να την αποτρέψουμε από μία τέτοια συμπεριφορά πρέπει να βάλουμε μπροστά το quote ( ' ).
Έτσι, αν γράψουμε: (display mitsos), η Scheme θα προσπαθήσει να βρει μια μεταβλητή με όνομα mitsos και αν δεν υπάρχει, θα εμφανίσει μήνυμα λάθους. Για να εκτυπώσει το mitsos πρέπει να γράψουμε (display 'mitsos), ώστε να μετριάσουμε τις αβυσσαλέες ορέξεις της Scheme για κυνήγι ονομάτων.

Scheme 2: η IF και η φρικαλέα αναδρομή