82
votes
Accepted
Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?
Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that.
A list is not a natural number, and list ...
- 5,830
31
votes
Accepted
What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?
Very good explanations of programming paradigms and the programming concepts from which those paradigms are built are found in Peter van Roy's works. Especially in the book Concepts, Techniques, and ...
- 5,830
10
votes
What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?
Check out the book Types and Programming Languages (TAPL) by Benjamin Pierce. This is an excellent introduction to the fundamental concepts of the field of programming languages.
- 6,958
8
votes
What is the sequence of numbers for N = 6?
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 ...
- 275k
6
votes
Accepted
Generalization of Horn clauses in logic programming?
$\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 ...
5
votes
Accepted
What is the difference between control flow and control logic?
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 ...
- 29.7k
4
votes
Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?
Expressiveness is not a criteria of being Turing complete. Computability is.
If Pure Prolog is Turing Complete then Pure Prolog can compute the intersection between two sequential sets.
You may not be ...
- 669
2
votes
What is Herbrand interpreration and model?
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 ...
- 791
2
votes
Accepted
What algorithms for unification over (multidimensional) array terms?
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 ...
- 923
2
votes
Accepted
Is Unification "an Implementation of Existential Quantification"?
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 (...
2
votes
What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?
Teach yourself how to make a compiler and learn about computer architecture/digital design. Knowing that material will distinguish you from beginners very easily. This free course material from the ...
- 21
1
vote
Accepted
Is it possible to encode contradictory horn clauses without goal clauses?
If you only allow propositional letters p, q, r, ... and Horn clauses of the form ...
- 30k
1
vote
How does Warrens Abstract Machine work?
This may be a question that's too broad to cover here.
The WAM covers a lot of Prolog-specific capabilities (e.g. unification, nondeterminism, the cut) that other abstract machines do not, and its ...
- 21.6k
1
vote
Pseudocode for constructing control flow graph
To create a CFG you begin with an Abstract Syntax Tree (AST). So I
assume you have an AST available. The first step is to collect the
nodes in the tree into basic blocks. This step is optional but ...
- 1,151
1
vote
What makes PROLOG Turing-complete?
Completing the excellent answer by @Pseudonym and referring to your last question "Are function symbols themselves Turing complete?".
You probably mean: Can a language made only of function symbols ...
- 11
1
vote
What is the state of the art in encapsulated search in functional logic programming?
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 ...
- 121
Only top scored, non community-wiki answers of a minimum length are eligible