ud GaucheG GaucheD) Droite Chemin) ud Haut Droite) GaucheG GaucheD [zip_gauche|Chemin]) . ud DroiteG DroiteD) Chemin) ud Gauche Haut) DroiteG DroiteD [zip_droite|Chemin]) .
Y.
Aussi appelé combinateur paradoxal.
C'est un combinateur de point-fixe :
.
Il est définissable dans le 
-calcul* pur,
,
mais il ne l'est pas dans le
-calcul simplement typé*.
En fait,
aucun combinateur de point-fixe n'est définissable dans le
-calcul simplement typé,
et donc par des termes de Prolog.
Or,
ce sont ces combinateurs qui donnent la puissance de calcul de la
récursion générale au -calcul.
La puissance de calcul de Prolog ne vient donc pas de la structure de ses termes,
mais seulement de la récursivité dans les clauses, comme cela est
déjà le cas en Prolog*.
Les termes de Prolog* n'ont donc pas tant un rôle calculatoire
qu'un rôle de représentation de structures abstraites.
Il faut noter que le -calcul simplement typé contient la
possibilité de définir des itérateurs sur les
types inductifs*
(entier, listes,
arbres, etc. [Böhm et Berarducci 85, Pierce et al. 89]).
Dans l'état actuel de la technologie de
Prolog,
c'est plutôt moins efficace que la programmation récursive
traditionnelle,
mais cela permet d'utiliser des termes évaluables sans passer par la
résolution.
Cela peut être intéressant pour simplifier la structure d'un programme
en réservant la récursivité au calcul principal et en utilisant
les termes évaluables pour des aspects plus marginaux.
Cela peut augmenter la réversibilité des programmes en évitant
d'employer un évaluateur explicite
(par exemple, le prédicat évaluable is).
Par exemple,
le prédicat harrop*
utilise une notation en -terme de la polarité et de son inversion
(
ex.progr. définitions PLUS*, MOINS* et INV*)