Qu'est-ce qui est si difficile avec les pointeurs / récursivité? [fermé]

20

Dans les périls des écoles de Java, Joel discute de son expérience à Penn et de la difficulté des "défauts de segmentation". Il dit

[Les erreurs de segmentation sont difficiles jusqu'à ce que vous] "prenez une profonde respiration et essayez vraiment de forcer votre esprit à travailler à deux niveaux d'abstraction différents simultanément."

Étant donné une liste de causes courantes de défauts de segmentation, je ne comprends pas comment nous devons travailler à 2 niveaux d'abstraction.

Pour une raison quelconque, Joel considère que ces concepts sont au cœur de la capacité des programmeurs à résumer. Je ne veux pas trop en supposer. Alors, qu'est-ce qui est si difficile avec les pointeurs / récursivité? Des exemples seraient bien.

P.Brian.Mackey
la source
31
Arrêtez de vous inquiéter de ce que Joel pourrait penser de vous. Si vous trouvez la récursivité facile, c'est bien. Tout le monde ne le fait pas.
FrustratedWithFormsDesigner
6
La récursivité est facile par définition (fonction qui s'appelle soi-même), mais savoir quand l'utiliser et comment le faire fonctionner est la partie difficile.
JeffO
9
Postulez pour un emploi à Fog Creek et faites-nous savoir comment cela se passe. Nous sommes tous très intéressés par votre auto promotion.
Joel Etherton
4
@ P.Brian.Mackey: Nous ne comprenons pas mal. La question ne pose vraiment rien. C'est une auto-promotion flagrante. Si vous voulez savoir ce que Joel demande au sujet des pointeurs / récursivité, demandez-lui: [email protected]
Joel Etherton
19
Dupliquer cette question ?
ozz

Réponses:

38

J'ai d'abord remarqué que les pointeurs et la récursivité étaient difficiles au collège. J'avais suivi quelques cours typiques de première année (l'un était C et assembleur, l'autre était en programme). Les deux cours ont commencé avec des centaines d'étudiants, dont beaucoup avaient des années d'expérience en programmation de niveau secondaire (généralement BASIC et Pascal, à l'époque). Mais dès que des pointeurs ont été introduits dans le cours C et que la récursion a été introduite dans le cours Scheme, un grand nombre d'étudiants - peut-être même une majorité - ont été complètement déconcertés. C'étaient des enfants qui avaient écrit BEAUCOUP de code auparavant et qui n'avaient eu aucun problème, mais lorsqu'ils frappaient des pointeurs et des récursions, ils heurtaient également un mur en termes de capacité cognitive.

Mon hypothèse est que les pointeurs et la récursivité sont les mêmes en ce sens qu'ils vous obligent à garder deux niveaux d'abstraction dans votre tête en même temps. Il y a quelque chose à propos des niveaux d'abstraction multiples qui nécessite un type d'aptitude mentale que certaines personnes n'auront jamais.

  • Avec les pointeurs, les «deux niveaux d'abstraction» sont «les données, l'adresse des données, l'adresse de l'adresse des données, etc.» ou ce que nous appelons traditionnellement «la valeur par rapport à la référence». Pour l'étudiant non formé, il est très difficile de voir la différence entre l'adresse de x et x elle-même .
  • Avec la récursivité, les "deux niveaux d'abstraction" comprennent comment il est possible pour une fonction de s'appeler. Un algorithme récursif est parfois ce que les gens appellent "programmation par vœux pieux" et il est très, très peu naturel de penser à un algorithme en termes de "cas de base + cas inductif" au lieu de la liste plus naturelle "d'étapes que vous suivez pour résoudre un problème" . " Pour l'étudiant non formé qui regarde un algorithme récursif, l'algorithme semble poser la question .

Je serais également parfaitement disposé à accepter qu'il est possible d'enseigner des pointeurs et / ou une récursivité à n'importe qui ... Je n'ai aucune preuve d'une manière ou d'une autre. Je sais qu'empiriquement, être capable de vraiment comprendre ces deux concepts est un très, très bon prédicteur de la capacité de programmation générale et que dans le cours normal de la formation de premier cycle en CS, ces deux concepts sont parmi les plus grands obstacles.

Joel Spolsky
la source
4
"très, très contre nature de penser à un algorithme en termes de" cas de base + cas inductif "" - je pense que ce n'est pas du tout naturel, c'est juste que les enfants ne sont pas formés en conséquence.
Ingo
14
si c'était naturel, vous n'auriez pas besoin d'être formé. : P
Joel Spolsky
1
Bon point :), mais n'avons-nous pas besoin de formation en mathématiques, en logique, en physique, etc. Fait intéressant, peu de programmeurs ont des problèmes avec la syntaxe des langues, mais elle est pleine de récursivité.
Ingo
1
À mon université, le premier cours a commencé avec la programmation fonctionnelle et la récursivité presque immédiatement, bien avant l'introduction de la mutation et similaires. J'ai trouvé que certains étudiants sans expérience comprenaient mieux la récursivité que ceux avec une certaine expérience. Cela dit, le sommet de la classe était composé de personnes ayant beaucoup d'expérience.
Tikhon Jelvis
2
Je pense que l'incapacité à comprendre les pointeurs et la récursivité est liée à a) le niveau global de QI et b) une mauvaise éducation mathématique.
quant_dev
23

La récursivité n'est pas seulement "une fonction qui s'appelle elle-même". Vous n'allez pas vraiment comprendre pourquoi la récursivité est difficile jusqu'à ce que vous vous retrouviez à dessiner des cadres de pile pour comprendre ce qui n'a pas fonctionné avec votre analyseur de descente récursif. Souvent, vous aurez des fonctions récurrentes (la fonction A appelle la fonction B, qui appelle la fonction C, qui peut appeler la fonction A). Il peut être très difficile de comprendre ce qui s'est mal passé lorsque vous êtes N stackframes au fond d'une série de fonctions mutuellement récursives.

En ce qui concerne les pointeurs, encore une fois, le concept de pointeurs est assez simple: une variable qui stocke une adresse mémoire. Mais encore une fois, lorsque quelque chose ne va pas avec votre structure de données compliquée de void**pointeurs qui pointent vers différents nœuds, vous verrez pourquoi cela peut devenir difficile lorsque vous avez du mal à comprendre pourquoi l'un de vos pointeurs pointe vers une adresse poubelle.

Charles Salvia
la source
1
La mise en œuvre d'un analyseur décent récursif était quand j'ai vraiment senti que j'avais un peu de prise sur la récursivité. Les pointeurs sont faciles à comprendre à un niveau élevé comme vous l'avez dit; ce n'est que lorsque vous entrez dans les écrous et les boulons des implémentations traitant des pointeurs que vous voyez pourquoi ils sont compliqués.
Chris
La récursion mutuelle entre de nombreuses fonctions est essentiellement la même que goto.
starblue
2
@starblue, pas vraiment - puisque chaque stackframe crée de nouvelles instances de variables locales.
Charles Salvia
Vous avez raison, seule la récursivité de la queue est la même que goto.
starblue
3
@wnoise int a() { return b(); }peut être récursif, mais cela dépend de la définition de b. Donc, ce n'est pas aussi simple qu'il y paraît ...
alternative
14

Java prend en charge les pointeurs (ils sont appelés références) et il prend en charge la récursivité. Donc, en surface, son argument semble inutile.

Ce dont il parle vraiment, c'est de la capacité de débogage. Un pointeur Java (err, référence) est garanti pour pointer vers un objet valide. Le pointeur AC ne l'est pas. Et l'astuce dans la programmation C, en supposant que vous n'utilisez pas d'outils comme valgrind , est de savoir exactement où vous avez foiré un pointeur (c'est rarement au point trouvé dans un stacktrace).

Anon
la source
5
Les pointeurs en soi sont un détail. Utiliser des références en Java n'est pas plus compliqué que d'utiliser des variables locales en C. Même les mélanger comme le font les implémentations Lisp (un atome peut être un entier de taille limitée, ou un caractère, ou un pointeur) n'est pas difficile. Cela devient plus difficile lorsque le langage permet au même type de données d'être local ou référencé, avec une syntaxe différente, et vraiment poilu lorsque le langage permet l'arithmétique des pointeurs.
David Thornley
@David - euh, qu'est-ce que cela a à voir avec ma réponse?
Anon
1
Votre commentaire sur les pointeurs supportant Java.
David Thornley
"où vous avez foiré un pointeur (c'est rarement au point trouvé dans un stacktrace)." Si vous avez la chance d'obtenir un stacktrace.
Omega Centauri
5
Je suis d'accord avec David Thornley; Java ne prend pas en charge les pointeurs, sauf si je peux faire un pointeur vers un pointeur vers un pointeur vers un pointeur vers un int. Lequel peut-être je suppose que je pourrais en faisant comme 4-5 classes qui référencent chacune autre chose, mais est-ce vraiment des pointeurs ou est-ce une mauvaise solution?
alternative
12

Le problème avec les pointeurs et la récursivité n'est pas qu'ils sont nécessairement difficiles à comprendre, mais qu'ils sont mal enseignés, en particulier en ce qui concerne les langages comme C ou C ++ (principalement parce que les langages eux-mêmes sont mal enseignés). Chaque fois que j'entends (ou lis) quelqu'un dire "un tableau n'est qu'un pointeur", je meurs un peu à l'intérieur.

De même, chaque fois que quelqu'un utilise la fonction Fibonacci pour illustrer la récursivité, je veux crier. C'est un mauvais exemple car la version itérative n'est pas plus difficile à écrire et elle fonctionne au moins aussi bien ou mieux que la version récursive, et elle ne vous donne aucune idée réelle de la raison pour laquelle une solution récursive serait utile ou souhaitable. Le tri rapide, la traversée d'arbre, etc., sont de bien meilleurs exemples du pourquoi et du comment de la récursivité.

Devoir se moquer des pointeurs est un artefact de travailler dans un langage de programmation qui les expose. Des générations de programmeurs Fortran construisaient des listes et des arbres et des piles et des files d'attente sans avoir besoin d'un type de pointeur dédié (ou d'une allocation de mémoire dynamique), et je n'ai jamais entendu personne accuser Fortran d'être un langage de jouet.

John Bode
la source
Je suis d'accord, j'avais eu des années / décennies de Fortran avant de voir de vrais pointeurs, alors j'avais déjà utilisé ma propre façon de faire la même chose, avant d'avoir eu la chance de laisser le lanquage / compilateur le faire pour moi. Je pense également que la syntaxe C concernant les pointeurs / adresses est très déroutante, même si le concept d'une valeur, stockée à une adresse est très simple.
Omega Centauri
si vous avez un lien vers Quicksort implémenté dans Fortran IV, j'aimerais le voir. Je ne dis pas que cela ne peut pas être fait - en fait, je l'ai implémenté dans BASIC il y a environ 30 ans - mais je serais intéressé de le voir.
Anon
Je n'ai jamais travaillé dans Fortran IV, mais j'ai implémenté des algorithmes récursifs dans l'implémentation VAX / VMS de Fortran 77 (il y avait un crochet pour vous permettre d'enregistrer la cible d'un goto en tant que type spécial de variable, afin que vous puissiez écrire GOTO target) . Je pense que nous avons dû créer nos propres piles d'exécution, cependant. Cela fait assez longtemps que je ne me souviens plus des détails.
John Bode
8

Il y a plusieurs difficultés avec les pointeurs:

  1. Aliasing La possibilité de changer la valeur d'un objet en utilisant différents noms / variables.
  2. Non-localité La possibilité de changer la valeur d'un objet dans un contexte différent de celui dans lequel il est déclaré (cela se produit également avec des arguments passés par référence).
  3. Incohérence de durée de vie La durée de vie d'un pointeur peut être différente de la durée de vie de l'objet vers lequel il pointe, ce qui peut entraîner des références non valides (SEGFAULTS) ou des ordures.
  4. Arithmétique des pointeurs . Certains langages de programmation permettent la manipulation de pointeurs sous forme d'entiers, ce qui signifie que les pointeurs peuvent pointer n'importe où (y compris les endroits les plus inattendus lorsqu'un bogue est présent). Pour utiliser correctement l'arithmétique des pointeurs, un programmeur doit être conscient de la taille de la mémoire des objets pointés, et c'est quelque chose de plus à penser.
  5. Conversion de type La possibilité de convertir un pointeur d'un type à un autre permet d'écraser la mémoire d'un objet différent de celui prévu.

C'est pourquoi un programmeur doit réfléchir plus à fond lorsqu'il utilise des pointeurs (je ne connais pas les deux niveaux d'abstraction ). Voici un exemple des erreurs typiques commises par un novice:

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

Notez que le code comme ci-dessus est parfaitement raisonnable dans les langages qui n'ont pas de concept de pointeurs mais plutôt de noms (références), d'objets et de valeurs, comme le font les langages de programmation fonctionnels et les langages avec garbage collection (Java, Python). .

La difficulté avec les fonctions récursives se produit lorsque des personnes sans formation mathématique suffisante (où la récursivité est courante et requiert des connaissances) essaient de les approcher en pensant que la fonction se comportera différemment selon le nombre de fois où elle a été appelée auparavant . Ce problème est aggravé parce que les fonctions récursives peuvent en effet être créées de manière à ce que vous ayez à penser de cette façon pour les comprendre.

Pensez à des fonctions récursives avec des pointeurs transmis, comme dans une implémentation procédurale d'un arbre rouge-noir dans lequel la structure de données est modifiée sur place; c'est quelque chose de plus difficile à penser qu'une contrepartie fonctionnelle .

Ce n'est pas mentionné dans la question, mais l'autre problème important avec lequel les novices ont des difficultés est la concurrence .

Comme d'autres l'ont mentionné, il existe un problème supplémentaire, non conceptuel, avec certaines constructions de langage de programmation: c'est que même si nous comprenons, des erreurs simples et honnêtes avec ces constructions peuvent être extrêmement difficiles à déboguer.

Apalala
la source
L'utilisation de cette fonction renvoie un pointeur valide mais la variable est dans une portée supérieure à la portée qui a appelé la fonction, de sorte que le pointeur pourrait (supposer) être invalidé lorsque malloc est utilisé.
plié à droite
4
@Radek S: Non, ce ne sera pas le cas. Il renverra un pointeur invalide qui, dans certains environnements, fonctionnera pendant un certain temps jusqu'à ce que quelque chose d'autre le remplace. (En pratique, ce sera la pile, pas le tas. malloc()
N'est
1
@Radeck Dans l'exemple de fonction, le pointeur pointe vers la mémoire que le langage de programmation (C dans ce cas) garantit sera libérée une fois la fonction revenue. Ainsi, le pointeur renvoyé pointe vers les ordures . Les langages avec garbage collection gardent l'objet vivant tant qu'il est référencé dans n'importe quel contexte.
Apalala
Soit dit en passant, Rust a des pointeurs mais sans ces problèmes. (quand il n'est pas dans un contexte dangereux)
Sarge Borsch
2

Les pointeurs et la récursivité sont deux bêtes distinctes et il y a différentes raisons qui qualifient chacune comme étant "difficile".

En général, les pointeurs nécessitent un modèle mental différent de l'affectation de variable pure. Lorsque j'ai une variable de pointeur, c'est juste cela: un pointeur vers un autre objet, les seules données qu'il contient sont l'adresse mémoire vers laquelle il pointe. Donc, par exemple, si j'ai un pointeur int32 et que je lui attribue une valeur directement, je ne change pas la valeur de l'int, je pointe vers une nouvelle adresse mémoire (il y a beaucoup d'astuces intéressantes que vous pouvez faire avec cela ). Encore plus intéressant est d'avoir un pointeur sur un pointeur (c'est ce qui se produit lorsque vous passez une variable Ref en tant que paramètre de fonction en C #, la fonction peut affecter un objet entièrement différent au paramètre et cette valeur sera toujours dans la portée lorsque la fonction sort.

La récursion prend un léger bond mental lors de la première apprentissage parce que vous définissez une fonction en termes d'elle-même. C'est un concept sauvage lorsque vous le rencontrez pour la première fois, mais une fois que vous avez saisi l'idée, cela devient une seconde nature.

Mais revenons au sujet en question. L'argument de Joel ne concerne pas les pointeurs ou la récursivité en eux-mêmes, mais plutôt le fait que les étudiants sont davantage éloignés du fonctionnement réel des ordinateurs. C'est la science en informatique. Il y a une différence nette entre apprendre à programmer et apprendre comment fonctionnent les programmes. Je ne pense pas que ce soit tellement une question de "je l'ai appris de cette façon, donc tout le monde devrait avoir à l'apprendre de cette façon", comme lui en faisant valoir que de nombreux programmes de CS deviennent des écoles de métiers glorifiées.

Michael Brown
la source
1

Je donne à P. Brian un +1, car j'ai l'impression que c'est le cas: la récursivité est un concept si fondamental que celui qui a les moindres difficultés devrait mieux envisager de chercher un emploi chez mac donalds, mais alors, même il y a récursivité:

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

Certes, le manque de compréhension a aussi à voir avec nos écoles. Ici, on devrait introduire des nombres naturels comme Peano, Dedekind et Frege l'ont fait, donc nous n'aurions pas autant de difficultés plus tard.

Ingo
la source
6
C'est la récidive de la queue, qui est sans doute en boucle.
Michael K
6
Désolé, pour moi, la boucle est sans doute une récursion de queue :)
Ingo
3
@Ingo: :) Fanatique fonctionnel!
Michael K
1
@Michael - hehe, en effet !, mais je pense que l'on peut faire valoir que la récursivité est le concept le plus fondamental.
Ingo
@Ingo: Vous pourriez, en effet (votre exemple le démontre bien). Cependant, pour une raison quelconque, les humains ont du mal avec cela dans la programmation - nous semblons vouloir cet extra goto toppour une raison IME.
Michael K
1

Je ne suis pas d'accord avec Joel que le problème est de penser à plusieurs niveaux d'abstraction en soi, je pense que c'est plus que les pointeurs et la récursivité sont deux bons exemples de problèmes qui nécessitent un changement dans le modèle mental que les gens ont de la façon dont les programmes fonctionnent.

Les pointeurs sont, je pense, le cas le plus simple à illustrer. La gestion des pointeurs nécessite un modèle mental d'exécution de programme qui tient compte de la façon dont les programmes fonctionnent réellement avec les adresses et les données de la mémoire. D'après mon expérience, il arrive souvent que les programmeurs n'y aient même pas pensé avant d'en savoir plus sur les pointeurs. Même s'ils le connaissent dans un sens abstrait, ils ne l'ont pas adopté dans leur modèle cognitif du fonctionnement d'un programme. Lorsque des pointeurs sont introduits, cela nécessite un changement fondamental dans leur façon de penser le fonctionnement du code.

La récursivité est problématique car il y a deux blocs conceptuels à la compréhension. Le premier est au niveau de la machine, et tout comme les pointeurs, il peut être surmonté en développant une bonne compréhension de la façon dont les programmes sont réellement stockés et exécutés. L'autre problème avec la récursivité est, je pense, que les gens ont une tendance naturelle à essayer de déconstruire un problème récursif en un problème non récursif, ce qui brouille la compréhension d'une fonction récursive en tant que gestalt. C'est soit un problème avec des personnes ayant une formation mathématique insuffisante, soit un modèle mental qui ne lie pas la théorie mathématique au développement de programmes.

Le fait est que je ne pense pas que les pointeurs et la récursivité soient les deux seuls domaines problématiques pour les personnes coincées dans un modèle mental insuffisant. Le parallélisme semble être un autre domaine dans lequel certaines personnes se retrouvent simplement coincées et ont du mal à adapter leur modèle mental pour en tenir compte, c'est juste que souvent les pointeurs de temps et la récursivité sont faciles à tester dans une interview.

Cercerilla
la source
1
  DATA    |     CODE
          |
 pointer  |   recursion    SELF REFERENTIAL
----------+---------------------------------
 objects  |   macro        SELF MODIFYING
          |
          |

Le concept de données et de code auto-référentiels sous-tend respectivement la définition des pointeurs et de la récursivité. Malheureusement, une exposition généralisée aux langages de programmation impératifs a conduit les étudiants en informatique à croire qu'ils doivent comprendre l'implémentation via le comportement opérationnel de leurs runtimes quand ils doivent faire confiance à ce mystère pour l'aspect fonctionnel du langage. La somme de tous les nombres jusqu'à une centaine semble être une simple question de commencer par un et de l'ajouter au suivant dans la séquence et de le faire à l'envers à l'aide de fonctions auto-référentielles circulaires semble perverse et même dangereuse pour beaucoup non habitués à la sécurité de fonctions pures.

Le concept de données et de code auto-modifiables sous-tend respectivement la définition des objets (c'est-à-dire les données intelligentes) et des macros. Je les mentionne car ils sont encore plus difficiles à comprendre, en particulier lorsqu'une compréhension opérationnelle du runtime est attendue d'une combinaison des quatre concepts - par exemple, une macro générant un ensemble d'objets qui implémente un analyseur décent récursif à l'aide d'un arbre de pointeurs . Plutôt que de suivre pas à pas l'intégralité du fonctionnement de l'état du programme à travers chaque couche d'abstraction, les programmeurs doivent impérativement apprendre à faire en sorte que leurs variables ne soient affectées qu'une seule fois dans des fonctions pures et que les invocations répétées de la même fonction pure avec les mêmes arguments donnent toujours le même résultat (c'est-à-dire la transparence référentielle), même dans un langage qui prend également en charge les fonctions impures, comme Java. Courir en rond après l'exécution est une entreprise infructueuse. L'abstraction devrait simplifier.

Peu compétitif
la source
-1

Très similaire à la réponse d'Anon.
Mis à part les difficultés cognitives pour les débutants, les pointeurs et la récursivité sont très puissants et peuvent être utilisés de manière cryptique.

L'inconvénient d'une grande puissance, c'est qu'ils vous donnent une grande puissance pour bousiller votre programme de manière subtile.
Le stockage d'une valeur fausse dans une variable normale est déjà assez mauvais, mais le stockage de quelque chose de faux dans un pointeur peut provoquer toutes sortes de choses catastrophiques retardées.
Et pire encore, ces effets peuvent changer à mesure que vous essayez de diagnostiquer / déboguer la cause du comportement bizarre du programme. Mais, si quelque chose est mal fait subtilement, il peut être difficile de comprendre ce qui se passe.

De même avec la récursivité. Cela peut être un moyen très puissant d'organiser des trucs délicats - en mettant le truc dans la structure de données cachée (pile).

Omega Centauri
la source