Lambda the Ultimate

Axiomatic Language was mentioned on LtU long ago, but with our recent paper A Tiny Specification Metalanguage [Wilson & Lei, SEKE 2012], we thought a new post would be in order:

A logic programming language with potential software engineering benefit is described. The language is intended as a specification language where the user specifies software functionality while ignoring efficiency. The goals of the language are: (1) a pure specification language – “what, not how”, (2) small size, and (3) a metalanguage – able to imitate and thus subsume other languages. The language, called “axiomatic language”, is based on the idea that any function or program can be defined by an infinite set of symbolic expressions that enumerates all possible inputs and the corresponding outputs. The language is just a formal system for generating these symbolic expressions. Axiomatic language can be described as pure, definite Prolog with Lisp syntax, HiLog higher-order generalization, and “string variables”, which match a string of expressions in a sequence.

Axiomatic language requires solving the difficult problem of automatic synthesis of efficient programs from specifications. Is there any hope for this?