----- 16/3/06 -----

> Abbiamo alcune difficolta' nell'implementazione degli algoritmi di
> visita degli alberi. Noi alle superiori abbiamo sempre programmato
> con linguaggi non funzionali, e quindi siamo abituati a svolgere 
> in sequenza diverse azioni, per cui l'utilizzo di Scheme ci risulta
> a volte difficoltoso.
> Nell'esempio riportato sotto, nel "cond" abbiamo messo tre azioni,
> che secondo il nostro ragionamento dovrebbero essere fatte dal
> programma una consecutivamente all'altra, invece la veridicita' di
> una esclude le altre.
> Come si pu˜ modificare il programma affinche' funzionino le altre?


----- Esempio -----

; Protocollo degli alberi
(define leaf-tree
  (lambda (elemento)
    (list elemento null null)
  ))
(define leaf?
  (lambda (albero)
    (AND (null? (cadr albero)) (null? (caddr albero)))
  ))    
(define grow-tree
  (lambda (elemento albero1 albero2)
    (list elemento albero1 albero2)
  ))
(define left
  (lambda (albero)
    (cadr albero)
  ))
(define right
  (lambda (albero)
    (caddr albero)
  ))
(define empty-tree 
  (list null null null)
  )
(define empty-tree?
  (lambda (albero)
    (null? (car albero))
  ))

; Funzione visita simmetrica
(define visitaSimmetrica
  (lambda (tree lista)
    (if (empty-tree? tree)
      lista        
      (cond
        ((NOT (null? (left tree))) (visitaSimmetrica (left tree) lista))
        ((NOT (null? (right tree))) (visitaSimmetrica (right tree) (cons (car tree) lista)))
        (else (cons (car tree) lista))
        ;Queste tre azioni dovrebbero essere svolte una dopo l'altra,
        ;mentre qui se la prima e' vera le altre due non vengono svolte
      )
    )
  )
)

; Verifica della visita simmetrica
(visitaSimmetrica
  (list 1 (list 2 (list 3 null null) (list 4 null null)) (list 5 null (list 6 null null))) null)


----- Discussione -----

Ecco alcuni commenti in relazione alla procedura di visita.

(define visitaSimmetrica
   (lambda (tree lista)

1. Le procedure Scheme rappresentano funzioni: l'unico argomento e' 
l'albero da visitare, mentre la "lista" e' il valore che la funzione
deve assumere (nell'esempio, invece, sembra si voglia definire un
parametro passato per riferimento, ma questo concetto non e' esprimibile
in  termini funzionali).

     (if (empty-tree? tree)
       lista

2. A "lista" qui non e' associato alcun valore. Se l'albero e' vuoto, 
comunque, anche la lista dei nodi sara' vuota, per cui il valore assunto
e' semplicemente "null".

       (cond
         ((NOT (null? (left tree))) ... )
         ((NOT (null? (right tree))) ... )
         (else ... )

3. Il costrutto "cond" si utilizza per scegliere l'espressione da 
valutare fra un certo numero di alternative, ma in questo caso,
intuitivamente, la visita di un  sottoalbero non esclude quella
dell'altro perche' i risultati di entrambe le visite sono necessari
per costruire la lista completa dei nodi.

           ... (visitaSimmetrica (left tree) lista)
           ... (visitaSimmetrica (right tree) (cons (car tree) lista))
           ... (cons (car tree) lista))

4. Le liste risultanti dalle visite dei sottoalberi devono poi essere 
opportunamente combinate per costruire la lista risultante, facendo
inoltre attenzione a collocare la radice al posto giusto;
ovviamente l'unico argomento pertinente e' il sottoalbero, mentre tutto 
il resto deve sparire.

         ; ...
       )
     )
   )
)

5. Ulteriore osservazione: il protocollo realizzato nella parte 
precedente del programma non permette di costruire alberi vuoti e
quindi non e' sufficiente per verificare il corretto funzionamento
dell'algoritmo di visita impostato sopra.

Quando si programma secondo il paradigma funzionale occorre sempre 
pensare in termini di relazioni fra l'oggetto che rappresenta la
soluzione del problema e gli oggetti che rappresentano i dati del
problema (qui ho usato il termine "oggetto" in senso generico, non
nel senso della programmazione orientata agli oggetti).
E' importante riuscire a ragionare (anche) in questo modo: per
questo motivo puo' essere utile partire con un linguaggio funzionale.
Pensando in termini di sequenze di azioni non si va molto lontano
perche' si e' troppo condizionati dall'architettura della macchina
e si perde di vista il problema da risolvere.

----- * -----