24

Since Prolog = Syntactic Unification + Backward chaining + REPL All three parts can be found in Artificial intelligence: structures and strategies for complex problem solving by George F. Luger. In the fourth edition of the book all three parts are implemented in LISP in Section 15.8, Logic Programming in LISP. He also puts the same code in his other books, ...


21

It's a fairly reliable rule of thumb that Turing-completeness depends on the ability to construct answers or intermediate values of unrestricted "size" and the ability to loop or recurse an unrestricted number of times. If you have those two things, you probably have Turing-completeness. (More specifically, if you can construct Peano arithmetic, then you ...


13

See the implementation of miniprolog at my Programming languages zoo, it is the last one on the list. You can see source code online, the code is well documented.


11

Term rewriting is a rewriting formalism. Starting with a term we rewrite the term according to the term rewriting rules until a normal form is found. Unification is finding a solution (substitution with specific properties) to a problem (a pair of terms). Term rewriting uses a notion called "pattern matching". What you probably meant is: what is the ...


9

If you understand Prolog then you're probably fine. The jargon in Prolog-land is not as fixed as you'd expect, because we really only have three things to refer to, with a dozen or more pieces of jargon to use on. These are my working definitions arrived at from reading books and reading/answering questions about Prolog on Stack Overflow. I may have a ...


7

Here is one possible algorithm: If $N = 0$, output the empty string. If $N = 1$, output "0 1". If $N = 2$, output "0 2 2 3". If $N = 3$, output "0 2 4 3 4 5". If $N = 4$, output "0 2 4 6 4 5 6 7". If $N = 5$, output "0 2 4 6 8 5 6 7 8 9". Otherwise, output the empty string. Now, this is probably not the answer they were expecting, but it's perfectly valid. ...


6

$\lambda$Prolog is a logic programming language based on a much richer logic than Prolog. In particular, the formulas that constitute its language are (higher-order) hereditary Harrop formulas. Horn clauses are a pallid fragment of that. The enabling concept for $\lambda$Prolog is the notion of a uniform proof, and additionally switching to an intuitionistic ...


2

Given the usual substitution function $[x/y]$ s.t. $M[x/y]$ is the result of substituting all free occurrences of '$y$' with '$x$' in $M$, your desired function can be defined as follows: $M [x//y] =_{df} M[x'/y][y/x][x/x']$ provided $x'$ doesn't occur in $M$. Example. Let $C = m(P,X,Y)←m(Q,X,Z),m(R,Z,Y)$. Then: \begin{align*} D &= C~[Q~//~R]\\ ...


2

I found out that this could not be done natively in ASP (or at least in the solvers that I am using). So the abduction theory needs to be modeled with the problem in order to derive expected results. This is an example that demonstrates how it can be done. I haven't had the time to thoroughly test its efficiency but it works for some basic examples. ...


2

Control flow is oriented around the idea of imperative statements. What is the computer doing at this given time? What will it do next? What actions should it perform? Declarative programming abstracts this away (or at least tries to). You're program is now not a set of instructions for the computer to follow, but a sort of specification for the problem. In ...


2

It's possible you're paraphrasing me. I've certainly said things similar to that e.g. here. A more precise statement would be that existential quantification in logic programming languages is (typically) handled by introducing a unification variable. To perform existential introduction, you need to have a term $t$. The rule looks like: $$\dfrac{\Gamma\vdash ...


1

Herbrand models have special domains. The domain of every Herbrand model for $S$ (which is a set of formulas of $L$) is the Herbrand universe $U_L$ for $L$. The set $U_L$ cannot be $\{0, 1\}$, it has a totally different form, see the definition of Herbrand universe in Chapter 1 “Preliminaries”, §3 “Interpretations and models”. The set $U_L$ can contain $p(a)$...


1

By way of context, I'll assume the goal is to do unification in classical first-order logic in a fixed language $\mathscr{L}$. (Formatting and other corrections welcome.) Briefly, you can treat arrays as terms and multidimensional arrays as arrays of arrays. You'll also introduce a new term symbol that doesn't occur in $\mathscr{L}$. So for example, if you ...


1

My suggestion is in preparation for this course, to try and read some beginners guides on pure functional programming language. Having some practical experience actually doing some functional programming before learning the theory could be beneficial. I learned functional programming with F# which might not be the best idea, since it is a hybrid language ...


1

I use predicate to denote p(X) (just like this ). A clause is a disjunction of literals: both facts and rules are (Horn) clauses (Horn) clauses . See the Horn clause wiki link on how to read Prolog rules and on what is a goal (short answer goal=query). Hope that helps.


1

See http://www-ps.informatik.uni-kiel.de/kics2/lib/Findall.html: it says IO based approach is deprecated and the prefferred way not is Curry's SetFunctions module, This new design does away with IO-wrapped return values and has other means to avoid leaking indeterminism and referential non-transparency into the pure-FP land.


1

The reasons for using the IO monad appear to be described in Braßel and Huch and Hanus, 2004, but I cannot find a clear reason given for using a list instead of a set. I guess it is so the list can be elaborated lazily. It seems that the approach described in the 2007 paper was unsatisfactory for some reason (I don't know why), because KiCS2 has gone back ...


Only top voted, non community-wiki answers of a minimum length are eligible