1Finding psychological security before going full Prolog

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:
    • <2018-12-09> SWI-Prolog open/4 has "update" mode2
    • <2018-12-09> ECLiPSe Prolog open/4 has "update" mode3
  • Prolog implementations that cannot open a file for writing without truncating it:
    • <2018-12-09> GNU Prolog4
    • <2018-12-09> SICStus Prolog5
    • <2018-12-09> Ciao Prolog6

<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?

SWISH?1415

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:

What:

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.

  • 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 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

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

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

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) or edit(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:

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?

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

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".

  1. 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

But you can emulate other search algorithms too.

  1. 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:

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 satisfying a. If a can be satisfied in N ways, and satisfying b 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

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

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 to beget or sire?

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

  1. 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.

  2. Executable specification?

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

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

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:

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?

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 object
  • A ? 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?

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?

:- 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?

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?

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

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

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),_)).

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.

The printed message is the concatenation of all 'Line's.

TODO:

  • How do we log to file?
  • How do we rotate log files?

References:

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

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?

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

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?

Prolog marelle, Haskell shake, build system?

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.

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."

http://collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/Website/articles/DDJ/1989/8910/8910f/8910f.htm

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?

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?

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?

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

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

https://math.stackexchange.com/questions/2112719/what-is-the-difference-between-herbrand-logic-and-relational-logic-or-predicate

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?

https://math.stackexchange.com/questions/2394518/why-was-the-resolution-method-so-important-to-ai-theorem-proving?

11.4What is wrong with Prolog?

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

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.

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.

  • 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

13.15Making compilers

"Universal-transpiler" may be similar to what we want.

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?

13.17.2Lambda-prolog?

13.18Resources for beginners?

  • "Real World Programming in SWI-Prolog"71
  • "Frequently Asked Questions for ##Prolog"72

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?

  • 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?
    • 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.)

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

"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

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?

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

  • 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?

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?

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

  • 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;
};

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

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?

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.
    • The next motivation was to reduce disk and memory usage.
  • 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

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?

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) where Path 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.8Implementing modules

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

  • Elixir

  • 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

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

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

15.3.2Embedding Haskell in Prolog: Nobody is talking about this?

translate haskell to prolog

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)).
  • 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."

Mercury vs Prolog

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

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:

  1. Assert A.
  2. Call B.
  3. 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

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?

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?

<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-function109 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>.

  1. https://www.amzi.com/manuals/amzi/pro/ref_io.htm↩

  2. http://www.swi-prolog.org/pldoc/doc_for?object=open/4↩

  3. http://eclipseclp.org/doc/bips/kernel/iostream/open-4.html↩

  4. http://www.gprolog.org/manual/html_node/gprolog034.html#open%2F4↩

  5. https://sicstus.sics.se/sicstus/docs/4.2.1/html/sicstus/mpg_002dref_002dopen.html↩

  6. https://ciao-lang.org/docs/1.14/13646/CiaoDE-1.14.2-13646_ciao.html/streams_basic.html#open/4↩

  7. http://www.swi-prolog.org/FAQ/PrologLAMP.txt↩

  8. https://www3.hhu.de/stups/prob/index.php/Why_Prolog%3F↩

  9. https://www.semanticscholar.org/paper/On-the-Implementation-of-GNU-Prolog-Diaz-Abreu/2c4f697f96202f988602e88c49625a862a4ce696↩

  10. https://en.wikipedia.org/wiki/Comparison_of_Prolog_implementations↩

  11. http://www.david-reitter.com/compling/prolog/compare.html↩

  12. http://www.fraber.de/university/prolog/comparison.html↩

  13. http://tau-prolog.org/↩

  14. http://www.swi-prolog.org/IDE.html↩

  15. https://stackoverflow.com/questions/5277263/good-ide-to-get-started-with-prolog↩

  16. https://swi-prolog.discourse.group↩

  17. https://groups.google.com/forum/#!forum/swi-prolog↩

  18. https://github.com/klauscfhq/awesome-prolog/blob/master/readme.md↩

  19. https://stackoverflow.com/questions/14168363/what-does-a-clause-without-a-head-mean-in-prolog↩

  20. https://en.wikipedia.org/wiki/Abraham%27s_family_tree↩

  21. https://en.wikipedia.org/wiki/SLD_resolution↩

  22. http://www.swi-prolog.org/pldoc/man?section=implhistory↩

  23. https://vanemden.wordpress.com↩

  24. https://vanemden.wordpress.com/2017/09/08/conceptual-integrity-why-it-matters-and-how-to-get-it/↩

  25. https://en.wikipedia.org/wiki/Extension_(predicate_logic)↩

  26. https://en.wikipedia.org/wiki/Fire_triangle↩

  27. http://www.swi-prolog.org/pldoc/man?section=ext-compound-zero↩

  28. http://www.swi-prolog.org/pack/list?p=plgi↩

  29. https://github.com/SWI-Prolog/roadmap/issues/29↩

  30. http://www.swi-prolog.org/packages/xpce/UserGuide/exeobjects.html↩

  31. https://www.reddit.com/r/linux/comments/2dxik3/future_of_gnome_and_gtk_when_whole_world_is/↩

  32. https://www.reddit.com/r/linuxmasterrace/comments/7xkcwo/why_does_everyone_hate_gtk/↩

  33. http://www.swi-prolog.org/pldoc/doc_for?object=section(%27packages/plunit.html%27)↩

  34. https://logtalk.org/tools.html↩

  35. https://logtalk.org/manuals/userman/documenting.html↩

  36. https://logtalk.org/manuals/userman/declarative.html↩

  37. http://www.swi-prolog.org/pldoc/man?section=strings↩

  38. http://www.swi-prolog.org/pldoc/man?section=ext-dquotes-motivation↩

  39. http://eclipseclp.org/wiki/Prolog/Strings↩

  40. http://fsl.cs.illinois.edu/images/9/9c/PrologStandard.pdf↩

  41. https://en.wiktionary.org/wiki/prorogue↩

  42. https://logtalk.org/manuals/userman/features.html↩

  43. http://www.swi-prolog.org/pldoc/man?section=record↩

  44. https://docs.racket-lang.org/reference/define-struct.html↩

  45. https://logtalk.org/documentation.html↩

  46. https://logtalk.org/guides.html↩

  47. https://github.com/LogtalkDotOrg/logtalk3↩

  48. https://logtalk.org/running_developer_versions.html↩

  49. https://en.wikipedia.org/w/index.php?title=Side_effect_(computer_science)&oldid=855461052↩

  50. https://softwareengineering.stackexchange.com/questions/40297/what-is-a-side-effect↩

  51. https://en.wikipedia.org/w/index.php?title=Side_effect&oldid=875244456↩

  52. http://www.dubberly.com/articles/distinguishing-between-control-and-collaboration-and-communication-and-conversation.html↩

  53. http://www.swi-prolog.org/howto/http/HelloHTML.html↩

  54. http://www.swi-prolog.org/pldoc/man?section=persistency↩

  55. https://www3.cs.stonybrook.edu/~warren/xsbbook/node11.html↩

  56. http://www.swi-prolog.org/pldoc/man?section=cql↩

  57. https://swi-prolog.discourse.group/t/scaling-to-billions-of-facts/380/2↩

  58. https://stackoverflow.com/questions/25641240/is-it-possible-to-partially-refresh-a-materialized-view-in-postgresql↩

  59. https://news.ycombinator.com/item?id=12941910↩

  60. https://github.com/salva/plswipl↩

  61. http://hiro-tan.org/~ekoontz/psqlog/doc/psqlog.html↩

  62. https://twiki.org/cgi-bin/view/Plugins/SwiPrologToPostgreSqlAddOn↩

  63. http://xsb.sourceforge.net/manual2/manual2.pdf↩

  64. http://mrhoyestokwebsite.com/Knower/Useful%20Information/Three%20Different%20Theories%20of%20Truth.htm↩

  65. https://en.wikipedia.org/wiki/Truth↩

  66. http://logic.stanford.edu/herbrand/herbrand.html↩

  67. https://conference.imp.fu-berlin.de/cade-25/download/2015_CADE_ruleml_genesere.pdf↩

  68. http://www.lix.polytechnique.fr/~dale/lolli/↩

  69. https://math.stackexchange.com/questions/1761680/what-formal-systems-are-various-programming-paradigms-based-on/1761959↩

  70. https://gym.openai.com↩

  71. http://www.pathwayslms.com/swipltuts/index.html↩

  72. http://www.pathwayslms.com/swipltuts/student/↩

  73. https://swi-prolog.discourse.group/t/improving-contributor-guide-discoverability-was-consolidating-the-71-github-repositories-to-simplify-maintenance-and-contribution/492/16↩

  74. https://github.com/SWI-Prolog/swipl-devel/pull/459↩

  75. https://www.discourse.org↩

  76. https://twitter.com/r_Prolog/status/1092721329596444672↩

  77. https://www.reddit.com/r/prolog/comments/ancj74/using_logic_programming_to_recover_c_classes_and/↩

  78. https://blog.logtalk.org/2011/03/a-more-sane-implementation-of-the-term-expansion-mechanism/↩

  79. https://groups.google.com/forum/#!searchin/swi-prolog/clash$20module%7Csort:date/swi-prolog/f8LpJN8MYm0/uUYfUmN5AgAJ↩

  80. http://www.haskellforall.com/2016/12/dhall-non-turing-complete-configuration.html↩

  81. https://stackoverflow.com/questions/6695788/programming-in-the-large-with-prolog↩

  82. https://en.wikipedia.org/wiki/Adaptive_grammar↩

  83. https://news.ycombinator.com/item?id=2330830↩

  84. https://stackoverflow.com/questions/953185/composable-grammars↩

  85. https://en.wikipedia.org/wiki/Scannerless_parsing↩

  86. https://en.wikipedia.org/wiki/The_lexer_hack↩

  87. https://rmod.inria.fr/archives/papers/Reng10cDynamicGrammars.pdf↩

  88. https://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord.html↩

  89. https://blog.logtalk.org/2009/12/lambda-expressions-in-logtalk/↩

  90. https://en.wikipedia.org/wiki/Lambda_lifting↩

  91. http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/naish.html↩

  92. https://github.com/webyrd/miniKanren-uncourse/wiki/Other-Interesting-Logic-or-Relational-Programming-Languages↩

  93. https://en.wikipedia.org/wiki/Resolution_(logic)↩

  94. http://www.cs.miami.edu/home/geoff/Courses/CSC749-17F/Content/Typed1stOrder.shtml↩

  95. https://gmplib.org/manual/Introduction-to-GMP.html↩

  96. https://gcc.gnu.org/onlinedocs/cpp/Overview.html#Overview↩

  97. https://swi-prolog.discourse.group/t/consolidating-the-71-github-repositories-to-simplify-maintenance-and-contribution/492/10↩

  98. https://svn.apache.org/repos/asf/subversion/trunk/notes/subversion-design.html↩

  99. https://stackoverflow.com/questions/28465362/svn-tree-conflict-when-merging-renamed-folder↩

  100. https://www.theregister.co.uk/2017/03/17/subversion_svn_file_renaming/↩

  101. http://www.swi-prolog.org/howto/SubmitPatch.html↩

  102. http://www.swi-prolog.org/build/unix.html↩

  103. https://swi-prolog.discourse.group/t/being-friendly-to-quick-contributions/493/3↩

  104. http://www.swi-prolog.org/pldoc/man?section=foreign↩

  105. http://www.swi-prolog.org/pack/list?p=ffi↩

  106. https://groups.google.com/forum/#!topic/comp.lang.prolog/-WhsxJqPRRU↩

  107. https://dtai.cs.kuleuven.be/projects/ALP/newsletter/archive_93_96/net/grammars/compiler2.html↩

  108. https://en.wikipedia.org/wiki/Unicode_equivalence↩

  109. https://emacsredux.com/blog/2014/06/18/quickly-find-emacs-lisp-sources/↩

  110. https://stackoverflow.com/questions/33707068/how-can-i-view-the-definition-of-a-function-in-lisp-sbcl↩

  111. https://web.cs.wpi.edu/~jshutt/adapt/top.html↩