Rethinking Prolog | Hacker News Reader

Rethinking Prolog

academia.edu

37 pointsZuider16 comments

A better link: https://okmij.org/ftp/kakuritu/rethinking.pdf

The OCaml library mentioned in the paper appears to be linked as individual files from the web page here: https://okmij.org/ftp/kakuritu/Hansei.html

...not sure if it's properly published as a package anywhere.

Looks like someone collected it to GitHub here: https://github.com/cararemixed/hansei

There's some discussion here that the Hansei code may no longer work under OCaml 5: https://discuss.ocaml.org/t/multi-shot-continuations-gone-fo...

Could someone ELI5 for me how this stuff relates to Kanren? It looked superficially similar.

Past thread: https://news.ycombinator.com/item?id=8305486

Meh. As usual, functional programmers look at Prolog and completely miss the point. "Classical Prolog" (which part?) is "all about nondeterminism"?

The nondeterminism in Prolog comes from the completeness of SLD-Resolution as an inference rule. Because SLD-Resolution is complete [1], it can find every proof that exists. When there are many proofs, it is natural to have some mechanism to represent them all. Prolog does that by backtracking and trying different branches of a proof, hierarchically.

Parsing is indeed a good example of this. When a grammar is ambiguous, a string may have multiple different parses. But if a grammar is ambiguous, that's because the language it represents is ambiguous, and that means we want to represent the ambiguity, and have multiple parses. That is where a mechanism for nondeterministic return of all results is needed. A parser written in Prolog [2] will naturally backtrack and get all parses of a string.

So how about that maudlin cut, that people, like the authors of the article above, have bitched and moaned about, since the creation of Prolog? Well the cut clearly exists to avoid reaching unwanted branches of a proof, or in other words, to avoid unwanted backtracking.

But why then is there unwanted backtracking? The reason for unwanted backtracking is, invariably, that a program is over-general. In over-generalising, the program non-deterministically generates results that the programmer did not want, even as it returns (hopefully first) the results that the programmer wants. But human programmers are not perfect, and sometimes it can be too hard to write a program that is exactly as general, and as specific, as one wants, especially when the program crosses some threshold of size beyond which it is difficult to keep all of one's ducks in a row and understand exactly the behaviour of every single sub-program (i.e. predicate definition). That is when the cut is needed. The cut is a time-saver that keeps you from having to rewrite your entire program from scratch, multiple times, just because you are an imperfect programmer, and you cannot handle the full might of a programming language with Universal Turing Machine expressivity.

And more esoterically, perhaps, unwanted non-determinism arises because Resolution is semi-decidable, meaning that if a proof exists, Resultion will find it, but if a proof does not exist, it will keep trying forever. And that is the best that can be achieved under the Church-Turing thesis, and if you are unhappy with that, you can take your case with Mr. Gödel. In the meantime, you can use the cut to avoid your program going haywire, when you can tell (but the Prolog interpreter can't, because Church-Turing) that a program will loop forever after succeeding n times.

The authors say that "Classical Prolog" (really, what is that?) is not a "general purpose programming language". It is. Thanks to the cut. Now shoo, go code in your functional languages, which are safe and easy. Don't mess with my Prolog because you don't understand it.

___________________

[1] More precisely, SLD-Resolution is both sound and refutation complete.

[2] Generally, as a Definite Clause Grammar.

[3] https://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf

I tried Turbo Prolog[1] back in the 1980s. I could never figure out how to get it to do file I/O at that time, so I got frustrated and gave up. Even now, it looks fairly hopeless as a language.

Is there a modern example of the language that can do file I/O? To me, if you can't do I/O, there's no point to a language. It's why Standard Pascal lost so much ground to Turbo Pascal with it's excellent I/O support.

[1] https://ia802902.us.archive.org/1/items/bitsavers_borlandtur...

Why couldn't you do file I/O? Of course there's file I/O in Prolog, and I'd be really surprised if there wasn't in Turbo Prolog

Here's I/O in SWI-Prolog:

https://www.swi-prolog.org/pldoc/man?section=IO

I find it hard to parse your comment in good faith. You seem to say that Prolog is hopeless as a language because you couldn't find out how to do file I/O in Turbo Prolog in the '80s, when file I/O is both entirely possible and very simple to do in Prolog. It's not the fault of the language if you couldn't figure it out 40 years ago.

Edit: the Turbo Prolog manual you linked to lists the file_str/2 predicate for file I/O on page 73. Did you try that?.

I installed SWI prolog, and I can not figure out how to run the example code I found on the internet.

Here's hello.pl:

  main :- write('This is a sample Prolog program'),
      write(' This program is written into hello.pl file').

Trying to run hello.pl

  Welcome to SWI-Prolog (threaded, 64 bits, version 9.0.4)
  SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
  Please run ?- license. for legal details.
  .
  For online help and background, visit https://www.swi-prolog.org
  For built-in help, use ?- help(Topic). or ?- apropos(Word).
  .
  1 ?- [hello.pl].
  ERROR: Type error: `dict' expected, found `hello' (an atom)
  ERROR: In:
  ERROR:   [13] throw(error(type_error(dict,hello),_15432))
  ERROR:   [11] '.'(hello,pl,_15466) at c:/program files/swipl/boot/dicts.pl:57
  ERROR:   [10] '<meta-call>'(user:user: ...) <foreign>
  ERROR:    [9] toplevel_call(user:user: ...) at c:/program files/swipl/boot/toplevel.pl:1173
  ERROR:
  ERROR: Note: some frames are missing due to last-call optimization.
  ERROR: Re-run your program in debug mode (:- debug.) to get more detail.
  2 ?-

Google seems to be no help at this point, it's taken about 2 hours to get to this point. This is typical of the frustration I've experienced in my past attempts to understand this language.

You can express a bunch of facts and rules, great... but you can't actually write code to act on them, apparently. 8(

-----------

Edit -- Success has been achieved

  C:\Program Files\swipl>bin\swipl -s hello.pl -g main -g halt
  This is a sample Prolog program This program is written into hello.pl file
  C:\Program Files\swipl>

----------

Even better... here's hello2.pl

  main :- write('This is a sample Prolog program'),
      write(' This program is written into hello.pl file').
  .
  ?- main.
  ?- halt.

and it works as expected

  C:\Program Files\swipl>bin\swipl hello2.pl
  This is a sample Prolog program This program is written into hello.pl file
  C:\Program Files\swipl>

it is just

  [hello].
  %or
  ['hello.pl'].
  %or
  ["hello.pl"].

the '.' has syntactic meaning outside of quotes.

now to demonstrate file i/o:

we make a file hello.pl that has

  :- use_module(library(readutil)).

  readmyfile(Filename) :-
    open(Filename,read, Stream),
    read_line_to_string(Stream,Input),
    write("The line is:"), nl,
    write(Input), nl,
    close(Stream),
    %or slurp the whole thing
    read_file_to_string(Filename,WholeFile,[encoding(text)]),
    %lets use the formatted output predicate
    format("The file ~s has the following contents ~n~s ~n",[Filename,WholeFile]).

then launch swi and

  ?- [hello].
  true.

  ?- readmyfile('hello.pl').
  The line is:
  :- use_module(library(readutil)).
  The file hello.pl has the following contents 
  ...
  ...
  ...
  true.

>> ?- [hello.pl].

Can I ask, why did you type that?

I finally got a hello world program that works like I expect it would, here's hello.pl

  main :- write('This is a sample Prolog program'),
      write('\nThis program is written into hello.pl file').
  
  ?- main.
  ?- halt.

That shouldn't have taken 35 years. ;-)

Tells more about you than about Prolog.

Ok lay it on me

I did some Prolog programming in school but I never really got the language coming from a Pascal/C background. Your first language(s) really do affect your future learning.

Too long did not read. Me thinks Prolog should be parallel only now that we have AI-machines and such shit. It should starts every direction immediately and when some criteria is fulfilled it should start dropping answers without ever reaching the end.

fib(X,Y1+Y2):- fib(X-1,Y1),fib(X-2,Y2).

This should be legal kwestion and machine should start spewing numbers from zero to infinity.

I wish I had never opened this thread... I hate Prolog with a burning passion now, I just thought it was weird earlier. It makes brainfuck look like a walk in the park.

  ?- write(10-2).
  10-2
  true.

Why do I care? I figured out how to count to 5

  ?- foreach(between(0,5,N),writeln(N)).
  0
  1
  2
  3
  4
  5
  true.

Then since there's no way to count down, I figured I'd just do a bit of math

  ?- foreach(between(0,5,N),writeln(5-N)).
  5-0
  5-1
  5-2
  5-3
  5-4
  5-5
  true.

I can not find a single way to force the evaluation before printing, it's nuts!

arithmetic is evaluated by 'is'

  ?- A is 10-2, write(A).
  8
  A = 8.
  %or
  ?- use_module(library(clpfd)).
  true.
  ?- A #= 10-2, write(A).
  8
  A = 8.
  %this lets you do the other thing too
  ?- 8 #= A-2, write(A).
  10
  A = 10.

foreach doesn't really work the way you want it though, in this case you want forall.

  ?- forall(between(0,5,N), (A is 5-N,writeln(A))).
  5
  4
  3
  2
  1
  0
  true.

Wow... ok... I can calm down a bit... thanks for the help!

Reply on news.ycombinator.com