Tout le code peut-il être représenté comme une série d'opérations Map / Filter / Reduce?

16

J'ai récemment refactorisé de gros morceaux de code et les remplacer par des requêtes Linq.

Suppression du biais linguistique - Linq est essentiellement un ensemble d'opérations Map / Filter and Reduce qui opèrent sur une séquence de données.

Cela m'a fait réfléchir, jusqu'où serais-je théoriquement capable de prendre cela. Serais-je capable de réécrire la base de code entière en une série (ou même une seule) d'opérations de carte / filtre et de réduction.

Malheureusement, je suis payé pour faire des choses utiles, donc je n'ai pas pu expérimenter beaucoup plus, mais je ne pense à aucune structure de code qui ne pourrait pas être restructurée en tant que telle. Le code à effets secondaires peut être traité via des monades. Même la sortie mappe essentiellement les adresses mémoire aux adresses d'écran.

Y a-t-il quelque chose qui ne pourrait pas (théoriquement) être réécrit en tant que requête Linq?

computer-science Mongus Pong
la source
Pour les arbres, voir ici: stackoverflow.com/questions/250377/…
blueberryfields
J'ai toujours pensé que "réduire" était suffisant pour garantir l'achèvement de Turing (la carte et le filtre peuvent être implémentés comme des opérations de réduction, non?) - au moins, l'équivalent du langage fonctionnel de réduire. Je ne connais pas suffisamment Linq pour être sûr à quel point l'implémentation y suit celle fonctionnelle.
blueberryfields
1
Je ne sais pas, mais une règle approximative est que tout ce que n'importe qui envisagerait même d'écrire tout son code se révélera être Turing complet. Mais le corollaire de cela est qu'être Turing complet n'est pas très excitant.
psr
1
Je suis d'accord avec psr; Je pense qu'une réponse valide à cette question doit répondre à l'exhaustivité de Turing. Une preuve peut tenter d'implémenter une machine Turing en utilisant uniquement ces opérations.
Rob
Pensée oiseuse: même si nous autorisons un non-sens my_list.map(_ignored => a copy of my_list), il semble que l'utilisation de l'espace d'un tel programme soit limitée par un polynôme (en fonction de la longueur du programme). Alors un tel langage ne pourrait certainement pas calculer des problèmes qui ne sont pas dans PSPACE. Cependant, comme de nombreux problèmes dans PSPACE sont considérés comme insolubles, sans parler des classes plus importantes, cela peut ne pas être une restriction très sérieuse.

Réponses:

1

C'est ce qu'on appelle la programmation fonctionnelle, et est considéré par beaucoup comme un concept fondamental. voici une bonne introduction sur Joel On Software . La réponse la plus technique est non, il n'existe actuellement aucun moyen connu de poser à votre ordinateur des questions (d'une manière bien définie) auxquelles il est impossible de répondre via SKI calculus.

JP Mcgrady
la source
1
Il y a bien plus dans la programmation fonctionnelle que les fonctions map, filteret reduce(cela va trois fois si nous ignorons l'intégralité de turing et utilisons des langages FP pratiques). En fait, ils se trouvent être assez généraux et donc généralement utiles, mais sont en fait des applications très simples de programmation fonctionnelle. Le calcul lambda minimum nu peut définir ces fonctions parmi beaucoup d'autres, et non l'inverse.
"voici une bonne introduction sur Joel On Software" - qui parvient à confondre Fortran avec Basic, donc je ne ferais pas trop confiance à d'autres faits.
quant_dev