News for hackers. Stuff that matters.
Re:Show HN: Writing an HTTP server in Prolog by gnarbarian on Saturday November 12, 2016 @07:12PM (#12941004)
Prolog is extremely different than other programming languages and as a result, learning it and writing a few small programs is very mind expanding.

It really drives home how different paradigms are suited to different problems. Prolog is suited toward problems like Einsteins riddle

https://udel.edu/~os/riddle.html

Re:Show HN: Writing an HTTP server in Prolog by rtpg on Sunday November 13, 2016 @12:19AM (#12941984)
A very interesting aspect of Prolog is how its primary primitive is backtracking search.

This is orders of magnitude more complex than C-language style primary primitives which closely match single machine instructions. Or even slightly more complex models in lazy languages like Haskell.

It's strange that you can build a language almost purely off of graph search yet have it be generally useful. Makes you wonder what other techniques spawn their own paradigm.

Re:Show HN: Writing an HTTP server in Prolog by Allan_Smithee on Sunday November 13, 2016 @06:11AM (#12942817)
There's at least one language (Refal: there may be more!) based on Markov algorithms. Another language (XL: as far as I know this is the only one of its breed thus far) works at its core on parse tree substitution. Yet another (CHR) does a weird generalization of term re-writing to provide a toolkit for making constraint languages. (Yes, a language to make languages.)

There's a reason I've become a programming language whore.

Re:Show HN: Writing an HTTP server in Prolog by vram22 on Sunday November 13, 2016 @07:10AM (#12942961)
>(Yes, a language to make languages.)

Are there any other languages that are mainly designed with the goal of making it easier to make other general-purpose languages (as opposed to languages for DSLs or parser generation etc.)?

I know that generally many languages are written in C or compile to C, and that Lisp can also be used to make other languages or sub-languages.

But asking about languages (mostly) dedicated for that purpose - creation of new general-purpose programming languages.

Re:Show HN: Writing an HTTP server in Prolog by tom_mellior on Sunday November 13, 2016 @10:35AM (#12943797)
The K framework: http://www.kframework.org/index.php/Main_Page It's a system for formally expressing the semantics of programming languages and getting an interpreter.

That said, the parent's claim about CHR is rather broad, and you may have read too much into it. It's a library for writing new constraint programming libraries for Prolog. Combined with operator overloading, you get embedded DSLs for constraint systems. That's great, and it is "language development" in some sense. But CHR is not a tool for implementing interpreters or compilers for new programming languages (though it may be useful for some subtasks).

Re:Show HN: Writing an HTTP server in Prolog by vram22 on Sunday November 13, 2016 @12:00PM (#12944242)
Yes, I did get that from what he said about CHR - it is constrained (heh) to that area of constraint systems.

Interesting about the K framework, thanks. Will take a look. That's the sort of thing I was asking about - if such existed.

Re:Show HN: Writing an HTTP server in Prolog by kazinator on Sunday November 13, 2016 @10:33PM (#12947333)
Lisp is used for making languages that can usually be all used together in the same project and even mixed together.

If I had to write a C or C++ compiler from scratch, I'd do it in Lisp. That project probably wouldn't work in the usual "language inside Lisp" way; it would spit out assembly code or object files which then have nothing to do with Lisp.

The GNU people who originally wrote GCC (Stallman, et al) wanted to use Lisp; they write in C instead because it was well supported on Unix-like system. Stallman is a Lisper; he was on the ANSI CL committee and of course is well known for the Emacs work.

GCC internals are full of Lisp terminology and "Frankenstein monster" versions of Lisp data structures.

As an example, someone posted the following link on Reddit, in the Japanese subreddit:

https://gcc.gnu.org/git/?p=gcc.git;a=commit;h=28251d450e034f...

It's a GCC commit, whose message discusses the optimization using Lisp notation. The C code doesn't look like Lisp, but the comment explains what it's doing as an S-exp.

Re:Show HN: Writing an HTTP server in Prolog by vram22 on Monday November 14, 2016 @11:32AM (#12950912)
"The GNU people who originally wrote GCC (Stallman, et al) wanted to use Lisp; they write in C instead because it was well supported on Unix-like system."

Interesting, did not know they wanted to use Lisp for GCC, though I've read some about Stallman's work.

Edit:

Makes sense, I guess. I've read that functional languages are well-suited to the domain of writing language compilers. Seems logical, because a transformation from, say, a C program to assembly or machine code, can be thought of as a function call:

y = f(x)

where x is the C program, y the machine code, and f the compiler :)

"Stallman is a Lisper; he was on the ANSI CL committee and of course is well known for the Emacs work."

True.

Re:Show HN: Writing an HTTP server in Prolog by kazinator on Monday November 14, 2016 @12:31PM (#12951510)
On this same topic, see this amusing comment in the middle of Bash:

http://git.savannah.gnu.org/cgit/bash.git/tree/unwind_prot.c

Firstly, the non-local jumps that handle Ctrl-C in Bash and whatnot are referred to using the "unwind protect". Then see the comment in that file:

  /* I can't stand it anymore!  Please can't we just write the
     whole Unix system in lisp or something? */
:)
Re:Show HN: Writing an HTTP server in Prolog by lispm on Monday November 14, 2016 @03:53PM (#12953248)
Stallman was member of X3J13?

What did he do there?

Re:Show HN: Writing an HTTP server in Prolog by kazinator on Monday November 14, 2016 @06:21PM (#12954262)
Am I mis-remembering something?

[update: no]

Richard Gabriel's and Guy Steele's Evolution of Lisp lists Stallman among the people in a "Common Lisp Group".

See: https://www.dreamsongs.com/Files/Hopl2.pdf (P. 21)

Steele's CLTL (1) gives a list of people who were involved in the actual ANSI XJ13, but Stallman isn't listed.

Stallman, however, is credited in that very same book and section as having worked on an implementation of the "New Error System" (NES) as follows: "A reimplementation of the NES for non-Symbolics Lisp Machine dialects (MIT, LMI, and TI) was done at MIT by Richard M. Stallman. During the process of that reimplementation, some conceptual changes were made which have significantly influenced the Common Lisp Condition System."

There you go: Stallman is noted as having been part of an early "Common Lisp Group", and did some implementation work which influenced the CL condition system.

Re:Show HN: Writing an HTTP server in Prolog by lispm on Tuesday November 15, 2016 @07:29AM (#12957442)
On the Common Lisp mailing list there are 30 mails from RMS.

His participation ended in 83. Before CLtL1 was published and way before X3J13 was started.

I'd say RMS was never a member of X3J13.

Re:Show HN: Writing an HTTP server in Prolog by lispm on Monday November 14, 2016 @11:53PM (#12955687)
This was not ANSI CL. This was CLtL1 Common Lisp. X3J13 was formed a few years later. I never heard of him being active in X3J13.

Stallman never did much work with or on CL. I never had the impression that Stallman was very active in CL design. The mailing list protocols would clear this up...

Stallman actually does not like CL and has critized CL features many times and prevented them to be used in GNU Emacs.

The NES was done at Symbolics. Stallman likely tried to copy it for LMI, while he was fighting against Symbolics. But that phase did not last long.

Re:Show HN: Writing an HTTP server in Prolog by fulafel on Sunday November 13, 2016 @08:57AM (#12943327)
People sometimes say ML is aimed at compiler writing.
Re:Show HN: Writing an HTTP server in Prolog by agumonkey on Monday November 14, 2016 @06:47AM (#12949164)
Because FP is in love with algebra and trees, which are the bread and butter of ASTs.
Re:Show HN: Writing an HTTP server in Prolog by freeduck on Sunday November 13, 2016 @09:31AM (#12943442)
Lisp. Clojure for instance has a built in logic language called miniKanren
Re:Show HN: Writing an HTTP server in Prolog by vram22 on Sunday November 13, 2016 @02:32PM (#12945138)
Interesting. IIRC I came across a series of libs from that family recently - for different languages, including Python. Need to check it out. Update: Googled, it's right here:

https://en.wikipedia.org/wiki/MiniKanren

From that page:

"There are implementations of miniKanren in Haskell, Racket, Ruby, Clojure, and Python. The canonical implementation is an embedded language in Scheme. The Clojure core.logic library was inspired by miniKanren."

The name kanren comes from a Japanese word for "relation".

Re:Show HN: Writing an HTTP server in Prolog by jamesbvaughan on Saturday November 12, 2016 @07:22PM (#12941037)
The class I was taking kind of blew my mind when I saw how you can solve some problems in such cool ways with Prolog, but I would certainly admit that this server isn't exactly the kind of use it's best suited for.
Re:Show HN: Writing an HTTP server in Prolog by doublec on Sunday November 13, 2016 @12:27AM (#12942010)
You might be surprised! SWI Prolog has libraries for web applications (http://www.pathwayslms.com/swipltuts/html/index.html) and other modern application development toolkits. Their online IDE (http://swish.swi-prolog.org/) is written in Prolog.
Re:Show HN: Writing an HTTP server in Prolog by xapata on Saturday November 12, 2016 @07:39PM (#12941112)
Python's set class and comprehension syntax can get you much of the declarative power of Prolog.
Re:Show HN: Writing an HTTP server in Prolog by siddboots on Saturday November 12, 2016 @11:51PM (#12941930)
How so? I mean, there are logic libraries available for python to be sure. But the "set class and comprehension syntax" are two features only tangentially related to logic programming. Using them alone doesn't get you inference, or even unification.
Re:Show HN: Writing an HTTP server in Prolog by xapata on Sunday November 13, 2016 @04:06AM (#12942508)
Inference is straightforward using dictionaries, membership-testing, and set methods, like subset, superset, disjoint, union, intersection, and difference.

Python can't do a conditional assignment as nicely as Prolog's unification, but you can get similar behavior via the application of predicates in comprehensions and using set methods. I'm not saying Python is equivalent, but simply that you can get some of Prolog's style in Python. Erlang's pattern matching and concept of bound vs unbound variables is a bit closer to Prolog's unification.

Here's some Python implementations for examples shown in my first Google result for "prolog examples" (http://www.cs.toronto.edu/~sheila/384/w11/simple-prolog-exam...)

1. Here are some simple clauses.

    >>> likes = {'mary': {'food', 'wine'},
    ...          'john': {'wine', 'mary'}}
    >>> 'food' in likes['mary']
    True
    >>> 'wine' in likes['john']
    True
    >>> 'food' in likes['john']
    False
    >>> # John likes anything that Mary likes
    >>> likes['john'] |= likes['mary']
    >>> # John likes anyone who likes wine
    >>> likes['john'] |= {name for name, objs likes.items() if 'wine' in objs}
    >>> # John likes anyone who likes themselves
    >>> likes['john'] |= {name for name, objs in likes.items() if name in objs}
2. Slightly more complicated family tree.

   >>> male = {'james1', 'charles1', 'charles2', 'james2', 'george1'}
   >>> female = {'catherine', 'elizabeth', 'sophia'}
    >>> parents = {'charles1': 'james1',
    ...            'elizabeth': 'james1',
    ...            'charles2': 'charles1',
    ...            'catherine': 'charles1',
    ...            'james2': 'charles1',
    ...            'sophia': 'elizabeth',
    ...            'george1': 'sophia'}
    >>> # Was George I the parent of Charles I?
    >>> parents['charles1'] == 'george1'
    False
    >>> # Who was Charles I's parent?
    >>> parents['charles1']
    'james1'
    >>> # Who were the children of Charles I?
    >>> {child for child, parent in parents.items() if parent == 'charles1'}
    {'charles2', 'james2', 'catherine'}
3. Recursion: Towers of Hanoi

    >>> def move_one(x, y):
    ...     print('Move top disk from {0} to {1}'.format(x, y))
    ...     return True
    ...
    >>> def move(n, x, y, z):
    ...     if n == 1:
    ...             return move_one(x, y)
    ...     m = n - 1
    ...     move(m, x, z, y)
    ...     move_one(x, y)
    ...     return move(m, z, y, x)
    ...
    >>> move(3, 'left', 'right', 'center')
    Move top disk from left to right
    Move top disk from left to center
    Move top disk from right to center
    Move top disk from left to right
    Move top disk from center to left
    Move top disk from center to right
    Move top disk from left to right
    True
4. An example using lists:

This last one is a bit silly in Python as all the tools shown are built-ins.

Re:Show HN: Writing an HTTP server in Prolog by siddboots on Sunday November 13, 2016 @07:35PM (#12946674)
I appreciate you taking the time. Your approach shows the first steps towards building an inference engine in Python, but these are all very trivial examples. The difference between this and a real logic language will become apparent as the database of facts and rules becomes more complicated.

In order to follow this through, you would need to separate all of search code (i.e. the comprehensions) from the declaration of facts and rules. If you were successful in doing so, you will have made a basic logical inference engine in Python.

Consider one of the queries described in the family tree example: "M is the mother of X if she is a parent of X and is female"

In Prolog this might look like:

    mother(X, M) :-
       parent(X, M),
       female(M).
Having built that rule, I can ask

1) Who is the mother of sophia? : mother(sophia, X).

2) Who is sophia the mother of? : mother(X, sophia).

3) Which mothers have male children? : mother(M, X), male(M).

The question is, how would you define the `mother` relation using comprehensions in a way that is agnostic to the specific questions that will be asked? You would inevitably need to write different loop for each variant of the question. The trick is to write an engine that, given a query, automatically generates the comprehensions required to find the answers. It isn't an easy problem at all.

To make this even clearer, consider your claim that the tools in part 4 are trivial in python, because they are all built-ins. But this is not true at all! Python's built-ins are one-way functions, rather than relations. In python I can ask "what is the sum of the elements in this list?" but I can't as easily ask "what is a list with 30 unique integer elements that sum to 100" To do this in python you would need to put some thought in to how you would generate lists using nested loops so that all of the properties were satisfied. In Prolog you just list the search criteria and it does the work for you:

    size(L, 30),
    unique(L),
    sum(L, 100).
Edit: By the way, check out pyDatalog if you are interested in a fully featured inference engine built in python:

https://sites.google.com/site/pydatalog/

Re:Show HN: Writing an HTTP server in Prolog by xapata on Sunday November 13, 2016 @09:15PM (#12947071)
Prolog relaxes the requirement to think linearly, bottom-up. If you write all the facts and predicates bottom-up it's easy in Python. Dictionaries, sets, and comprehensions take care of everything. As you say, it's trivial.

If you want to write top-down, defining what a mother is before defining who are parents and who are female, then you'll need to write functions and it gets trickier in Python. The sticking point is when to transition from functions to dict/set -- what's a predicate and what's a fact. We could get fancy with decorators to create some funky predicate class, but let's stay away from metaprogramming for the moment.

I agree that Python (without getting fancy) requires the programmer to think through a bit more of the inferential logic than Prolog would under some circumstances. How often do those circumstances arise in practical problems? I'm not sure.

However, I've got to accept the challenge: "What is a list with 30 unique integer elements that sum to 100?"

First, there is no list with 30 unique positive integers that sum to 100.

    >>> sum(range(30))
    435
Allowing negatives would create an infinity of possible solutions. So, I'm going to rephrase the problem: Generate a list of N unique positive integers that sum to M.

    >>> from itertools import combinations
    >>> m = 30
    >>> n = 5
    >>> combos = (c for c in combinations(range(m), n) if sum(c) == m)
    >>> next(combos)
    (0, 1, 2, 3, 24)
Re:Show HN: Writing an HTTP server in Prolog by justinhj on Saturday November 12, 2016 @10:57PM (#12941780)
that's a tiny subset of what Prolog can do