Do supérieur Order Fonctions fournissent plus de puissance à la programmation fonctionnelle?

Question

J'ai posé une question similaire sur cstheory.SE.

Selon cette réponse sur Stackoverflow il y a un algorithme qui sur un langage de programmation fonctionnel pur non paresseux a un $ \ Omega (n \ log n) $ complexité, alors que le même algorithme dans la programmation impérative est $ \ Omega (n) $. Ajout lazyness à la langue FP ferait l'algorithme $ \ Omega (n) $.

Y at-il relation équivalent comparant une langue FP avec et sans fonctions supérieures commande? Est-il encore complet Turing? Dans ce cas, ne le manque d'ordre supérieur sur la PF rend le langage moins « puissant » ou efficace?

Answer 1

Dans un langage de programmation fonctionnelle qui est assez puissant (par exemple, avec des types de données à mettre en œuvre fermetures ) vous pouvez éliminer toutes les utilisations d'ordre supérieur par la transformation de défonctionnalisation . Étant donné que cette méthode est utilisée pour compiler ce genre de langage, vous pouvez raisonnablement supposer que cela ne touche pas les performances et que dans ce paramètre ordre supérieur ne rend pas la langue pas moins puissante. Toutefois, il n'affecte comment écrire du code.

Toutefois, si la langue n'est pas assez puissant, alors oui, d'ordre supérieur ne fournit la puissance expressive. Considérons le lambda-calcul:. Sans fonction d'ordre supérieur, il ne peut vraiment pas faire quoi que ce soit, surtout parce que la plupart des types de données de base (entiers, booléens) sont mis en œuvre en utilisant les fonctions

En conclusion, cela dépend vraiment de la langue.

---

Au-dessus est ma réponse. Ci-dessous, un commentaire sur une hypothèse habituelle sur les langues impératives.

  

au sujet d'un algorithme qui sur un langage de programmation fonctionnelle non paresseux a un $ \ Omega (n \ log n) $ complexité, alors que le même algorithme dans la programmation impérative est $ \ Omega (n) $. Ajout lazyness à la langue FP ferait l'algorithme $ \ Omega (n) $.

Je voudrais voir cette référence. L'hypothèse est que d'habitude un accès à une gamme de longueur $ n $ dans une mémoire RAM est dans le temps $ O (1) $ et l'équivalent en FP pur est dans le temps $ O (\ log n) $. Ce n'est pas tout à fait vrai: le temps d'accès à une mémoire vive est en $ O (\ log m) $ où $ m $ est la taille de la mémoire. Bien sûr, $ m=n $. En pratique l'accès à un élément d'un tableau est beaucoup plus rapide. Une raison serait que $ m $ est limitée, mais ... donc est n $ $!

EDIT: merci pour le lien (le lien pour le papier au sujet de la paresse n'est pas disponible, ici est un autre ). Comme écrit dans les commentaires ci-dessus et dans ma réponse, le modèle de RAM est un peu injuste de PF pur en fournissant O $ (1) $ - temps look-ups, même lorsque la taille d'une adresse n'est pas limitée. Je suis encore à comprendre comment fonctionne le truc paresseux, mais je pense qu'il est important de noter que cela ne concerne que ce problème particulier.

Answer 2

Cela dépend de ce que vous entendez par l'expressivité.

Voici un argument d'ordre supérieur fait quelque chose d'ajouter: avec les langages de premier ordre, la récursion primitive ne suffit pas d'exprimer la fonction Ackermann . Cependant, en présence de fonctions d'ordre supérieur, récursion primitive suffit:

$$ \ Begin {array} {} lcl    \ Textit {Ackermann} \ 0 & = & \ lambda x. x + 1 \\    \ Textit {Ackermann} \ (m + 1) = & & \ textit {} Iter \ (\ textit {Ackermann} \ m) \\    \ Textit {} Iter \ f \ 0 & = & f \ 1 \\    \ Textit {Iter} \ f \ (n + 1) = & & f \ (\ textit {Iter} \ f \ n) \ End {array} $$

Ceci définit la fonction d'Ackermann en utilisant seulement récursion primitive.

Notez que $ \ textit {} $ Iter ne peut être défini dans la théorie de la récursivité classique, parce que $ \ textit {} $ est Iter ordre supérieur. Dans la théorie de la récursivité conventionnelle toutes les fonctions définissables sont de type $ \ mathbb {N} ^ k \ rightarrow \ mathbb {N} $ pour un k $ $, tandis que $ \ textit {Iter} $ est de type $ (\ mathbb {N} \ rightarrow \ mathbb {N}) \ rightarrow (\ mathbb {N} \ rightarrow \ mathbb {N}) $.