Cosa c'è di così difficile nei puntatori / ricorsione? [chiuso]

Ho notato per la prima volta che gli indicatori e la ricorsione erano difficili all'università. Avevo preso un paio di corsi tipici del primo anno (uno era C e Assembler, l'altro era in Scheme). Entrambi i corsi sono iniziati con centinaia di studenti, molti dei quali avevano anni di esperienza di programmazione a livello di scuola superiore (in genere BASIC e Pascal, a quei tempi). Ma non appena furono introdotte le indicazioni nel corso C, e la ricorsione fu introdotta nel corso Scheme, un numero enorme di studenti - forse anche una maggioranza - furono completamente sconcertati. Erano ragazzi che avevano scritto molto codice prima e non avevano avuto alcun problema, ma quando hanno colpito puntatori e ricorsioni, hanno anche colpito un muro in termini di capacità cognitive.

La mia ipotesi è che i puntatori e la ricorsione sono gli stessi in quanto richiedono di mantenere due livelli di astrazione nella testa allo stesso tempo. C'è qualcosa nei livelli multipli di astrazione che richiede un tipo di attitudine mentale che è molto probabile che alcune persone non avranno mai.

• Con i puntatori, i "due livelli di astrazione" sono "dati, indirizzo dei dati, indirizzo dell'indirizzo dei dati, ecc." o ciò che tradizionalmente chiamiamo "valore vs riferimento". Per lo studente non addestrato, è molto difficile vedere la differenza tra l'indirizzo di x e x stesso .
• Con la ricorsione, i "due livelli di astrazione" stanno capendo come è possibile che una funzione si autoprocluisca. A volte, un algoritmo ricorsivo è quello che la gente chiama "programmazione di un pio desiderio" ed è molto, molto innaturale pensare a un algoritmo in termini di "caso base + caso induttivo" invece dell'elenco più naturale di passaggi che segui per risolvere un problema ". Per lo studente non allenato che osserva un algoritmo ricorsivo, l'algoritmo appare fai una domanda .

Sarei anche perfettamente disposto ad accettare che sia possibile insegnare i puntatori e / o la ricorsione a chiunque ... Non ho alcuna prova in un modo o nell'altro. So che empiricamente, essere in grado di comprendere veramente questi due concetti è un ottimo predittore di abilità di programmazione generale e che nel normale corso di formazione per CS non laureati, questi due concetti rappresentano alcuni dei maggiori ostacoli.

La ricorsione non è solo "una funzione che chiama se stessa". Non apprezzerai davvero il motivo per cui la ricorsione è difficile fino a quando non ti ritrovi a disegnare tralicci per capire cosa è andato storto con il tuo parser di discendenza ricorsiva. Spesso avrai funzioni reciprocamente ricorsive (funzione A chiama la funzione B, che chiama la funzione C, che può chiamare la funzione A). Può essere molto difficile capire cosa è andato storto quando sei in N stack nel profondo di una serie di funzioni reciprocamente ricorsive.

Per quanto riguarda i puntatori, ancora una volta, il concetto dei puntatori è piuttosto semplice: una variabile che memorizza un indirizzo di memoria. Ma ancora una volta, quando qualcosa va storto con la tua complicata struttura di dati di void** puntatori che puntano a nodi diversi, vedrai perché può diventare complicato mentre ti sforzi di capire perché uno dei tuoi puntatori punta a un indirizzo spazzatura.

Java supporta i puntatori (vengono chiamati riferimenti) e supporta la ricorsione. Quindi in superficie, il suo argomento sembra inutile.

Ciò di cui sta realmente parlando è la possibilità di eseguire il debug. Un puntatore Java (err, riferimento) è garantito per puntare a un oggetto valido. Un puntatore C non lo è. E il trucco nella programmazione in C, supponendo che non si utilizzino strumenti come valgrind , è scoprire esattamente dove si è rovinato un puntatore (raramente si trova in uno stacktrace).

Il problema con i puntatori e la ricorsione non è che siano necessariamente difficili da capire, ma che siano insegnati male, specialmente rispetto a linguaggi come C o C ++ (principalmente perché le lingue stesse sono viene insegnato male). Ogni volta che sento (o leggo) qualcuno dice "un array è solo un puntatore" muoio un po 'dentro.

Allo stesso modo, ogni volta che qualcuno usa la funzione di Fibonacci per illustrare la ricorsione, voglio urlare. È un cattivo esempio perché la versione iterativa non è più difficile da scrivere e che esegue almeno altrettanto bene o meglio di quella ricorsiva, e non fornisce una vera comprensione del motivo per cui una soluzione ricorsiva sarebbe utile o desiderabile. Quicksort, tree traversal, ecc. Sono lontano esempi migliori per il perché e il come della ricorsione.

Il dover muck con i puntatori è un artefatto di lavorare in un linguaggio di programmazione che li espone. Le generazioni di programmatori di Fortran stavano costruendo liste e alberi e pile e code senza bisogno di un tipo di puntatore dedicato (o allocazione dinamica della memoria), e non ho mai sentito nessuno accusare Fortran di essere un linguaggio giocattolo.

Ci sono diverse difficoltà con i puntatori:

1. Aliasing La possibilità di modificare il valore di un oggetto utilizzando nomi / variabili diversi.
2. Non-località La possibilità di modificare un valore di oggetti in un contesto diverso da quello in cui è dichiarato (questo accade anche con argomenti passati per riferimento).
3. Mancata corrispondenza a vita La durata di un puntatore può essere diversa dalla durata dell'oggetto a cui punta e ciò può portare a riferimenti non validi (SEGFAULTS) o garbage.
4. Aritmetica puntatore . Alcuni linguaggi di programmazione consentono la manipolazione di puntatori come numeri interi e ciò significa che i puntatori possono puntare ovunque (compresi i punti più inattesi quando è presente un bug). Per usare correttamente l'aritmetica del puntatore, un programmatore deve essere consapevole delle dimensioni della memoria degli oggetti puntati, e questo è qualcosa su cui riflettere.
5. Tipi di cast La possibilità di trasmettere un puntatore da un tipo all'altro consente di sovrascrivere la memoria di un oggetto diverso da quello desiderato.

Ecco perché un programmatore deve pensare in modo più approfondito quando usa i puntatori (non conosco i due livelli di astrazione ). Questo è un esempio degli errori tipici compiuti da un novizio:

Pair* make_pair(int a, int b)
{
    Pair p;
    p.a = a;
    p.b = b;
    return &p;
}

Si noti che il codice come sopra è perfettamente ragionevole in linguaggi che non hanno un concetto di puntatori ma piuttosto uno di nomi (riferimenti), oggetti e valori, come linguaggi di programmazione funzionale e lingue con garbage collection (Java, Python).

La difficoltà con le funzioni ricorsive si verifica quando le persone senza sufficiente background matematico (dove la ricorsività è comune e richiede conoscenza) cercano di avvicinarle pensando che la funzione si comporterà in modo diverso a seconda di quante volte è stata chiamata prima . Questo problema è aggravato dal fatto che le funzioni ricorsive possono infatti essere create in modi in cui devi pensare in questo modo per capirle.

Pensa alle funzioni ricorsive con i puntatori che vengono passati in giro, come in un'implementazione procedurale di un Albero rosso-nero in cui la struttura dei dati è modificata sul posto; è qualcosa di più difficile da pensare rispetto a una controparte funzionale .

Non è menzionato nella domanda, ma l'altro problema importante con cui i principianti hanno difficoltà è concorrenza .

Come altri hanno accennato, c'è un problema aggiuntivo, non concettuale, con alcuni costrutti del linguaggio di programmazione: è che anche se comprendiamo, errori semplici e onesti con questi costrutti possono essere estremamente difficili da eseguire il debug.

I puntatori e la ricorsione sono due bestie separate e ci sono diversi motivi per cui ognuno di essi è "difficile".

In generale, i puntatori richiedono un modello mentale diverso rispetto all'assegnazione di una pura variabile. Quando ho una variabile puntatore, è proprio questo: un puntatore a un altro oggetto, l'unico dato che contiene è l'indirizzo di memoria a cui punta. Quindi, per esempio se ho un puntatore int32 e gli assegno un valore direttamente, non sto cambiando il valore dell'int, sto puntando a un nuovo indirizzo di memoria (ci sono molti trucchetti che puoi fare con questo ). Ancora più interessante è avere un puntatore a un puntatore (questo è ciò che accade quando si passa una variabile Ref come una funzione Parametro in C #, la funzione può assegnare un oggetto completamente diverso al Parametro e quel valore sarà ancora in ambito quando la funzione uscite.

La ricorsione fa un leggero salto mentale quando si apprende per la prima volta perché si sta definendo una funzione in termini di se stessa. È un concetto selvaggio quando lo si incontra per la prima volta, ma una volta afferrato l'idea, diventa una seconda natura.

Ma torniamo all'argomento in questione. L'argomento di Joel non riguarda puntatori o ricorsi in sé e per sé, ma piuttosto il fatto che gli studenti vengano rimossi ulteriormente dal modo in cui i computer funzionano davvero. Questa è la scienza in informatica. C'è una netta differenza tra imparare a programmare e imparare come funzionano i programmi. Non penso che sia tanto una questione di "l'ho imparato in questo modo, quindi tutti dovrebbero doverlo imparare in questo modo" mentre sostiene che molti programmi CS stanno diventando scuole di commercio glorificate.

Dò a P. Brian un +1, perché mi sento come se lo facesse: la ricorsione è un concetto così fondamentale che chi ha la minima difficoltà con esso dovrebbe considerare la ricerca di un lavoro a Mac Donalds, ma poi, anche lì è una ricorsione:

make a burger:
   put a cold burger on the grill
   wait
   flip
   wait
   hand the fried burger over to the service personel
   unless its end of shift: make a burger

Sicuramente, la mancanza di comprensione ha a che fare anche con le nostre scuole. Qui si dovrebbero introdurre numeri naturali come Peano, Dedekind e Frege, quindi non avremmo avuto così tante difficoltà in seguito.

Non sono d'accordo con Joel che il problema è quello di pensare a più livelli di astrazione per se, penso che sia più che i puntatori e la ricorsione siano due buoni esempi di problemi che richiedono un cambiamento nel modello mentale che le persone hanno di come programmi lavoro.

I puntatori sono, penso, il caso più semplice da illustrare. Trattare con i puntatori richiede un modello mentale di esecuzione del programma che spiega il modo in cui i programmi funzionano effettivamente con indirizzi e dati di memoria. La mia esperienza è stata che spesso i programmatori non ci hanno mai pensato prima che imparassero sui puntatori. Anche se lo conoscono in senso astratto, non l'hanno adottato nel loro modello cognitivo di come funziona un programma. Quando vengono introdotti i puntatori, è necessario un cambiamento fondamentale nel modo in cui pensano a come funziona il codice.

La ricorsione è problematica perché ci sono due blocchi concettuali da comprendere. Il primo è a livello di macchina e, proprio come i puntatori, può essere superato sviluppando una buona comprensione di come i programmi vengono effettivamente memorizzati ed eseguiti. L'altro problema con la ricorsione è, penso, che le persone hanno una tendenza naturale a provare a decostruire un problema ricorsivo in uno non ricorsivo, il che confonde la comprensione di una funzione ricorsiva come una gestalt. Questo è un problema con persone con un background matematico insufficiente, o un modello mentale che non lega la teoria matematica allo sviluppo di programmi.

Il fatto è che non penso che i puntatori e la ricorsione siano le uniche due aree problematiche per le persone bloccate in un modello mentale insufficiente. Il parallelismo sembra essere un'altra area in cui alcune persone semplicemente rimangono bloccate e hanno difficoltà ad adattare il loro modello mentale per renderlo conto, è solo che spesso in un colloquio è facile testare i puntatori e la ricorsione.

  DATA    |     CODE
          |
 pointer  |   recursion    SELF REFERENTIAL
----------+---------------------------------
 objects  |   macro        SELF MODIFYING
          |
          |

Il concetto di dati autoreferenziali e codice è alla base della definizione di puntatori e ricorsione, rispettivamente. Sfortunatamente, l'ampia esposizione ai linguaggi di programmazione imperativi ha portato gli studenti di informatica a credere che devono comprendere l'implementazione attraverso il comportamento operativo dei loro runtime quando dovrebbero fidarsi di questo mistero per l'aspetto funzionale della lingua. Sommare tutti i numeri fino a cento sembra una semplice questione di iniziare con uno e aggiungerlo al successivo nella sequenza e farlo all'indietro con l'aiuto di funzioni auto-referenziali circolari sembra perverso e persino pericoloso per molti non abituati alla sicurezza di funzioni pure. L'esperienza passata con linguaggi imperativi li ha bruciati e il desiderio di comprendere tutti gli stati intermedi è guidato dal sospetto che le variabili siano soggette a cambiamenti anche se capiscono che lo stesso nome non si riferisce alla stessa cosa quando viene invocata una funzione da dentro se stesso.

Il concetto di auto-modifica di dati e codice è alla base della definizione di oggetti (cioè smart data) e macro rispettivamente. Ne parlo perché sono ancora più difficili da capire, specialmente quando ci si aspetta una comprensione operativa del runtime da una combinazione di tutti e quattro i concetti - ad es. una macro che genera un insieme di oggetti che implementa un parser decente ricorsivo con l'aiuto di un albero di puntatori. Piuttosto che tracciare l'intera operazione dello stato del programma passo dopo passo attraverso ogni livello di astrazione in una sola volta, i programmatori imperiosi devono imparare a credere che le loro variabili siano assegnate una sola volta all'interno di funzioni pure e che invocazioni ripetute della stessa funzione pura con gli stessi argomenti producono sempre lo stesso risultato (cioè trasparenza referenziale), anche in un linguaggio che supporta anche le funzioni impure, come Java. Correre in cerchio dopo il runtime è un tentativo infruttuoso. L'astrazione dovrebbe semplificare.

Molto simile alla risposta di Anon.
A parte le difficoltà cognitive per i neofiti, sia i puntatori sia la ricorsione sono molto potenti e possono essere usati in modi criptici.

Il lato negativo di un grande potere, è che ti danno un grande potere di rovinare il tuo programma in modo sottile.
La memorizzazione di un valore falso in una variabile normale è già abbastanza grave, ma memorizzare qualcosa di falso in un puntatore può causare ogni sorta di eventi catastrofici ritardati.
E, peggio ancora, quegli effetti potrebbero cambiare quando provi a diagnosticare / eseguire il debug qual è la causa del comportamento bizzarro del programma.

Analogamente alla ricorsione. Può essere un modo molto potente per organizzare roba complicata, riempiendo l'ingannevolezza della struttura dati nascosta (stack).
Ma se qualcosa viene fatto semplicemente in modo sbagliato, può essere difficile capire cosa sta succedendo.