9 ms·

Interpreter for a simple Lisp, Written in Prolog

120 points by martinlaz 8y ago

jasim 8y ago
It seems that it takes far fewer lines of code (and correspondingly simple program model) to implement LISP in Prolog than both imperative and functional languages. Once I asked a Prolog expert at a conference "Prolog is truly mind-bending and powerful, but why don't we see it used more often? where are the jobs so I could get one" and they said that for those who use Prolog in production it is a real competitive advantage that they don't want to announce to the world; plus some are state actors and quasi-state actors who use it for huge scheduling and optimization problems and like their secrets secret. I think I believe that.
- petra 8y ago
  Every new powerful tool/language probably offers a competitive advantage to some companies. Yet, nothing is really a secret in the world of software development. Why is prolog among the rare few who can keep a secret ?
  - JaumeGreen 8y ago
    Because prolog requires a different mindset. When I encountered prolog I tried to understand it, and on the assigment -something about stacking dice having same or different values on the faces, I don't recall it- I managed to write prolog with explicit backtracking. That means that I had several "functions" with different fixed parameters that where the recursion level where they were at, and like a hundred lines of code for this assigment. TA called us in, trying to understant that, we explained and he showed us the "real" solution, in a handful of lines of code. Then it clicked, I understood it. Without that moment I would find prolog too alien, and I guess most people do, that's why it isn't more present in the world. It's too different to "actual programming", that is, it's too different from imperative programming. Even haskell and the like are closer to python and the like than prolog. Heck, even lisp can be closer to them. It's not just learning a new programming language, it's learning a new way to think, not everyone can do that.
    - SolaceQuantum 8y ago
      The most effective way prolog has been taught to me in the form of logic puzzles that we are all familiar with- "We have 6 people who work 1 job each, here a list of possible jobs, there is a list of possible people, the cook is male, the doctor went golfing with the cook on friday, joshua doesn't golf..." After that, you move to programming checking validation of facts and finally to behavior that resembles 'normal' programming. I agree that it's a massively different mindset and the capacity to grasp prolog quickly or be interested in prolog programming should be considered a reflection of the adaptability/curiosity of a person, IMHO.
    - hcarvalhoalves 8y ago
      Prolog tends to "click" once you understand it's a query language for relations, rather than a general programming language (although you can do a lot on top of it you bend it just enough).
- 0db532a0 8y ago
  Do you know of anyone combining prolog with integer linear programming? I modelled quite a complex convex optimisation problem as a mixed integer linear programme, but it was very buggy at the beginning to say the least. I was left wishing that there was a better way to express the logical constraints, which in any case can be converted to integer linear equations, while keeping the linear equations where needed and possible.
  - yaantc 8y ago
    ECLiPSe CLP [1] (no relation with the IDE) is a Prolog implementation with constraint logic programming support and interfaces to lots of solvers, including MIP ones [2]. So I guess the answer is yes, although you may not find lots of public use-cases. Eclipse CLP was bought and open sourced by Cisco. [1] http://eclipseclp.org/ http://eclipseclp.org/ [2] From http://eclipseclp.org/features.html http://eclipseclp.org/features.html: "Solver Interfaces. ECLiPSe interfaces to the COIN-OR, CPLEX, Gurobi and XPRESS-MP linear and mixed-integer programming solvers, and the Gecode finite-domain solver. Other interfaces are under development."
    - 0db532a0 8y ago
      Seems to be exactly what I was looking for. Thanks.
  - YeGoblynQueenne 8y ago
    Markus Triska, the author of the Lisp interpreter above has also contributed library(simplex), a linear programming library for Swi-Prolog: http://www.swi-prolog.org/pldoc/man?section=simplex http://www.swi-prolog.org/pldoc/man?section=simplex
    - 0db532a0 8y ago
      From first look, this library doesn't seem to provide a way of translating logical constraints into MIP constraints. I'm sure that could be implemented in terms of the library though.
  - 8y ago
- plinkplonk 8y ago
  " they said that for those who use Prolog in production it is a real competitive advantage that they don't want to announce to the world;" with due respect to prolog (which is a mindbending language), the proponents of every niche language say the same thing. "it is so powerful that users don't talk about it and that is why you don't hear about it" I've heard many variants of this with respect to Forth, for example. The reality is that devs can't stop talking about the languages, tools, and frameworks they use. The simpler explanation is that next to no one actually uses prolog in productions, because it is, well, a niche language (which doesn't take away from its coolness) Color me skeptical about "secret weapons".
  - yaantc 8y ago
    Few people use it overall, yes. That doesn't mean it's not a differentiator in some areas. You can often find a Prolog system behind complex scheduling and resource planning systems for example. It's no longer pure Prolog nowadays, you also have constraint logic programming and other solvers hooked in (see my other comment on ECLiPSe CLP, http://eclipseclp.org/ http://eclipseclp.org/) but Prolog is still often the host language. The ECLiPSe web page has for example a reference on Opel, the car maker, optimizing its supply chain with it. Sicstus (https://sicstus.sics.se/ https://sicstus.sics.se/) is also present in this space. In a very different domain, IBM publicly commented on how they use Prolog in their Watson system, the one who won Jeopardy (the name was over-used afterward): https://www.cs.nmsu.edu/ALP/2011/03/natural-language-processing-with-prolog-in-the-ibm-watson-system/ https://www.cs.nmsu.edu/ALP/2011/03/natural-language-process...
  - jasim 8y ago
    Forth! "Going Forth to Erlang" by Manoj Govindan is a great talk on the language: https://www.youtube.com/watch?v=RpsZ1Ka2HPQ https://www.youtube.com/watch?v=RpsZ1Ka2HPQ
  - haolez 8y ago
    Paul Graham himself considered Lisp his secret weapon, and it was very successful at that.
    - 8y ago
- yesenadam 8y ago
  I got into Prolog last year, I really love it. I came across the fascinating article "Who Killed Prolog?" (2010), from Maarten van Emden's blog A Programmer's Place. "Compared to these three [Fortran, Lisp, Smalltalk], Prolog has fallen far behind. This was not the case in the early 1980’s, when Prolog had caught up with Lisp in capturing mindshare of what you could call non-IBM computing (to avoid the vexed term “AI”). Hence the title of this article. As culprit (or benefactor, depending on how you look at it) I identify the Japanese “Fifth-Generation Computer System” project, which existed from 1982 to 1992. Even for those who were aware of the project at the time, it is now worth reviewing its fascinating history in the context of its time. This article is such a review as well as a theory of how Prolog was killed and how Lisp was saved from this fate." Richard Grigonis commented in 2014 (incorporated in a Postscript to the article): "The funny thing about this is that, in 1982, as I recall, Fifth-Generation Computer Systems project director, Kazuhiro Fuchi, came to Columbia University in New York, along with Edward Feigenbaum, to give a speech and answer questions of students. Feigenbaum was railing about how the Japanese were going to take over AI and the world, and we should better fund AI researchers in America or we would all be left behind in the dust. It was as if he was using Fuchi as a prop to get more excitement in America for AI. ... When the question-and-answer period came..., I raised my hand and said, “I hate to be the fly in the ointment here, but this whole thing is based on Prolog? A sort of embodiment of the first-order predicate calculus? Even with trimming the search space in various ways, paramodulation, etc, if you use logic as a knowledge representation scheme it always leads to a combinatorial explosion, doesn’t it? Even with parallel processing, if you encode all of the facts of the real world into this thing, you will end up with ‘all day deductions,’ won’t you?” Feigenbaum looked around uncomfortably, swatted the air like he was indeed being pestered by a fly, but then, amazingly (and much to his credit) said — and very quickly at that — “Well, yes, he’s right. BUT Americans need more support because the Japanese are advancing the field!” Feibenbaum quickly moved the session forward. It was the strangest moment. My friend Mike, who had tagged along to watch know-it-all me get verbally obliterated by this erudite group, was stupified, incredulously uttering, with a tone of disbelief in his voice, “Oh my God Richard, you are right!” ...The top American researchers knew the FGCS was completely flawed, but we were humoring them and making a big deal of it so we could get better funding for other, LISP-based projects in the U.S." Van Emden concludes: "A quick way to get an idea of the promise of Prolog is to read “Prolog: The language and its implementation compared with Lisp” by D.H.D. Warren, ACM SIGPLAN Notices, 1977, pages 109-115. Warren shows that in the four years of Prolog implementation development an efficiency in terms of execution speed and memory use was reached that equalled what was reached by a quarter of a century of Lisp implementation development. This is remarkable for a language that in some repects is more high-level than Lisp. The Japanese were smarter than researchers like Feigenbaum in that they took the trouble to discover that Prolog was a different animal from resolution-based automatic theorem provers, where the search space was pruned by the paramodulation technique you mention and by several others. Prolog is also based on resolution logic, but its inference is restricted to mimicking the function definition and the function call mechanism that has been the mainstay of conventional programming since Fortran. As Lisp also relies on this it is not surprising that since 1977 their performances are similar. In applications where Lisp need not search, Prolog does not search either. I don’t want to suggest that Feigenbaum should have switched to Prolog, although I may have told him so during the rare and brief meetings we had in the 1980s. My present opinion is that the difference in the strengths of the two languages does not make one of them overall superior to the other. Other things being equal I might now recommend Lisp because its development has steadily continued since the time when interest in Prolog plummeted with the demise of FGCS. I believe that FGCS was a plausible idea and was similar to the idea behind the Lisp machines of the time. FGCS failed because it failed to come up with a convincing demonstration. Such a demonstration should have come in the form of at least a prototype comparable to a Lisp machine. It could have been clear from the start that a project headed by government bureaucrats and staffed with technical people on loan from big companies had little chance of coming up with a convincing prototype. A Prolog version of a Lisp machine was at least as promising as the Lisp machine itself. I believe that the failure of the Lisp machines was not predictable. Around 1990 everybody was caught off-guard by the rapid drop in price and rise in performance of commodity PCs. There were a few exceptions: Larry Ellison and Linus Thorvalds come to mind. “The Japanese Did It” is not the correct answer to “Who Killed Prolog?”. Prolog was killed by the failure in the early 1980s of mainstream AI researchers to find out about Prolog, by their willingness to play along with the “appropriate responses” to FGCS, and by their use of FGCS’s failure as an excuse for continued neglect of a promising alternative to Lisp." [0] https://vanemden.wordpress.com/2010/08/21/who-killed-prolog/ https://vanemden.wordpress.com/2010/08/21/who-killed-prolog/
- agumonkey 8y ago
  There are other factors: - paradigm is high level, borderline esoteric to the main dev stream - it's not the IT culture, it's expressive and mathematical, not tool nor community oriented people in this area enjoy their own quests and don't create huge fads
  - YeGoblynQueenne 8y ago
    >> - it's not the IT culture, it's expressive and mathematical, not tool nor community oriented Prolog is actually much closer to the computer science mindset than the statistical machine learning algorithms that are so popular right now. The kind of mathematics required to understand it are already in the computer science student's toolbox- discrete, combinatorial maths and logic. The lack of toolkits and frameworks like in javascript, say, is the result of poor adoption, not its cause.
    - agumonkey 8y ago
      I'm not sure I get the ML parallel, but tooling is often a word thrown by average groups as a feature required for a language to thrive or be valuable. For instance python/java etc often want these .. whereas common lisp didn't really. And often it's because the language paradigm/design makes tooling a thing you're not looking after. The few times you need something, you can hack it in on your own and keep your day going. Whereas other languages are heavy and require tooling and people thinks that's the norm and it's even a proof of professionalism to have and master tooling.
      - YeGoblynQueenne 8y ago
        Well, it looks to me like everyone is falling over themselves to learn about machine learning at the moment- I often see posts on HN that ask questions about how one gets started with it without first learning statistics, calculus and linear algebra and so on. I find it strange that there should be so much interest from programmers for a field that is completely alien to their background. It's a bit like if neurologists suddendly started asking "how does one get started on quantum entanglement, without first learning about general relativity and quantum mechanics?". And I find it strange in particular when compared to the lack of any such interest in logic programming, for which programmers, like I say, already have the necessary background. So, my conclusion is, the fact that most programmers are not interested in prolog has nothing to do with how hard or easy it is to learn the language and much more with practical considerations, like what happens to be popular in the industry right now.
- mxcrossb 8y ago
  It’s not like you can’t write backtracking search in other languages. Prolog’s power seems to be in the ease you have expressing new versions these kind of problems, but I’m skeptical that it actually has an advantage for solving large workflows.
- gambler 8y ago
  Prolog is a great idea with one huge flaw that annoys me so much I don't want to use it even for side projects. It complected rule declarations and search algorithm hints. As for your comment about size, Prolog was designed in part to parse things, so it's really good at it. Some other programs in it are trickier and require a certain affinity to Prolog way of thinking. If someone made a Prolog with cleaner syntax that completely segregates rules from hints, I would probably use it a lot.
  - jacinabox 8y ago
    A while back I developed an approach to this in haskell; the idea is to use a logic monad transformer ("Backtracking, Interleaving, and Terminating Monad Transformers" 2005), working at a monad which implements a type class 'Costly' with a single method 'cost'. The implementation of 'cost' can terminate branches of the logic program or transform it in other ways. Then polymorphism over this monad accomplishes the generalization of the logic program over different search strategies.
  - tom_mellior 8y ago
    If you want nonstandard search or other nonstandard semantics for Prolog, you typically write a metainterpreter. See some examples at https://www.metalevel.at/acomip/ https://www.metalevel.at/acomip/ (from the same author as the Lisp interpreter discussed here). It's really easy to implement something like breadth-first search, or depth-first search with iterative deepening, or random search, or some sort of best-first search.
- dkersten 8y ago
  In my (limited) experience, prolog is amazing for a subset of what a useful program might want to do, but it can be really difficult for the remainder, which is why I’m personally a big fan or the miniKanren-based logic libraries for Scheme, or Clojure’s core.logic — you can use logic programming as a library for the subsets of your code where it makes sense and you can use a more traditional language for everything else, seamlessly in the same codebase.
kevsim 8y ago
This brings back fond memories as writing a lisp interpreter in prolog was the final project for my survey of programming languages course in university. Didn’t know people would still be doing it 20 years later.
- KineticLensman 8y ago
  As someone who is implementing a Lisp interpreter (admittedly in C#, not Prolog) I've decided that this sort of project is somewhat analogous to restoring a classic car. It'a a good way to get a handle on earlier times.
lispm 8y ago
a more complex attempt at a Common Lisp in Prolog: https://github.com/TeamSPoon/wam_common_lisp https://github.com/TeamSPoon/wam_common_lisp
ealhad 8y ago
Funny. Chapter 24 of Paul Graham's On Lisp is about implementing Prolog in Common Lisp.
- zerr 8y ago
  It's obligatory for any Lisp book to include a Prolog implementation.
  - vram22 8y ago
    Interesting. Do you know why?
    - lispm 8y ago
      Implementing some kind of Prolog (and also other logic formalism) was common in the AI boom. Some were primitive (for example only using Lisp-like syntax), some were quite extensive (then also providing Edinburgh-Prolog syntax). Most AI tools included some reasoning facility, often in the form of some Prolog. The two commercial Common Lisps (Allegro CL and LispWorks) still offer Prolog implementations. One of the more extensive treatments of implementing Prolog-like features can be found in "Paradigms of Artificial Intelligence Programming" (PAIP) by Peter Norvig. Book and code available here: https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp
      - ken 8y ago
        "Prolog is similar to Lisp on the main points." (ibid)
        triska 8y ago
        In my opinion, this is true for some main points, but definitely not for all of them. A key difference between the languages is in how easily you can reason about programs. In Prolog, if you program in the pure monotonic subset of the language, you get certain algebraic guarantees that are not available in Lisp. For instance, for pure Prolog code and a declarative reading, removing a goal can at most increase the set of solutions, and removing a clause can at most decrease the set of solutions. In Prolog, these guarantees can be used to test and debug your programs by logical reasoning. In fact, to a significant extent, you can even automate debugging due to these properties. Such techniques were pionereed by Ehud Shapiro in his 1982 PhD thesis, Algorithmic Program Debugging: http://cpsc.yale.edu/sites/default/files/files/tr237.pdf http://cpsc.yale.edu/sites/default/files/files/tr237.pdf The thesis is an excellent read, and I highly recommend it! Specifically, quoting from page 155: “Although Lisp is considered a high level language, it is not clear that it encourages precision and clarity of thought. As one Lisp hacker puts it [91]: "Lisp...is like a ball of mud. You can add any amount of mud to it...and it still looks like a ball of mud!". This aspect of Lisp is the hacker's delight, but the theoretician's nightmare. It is known that one may implement without too much effort a reasonable Prolog in Lisp. However, the issue is not implementation — the issue is the method of thought. Based on my experience with both languages I maintain that one's thoughts are better organized, and one's solutions are clearer and more concise, if one thinks in Prolog rather than in Lisp.” Another key feature of Prolog is that constraints blend in seamlessly, leading to an important declarative programming paradigm called constraint logic programming (CLP). This is the key reason why Prolog is frequently used to solve combinatorial tasks in practice, and often an important motivation for buying a commercial Prolog system.
jedimastert 8y ago
This is a weird nit, and I might be wrong, but isn't the "pl" extension usually used with Perl scripts?
- def- 8y ago
  Prolog uses .pl and because of the Perl conflict occasionally .pro: http://www.swi-prolog.org/pldoc/man?section=fileext http://www.swi-prolog.org/pldoc/man?section=fileext I still found a autocmd Filetype pl set syntax=prolog in my vim config from my Prolog days.
- RodgerTheGreat 8y ago
  Now you know how forth programmers feel about F#. (.fs)
- tannhaeuser 8y ago
  Exactly. Perl has insensitively hijacked it.
mark_l_watson 8y ago
This is old code, but it has sparked a great discussion here. In the 1980s I spent months writing a prototype planning system in Common Lisp (which is a primary language for me, and I wrote a CL book for Springer-Verlag back then). Even though I was a Prolog novice, I was able to rewrite my entire prototype in Prolog in one week. Admittedly this was because the second implementation of something is always easier, but also because Prolog was such a good fit to this particular problem. I remember reading The Fifth Generation Computer about Japan’s AI efforts - enjoyed the book but it didn’t really click for me, mostly because I had a Lisp Machine and considered that the `one true path` for AI development at the time.
crimsonalucard 8y ago
This can probably done with CSS. Also assembly language. You can do it with assembly language as well.
MayeulC 8y ago
I suspect that an optimization problem I will have to face in a bit of time might be a good fit for Prolog. What would be the best resources for a quick, relatively high level overview/introduction, then a more involved guide for learning it? This question has been asked elsewhere, but is there a way to pass data back and forth with other languages, and let them control the execution flow? A C interface would seem like a good IR to target. My apologies if I used the wrong terminology, I am not intimate with the more academic nomenclature.
- hjek 8y ago
  Here's a nice and simple one: https://xmonader.github.io/prolog/2018/12/21/solving-murder-prolog.html https://xmonader.github.io/prolog/2018/12/21/solving-murder-...
  - deleted 8y ago
    [deleted]
sp332 8y ago
Some online books... require you to manually translate Prolog programs to Lisp forms that are no longer valid Prolog syntax. I thought Lisp was commonly used to create domain-specific languages with different syntaxes. Wouldn't this be old hat for someone experienced with Lisp? (Asking because I don't have a lot of experience with Lisp.)
- sjatkins 8y ago
  There is a small prolog implementation in the book "On Lisp" done in 200 lines of code or so.
- lispm 8y ago
  Often Prolog implementations in Lisp used a lisp-like syntax. They were not concerned with reading standard Prolog code. Several implementations support(ed) standard Edinburgh-Prolog syntax. For example the LispWorks implementation of Prolog supports both: http://www.lispworks.com/documentation/lw71/KW-W/html/kwprolog-w-135.htm#marker-869240 http://www.lispworks.com/documentation/lw71/KW-W/html/kwprol...
pjmlp 8y ago
Prolog was one of my favourite languages during my degree, to the point that I participated in some logic programming championships. Would like to have some excuses to actually use it on my daily work. As side note, until our compiler design lectures decided to switch the required implementation language to the newly arrived Java, it was possible to choose whatever programming language to implement our assignments. However Lisp and Prolog were off limits as they would make them too easy!
- deleted 8y ago
  [deleted]
FigBug 8y ago
This was a fairly common project when I was in University, except we had to do Scheme in Prolog. https://github.com/FigBug/scheme https://github.com/FigBug/scheme Prolog was a mind bending language. Some things that would be so simple in another language were so hard, and somethings that would be hard, were so easy. I never really got my head around Prolog, just enough to get the assignment finished. But I do remember it as being one of the more interesting assignments I did, interesting enough that I've managed to keep the code for 20+ years.

120 points by martinlaz 8y ago

It seems that it takes far fewer lines of code (and correspondingly simple program model) to implement LISP in Prolog than both imperative and functional languages. Once I asked a Prolog expert at a conference "Prolog is truly mind-bending and powerful, but why don't we see it used more often? where are the jobs so I could get one" and they said that for those who use Prolog in production it is a real competitive advantage that they don't want to announce to the world; plus some are state actors and quasi-state actors who use it for huge scheduling and optimization problems and like their secrets secret. I think I believe that.

petra 8y ago
Every new powerful tool/language probably offers a competitive advantage to some companies. Yet, nothing is really a secret in the world of software development. Why is prolog among the rare few who can keep a secret ?
- JaumeGreen 8y ago
  Because prolog requires a different mindset. When I encountered prolog I tried to understand it, and on the assigment -something about stacking dice having same or different values on the faces, I don't recall it- I managed to write prolog with explicit backtracking. That means that I had several "functions" with different fixed parameters that where the recursion level where they were at, and like a hundred lines of code for this assigment. TA called us in, trying to understant that, we explained and he showed us the "real" solution, in a handful of lines of code. Then it clicked, I understood it. Without that moment I would find prolog too alien, and I guess most people do, that's why it isn't more present in the world. It's too different to "actual programming", that is, it's too different from imperative programming. Even haskell and the like are closer to python and the like than prolog. Heck, even lisp can be closer to them. It's not just learning a new programming language, it's learning a new way to think, not everyone can do that.
  - SolaceQuantum 8y ago
    The most effective way prolog has been taught to me in the form of logic puzzles that we are all familiar with- "We have 6 people who work 1 job each, here a list of possible jobs, there is a list of possible people, the cook is male, the doctor went golfing with the cook on friday, joshua doesn't golf..." After that, you move to programming checking validation of facts and finally to behavior that resembles 'normal' programming. I agree that it's a massively different mindset and the capacity to grasp prolog quickly or be interested in prolog programming should be considered a reflection of the adaptability/curiosity of a person, IMHO.
  - hcarvalhoalves 8y ago
    Prolog tends to "click" once you understand it's a query language for relations, rather than a general programming language (although you can do a lot on top of it you bend it just enough).
0db532a0 8y ago
Do you know of anyone combining prolog with integer linear programming? I modelled quite a complex convex optimisation problem as a mixed integer linear programme, but it was very buggy at the beginning to say the least. I was left wishing that there was a better way to express the logical constraints, which in any case can be converted to integer linear equations, while keeping the linear equations where needed and possible.
- yaantc 8y ago
  ECLiPSe CLP [1] (no relation with the IDE) is a Prolog implementation with constraint logic programming support and interfaces to lots of solvers, including MIP ones [2]. So I guess the answer is yes, although you may not find lots of public use-cases. Eclipse CLP was bought and open sourced by Cisco. [1] http://eclipseclp.org/ http://eclipseclp.org/ [2] From http://eclipseclp.org/features.html http://eclipseclp.org/features.html: "Solver Interfaces. ECLiPSe interfaces to the COIN-OR, CPLEX, Gurobi and XPRESS-MP linear and mixed-integer programming solvers, and the Gecode finite-domain solver. Other interfaces are under development."
  - 0db532a0 8y ago
    Seems to be exactly what I was looking for. Thanks.
- YeGoblynQueenne 8y ago
  Markus Triska, the author of the Lisp interpreter above has also contributed library(simplex), a linear programming library for Swi-Prolog: http://www.swi-prolog.org/pldoc/man?section=simplex http://www.swi-prolog.org/pldoc/man?section=simplex
  - 0db532a0 8y ago
    From first look, this library doesn't seem to provide a way of translating logical constraints into MIP constraints. I'm sure that could be implemented in terms of the library though.
- 8y ago
plinkplonk 8y ago
" they said that for those who use Prolog in production it is a real competitive advantage that they don't want to announce to the world;" with due respect to prolog (which is a mindbending language), the proponents of every niche language say the same thing. "it is so powerful that users don't talk about it and that is why you don't hear about it" I've heard many variants of this with respect to Forth, for example. The reality is that devs can't stop talking about the languages, tools, and frameworks they use. The simpler explanation is that next to no one actually uses prolog in productions, because it is, well, a niche language (which doesn't take away from its coolness) Color me skeptical about "secret weapons".
- yaantc 8y ago
  Few people use it overall, yes. That doesn't mean it's not a differentiator in some areas. You can often find a Prolog system behind complex scheduling and resource planning systems for example. It's no longer pure Prolog nowadays, you also have constraint logic programming and other solvers hooked in (see my other comment on ECLiPSe CLP, http://eclipseclp.org/ http://eclipseclp.org/) but Prolog is still often the host language. The ECLiPSe web page has for example a reference on Opel, the car maker, optimizing its supply chain with it. Sicstus (https://sicstus.sics.se/ https://sicstus.sics.se/) is also present in this space. In a very different domain, IBM publicly commented on how they use Prolog in their Watson system, the one who won Jeopardy (the name was over-used afterward): https://www.cs.nmsu.edu/ALP/2011/03/natural-language-processing-with-prolog-in-the-ibm-watson-system/ https://www.cs.nmsu.edu/ALP/2011/03/natural-language-process...
- jasim 8y ago
  Forth! "Going Forth to Erlang" by Manoj Govindan is a great talk on the language: https://www.youtube.com/watch?v=RpsZ1Ka2HPQ https://www.youtube.com/watch?v=RpsZ1Ka2HPQ
- haolez 8y ago
  Paul Graham himself considered Lisp his secret weapon, and it was very successful at that.
  - 8y ago
yesenadam 8y ago
I got into Prolog last year, I really love it. I came across the fascinating article "Who Killed Prolog?" (2010), from Maarten van Emden's blog A Programmer's Place. "Compared to these three [Fortran, Lisp, Smalltalk], Prolog has fallen far behind. This was not the case in the early 1980’s, when Prolog had caught up with Lisp in capturing mindshare of what you could call non-IBM computing (to avoid the vexed term “AI”). Hence the title of this article. As culprit (or benefactor, depending on how you look at it) I identify the Japanese “Fifth-Generation Computer System” project, which existed from 1982 to 1992. Even for those who were aware of the project at the time, it is now worth reviewing its fascinating history in the context of its time. This article is such a review as well as a theory of how Prolog was killed and how Lisp was saved from this fate." Richard Grigonis commented in 2014 (incorporated in a Postscript to the article): "The funny thing about this is that, in 1982, as I recall, Fifth-Generation Computer Systems project director, Kazuhiro Fuchi, came to Columbia University in New York, along with Edward Feigenbaum, to give a speech and answer questions of students. Feigenbaum was railing about how the Japanese were going to take over AI and the world, and we should better fund AI researchers in America or we would all be left behind in the dust. It was as if he was using Fuchi as a prop to get more excitement in America for AI. ... When the question-and-answer period came..., I raised my hand and said, “I hate to be the fly in the ointment here, but this whole thing is based on Prolog? A sort of embodiment of the first-order predicate calculus? Even with trimming the search space in various ways, paramodulation, etc, if you use logic as a knowledge representation scheme it always leads to a combinatorial explosion, doesn’t it? Even with parallel processing, if you encode all of the facts of the real world into this thing, you will end up with ‘all day deductions,’ won’t you?” Feigenbaum looked around uncomfortably, swatted the air like he was indeed being pestered by a fly, but then, amazingly (and much to his credit) said — and very quickly at that — “Well, yes, he’s right. BUT Americans need more support because the Japanese are advancing the field!” Feibenbaum quickly moved the session forward. It was the strangest moment. My friend Mike, who had tagged along to watch know-it-all me get verbally obliterated by this erudite group, was stupified, incredulously uttering, with a tone of disbelief in his voice, “Oh my God Richard, you are right!” ...The top American researchers knew the FGCS was completely flawed, but we were humoring them and making a big deal of it so we could get better funding for other, LISP-based projects in the U.S." Van Emden concludes: "A quick way to get an idea of the promise of Prolog is to read “Prolog: The language and its implementation compared with Lisp” by D.H.D. Warren, ACM SIGPLAN Notices, 1977, pages 109-115. Warren shows that in the four years of Prolog implementation development an efficiency in terms of execution speed and memory use was reached that equalled what was reached by a quarter of a century of Lisp implementation development. This is remarkable for a language that in some repects is more high-level than Lisp. The Japanese were smarter than researchers like Feigenbaum in that they took the trouble to discover that Prolog was a different animal from resolution-based automatic theorem provers, where the search space was pruned by the paramodulation technique you mention and by several others. Prolog is also based on resolution logic, but its inference is restricted to mimicking the function definition and the function call mechanism that has been the mainstay of conventional programming since Fortran. As Lisp also relies on this it is not surprising that since 1977 their performances are similar. In applications where Lisp need not search, Prolog does not search either. I don’t want to suggest that Feigenbaum should have switched to Prolog, although I may have told him so during the rare and brief meetings we had in the 1980s. My present opinion is that the difference in the strengths of the two languages does not make one of them overall superior to the other. Other things being equal I might now recommend Lisp because its development has steadily continued since the time when interest in Prolog plummeted with the demise of FGCS. I believe that FGCS was a plausible idea and was similar to the idea behind the Lisp machines of the time. FGCS failed because it failed to come up with a convincing demonstration. Such a demonstration should have come in the form of at least a prototype comparable to a Lisp machine. It could have been clear from the start that a project headed by government bureaucrats and staffed with technical people on loan from big companies had little chance of coming up with a convincing prototype. A Prolog version of a Lisp machine was at least as promising as the Lisp machine itself. I believe that the failure of the Lisp machines was not predictable. Around 1990 everybody was caught off-guard by the rapid drop in price and rise in performance of commodity PCs. There were a few exceptions: Larry Ellison and Linus Thorvalds come to mind. “The Japanese Did It” is not the correct answer to “Who Killed Prolog?”. Prolog was killed by the failure in the early 1980s of mainstream AI researchers to find out about Prolog, by their willingness to play along with the “appropriate responses” to FGCS, and by their use of FGCS’s failure as an excuse for continued neglect of a promising alternative to Lisp." [0] https://vanemden.wordpress.com/2010/08/21/who-killed-prolog/ https://vanemden.wordpress.com/2010/08/21/who-killed-prolog/
agumonkey 8y ago
There are other factors: - paradigm is high level, borderline esoteric to the main dev stream - it's not the IT culture, it's expressive and mathematical, not tool nor community oriented people in this area enjoy their own quests and don't create huge fads
- YeGoblynQueenne 8y ago
  >> - it's not the IT culture, it's expressive and mathematical, not tool nor community oriented Prolog is actually much closer to the computer science mindset than the statistical machine learning algorithms that are so popular right now. The kind of mathematics required to understand it are already in the computer science student's toolbox- discrete, combinatorial maths and logic. The lack of toolkits and frameworks like in javascript, say, is the result of poor adoption, not its cause.
  - agumonkey 8y ago
    I'm not sure I get the ML parallel, but tooling is often a word thrown by average groups as a feature required for a language to thrive or be valuable. For instance python/java etc often want these .. whereas common lisp didn't really. And often it's because the language paradigm/design makes tooling a thing you're not looking after. The few times you need something, you can hack it in on your own and keep your day going. Whereas other languages are heavy and require tooling and people thinks that's the norm and it's even a proof of professionalism to have and master tooling.
    - YeGoblynQueenne 8y ago
      Well, it looks to me like everyone is falling over themselves to learn about machine learning at the moment- I often see posts on HN that ask questions about how one gets started with it without first learning statistics, calculus and linear algebra and so on. I find it strange that there should be so much interest from programmers for a field that is completely alien to their background. It's a bit like if neurologists suddendly started asking "how does one get started on quantum entanglement, without first learning about general relativity and quantum mechanics?". And I find it strange in particular when compared to the lack of any such interest in logic programming, for which programmers, like I say, already have the necessary background. So, my conclusion is, the fact that most programmers are not interested in prolog has nothing to do with how hard or easy it is to learn the language and much more with practical considerations, like what happens to be popular in the industry right now.
mxcrossb 8y ago
It’s not like you can’t write backtracking search in other languages. Prolog’s power seems to be in the ease you have expressing new versions these kind of problems, but I’m skeptical that it actually has an advantage for solving large workflows.
gambler 8y ago
Prolog is a great idea with one huge flaw that annoys me so much I don't want to use it even for side projects. It complected rule declarations and search algorithm hints. As for your comment about size, Prolog was designed in part to parse things, so it's really good at it. Some other programs in it are trickier and require a certain affinity to Prolog way of thinking. If someone made a Prolog with cleaner syntax that completely segregates rules from hints, I would probably use it a lot.
- jacinabox 8y ago
  A while back I developed an approach to this in haskell; the idea is to use a logic monad transformer ("Backtracking, Interleaving, and Terminating Monad Transformers" 2005), working at a monad which implements a type class 'Costly' with a single method 'cost'. The implementation of 'cost' can terminate branches of the logic program or transform it in other ways. Then polymorphism over this monad accomplishes the generalization of the logic program over different search strategies.
- tom_mellior 8y ago
  If you want nonstandard search or other nonstandard semantics for Prolog, you typically write a metainterpreter. See some examples at https://www.metalevel.at/acomip/ https://www.metalevel.at/acomip/ (from the same author as the Lisp interpreter discussed here). It's really easy to implement something like breadth-first search, or depth-first search with iterative deepening, or random search, or some sort of best-first search.
dkersten 8y ago
In my (limited) experience, prolog is amazing for a subset of what a useful program might want to do, but it can be really difficult for the remainder, which is why I’m personally a big fan or the miniKanren-based logic libraries for Scheme, or Clojure’s core.logic — you can use logic programming as a library for the subsets of your code where it makes sense and you can use a more traditional language for everything else, seamlessly in the same codebase.

kevsim 8y ago

This brings back fond memories as writing a lisp interpreter in prolog was the final project for my survey of programming languages course in university. Didn’t know people would still be doing it 20 years later.

KineticLensman 8y ago
As someone who is implementing a Lisp interpreter (admittedly in C#, not Prolog) I've decided that this sort of project is somewhat analogous to restoring a classic car. It'a a good way to get a handle on earlier times.

lispm 8y ago

a more complex attempt at a Common Lisp in Prolog: https://github.com/TeamSPoon/wam_common_lisp https://github.com/TeamSPoon/wam_common_lisp

ealhad 8y ago

Funny. Chapter 24 of Paul Graham's On Lisp is about implementing Prolog in Common Lisp.

zerr 8y ago
It's obligatory for any Lisp book to include a Prolog implementation.
- vram22 8y ago
  Interesting. Do you know why?
  - lispm 8y ago
    Implementing some kind of Prolog (and also other logic formalism) was common in the AI boom. Some were primitive (for example only using Lisp-like syntax), some were quite extensive (then also providing Edinburgh-Prolog syntax). Most AI tools included some reasoning facility, often in the form of some Prolog. The two commercial Common Lisps (Allegro CL and LispWorks) still offer Prolog implementations. One of the more extensive treatments of implementing Prolog-like features can be found in "Paradigms of Artificial Intelligence Programming" (PAIP) by Peter Norvig. Book and code available here: https://github.com/norvig/paip-lisp https://github.com/norvig/paip-lisp
    - ken 8y ago
      "Prolog is similar to Lisp on the main points." (ibid)
      - triska 8y ago
        In my opinion, this is true for some main points, but definitely not for all of them. A key difference between the languages is in how easily you can reason about programs. In Prolog, if you program in the pure monotonic subset of the language, you get certain algebraic guarantees that are not available in Lisp. For instance, for pure Prolog code and a declarative reading, removing a goal can at most increase the set of solutions, and removing a clause can at most decrease the set of solutions. In Prolog, these guarantees can be used to test and debug your programs by logical reasoning. In fact, to a significant extent, you can even automate debugging due to these properties. Such techniques were pionereed by Ehud Shapiro in his 1982 PhD thesis, Algorithmic Program Debugging: http://cpsc.yale.edu/sites/default/files/files/tr237.pdf http://cpsc.yale.edu/sites/default/files/files/tr237.pdf The thesis is an excellent read, and I highly recommend it! Specifically, quoting from page 155: “Although Lisp is considered a high level language, it is not clear that it encourages precision and clarity of thought. As one Lisp hacker puts it [91]: "Lisp...is like a ball of mud. You can add any amount of mud to it...and it still looks like a ball of mud!". This aspect of Lisp is the hacker's delight, but the theoretician's nightmare. It is known that one may implement without too much effort a reasonable Prolog in Lisp. However, the issue is not implementation — the issue is the method of thought. Based on my experience with both languages I maintain that one's thoughts are better organized, and one's solutions are clearer and more concise, if one thinks in Prolog rather than in Lisp.” Another key feature of Prolog is that constraints blend in seamlessly, leading to an important declarative programming paradigm called constraint logic programming (CLP). This is the key reason why Prolog is frequently used to solve combinatorial tasks in practice, and often an important motivation for buying a commercial Prolog system.

jedimastert 8y ago

This is a weird nit, and I might be wrong, but isn't the "pl" extension usually used with Perl scripts?

def- 8y ago
Prolog uses .pl and because of the Perl conflict occasionally .pro: http://www.swi-prolog.org/pldoc/man?section=fileext http://www.swi-prolog.org/pldoc/man?section=fileext I still found a autocmd Filetype pl set syntax=prolog in my vim config from my Prolog days.
RodgerTheGreat 8y ago
Now you know how forth programmers feel about F#. (.fs)
tannhaeuser 8y ago
Exactly. Perl has insensitively hijacked it.

mark_l_watson 8y ago

This is old code, but it has sparked a great discussion here. In the 1980s I spent months writing a prototype planning system in Common Lisp (which is a primary language for me, and I wrote a CL book for Springer-Verlag back then). Even though I was a Prolog novice, I was able to rewrite my entire prototype in Prolog in one week. Admittedly this was because the second implementation of something is always easier, but also because Prolog was such a good fit to this particular problem. I remember reading The Fifth Generation Computer about Japan’s AI efforts - enjoyed the book but it didn’t really click for me, mostly because I had a Lisp Machine and considered that the `one true path` for AI development at the time.

crimsonalucard 8y ago

This can probably done with CSS. Also assembly language. You can do it with assembly language as well.

MayeulC 8y ago

I suspect that an optimization problem I will have to face in a bit of time might be a good fit for Prolog. What would be the best resources for a quick, relatively high level overview/introduction, then a more involved guide for learning it? This question has been asked elsewhere, but is there a way to pass data back and forth with other languages, and let them control the execution flow? A C interface would seem like a good IR to target. My apologies if I used the wrong terminology, I am not intimate with the more academic nomenclature.

hjek 8y ago
Here's a nice and simple one: https://xmonader.github.io/prolog/2018/12/21/solving-murder-prolog.html https://xmonader.github.io/prolog/2018/12/21/solving-murder-...
- deleted 8y ago
  [deleted]

sp332 8y ago

Some online books... require you to manually translate Prolog programs to Lisp forms that are no longer valid Prolog syntax. I thought Lisp was commonly used to create domain-specific languages with different syntaxes. Wouldn't this be old hat for someone experienced with Lisp? (Asking because I don't have a lot of experience with Lisp.)

sjatkins 8y ago
There is a small prolog implementation in the book "On Lisp" done in 200 lines of code or so.
lispm 8y ago
Often Prolog implementations in Lisp used a lisp-like syntax. They were not concerned with reading standard Prolog code. Several implementations support(ed) standard Edinburgh-Prolog syntax. For example the LispWorks implementation of Prolog supports both: http://www.lispworks.com/documentation/lw71/KW-W/html/kwprolog-w-135.htm#marker-869240 http://www.lispworks.com/documentation/lw71/KW-W/html/kwprol...

pjmlp 8y ago

Prolog was one of my favourite languages during my degree, to the point that I participated in some logic programming championships. Would like to have some excuses to actually use it on my daily work. As side note, until our compiler design lectures decided to switch the required implementation language to the newly arrived Java, it was possible to choose whatever programming language to implement our assignments. However Lisp and Prolog were off limits as they would make them too easy!

deleted 8y ago
[deleted]

FigBug 8y ago

This was a fairly common project when I was in University, except we had to do Scheme in Prolog. https://github.com/FigBug/scheme https://github.com/FigBug/scheme Prolog was a mind bending language. Some things that would be so simple in another language were so hard, and somethings that would be hard, were so easy. I never really got my head around Prolog, just enough to get the assignment finished. But I do remember it as being one of the more interesting assignments I did, interesting enough that I've managed to keep the code for 20+ years.