One big issue in the logic programming vs functional programming debate is logic programming’s (or at least the original Prolog’s) restriction to first order logic. To functional programmers this constraint is intolerable; even the simplest Haskell programs are higher order (although this is often due to currying).
Can this be fixed? Yes, but you have to be careful.
If you ever took an English course. you learned that “redundancy” is a bad thing. It means useless, wasted repetition. If you live in the UK you dread being made “redundant” because it means your boss has no use for you and has laid you off.
Only in engineering can it have a positive connotation – for example, a redundant duplicate backup system can be a good idea for safety and reliability. It’s repetition but it’s not useless or wasted.
In fact redundancy is widely used in practice and duplication/backup is only the simplest form. I discovered this trying to make sense of a multi-topic introductory computer science course.
When I was a young grad student at UC Berkeley, I invented what are now called “Wadge degrees”. Not to mention “Wadge reducibility”, “Wadge games”, “Wadge’s Lemma” and the “Wadge hierarchy” (there’s a Wikipedia entry on the latter).
“So”, I am often asked, “what is this all about?”
Short answer: Wadge reducibility is a simple way to compare the complexity of two properties (sets) of real numbers. If A and B are two such sets, A≤WB (or simply A≤B) iff there is a continuous total function f such that for all reals a
a is a member of A iff f(a) is a member of B
I remember when, a long time ago, Logic Programming was just starting out. The logic programmers would go to the functional programming gatherings and hang around the sidelines, hoping to convince everyone that logic programming was a kind of functional programming worthy of attention.
Then came the Japanese “Fifth Generation” project (which was based on Prolog) and the situation was reversed. Functional programmers would loiter in the hallways at Logic Programming conferences trying to convince everyone that functional programming was a kind of logic programming worthy of attention.
Neither side ever succeeded, partly because of serious technical difficulties. Functional programming is deterministic; a program has only one answer. Adding nondeterministic operators (like McCarthy’s amb(a,b), which returns either a or b) messes up the least fixed point semantics. Attempts to handle this with a “power domain” construct never really worked.
The Universal Hybrid Calculus (UHC) is a simple logical formalism that has the power of the monadic predicate calculus but has no bound variables. Natural language statements (which also do not use variables) can be formulated more directly in the UHC. In particular, the UHC, like natural language, uses quantifier phrases (such as some Greeks or all mortals) rather than quantifiers and variables.
(This is joint work with my PhD student Omar Alaqeeli)
The UHC is based on the simplest of the modal logics, S5. S5 can be explained (in a nonstandard way) as follows: there is a nonempty universe of individuals (say, people). Properties of individuals are denoted by property constants, which are upper case letters. For example, M might denote the property of being mortal, and G the property of being Greek. Boolean combinations of property constants also denote properties in the obvious way; so that e.g. G∧M denotes the property of being Greek and Mortal.
This summer I was at LC2015, the big European logic conference (it was great). I was sitting listening to a talk with one of my logic buddies when the speaker mentioned “deontic logic”, which is a fancy Greek name for the logic of obligations.
A thought popped into my mind; I turned to my friend and whispered, “you ought to study deontic logic”. Ha ha ha! A self-referential statement!
My friend wasn’t exactly convulsed with laughter but never mind. A whole research program opened up before me – self descriptive “studying <adjective> logic” sentences.
Besides the development of Lucid, for a long while I’ve been working on another application of intensionality, namely intensional web pages – pages whose exact content depends on an implicit context. Unlike with Lucid, the contexts are not lists of natural numbers but rather lists of parameter settings – originally, based on the algebra of contexts John Plaice and I developed back in 1993 in
Plaice, J. and W.W. Wadge, “A new approach to version control,” IEEE Transactions on Software Engineering, pp. 268-276, 1993.
Originally these contexts were intended to specify versions of software systems but we soon realized that they could equally well be used to specify versions of web pages. In its simplest form a context is a list (sum) of parameter settings, for example