3 ms·

Really, how does it handle parsing? What kind of languages can you parse? I recall this paper, by Joe Armstrong of Erlang... I'll have to go read it again. "

by chubot 10y ago

Really, how does it handle parsing? What kind of languages can you parse? I recall this paper, by Joe Armstrong of Erlang... I'll have to go read it again. "Use of Prolog for developing a new programming language" https://scholar.google.com/scholar?cluster=2346610420909745067&hl=en&as_sdt=0,5&sciodt=0,5 https://scholar.google.com/scholar?cluster=23466104209097450... Hm after scanning it, I think the reason I never really got it the first time around is that I don't know Prolog :) Might be time to fix that. What turned me off to Prolog is that there's no way to reason about the computational complexity of the algorithm. Declarative languages often have this problem. That's why you have SQL queries that literally take thousands of times longer than a Python script in production (hours vs seconds). Programming models also need performance models.

abecedarius 10y ago
https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar -- parsing in Prolog. As usual with Wikipedia on technical topics it looks like a poor introduction, sorry. Reasoning about performance is quite possible; there's good advice in Richard O'Keefe's The Craft of Prolog. [Edit: fixed the book title, thanks to a friendly correction. The Practice of Prolog is a different book, also good, but less relevant.]
- qohen 10y ago
  As usual with Wikipedia on technical topics it looks like a poor introduction, sorry. There are real tutorials on DCGs available, e.g. http://www.pathwayslms.com/swipltuts/dcg/ http://www.pathwayslms.com/swipltuts/dcg/ (BTW, SWI-Prolog, which the tutorial uses, is freely available here: http://www.swi-prolog.org/ http://www.swi-prolog.org/ )
  - qohen 10y ago
    Also, if you want to dive deeper, the book, "Prolog and Natural Language Analysis" by Fernando C. N. Pereira and Stuart M. Shieber, is available as a free PDF from the publisher: http://www.mtome.com/Publications/PNLA/prolog-digital.pdf http://www.mtome.com/Publications/PNLA/prolog-digital.pdf And there's a set of course materials in HTML for "Natural Language Processing in Prolog", a course at Union College in Schenectady, NY by Patrick Blackburn and Kristina Striegnitz that seems worthwhile: http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/toc.html http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/t...
deleted 10y ago
[deleted]
YeGoblynQueenne 10y ago
>> What turned me off to Prolog is that there's no way to reason about the computational complexity of the algorithm. That's easy to figure out once you realise your code also has an imperative reading. So for instance it's obvious that reversing a list: reverse(A, B) :- reverse(A, [], B, B). reverse([], A, A, []). reverse([B|A], C, D, [_|E]) :- reverse(A, [B|C], D, E). takes time proportional to the lists' length, since you're walking through the list an element at a time. And it's easy to figure out that consing, as in [B|C], is a constant-time operation. Or, for instance, say you wanted to apply reverse/4 to elements of a list-of-lists: findall(L_, (member(L, Ls), reverse(L, L_)), Ls_). You can see that this is going to take the time to go through Ls, times the time to reverse each L. Same goes for the recursive version, except we need to reverse the output also to get it back in the right order: revall(Ls, Ls_):- revall(Ls, [], Ls_). revall([], Ls, Ls_):- reverse(Ls, Ls_) ,!. revall([L|Ls],Acc,Bind):- reverse(L, L_) ,revall(Ls, [L_|Acc], Bind). So it's not different than any other language really, and in fact you can, up to a point, completely ignore the declarative meaning of your program if you just want to think about how fast it's going to go.

by chubot 10y ago

abecedarius 10y ago

https://en.wikipedia.org/wiki/Definite_clause_grammar https://en.wikipedia.org/wiki/Definite_clause_grammar -- parsing in Prolog. As usual with Wikipedia on technical topics it looks like a poor introduction, sorry. Reasoning about performance is quite possible; there's good advice in Richard O'Keefe's The Craft of Prolog. [Edit: fixed the book title, thanks to a friendly correction. The Practice of Prolog is a different book, also good, but less relevant.]

qohen 10y ago
As usual with Wikipedia on technical topics it looks like a poor introduction, sorry. There are real tutorials on DCGs available, e.g. http://www.pathwayslms.com/swipltuts/dcg/ http://www.pathwayslms.com/swipltuts/dcg/ (BTW, SWI-Prolog, which the tutorial uses, is freely available here: http://www.swi-prolog.org/ http://www.swi-prolog.org/ )
- qohen 10y ago
  Also, if you want to dive deeper, the book, "Prolog and Natural Language Analysis" by Fernando C. N. Pereira and Stuart M. Shieber, is available as a free PDF from the publisher: http://www.mtome.com/Publications/PNLA/prolog-digital.pdf http://www.mtome.com/Publications/PNLA/prolog-digital.pdf And there's a set of course materials in HTML for "Natural Language Processing in Prolog", a course at Union College in Schenectady, NY by Patrick Blackburn and Kristina Striegnitz that seems worthwhile: http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/toc.html http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/t...

deleted 10y ago

[deleted]

YeGoblynQueenne 10y ago

>> What turned me off to Prolog is that there's no way to reason about the computational complexity of the algorithm. That's easy to figure out once you realise your code also has an imperative reading. So for instance it's obvious that reversing a list: reverse(A, B) :- reverse(A, [], B, B). reverse([], A, A, []). reverse([B|A], C, D, [_|E]) :- reverse(A, [B|C], D, E). takes time proportional to the lists' length, since you're walking through the list an element at a time. And it's easy to figure out that consing, as in [B|C], is a constant-time operation. Or, for instance, say you wanted to apply reverse/4 to elements of a list-of-lists: findall(L_, (member(L, Ls), reverse(L, L_)), Ls_). You can see that this is going to take the time to go through Ls, times the time to reverse each L. Same goes for the recursive version, except we need to reverse the output also to get it back in the right order: revall(Ls, Ls_):- revall(Ls, [], Ls_). revall([], Ls, Ls_):- reverse(Ls, Ls_) ,!. revall([L|Ls],Acc,Bind):- reverse(L, L_) ,revall(Ls, [L_|Acc], Bind). So it's not different than any other language really, and in fact you can, up to a point, completely ignore the declarative meaning of your program if you just want to think about how fast it's going to go.