Logic programming and program synthesis

Well-known theoretical arguments proving that logic programming does not eliminate the problem of transforming a specification into an executable program are presented and illustrated. PS (program synthesis) is therefore still a real problem to be faced by AI (artificial intelligence) research since complete automation of a PS tool is still far off, especially for long, complicated specifications such as those usually met in practice. It is shown how it is quite possible to write down specifications in Prolog. Nevertheless, it is pointed out that well-known theoretical reasons limit this possibility, and a detailed analysis of the practical reasons why a formal specification may be hard to program in Prolog is provided. The present work contributes to the clarification of the exact role of PS in AI and in software engineering and its possible application to software certification.