Lucid Meets Prolog extension

[v217]

Hi,
I read Lucid Meets Prolog on Bill Wadge's Blog and thought this sounds very useful.
I am quite new to prolog, so maybe I am missing something. Can this extension be implemented in Hopes?
Thanks,
Vincent

PS:
In your build script, there is the dependency for the happy parser missing.

[acharal]

Hi @v217,

Thanks for the feedback, I will amend the README file to add happy as a dependency. I am not sure if this can be done by cabal itself.

Now, I'll try to address your main question. THLP (Temporal Horn LP) can be implemented (at least for some examples presented in the blog post you cited) using plain first-order PROLOG. The idea is to use an extra argument for each time-varying predicates to explicitly represent time. For example, the time-varying predicate fib(X) defined in THLP as

first fib (0).
first next fib(1).
next next fib(K) ← next fib(M), fib(N), K is M + N.

will become a predicate fib(T, X)where T represents time. The THLP fib program can be written in PROLOG as:

fib(0,0).
fib(s(0), 1).
fib(s(s(T)), K) :- fib(s(T), M), fib(T, N), K is M + N.

The aforementioned programs will correspond to a Lucid program that uses the fby operator. However, transforming every Lucid program into THLP is not possible, mainly because in Lucid you are allowed to define custom filters (i.e. operators on streams). Notice that in THLP the time-varying predicates are analogous to Lucid streams, thus THLP operators must be predicates that operate on time-varying predicates that sound very close to what HOPES allows you to define. For example,
the operator fby can be defined in HOPES:

fby(S1,S2)(0, X) :- S1(0,X).
fby(S1,S2)(s(T), X) :- S2(s(T), X).

To conclude, in principle someone can implement some time-varying operators in HOPES, however, it is still open (and also interesting) whether the syntactic fragment of HOPES supports all operators of Lucid.

[v217]

Thank you!
Hopefully these ideas and great improvements over the status quo, will soon become adapted by mainstream prologs. Anyway being able to play with these exiting new possibilities in hopes will convince people, that these improvements are really a practical advantage.

[v217]

Hi, I've got time to play with the examples. It seems that some of the examples in the mini-prelude stopped working.
Do you think, if one is only interested in the datalog subset of prolog, that it's possible to write a Higher-Order Datalog to First-Order Datalog transpiler/preprocessor. This added expressivity would be interesting for lots of other projects. I've mentioned this idea for datalog here: Extensional Higher-Order Datalog #239.

[acharal]

Hi @v217,

Do you mind open a separate issue with the non-working prelude definitions, so we can track them down? I much appreciate the feedback!

Higher-order Datalog is an interesting subset so I think it is worth the effort to be studied separately. However, I think that transforming Higher-order Datalog into First-Order Datalog is not trivial. Actually, to the best of my knowledge, I am not aware of such a transformation with respect to the extensional semantics. Now, if you can live with first-order semantics, there is Hilog (part of the XSB compiler) that uses a higher-order syntax with a first-order semantics and thus it is straightforward to define for every Hilog program without function symbols an equivalent first-order Datalog program. More information in Hilog's paper.
I believe that if someone restricts the syntax then there is modest subset of Higher-order Datalog where both the extensional semantics and Hilog semantics coincide.

[v217]

Thank you for the Hilog Links. I will start a separate issue.