Le rêve d'une programmation déclarative [clôturé]

Pourquoi le rêve d'une programmation déclarative ne s'est-il pas réalisé? Quels obstacles concrets entravent-ils? Pour un exemple simple, pourquoi ne puis-je pas dire

sort(A) is defined by sort(A) in perm(A) && asc(sort(A))

et en extraire automatiquement un algorithme de tri. permsignifie permutations et ascsignifie ascendant.

Il y a de très bonnes réponses. Je vais essayer de contribuer à la discussion.

Au sujet de la programmation déclarative et logique dans Prolog, il y a le grand livre "The Craft of Prolog" de Richard O'Keefe . Il s'agit d'écrire des programmes efficaces en utilisant un langage de programmation qui vous permet d'écrire des programmes très inefficaces. Dans cet ouvrage, tout en discutant des implémentations efficaces de plusieurs algorithmes (dans le chapitre "Méthodes de programmation"), l'auteur adopte l'approche suivante:

• définir le problème en anglais
• écrire une solution de travail aussi déclarative que possible; généralement, cela signifie à peu près exactement ce que vous avez dans votre question, juste corriger Prolog
• à partir de là, prenez des mesures pour affiner la mise en œuvre pour la rendre plus rapide

L'observation la plus éclairante (pour moi) que j'ai pu faire en travaillant à travers ceux-ci:

Oui, la version finale de l'implémentation est beaucoup plus efficace que la spécification "déclarative" avec laquelle l'auteur a commencé. Il est toujours très déclaratif, succinct et facile à comprendre. Ce qui s'est passé entre les deux, c'est que la solution finale capture les propriétés du problème auquel la solution initiale était inconsciente.

En d'autres termes, lors de la mise en œuvre d'une solution, nous avons utilisé autant que possible nos connaissances sur le problème. Comparer:

Trouver une permutation d'une liste telle que tous les éléments sont dans l'ordre croissant

à:

La fusion de deux listes triées entraînera une liste triée. Puisqu'il peut y avoir des sous-listes qui sont déjà triées, utilisez-les comme point de départ, au lieu de sous-listes de longueur 1.

Petit bémol: une définition comme celle que vous avez donnée est séduisante car elle est très générale. Cependant, je ne peux pas échapper au sentiment qu'il ignore délibérément le fait que les permutations sont, bien, un problème combinatoire. C'est quelque chose que nous savons déjà ! Ce n'est pas une critique, juste une observation.

Quant à la vraie question: comment avancer? Eh bien, une façon consiste à fournir autant de connaissances sur le problème que nous déclarons à l'ordinateur.

La meilleure tentative que je connaisse pour vraiment résoudre le problème est présentée dans les livres co-écrits par Alexander Stepanov, "Elements of Programming" et "From Mathematics to Generic Programming" . Je ne suis malheureusement pas à la hauteur de tout résumer (ou même de bien comprendre) tout dans ces livres. Cependant, l'approche consiste à définir des algorithmes de bibliothèque et des structures de données efficaces (voire optimaux), sous réserve que toutes les propriétés pertinentes de l'entrée soient connues à l'avance. Le résultat final est:

• Chaque transformation bien définie est un raffinement des contraintes déjà en place (les propriétés connues);
• Nous laissons l'ordinateur décider de la transformation optimale en fonction des contraintes existantes.

Quant à savoir pourquoi cela ne s'est pas encore produit, eh bien, l'informatique est un domaine très jeune, et nous devons encore vraiment apprécier la nouveauté de la plupart d'entre eux.

PS

Pour vous donner un avant-goût de ce que je veux dire par "affiner l'implémentation": prenez par exemple le problème facile d'obtenir le dernier élément d'une liste, dans Prolog. La solution déclarative canonique est de dire:

last(List, Last) :-
    append(_, [Last], List).

Ici, la signification déclarative de append/3est:

List1AndList2est la concaténation List1etList2

Étant donné que dans le deuxième argument, append/3nous avons une liste avec un seul élément et que le premier argument est ignoré (le trait de soulignement), nous obtenons un fractionnement de la liste d'origine qui supprime le début de la liste ( List1dans le contexte de append/3) et exige que le dos ( List2dans le contexte de append/3) est en effet une liste avec un seul élément: c'est donc le dernier élément.

La mise en œuvre réelle fournie par SWI-Prolog , cependant, dit:

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

C'est encore bien déclaratif. Lisez de haut en bas:

Le dernier élément d'une liste n'a de sens que pour une liste d'au moins un élément. Le dernier élément pour une paire de queue et la tête d'une liste est donc: la tête, quand la queue est vide, ou la dernière de la queue non vide.

La raison pour laquelle cette implémentation est fournie est de contourner les problèmes pratiques entourant le modèle d'exécution de Prolog. Idéalement, cela ne devrait pas faire de différence quant à l'implémentation utilisée. De même, nous aurions pu dire:

last(List, Last) :-
    reverse(List, [Last|_]).

Le dernier élément d'une liste est le premier élément de la liste inversée.

Si vous souhaitez obtenir un remplissage de discussions non concluantes sur ce qui est bon, déclaratif Prolog, passez simplement par certaines des questions et réponses dans la balise Prolog sur Stack Overflow .

Les langues logiques le font déjà. Vous pouvez définir le tri de la même manière que vous le faites.

Le principal problème est la performance. Les ordinateurs peuvent être excellents pour calculer beaucoup de choses, mais ils sont intrinsèquement stupides. Chaque décision «intelligente» qu'un ordinateur pouvait prendre était programmée par un programmeur. Et cette décision est généralement décrite non pas par l'apparence du résultat final, mais par la façon d'atteindre, étape par étape, ce résultat final.

Imaginez l'histoire d'un Golem . Si vous essayez de lui donner un ordre abstrait, alors au mieux, il le fera de manière inefficace et au pire, se blessera, vous ou quelqu'un d'autre. Mais si vous décrivez ce que vous voulez dans les moindres détails, vous êtes assuré que la tâche sera accomplie de manière efficace et efficiente.

C'est le travail du programmeur de décider du niveau d'abstraction à utiliser. Pour l'application que vous créez, allez-vous aller de haut niveau et la décrire de manière abstraite et prendre les performances ou aller bas et sale, y passer 10 fois plus de temps, mais obtenir un algorithme 1000 fois plus performant?

En plus de l'excellent point d'Euphoric , je voudrais ajouter que nous utilisons déjà des langages déclaratifs dans de nombreux endroits où ils fonctionnent bien, c'est-à-dire décrire un état qui ne changera probablement pas ou demander quelque chose pour lequel l'ordinateur peut réellement générer du code efficace seul:

• HTML déclare quel est le contenu d'une page Web.

• CSS déclare à quoi devraient ressembler les différents types d'éléments d'une page Web.

• Chaque base de données relationnelle possède un langage de définition de données qui déclare quelle est la structure de la base de données.

• SQL est beaucoup plus proche du déclaratif que de l'impératif, car vous lui dites ce que vous voulez voir et le planificateur de requêtes de la base de données détermine comment y arriver.

• On pourrait soutenir que la plupart des fichiers de configuration (.vimrc, .profile, .bashrc, .gitconfig) utilisent un langage spécifique au domaine qui est largement déclaratif

Les abstractions fuient

Vous pouvez implémenter un système déclaratif où vous déclarez ce que vous voulez, et le compilateur ou l'interpréteur détermine un ordre d'exécution. L'avantage théorique est qu'il vous libère de la nécessité de réfléchir au «comment», et vous n'avez pas à détailler cette implémentation. Cependant, dans la pratique pour l'informatique à usage général, vous devez toujours penser au `` comment '' et écrire toutes sortes d'astuces tout en gardant à l'esprit comment cela sera implémenté, car sinon le compilateur peut (et souvent choisit) choisir une implémentation qui sera très, très, très lent (par exemple n! opérations où n suffirait).

Dans votre exemple particulier, vous obtiendrez un algorithme de tri - cela ne signifie pas que vous en obtiendrez un bon ou même un peu utilisable. Votre définition donnée, si elle est implémentée littéralement (comme le ferait probablement un compilateur), entraîne http://en.wikipedia.org/wiki/Bogosort qui est inutilisable pour les jeux de données plus volumineux - elle est techniquement correcte, mais a besoin d'une éternité pour trier un millier de nombres .

Pour certains domaines limités, vous pouvez écrire des systèmes qui réussissent presque toujours bien à trouver une bonne implémentation, par exemple SQL. Pour l'informatique à usage général qui ne fonctionne pas particulièrement bien - vous pouvez écrire des systèmes dans, disons, Prolog mais vous devez visualiser comment exactement vos déclarations seront converties en un ordre d'exécution impératif à la fin, et cela perd une grande partie du déclaratif attendu avantages de la programmation.

La décidabilité informatique est la raison la plus importante pour laquelle la programmation déclarative ne s'est pas avérée aussi simple qu'elle semble l'être.

De nombreux problèmes relativement faciles à énoncer se sont révélés indécidables ou ont une complexité NP-complète à résoudre. Cela se produit souvent lorsque nous prenons en compte les classes négatives et la classification, la comptabilité et la récursivité.

Je voudrais expliquer cela avec certains domaines bien connus.

La décision sur la classe CSS à utiliser nécessite une connaissance et une prise en compte de toutes les règles CSS. L'ajout de nouvelles règles peut invalider toutes les autres décisions. Les classes CSS négatives ne sont pas intentionnellement ajoutées au langage, en raison de problèmes NP-complets, mais le manque de classes négatives complique les décisions de conception CSS.

Dans un optimiseur de requête (SQL), il y a le problème délicat de décider dans quel ordre se joindre, quels indices utiliser et quelle mémoire allouer à quels résultats temporaires. Il s'agit d'un problème NP-complete connu qui complique la conception de la base de données et la formulation des requêtes. Pour le formuler différemment: lors de la conception d'une base de données ou d'une requête, le concepteur doit connaître les actions et l'ordre des actions que l'optimiseur de requêtes est susceptible de prendre. Un ingénieur expérimenté a besoin de connaître l'heuristique utilisée par les principaux fournisseurs de bases de données.

Les fichiers de configuration sont déclaratifs, mais certaines configurations sont difficiles à déclarer. Par exemple, pour configurer correctement les fonctionnalités, il faut prendre en compte la gestion des versions, le déploiement (et l'historique du déploiement), les remplacements manuels possibles et les conflits possibles avec d'autres paramètres. Valider correctement une configuration peut devenir un problème NP-complet.

Le résultat est que ces complications prennent les débutants par surprise, elles brisent la «beauté» de la programmation déclarative et obligent certains ingénieurs à rechercher d'autres solutions. La migration d'ingénieurs inexpérimentés de SQL vers NoSQL pourrait avoir été déclenchée par la complexité sous-jacente des bases de données relationnelles.

Nous avons une différence de déclarativité des langages de programmation qui est mise à profit dans la vérification de la logique numérique.

Normalement, la logique numérique est décrite au niveau de transfert de registre (RTL) où le niveau logique des signaux entre les registres est défini. Pour vérifier que nous ajoutons de plus en plus de propriétés définies de manière plus abstraite et déclarative.

L'un des langages / sous-ensembles de langues les plus déclaratifs est appelé PSL pour Property Specification Language. Lors du test d'un modèle RTL d'un multiplicateur dans lequel, par exemple, toutes les opérations logiques de décalage et d'addition sur plusieurs cycles d'horloge doivent être spécifiées; vous pouvez écrire une propriété à la manière de assert that when enable is high, this output will equal the multiplication of these two inputs after no more than 8 clock cycles. La description PSL peut ensuite être vérifiée avec le RTL dans une simulation, ou le PSL peut être formellement prouvé pour la description RTL.

Le modèle PSL plus déclaratif oblige à décrire le même comportement que la description RTL mais d'une manière suffisamment différente qui peut être vérifiée automatiquement par rapport au RTL pour voir si elles sont d'accord.

Le problème est surtout de savoir comment vous modélisez les données; et la programmation déclarative n'aide pas ici. Dans les langues impératives, vous avez déjà des tonnes de bibliothèques qui font beaucoup de choses pour vous, vous n'avez donc qu'à savoir quoi appeler. D'une manière particulière, on pourrait considérer cette programmation déclarative (probablement le meilleur exemple pour cela est Stream API en Java 8 ). Ayant cela, l'abstraction est déjà résolue et la programmation déclarative n'est pas nécessaire.

De plus, comme cela a été dit, les langages de programmation logique font déjà exactement ce que vous voulez. On pourrait dire que le problème est la performance, mais avec le matériel et la recherche d'aujourd'hui dans ce domaine, les choses peuvent être améliorées pour être prêtes pour une utilisation en production; en fait, Prolog est utilisé pour les trucs de l'IA, mais je crois seulement par le milieu universitaire.

Il convient de noter qu'il s'applique aux langages de programmation à usage général. Pour les langues spécifiques à un domaine, les langues déclaratives sont bien meilleures; SQL est probablement le meilleur exemple.

Cela ressemblerait à quelque chose comme ça .. {(quel que soit => lire un fichier et appeler une URL) | appeler une url & lire un fichier} Cependant, ce sont des actions à exécuter, et l'état du système change en conséquence, mais ce n'est pas évident de la source.

Les déclarants peuvent décrire une machine à états finis et ses transitions. Le FSM est comme l'opposé des déclaratifs sans actions, même si la seule action est de passer de l'état à l'état suivant.

L'avantage de cette méthode est que les transitions et les actions peuvent être spécifiées par des prédicats qui s'appliquent à plusieurs transitions, plutôt qu'à une seule.

Je sais que cela semble un peu étrange, mais en 2008, j'ai écrit un générateur de programme qui utilise cette méthode, et le C ++ généré est de 2 à 15 fois plus que la source. J'ai maintenant plus de 75 000 lignes de C ++ à partir de 20 000 lignes d'entrée. Deux choses vont de pair: la cohérence et l'exhaustivité.

Cohérence: aucun prédicat qui peut être vrai en même temps ne peut impliquer des actions incohérentes, comme x = 8 et x = 9, ni différents états suivants.

Complétude: la logique de chaque transition d'état est spécifiée. Ceux-ci peuvent être difficiles à vérifier pour les systèmes avec N sous-états, avec> 2 ** N états, mais il existe des méthodes combinatoires intéressantes qui peuvent tout vérifier. En 1962, j'ai écrit la phase 1 d'un système de tri pour les machines 7070, en utilisant ce type de génération de code conditionnel et de débogage combinatoire. Sur les 8 000 lignes du genre, le nombre de bogues à partir du jour de la première version était pour toujours nul!

La phase deux du genre, 12 000 lignes, a enregistré plus de 60 erreurs au cours des deux premiers mois. Il y a beaucoup plus à dire à ce sujet, mais cela fonctionne. Si les constructeurs automobiles utilisaient cette méthode pour vérifier le firmware, nous ne verrions pas les échecs que nous voyons maintenant.

Tout ne peut pas être représenté de manière déclarative.

Souvent, vous souhaitez explicitement contrôler le flux d'exécution

Par exemple, le pseudo-code suivant: if whatever read a file call an URL else call an URL write a file Comment le représenteriez-vous de manière déclarative?

Bien sûr, il existe probablement des moyens exotiques de le faire. Comme des monades . Mais ceux-ci sont généralement plus encombrants, compliqués et beaucoup moins intuitifs que leur partie procédurale.

Tout se résume au fait que "interagir" avec votre environnement / système n'est pas déclaratif. Tout ce qui concerne les E / S est par essence procédural. Vous devez dire exactement quand et ce qui doit arriver, et dans quel ordre.

Le déclaratif est idéal pour tout ce qui est purement lié au calcul. Comme une fonction géante, vous mettez X et vous obtenez Y. C'est super. Un exemple pour cela est HTML, l'entrée est du texte, la sortie est ce que vous voyez dans votre navigateur.