Lisp: stampa di strutture circolari tramite metodi di stampa definiti dall'utente: quali sono i requisiti?

4

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?

    
posta Kaz 21.10.2016 - 06:37
fonte

1 risposta

2

La risposta è: sì, ma la stampante non è necessaria per spazzare l'intera immagine, solo gli oggetti forniti alle funzioni di stampa.

Nulla impedisce alla stampante Lisp di eseguire più passate o qualsiasi altra tecnica che può permettersi.

Con più passaggi, la stampante può popolare le tabelle hash per flusso con i duplicati nel primo passaggio iniziando con un flusso null (ad esempio broadcast-stream senza flussi di componenti), interrompendo la ricorsione sui duplicati trovati con #n# , quindi stampa effettivamente sul flusso di destinazione includendo i marcatori #n= prima della prima istanza di ciascun oggetto duplicato.

Senza passaggi multipli, la stampante può creare un flusso di scopo speciale che registra la posizione di ogni oggetto stampato per inserire% marcatori #n= internamente. Una cosa che può essere semplificata con questo approccio è la contabilità circolare per-stream. Tuttavia, il conteggio delle colonne non sarebbe accurato.

Le stampanti graziose (più avanzate della semplice stampa) utilizzano solitamente una combinazione di tecniche: più passaggi, in cui lo stream utilizzato su ogni pass è uno scopo speciale con dimensioni, colonna, tabella di circolarità e tutti gli altri stati necessari, oltre a eseguendo un ultimo passaggio o scrivendo risultati intermedi nel tream di destinazione.

Questo ha solo graffiato la superficie della stampante Lisp, specialmente una bella stampante. Ti suggerisco di cercare nel web per ulteriori informazioni, ci sono un sacco di carte sull'argomento. Inizia con CLtL2 §27. Pretty Printing e XP - Un comune sistema di stampa Pretty Lisp .

Finché utilizzi write , prin1 , princ o format con ~a , ~s o ~w sul flusso stesso in print-object , la stampante considererà ogni oggetto dato per circolarità. Non importa se un dato oggetto fa parte o meno della struttura di un altro oggetto. Inoltre, la stampante non deve prendere in considerazione tutti gli oggetti in memoria, solo quelli effettivamente stampati.

In sostanza, sembra che tu abbia duplicato il comportamento della stampante Lisp per quanto riguarda i duplicati. Non affidandoti all'impegno della stampante, non puoi realmente garantire che il tuo #n= / #n# sia unico per quanto riguarda l'operazione di scrittura più avanzata che inizializza il contesto di circolarità della stampante.

    
risposta data 07.03.2017 - 02:22
fonte

Leggi altre domande sui tag