Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lisp Prolog and Evolution

blog.samibadawi.com

Post reply on HN
Print view View original

11–20 of 40 posts

Re: Lisp Prolog and Evolution

#11

Post by smu »

RBerenguel wrote: post #7

I find Prolog a marvel in "look what I can do!" Writing stupidly fun code in it is almost a no-brainer, compared to other languages (I have a half-assed English grammar parser in 60-odd lines, with a few comments!) But getting into prolog needs a complete rewire of how you think about programming: if you are used to imperative (or functional, or list-based, or almost whatever else) prolog feels very foreign. I'm also…

Indeed! During a security assessment of a large code base, I wrote a simple ruby source code parser that spat out Prolog terms. After that, it was a breeze to find certain kinds of logic errors, such as code paths that used user input before sanitation...

It's beautiful when it all works together, checking everything manually would certainly have been a PITA and would have resulted in a lower quality result.

Definitely an aha moment!

Re: Lisp Prolog and Evolution

#13

Post by pjmlp »

octo_t wrote: post #3

I absolutely love programming in Prolog. I've never needed to write anything large in it at all (which is where most prolog interpreters fail), but when it comes together so beautifully at the end, its quite amazing. I thoroughly recommend "The Art of Prolog" which is an engaging and fun read.

I really enjoyed learning it back in the day (94-99), specially given that many of our teachers were into Prolog and ML languages.

Sadly I seldom saw it being used commercially.

Re: Lisp Prolog and Evolution

#14

Post by pjmlp »

RBerenguel wrote: post #7

I find Prolog a marvel in "look what I can do!" Writing stupidly fun code in it is almost a no-brainer, compared to other languages (I have a half-assed English grammar parser in 60-odd lines, with a few comments!) But getting into prolog needs a complete rewire of how you think about programming: if you are used to imperative (or functional, or list-based, or almost whatever else) prolog feels very foreign. I'm also…

Back when I was at the university, Prolog and Lisp were the forbiden languages to write compilers on our compiler courses, because the teachers saw them as making the whole exercise too easy.

Re: Lisp Prolog and Evolution

#15

Post by fabriceleal »

smu wrote: post #11
RBerenguel wrote: post #7

I find Prolog a marvel in "look what I can do!" Writing stupidly fun code in it is almost a no-brainer, compared to other languages (I have a half-assed English grammar parser in 60-odd lines, with a few comments!) But getting into prolog needs a complete rewire of how you think about programming: if you are used to imperative (or functional, or list-based, or almost whatever else) prolog feels very foreign. I'm also…

Indeed! During a security assessment of a large code base, I wrote a simple ruby source code parser that spat out Prolog terms. After that, it was a breeze to find certain kinds of logic errors, such as code paths that used user input before sanitation... It's beautiful when it all works together, checking everything manually would certainly have been a PITA and would have resulted in a lower quality result. Definite…

Could you open source it? I'm very interested in seeing how one would do that, I've been thinking about writing one myself, for PHP (I've a somewhat large codebase to inherit, that only works in a old version of PHP, and I might need to migrate it).

Re: Lisp Prolog and Evolution

#16

Post by oneandoneis2 »

arethuza wrote: post #6
oneandoneis2 wrote: post #4

On the subject of why amazingly-powerful, ahead-of-their-time languages don't catch on.. I'd be interested to know if a study has ever been done on the "accessibility" of a language and its popularity. By which I mean: A total novice, even a non-programmer, can be given a simple bit of PHP/Javascript, and work out what it does and how to make minor changes to it. But something like Lisp & Haskell, you just can't do t…

"you need to spend some time learning the syntax" But Lisp has rather less syntax than most other programming languages - and that's possibly a weakness rather than a strength when it comes to anyone new to the language. I suspect there is a sweet spot when it comes to the syntactic complexity of programming languages - too little and people get lost in the generality and abstractions, too much and its difficult to r…

> Lisp has rather less syntax than most other programming languages - and that's possibly a weakness

Yup: it's like saying that binary is easier than decimal because it has less digits - the average Joe would still find it easier to do his maths in base ten :)

Re: Lisp Prolog and Evolution

#17

Post by yaantc »

oneandoneis2 wrote: post #4

On the subject of why amazingly-powerful, ahead-of-their-time languages don't catch on.. I'd be interested to know if a study has ever been done on the "accessibility" of a language and its popularity. By which I mean: A total novice, even a non-programmer, can be given a simple bit of PHP/Javascript, and work out what it does and how to make minor changes to it. But something like Lisp & Haskell, you just can't do t…

In both cases I wouldn't say that learning the syntax is the problem. The challenge IMHO lies in the different execution models. And there starting with LISP is likely a good idea, as it's less different than Prolog. It's functional, but still imperative. While in Prolog the switch to declarative programming is more disruptive in my experience (and mind blowing / expanding).

The hard thing in Prolog is that for a non trivial program (and not even a big one) it becomes necessary to understand how the underlying engine works on your code rules in order to be efficient. I had a real case where reordering a few statements meant going from ~15mn to find the first solution to a problem to a split second for all 7 ones!

What helped me with Prolog is viewing the runtime as an engine searching through a possibilities space for a solution fulfilling the program requirements (constraints). The trick is then to layout the requirements to fail early during the search, so that the engine doesn't waste time exploring doomed parts of the space of possibilities.

Re: Lisp Prolog and Evolution

#18

Post by yaantc »

arethuza wrote: post #10
dhkl wrote: post #5

Earlier quoted context omitted.

When I first learned about Prolog in AI class, the first thing that struct me was how beautiful Prolog/logic programming solutions are. In non-declarative languages like Java, you have to build up the different pieces of computations, while you keep maintaining a mental picture of how the various pieces fit together. In Prolog, you declare the entities and the relationships/constraints between them, and the system wi…

I seem to recall that one of the issue with Prolog is that, above a certain level of complexity, you can't really write purely declarative Prolog "progams" - you have to start considering the procedural aspect as well which (in certain cases) can be non-trivial.

(See my other comment below too on this topic)

You indeed have to understand how the Prolog engine works in order to structure the declarative statements of your code in a way that will lead to an efficient execution.

A way to see a Prolog programs is as a sequence of facts and statements, and at least one query. The Prolog engine will then search for a solution that fits the given facts and requirements and answer the query. In a way the Prolog engine will search a space of possible answers to the query to find the one(s) that match the given facts and requirements. The key to speed is to structure the facts and statements that the search will fail as early as possible when a wrong path is taken. This amount to pruning the useless parts of the search space as aggressively as possible, so that the Prolog engine does not waste time evaluating options that are doomed in the end.

Before getting this I was often frustrated with apparently nice and correct Prolog programs that took forever and in effect just looked stuck (at some point you just stop waiting and abort the execution). I guess it's a pretty common frustration when beginning in Prolog. But once you get it, it's possible to come up with efficient code. It's still scary to see that some small changes in statements ordering can lead to dramatic difference in runtime. You can have big differences in performance for imperative programming too, but it's rare that it's so bad that a first implementation is completely useless. In Prolog it's quite common. And the way to optimize Prolog performance is very specific, you need to learn to anticipate how the engine walks the search space. I guess it's one of the big roadblock in the practical use of Prolog.

Re: Lisp Prolog and Evolution

#19

Post by smu »

fabriceleal wrote: post #15
smu wrote: post #11

Earlier quoted context omitted.

Indeed! During a security assessment of a large code base, I wrote a simple ruby source code parser that spat out Prolog terms. After that, it was a breeze to find certain kinds of logic errors, such as code paths that used user input before sanitation... It's beautiful when it all works together, checking everything manually would certainly have been a PITA and would have resulted in a lower quality result. Definite…

Could you open source it? I'm very interested in seeing how one would do that, I've been thinking about writing one myself, for PHP (I've a somewhat large codebase to inherit, that only works in a old version of PHP, and I might need to migrate it).

I don't have the IP for the code so I can't copy it here, but what I did was very simple and the gist of it is described below:

The parser used regular expressions to recognise function definitions and calls in those definitions. I used file names as the function scope, this was good enough because there were no two functions with identical names in the same file. Function calls became the following terms: "calls(x,y,z).", meaning that function x in file y calls z.

These "calls" terms actually define a directed graph. If you google "prolog path through directed graph", there are lots of hits that will help you out. The following (untested) code should get you started:

    %there is a path if there is a call
    path(Caller, File, Called, [calls(Caller, File, Called)]) :- calls(Caller, File, Called). 
    %there is a path if there is a call to some function and there is a path from that function
    path(Caller, File, Called, [calls(Caller, File, A) | P]) :- calls(Caller, File, A), path(A, _, Called).
After that, you can find all possible paths with "findall/3" and check for existence of a certain known good/bad function with "member/2" (again, google is your friend)

Due to some properties of the code, this simple approach worked well enough for me. Hopefully this helps you out.

Re: Lisp Prolog and Evolution

#20

Post by swannodette »

A few people have asked if the video and slides for this talk are available. Unfortunately it did not get recorded and the slides don't make much sense without the words and there was a considerable amount of live coding in a REPL.

However I'll be attending http://webrebels.org where I'll be giving a more refined version of the talk - it will be recorded.

Post reply on HN