Un des plus anciens théorèmes de la programmation logique est celui de la complétude calculatoire des théories de Horn considérées comme des programmes [Andréka et Németi 76, Tärnlund 77]. Cela correspond bien à une des préoccupations majeures des concepteurs de langages de programmation : offrir la puissance d'une machine de Turing. Cet attachement à la complétude calculatoire porte en germe des difficultés considérables, dont l'impossibilité de prévoir aussi précisément qu'on le veut le comportement des programmes au simple vu de leur texte.
Quelques niches ont vu la création de langages de
«programmation»
incomplets
(par exemple, les bases de données avec 
et Datalog).
Nous pensons qu'il est possible de créer de tels langages pour des
niches de plus en plus larges et variées en donnant des restrictions
de plus en plus faibles à la formation des programmes d'un langage
éventuellement complet,
ou en combinant des fragments décidables.
Une niche correspondrait à une classe d'applications qui utiliserait
une classe d'algorithme.
La logique a une longue tradition d'étude de fragments décidables.
À certains correspondent des classes de complexités et donc les
problèmes ou les algorithmes qui sont dans cette classe.
Les grammaires logiques*,
avec les 
,
constituent une autre approche.
Les ne constituent pas véritablement un formalisme incomplet,
mais quelques restrictions supplémentaires permettraient d'en faire un fragment
décidable de Prolog pour application dans une niche particulière :
la programmation dans un monoïde.
Les types inductifs*
fournissent une autre piste pour la définition de fragments décidables.
La programmation logique se prête donc
bien à l'expression de restrictions décidables.
Qu'elles soient toutes issues d'un même paradigme permettrait
de les combiner dans des applications hétérogènes.