Hacker News new | comments | show | ask | jobs | submit login
Extensional Higher Order Prolog (billwadge.wordpress.com)
81 points by rutenspitz on Mar 23, 2016 | hide | past | web | favorite | 5 comments



I've just published a draft paper on an entirely different approach to the same problem: instead of creating a higher-order Prolog, we've discovered a functional (and so higher-order) analogue of Datalog, a more limited language (http://www.rntz.net/files/datafun.pdf, on github at https://www.github.com/rntz/datafun)

This idea of a higher-order Prolog is very interesting! But it's not clear to me how it can be truly extensional without further limiting the language. For there is another reason why Prolog is not extensional: non-termination. As a simple example, consider this program:

    q(X) :- q(X).
    q(adam).
    p(adam).
`p` and `q` are logically equivalent (the line `q(X) :- q(X).` is a no-op; of course a predicate implies itself). But in Prolog, `q` is a useless, nonterminating predicate. This problem is not a simple quirk: provability in even first-order Horn logic is undecidable if you augment it with compound terms & unification (as Prolog does), so there is no general algorithm for deciding Prolog queries.

It looks like extensional higher-order prolog should have the same problem. The article doesn't address it, so I'll go read the papers.

EDIT: The relevant research papers on Higher-Order Prolog, if anybody is interested: http://arxiv.org/abs/1106.3457 "Extensional Higher-Order Logic Programming"; http://arxiv.org/abs/1405.3792 in which they extend it to negation; https://github.com/acharal/hopes the implementation's github repo


I'm interested, thanks for posting! I have no background in logic programming, but I have a problem at work that seems to be screaming for it. I tried Prolog but ran into some limitations. I couldn't tell whether they were with the language or whether I was just holding it wrong.


Nice. I might use this for a project I'm working on.

I have a question for you: have you considered what a homoiconic datafun might look like?


This is fantastic, thanks for posting.


Good to see Prolog getting a mention!




Applications are open for YC Winter 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: