come guardare fuori per il fatto che nreverse può modificare auto, invece

Question

http://www.aiai.ed.ac.uk/~jeff/lisp/cl-pitfalls stati questo come uno dei Common Lisp insidie ​​

funzioni distruttive che si pensa possa modificare CDR potrebbe modificare auto, invece. (Per esempio, NREVERSE.)

Non sono sicuro di quali precauzioni dovrei prendere. La precauzione abituale che posso prendere dal fatto che NREVERSE può modificare i CDR è usare NREVERSE solo quando la lista (l'argomento) non condivide la coda con altre liste alle quali le mie variabili possono riferirsi successivamente (tranne che per la variabile salvi il valore di ritorno a). Quale precauzione dovrei prendere dal fatto che NREVERSE può modificare le CAR? Come è questo qualcosa a cui fare attenzione?

Answer 1

Senza alcun contesto questo è molto difficile da capire.

Esempio:

(setq list1 (list 1 2 3 4)) 

Ora abbiamo una lista di quattro numeri. La variabile list1 punta ai primi contro.

Se guardiamo a un rovescio distruttivo stiamo parlando di un'operazione che può alterare le cellule. Ci sono diversi modi in cui questo elenco può essere invertito.

Potremmo ad esempio prendere le celle del contro e invertirle. La prima cella di controllo quindi è l'ultima. Il cdr di tale cella deve quindi essere modificato in NIL.

CL-USER 52 > (setq list1 (list 1 2 3 4)) 
(1 2 3 4) 

CL-USER 53 > (nreverse list1) 
(4 3 2 1) 

Ora la nostra variabile list1 ancora punta alla stessa cella contro, ma la sua CDR è stato cambiato:

CL-USER 54 > list1 
(1) 

Per assicurarsi che la variabile punta ad una lista invertita, il programmatore ha quindi la obbligo di aggiornare la variabile e impostarla sul risultato dell'operazione nreverse. Si può anche essere tentati di sfruttare il risultato osservabile che list1 punta agli ultimi svantaggi.

Sopra ciò che uno sviluppatore Lisp di solito si aspetterebbe. La maggior parte delle implementazioni del contrario sembrano funzionare in questo modo. Ma non è specificato nello standard ANSI CL come deve essere implementato nreverse.

Quindi cosa significherebbe cambiare le CAR?

Diamo un'occhiata ad un'implementazione alternativa di nreverse:

(defun nreverse1 (list) 
    (loop for e across (reverse (coerce list 'vector)) 
     for a on list do 
     (setf (car a) e)) 
    list) 

Sopra funzione diamo la catena di celle cons intatte, ma cambia il auto.

CL-USER 56 > (setq list1 (list 1 2 3 4)) 
(1 2 3 4) 

Ora usiamo la nuova versione, nreverse1.

CL-USER 57 > (nreverse1 list1) 
(4 3 2 1) 

CL-USER 58 > list1 
(4 3 2 1) 

Ora si vede la differenza: list1 punta ancora a tutta la lista.

Sommario: è necessario essere consapevoli del fatto che esistono diverse implementazioni di nreverse possibili. Non sfruttare il solito comportamento, in cui una variabile punta agli ultimi svantaggi. Basta usare il risultato di nreverse e tutto va bene.

Side note: dove è stata utilizzata la seconda versione?

Alcune implementazioni Lisp su macchine Lisp hanno consentito una rappresentazione vettoriale di elenchi compatta. Se su un'implementazione Lisp di questo tipo non si dovesse annullare un elenco di questo tipo, gli implementatori potrebbero fornire un nreverse efficiente di tipo vettoriale.

Answer 2

In ogni caso, che si tratti di CAR o CDR di fotocellule modificate, non utilizzare NREVERSE se qualsiasi cella di controllo (inclusa la cella di primo scrigno) della lista passata può essere condivisa con un'altra lista. Utilizzare invece REVERSE.

BTW, clisp modifica infatti le automobili:

> (let ((a (list 1 2 3 4 5 6 7 8 9 0))) 
    (nreverse a) 
    a) 
(0 9 8 7 6 5 4 3 2 1)