In un dialetto Lisp, ho implementato il supporto di tipo ANSI-CL per la stampa di oggetti in modo tale che la loro struttura circolare e condivisa sia codificata. Questo è abilitato dalla variabile speciale *print-circle*
. Analogamente a ANSI-CL, lo faccio funzionare quando attraversa oggetti che hanno metodi di stampa personalizzati. Ma ci sono casi angosciosi.
Per riferimento, facciamo questo diagramma. L'oggetto X è la cosa che viene stampata e la piramide sottostante rappresenta l'albero dipendente degli oggetti costitutivi: elenchi annidati e quant'altro. L'oggetto O è un costituente che è un oggetto OOP con un metodo di stampa personalizzato. Quando viene invocato, può stampare vari oggetti come gli oggetti R e NR. R è raggiungibile attraverso uno o più degli slot dell'oggetto O. L'oggetto NR non è raggiungibile in questo modo: il metodo di stampa lo tira da una variabile globale o qualsiasi altra cosa:
X
|
/ \
/ \
/ \
/ \
/ \
<_________O_>
|
/ print
,-' '---.
| |
R NR
| |
/ \ / \
<___> <___>
Ora ho sviluppato un algoritmo che funziona in due passaggi. Quando la stampante viene chiamata blu per stampare X (non una chiamata ricorsiva) e la stampa circolare è abilitata, crea un nuovo contesto di stampa circolare che contiene una tabella hash per il rilevamento del ciclo. Prima di fare qualsiasi altra cosa, la funzione percorre l'intero grafico radicato in X, che raggiunge O e ricorre in R. Quindi conosce tutti gli oggetti duplicati ei cicli, e può procedere a camminare la struttura e generare la notazione circolare. Non ha conoscenza di NR. Tuttavia, quando viene chiamato il metodo di stampa dell'oggetto O e si ricorre nella stampante per stampare l'oggetto NR, la stampante completerà la tabella hash camminando sull'NR dell'oggetto in quel punto. Tutto è bello se NR è autonomo: può avere cicli interni e sottostruttura condivisa. Ciò che garantiamo è che la numerazione delle etichette per gli oggetti che si verificano in NR non sia in conflitto. Se X e R utilizzano le etichette da 1 a 21, tutte le etichette in NR iniziano da 22.
Il caso problematico è questo:
X
|
/ \
/ Y < ----------.
/ \ |
/ \ |
/ \ |
<_________O_> |
| |
/ print |
,-' '---. |
| | |
R NR |
| | |
/ \ / \ |
<___> < >--'
Supponiamo che NR contenga un backpointer nella struttura precedentemente attraversata, X o R, a qualche oggetto Y. L'algoritmo si romperà; se quell'oggetto referenziato Y non appare due o più volte nella struttura originariamente attraversata, allora non è stato notato dall'algoritmo come richiedendo l'etichetta speciale def / ref notazione. Non può essere reso correttamente come riferimento #<n>#
. (Se Y è apparso due o più volte prima dell'elaborazione di NR, l'occorrenza di esso incontrata tramite NR è solo un'altra occorrenza che sarà eseguita correttamente. Ad esempio se Y è rappresentato come etichetta 17, diventerà #17#
.) Se Y appare una volta, però, non possiamo più tornare indietro e applicare la definizione di etichetta #17=
di fronte ad essa nell'output che abbiamo già stampato; nel momento in cui chiamiamo il metodo print
che ricorre in NR
, la struttura precedente è già stata stampata.
Buon sottocaso di caso brutto:
X
|
/ \ rendered as #17=Y
/ Y < ----------.
/ \ |
/ \ |
/ \ |
<_________O_> |
| |
/ print |
,-' '---. |
| | |
R NR |
| | |
/ \ / \ |
<_Y_> <__Y>---'
Rendered as #17# Also rendered as #17#: lucky!
Se manca la seconda occorrenza di Y in R, la prima Y viene semplicemente resa come se stessa senza l'etichetta #17=
. Quando stampiamo NR, non possiamo quindi rendere Y come #17#
; quello sarebbe un riferimento di etichetta penzolante. Potremmo rendere Y come un nuovo oggetto, diciamo il numero 256: #256=(...)
che potrebbe ricorrere nuovamente in NR
, dove la seconda stampa di Y
diventa #256#
. O potremmo riconoscere la situazione e lanciare un'eccezione: un metodo di stampa ci ha lanciato una palla curva non supportata da *print-circle*
.
La domanda è: è un requisito in ANSI Common Lisp per gestire quel caso? I metodi di stampa possono acquisire assolutamente qualsiasi oggetto esistente dall'immagine, passarlo alla stampante in modo ricorsivo e deve essere gestito correttamente, indipendentemente dal fatto che non sia correlato all'oggetto O e non raggiungibile attraverso gli slot di quell'oggetto?