La philosophie de la programmation

Pensée logique === bon logiciel

La programmation est la nouvelle alphabétisation. Mais comment écrire de bons programmes? Voici les questions récurrentes que nous devons résoudre:

  • Comment trouver des solutions algorithmiques à un problème?
  • Alors, comment savons-nous que la solution fonctionne réellement?
  • Même si nous sommes sûrs que cela fonctionne, comment dire à l'ordinateur de l'exécuter?

Fait amusant - si vous avez du mal à résoudre l'une de ces questions, vous faites en fait de la philosophie.

Pour voir pourquoi, examinons quelques similitudes intéressantes entre la programmation et le raisonnement philosophique.

Le premier principe: il faut bien réfléchir.

Les ordinateurs ne font rien de plus intelligent que nous ne pouvons le faire - la différence est qu'ils le font plus rapidement.

Mais ils ne peuvent pas résoudre un problème réel tel que «comment puis-je me rendre à mon bureau depuis la maison?»

Une méthode efficace peut (en principe) être mise en œuvre par un être humain sans l'aide d'aucun mécanisme autre que le papier et le crayon. - The Church-Turing Thesis

Le mérite de la programmation réside toujours dans la partie raisonnement. Autrement dit, traduire un problème du monde réel en instructions simples qu'un ordinateur peut exécuter.

Bien sûr, différents langages de programmation ont différents niveaux d'abstractions sémantiques. Un programme Python peut être plus court que son homologue C. Mais cela ne fait que changer la quantité de traductions. Nous ne pouvons pas nous débarrasser du travail de traduction. Mais nous laisserons cette discussion pour plus tard.

Flux de raisonnement d'un programmeur

Nous examinons maintenant une description du problème. Nous pouvons d'abord rechercher des exemples d'entrée-sortie à petite échelle pour comprendre le problème:

Induction. Nous avons besoin d'un algorithme capable de gérer de tels exemples. Maintenant, vous faites l'initiation: généraliser les principes de l'expérience.

Déduction. Comment savoir si cela fonctionne pour d'autres entrées inconnues? Nous faisons une déduction pour prouver l'exactitude de notre algorithme.

Ontologie . Nous devons conserver les données dans la mémoire de l'ordinateur. Le but est de les rendre efficaces pour les ordinateurs à traiter. En d'autres termes, quelle structure de données peut le mieux capturer le flux dynamique de mes informations?

Induction à nouveau . Vient ensuite la toute dernière étape: le débogage. Nous induisons la partie boguée du programme d'analyser les sorties inattendues.

Un exemple

Examinons maintenant le processus ci-dessus en suivant cet exemple réel: trouver le chemin le plus court du sommet A au sommet E.

Pour les problèmes à petite échelle, nous pouvons les résoudre par instinct. Par exemple, il est très simple pour nous de reconnaître la solution ACE simplement en regardant.

Mais qu'en est-il des topologies plus complexes? Qu'en est-il des différents poids de bord?

Nous avons besoin de l'aide des ordinateurs. Pourtant, il n'est pas simple de dire à un ordinateur ce qu'il doit faire. Il y a un fossé entre la façon dont les humains pensent et le fonctionnement d'un ordinateur.

Le processus

1. Généraliser les principes de l'expérience: algorithmes

Pour dire à un ordinateur ce qu'il doit faire, nous devons d'abord proposer une procédure algorithmique.

Les stratégies gourmandes sont une manière naturelle de procéder. C'est-à-dire en partant du sommet source A et en allant tout le long du chemin le plus court connu. Continuez à explorer de nouveaux sommets jusqu'à ce que nous atteignions la destination E. Et en effet, cette approche satisfait notre exemple.

L'intuition est que, le long du chemin le plus court vers une destination, chaque nœud intermédiaire est également visité sur le chemin le plus court. (Bien sûr, cette intuition suppose que toutes les arêtes ont des poids positifs. Cela peut ne pas être vrai, selon les applications. Nous en discuterons en détail plus tard).

Voici donc la procédure algorithmique:

  1. Quelques configurations: (1) tenez compte des sommets que nous avons visités: un ensemble ( visited), (2) mémorisez les distances les plus courtes connues à chaque sommet qui n'utilisent que les sommets découverts : un autre ensemble distance(u). La distance de chaque sommet est initialement l'infini, sauf que le sommet source est 0.
  2. Maintenant, nous commençons à explorer: d'abord nous visitons le sommet qui a le chemin le plus court connu jusqu'à présent, disons que c'est u. (Au départ, ce serait le sommet source).
  3. Lorsque unous nous tenons au sommet , nous regardons autour des bords sortants. Chaque arête, par exemple (u,v), nous donne un chemin vers le sommet vqui utilise le sommet ucomme la dernière étape, mais une seule. Si l'un d'entre eux est en effet un chemin plus court vers v, ou le premier chemin que nous avons trouvé v, hourra nous pouvons mettre à jour notre ensemble de chemins les plus courts maintenant. Sinon, ignorez et continuez.
  4. Nous en avons terminé avec le vertex u, nous l'ajoutons donc à notre visitedensemble.
  5. Revenez à l'étape 2, continuez à explorer jusqu'à ce que nous ayons visité tous les sommets.

distancepeut maintenant nous indiquer les distances globales les plus courtes, car il est utilisé pour garder les distances les plus courtes en utilisant uniquement les nœuds visités. Et tous les sommets sont visités lorsque l'algorithme se termine.

Nous venons de réinventer l'algorithme de Dijkstra. Bien sûr, il existe de nombreux autres algorithmes pour trouver le chemin le plus court. Mais le fait est que nous avons besoin d'une procédure algorithmique pour résoudre le problème.

2. Valider les principes généraux par déduction

Comment s'assurer que les principes de l'algorithme sont corrects? Nous pouvons soit augmenter notre confiance en testant le principe par rapport à plus d'exemples d'entrée, soit, plus efficacement, nous pouvons trouver une preuve mathématique rigoureuse.

Comme une proposition a priori en philosophie, l'exactitude d'un algorithme est indépendante de son exécution. En d'autres termes, les tests ne peuvent garantir l'exactitude des algorithmes. Nous devons le prouver.

Voici le flux de base de la preuve:

1. Pour tous les sommets visités, nous trouvons les chemins les plus courts.

2. La destination est visitée.

3. Par conséquent, nous trouvons le chemin le plus court vers la destination.

Ne semblent-ils pas un peu familiers? Comme ça:

1. Tous les hommes sont mortels.

2. Socrate est un homme.

3. Par conséquent, Socrate est mortel.

En fait, il s'agit du syllogisme, une forme classique de raisonnement déductif. C'est à peu près ce que font les logiciens.

Autre fait historique intéressant: le concept formel de calcul a été proposé pour la première fois par les logiciens dans les années 1930. Ils avaient besoin de savoir si certains problèmes logiques sont réellement résolubles (pour éviter de perdre leur temps à résoudre des problèmes insolubles). Pour répondre à cela, ils proposent la notion de calculabilité.

Plus tard en 1936, Alonzo Church et Alan Turing ont développé la définition formelle de la calculabilité, indépendamment, en même temps. Cet article donne une revue historique du calcul.

L'exactitude de la conclusion dépend des deux premières prémisses. Dans notre preuve, la deuxième prémisse est triviale, puisque notre algorithme visite littéralement tous les nœuds. Pourtant, la preuve de la première prémisse, que nous trouvons le chemin le plus court au moment où nous visitons un nœud, nécessite du travail.

L'induction mathématique peut aider. C'est en fait l'une des techniques les plus utiles pour prouver l'exactitude de nombreux autres algorithmes.

Le flux général est le suivant. Premièrement, si un algorithme fonctionne en entrée 0, et deuxièmement, si le fait qu'il fonctionne en entrée nimplique qu'il fonctionne également en entrée n+1 , alors il fonctionne pour toutes les entrées supérieures ou égales à 0. À ce stade, vous êtes en mesure de garantir l'exactitude de votre algorithme.

Pour plus de simplicité, je vous renvoie à cette note de cours pour la preuve complète de cet algorithme de recherche de chemin.

Notez qu'il ne faut pas confondre induction mathématique et induction philosophique. Selon la définition philosophique, l'induction mathématique est un processus de raisonnement déductif, car sa justesse est contenue en elle-même, sans aucune observation externe.

La leçon est la suivante: lorsque nous proposons un algorithme, il doit être capable de gérer tous les cas d'exécution possibles.

En pratique, passer par la preuve mathématique rigoureuse peut ne pas être la stratégie la plus efficace. Mais au moins, nous voulons considérer autant de cas d'exécution que possible, en particulier les cas contradictoires. Cette pratique améliorerait la robustesse de notre code.

Vous avez peut-être remarqué que, dans notre exemple d'algorithme de recherche de chemin, cela ne fonctionne pas si le poids du bord est négatif. Vous pouvez trouver la raison dans cette note de cours. Pour gérer un graphique à poids négatif, vous pouvez utiliser l'algorithme Bellman-Ford.

3. Le problème de l'ontologie: la structure des données

Jusqu'à présent, nous nous sommes convaincus que nous avons un algorithme correct. Mais ce n'est que la moitié de la bataille.

La question suivante est: comment alimenter les informations dans les ordinateurs? Les humains aiment les informations visualisées, comme les graphiques ou les histogrammes. Mais les ordinateurs d'aujourd'hui ne traitent que des bits binaires.

Nous devons créer une structure de données contenant les informations essentielles. Et il devrait être efficace pour un programme de traiter en même temps.

Continuons sur notre exemple de recherche de chemin. Un chemin est une liste ordonnée. Mais c'est irritant à gérer, comparé à un entier. Notez que dans notre algorithme, nous devons trouver le chemin le plus court de notre ensemble de chemins découverts. Et puis itérer jusqu'à sa fin. On dirait que nous devons consacrer un tableau ou une mémoire pour stocker chaque chemin.

Pouvons-nous faire mieux? Notez que dans un chemin valide, les apparitions consécutives d'éléments doivent correspondre à une arête du graphique. Mais, nous avons déjà les informations de bord et elles sont les mêmes pour tous les chemins. Pourquoi ne pouvons-nous pas nous débarrasser de ces informations redondantes?

Eh bien, nous pouvons nous débarrasser de la liste. Il s'avère que pour obtenir le chemin le plus court, l'étape intermédiaire consiste à déterminer quel est le prochain saut à parcourir. Tout ce dont nous avons besoin pour récupérer le chemin le plus court de la source A à n'importe quel nœud cible est juste le graphe lui-même, et la distance la plus courte de A à chaque nœud.

Une représentation visuelle est dans l'image ci-dessus. Cette représentation est efficace en mémoire. Le traitement du programme est également plus efficace.

C'est ainsi qu'il construit le chemin le plus court en utilisant uniquement le vecteur de distance. Commencez par le sommet de destination et un chemin vide. Recherchez les sommets intermédiaires à travers les arêtes entrantes. Choisissez celui avec la valeur la plus basse distance. Ajoutez-le à la tête du chemin. Répétez jusqu'à ce que nous atteignions la source. Cette astuce a en fait une notation formelle, appelée back-tracking.

Les philosophes recherchent la vérité éternelle. Et les programmeurs veulent découvrir la structure de données précise qui capture le mieux la dynamique de l'information. Comme vous le voyez dans l'exemple de recherche de chemin, tout ce dont il a besoin pour donner un chemin le plus court est juste un vecteur, vous indiquant les distances les plus courtes à chaque sommet. Cela est vrai pour n'importe quel graphique, quel que soit le nombre de sommets ou d'arêtes.

4. Proposition a posteriori: débogage

La plupart des programmeurs ont traversé ce raisonnement des tonnes de fois. Je parie que c'est l'une des parties les plus difficiles et les plus chronophages de toute tâche de programmation.

Par exemple, les erreurs de segmentation dans les programmes C sont souvent causées par des références de pointeur nulles. J'ai appris cela après avoir traité des tonnes de défauts de segmentation C / C ++. Bien sûr, il existe des cas plus subtils liés aux habitudes de programmation personnelles.

L'exemple suivant est une erreur de syntaxe commise par un programmeur. La condition if aurait dû l'être is_float==1, mais le programmeur a confondu l'opérateur d'égalité logique avec un opérateur ==d'évaluation =. Cela passera toujours la vérification du compilateur, car la syntaxe est correcte.

if (is_float = 1) { // do something}

Il s'agit d'un processus de raisonnement inductif. Votre diagnostic de débogage n'a de sens que si vous avez observé suffisamment d'exécutions de programme.

C'est là que la valeur de la pratique entre en jeu. Peu importe le type de techniques que vous apprenez, vous devez rassembler suffisamment de données pratiques. Sinon, vous n'auriez pas assez d'expérience pour conduire l'induction.

Vous devriez garder un œil sur les modèles récurrents dans vos codes de buggy. Lorsque vous trouvez un bogue, le corriger ne suffit pas. Vous avez besoin d'une analyse de cause à effet supplémentaire sur votre propre pratique de programmation. Posez-vous la question: est-ce que cela fait partie de mes habitudes de programmation particulièrement vulnérable à ce type de bogue?

Alors pourquoi est-ce important?

La programmation ne consiste pas seulement à écrire du code, c'est une manière systématique de raisonner. Parce que le code, ou les instructions, n'est qu'un moyen pour atteindre une fin. Avec le développement de la technique de synthèse de programme, vous ne pouvez même pas vous soucier d'écrire du code et de vous déboguer. Tout ce qui compte, c'est de savoir si vous pouvez dire à l'ordinateur ce qu'il doit faire.

En tant que première étape vers l'amélioration de vos compétences en programmation, cet article révèle le modèle de raisonnement sous-jacent que nous pouvons même ne pas reconnaître lorsque nous programmions. La plupart d'entre nous comptent sur la réflexion subconsciente et automatique pour terminer la plupart de nos tâches quotidiennes. Mais d'où vient l'amélioration? Cela vient d'abord de la constatation d'une erreur ou d'erreurs que nous avons commises dans notre processus de raisonnement.

Pour des conseils pratiques, je vous recommande cet article sur la façon de penser comme un programmeur, et ce livre sur le même sujet mais avec plus de détails.

Références

  • Calcul, questions philosophiques sur. Matthias Scheutz.
  • La thèse de Church-Turing.
  • Pensez comme un programmeur: une introduction à la résolution créative de problèmes. V. Anton Spraul.