Using the Prolog programming language
- 1Finding psychological security before going full Prolog(1197w~6m)
- 2Set-up and workflow(815w~5m)
- 3Understanding Prolog(2684w~14m)
- 4Graphical-user-interface programming(455w~3m)
- 5Maintaining large knowledge bases(707w~4m)
- 6Logtalk(54w~1m)
- 7Ugly things, awkward squads, states and errors(543w~3m)
- 8Object-logic programming?(623w~4m)
- 9Writing enterprise web applications(1212w~7m)
- 10DSL, meta-programming, optimizing, checking, multi-paradigm, whatnot(826w~5m)
- 11Theoretical foundations of logic programming(467w~3m)
- 12Artificial intelligence?(149w~1m)
- 13What mess?(1702w~9m)
- 14Rethinking module systems, especially of Prolog(3617w~19m)
- 15The problems with Prolog(1224w~7m)
- 16Extending Prolog(91w~1m)
- 17Program checking(294w~2m)
- 18Sometimes we want function and determinism(57w~1m)
- 19Prolog implementation(572w~3m)
- 20SWI-Prolog packs(95w~1m)
- 21What I like about Prolog and Lisp(54w~1m)
- 22Namespacing atoms(47w~1m)
- 23Parsing Prolog?(11w~1m)
- 24Other resources(12w~1m)
- 25Bibliography(543w~3m)
1Finding psychological security before going full Prolog
- 1.1<2018-11-30> This is a book in progress!(138w~1m)
- 1.2Warning about the woes and blockers(239w~2m)
- 1.3If you need to be hyped up(350w~2m)
- 1.4Not sure yet? Try Prolog with minimal investment.(33w~1m)
- 1.5Comparing Prolog implementations?(133w~1m)
- 1.6<2019-03-26> Is there any Prolog IDE?(171w~1m)
- 1.7Prolog community(80w~1m)
- 1.8Recommended learning sequence(54w~1m)
1.1<2018-11-30> This is a book in progress!
I don't know whether I will ever finish this.
By "See file X" I mean a file somewhere in my Github repository.
Who might you be? How might this book serve you?
- a programmer used to C, C++, Java, PHP, Ruby, Python
- a programmer used to Lisp, Scheme, Haskell
- a Prolog believer
- a Prolog evangelist
- someone who used to write Prolog codes
- a dreamer who thinks machines should do more
- a researcher, theoretician, computer scientist, mathematician, logician, philosopher?
- (Who else might you be, why the hell are you here, and how should I write for you?)
We are wearing multiple hats:
- mathematician
- philosopher
- engineer
The goal of this book is to convince you that you should use Prolog to create your next system (what system? game? enterprise application? shell script?).
Ivan Bratko has a "Prolog programming for artificial intelligence" book. I want a "Prolog programming for everything" book.
1.2Warning about the woes and blockers
I'm selling you Prolog here, but let me be honest: Don't buy it if any of these year-2018 deal-breakers are an issue for you. Prolog isn't ready for these use cases in 2018; I hope these will change.
<2018-12-09> Somewhat fatal: ISO Prolog open/4 has no way to open a file for writing without truncating it. (How the hell did they overlook such a common use case?) But some implementations have extensions to work around that:
- Prolog implementations that can open a file for both reading and writing:
- <2018-12-09> Amzi! Prolog open/4 has "readwrite" mode1
- Prolog implementations that can open a file for writing without truncating it, but not for both reading and writing:
- Prolog implementations that cannot open a file for writing without truncating it:
<2018-11-30> No arrays.
<2018-11-30> SWI-Prolog is honest: "The main weakness of Prolog are algorithms that require destructive assignment, intensive array processing or bare-metal performance for e.g., processing pixels."7
<2018-10-24> There is no standard date/time/calendar library? There may be one? I'm still looking. library(julian)?
- Java 8 has "java.util.time". Previous Java versions can use "Joda Time".
- Haskell has the "time" package ("Data.Time" module).
1.2.1<2018-11-22> Prolog weakness: binary array and low-level input-output
Prolog doesn't have arrays.
Workaround: we can fake an array: Allocate with functor(T,F,N), read with arg(N,T,A), and write with nb_setarg(N,T,A).
Prolog doesn't have unsigned integers.
How fast is this?
This requires that the implementation doesn't limit functor arguments.
1.3If you need to be hyped up
(You can skip this.)
<2018-11-30> Don't take this too seriously. I'm on a honeymoon with Prolog.
Prolog is a mind augmentation language. Prolog is a mental prosthesis. With prosthetic arms, I can beat you in arm wrestling. With prosthetic legs, I can beat you in running. With prosthetic minds, I can beat you in thinking. If logic is the language of thought, then Prolog is the closest thing we have to mind dump. Offload your reasoning to computers. As Leibniz said, "Let us calculate!"
You love Lisp macros? Prolog has term_expansion/2, goal_expansion/2, op/2, and the infix operators that you have been dreaming of!
You love Haskell type system? In Prolog you can write your own type systems!
You love C++ operator overloading? In Prolog you can define your own operators with their precedences and associativities!
You want to beat/outdo/one-up your coworkers? Prolog is perfect for that! Unless you're low-level-programming, Prolog is the secret weapon that multiplies your productivity by 20 compared to a low-level programming language such as C, C++, Java. When you build your home, you don't build your own bricks.
Your coworkers are beating you with Prolog? Well, what the hell are you waiting for? Learn Prolog now, or lose your job and die in oblivion!
"Prolog is a convenient language in which to express the semantics of other languages."8
Why logic programming? Because logic is the internal language of thought. It is the highest level programming possible, until we invent telepathy. Don't we dream about programming directly in the language of thought?
A paragraph from Kowalski 1974 [12]:
As a programming language, predicate logic is the only language which is entirely user-oriented. It differs from existing high-level languages in that it possesses no features which are meaningful in only machine-level terms. It differs from functional languages like LISP, based on the \(\lambda\)-calculus, in that it derives from the normative study of human logic, rather than from investigations into the mathematical logic of functions."[12]
"Prolog is an excellent programming contest language: Prolog is close enough to the ultimate specification language (logic), so that the distance between problem and solution is not too big." [7]
1.4Not sure yet? Try Prolog with minimal investment.
If you're not sure yet, I suggest that you read Markus Triska's book "The power of Prolog" while doodling some code on SWISH online Prolog interpreter.
1.5Comparing Prolog implementations?
I use SWI-Prolog because it's what I used in university, and because of this SWI-Prolog sales pitch.
This book assumes that the reader uses SWI-Prolog 7.6.4.
There are many Prolog implementations. Some companies have their own Prolog implementations.
GNU Prolog is "a native-code compiler which produces standalone executables which don’t rely on any byte-code emulator or meta-interpreter."9 But as of 2019 GNU Prolog does not have a module system.
What can we conclude from Wikipedia?10?
Comparison between SWI Prolog, YAP, GNU Prolog.11
How current is this?12
Prolog in JavaScript/browser13
Questions that we should answer, for each implementation:
- Who uses it? How many people use it?
- What is its strengths?
- What is its weaknesses?
- Where is its source code?
- Does the project seem alive?
- Where is the community?
The first impression to me is that XSB Prolog has stronger theoretical foundation and SWI-Prolog has stronger practical implementation.
1.6<2019-03-26> Is there any Prolog IDE?
I use VSCode. There may be other IDEs, but I don't know which one is supported. It's one of the woes of using an unpopular language: Few people are working on the tools.
<2018-12-10> Smart editors are dangerous! Arbitrary code execution!
I use the VSCode extension VSC-Prolog, but I disabled its linter after I realize that it may execute arbitrary code. I only use its syntax highlighting and documentation popup feature. Fortunately the plugin is still very useful without the linter.
Imagine this file:
% doom.pro
:- shell('touch ~/doomed').
I loaded that file into VSCode, and a file named doomed
appeared in my home directory. I'd be really doomed if someone replaced that command with 'rm -rf /'.
Perhaps we should make a whitelist of allowed directives?
Vim suffers the same thing with its modelines. I think it's now disabled by default?
However, this doesn't affect you if you only open what you write yourself, and never open a criminal's Prolog code. But this is an accident waiting to happen!
I reported this:
I hear some things about Eclipse PDT.
1.7Prolog community
Questions, answers, discussions, news:
- SWI-Prolog Discourse Group16. <2019-04-03> The old SWI-Prolog Google Groups17 has been deprecated. They are moving.
- IRC requires login. Where is the chat log?
- comp.lang.prolog https://groups.google.com/forum/#!forum/comp.lang.prolog
- StackOverflow tag swi-prolog https://stackoverflow.com/questions/tagged/swi-prolog
- https://www.reddit.com/r/prolog/
What:
- SWI-Prolog roadmap https://github.com/SWI-Prolog/roadmap
- http://www.swi-prolog.org/Links.html
Unclear links:
"Conference on the practical application of Prolog": When was it last held? It seems no more.
Twitter LOPSTR: Logic Based Program Synthesis and Transformation: 13th International…
Who uses Prolog?
Gerrit has prolog? https://gerrit-review.googlesource.com/Documentation/prolog-cookbook.html
I hate "awesome" lists like this "awesome Prolog"18 list because such lists do not explain why something is awesome.
1.8Recommended learning sequence
- Know how to read Prolog programs.
- Know basic Prolog syntax.
- Know what a Prolog term is.
- Know what a Prolog clause is.
- prolog headless clause19
- Know how to read/interpret the meaning of a Prolog clause as an English sentence.
- Know basic Prolog syntax.
- Know the operational semantics of Prolog.
- Know some declarative semantics of Prolog.
- Come up with alternative declarative semantics for Prolog programs.
p(0,1).
% is the same as
p(0,1) :- true.
2Set-up and workflow
We assume that you have installed SWI-Prolog 7.6.4.
- 2.1Things to do in each OS reinstall(319w~2m)
- 2.2Workflow(488w~3m)
2.1Things to do in each OS reinstall
This has to be at least once. This may have to be redone every time we replace our operating system, such as when replacing Ubuntu 14.04 with Debian 9.
- 2.1.1<2018-10-20> Installing SWI-Prolog 7.6.4 on Ubuntu 14.04(225w~2m)
- 2.1.2Enabling readline(61w~1m)
2.1.1<2018-10-20> Installing SWI-Prolog 7.6.4 on Ubuntu 14.04
If you are using Ubuntu 14.04, follow my instructions below. If your operating system has packaged SWI-Prolog 7.6.4 or newer, use it. Otherwise, follow the official instructions and find SWI-Prolog 7.6.4.
The following guide is for installing SWI-Prolog 7.6.4 on Ubuntu 14.04.
Uninstall existing SWI-Prolog installations. The version packaged with Ubuntu 14.04 is too old (6.6.4). SWI-Prolog 7 introduces a new double-quoted string type.
Install dependencies. I take this from the Debian build instructions with these changes. I replace libunwind-dev
with libunwind8-dev
. I remove openjdk-8-jdk
and junit
. I add libreadline-dev
.
sudo apt-get install \
build-essential autoconf curl chrpath pkg-config \
ncurses-dev libreadline-dev libedit-dev \
libunwind8-dev \
libgmp-dev \
libssl-dev \
unixodbc-dev \
zlib1g-dev libarchive-dev \
libossp-uuid-dev \
libxext-dev libice-dev libjpeg-dev libxinerama-dev libxft-dev \
libxpm-dev libxt-dev \
libdb-dev \
libpcre3-dev \
libyaml-dev \
libreadline-dev
That doesn't include the documentation dependencies because they are too big. Just read the documentation online.
After apt-get finishes, for security (avoiding sudo cache), close that terminal, and open a new one.
Download the source.
Check the checksum using sha256sum.
cp -p build.templ build
mkdir -p $HOME/.local
Edit build
script. Set PREFIX
to $HOME/.local
. Uncomment the --link
option in EXTRACFG
variable.
Run ./build
. It should take a few minutes (about 5 minutes on my 4-core 8-GB-RAM machine).
Ensure that $HOME/.local/bin
is in your PATH
. For example, I have this line somewhere near the end of my ~/.bashrc
file:
export PATH="$PATH:$HOME/.local/bin"
If you edit your bashrc, close your terminal and open a new one. Then enter swipl --version
in the new terminal. The program should show something like this:
SWI-Prolog version 7.6.4 for x86_64-linux
If you don't want to edit your bashrc, you can run swipl by its full path ~/.local/bin/swipl
.
2.1.2Enabling readline
We want readline for history (Ctrl+R, Ctrl+S) and completion (Tab, Ctrl+P/Up, Ctrl+N/Down).
To keep the entire codebase under BSD license, SWI-Prolog doesn't enable the GPL-licensed GNU readline by default. But you can tell SWI-Prolog to use readline. First, install your distro's libreadline-dev package. Then, put this line in your ~/.swiplrc
:
:- set_prolog_flag(readline, readline).
Related: GitHub issue #72: "how to build with GNU readline on linux".
2.2Workflow
- 2.2.1Starting the interpreter and the documentation server(22w~1m)
- 2.2.2Thinking and editing(70w~1m)
- 2.2.3Rebuilding(70w~1m)
- 2.2.4Trying and manual testing(121w~1m)
- 2.2.5Seeing source codes and finding definitions(49w~1m)
- 2.2.6Troubleshooting: tracing and spying(130w~1m)
- 2.2.7Committing to a Git repository(32w~1m)
2.2.1Starting the interpreter and the documentation server
I start SWI-Prolog with this command line:
swipl --pldoc=DocPort -l PrologFile
I use 4002 for DocPort.
I open http://localhost:4002/pldoc/ in my browser.
2.2.2Thinking and editing
I edit some Prolog source files in Visual Studio Code with vim key bindings because I often need to duplicate a line when adding a new clause.
I add statements or comments.
I think a lot about names, representations, and relations.
To edit the source of a thing in PceEmacs, we have several options:
- click the "Edit file" or "Edit predicate" button in pldoc server, or
- query
edit(Name)
oredit(Name/Arity)
in the interpreter.
2.2.3Rebuilding
To see the updated documentation, I click "Make & Reload" button in my pldoc website, if I haven't done so. If I have clicked that button, I simply refresh my browser with F5 or Ctrl+R.
To test the program, I query make.
in the interactive prompt, and I enter some queries.
Warnings are errors. If there is a warning, I go back to editing. "Singleton variables" most likely mean there's a typo.
2.2.4Trying and manual testing
Important: Prolog source file and Prolog query prompt have different syntax. A Prolog source file contains statements. The Prolog interpreter accepts queries. Pasting a file into the interpreter does not load the file; this is contrary to Lisp/Python/Ruby interpreters.
The prompt ?-
means that the interpreter is expecting a query. However, we can enter temporary statements:
- Type the query
[user].
. The prompt changes to|:
. We're now at the statement prompt. (The syntax:- [foo].
is shorthand for:- consult(foo).
which is documented in consult/1.) - Enter several lines of statements.
- End with a new line and Control+D. We're now back at the query prompt.
Those temporary statements disappear when the interpreter quits.
Usually, after trying my changes, I go back to thinking and editing.
2.2.5Seeing source codes and finding definitions
To show the canonical representation (properly-parenthesized tree form) of a term, query write_canonical(Term)
.
To see the source code of a predicate, query edit(Name)
or edit(Name/Arity)
or listing(Module:Name)
or listing(Name)
. We can see the source code of libraries. We can easily find where things are defined.
2.2.6Troubleshooting: tracing and spying
Having to use the tracer means I have failed to design unsurprising programs. It means that my past self have failed to communicate to my future self.
Sometimes I query debug/0 to disable optimizations so that errors have full stack trace. Sometimes I need to restart the interpreter and query debug/0 before running my development web server. See also nodebug/0.
I start tracing a goal with the query trace, Goal.
In the tracer prompt:
a
aborts (calls abort/0; goes back to toplevel interpreter prompt)c
creeps ("step into" in modern debugger parlance)s
skips ("step over" in modern debugger parlance)l
leaps ("run" in modern debugger parlance)- Type
/f
in the tracer prompt to run to the next failure.
I stop tracing by notrace/0.
TODO spy/1, tspy/1
trace/0, gtrace/0, notrace/0
These resources say something about fixing programming errors:
- https://www.cs.ucsb.edu/~kyledewey/cs162w15/debugging_prolog.html
- http://www.swi-prolog.org/pldoc/man?section=debugoverview
- https://www.metalevel.at/prolog/testing
- https://www.metalevel.at/prolog/debugging
2.2.7Committing to a Git repository
I commit my work to Git repository with Emacs Magit or git-gui. I sanity-check the tree with gitk --all
. I push my work to my GitHub work repository.
3Understanding Prolog
There are several models (ways of understanding what a Prolog program does):
- procedural
- database/relational
- functional
- logic
The procedural way is what actually happens.
Sometimes an abstraction fails, and we have to know what is really going on under the abstraction.
- 3.1Should we introduce Prolog as a database or as a programming language?(77w~1m)
- 3.2What does Prolog code look like and what does it mean?(351w~2m)
- 3.3What actually happens under the hood?(340w~2m)
- 3.4Why was Prolog invented?(190w~1m)
- 3.5<2018-12-05> How to present Prolog to newcomers(349w~2m)
- 3.6Why use Prolog for AI?(9w~1m)
- 3.7Prolog as database programming language(420w~3m)
- 3.8Prolog as logic programming language(458w~3m)
- 3.9Prolog as procedural programming language(464w~3m)
3.1Should we introduce Prolog as a database or as a programming language?
Perhaps it helps to introduce Prolog as a deductive database instead of as a programming language.
The working of Prolog can be summarized this way:
- A database is a collection of Horn clauses.
- A Horn clause is an implication whose antecedent is an atomic formula.
- To prove A and B, prove A then prove B. (Prolog operational semantics.)
- The order of clauses matters. Prolog tries clauses in the order they appear.
3.2What does Prolog code look like and what does it mean?
A Prolog program is a collection of Horn clauses?
- 3.2.1Reading Prolog programs, and a crash course to logic(54w~1m)
- 3.2.2The meanings of a Horn clause(223w~2m)
- 3.2.3The procedural-provability-logic interpretation of Prolog Horn clauses(58w~1m)
3.2.1Reading Prolog programs, and a crash course to logic
What is the meaning/interpretation of a Prolog program?
A clause has the shape Head :- Body
.
Usually we begin with genealogy like Abraham's20. Family tree is actually not a tree but a directed graph: Families sometimes inbreed.
The words "father" and "mother" are to be interpreted as verbs here.
father(abraham, isaac).
father(abraham, ishmael).
father(isaac, esau).
father(isaac, jacob).
mother(sarah, isaac).
mother(hagar, ishmael).
mother(rebecca, esau).
mother(rebecca, jacob).
parent(A, B) :- father(A,B) ; mother(A,B).
3.2.2The meanings of a Horn clause
A Horn clause in Prolog looks like A :- B
.
A Horn clause can be thought of in several ways.
The operational meaning of A :- B1, ..., Bn
is that calling the procedure A causes B1, …, Bn to be called in that order. This is the actual meaning of Prolog programs. All other meanings are useful fantasies.
The classical-logic reading of A :- B
is \(A \leftarrow B\), that is, "A is true if B is true" or "A is implied by B".
The proof-theoretic reading of A :- B
is "to prove \(A\), it is enough to prove \(B\)".
The search-tree reading of A :- B1, ..., Bn
is that the tree node A has the children B1, …, Bn.
These multiple readings are confusing. For example, the classical-logic reading implies that querying a
against the following knowledge base should succeed because in classical logic \( A \leftarrow (B \wedge A) \equiv A \leftarrow B \), but the query a
actually does not terminate.
a :- b, a.
b.
In classical logic but not in Prolog, that knowledge base is equivalent to this:
a :- b.
b.
Enhancing the declarativeness of Prolog requires memoization.
What is the relationship between logic programming, relational programming, logic, Horn clauses, theorem proving, searching, and backtracking?
If each phrase is deterministic (always succeeds exactly once and never fails), then Prolog becomes a procedural programming language with assign-once variables and unification.
3.2.3The procedural-provability-logic interpretation of Prolog Horn clauses
p :- q, r
can be interpreted as "to prove p, first prove q, and then prove r".
Problem: Horn clauses and biimplications
Classical propositional logic formula \( a \iff b \) (which is equivalent to \((a \to b) \wedge (b \to a)\)) does not translate to this Prolog program:
a :- b. b :- a.
Querying
?- a
does not terminate.This terminates:
% H is the hypothesis bag. a(H) :- member(a,H). a(H) :- \+ member(a,H), b(H). b(H) :- member(b,H). b(H) :- \+ member(b,H), a(H).
3.3What actually happens under the hood?
- 3.3.1Prolog is a depth-first brute-forcer(136w~1m)
- 3.3.2Swapped phrases, depth-first, breadth-first?(30w~1m)
- 3.3.3Understanding depth-first search, backtracking, choice points, performance, and cuts(171w~1m)
3.3.1Prolog is a depth-first brute-forcer
But you can emulate other search algorithms too.
Non-termination pitfalls, and how to generate terms correctly
Sometimes we forget that Prolog, on failure, backtracks (retries), not stops.
Sometimes we focus too much on the logical reading and neglect the procedural reading.
For example, suppose that you want to generate all lists whose length doesn't exceed 2.
The following is a mathematically correct statement about that fact, but it doesn't work in Prolog. It has correct logical reading, but incorrect procedural reading. If you keep pressing
;
, this will fail to terminate.The correct way to do that is to use
between/3
(inclusive):We can also use the
clpfd
library:We shouldn't have to resort to cuts:
See also:
- https://www.metalevel.at/prolog/nontermination
- "[Non-termination is] common among beginners, and often lead them to perceive Prolog as 'slow', when in fact their program does not terminate at all."
- https://www.metalevel.at/prolog/nontermination
3.3.2Swapped phrases, depth-first, breadth-first?
In this example, there is only a small syntactic difference between dfs
and bfs
(it's just flipped order). Which one exploits tail call optimization (last call optimization)?
3.3.3Understanding depth-first search, backtracking, choice points, performance, and cuts
Save this knowledge base into a file, and load it into Prolog.
Run the query a(A), b(B).
and press ;
until Prolog fails.
This is what Prolog finds (we remove the newlines to make it more readable):
A = B, B = 0 ;
A = 0, B = 1 ;
A = 1, B = 0 ;
A = B, B = 1.
This is the search space (search tree) of that query.
?- a(A), b(B).
/ \
A = 0 A = 1
/ \ / \
B = 0 B = 1 B = 0 B = 1
Prolog traverses that tree in depth-first order as follows:
- ?- a(A), b(B).
- A = 0
- B = 0
- B = 1
- A = 1
- B = 0
- B = 1
The important things to infer from this experiment are:
- Prolog repeats the work on
b
as many times as the number of ways of satisfyinga
. Ifa
can be satisfied in N ways, and satisfyingb
is a lot of work, then Prolog may do that work N times, although the work produces the same result. - Everything to the right of an infinite branch will never be visited.
What is a choice point?
A cut makes a(A), b(B)
and b(B), a(A)
return different results.
How far does a cut cut?
"The craft of Prolog" defines three kinds of cuts: red, green, and blue.
- A red cut destroys the logical meaning of a program. Green and blue cuts don't.
3.4Why was Prolog invented?
If Prolog is the answer, what is the problem? The problem was the creation of natural-language user-interface. Colmerauer & Roussel 1996 [6]: "It can be said that Prolog was the offspring of a successful marriage between natural language processing and automated theorem-proving."
Philippe Roussel coined the name "Prolog" in Marseilles in 1972. [6]
Robinson 1965 [24]
The key idea of logic programming is the interpretation of a Horn clause as a procedure declaration (Kowalski 1974 [12]).
Logic seems to be the internal language of thought.
Elaborated in van Emden & Kowalski 1976 [28].
Predicate logic can be used both for programming and for knowledge representation.
What is "refutation-complete"21?
http://www.prolog-heritage.org/en/ph1.html
SWI-Prolog goes back to 1986.22
Did logic programming emerge from automated theorem proving? What is computational logic? What is automated reasoning?
Maarten van Emden has a blog23.
The relationship between Lisp and lambda calculus is superficial: van Emden24) wrote that John McCarthy wrote (emphasis mine):
To use functions as arguments, one needs a notation for functions, and it seemed natural to use the lambda notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions.
3.5<2018-12-05> How to present Prolog to newcomers
This is a draft. These are slides. Assume that one section is one slide.
There are several ways to introduce Prolog:
- as a deductive database
- as a logic programming language
- as a procedural programming language with backtracking
- as a natural language processing tool, which is its original reason of existence [6]
- as an artifical intelligence tool (what? automated reasoning?)
It may be best to introduce Prolog as a deductive database. We want people to have understanding and good habit.
- 3.5.1"Talking" with the computer(144w~1m)
- 3.5.2Write once, run in several directions(99w~1m)
- 3.5.3Another declarative example: palindromes(15w~1m)
- 3.5.4Learning resources?(17w~1m)
3.5.1"Talking" with the computer
We can think of an interactive Prolog session as a conversation with the computer.
The Prolog phrase "append(A, B, C)" means the English clause "appending list A and list B produces list C".
Here we show some ways of calling append/3.
Here we show how to read Prolog fragments in English.
"Prolog, does appending [1] and [2,3] produce [1,2,3]?"
?- append([1], [2,3], [1,2,3]).
true.
"Prolog, what does appending [1] and [2,3] produce?"
?- append([1], [2,3], C).
C = [1,2,3].
"Prolog, what list do I have to append to [1] in order to produce [1,2,3]?"
?- append([1], B, [1,2,3]).
B = [2,3].
"Prolog, what list produces [1,2,3] when appended with [2,3]?"
?- append(A, [2,3], [1,2,3]).
A = [1] ;
false.
"Prolog, does appending [1] and [2] produce [1,2,3]?"
?- append([1], [2], [1,2,3]).
false.
We press ";" to ask Prolog to find another solution. Prolog prints "false" when it doesn't find any more solutions.
"Prolog, what list produces [1] when appended with itself?"
?- append(A, A, [1]).
false.
"Prolog, what list produces [1,2,1,2] when appended with itself?"
"[1,2]."
"Is there any other such list?"
"No."
?- append(A, A, [1,2,1,2]).
A = [1,2] ;
false.
"Prolog, what two lists A and B produce [1,2,3] when appended?"
append(A, B, [1,2,3]).
A = [], B = [1,2,3] ;
A = [1], B = [2,3] ;
A = [1,2], B = [3] ;
A = [1,2,3], B = [] ;
false.
3.5.2Write once, run in several directions
The Prolog code for append/3 seems simple. We can see in SWI-Prolog library/lists.pl append/3 (I renamed some variables):
append([], B, B).
append([H|A], B, [H|C]) :- append(A, B, C).
Haskell seems simpler:
append [] b = b
append (h : a) b = h : append a b
But those fragments differ. In Prolog we can run the code in other directions. There are 3 parameters, each with two directions (input/bound or output/unbound); thus there are 2^3 = 8 possible directions. The Prolog predicate translates to at least 5 Haskell functions, for the 5 ways of using append/3 we saw earlier.
We write append/3 once, and we get at least five ways of calling it.
But this beautiful dream crumbles outside pure symbolic logic programming.
3.5.3Another declarative example: palindromes
"A list L is a palindrome iff L is its own reverse."
palindrome(L) :- reverse(L, L).
3.5.4Learning resources?
2015 Approaches for Learning Prolog Programming https://www.tandfonline.com/doi/full/10.11120/ital.2007.06040088
Roman Barták's "On-line Guide to Prolog Programming"
https://www.cis.upenn.edu/~matuszek/Concise%20Guides/Concise%20Prolog.html
display/1 vs write_canonical/2? https://swi-prolog.discourse.group/t/re-swipl-re-pedagogy/48/10
3.6Why use Prolog for AI?
Because Prolog produces explainable AI.
3.7Prolog as database programming language
- 3.7.1Prolog and ontology(44w~1m)
- 3.7.2"Pure" relation built from impure parts(39w~1m)
- 3.7.3Knowledge representation; designing predicates; naming is hard(156w~1m)
- 3.7.4Knowledge representation and software specification(54w~1m)
- 3.7.5Total relational programming? Relational programs that can be proven to terminate?(48w~1m)
- 3.7.6The meaning of a pure Prolog predicate(80w~1m)
3.7.1Prolog and ontology
Writing a Prolog knowledge base is an exercise in ontology (a branch of philosophy, that studies beings and relationships). We ask these all the time:
- What exist?
- How do they relate?
- How do we model all those entities and relationships in Prolog for not-too-slow computation?
3.7.2"Pure" relation built from impure parts
We can define a truly relational plus/3 that works for all mode combinations for natural numbers, but the code seems too much and illogical.
nat(A) :- integer(A), A >= 0.
plus(A, B, C) :- nat(A), nat(B), nat(C), !, C =:= A + B.
plus(A, B, C) :- nat(A), nat(B), !, C is A+B.
plus(A, B, C) :- nat(A), nat(C), !, B is C-A.
plus(A, B, C) :- nat(B), nat(C), !, A is C-B.
plus(A, B, C) :- nat(A), !, between(0, inf, C), plus(A, B, C).
plus(A, B, C) :- nat(B), !, between(0, inf, C), plus(A, B, C).
plus(A, B, C) :- nat(C), !, between(0, C, A), plus(A, B, C).
plus(A, B, C) :- between(0, inf, C), plus(A, B, C).
We can write that shorter in miniKanren which uses iterative-deepening search?
3.7.3Knowledge representation; designing predicates; naming is hard
One possible mapping is:
- a noun maps to a term
- a verb maps to a predicate
Come to think of it, a transitive verb indeed denotes a relation between two nouns.
The name of a predicate is less important than its mapping and its meaning.
father(abraham, isaac).
beget(abraham, issac).
papa(abraham, issac).
spawn(abraham, issac).
mystery_predicate(abraham, issac).
"A bird eats an apple" means \( \exists x \exists y ( bird(x) \wedge apple(y) \wedge eat(x,y) ) \).
The name of a relation should describe the relationship.
If we intend that there is only one relation between A and B that makes sense, then we may name that relation A_B. But:
- What if A or B contains underscores?
- Why do we prefer
father_child
tobeget
orsire
?
is_thing(A).
A procedure's name should begin with a verb.
Order the parameters from the most likely to be bound. If parameter A is more likely to be more bound than parameter B, then A should come before B. Example: Write list_length/2 instead of length_list/2. Unfortunately not everyone follows this convention.
3.7.4Knowledge representation and software specification
Their relationships
- 2010, "Functional-Logic Programming Lecture Notes", Harold Boley, slides, pdf
- Knowledge representation in AI roughly corresponds to software specification in software engineering.
- Declarative programs can be thought of as executable specifications.
- Invertibility principle (slide 36)
- Nesting/conjunction principle (slide 46)
- Unification principle (slide 50)
- Amalgamation/integration principle (slide 55)
- That's a long deck: 270 slides.
- 2010, "Functional-Logic Programming Lecture Notes", Harold Boley, slides, pdf
Executable specification?
- lightweight executable mathematics https://www.cl.cam.ac.uk/~pes20/lem/
3.7.5Total relational programming? Relational programs that can be proven to terminate?
A total relation is a relation that is defined for every element in its domain.
If there is total functional programming, then there should be total relational programming.
It is too easy to write a Prolog program that doesn't terminate.
3.7.6The meaning of a pure Prolog predicate
The meaning of a predicate is the set of all ground terms that satisfy that predicate. Formally, the meaning of the predicate \(p\) is the set \( \SetBuilder{x}{p(x)} \). Such set is called the extension25 of the predicate.
In this example, what is the meaning of t/2 supposed to be? Declaratively, the query ?- t(A,B)
means the finite set {(1,1)}
, and thus the query should terminate. But with SLD-resolution operational semantics, the query does not terminate.
e(1,1).
t(A,B) :- e(A,M), t(M,B).
3.8Prolog as logic programming language
- 3.8.1Multi-directional predicates(81w~1m)
- 3.8.2Functional (deterministic) relation(3w~1m)
- 3.8.3How to read declarative Prolog programs(186w~1m)
- 3.8.4Epistemic interpretation of Prolog programs: Failure as ignorance(159w~1m)
- 3.8.5Naming the parts of a list: head, tail, and butt(23w~1m)
- 3.8.6Defining your own operators(7w~1m)
3.8.1Multi-directional predicates
A predicate has several uses: iteration, searching, testing, and other computation. A predicate can be used both to enumerate/iterate a finite set, to search for a satisfier, and to test membership.
person(alice).
person(bob).
?- person(charlie). % test membership
?- once(person(A)). % satisfy
?- person(A), !. % satisfy
?- person(A). % iterate
A predicate can be used both to enumerate some infinite sets and to test membership. The programmer is reponsible to ensure that the recursion terminates.
nat(z).
nat(s(A)) :- nat(A).
succ(A, s(A)).
succ(A, s(A)) :- nat(A).
For non-pure Prolog programs, we have to do some repetition if we want a multi-directional relation.
succ(A, B) :- integer(A), !, B is A+1.
succ(A, B) :- integer(B), !, A is B-1.
succ(A, B) :- !, type_error(succ, succ(A,B)).
But that can be done more elegantly with constraint logic programming.
succ(A, B) :- A + 1 #= B.
3.8.2Functional (deterministic) relation
f(In1, Out1) :- Guard1, !, Body1.
...
f(InN, OutN) :- GuardN, !, BodyN.
f(In, _) :- !, type_error(Type, In).
3.8.3How to read declarative Prolog programs
A Horn clause A :- B
means "to prove A, prove B". The left-arrow :-
can be read as "if".
wet :- rain.
wet :- sprinkle.
% The same.
wet :- rain ; sprinkle.
The conjunction A,B
means prove A and then prove B. Prolog proves them in sequence.
Example: The fire triangle26:
% A line comment begins with a percent sign.
fire :- oxygen, heat, fuel.
oxygen.
heat.
Prolog complains about undefined predicate fuel/0.
An alternative in which Prolog does not complain about undefined predicates:
known(oxygen).
known(heat).
known(fire) :- known((oxygen,heat,fuel)).
known((A,B)) :- known(A), known(B).
We have just defined a small world, a small ontology. (Is this too fast-paced for beginners?)
The disjunction A;B
means prove A or prove B. If A fails, Prolog backtracks and tries to prove B.
Non-variables in clause head abbreviate unification. For example, p(a,b) :- Q
abbreviates p(A,B) :- A=a, B=b, Q
.
A :- B
is pure iff all reordering of the phrases of B doesn't change the result?
\+A
means "fail to prove A". It is not classical-logical negation.
Every variable is implicitly universally quantified.
The prompt ?- Q
means we ask Prolog to prove Q
.
Perhaps elucidating https://en.wikipedia.org/wiki/Prolog_syntax_and_semantics
We often define a set \(A\) with the set-builder notation \( \SetBuilder{x}{\phi_A(x)} \). We should not conflate a set \(A\) and its membership-testing predicate \(\phi_A\).
A set can be thought of as all the ground terms that satisfy a predicate.
% person ~ {joe}
person(joe).
% natural ~ {0, 1, 2, ...}
natural(N) :- integer(N), N >= 0.
3.8.4Epistemic interpretation of Prolog programs: Failure as ignorance
Sometimes a Prolog program should be interpreted epistemically, in which Prolog's fail is treated as unknown instead of false. In this interpretation:
- Succeeding to prove a goal G means that we know that G is true.
- Failing to prove a goal G means that we do not know anything about G.
There are two negations: There is a difference between not/1 and \+/1. In the epistemic interpretation, "\+" should be read as "unknown".
\+G
means we do not know G.
Succeeding to prove not(G) means that we know that G is false.
:- multifile not/1.
We waive the law of excluded middle. In our Prolog program it does not hold that G ; not(G).
Suppose is_big(john). If is_big(X) fails, it simply means that we don't know whether X is big.
Suppose that is_big(john,true) means we know that John is big. And is_big(john,false) means we know that John is not big. If is_big(john,_) fails, then we don't know whether John is big or not.
3.8.5Naming the parts of a list: head, tail, and butt
- "head" is the first element
- "tail" is everything but the head
- "butt" is the last element
3.8.6Defining your own operators
:- op(Precedence, Type, Name)
3.9Prolog as procedural programming language
Some ugly things are unfortunately necessary. There are always some dirty jobs in real-world programming. Example dirty jobs are input-output and error handling.
- 3.9.1Cuts(9w~1m)
- 3.9.2Speeding things up(43w~1m)
- 3.9.3Functional/expression style sometimes beats relational/unification style(93w~1m)
- 3.9.4Operators complicate parsing a Prolog source code(7w~1m)
- 3.9.5Zero-arity compound term(134w~1m)
- 3.9.6Some Prolog negation tricks?(62w~1m)
- 3.9.7Purifying Prolog?(11w~1m)
- 3.9.8States and dynamic predicates(86w~1m)
3.9.1Cuts
- slide 5-28, pitfalls in implementing abs with cut http://users.informatik.uni-halle.de/~brass/lp06/c5_propr.pdf
3.9.2Speeding things up
The first thing to do is to get an unbiased profiler.
(Is SWI-Prolog profiler unbiased?)
Profiling: finding where your program spends time; finding where it is slow; diagnosing slowness
To run your Goal
with profiling, simply query profile(Goal)
.
Profiling couldn't be any simpler than this!
3.9.3Functional/expression style sometimes beats relational/unification style
-- Functional/expression style
g (f0 x0) (f1 x1) (f2 x2)
% Relational/unification style
f0(X0, Y0), f1(X1, Y1), f2(X2, Y2), g(Y0, Y1, Y2, Z).
Example where functional style wins:
- string formatting
- number crunching
If backtracking isn't involved, functional style wins (is more concise than relational style).
If computation is reversible, relational style wins (half the amount of code of functional style).
We should use both styles depending on circumstances.
We can define a functional/expression/applicative/evaluative sublanguage in Prolog, roughly like this:
eval((A = B), Val) :- A = B, eval(B, Val), !.
eval(F, Val) :- callable(F), call(F, Val), !. % lots of hand-waving here
% etc.
Haskell is weak against the AST decoration problem. Dynamic languages (Scheme, JavaScript, Prolog) / gradual-typed languages (TypeScript) beat static languages (Haskell) on the AST decoration problem. How about Ocaml polymorphic variants?
Should we move from Prolog to Scheme/miniKanren or Mercury?
3.9.4Operators complicate parsing a Prolog source code
3.9.5Zero-arity compound term
SWI-Prolog extension compound_name_arity/3 vs ISO standard functor/3.27
- A function symbol with arity 2 looks like f(x,y).
- A function symbol with arity 1 looks like f(x).
- A function symbol with arity 0 should look like f().
Thus, indeed, SWI-Prolog's extension is the logical way, but unfortunately we are stuck for historical reasons. This makes sense if we are coming from mathematics, in which it is common to conflate constants and 0-ary function symbols. The formal logic literature conflates f() and f.
Problem arises when we want to distinguish between the x that is a variable reference and the x() that is a procedure call. We can introduce additional abstract syntax to wrap and disambiguate them: var(x) and call(x,[]).
It is embarrassing that we have known zero for at least 2,000 years and yet we still have problems with zero.
3.9.6Some Prolog negation tricks?
Prolog \+
can be used to limit the scope of unification, although not the scope of the variable itself. This exploits the fact that throw/1 does not backtrack in the way fail/0 does.
When using Prolog procedurally, we often want throw/1 instead of fail/0.
It makes more sense to design a procedural DSL on Prolog than to use Prolog itself procedurally.
3.9.7Purifying Prolog?
- assert/2 can be replaced with two parameters (state and next-state).
3.9.8States and dynamic predicates
Suppose that we want to write SQL connection pool. We need state. How do we write states in Prolog? Dynamic predicates is one way of having states in Prolog. The other is threading two extra state variables in each predicate that uses the state. But this time purism seems to lose. In the case of writing connection pools, procedural programming seems to be the paradigm that produces the most concise and understandable code.
A stateless system is of limited use: They can't store data!
4Graphical-user-interface programming
- 4.1<2019-04-02> What are the options?(143w~1m)
- 4.2Selecting a GUI library?(107w~1m)
- 4.3Enlarge the fonts(62w~1m)
- 4.4Saving PCE/XPCE by porting it as much as possible to pure Prolog?(116w~1m)
- 4.5Declarative GUI?(24w~1m)
- 4.6Using SWI-Prolog plgi pack(7w~1m)
4.1<2019-04-02> What are the options?
There are two options for doing GUI in SWI-Prolog:
- PCE: an abstraction layer like GNOME from the 1990s
- plgi28: a SWI-Prolog pack containing bindings to Gtk
The future of XPCE is uncertain, but all the SWI-Prolog IDE components use it.29 It works; it's just not shiny. Design sensibilities have changed due to new hardware.
PCE is an abstraction layer like GNOME. It has an object system like GObject, a drawing-primitive system like Gdk, and GUI toolkit like Gtk.
PCE is written in C.
XPCE is PCE + SWI-Prolog bindings.
:- use_module(library(pce),[
new/2
, free/1
, get/3
, send/2
]).
:- use_module(library(pce_util),[
send_list/3
]).
The predicates are:
- new(-Object, +Class) is det.
- free(+Object) is det.
- send(+Object, +MessageExp) is det.
- get(+Object, +MessageExp, -Result) is det.
A convenience predicate:
- send_list(+Object, +Slot, +Args) is det.
XPCE object expression (message expression?) syntax is documented in XPCE User Guide section 10.2 ("Executable objects")30:
@Name
global objectA ? B
obtainer ("getter" in Java parlance)
PCE is similar to C Gtk or Java Swing. They are all object-oriented.
4.2Selecting a GUI library?
Is GTK 3 here to stay? Is GIR (Gnome Introspection) here to stay? Is everyone switching from GTK to Qt?31
Why do everyone hate GTK?32 From a deleted user: "GTK is no longer an independent toolkit, it's built by Gnome developers, for Gnome developers. They change the API in every single new release, which breaks third-party applications, extensions and themes. They don't care about other projects and developers."
That is fatal. That is a deal-breaker for me. I want my software to work forever.
Qt uses C++, and C++ turns me off, but some people say that Qt is more stable and C++ is a mature language.
4.3Enlarge the fonts
XPCE was made in the 1990s when 800x600 screens were common. In 2019, 1920x1080 screens are common.
The easiest way to set up the XPCE Defaults file is by PceEmacs.
?- emacs.
Edit > Editor preferences
Increment each number in "display.system_fonts" chain by 2 (thus replace 12 with 14, replace 13 with 15, and so on).
Save the file, exit PceEmacs, and restart the Prolog interpreter.
4.4Saving PCE/XPCE by porting it as much as possible to pure Prolog?
PCE/XPCE is surprisingly modern? PCE catch_all
is Ruby method_missing. But perhaps this is not surprising because both PCE and Ruby take something from Smalltalk, directly or indirectly.
Need to be done:
- Write a shorter user guide. Write about the things that the user really needs to care about. People are impatient. Life is short.
- Integrate XPCE documentation system and PlDoc documentation system.
- Make manpce use one frame instead of many frames. Compare GIMP before single-window layout.
Nice to have?
- Rewrite the C parts in ISO Prolog.
- Build on GTK.
One problem is that PCE is not Prolog-only. In principle, PCE may also be used with any host language, such as Lisp and C.
4.5Declarative GUI?
It is easy to model the static structure of a GUI:
window(main).
textbox(a).
textbox(b).
textbox(c).
contain(main,a).
contain(main,b).
contain(main,c).
It is harder to model the dynamic behavior of a GUI.
textbox_text(c,C) :-
textbox_text(a,A),
textbox_text(b,B),
string_concat(A,B,C).
constraint(text(c) = text(a) + text(b)).
Logical reactive programming?
4.6Using SWI-Prolog plgi pack
Before building on Debian/Ubuntu:
sudo apt-get install libgirepository1.0-dev
5Maintaining large knowledge bases
- 5.1A suggested way to use Prolog for programming in the large?(45w~1m)
- 5.2Disciplines for writing large maintainable Prolog knowledge bases(33w~1m)
- 5.3Writing extensible knowledge bases(16w~1m)
- 5.4Production Prolog(29w~1m)
- 5.5Testing(14w~1m)
- 5.6Why do we need predicates at all if we can do with one unary predicate?(177w~1m)
- 5.7Documentation system(26w~1m)
- 5.8Writing portable Prolog programs(180w~1m)
- 5.9How do we manage language complexity?(95w~1m)
- 5.10Not interesting?(20w~1m)
- 5.11Testing(58w~1m)
- 5.12Logtalk?(14w~1m)
- 5.13Logtalk vs library(record)?(9w~1m)
5.1A suggested way to use Prolog for programming in the large?
Begin by defining an ontology or domain-specific language. This is pure Prolog with declarative semantics.
Then specify a transformation or interpretation to reality.
Example: A functional programming language:
%% interpret(+Expression,-Value) is det.
interpret(write(A), Z) :- !,
interpret(A, A0),
write(A0),
Z = unit.
interpret(A+B, Z) :- !,
interpret(A, A0),
interpret(B, B0),
Z is A0 + B0.
interpret((A,B), Z) :- !,
interpret(A, _),
interpret(B, Z).
interpret(A, Z) :- number(A), !, Z = A.
interpret(A, Z) :- string(A), !, Z = A.
interpret(A, _) :- !, type_error(expression, A).
Always use explicit imports and exports. Help grep
help us.
5.2Disciplines for writing large maintainable Prolog knowledge bases
Some disciplines are required:
- Separate declarative and imperative codes.
- Avoid depending on module systems.
- Each declarative source file is a small ontology. Each imperative source file merges some ontologies.
5.3Writing extensible knowledge bases
- 5.3.1Multifile or parametrization-and-catamorphism?(13w~1m)
5.3.1Multifile or parametrization-and-catamorphism?
:- multifile foo_ext/1.
foo(A) :- foo_ext(A).
Catamorphism:
foo(F,A) :- call(F,A).
Don't multifile if clause order matters. Reloading changes clause order. http://www.swi-prolog.org/FAQ/Multifile.html
5.4Production Prolog
"Production Prolog" by Michael Hendricks; Strange Loop 2014 https://www.youtube.com/watch?v=G_eYTctGZw8
- This mentions "Mercury's bisecting debugger"
- mavis library for optional type declarations
- julian library for dates
- time/1 for measuring how long a goal takes
- library(spawn)?
5.5Testing
An example of unit testing is in test.pro
.
test(addition) :-
1+2 =:= 3.
test(multiplication) :-
2*3 =:= 6.
?- test_all.
What is this library for unit testing?33
5.6Why do we need predicates at all if we can do with one unary predicate?
:- op(600,xfy,:).
:- op(650,xfx,@).
invoke(father @ [abraham, isaac]).
invoke(father @ [abraham, ishmael]).
invoke(list_length @ [[], z]).
invoke(list_length @ [[_|A], N]) :-
invoke(list_length @ [A,N0]),
invoke(succ @ [N0,N]).
invoke(nat @ [z]).
invoke(nat @ [s(A)]) :- invoke(nat @ [A]).
invoke(succ @ [A, s(A)]) :- invoke(nat @ [A]).
We can even do module systems.
We can encode 1 module as 1 predicate.
module1(pred @ [Arg1, Arg2, ...]) ...
module2(pred @ [Arg1, Arg2, ...]) ...
We can encode all modules as 1 predicate. We can have meta-predicates. We can have variable-arity predicates.
invoke(module1:pred @ [Arg1, ...]) ...
invoke(module2(pred) @ [Arg1, ...]) ...
invoke(call @ [F|A]) :- invoke(F @ A).
We can do first-order logic with one predicate only and unlimited function symbols. We can convert predicates into function symbols: We can transform \( p_1(\vec{x}_1), \ldots, p_n(\vec{x}_n) \) to \( P(p_k, \vec{x}_k) \). This is like writing the interpretation function inside the formal system itself. This is still first-order logic.
Should a:b@c
be interpreted as (a:b)@c
(call a:b with arguments c) or a:(b@c)
(call b with context a and arguments c)?
Abstract terms. What if we write programs with only predicates and variables and no concrete terms? Why should we? Because it enables us to change the representation without changing the meaning of the program. It is the same as abstract data types in other languages.
We can see an as atom as a singleton predicate, that is, a predicate that is satisfied by one thing only, that is the atom.
5.7Documentation system
PlDoc <module> documentation should be taken to mean <file> documentation: It is files that are documented, not modules.
Compare: Logtalk documentation system34 and Logtalk documentation markup35.
5.8Writing portable Prolog programs
- 5.8.1Use Logtalk?(31w~1m)
- 5.8.2Which string representation should I use?(147w~1m)
5.8.1Use Logtalk?
Logtalk: "What an object encapsulates depends on the base programming paradigm where we apply object-oriented programming concepts."36
Object-orientation itself is not a paradigm, but something built on top of a paradigm.
5.8.2Which string representation should I use?
If you don't need to write portable Prolog programs, you can skip this section.
Unless you have to care about portability, use dedicated double-quoted string type (SWI-Prolog 7):
- "Strings are distinct from lists"37
- "Why has the representation of double quoted text changed?"38
- 2013 article "Strings in ECLiPSe 6.2, SWI-7 and YAP"39
- "With SWI-7 and ECLiPSe 6.2 string support has been harmonized, and YAP is expected to agree as well."
- "Agreed Common Functionality"
- "Situation before December 2013"
Non-answer: Edinburgh style: Double-quoted string as list of integer codes (default mode of SWI-Prolog 6.6.4 on Ubuntu 14.04): A string is represented as a list of character codes. This was in 1993 ISO standard draft40, but this wasn't in the final version? Example: "aaa" = [97,97,97]
. But this behavior changed in SWI-Prolog 7.
Non-answer: Double-quoted string as list of one-character atoms. A string is represented as a list of one-character atoms. Example: "aaa" = [a,a,a]
.
5.9How do we manage language complexity?
We use context to disambiguate sayings in natural languages. For example, "man" can mean a male human or to station people at some places as in "man the guns" or "unmanned vehicle". We use "table" to mean a flat surface or a data set shown in columns and rows, depending on context.
Ad-hoc overloading is an example of this in programming languages. We use the same procedure name but different parameter types.
But ad-hoc overloading quickly becomes confusing? Also, what is the philosophical/mathematical foundation of ad-hoc overloading? Is it an engineering kludge?
5.10Not interesting?
Sterling & Yalçinalp 1996 [27] presents the logic programming analog of the Gang of Four object programming design patterns.
5.11Testing
The initial idea of "prorogued" programming [1] is to use the user as an interactive dummy implementation of stub methods. The stub implementation is "ask the user for what the return value of this stub method should be". "Prorogue" is a rare English word meaning prolong or extend41. But that is not all; types can be prorogued too.
5.12Logtalk?
"Strong motivation also come from my frustration with Prolog shortcomings for writing large applications."42
5.13Logtalk vs library(record)?
SWI-Prolog library(record)43 is similar to Racket struct44.
6Logtalk
The problem with Logtalk: too much documentation, and unclear which one is authoritative; no authoritative documentation for onboarding new users. Two tutorials and one handbook45, and a quick start and a tutorial46. Which one am I supposed to follow? More text does not mean better documentation.
- 6.1How do I start using Logtalk?(9w~1m)
6.1How do I start using Logtalk?
Git clone47.
Set up bashrc.
swilgt.sh48
7Ugly things, awkward squads, states and errors
Simon Peyton-Jones [22] calls these the "awkward squad": input/output, concurrency, exceptions, and foreign-language calls.
- 7.1Effects, side-effects, and errors(338w~2m)
- 7.2Error handling and logging(187w~1m)
7.1Effects, side-effects, and errors
- 7.1.1An effect is what?(335w~2m)
7.1.1An effect is what?
What is an "effect"?
What is a "side-effect"?
Does "side-" imply undesirability?
Isn't memory allocation an effect?
What is a "side-effect"? Wikipedia4950 is inconclusive.
The "side" in "side-effect" implies that there are effects and main-effects, and that side-effects are unintended, unrelated, or unwanted. The effect of running a program is the change of the state of the universe that results from executing that program. In medicine, a side effect is an unintended effect, not necessarily bad51. Thus, there is a parallel between chemists-and-drugs and programmers-and-programs: the designer of a drug (the programmer of a program) intends that taking the drug (running the program) accomplishes the main-effect, but reality is a bitch.
What is our intention when we write a program such as a Haskell program inc x = (x :: Integer) + 1
? Our intention is that it increments an integer, for every integer, which is mathematically trivial but physically impossible. The side-effects are: heating up the CPU, taking up some memory, taking up some time. We certainly did not intend to heat up the CPU; therefore such heating is a side-effect. Thus the main-effect is the denotation (the mathematical meaning) of the program, and every implementation detail is a side-effect.
Thus "side-effect" means an effect that we failed to foresee, because the complexity was too much for us.
Side-effects may be fatal.
Spectre/Meltdown are side-effects in that sense. The chip designers sacrificed understandability for speed.
There is also the phrase "algebraic effect".
We have to distinguish between a program and a machine running the program. A program does not run by itself. A machine runs a program. A program describes a computation. The machine performs the computation. A program is passive. A machine is active. A program exists in idea-world. A machine exists in material-world. A machine affects reality according to the program that the machine is running. The question: which is the cause of the change in reality: the machine or the program?
If we assume free will, then our thought causes our behavior, and our behavior causes something in the material-world.
7.2Error handling and logging
- 7.2.1Fail, throw, stack traces(57w~1m)
- 7.2.2Structured logging(128w~1m)
7.2.1Fail, throw, stack traces
Two options: throw or fail.
If backtracking doesn't make sense, then throw, don't fail.
person(joe).
pair_first_second(pair(A,_), A, B).
Should person(1)
fail or throw? Should pair_first_second(foo)
fail or throw?
Fail means try the next alternative.
If you want throw/1 with stack trace, you must write it like throw(error(Something, _))
.
A function should always throw and not fail, when an argument has a wrong type.
negate(A,B) :- integer(A), !, B is -A.
negate(A,B) :- integer(B), !, A is -B.
negate(A,B) :- throw(error(negate(A,B),_)).
- https://wiki.colby.edu/display/~amvartan/Exception+and+Error+Handling+in+Prolog
- https://stackoverflow.com/questions/32968148/why-throw-an-exception-in-prolog-instead-a-simple-fail
7.2.2Structured logging
This is how we log messages in Prolog:
- Design a term that represents the meaning of the message.
- Call
print_message(Kind,Message)
where Message is that term. - Extend
prolog:message//1
to translate that term to string.
% Syntax:
prolog:message(Term) --> Lines.
% Example:
prolog:message(Term) -->
[ 'The term is ~q.'-[Term] ],
[ 'This is the second line in the message.' ].
Syntax description:
- 'Lines' is a list of 'Line's.
- A 'Line' has this shape:
- Format-Args: 'Format' and 'Args' are the same arguments accepted by format/2.
- Terms of other shapes are converted to string.
- A 'Line' has this shape:
The printed message is the concatenation of all 'Line's.
TODO:
- How do we log to file?
- How do we rotate log files?
References:
- Anne Ogborn's "Printing Messages in SWI-Prolog"
- http://www.swi-prolog.org/pldoc/man?section=printmsg
- http://www.swi-prolog.org/pldoc/man?section=debug
- https://www.metalevel.at/prolog/business
Usability issues:
- Where is
prolog:message//1
documented? I found that by looking at others' source code. There does not seem to be any documentation, or if there is, then it is at the wrong place. - Why do we require people to understand DCG rules before they can use the messaging system?
8Object-logic programming?
8.1Can we model objects with identities without unique name assumption?
8.2How do we do/make/model objects and properties in Prolog?
"From a logical point of view, an object, the basic abstraction unit, has a natural interpretation as a logic theory: an object is simply a collection of axioms which describe what is true about the object itself." [5] (emphasis mine)
An object is something with identity. In Prolog, we represent identity with the unique name assumption. Each object has a unique surrogate primary key. Usually this key is a Prolog atom.
- 8.2.1Analogy: adding objects to C(360w~2m)
- 8.2.2One-property-one-predicate representation of objects(38w~1m)
- 8.2.3OPV (object-property-value) representation of constant objects(10w~1m)
- 8.2.4Representation(131w~1m)
8.2.1Analogy: adding objects to C
In C we can have OOP by adding one "this/self" parameter as the first parameter of each method. I think it is also possible in Prolog. But should we?
object_class(alice, person).
object_class(bob, person).
object_property_value(alice, name, "Alice").
object_property_value(bob, name, "Bob").
person(alice).
person(bob).
person_name(alice, "Alice").
person_name(bob, "Bob").
Do we want to parameterize the class? Note that in Prolog unifying parameters is easier than unifying predicate names. That is, we cannot write P(A) = Q(A)
where P and Q are variables.
"Mapping Objects to Persistent Predicates" https://pdfs.semanticscholar.org/f1ec/9e0e24faa1332d0cb60149e1d633b8d2509e.pdf
Should we write our DSL in Twelf instead of Prolog? http://twelf.org/wiki/LF
"Objects with logic" 1990 https://dl.acm.org/citation.cfm?id=100368
The difference between object and value is that an object has identity.
Must everything have a name?
An object has properties. A property is a key-value pair.
There are several ways to represent such objects in Prolog.
The 1-object-1-term representation represents an object as a ground term. There are two choices for such term: (1) a Prolog functor whose arity is the object's property count, or (2) a list of key-value pairs. The meaning of such representation is that iff the list L contains K-V, then the represented object has a property K whose value is V.
The 1-property-1-predicate representation represents each property as a predicate, but this requires unique surrogate naming of the object for identification: object_property1(O,P). object_property2(O,P).
It is surprising that database normalization theory explains some characteristics of good Prolog code.
Example: Suppose that there are two people Alice and Bob.
The question: is the object an entity or a value? An entity has identity. A value does not have identity. A natural number does not have an identity. A person has an identity. Two people may have the same name while still being two different people. The same natural number may be referred with a Arabic numeral or a Chinese numeral, but both of them refer to the same natural number.
The 1-object-1-term representation:
[name-"Alice", birthdate-date(1990,1,1), pets-[cat,dog]]
[name-"Bob", birthdate-date(1990,1,1), pets-[cat,dog]]
The 1-object-1-predicate representation:
person([name-"Alice",birthdate-date(1990,1,1)).
person([name-"Bob",birthdate-date(1990,1,1)]).
The 1-property-1-predicate representation (is this database in sixth normal form?):
person_name(alice,"Alice").
person_pet(alice,cat).
person_pet(alice,dog).
person_name(bob,"Bob").
Note that we do not write person_pets(alice,[cat,dog]).
The ontological representation: kind_surrogate_property_value(person,alice,name,"Alice"). kind_surrogate_property_value(person,alice,birthdate,date(1990,1,1)).
The parameter O serves as an internal name. The equality of that parameter determines the identity of the represented object.
Two objects can be equal but not identical.
A value has no identity. An object has an identity.
Iff object_property(O,P) is provable, then object O has property P.
Object-oriented programming in Prolog? https://stackoverflow.com/questions/28154041/objected-oriented-programming-in-swi-prolog
8.2.2One-property-one-predicate representation of objects
Another core idea is the one-property one-predicate representation, with surrogate primary keys. This enables us to represent objects in Prolog. Objects have identities. Two objects are identical iff their identifiers (primary keys) are equal. Example:
person(PersonId)
person_name(PersonId, Name)
person_birthdate(PersonId, BirthDate)
8.2.3OPV (object-property-value) representation of constant objects
Objects without mutation. Immutable objects.
8.2.4Representation
A class C has properties P1, P2, P3, etc. How do we represent an instance of C in Prolog? There are at least two ways: many-predicates and one-term.
The many-predicates representation makes it easy to add derived properties. One predicate represents one property. This is similar to 6NF (sixth normal form) in database theory.
c_prop1(InstanceId, Prop1).
c_prop2(InstanceId, Prop2).
c_prop3(InstanceId, Prop3).
...
The one-term representation makes it easy to specify an instance. One term represents one instance. This is similar to 0NF/1NF (zeroth or first normal form) in database theory.
c(InstanceId, [
prop1 - Prop1,
prop2 - Prop2,
prop3 - Prop3,
...
]).
But we can combine both. We can translate an instance-wise representation to a property-wise representation:
:- discontiguous c_prop1/2, ..., c_propN/2.
c_prop1(InstanceId, Prop1) :- c(InstanceId, Props), member(prop1-Prop1, Props).
c_prop2(InstanceId, Prop2) :- c(InstanceId, Props), member(prop2-Prop2, Props).
c_prop3(InstanceId, Prop3) :- c(InstanceId, Props), member(prop3-Prop3, Props).
...
But the many-predicates representation is easier to refactor than the one-term representation.
Conclusions:
- A module may internally specify objects in the one-term (denormal-form) style, but should only export predicates in the many-predicates (normal-form) style.
- A translation should not import denormal-form predicates.
9Writing enterprise web applications
- 9.1Why do we model things?(5w~1m)
- 9.2Modeling the dynamic aspect of software systems as inter-agent dialogs(96w~1m)
- 9.3Why should we use a modeling language expressive enough to model itself?(39w~1m)
- 9.4Convenient Prolog HTML Expression(161w~1m)
- 9.5SQL-Prolog integration sketch(602w~4m)
- 9.6Relational-multidirectional-logic programming?(2w~1m)
- 9.7The operations(101w~1m)
- 9.8Idea: Write an SQL database explorer in Prolog.(53w~1m)
- 9.9Use Prolog for formal software requirement capture / modeling.?(133w~1m)
- 9.10Prolog revival attempt(19w~1m)
- 9.11Logic programming for software engineering?(5w~1m)
- 9.12How reliable is query-by-example?(4w~1m)
9.1Why do we model things?
http://www.dubberly.com/articles/models-of-models.html
9.2Modeling the dynamic aspect of software systems as inter-agent dialogs
We can think of a software system as the set of all possible dialogs between agents.
- Man queries machine.
- Machine queries man.
- Man commands machine.
- Machine commands man.
- Man queries man, man commands man, machine queries machine, machine commands machine.
An agent is a man or a machine. An agent is something that can cause something.
An agent may query another agent. An agent may command another agent.
People must have thought about this before.
"Behymer and Flach build on the idea of collaboration, proposing a model comprised of actors or 'agents', both human and 'automaton'."52
9.3Why should we use a modeling language expressive enough to model itself?
(Not yet answered.)
instance_of(O,C) means that O instantiates (is an instance of) C.
class_property(C,P) means that each instance of C has a property named P.
The constraint:
forall O C : instance_of(O,C), class_property(C,P) -> exists V : opv(O,P,V)
Class-property is its own meta-model.
class(class).
class_property(class, name).
class_property(class, property).
class(property).
class_property(property, name).
9.4Convenient Prolog HTML Expression
CPH stands for Convenient Prolog HTML. CPHE stands for CPH Expression. The source file is html_cph.pro
.
Before you use this library:
- We have only HTML 5 in mind. We do not handle DTD, SGML, XML, and all that stuffs.
- We require that the Prolog implementation have a dedicated double-quoted string type, in which a string is not a list of codes.
- We only write HTML and do not read HTML.
- We do not handle all tags. See is_tag/1 and is_empty_tag/1 in the source.
- We do not handle comments.
- We do not indent the HTML output. It is human-unreadable.
- Security notice: We only escape attribute values and text nodes. We do not escape attribute names and doctypes.
- Element names must be all-lower-case atoms.
<2019-03-29> Motivation: SWI Prolog 7.6.4 library(http/html_write)53 was made before double-quoted strings.
To understand the idea, see the following example translation.
The predicate cphe_string/2 translates CPHE to HTML like this:
p(class=foo, "Text", style="color:#f00;", strong("Strong"))
<p class="foo" style="color:#f00;">Text<strong>Strong</strong></p>
An example of a document:
[
'!doctype'(html)
, html(
head(
title("Title")
)
, body(
p("Paragraph")
)
)
]
Do not conflate atoms and strings. Atoms translate to empty elements. Strings translate to escaped texts.
9.5SQL-Prolog integration sketch
- 9.5.1The idea(291w~2m)
- 9.5.2Making it work(3w~1m)
- 9.5.3Making it fast(53w~1m)
- 9.5.4Incremental/progressive aggregation(98w~1m)
- 9.5.5What else? Other similar implementations?(43w~1m)
- 9.5.6More ambitions: all data sources are predicates, and predicates are iterators(48w~1m)
- 9.5.7SWI-Prolog, PostgreSQL, and ODBC(70w~1m)
9.5.1The idea
The source file is sql.pro
.
The initial key idea is a 1:1 mapping between SQL tables and Prolog predicates. But is it mapping to tables or to SQL SELECT queries? We can think of a table as a SELECT query. The key idea is a Prolog predicate that succeeds once for each row in a corresponding SQL table. What if we can access a SQL table as if it were a Prolog predicate?
It should be possible to make something like F# data provider but with Prolog predicates. It should be possible to make a Prolog predicate that fetches data when called.
The dream is seamless integration between Prolog and SQL databases. Seamless SQL-backed Prolog predicates.
Several design choices:
- seamless/proxy-predicate approach: a predicate that uses a connection pool; use "proxy" predicates with odbc_query/3; an SQL table with N columns is represented by a predicate with arity N
- dynamic-predicate approach: populate dynamic predicates with data from table
- optimizer-interpreter that works for both Prolog databases and SQL databases; an SQL table is modeled by a term table(Id,Cols)
- The "persistency" library for persistent dynamic predicates54
Warren 1999: "Prolog is an elegant language for database queries. In fact if one constrains Prolog programs to use only atoms, integers and reals (no lists or complex terms) and disallows recursive definitions, one gets a database language that is equivalent to a powerful subset of SQL."55
% employee(Id, Name, Age)
query :- interpret((table_row(employee,E), row_column_value(E,age,Age), Age >= 20)).
Models of SQL SELECT statements:
- select(Table, Columns, Opts) where Opts is the optional parts (WHERE clause)
- Column is an atom or an "Column as Alias"
select(information_schema:columns
, [table_name as table, column_name as column, column_type as type]
, [
where(column_type = "integer")
, order_by([asc(table)])
])
For testing (Do not do this on public/production server):
CREATE USER test PASSWORD 'test';
CREATE DATABASE test OWNER test;
Other systems:
- CQL56 (Constraint Query Language) encloses its DSL expression in braces.
"There have been some Prolog systems in the past that could store predicates on a file."57
An SQL table can be thought of as a predicate that only works with ground terms.
9.5.2Making it work
9.5.3Making it fast
We want to push the filter condition to SQL. We want to filter as close as possible to the source as much as possible. We want to minimize the amount of data transferred over the network. We want to move the computation? We want to run Prolog on the SQL database?
employee(E), employee_age(E,A), A >= 30
9.5.4Incremental/progressive aggregation
We often need to derive OLAP table from OLTP table. But PostgreSQL materialized view cannot partial-refresh.58 Often an OLTP table is an append-only log (but sometimes there is "backdating").
Often we want to speed up queries like this:
SELECT date, SUM(amount) FROM sale GROUP BY date;
We know that the query does not have to be recomputed because we know that there has been no changes to the past data in the source table.
But SQL is inconvenient, so we want to aggregate in the application and cache the result in an SQL table.
It should be possible to capture this architectural pattern in Prolog, and generate the implementation.
9.5.5What else? Other similar implementations?
Jarke, Clifford, Vassiliou 1984 [10]
"One of the things that ProLog by BIM had was the ability to have Prolog use Oracle or Sybase databases as if they were Prolog's own native database"59
XSB-ODBC may be similar to what I want.
9.5.6More ambitions: all data sources are predicates, and predicates are iterators
It is straightforward to generalize to other data sources: JSON, CSV, NoSQL, Redis, Lucene, etc. SLD resolution makes predicates behave as iterators.
Every object or table-row can be represented by a relation instance.
This is similar to F# type providers.
9.5.7SWI-Prolog, PostgreSQL, and ODBC
Install the Ubuntu 14.04 package odbc-postgresql
.
I want my application to self-contain its configuration. I don't configure ODBC INI files.
ODBC Data Source Name (DSN) connection string
Relevant commands: odbcinst -j
The file /etc/odbcinst.ini
contains a list of driver names.
SWI-Prolog CQL documentation doesn't inspire confidence. Draxler 1991 relates database table and Prolog predicate. CQL models SQL query in Prolog terms.
Sketches, as good as non-existent: PL/SWI-Prolog60, psqlog61, what62.
XSB-Prolog has viewsys and persistent_tables.63
9.6Relational-multidirectional-logic programming?
9.7The operations
The story does not end with development. After it comes operation. It's a boring task. But someone has to do it. Thus, how we make it as painless as possible?
- 9.7.1Devops, dependency, build system?(71w~1m)
9.7.1Devops, dependency, build system?
Prolog marelle, Haskell shake, build system?
- http://quietlyamused.org/blog/2013/11/09/marelle-for-devops/
- "there is already a configuration management language that is strongly influenced by Prolog and logic programming - Puppet - and the results are not that great" https://news.ycombinator.com/item?id=6701362
- really?
- The computer can't read your mind. You lie to the computer, it does what you told it to do. Don't blame the computer for your failing to tell the computer everything it needs to do the job.
https://cloudbootup.com/post/cloudy-with-a-chance-of-prolog.html
9.8Idea: Write an SQL database explorer in Prolog.
CLI interface without ncurses without pager. Imagine printing to paper like early Fortran/Unix/ed. Paper user interface.
- menu(KeyActionPairs).
- select database
- select schema
- show 10 rows of table, 15 chars per column, truncating long strings with ">"
- tput https://stackoverflow.com/questions/263890/how-do-i-find-the-width-height-of-a-terminal-window
- My 1920x1080 terminal has 191 columns and 53 lines.
- go up / back to previous menu.
9.9Use Prolog for formal software requirement capture / modeling.?
"Are there any standard Prolog knowledge bases available anywhere that have the same purpose as Cyc, namely to encode generally accepted common sense and human knowledge?" https://cs.stackexchange.com/questions/35237/open-standard-prolog-knowledge-bases
2004 "SweetProlog: A System to Integrate Ontologies and Rules" https://pdfs.semanticscholar.org/03c2/a0048a5845bb1f52462c4f26d7be0a929d7a.pdf
Prolog is better than Turtle. http://sujitpal.blogspot.com/2009/06/ontology-rules-with-prolog.html "I actually set out to learn Jena Rules using the Semantic Web Programming book as a guide. Midway through that exercise, it occurred to me that Prolog would be a cleaner and almost drop-in replacement to the rather verbose Turtle syntax. Apparently the Semantic Web community thinks otherwise, since Turtle stands for Terse RDF Triple language. I haven't actually used Prolog before this, although I've read code snippets in articles once or twice (but not recently), so the realization was almost like an epiphany."
https://www.cs.auckland.ac.nz/~j-hamer/07.363/prolog-for-se.html
http://ceur-ws.org/Vol-274/paper6.pdf
9.10Prolog revival attempt
Wielemaker & Angelopoulos 2012 "Syntactic integration of external languages in Prolog" https://pdfs.semanticscholar.org/35eb/0b9d6edc27dd4564d98b107fec08e45e36cd.pdf SQL-Prolog Draxler [2] NED [5]
9.11Logic programming for software engineering?
[5]
[13]
9.12How reliable is query-by-example?
https://en.wikipedia.org/wiki/Query_by_Example
10DSL, meta-programming, optimizing, checking, multi-paradigm, whatnot
- 10.1Ramble: Translating Prolog to native code?(183w~1m)
- 10.2Implicit state language?(3w~1m)
- 10.3<2018-11-30> Prolog needs static checking like Erlang Dialyzer.(34w~1m)
- 10.4Alternative declarative semantics(85w~1m)
- 10.5Meta-programming(26w~1m)
- 10.6Constraint logic programming(55w~1m)
- 10.7Advanced logic programming(20w~1m)
- 10.8Language-oriented programming, embedding a language in Prolog(149w~1m)
- 10.9Iterative deepening search with length/1(37w~1m)
- 10.10Prolog = Lisp + operators + reflection + backtracking(87w~1m)
- 10.11All state computations are pure in the bigger supersystem(28w~1m)
- 10.12Warren abstract machine(23w~1m)
- 10.13Attributed variables(20w~1m)
- 10.14Partial evaluation(59w~1m)
- 10.15Logic programming and compiler writing(26w~1m)
10.1Ramble: Translating Prolog to native code?
The idea is to relate a Prolog predicate and a C routine.
Every disjunct translates into one routine / basic block.
The current goal relates to the instruction pointer.
Proving a goal ~ calling a routine Conjunction of phrase ~ sequence of call Disjunction of clause ~ speculative parallel execution, for pure predicates only
p(A),q(A) can be optimized from O(PQ) time to O(max(P,Q)) time if we order the storage.
Intermediate language Compile by abstract interpretation unify(Var1,Var2) frame(Instrs) prove((A,B)) :- prove(A), prove(B).
A variable in clause head is implicitly universally quantified. A free variable in clause body is implicitly existentially quantified.
Prolog just-in-time compilation compile(GoalAst, Fragment) call(Fragment) Execute?
Compile prolog predicates, limited to u32 parameters. Normalize p(a). to p(A) :- A=a. If first arg is bound, use index. Else sequential scan. Subset of prolog. Focus on translation for performance. No dynamic predicates. Generate a c func for some predicate direction. plus_bbb plus_bbu … plus_uuu Add a state parameter for nondet predicate. (Next clause index to try). Initial value 0. p(A,B) :- B is A + 1.
Libjit vs llvm? mmap and mprotect
father_child(F,C)
bool father_child(termref F, termref C) { }
10.2Implicit state language?
interpret(state(S), S, S).
interpret(state_set(S), _, S).
interpret((A,B),S0,S2) :- interpret(A,S0,S1), interpret(B,S1,S2).
10.3<2018-11-30> Prolog needs static checking like Erlang Dialyzer.
SWI-Prolog has check library?
Is there a Prolog totality/determinism checker?
Prolog typechecking is vital to prevent stupid mistakes in a large knowledge base?
1997 inconclusive discussion "Prolog Type Checker" https://dtai.cs.kuleuven.be/projects/ALP/newsletter/archive_93_96/net/typing/types.html
10.4Alternative declarative semantics
- 10.4.1Prolog should use three-valued logic?(54w~1m)
- 10.4.2Declarative programming? Function arguments?(28w~1m)
- 10.4.3What?(3w~1m)
10.4.1Prolog should use three-valued logic?
Suppose that both A and B are unbound variables. Then:
A =
B= is unknown, but it's false in Prolog.A \
B= is unknown, not it's false in Prolog.
In that case, it is better for Prolog to throw an instantiation_error instead of failing.
Three-valued logic would simplify and elegantize constraint logic programming?
10.4.2Declarative programming? Function arguments?
The idea: A relation's parameter can be a unifiable logic variable or a beta-reducible lambda expression.
is_one(A : exp(integer)) :- A = 1.
?- is_one(0+1).
true.
f(A : var(integer)) :- A = 1.
?- f(0+1).
false.
TODO Compare various approaches such as LambdaProlog, Mercury, and Curry.
10.4.3What?
Porto 2011 [23]
10.5Meta-programming
<2018-12-06> Prolog is the best meta-language I have found so far. It is a good meta-language for defining other languages.
To define 'macros', use term_expansion
or goal_expansion
.
10.6Constraint logic programming
Why does use_module(library(clpfd)) increases loading time perceptibly?
Should we use clpfd #=/2 instead of is/2? But it's good to have minimal dependencies.
Motivation?
Consider this program for enumerating the duplicates in an array.
duplicate(F, I, J, A) :-
arg(I, F, A),
arg(J, F, A),
I \= J.
The compiler should be able to infer the constraints and use it to produce this, reducing the number of comparisons to half the original?
duplicate(F, J, K, A) :-
functor(F, _, N),
between(1, N, J),
between(J, N, K),
arg(J, F, A),
arg(K, F, A),
J \= K.
10.7Advanced logic programming
According to some curriculums, advanced logic programming includes SLG (tableau) resolution, constraint logic programming, and inductive logic programming.
10.8Language-oriented programming, embedding a language in Prolog
Advantages:
- Reuse all of Prolog.
- Concentrate on the abstract syntax and the semantics, and not on the surface syntax.
Disadvantages:
- No custom syntax error messages, because we embed our language in Prolog.
- Limited to Prolog syntax. No array index operator such as
a[i]
.
Several possibilities:
- Horn clauses.
- Custom terms with custom interpretation function.
The 2010 article "Using DSLs for Developing Enterprise Systems" pdf:
- It uses the terms "language engineer", "transformation specialist", and "business engineer".
- It defines several usage scenarios of DSLs.
- It defines five criteria for comparing DSL tools.
- It compares some DSL tools.
- It should have been a wiki article.
A relation can be thought of as an interpretation of function terms. For example, m0/2 and m1/2 give different meanings to the same function term f/1.
m0(f(X), Y) :- Y is X+1.
m1(f(X), Y) :- Y is 2*X.
Prolog is ideal for writing DSLs because:
- We can embed the abstract syntax in Prolog syntax. We can skip specifying the grammar and go directly to specifying the semantics.
- Specifying the semantics is straightforward.
exp_val(S, T) :- string(S), !, S = T.
exp_val(S, T) :- number(S), !, S = T.
exp_val(A+B, C) :- string(A), string(B), !, string_concat(A, B, C).
exp_val(A+B, C) :- number(A), number(B), !, C is A+B.
10.9Iterative deepening search with length/1
Prolog uses depth-first search. It isn't complete. (What does that mean?)
If you have a query goal(List)
where List
is a list, then you can query length(List, _), goal(List)
to make the search complete.
https://en.wikibooks.org/wiki/Prolog/Search_techniques
10.10Prolog = Lisp + operators + reflection + backtracking
Both Prolog and Lisp has terms, read, eval, write, and macros.
Prolog has read/1. Lisp has read.
Prolog has call/1. Lisp has eval.
Prolog has term_expansion/2. Lisp has defmacro.
Prolog has infix prefix, infix, and suffix operators. Lisp does not have them? Lisp is all prefix? There may be some extensions?
Operators facilitate human-reading but complicate machine-parsing.
If we are going to pick a high-level language, we should pick one that has solid mathematical foundation. But that is enough. How about language usability and toolchain?
10.11All state computations are pure in the bigger supersystem
Endofunction from state to state.
Side-effects are like weed: They are human-invented labels, a subjective teleological categorization without objective ontological existence.
10.12Warren abstract machine
"Goal: Adapting the Warren abstract machine to the LLVM IR machine model for later compilation." "Hassan Aït-Kaci's WAM book" 2018 https://www.researchgate.net/project/Compiling-Prolog
10.13Attributed variables
I feel that attributed variables seem to be an engineering hack without mathematical justification. It interacts badly with term-copying.
10.14Partial evaluation
A common way to make compiler is to use a parser generator and what?
A possibly better way is to write an interpreter and get a compiler for free by partial evaluation.
Writing an interpreter is much easier than writing a compiler.
"Partial deduction" is partial evaluation from logic point of view.
Jones, Gomard, & Sestoft 1993 book on partial evaluation [11]
10.15Logic programming and compiler writing
Warren 1980 "Logic programming and compiler writing" http://sovietov.com/tmp/warren1980.pdf
Hamel 2016 "Formal Methods: A First Introduction using Prolog to specify Programming Language Semantics" https://pdfs.semanticscholar.org/1c13/792241df9d5e002dab7a2515f11ad1fbc85e.pdf
11Theoretical foundations of logic programming
- 11.1Theories of truth(22w~1m)
- 11.2Semantics(50w~1m)
- 11.3Why does automatic theorem proving use resolution?(7w~1m)
- 11.4What is wrong with Prolog?(91w~1m)
- 11.5Is there a general-purpose relational programming language not restricted to databases?(11w~1m)
- 11.6Which point of view should we use: logic, set, relation?(33w~1m)
- 11.7Prolog vs datalog(8w~1m)
- 11.8How does Lambda-Prolog extend Prolog?(82w~1m)
- 11.9How do Lambda-Logic and Lambda-Prolog relate?(17w~1m)
- 11.10Predicate logic can be thought of propositional logic with parameters(47w~1m)
- 11.11Horn clauses, history, importance, why?(31w~1m)
- 11.12Why is Prolog a dynamic programming language?(75w~1m)
11.1Theories of truth
There are at least three theories of truth64. But there are more.65 There is also Tarski's model-theoretic theory of truth.
11.2Semantics
There are several semantics for logic programs:
- Tarski
- model
- Herbrand
- operational
Genesereth & Kao advocates using Herbrand semantics instead of Tarski semantics. They claim that Herbrand semantics is easier to teach.6667
Shieber et al. 1995 [25] p. 14 puts it eloquently: First-order terms "can be understood as abbreviations for the sets of all their ground instances".
11.3Why does automatic theorem proving use resolution?
11.4What is wrong with Prolog?
- 11.4.1The problem with var/1: non-commutativity and non-monotonicity(21w~1m)
- 11.4.2Why should a logic programming language be sound and complete?(17w~1m)
- 11.4.3How is Prolog unsound?(32w~1m)
- 11.4.4What is wrong with logic programming?(20w~1m)
11.4.1The problem with var/1: non-commutativity and non-monotonicity
Usually conjunction is commutative: \(a \wedge b \equiv b \wedge a\). But var/1 breaks that.
p(A) :- var(A), A = 1.
q(A) :- A = 1, var(A).
?- p(A).
A = 1.
?- q(A).
false.
11.4.2Why should a logic programming language be sound and complete?
Prolog is unsound. So what?
(example of Prolog's unsoundness?)
11.4.3How is Prolog unsound?
From [3]:
- "The absence of the occur check entails the unsoundness of the resolution strategy used by Prolog."
- "The main reason for this omission is a sensible gain in execution time."
11.4.4What is wrong with logic programming?
"What is Wrong with Logic Programming?" "A Deductive Solution to Mutable State and I/O" https://pdfs.semanticscholar.org/ca08/dcb9eddc1e7651509daac7fa02eddb7f675b.pdf
11.5Is there a general-purpose relational programming language not restricted to databases?
11.6Which point of view should we use: logic, set, relation?
A relation is not a mere set, but is a triple of domain, codomain, and mapping. Thus there is a type theory of relations.
11.7Prolog vs datalog
Prolog is top-down/backward-chaining. Datalog is bottom-up/forward-chaining.
11.8How does Lambda-Prolog extend Prolog?
Nadathur & Miller 1988 [20] justifies Lambda-Prolog.
"The language Lambda-Prolog extends the logic of Horn clauses by allowing the use of implication not just in clauses, but also in goals," among other things.68
"By moving away from classical logic, Lambda Prolog was able to expand to a much larger fragment of logic: higher-order hereditary Harrop formulas. This allows some features, e.g. modules, to be handled in a logical way as opposed to the ad-hoc way they are handled in Prolog."69
11.9How do Lambda-Logic and Lambda-Prolog relate?
How do Beeson 2004 [2] and Miller & Nadathur 2012 [18] relate?
11.10Predicate logic can be thought of propositional logic with parameters
This fragment looks like written by a programmer who does not know arrays or a logician who does not know parameters.
handsome_bob
man_bob
handsome_joe
man_joe
handsome_bob -> man_bob
handsome_joe -> man_joe
Then he learns about arrays and parameters, and he rewrites that to \( \forall x (handsome(x) \to man(x)) \).
11.11Horn clauses, history, importance, why?
<2019-04-13> It is a shame that Horn's paper "On sentences which are true of direct unions of algebras" is not freely available online. (Login-wall is not free.)
11.12Why is Prolog a dynamic programming language?
https://en.wikipedia.org/wiki/Dynamic_programming_language
Functionalities such as assert/1 and retract/1 are inherently dynamic.
Why use dynamic programming languages?
Dynamic does not mean lack of checking. We can write our own checker in Prolog.
Static language = dynamic language + checking
Static languages are usually translated (compiled) instead of interpreted.
The checking is part of the translation.
Writing an interpreter is much easier than writing a compiler because when writing an interpreter we can reuse all features of the meta-language.
12Artificial intelligence?
12.1Finding out what to ask; coming up with a question; machine scientist?
Suppose that:
- There is an agent \(A\) with goal \(G\).
- \(K\) is the entire knowledge of agent \(A\). This \(K\) may be thought of as a set of Horn clauses.
Define "hypothesis" as "something we don't know but should know"?
The questions:
- What question should the agent ask (and try to answer) in order to optimally increase the agent's knowledge?
- How do we craft/select/formulate hypotheses?
Intuitively, an agent gains zero knowledge by answering a question whose answer is already in its knowledge set.
12.2Logic of machine comprehension and machine translation?
We can imagine a relation internal_external(I,E) where I is an internal language of thought and C is an external language (natural language).
We can see that a relation like english_indonesian(EnglishWord,IndonesianWord) does not have any provisions for using context to disambiguate meanings.
12.3Advanced reasoning: non-monotonic logic, abduction, induction
https://book.simply-logical.space/part_iii.html
12.4<2019-04-16> Problem with OpenAI Gym
The OpenAI Gym70 overrepresents connectionists and underrepresents symbolists.
13What mess?
- 13.1Gospel(29w~1m)
- 13.2Alternative Prolog syntax?(6w~1m)
- 13.3What?(85w~1m)
- 13.4overview(1w~1m)
- 13.5what(8w~1m)
- 13.6what(1w~1m)
- 13.7what(55w~1m)
- 13.8whaaat(12w~1m)
- 13.9Reverse engineering?(34w~1m)
- 13.10Prolog, somewhat object-oriented, mapping from Java to Prolog(48w~1m)
- 13.11What? 99 Prolog problems?(23w~1m)
- 13.12Difference lists(66w~1m)
- 13.13<2018-10-20> How do we make sense of this counterintuitive module syntax?(11w~1m)
- 13.14Discover the wonderful world of Prolog / logic programming / relational programming(79w~1m)
- 13.15Making compilers(20w~1m)
- 13.16Declarative programming languages(30w~1m)
- 13.17Speculative(4w~1m)
- 13.18Resources for beginners?(11w~1m)
- 13.19Resources not for beginners(122w~1m)
- 13.20What?(583w~3m)
- 13.21The things we have to know(105w~1m)
- 13.22Drafts and archives of my correspondence with the Prolog community(150w~1m)
- 13.23Discourse is interesting(31w~1m)
- 13.24Unread(107w~1m)
- 13.25Reverse engineering with Prolog(19w~1m)
- 13.26Teachers who can't teach shouldn't teach, lest they condemn students to hatred(54w~1m)
- 13.27Reason for distinguishing atoms and zero-arity compound terms(28w~1m)
- 13.28Kowalski 1992 "Legislation as Logic Programs"(6w~1m)
13.1Gospel
If everyone could be 20x more productive using Prolog, then it is a sin to let them use Java or C++. It is a massive waste of human life.
13.2Alternative Prolog syntax?
Curry/ML-like syntax for Prolog?
append([],B,B).
append([H|A], B, [H|C]) :- append(A,B,C).
append [] B B.
append [H|A] B [H|C] :- append A B C.
13.3What?
Prolog web browser, prolog gui, prolog operating system, prolog system f, normal-order lambda calculus, Haskell in prolog
Prolog to glue Haskell, racket, typescript
"adding a search Path in SWI prolog" https://stackoverflow.com/questions/6334050/adding-a-search-path-in-swi-prolog
"The Mess We're In" by Joe Armstrong" https://www.youtube.com/watch?v=lKXe3HUG2l4 43:20 We assume that two files A and B are similar if size(compress(A)) is similar to size(compress(A++B)).
decompilation, reverse engineering
"J.P. Bowen, From Programs to Object Code and Back Again Using Logic Programming: Compilation and Decompilation, Journal of Software Maintenance: Research and Practice, Vol. 5, No. 4, pp.205-234, December, 1993" https://dtai.cs.kuleuven.be/projects/ALP/newsletter/archive_93_96/net/grammars/compiler2.html
13.4overview
https://www.ajibot.com/blog/overview-of-logic-languages
13.5what
Prolog clpq documentation doesn't mention multivariate optimization? https://stackoverflow.com/questions/27716598/constraint-values-on-local-variable
http://www.amzi.com/manuals/amzi/pro/ref_execution.htm
http://users.cs.cf.ac.uk/O.F.Rana/prolog/lectureP5/node3.html
https://coderwall.com/p/laduzw/how-to-measure-execution-time-in-swi-prolog
https://www.reddit.com/r/prolog/comments/9mxhbw/the_art_of_prolog_second_edition_is_available_as/
http://www.swi-prolog.org/pldoc/man?section=modes
13.6what
http://dbs.informatik.uni-halle.de/Lehre/LP09/c3_purep.pdf
http://fsl.cs.illinois.edu/images/9/9c/PrologStandard.pdf
13.7what
Read "The art of Prolog", second-order programming,
https://stackoverflow.com/questions/32835086/prolog-how-to-avoid-backtracking-without-cuts
Now I know this is false:
- Relational programming subsumes functional programming.
- Functional programming is a special case of relational programming.
- Every function is a relation.
Functional programming is more concise and readable than logic (relational?) programming when we are describing functions:
But we can translate a function to a deterministic (det) predicate in Prolog.
13.8whaaat
This marshallp guy is… inhuman? He uses Prolog for note taking! https://news.ycombinator.com/item?id=1142292
13.9Reverse engineering?
- 1992 "A Logic-Based Approach to Reverse Engineering Tools Production"
https://pdfs.semanticscholar.org/4882/9fd716349ff586e21e9277890989daa0e916.pdf
Prolog-COBOL stuff
- 1991, Using Prolog for Reverse-Engineering and Validation
http://www.academia.edu/2493008/Using_Prolog_for_reverse-engineering_and_validation
- 1994, "Reverse Engineering of COBOL Programs into Prolog Programs"
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.5073&rep=rep1&type=pdf
- 1992, "The Art of Computer Un-Programming: Reverse Engineering in Prolog"
http://www.academia.edu/1413561/The_art_of_computer_un-programming_Reverse_engineering_in_Prolog
http://www.academia.edu/1413561/The_art_of_computer_un-programming_Reverse_engineering_in_Prolog
13.10Prolog, somewhat object-oriented, mapping from Java to Prolog
Prior arts: 2017 "Mapping Objects to Persistent Predicates" https://pdfs.semanticscholar.org/f1ec/9e0e24faa1332d0cb60149e1d633b8d2509e.pdf
http://ceur-ws.org/Vol-274/paper6.pdf
Every Java class instantiation expression becomes a Prolog compound.
% From Java expression: new Class_name(field_1, field_n)
class_name(Field_1, ..., Field_N)
Every Java class instantiation statement becomes a Prolog fact.
% From Java statement: Class_name instance_name = new Class_name(field_1, field_n)
Class_name(Instance_name, Field_1, ..., Field_N).
Example 2010 "Simulating BPMN Models with Prolog"
final class Car {
final String brand;
final int year;
// constructor omitted
}
Car a_car = new Car("Toyota", 2000);
becomes
car(a_car, [brand('Toyota'), year(2000)]).
% or
car(a_car, 'Toyota', 2000).
% or
car(a_car, car('Toyota', 2000)).
Large-scale Prolog? 1991 "Efficient Access To Large Prolog Knowledge Bases" https://link.springer.com/chapter/10.1007/978-3-7091-7555-2_26
13.11What? 99 Prolog problems?
There is the 99 Prolog problems. But what if you we are not undergraduate students with too much free time?
13.12Difference lists
- Who invented difference lists when?
A "difference list" is a term of the form A - B
where A
is a list and B
is a list.
A difference list represents a list.
The difference list A - []
represents the list A
.
- https://en.wikipedia.org/wiki/Difference_list
- https://en.wikibooks.org/wiki/Prolog/Difference_Lists
- Difference list has constant-time append. Ordinary list has linear-time append.
- https://wiki.haskell.org/Difference_list
- "Whether this kind of difference list is more efficient than another list representations depends on usage patterns."
- http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html
13.13<2018-10-20> How do we make sense of this counterintuitive module syntax?
13.14Discover the wonderful world of Prolog / logic programming / relational programming
- 13.14.1Symbolic AI is the easiest AI approach.(53w~1m)
- 13.14.2Dreams(16w~1m)
13.14.1Symbolic AI is the easiest AI approach.
- Connectionist AI (neural networks) excels at tasks that are difficult to describe in formal logic.
- Symbolic AI (Prolog) is much more understandable and predictable than connectionist AI.
- Understanding connectionist AI requires probability, statistics, and real analysis.
- Why not both? 2017 article "SLDR-DL: A Framework for SLD-Resolution with Deep Learning" https://arxiv.org/pdf/1705.02210.pdf?
13.14.2Dreams
- offload/scale/formalize thinking/cognition
- transform reasoning into data entry
- brain prosthetics; cognitive prosthetics
- Leibniz, "Let us calculate!", calculus ratiocinator
- probabilistic logic programming
- https://softwareengineering.stackexchange.com/questions/275680/the-dream-of-declarative-programming
13.15Making compilers
- https://www.reddit.com/r/ProgrammingLanguages/comments/9em9jf/future_directions_for_optimizing_compilers/
- "Future Directions for Optimizing Compilers" https://arxiv.org/abs/1809.02161
"Universal-transpiler" may be similar to what we want.
- "Universal-transpiler"
- https://github.com/jarble/transpiler
- it also has links to similar projects
- http://www.swi-prolog.org/pack/list?p=transpiler
- https://github.com/jarble/transpiler
13.16Declarative programming languages
Declarative Programming Languages, functional logic programming, two ways it is done (narrowing and residuation); definitional programming, GCLA language (separate definition and control)
- 1995, "Functional Logic Programming in GCLA", pdf
13.17Speculative
- 13.17.1Fast logic programming?(3w~1m)
- 13.17.2Lambda-prolog?(2w~1m)
13.17.1Fast logic programming?
- https://www.reddit.com/r/ProgrammingLanguages/comments/9fgv3v/can_logic_programming_execute_as_fast_as/
- https://stackoverflow.com/questions/23711790/comparision-of-abstract-machines-for-execution-of-prolog
13.17.2Lambda-prolog?
- lambda-prolog http://www.lix.polytechnique.fr/~dale/lProlog/
13.18Resources for beginners?
13.19Resources not for beginners
- 1990 book "The craft of Prolog" by Richard A. O'Keefe
- from the preface: "There are a lot of introductory Prolog books around. This is not one of them. Think of it as "second steps in Prolog". If you have already read one of the introductory books, if you have taken an introductory course on Prolog, if you have written one or two Prolog programs, and if you are wondering why it is still hard to writegood Prolog programs, this book is meant to help you. The purpose of the book is to show you how you can write Prolog programs that work, that don't take an unreasonable amount of time, and that are clean enough to show to your friends."
13.20What?
- 13.20.1What are these trying to say?(156w~1m)
- 13.20.2Books?(428w~3m)
13.20.1What are these trying to say?
- 1991 article "Logic Programming, Functional Programming, and Inductive Definitions" https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-205.pdf
- "The unification of logic and functional programming, like the Holy Grail, is sought by countless people"
- "More generally, we suggest that the traditional paradigm — logic programming as first-order logic — is seriously out of step with practice. We offer an alternative paradigm. We view the logic program as an inductive definition of sets and relations."
- "To justify the Closed World Assumption, we propose that logic programs should be viewed as inductive definitions, not as first-order theories. Some people refuse to abandon the dream of programming in first-order logic. But we have to ask whether this dream is possible — even whether it is desirable. The first-order paradigm does not deal adequately with negation in databases, and seems to be an unreliable guide in research on program correctness and language design. Inductive definitions are more fundamental than first-order logic, and perhaps easier to understand."
13.20.2Books?
- 1995 book "Prolog Programming in Depth" http://www.lsv.fr/~reichert/Enseignement/2012/PPL/Prolog_Programming_In_Depth.pdf
- 1.16 Styles of encoding knowledge, p. 28
- parent, male, female vs. father, mother
- "Which style is computationally more efficient depends on the kinds of queries to be answered."
- "Unlike other knowledge representation languages, Prolog does not force the knowledge base builder to state information in a particular logical style. Information can be entered in whatever form is most convenient, and then appropriate rules can be added to retrieve the information in a different form."
- "We could use a 'data-record' format to encode the family tree like [person(Name,Sex,Father,Mother)]"
- "The only advantage of this style is that the multi-argument facts are often easy to generate from conventional databases, by simply printing out the data in a format that conforms to Prolog syntax."
- 5.12 Grand Finale: Reading a Lotus Spreadsheet, p. 148
- 5.13 Language and Metalanguage, p. 153
- "A Prolog program can extend and modify the inference engine that controls program execution. Thus, the language can change itself in ways that go beyond superficial syntax."
- Really? How?
- "A Prolog program can extend and modify the inference engine that controls program execution. Thus, the language can change itself in ways that go beyond superficial syntax."
- 5.17 Intensional and Extensional Queries, p. 159
- 5.19 Giving Meaning to Operators, p. 163
- "How to make the ampersand mean 'and' in Prolog"
- 5.20 Prolog in Prolog, p. 165
- "Meta-interpreter for Prolog"
- 5.21 Extending the inference engine, p. 167
- biconditionals
- 11 Defeasible Prolog, p. 347
- 11.1 Nonmonotonic reasoning and Prolog, p. 347
- "If our reasoning is monotonic, the set of conclusions we draw from the information we have only gets larger as we get more and more information. Once we reach a conclusion, no additional information will cause us to reject it. When our reasoning is nonmonotonic, we may reject an earlier conclusion on the basis of new information."
- "Human reasoning is notoriously nonmonotonic. We make plans based on what we expect to happen, but we constantly revise our expectations, and our plans, as events unfold."
- "The Prolog inference engine is nonmonotonic because of the way it handles negation."
- Why is "defeasible" not spelled "defeatable"?
- 11.2 New syntax for defeasible reasoning, p. 348
- "Although Prolog can perform some kinds of nonmonotonic reasoning, Prolog rules are not defeasible."
- "Some instances of defeasible reasoning cannot be reproduced in ordinary Prolog."
- "What we need is a new way to represent defeasible rules and presumptions and an inference engine that knows how to use them. We also need a negation operator that is different from negation-as-failure so we can represent rules that tell us when something is positively not the case rather than just that we cannot prove that it is the case. These negative rules are needed to tell us when we have an exception to a defeasible rule, but they are desirable in their own right as well."
- The second sentence is too long.
- (I haven't read it.)
- 11.1 Nonmonotonic reasoning and Prolog, p. 347
- 1.16 Styles of encoding knowledge, p. 28
13.21The things we have to know
This chapter should not exist. The users have to know these, but when should we introduce these topics?
- operational semantics: how the Prolog program actually runs: depth-first search (brute force)
- how to get unstuck
- 13.21.1Some Greek words used in philosophy and programming(33w~1m)
- 13.21.2Modules?(28w~1m)
- 13.21.3Equalities and equivalences?(10w~1m)
13.21.1Some Greek words used in philosophy and programming
"ontos" is "(of) being".
"episteme" is "knowledge".
"logos" is "word", "theory".
Thus, "ontology" is "theory of being", and "epistemology" is "theory of knowledge". They are two branches of philosophy.
13.21.2Modules?
Prolog syntax for use_module is documented in LoadLibrary FAQ, not in the documentation for use_module/1. The library
alias is defined in file_search_path/2.
swipl: use -s
instead of -l
http://www.swi-prolog.org/pldoc/man?section=cmdline
13.21.3Equalities and equivalences?
What is the difference: , ~==~, ~
:=~, is
13.22Drafts and archives of my correspondence with the Prolog community
- 13.22.1Avoiding future SWI-Prolog pack nightmare(19w~1m)
- 13.22.2<2019-04-07> Improving contributor guide discoverability(36w~1m)
- 13.22.3<2019-04-08> Open-source donation does not work(88w~1m)
13.22.1Avoiding future SWI-Prolog pack nightmare
Semantic Web should be applied to make SWI-Prolog packs searchable and manageable.
SWI-Prolog packs need curation/vetting/testimony/promotion.
13.22.2<2019-04-07> Improving contributor guide discoverability
I wrote73:
The information, the person, and the task must be near to each other in space and time. Ideally, the information is presented right where people need it when they need it.
13.22.3<2019-04-08> Open-source donation does not work
Jan Wielemaker on swipl-devel pull-request 45974:
I'd drop donating. We've done that in the past. It is mostly hassle that is nice to buy some infrastructure, but doesn't cover salaries. So far we managed to get the required infra structure sponsored directly.
Indeed. It's like digital busking. It is extremely simple to throw money physically at physical buskers. But how do we throw money digitally at people? In 2019 digital money donation is so much hassle and so complex that few actually donate money digitally.
13.23Discourse is interesting
Discourse75 reputation system is an example of using software to enforce a policy that creates a system that self-heals against attacks.
I should put it in my open-source page somewhere.
13.24Unread
"Here I make use of a feature of the SWI Prolog REPL - prefixing a variable with $ will use the value that was assigned to that variable in a previous REPL command." https://bluishcoder.co.nz/2018/09/24/concurrent-and-distributed-programming-in-web-prolog.html
"Notes for a Tutorial on Abstract Interpretation of Logic Programs" https://www.reddit.com/r/prolog/comments/98cqie/notes_for_a_tutorial_on_abstract_interpretation/
"Prolog and the Database Of The Future" https://www.reddit.com/r/prolog/comments/99xwue/prolog_and_the_database_of_the_future/
"fizz: an experimental language/runtime for cognitive architectures (version 0.4)" https://www.reddit.com/r/prolog/comments/9c5evc/fizz_an_experimental_languageruntime_for/
"A Data-parallel Implementation of Prolog: : a simple model for parallel execution suitably restricted to guarantee efficient parallel execution" https://www.reddit.com/r/prolog/comments/9cbqj0/a_dataparallel_implementation_of_prolog_a_simple/
"Reform Prolog is an (dependent) AND-parallel system based on recursion parallelism and Reform compilation." https://www.reddit.com/r/prolog/comments/9ceohz/reform_prolog_the_language_and_its_implementation/
https://www.reddit.com/r/prolog/new/
1997 "FAQ: Prolog Resource Guide 1/2 [Monthly posting]" Where is the most recent version? http://www.faqs.org/faqs/prolog/resource-guide/part1/index.html
13.25Reverse engineering with Prolog
"Using Logic Programming to Recover C++ Classes and Methods from Compiled Executables. They use XSB Prolog"7677
13.26Teachers who can't teach shouldn't teach, lest they condemn students to hatred
People hate math because they are unfortunate enough to be taught by teachers who can't teach.
People hate Prolog because they are unfortunate enough to be taught by teachers who can't teach.
Those students grow up to be adults with atrophied minds condemned to mediocrity.
13.27Reason for distinguishing atoms and zero-arity compound terms
Such separation helps us write a language interpreter in which foo
means a variable value and foo()
means a function call.
13.28Kowalski 1992 "Legislation as Logic Programs"
https://www.doc.ic.ac.uk/~rak/papers/law.pdf
14Rethinking module systems, especially of Prolog
Miller 1986 [17] has what we want: implication as local scoping.
- 14.1What are the problems of existing module systems?(27w~1m)
- 14.2What problems are modules trying to solve?(614w~4m)
- 14.3How should modules and meta-predicates interact?(173w~1m)
- 14.4Designing the module system(821w~5m)
- 14.5Organizing and loading Prolog source files without name clashes(202w~2m)
- 14.6from module.md (Designing module systems)(908w~5m)
- 14.7<2019-04-02> The implementation? Draft: A clash-free module system(476w~3m)
- 14.8Implementing modules(259w~2m)
- 14.9Brain dumps(8w~1m)
- 14.10Operators and adaptive grammar(123w~1m)
14.1What are the problems of existing module systems?
A module system is often an afterthought to a core language.[18]
Chapter 6 of [18] contains a desiderata for module systems.
14.2What problems are modules trying to solve?
- 14.2.1Two problems that modules are trying to solve(64w~1m)
- 14.2.2Modules are for humans(48w~1m)
- 14.2.3Why do name clashes happen?(34w~1m)
- 14.2.4How does name clashes happen?(5w~1m)
- 14.2.5The key of avoiding name clashes: Things should not name themselves(116w~1m)
- 14.2.6How do module systems arise?(50w~1m)
- 14.2.7Secondary uses of modules(115w~1m)
- 14.2.8Modules as protection of internals?(108w~1m)
- 14.2.9What are hardware modules?(73w~1m)
- 14.2.10Ciao Prolog module system?(4w~1m)
14.2.1Two problems that modules are trying to solve
- our only mental weapon, to understand code and combat complexity, is divide-and-conquer and abstraction which is often somewhat hierarchical
- name clashes are bound to happen in a large software system
Modules reduce complexity by partitioning and independence. See Three Universal methods of reducing complexity from the course CA214 Systems Analysis and Design Page.
Which is essential: complexity management or namespacing?
14.2.2Modules are for humans
Computers don't need modules. All it needs is a sequence of machine codes.
Given enough memory, a computer can handle arbitrarily big programs.
Human uses modules for organizing things. Human uses modules to make machines separate compilation, speed up recompilation, and recompile a part of the program.
14.2.3Why do name clashes happen?
Natural languages also have name clashes.
English homonyms.
Why do we have homonyms?
We use language for practical purposes, not for philosophical purposes. Practically, conflating a thing and its representation makes life easier.
14.2.4How does name clashes happen?
14.2.5The key of avoiding name clashes: Things should not name themselves
Names and referents should be separated.
Philosophically, a name of a thing must not be a property of the thing itself. A rock does not implore us to call it "rock". It is we who name it "rock". My name is "Erik", but you can name me anything, although calling me with any other name may fail to grab my attention.
If A uses B, then A names B, and B must not tell A what to name B.
Example agreement: JavaScript functions and modules don't have names. What has a name is the variable that refers to the function or to the module.
Example violation: C functions have names.
14.2.6How do module systems arise?
We are merrily writing codes until our program grows big and we have difficulty finding things. Then we feel that something has to be done.
We make module systems because we are humans with limited working memory. Our only weapon against complexity is divide-and-conquer and hierarchical abstraction/categorization.
14.2.7Secondary uses of modules
All other purposes such as encapsulation and protection are secondary while-we're-at-it additions.
- to separate or parallelize compilation
- to protect internal constraints/consistency, to prevent the user from using the module in an incorrect way not designed by the module creator [8]
C does not even try: leave it the programmer. C++ solution is better but not satisfactory: automatically prefix everything. JavaScript's solution is fundamentally better: the names of modules, classes and functions can be locally scoped.
Static typing helps name resoution by overloading like in Java and C++. But this only delays the problem: the types themselves can have clashing names.
For example, a car driver does not mess with the internals of the car engine while driving.
14.2.8Modules as protection of internals?
There are two opposing hypotheses:
- Good abstraction (implementation-hiding) increases robustness.
- All abstraction leaks, and the fix requires knowing the implementation.
For robustness, we want caller to depend only on public interface; we want to make the contract explicit.
Modules are for protecting internal assumptions? From [8]:
- "One difficulty in Prolog comes from the call predicate which interferes with the protection of the code, an essential task of a module system."
- "[…] to guarantee the semantics of the predicates defined in a library, a module system has however to strictly prevent any predicate execution not allowed by the programmer."
- "The algebraic approach defines module calculi with operations over sets of program clauses"
14.2.9What are hardware modules?
An example is an integrated circuit, a black box that performs a high-level function. Thinking in terms of op-amps instead of in terms of Maxwell's equations. The essence of hardware module is abstraction. A module is a unit of reasoning. If a module breaks down, the user replaces the entire module. The module creator designs the module such that the module user can think at a higher level of abstraction.
14.2.10Ciao Prolog module system?
[4]
14.3How should modules and meta-predicates interact?
- 14.3.1What is the name of a thing?(18w~1m)
- 14.3.2What should call/1 mean? What is the reason for atom-based module systems?(151w~1m)
14.3.1What is the name of a thing?
The question boils down to "What is the name of a thing?"
14.3.2What should call/1 mean? What is the reason for atom-based module systems?
We propose two principles for call/1: transparency and lexical binding, because they simplify reasoning about the program.
Without modules, the meaning of call(foo(A))
is straightforward: It is as if the programmer had written foo(A)
instead.
Transparency means that textually replacing call(A)
with A
in the source code should preserve the meaning of the program. The semantics of call(A)
should be the same as the semantics of A
.
Lexical binding means that we should be able to determine the meaning just by looking at the source code without running the program.
An atom-based module system is one way of satisfying those principles. But a predicate-based module system is more amenable to compilation?
qname_module_name(QualName, Module, Name)
Lexical binding is a consequence of the principle of least surprise: do what most users most likely expect. But can the principle of least surprise clash with the principle of mathematical elegance?
14.4Designing the module system
- 14.4.1What is a module, functionally, relationally, and logically?(74w~1m)
- 14.4.2How does a module differ from dictionary, function, table, map, association?(177w~1m)
- 14.4.3Do not conflate modules and files(29w~1m)
- 14.4.4Should module names correspond to file names?(307w~2m)
- 14.4.5How do we design a module system that subsumes both atom-based and predicate-based module systems?(21w~1m)
- 14.4.6Anonymous predicates?(43w~1m)
- 14.4.7Prolog mixins(35w~1m)
- 14.4.8Component system with socket-plug metaphor(128w~1m)
- 14.4.9No separate header files(12w~1m)
14.4.1What is a module, functionally, relationally, and logically?
From functional programming perspective, a module is a function from name to value.
From relational programming perspective, a module is a functional relation between name and value.
From logic programming perspective, a module is a collection of Horn clauses.
Atom-based modules break those intuitions?
Thus in Prolog, if we have first-class relations, then we can have first-class modules.
Having first-class relation means using second-order logic. That is the M
in this example:
usefoo :-
import("foo.pro", mypred, M),
M(bar).
% But that can be made first-order?
usefoo :-
import("foo.pro", M),
M:bar.
14.4.2How does a module differ from dictionary, function, table, map, association?
What can we do with zero module? We can create the empty module. What can we do with a module? What can we do with many modules?
Equality vs identity: Must a programming language separate equality and identity? Should two strings be equal, if they have different memory addresses but the same content?
Let \( D \) be the programming language's domain of discourse.
Let \( F(D) = D \to D \) be the set of every endofunction whose domain is \( D \). Let \( D \) be the smallest set such that \( F(D) \subset D \). Thus \( D \) is the least fixed point of \( F \).
A dictionary can be a finite function whose domain is a finite subset of \( D \).
A module can be modeled as a dictionary. A module can be modeled as a finite function \( N \to D \) where \( N \) is the set of names for which the module has an entry. A module can be modeled as an infinite function \( N \to D \) where \( N \) is the set of all possible names.
14.4.3Do not conflate modules and files
A module is the internal representation. File contains the external representation. The analogy: A module contains thoughts. A file countains writings representing those thoughts.
14.4.4Should module names correspond to file names?
If the relationship between a file and a module does not have to be 1:1, then complications arise.
We assume 1:1 relationship between files and modules.
Problems:
- M:N mapping between files and modules
- Name clashes
- Module instantiation
- Imports and dependencies
- I want to make many languages and interpreters, and I don't want to prefix each predicate: I want to write N interpret predicates, I don't want to write 1 langN_interpret for each N.
- A clashy-named old predicate is used a lot.
Why do we have modules if records suffice? An OCaml "functor" would then simply be a function from records to records.
OCaml has first-class modules, but can it import a file into a module? https://v1.realworldocaml.org/v1/en/html/first-class-modules.html
OCaml ties module name to file name. Is this bad? "Source files in OCaml are tied into the module system, with each file compiling down into a module whose name is derived from the name of the file." https://v1.realworldocaml.org/v1/en/html/files-modules-and-programs.html
What JavaScript does right:
- a module is a plain JavaScript object
- it is possible import a file into a module referred by a local variable
What Ocaml does right:
- local import
interpret(Language, Context, Expression, Meaning).
Some solutions that come to mind:
- Load module using gensym/2 if not current_module/2. The loader generates the name of the module that the file is loaded to. module/2 is anti-pattern.
- name mangling like what C++ does on top of C; generated module names
- Pengines to separate the worlds?
- Logtalk
We want to state these facts:
- This file imports predicate P from file F, because a predicate in this file calls/uses/depends-on that predicate P defined in that file F.
We came up with the import/2 directive.
Prolog expansion has some problems.78
Moura 2003 [19]: "The first time I felt the need for strong encapsulation features in Prolog was during my final year undergraduate project, in 1989."
This SWI-Prolog Google Groups discussion thread79 is relevant.
Module is about namespacing.
We want to say that "The mypred/3 in file1 is the same as the yourpred/3 in file2."
14.4.5How do we design a module system that subsumes both atom-based and predicate-based module systems?
A module system is a name-prefixing mechanism.
14.4.6Anonymous predicates?
- Do anonymous predicates subsume module systems?
- What may anonymous predicates look like?
It should be possible to talk about a predicate without naming it first.
p(A) :- A = 0 ; A = 1.
% vs
\ A :- A = 0 ; A = 1.
\( p(x) \equiv x=0 \vee x=1 \) vs \( \lambda x (x=0 \vee x=1) \).
How do we add anonymous relations/predicates to Prolog?
let p = \ A :- (A = 1 ; A = 2).
p(A) :- A = 1, A = 2.
14.4.7Prolog mixins
A Prolog mixin (mix-in) is simply an include file that adds features to the includer. Example, this mixin endows the includer with a static vocabulary about objects and properties, akin to object-orientation without method.
% object.pro
:- multifile opv/3.
get(O,P,V) :- \+ opv(O,P,V), throw... . % what?
get(O,P,V) :- opv(O,P,V).
14.4.8Component system with socket-plug metaphor
I need a component system for programming in the large. Prolog module system is a building block, but Prolog modules by themselves are not enough. Socket-and-plug metaphor fits nicely? The name tells it all: a socket is a female connector and a plug is a male connector, and we connect plugs to sockets, and Prolog should complain if it sees a socket that is connected not exactly once.
An input is a multifile predicate.
A pin is a Name/Arity term.
A plug exports symbols.
A socket imports symbols.
A module may have multiple plugs and sockets.
Pins are matched by NameArity. The ordering of pins does not matter.
A Prolog module system is either predicate-based or atom-based. XSB is atom-based. SWI is predicate-based. GNU Prolog does not have a module system.
14.4.9No separate header files
Separate header files are remnants of the big-design-up-front era.
14.5Organizing and loading Prolog source files without name clashes
Prolog multifile predicates can be used for dependency injection. Instead of importing a module, declare a multifile predicate and let the user link that predicate.
Prolog source files come in two kinds depending on how they are loaded: type-1 files and type-2 (module-free) files. In short, a type-2 file should not assume that the Prolog implementation has a module system, unless when defining meta-predicates. The discipline is:
- A type-2 file should not contain any directives except include/1. Thus a type-2 file must not begin with module/2 directive, and must not use the use_module/[1,2] directive.
- A type-2 file should not contain hard-coded module references. A type-2 file should not contain any qualified M:P call where M is a hard-coded atom; it is fine if M is a variable.
There are several mostly incompatible ways to load a Prolog source file:
- include/1, only works as directive
- consult/1
- consult_unregistered/1, which is load_files/2 with register(false) option
- use_module/2
- load_files/2
- consult_unregistered_into_module/2, which is just load_files/2 with module/1 and register(false) options
- Logtalk, logtalk_load/1, logtalk_load/2
The function of the main file is to link the non-main files. To maximize reusability and minimize name clash, a non-main file must not contain any hard-coded module names: Those files must not contain module/2 declarations and use_module/[1,2] directives.
14.6from module.md (Designing module systems)
- How do we decompose a program? (I think David Parnas has answered this.)
- How do we organize programs?
What do we infer?
- We can develop different modules at the same time.
- 14.6.1Philosophical investigation(128w~1m)
- 14.6.2Key idea: Module = Dictionary -> Dictionary(162w~1m)
- 14.6.3Partial query problem(36w~1m)
- 14.6.4What are some cool ideas?(15w~1m)
- 14.6.5Finding a programming language for programming in the large(337w~2m)
- 14.6.6package/dependency management tools(13w~1m)
- 14.6.7Module algebra vs module calculus?(61w~1m)
- 14.6.8Other questions?(132w~1m)
14.6.1Philosophical investigation
- What are the properties of a module?
- What are its relationships with other things?
- interchangeability
- A module groups things.
- Is this essential or accidental? Is it made for grouping? Is grouping only a side-effect?
- What can we do with modules?
- We can combine modules.
- We can shadow modules.
- We can link modules.
- We can embed/inline modules.
- A module is an incomplete/dependent piece of functionality/code.
- A module may have unresolved symbols?
- A module is a decomposition of a program?
- Module is about reusability?
- A program is a module and a starting point.
- A module specifies a contract. A module can be swapped with another module that satisfies the same contract without changing the correctness of the program.
- A module is a bunch of imports and exports?
- A module is smallest unit of reuse? Isn't that function?
- A module is smallest unit of compilation? Isn't that function?
14.6.2Key idea: Module = Dictionary -> Dictionary
Assume a dependently-typed language.
Recall some terminologies:
- A record is a tuple whose components are named.
- A dictionary is also known as key-value map or look-up table.
Then a module is a lambda abstraction that takes a record and gives a record.
A module is a lambda abstraction.
This idea is similar to Nix and JavaScript modules.
type Module = Map Name Decl -> Map Name Decl
A module translates into a lambda-calculus expression. An import translates to an entry in the input dictionary. An export translates to an entry in the output dictionary. Example:
module {
import add mul Int32;
export f g T;
f = add;
g = mul;
T = Int32;
};
-- The expression above translates to:
\ {add; mul; Int32; ...} -> {
f = add;
g = mul;
T = Int32;
};
Key ideas of that example:
- Dictionary pattern matching simulates row polymorphism.
{a;b;c;}
is shorthand for{a:a; b:b; c:c;}
.- Notes on Elixir: Pattern-Matching Maps · Rob Phoenix
What we are doing here is also known as "blurring the phase distinction". See "Modules versus Higher-Order Functions" in Futhark blog post: "A module can be viewed as nothing but a record containing types and values."
A problem: compilation may fail to terminate. No big deal. Set a time-out.
14.6.3Partial query problem
Partial query problem is when an object-relational mapper is not smart enough to avoid pulling unused columns.
Does lazy evaluation solve the partial query problem elegantly? Lazy evaluation is not a substitute for dependency analysis?
14.6.4What are some cool ideas?
- Module system: Dhall can import from IPFS.80
- Elixir can pattern-match maps (dictionaries).
14.6.5Finding a programming language for programming in the large
- Ecosystem, libraries, tools, and communities.
- The most important thing in programming in the large is name management. Namespaces.
- C has two namespaces: type namespace and value namespace.
- Haskell has two namespaces: type namespace and value namespace.
- Java has better namespacing than C.
- Enable the same name to be used in different context, so that you can write
get_name employee
andget_name company
instead ofemployee_get_name employee
orcompany_get_name company
.- Ad-hoc polymorphism.
- Which one has the biggest community?
- Which one has a decent IDE?
- Which community puts their money on where their mouth is?
- Comparing type systems
- The Typed Racket Guide
- F#
- SML
- Caml
- OCaml
- Idris, Agda
- Coq, Lean
- Haskell
- 2004, chapter, "Type systems", Luca Cardelli, pdf
- from https://www.artima.com/forums/flat.jsp?forum=106&thread=185420
- 2005, book, "Advanced topics in types and programming languages", Benjamin C. Pierce (editor)
- Part IV, "Types for Programming in the Large"
- 2002, book, "Types and programming languages", Benjamin C. Pierce
- Java, Kotlin, Scala
- Things that annoy me
- ML, SML, Caml, OCaml:
'a tf
is somewhat annoying. It should have beentf a
.- F# uses
tf<'a>
. - Haskell uses
Tf a
.
- F# uses
- Would you rather type
'a list
(F#) or deal with an inadequate record/module system (Haskell)? - Haskell doesn't have
instance Read (->)
andinstance Show (->)
.- Haskell expressions are not first-class citizen in the language.
- Unlike Lisp/Scheme.
- Encumbers metaprogramming.
- Haskell expressions are not first-class citizen in the language.
- ML, SML, Caml, OCaml:
- OCaml labels and polymorphic variants?
- http://caml.inria.fr/pub/docs/manual-ocaml-400/manual006.html
- OCaml labels are somewhat similar to Scheme keyword arguments.
- F# quotations is important for metaprogramming.
- F# doesn't do ad-hoc polymorphism well?
- https://cstheory.stackexchange.com/questions/40705/why-did-caml-become-ocaml-or-why-use-objects-in-f
- ML begat Caml. Caml begat Caml Light? Caml Light begat OCaml?
- How does F# compare to OCaml, in regard to major syntactic differences, paradigm shifts, and interoperability with Windows? What about its numeric capabilities? - Quora
- Jon Harrop claims. More sources needed. Take it with a grain of salt.
- "OCaml has an integrated full-blown macro system in the form of Camlp4 whereas F# does not have macros and, in fact, has been deliberately closed off in order to discourage people from creating products that compete with Visual Studio."
- "deliberately closed off […]" is a bold claim.
- "OCaml has an integrated full-blown macro system in the form of Camlp4 whereas F# does not have macros and, in fact, has been deliberately closed off in order to discourage people from creating products that compete with Visual Studio."
- Jon Harrop claims. More sources needed. Take it with a grain of salt.
- Are all languages basically the same? - Software Engineering Stack Exchange
14.6.6package/dependency management tools
- Java: Maven, Gradle
- OCaml: OPAM
- Haskell: Cabal, Stack
- F#: Paket? NuGet?
- C/C++: conan? chocolate? vcpkg?
14.6.7Module algebra vs module calculus?
[8] mentions module algebra (when talking about Prolog modules).
The following seems different.
Formally adding modules to lambda calculus: What is module calculus?
- 2017 article "Modules, Abstraction, and Parametric Polymorphism" pdf
- 2003 article "A Type System for Higher-Order Modules" pdf
- 2001 article "A Calculus of Module Systems" pdf available
- 2012 course notes "Types for Module Systems" pdf from CS7480 Type Systems (Spring 2012)
14.6.8Other questions?
- Does a module have to coincide with a compilation unit?
- Basic module functions?
- How does a code describe its dependencies?
- How does the machine disambiguate names?
- Functions should be versioned. Not module. Not package. Version describes semantics.
Module is second-order logic programming? Note below, that the same Plus
is used as both a variable and a predicate.
export(module_name, type, name, value).
export(prelude, int, plus, Plus) |- export(my_module, int, three, Plus(1, 2)).
- The smallest unit for this discussion is a machine instruction.
- A subroutine is a collection of instructions.
- A library is a collection of subroutines.
- A program is a collection of libraries and an entry point.
- History
- The initial motivation was to reuse.
- Reduce development cost.
- Humans have always been looking for easier ways to live. This "laziness" (the ability to get bored repeating something) is the source of all human technology.
- Reduce development cost.
- The next motivation was to reduce disk and memory usage.
- The initial motivation was to reuse.
- The essence of programming-in-the-large is Don't Repeat Yourself?
14.7<2019-04-02> The implementation? Draft: A clash-free module system
- 14.7.1About this draft(64w~1m)
- 14.7.2Message(182w~1m)
- 14.7.3Implementation details(140w~1m)
- 14.7.4Proposal: import_qualified/1 directive(8w~1m)
- 14.7.5The problem: We could be a victim of our own success if we don't act(62w~1m)
- 14.7.6Criteria of a satisfactory solution(15w~1m)
- 14.7.7Related discourses(4w~1m)
14.7.1About this draft
The target audience is the SWI-Prolog maintainer, Jan Wielemaker.
I wish to convince Jan that we must have a clash-free module system so that we do not become the victim of our own success when Prolog becomes mainstream.
I wish to see such module system standardized and implemented.
Where should we publish this to?
- Post in SWI-Prolog Discourse group https://swi-prolog.discourse.group
- Open an issue in SWI-Prolog Roadmap https://github.com/SWI-Prolog/roadmap
14.7.2Message
Dear Prolog implementors,
The Prolog community seems to be growing, and so is the number of SWI-Prolog packs. As more people write code, name clashes become more likely. We should standardize a clash-free module system before we have too many users and name clashes become too painful.
There are two ways to avoid name clashes:
- Rely on programmer coordination and discipline. For example, the pack authors may prefix their module names by a domain name they control. But it would be better for a system to avoid assuming that humans behave well.
- Make name clashes impossible. This is the path taken by JavaScript. It is the only language I know that does this by its first-class modules.
The key to clash-free module names is simple:
- A file must not contain any module names/references.
- The module/2 directive must ignore its first argument (the module name).
- Dependency must be specified by file paths and not module names.
Both predicate-based and atom-based modules are fine, as long as a module does not name itself, that is, as long as a file does not expect to be loaded to a module with a certain name.
14.7.3Implementation details
I have a working code for SWI-Prolog in boot/load.pro. It defines an import/2
directive using term_expansion/2
. The loader generates module names. An example usage looks like this:
:- import("somefile.pl",[
pred/1
, run/0 as somefile_run
]).
The presence of an :- import(Source, Specs)
in a file means that the file requires some things from Source.
Source may be:
file(Path)
wherePath
is a relative path to a file. This path is resolved against the file that contains the import/2 directive.
Specs is a list of Spec.
Spec may be:
Name/Arity
Name/Arity as Alias
multifile(Name/Arity)
: a "reverse-import"multifiles(Preds)
where each Pred is a Name/Arity
Not yet implemented: importing operators like SWI-Prolog 7.6.4 use_module/2.
use_module(..., [
op(_,_,some_operator)
]).
One day someone may make it possible for Source to be github(...)
or pack(...)
, but perhaps we should not do that because it will increase compilation time.
An example language with a clash-free module system is JavaScript. Even better, modules are first-class in JavaScript.
function foo () {
var a = require("file1.js");
var b = require("file2.js");
console.log(a.x + b.y);
}
// a.js
export let x = 1;
// b.js
export let y = 2;
What do you think?
Best regards,
Erik
14.7.4Proposal: import_qualified/1 directive
:- import_qualified(file(RelativePath) as local_module(Name)).
:- import_qualified([
file(File1) as local_module(Name1),
file(File2) as local_module(Name2),
...
]).
This recursively replaces all module expressions.
14.7.5The problem: We could be a victim of our own success if we don't act
Imagine that there were 10,000 SWI-Prolog packs: There would be naming conflicts. We can learn from the Haskell community's complaints with Haskell's module system, and do it right before it becomes too painful. Let us prepare, so that we do not become a victim of our own success.
14.7.6Criteria of a satisfactory solution
Ideally, many people can write and use libraries without name clashes.
14.7.7Related discourses
- Contributing libraries https://swi-prolog.discourse.group/t/contributing-libraries/381
14.8Implementing modules
- 14.8.1Adding module system by term_expansion/2(44w~1m)
- 14.8.2Logtalk?(23w~1m)
- 14.8.3Haskell first-class modules?(7w~1m)
- 14.8.4Module systems in other languages?(91w~1m)
- 14.8.5Comparing existing module systems(97w~1m)
14.8.1Adding module system by term_expansion/2
If a Prolog system has term_expansion/2 but does not have a module system, then we can add a module system. The idea is to recursively replace each term A
with ':'(M,A)
.
This makes something similar to XSB Prolog's atom-based module system.
14.8.2Logtalk?
"You can even use [Logtalk] to run Prolog module code in Prolog compilers such as GNU Prolog that don't include a module system."81
14.8.3Haskell first-class modules?
Shields & Peyton-Jones 2002 [26].
14.8.4Module systems in other languages?
REBOL module system?
Bad example: java:
- name is a property of a method.
- a method cannot be referred to by a name.
If you use reflection, you are referring to a representation of that method, not the method itself.
Bad example: scheme: map, vector-map, tree-map, etc.
Racket vs prolog Racket has racklog and miniKanren
(infix x = 1 : y = x + x : )
Racket DCG, packrat
What is a module in an untyped functional programming language such as Tulip?
Ignored undocumented code sketches: jordanlewis/simple-module-system: Adding modules to a polymorphic lambda calculus, code in SML/NJ.
14.8.5Comparing existing module systems
How do programming languages deal with modules?
- dhall modules · Issue #182 · dhall-lang/dhall-lang
- Futhark
Racket
- 2011, article, "Languages as Libraries", pdf
- Scheme R7RS, Common Lisp, Clojure
Java, Scala, Kotlin, Go, C, C++
C ABI
- A module is an ELF shared object file (SO file).
- Pascal, Ada, Oberon, Algol, Fortran
- JavaScript, TypeScript, ECMAScript
Standard ML, Caml, OCaml, MLTON, SML/NJ, F#
2000, "A modular module system", pdf
- "Harper-Lillibridge-Leroy module system"
- "applicability of that module system to a wide range of programming languages"
- Haskell has underpowered module system.
book, "Advanced topics in types and programming languages", part IV, programming in the large, pdf
- book, "Types and programming languages", pdf
- WP:Modular programming
14.9Brain dumps
- http://erlang.org/pipermail/erlang-questions/2011-May/058768.html
- Hackernews commend thread https://news.ycombinator.com/item?id=8226139
- LtU comment thread http://lambda-the-ultimate.org/node/5079
14.10Operators and adaptive grammar
Should operator be module-scoped or global-scoped?
An operator declaration modifies the Prolog parser/reader's grammar in a limited manner.
Is it not confusing if parsing a text can, in the middle of parsing, change the grammar that is used to parse the text itself?
% input
:- op(400,yfx,'+').
:- op(500,yfx,'*').
a(A) :- A is 1+2*3.
:- op(500,yfx,'+').
:- op(400,yfx,'*').
b(A) :- A is 1+2*3.
% output
?- a(A).
A = 9.
?- b(A).
A = 7.
If we want adaptive grammars82, why stop at operators? Should we go at least as far as OMeta?
"Operator precedence parsing is particularly ugly in PEGs, since by default, they don't support left recursion. The OMeta folks figured out how to cleanly support left recursion in PEGs, but you lose the linear-time guarantee."83
If we have local variables, we should also have local operator declarations. We need an adaptive grammar with scope.
We also need composable grammars8485.
C grammar is ambiguous.86
What are dynamic grammars?87
15The problems with Prolog
- 15.1Absence of modules, scoping, and local variables(430w~3m)
- 15.2What next?(24w~1m)
- 15.3Embedding Prolog/Haskell in Haskell/Prolog(122w~1m)
- 15.4Comparison with other programming languages(211w~2m)
- 15.5Programming can be thought of as applied mathematics?(36w~1m)
- 15.6Theorem proving(113w~1m)
- 15.7Logic programming vs theorem proving(21w~1m)
- 15.8Avoid using list too much(19w~1m)
- 15.9miniKanren?(26w~1m)
- 15.10Dreams, speculations, ambitions(208w~2m)
- 15.11Dynamic, assert, retract(6w~1m)
- 15.12Why should we write type systems as macros?(16w~1m)
15.1Absence of modules, scoping, and local variables
Prolog does not have scopes and local variables.
Is that absence a bad thing?
(old title: Lambda, closure, scoping, higher-order logic programming, relational programming)
One application of higher-order logic programming is scopes (local variables). It can be done by allowing implications in Horn clause bodies.
Ulrich Neumerkel's "Lambdas in ISO Prolog"88.
Logtalk 2.38.0 has lambda expressions.89
Why can't it be this? Isn't "apply" just variable substitution? But the problem is not substitution. The problem is scoping.
apply(A^B, A, B).
<2019-04-05> See lambda.pro. It does the job, but the variables cannot be reused.
Example of closure:
let makeGetter list = \ i -> elemAt list i
We can manually do closure conversion (lambda lifting)90.
Naish 1996 [21]:91 "First, we point out that call/N is not the way to go, despite its recent popularity as the primitive to use for higher order logic programming."
Let's try something else.
I propose "local predicate" as the logic-relational analog of the functional lambda expression.
The meaning of the expression A ^ B
is "prove B assuming that A is true". The semantics is substitution.
Define the meaning of A^B
as prove B
assuming A
. Thus, the meaning of p(1) ^ (p(A), q(B))
is (A = 1, q(B))
.
Lambda expression is variable scoping. Prolog needs "knowledge base" scoping.
Each lambda parameter x is encoded as a unary predicate x(A) that succeeds exactly once and unifies A to the value of the variable.
Implication is the logic parallel of lambda abstraction. Proving is the logic parallel of lambda application.
lambda application: (x to x + 1) 23
becomes
prolog query: x(23), y(B) --> x(A), B is A+1
But this may be a bad idea, because the predicate x/1 is dynamically scoped. "Local dynamic clauses"
Assert the antecedent when entering frame. Retract the antecedent when leaving frame.
Ask at stackoverflow:
Is there a with_assumption_prove_goal/2 predicate in Prolog?
I am looking for "knowledge base scoping" as an analog of variable scoping in lambda expressions.
Assumption = (p(1) ; p(2)),
Goal = (p(A), writeln(A)),
with_assumption_prove_goal(Assumption, Goal)
1
2
It can be done with meta-interpretation. I think it can also be done with Prolog engines.
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/naish.html
https://pdfs.semanticscholar.org/904a/b2253330cdd379c7a405f400c6f9152afdca.pdf
Interesting google scholar search: logic with lexical scoping
It may be disconcerting that it takes an academic article to add local variables. But we are doing it in a principled manner. We are thinking about how to add local variables to logic, not to a programming language.
Predicate logic is dynamically scoped. p(G) leftarrow ( x(1) right arrow G) defines a local dynamic predicate x/1
Currying requires keeping track of the arity of partially-applied functions. Currying readily generalizes to partially-applied relations.
f (x,y) -> (f x) y
r (x,y) -> (r x) y
Logic vs relational?
MacLennan 1981 [15], MacLennan 1983 [16]
MacLennan 1981 [14]: A function is a left-univalent relation. I have been looking for that term.
\(R \wedge S\) in relation is R, S
in logic.
The connection is fundamental: Every set \(R\) corresponds to a predicate \(\phi\) in this way: \(\SetBuilder{\vec{x}}{\phi(\vec{x})}\). We say that the predicate is an intension and the set is an extension.
15.2What next?
Gödel, λProlog, Twelf, Datalog, Answer-Set-Programming.92
Lambda-Prolog 2012 book [18].
What are Prolog alternatives? See 2011 article A structured alternative to Prolog with simple compositional semantics?
15.3Embedding Prolog/Haskell in Haskell/Prolog
Why bother with this? Why not just use Oz?
- 15.3.1Embedding Prolog in Haskell(57w~1m)
- 15.3.2Embedding Haskell in Prolog: Nobody is talking about this?(55w~1m)
15.3.1Embedding Prolog in Haskell
- 1999 article "Embedding Prolog in Haskell" https://pdfs.semanticscholar.org/7c46/5d25205830735d0a034532746b7243221eca.pdf
- "We propose an embedding of logic programming into lazy functional programming in which each predicate in a Prolog program becomes a Haskell function, in such a way that both the declarative and the procedural reading of the Prolog predicate are preserved."
- 1988 article "Towards functional programming in Prolog" ftp://obaluae.inf.puc-rio.br/pub/docs/Publications/88_AI_Furtado_SINPLAN.Not.pdf
15.3.2Embedding Haskell in Prolog: Nobody is talking about this?
translate haskell to prolog
- https://stackoverflow.com/questions/1932770/haskell-vs-prolog-comparison
- https://github.com/COMS30106/slides
- https://github.com/COMS30106/slides/blob/master/haskell2prolog.pdf
Prolog and Haskell are almost equally concise. Prolog and Haskell are even in head/2 and tail/2. Prolog beats Haskell in null/1 and reverse/2. Haskell beats Prolog in length/2, sumList/2, and everything that has arithmetics where Prolog requires intermediate variable such as "N1 is N-1".
15.4Comparison with other programming languages
"GOEDEL is intended to be a declarative successor to Prolog." https://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/prolog/impl/other/goedel/0.html
How are Prolog and Lisp similar?
- Both Prolog and Lisp have symbols and cons cells.
- This is a Lisp cons cell:
(cons 'a 'b)
or'(a . b)
. - This is the corresponding SWI-Prolog cons cell:
[a|b]
(the canonical form is'[|]'(a,b)
).
- This is a Lisp cons cell:
- Both have macros.
- Lisp has defmacro.
- Prolog has term_expansion/2 and goal_expansion/2.
I'd say Prolog = Lisp + unification + backtracking - lambda.
Comparison between what is difficult in various programming languages:
- 2014 presentation "That scripting language called Prolog" https://www.slideshare.net/SergeiWinitzki/prolog-talk
- It compares what is difficult in various programming languages.
- It defines "declarative": 'Programming is "declarative" when specifications are programs.'
- Slide 29: "declarative programming = creating a good DSL for your domain"
- Slide 24 compares SQL, Datalog, and Prolog.
Comparison with other relational programming languages:
Comparison with miniKanren:
- https://stackoverflow.com/questions/28467011/what-are-the-main-technical-differences-between-prolog-and-minikanren-with-resp
- William E. Byrd's answer:
- Prolog is practical; miniKanren is pure.
- Prolog unification doesn't use occurs check; miniKanren unification uses occurs check.
- Prolog uses depth-first search; miniKanren uses complete interleaving search.
- '[…] miniKanren is being used for research in "relational" programming.'
- "Over time miniKanren has added more symbolic constraints, really becoming a symbolically-oriented Constraint Logic Programming language."
- "There are other very interesting logic programming languages as well, such as Mercury, Curry, and Gödel, each of which has its own take on logic programming."
- William E. Byrd's answer:
Mercury vs Prolog
- http://lambda-the-ultimate.org/node/890
- <2018-10-21> "The Prolog to Mercury transition guide" https://www.mercurylang.org/information/doc-latest/transition_guide.pdf
SQL? Datalog?
15.5Programming can be thought of as applied mathematics?
Prolog can be approached from logic, database theory, philosophy.
In Prolog, by default, function symbols mean themselves, and this gives us freedom to write interpreters to interpret function symbols differently.
15.6Theorem proving
Problem statement of automated theorem proving: Given a formula G (query, goal), a set of axioms A, and a set of inference rules R, prove G.
A formula can be represented by a Prolog term.
An inference rule transforms a formula into another formula having the same truth value.
It may be better to write a theorem prover in Prolog than to use Prolog directly as theorem prover.
Prolog can be used as a theorem prover.
p.
q :- p.
?- q.
true.
It is simple to write a theorem prover for propositional logic. But how about first-order logic?
What is resolution93? Why is it widely used in automatic theorem proving?
Aren't theorem provers just constrained rewriting systems?
Modus ponens \( \alpha, (\alpha \to \beta) \vdash \beta \).
15.7Logic programming vs theorem proving
- https://stackoverflow.com/questions/36335633/difference-between-logic-programming-and-automated-theorem-proving
- https://en.wikipedia.org/wiki/Automated_theorem_proving
There is an inverse relationship between the cleverness of a theorem prover and its suitability for programming?
15.8Avoid using list too much
Perhaps think more about the relations between the individuals.
Perhaps normalize your predicates to sixth-normal form.
15.9miniKanren?
Relational programming, microKanren http://matt.might.net/articles/microkanren/
2017 A Unified Approach to Solving Seven Programming Problems (Functional Pearl) http://io.livecode.ch/learn/gregr/icfp2017-artifact-auas7pp
2013 rKanren - Guided Search in miniKanren, Part I http://cgswords.github.io/rkanren/
Schelog vs minikanren?
15.10Dreams, speculations, ambitions
Harel 2008 [9] has a lovely ambition. But I'm afraid I see only two way to realize that ambition: either invent a human-level AI that can write software, or invent a machine that can do telepathy. But I believe that we will someday have at least one of that.
I want a browser like this. Each user should have total control of what runs on his/her machine. I should be able to tell my browser how to modify the CSS and JavaScript for certain websites. From [9]:
[…] conveniently remove pieces of behavior that we don’t like and replace them with others […] I would love to be able to reprogram the interactions that the web-based systems I work with force me to follow—not to mention reprogramming my annoying and unnecessarily complicated DVD. I can’t change the way Amazon or B&H respond to what I do, for example, but I can surely change everything that has to do with the way my browser and my computer deal with these websites. And how better to do that than by simply canceling some pieces of interactive behavior and playing in new ones, using the very interface on which we interact, subject, of course, to my inability to change their behavior?
15.11Dynamic, assert, retract
Assert accepts a clause.
assert(man(fred)).
assert(p(A,B) :- f(A), g(A), h(A,B)).
15.12Why should we write type systems as macros?
WIP implementation of a Haskell-like Lisp in Racket https://github.com/lexi-lambda/hackett
http://www.ccs.neu.edu/home/stchang/pubs/ckg-popl2017.pdf
16Extending Prolog
16.1First order logic already has local variable scoping and local assertion
Scoping existential quantified.
Local assertion is implication.
We need more than Horn clauses.
16.2Logical implication is local variable scoping
I have an example in scope.pro
.
fun :- (locvar(1) => locvar(A), format("locvar is ~w~n",[A]), nl).
The logical semantics of A => B
is "B is provable, if A is assumed to be true".
The operational semantics of A => B
is:
- Assert A.
- Call B.
- Retract A.
Problem: How do we "undefine" a local variable?
For example: In A => B, (not(A) => C)
, we want A to be defined in B but undefined in C.
Why should we prefer monotonic logic?
17Program checking
Motivation: We want two avoid stupid runtime mistakes that can be prevented before runtime (at "compile" time).
The problem: Given a Prolog term T, determine whether call(T)
will throw a type error. Note that T may be a conjunction of goals.
I'm thinking about using abstract interpretation or partial deduction.
Program checking is partial deduction.
This program is a mistake.
p(0).
mistake1 :- p(foo).
mistake2 :- number_string(_,_).
We can imagine a check_goal/1
predicate.
The key idea is to unify a variable with its type.
- 17.1The errors Prolog programmers make(58w~1m)
- 17.2Typed first-order logic(25w~1m)
- 17.3Vanilla Prolog type-checking(41w~1m)
- 17.4Type-checking interpreter(12w~1m)
- 17.5Abstract interpretation(39w~1m)
- 17.6Problem: the type of variables(44w~1m)
- 17.7Problem: non-terminating predicates(3w~1m)
- 17.8Checking when unchecked code calls checked code(7w~1m)
- 17.9Manual checking(2w~1m)
17.1The errors Prolog programmers make
The errors made by a Prolog programmer include:
- type error: instantiating an input argument to a term of a wrong type
- mode error: not instantiating an input argument
- termination error: infinite loop, left recursion
In this example, the first argument of interpret is n/1 or a +/1.
interpret(n(A),A).
interpret(A+B,C) :- C is A+B.
A call such as interpret(1-2,A)
should raise an exception instead of failing.
17.2Typed first-order logic
Another name for typed logic is many-sorted logic.94
Typing relation relates symbol to type (Cartesian product of sets) Example: \( T(p^2, Integer \times String) \).
type(p/2, relation([integer,string])).
17.3Vanilla Prolog type-checking
Suppose that we have a predicate p/1
that expects an integer or a var. We can type-check it like this:
% public
:- export(cp/1).
cp(A) :-
check_or_throw(p(A),before),
p(A),
check_or_throw(p(A),after).
% private
p(0).
p(1).
check(p(A),before) :- integer(A).
check(p(A),before) :- var(A).
check(p(A),after) :- integer(A).
check_or_throw(A,T) :- check(A,T), !.
check_or_throw(A,T) :- throw(error(check_failed(A,T),_)).
The advantage is that it is vanilla Prolog. No domain-specific type-specification languages.
The disadvantage is that it is often done unnecessarily.
17.4Type-checking interpreter
One step further than that is to make a checking interpreter.
cp(A) :- interpret(p(A)).
interpret(G) :- check(G,before), call(G), check(G,after).
17.5Abstract interpretation
The semantics is: If the check succeeds, then the goal will not fail due to stupid type error.
Unsatisfiability is not a type error. For example, the following q/1
is unsatisfiable, but it does not throw a type error.
p(0).
q(A) :- p(A), A = 1.
17.6Problem: the type of variables
We mean the type of the term bound to the variable. Attributed variables are suitable for this scenario. But not all Prolog implementations have attributed variables. So we use gensym?
Type-checking variables would be easier if Prolog variables were explicitly quantified.
17.7Problem: non-terminating predicates
check(p(A,B),before) :- integer(A).
check(p(A,B),after) :- string(B).
p(A,B) :- p(A,B).
17.8Checking when unchecked code calls checked code
17.9Manual checking
interpret(A,_) :- var(A), !, instantiation_error(A).
interpret(A,_) :- \+exp(A), !, type_error(exp,A).
interpret(n(A),Z) :- !, Z=A.
interpret(A+B,Z) :- !, Z is A+B.
interpret(A*B,Z) :- !, Z is A*B.
exp(n(_)).
exp(_+_).
exp(_*_).
18Sometimes we want function and determinism
Sometimes we really want to write a function and not a general relation. The sign of such unfilfilled desire is: Each clause begins with pattern-matching and cut, as in this example:
interpret(n(A),Z) :- !, Z=A.
interpret(A+B,Z) :- !, interpret(A,A0), interpret(B,B0), Z is A0+B0.
interpret(A*B,Z) :- !, interpret(A,A0), interpret(B,B0), Z is A0*B0.
It would be nice if we could write it in a functional style like this which might then be rewritten with term_expansion/2
:
:- function interpret(E) = case(E,[
n(A) -> A
, A+B -> interpret(A) + interpret(B)
, A*B -> interpret(A) * interpret(B)
]).
19Prolog implementation
- 19.1How would we implement Prolog in C?(79w~1m)
- 19.2Why does SWI-Prolog use Git submodules instead of a mono-repo?(121w~1m)
- 19.3How to contribute to SWI-Prolog?(33w~1m)
- 19.4Foreign language interface(241w~2m)
- 19.5What is a Unicode character?(47w~1m)
- 19.6The problem with dynamic database(48w~1m)
- 19.7Prolog parser in Prolog(4w~1m)
- 19.8Java(1w~1m)
- 19.9P# translates Prolog to C#.(5w~1m)
19.1How would we implement Prolog in C?
I am thinking of these:
- struct Prolog_interpreter
- struct Prolog_term
But there are no integers in logic; there are only logical symbols and non-logical symbols.
// .h
struct Prolog_term_;
typedef struct Prolog_term_ Prolog_term;
bool prolog_term_as_int (const Prolog_term*, int*);
bool prolog_term_as_strz (const Prolog_term*, size_t, char*);
// .c
struct Prolog_interpreter {
Prolog_term* clauses;
size_t cap;
};
enum Prolog_term_type {
Prolog_integer = 0, // but there are no integers in logic?
Prolog_string = 1,
Prolog_atom = 2,
Prolog_functor = 3,
Prolog_var = 4,
Prolog_foreign_object = 5,
};
struct Prolog_term_ {
Prolog_term_type type;
};
struct Prolog_string {
Prolog_term_ term;
size_t num_bytes;
char* bytes;
};
struct Prolog_atom {
Prolog_term_ term;
int id;
Prolog_string* string;
};
struct Prolog_functor {
Prolog_term_ term;
Prolog_atom name;
size_t arity;
Prolog_term* args;
};
struct Prolog_var {
Prolog_term_ term;
Prolog_term* value; // NULL if unbound
};
bool prolog_unify (Prolog_term* a, Prolog_term* b) {
// ???
}
We can use GMP (GNU multiprecision math library) for arbitrary-precision arithmetics. "GNU MP is a portable library written in C for arbitrary precision arithmetic on integers, rational numbers, and floating-point numbers."95
What a C preprocessor does is explained in GNU CPP Overview96.
How does SWI-Prolog implement Prolog in C?
SWI-Prolog has the macros PL_succeed
and PL_fail
.
19.2Why does SWI-Prolog use Git submodules instead of a mono-repo?
<2019-04-06> Jan Wielemaker wrote on Discourse97:
Submodules have had their value in the past when several of the modules were practically managed by other people. At the moment all package modules are practically in maintenance stage and this doesn’t matter too much, but I still like to be able to do so. Submodules were also intended to be shared with other Prolog systems. That too isn’t active right now, but work is going on between XSB and SWI, so who knows?
XSB Prolog source code is in a Subversion repository.
Reading "Subversion Design"98 helps us understand SVN.
- Subversion can track an empty directory. Git cannot.
- Both SVN99100 and Git have problems with merge conflicts that involve renames.
19.3How to contribute to SWI-Prolog?
- 19.3.1How to clone the Git repository?(29w~1m)
19.3.1How to clone the Git repository?
<2019-04-06> SubmitPatch.html101 is a little messy. See unix.html102 about git submodules. See also Discourse103.
It is not a simple git-clone, because we are using submodules.
19.4Foreign language interface
SWI-Prolog has a foreign language interface104, but I demand more.
I want to call C code from Prolog without writing a C wrapper. I want Prolog to marshal the arguments and unmarshal the return values.
Even more, I want to write low-level code directly in Prolog. A solution already exists: SWI-Prolog pack "ffi":105
- "This package deals with calling C functions from shared objects (DLLs) from Prolog without writing wrappers"
- It parses C header files and C source files!
I want to write C code in Prolog. I want to have C with type inference and other cool features in Prolog.
I dream of writing foreign code directly in Prolog. I dream of a Prolog code that can output an amd64 ELF binary. Related in mailing list106. Related from the 1990s107. Related: Warren 1980 [29].
There are two problems: emitting machine code, and executing machine code.
Options for emitting machine code:
- Design a DSL like ASN.1 to describe binary layout such as C struct or Pascal record. I have a sketch in database_internal_dcg.pro.
- Design an language that can be represented in Prolog and translated to C.
- Reuse LLVM.
- Building something like LLVM. Write our own intermediate representation. Static-single-assignment three-address code.
- Write amd64 machine code directly. This is bad. Too tightly coupled. We will want to generate i386, arm, and jvm machine codes.
Options for executing machine code:
- Write machine code to some memory area, set PROT_EXEC with mprotect, and call the address.
- Write an ELF SO object and use dlopen.
The skeleton of the minimum viable product:
example :-
compile(ret, ByteCode),
write_bytes(ByteCode).
nb_write_address(+Address, -Thing)
19.5What is a Unicode character?
This question is tricky.
Does a character correspond to a code point?
What about accents, ligatures, etc.?
Is an accent by itself a character?
Is a hanzi radical a character?
Is a hanzi a character?
How many bytes are in a character?
What are equivalent characters? What is Unicode normalization?108
19.6The problem with dynamic database
do_something :-
assert(a), ...
Dynamic database is like global variable. There can only be one instance of do_something
running without confusing the dynamic database.
But we can replace each occurence of assert(A)
with assert(local(G,A))
where G is generated by gensym/2
. This is like rewriting C global variables into structs.
int x;
int f () {
return x;
}
// becomes
struct global {
int x;
};
int f (struct global* g) {
return g->x;
}
19.7Prolog parser in Prolog
https://dtai.cs.kuleuven.be/projects/ALP/newsletter/archive_93_96/net/grammars/parser.html
19.8Java
https://stackoverflow.com/questions/1817010/embedded-prolog-interpreter-compiler-for-java
https://github.com/raydac/java-prolog-parser
19.9P# translates Prolog to C#.
https://pdfs.semanticscholar.org/12ec/568a6583d3d66b6821f28269f06937a9f2eb.pdf
20SWI-Prolog packs
I want to use a pack. I want to know:
- How do I install a pack the easy way? Use
pack_install/1
. - How do I install a pack manually outside SWI-Prolog without
pack_install/1
? - How do I install a specific version of a pack?
- How do I freeze my dependencies to avoid silent breakage?
- How do I use multiple versions of a pack? My program depends on A and B. A depends on C version 1. B depends on C version 2. It seems the packs must be updated.
- To what directory are packs installed?
pack_install/1
will prompt you where to install.
21What I like about Prolog and Lisp
I can see the source code of everything as long as it is loaded and is non-foreign. Prolog has listing/1
and edit/1
and help/1
. Emacs has M-x find-function
109 and C-h f
or M-x describe-function
. SBCL has describe
.110
We can think of Prolog as Lisp with M-expression instead of S-expression.
22Namespacing atoms
When we write a predicate that deconstructs an instance of an algebraic data type, we don't want the constructors to be namespaced.
When we use an atom as a name under the unique name assumption, in a multifile predicate, sometimes we want the atom to be namespaced.
23Parsing Prolog?
Prolog's grammar is adaptive111: the op/3
directive changes the grammar.
24Other resources
Rowe 1988 book: Artificial Intelligence through Prolog by Neil C. Rowe
25Bibliography
[1] Afshari, M. et al. 2012. Liberating the programmer with prorogued programming. Proceedings of the acm international symposium on new ideas, new paradigms, and reflections on programming and software (2012), 11–26. url: <http://earlbarr.com/publications/prorogue.pdf>.
[2] Beeson, M. 2004. Lambda logic. International joint conference on automated reasoning (2004), 460–474. url: <https://pdfs.semanticscholar.org/9721/c012782ef25023ac300e33d6ce34ffed7e18.pdf>.
[3] Boizumault, P. 2014. The implementation of prolog. Princeton University Press.
[4] Cabeza, D. and Hermenegildo, M. 2000. A new module system for prolog. International conference on computational logic (2000), 131–148. url: <https://core.ac.uk/download/pdf/148663021.pdf>.
[5] Ciancarini, P. and Levi, G. 1993. What is logic programming good for in software engineering? Advances in software engineering and knowledge engineering. World Scientific. 109–134. url: <https://pdfs.semanticscholar.org/2597/345fc719960dc214f41ad439ef9124ade1c6.pdf>.
[6] Colmerauer, A. and Roussel, P. 1996. The birth of prolog. History of programming languages—ii (1996), 331–367. url: <http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.7438&rep=rep1&type=pdf>.
[7] Demoen, B. et al. 2005. The first 10 prolog programming contests. Bart Demoen. url: <https://dtai.cs.kuleuven.be/ppcbook/ppcbook.pdf>.
[8] Haemmerlé, R. and Fages, F. 2006. Modules for prolog revisited. International conference on logic programming (2006), 41–55. url: <https://www.researchgate.net/profile/Francois_Fages/publication/220986844_Modules_for_Prolog_Revisited/links/00b495277f5b9dd5ce000000/Modules-for-Prolog-Revisited.pdf>.
[9] Harel, D. 2008. Can programming be liberated, period? Computer. 41, 1 (2008), 28–37. url: <http://www.wisdom.weizmann.ac.il/~harel/papers/LiberatingProgramming.pdf>.
[10] Jarke, M. et al. 1984. An optimizing prolog front-end to a relational query system. ACM sigmod record (1984), 296–306. url: <https://archive.nyu.edu/jspui/bitstream/2451/14555/1/IS-84-24.pdf>.
[11] Jones, N.D. et al. 1993. Partial evaluation and automatic program generation. Peter Sestoft. url: <http://www.itu.dk/~sestoft/pebook/jonesgomardsestoft-a4.pdf>.
[12] Kowalski, R. 1974. Predicate logic as programming language. IFIP congress (1974), 569–544. url: <http://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf>.
[13] Liu, Y.A. 2018. Logic programming applications: What are the abstractions and implementations? Declarative logic programming (2018), 519–548. url: <https://arxiv.org/pdf/1802.07284.pdf>.
[14] MacLennan, B.J. 1981. Introduction to relational programming. Naval Postgraduate School, Monterey, CA. url: <https://apps.dtic.mil/dtic/tr/fulltext/u2/a101435.pdf>.
[15] MacLennan, B.J. 1981. Overview of relational programming. Naval Postgraduate School, Monterey, CA. url: <https://apps.dtic.mil/dtic/tr/fulltext/u2/a114462.pdf>.
[16] MacLennan, B.J. 1983. Relational programming. Naval Postgraduate School, Monterey, CA. url: <https://apps.dtic.mil/dtic/tr/fulltext/u2/a133643.pdf>.
[17] Miller, D. 1986. A theory of modules for logic programming. url: <http://www.lix.polytechnique.fr/~dale/papers/slp86.pdf>.
[18] Miller, D. and Nadathur, G. 2012. Programming with higher-order logic. Cambridge University Press.
[19] Moura, P. 2003. Logtalk - Design of an Object-Oriented Logic Programming Language. Department of Computer Science, University of Beira Interior, Portugal. url: <https://logtalk.org/papers/thesis.pdf>.
[20] Nadathur, G. and Miller, D. 1988. An overview of lambda-prolog. (1988). url: <http://www.lix.polytechnique.fr/~dale/papers/iclp88.pdf>.
[21] Naish, L. 1996. Higher-order logic programming in prolog. Proc. Workshop on multi-paradigm logic programming, jicslp (1996), 1–23. url: <https://pdfs.semanticscholar.org/904a/b2253330cdd379c7a405f400c6f9152afdca.pdf>.
[22] Peyton-Jones, S. 2000. Tackling the awkward squad: Monadic input/output, concurrency, exceptions, and foreign-language call. (2000). url: <https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/mark.pdf>.
[23] Porto, A. 2011. A structured alternative to prolog with simple compositional semantics. Theory and Practice of Logic Programming. 11, 4-5 (2011), 611–627. url: <https://arxiv.org/pdf/1107.5408.pdf>.
[24] Robinson, J.A. and others 1965. A machine-oriented logic based on the resolution principle. Journal of the ACM. 12, 1 (1965), 23–41. url: <https://web.stanford.edu/class/linguist289/robinson65.pdf>.
[25] Shieber, S.M. et al. 1995. Principles and implementation of deductive parsing. The Journal of logic programming. 24, 1-2 (1995), 3–36. url: <https://www.eecs.harvard.edu/shieber/Biblio/Papers/infer.pdf>.
[26] Shields, M. and Jones, S.P. 2002. First-class modules for haskell. 9th international conference on foundations of object-oriented languages (fool 9), portland, oregon (2002), 28–40. url: <https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/first_class_modules.pdf>.
[27] Sterling, L. and Yalçinalp, Ü. 1996. Logic programming and software engineering—implications for software design. The Knowledge Engineering Review. 11, 4 (1996), 333–345. url: <https://pdfs.semanticscholar.org/a58d/c68f53af502c043793f49e5cd7c7a44d2914.pdf>.
[28] Van Emden, M.H. and Kowalski, R.A. 1976. The semantics of predicate logic as a programming language. Journal of the ACM (JACM). 23, 4 (1976), 733–742. url: <https://www.doc.ic.ac.uk/~rak/papers/kowalski-van_emden.pdf>.
[29] Warren, D.H. 1980. Logic programming and compiler writing. Software: Practice and Experience. 10, 2 (1980), 97–125. url: <http://sovietov.com/tmp/warren1980.pdf>.
http://www.gprolog.org/manual/html_node/gprolog034.html#open%2F4↩
https://sicstus.sics.se/sicstus/docs/4.2.1/html/sicstus/mpg_002dref_002dopen.html↩
https://ciao-lang.org/docs/1.14/13646/CiaoDE-1.14.2-13646_ciao.html/streams_basic.html#open/4↩
https://www.semanticscholar.org/paper/On-the-Implementation-of-GNU-Prolog-Diaz-Abreu/2c4f697f96202f988602e88c49625a862a4ce696↩
https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations↩
https://stackoverflow.com/questions/5277263/good-ide-to-get-started-with-prolog↩
https://github.com/klauscfhq/awesome-prolog/blob/master/readme.md↩
https://stackoverflow.com/questions/14168363/what-does-a-clause-without-a-head-mean-in-prolog↩
https://vanemden.wordpress.com/2017/09/08/conceptual-integrity-why-it-matters-and-how-to-get-it/↩
http://www.swi-prolog.org/pldoc/man?section=ext-compound-zero↩
http://www.swi-prolog.org/packages/xpce/UserGuide/exeobjects.html↩
https://www.reddit.com/r/linux/comments/2dxik3/future_of_gnome_and_gtk_when_whole_world_is/↩
https://www.reddit.com/r/linuxmasterrace/comments/7xkcwo/why_does_everyone_hate_gtk/↩
http://www.swi-prolog.org/pldoc/doc_for?object=section(%27packages/plunit.html%27)↩
http://www.swi-prolog.org/pldoc/man?section=ext-dquotes-motivation↩
https://en.wikipedia.org/w/index.php?title=Side_effect_(computer_science)&oldid=855461052↩
https://softwareengineering.stackexchange.com/questions/40297/what-is-a-side-effect↩
https://en.wikipedia.org/w/index.php?title=Side_effect&oldid=875244456↩
http://www.dubberly.com/articles/distinguishing-between-control-and-collaboration-and-communication-and-conversation.html↩
https://swi-prolog.discourse.group/t/scaling-to-billions-of-facts/380/2↩
https://stackoverflow.com/questions/25641240/is-it-possible-to-partially-refresh-a-materialized-view-in-postgresql↩
https://twiki.org/cgi-bin/view/Plugins/SwiPrologToPostgreSqlAddOn↩
http://mrhoyestokwebsite.com/Knower/Useful%20Information/Three%20Different%20Theories%20of%20Truth.htm↩
https://conference.imp.fu-berlin.de/cade-25/download/2015_CADE_ruleml_genesere.pdf↩
https://math.stackexchange.com/questions/1761680/what-formal-systems-are-various-programming-paradigms-based-on/1761959↩
https://swi-prolog.discourse.group/t/improving-contributor-guide-discoverability-was-consolidating-the-71-github-repositories-to-simplify-maintenance-and-contribution/492/16↩
https://www.reddit.com/r/prolog/comments/ancj74/using_logic_programming_to_recover_c_classes_and/↩
https://blog.logtalk.org/2011/03/a-more-sane-implementation-of-the-term-expansion-mechanism/↩
https://groups.google.com/forum/#!searchin/swi-prolog/clash$20module%7Csort:date/swi-prolog/f8LpJN8MYm0/uUYfUmN5AgAJ↩
http://www.haskellforall.com/2016/12/dhall-non-turing-complete-configuration.html↩
https://stackoverflow.com/questions/6695788/programming-in-the-large-with-prolog↩
https://stackoverflow.com/questions/953185/composable-grammars↩
https://rmod.inria.fr/archives/papers/Reng10cDynamicGrammars.pdf↩
https://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord.html↩
https://blog.logtalk.org/2009/12/lambda-expressions-in-logtalk/↩
http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/naish.html↩
https://github.com/webyrd/miniKanren-uncourse/wiki/Other-Interesting-Logic-or-Relational-Programming-Languages↩
http://www.cs.miami.edu/home/geoff/Courses/CSC749-17F/Content/Typed1stOrder.shtml↩
https://swi-prolog.discourse.group/t/consolidating-the-71-github-repositories-to-simplify-maintenance-and-contribution/492/10↩
https://svn.apache.org/repos/asf/subversion/trunk/notes/subversion-design.html↩
https://stackoverflow.com/questions/28465362/svn-tree-conflict-when-merging-renamed-folder↩
https://www.theregister.co.uk/2017/03/17/subversion_svn_file_renaming/↩
https://swi-prolog.discourse.group/t/being-friendly-to-quick-contributions/493/3↩
https://groups.google.com/forum/#!topic/comp.lang.prolog/-WhsxJqPRRU↩
https://dtai.cs.kuleuven.be/projects/ALP/newsletter/archive_93_96/net/grammars/compiler2.html↩
https://emacsredux.com/blog/2014/06/18/quickly-find-emacs-lisp-sources/↩
https://stackoverflow.com/questions/33707068/how-can-i-view-the-definition-of-a-function-in-lisp-sbcl↩