5 ms·

For me, I think the problem is that normal, boring, stupid, unsophisticated, plebian imperative programming lives in a world of O(1) operations. That is to say,

by jerf 3y ago

For me, I think the problem is that normal, boring, stupid, unsophisticated, plebian imperative programming lives in a world of O(1) operations. That is to say, a "normal" line of code you type will be O(1), and then you generally start gluing those together with various things that start stacking on O(n) complexities. As things like the accidentally quadratic blog [1], in the normal programming world it is a bit humorous to even so much as accidentally stack two of those things unnecessarily on top of each other. Certainly, people manage to make poorly performing things even so, but at least at the base level, your primitives may be stupid, but they are generally fast. The logic programming world works in a default space of O(n) operations, that stack together more freely than the imperative world, and that gives easy access to O(2^n). Since this is essentially impossible, a great deal of work is done to try to get that down, but you're always intrinsically starting behind the eight-ball. It is easier to work up from O(1) operations than to write an exponential or super-exponential algorithm and then try to trim it back down to a decent complexity for a normal programmer. I think this is the root cause as to why logic programming is generally not something we see a lot of. It's like a wild stallion; it may be powerful but the amount of effort you pour into just keeping it under control may exceed any benefit you could get. It isn't useless, of course. Amazing work has been done in the field of SAT solvers, and there's certainly a niche for it. The problems that are intrinsically higher-order polynomials or (technically) exponential, well, they are what they are and if you're going to be stuck in that world, logic programming may offer you a much better toolset than conventional programming on its own. But there was a hope a long time ago, in the Prolog era, that it could become part of the normal toolkit of general purpose programming, and I don't think that will ever happen, because of this line of logic. This is a bit tangential to the article, it's just what I happened to read that finally crystallized this in my mind. [1]: https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/

PaulHoule 3y ago
I took a comparative programming languages class in 1993 and the prof said that he thought Prolog was the future. It had numerous setbacks. The Japanese thought they could parallelize Prolog programs for their Fifth Generation Computing Project in the 1980s but found out quickly that you couldn't. They made a language called KL1 which was parallelizable, but it wasn't as good as Prolog in other respects. The ability to implement simple parsers in the Prolog using its evaluation process impressed me a lot when I didn't know much about parsers, now that I know how to implement parsers it doesn't impress me much. You can write mixed logical/imperative problems in Prolog but boy is it awkward. When I got interested in RDF circa 2010 I was interested in Datalog (a pure logical language) but found nobody else seemed interested in it and it was hard to find literature on it. That situation has changed a lot as Datalog is a pretty clear way to make database query code composable. Production rules engines (say Drools) are another "old A.I." technology that is largely forgotten even though they are heavily used in banks and a few other corners of the business world. These implement “forward chaining” inference distinct from the “backward chaining” inference implemented in Prolog. Between RETE engines and effective indexing structures it is easy to handle 1000x's more rules in your knowledge base in the 1980s but production rules never got standardized like C, FORTRAN or COBOL and no really general answers have come up for questions like controlling the order of execution when that matters.
- jerf 3y ago
  "The Japanese thought they could parallelize Prolog programs for their Fifth Generation Computing Project in the 1980s but found out quickly that you couldn't." One of the lessons I'm still trying to absorb is how convinced we all were (and many still are) that there must be a ton of implicit parallelism in the world, but once we went looking for it, it turned out there was hardly any. I've been chewing on this for years, trying to figure out whether this is something true about the world, true about the problems we try to solve, or because of the pervasive use of the imperative paradigm which is highly ordered and makes it very easy to impose ordering constraints. Now, clearly, the latter is a non-trivial component... but I still struggle with whether it is a full answer, because when people sat down with clean sheets of paper and tried to solve problems with extensive parallelism, they've largely failed to get more than low single-digit speedup factors. Non-imperative paradigms like logic programming have been tried, especially in these projects. It isn't exactly news that our intuitive beliefs about our code and the real characteristics it has is quite out of whack. This underlies the pervasive advice to just go grab a profiler whenever you're trying to accelerate some code because even experts in the field with decades of experience are routinely completely wrong about what is slow in some bit of code. This is one particular aspect I'm still struggling with. It still feels like there should be so much more parallelism available....
  - PaulHoule 3y ago
    Part of the "low code" puzzle is that part of the job of the professional programmer is to determine what sequence events need to happen in time. There are some cases (make and the Spring Framework) where the user specifies the dependencies between things and the framework does a topological sort to figure out what order to do them in. Even though this could be a basis for a whole paradigm of programming, professional programmers usually don't find it hard to figure out how to order things so there is little motivation to address this problem systematically. However, I think it is on the list of problems that non-professional programmers (say the subject matter expert who wants to learn Python to put their skills on wheels) get hung up. Instead it's seen as a special case that makes high-complexity systems scalable (... Spring lets you describe the parts of a system and how they are related without writing structurally unstable initialization code.)
bmitc 3y ago
In my experience, performance concerns have rarely been priority or the primary blocking issue with software development. With Prolog, you can often write entire programs in just a few lines that would require hundreds of lines in another language, which would likely contain the same performance pitfalls of the Prolog code.
- Karrot_Kream 3y ago
  This hasn't been my experience at all. I personally am great at thinking in logic programming. I often prototype algorithms or services in Prolog (for myself, not for wider circulation) because it matches how I think very well. I've had little trouble using cuts and other techniques to guide the search. But my experience working with others is that a lot of people find the Prolog search algorithm to be inscrutable and very non-intuitive. Sure one could make the argument as some FP advocates do that had we all started learning using logic programming ideas from the start that this would be the default, but in practice I find that most people struggle to structure their program in a way amenable to Prolog-style backtracking search. Working on open source projects with other Prolog enthusiasts is a bit different because that crowd self-selects for being good with Prolog.
manasij7479 3y ago
The issue you have circled around here is a bit deeper and nuanced than trimming down exponential code to something more tractable. In fact, it's often worse, and O(2^n) can be a blessing! The problem with logic programming is the 'logic' part. Modern imperative and functional programming languages are constructive. Logic programming is not, and the expressive power varies with the exact logic being used. Elementary logic gives you the following intuition. Propositional logic -- easy. First order logic -- easy (with caveats). And (some kinds of) second order logic -- only easy if you get lucky with the problem you are trying to solve. For logic based programming languages and systems, both the language implementer and the programmer have to be careful about supporting and using language constructs which boil down to tractable computation. This is much more difficult than it seems like. For example, when using SMT solvers you learn quickly that multiplication and division with constants is very fast while the same operations with variables can be intractable. i.e. reasoning about x * C --easy, while x * y is often (but not always..) going to hang.
- slaymaker1907 3y ago
  Of the logic programming languages, Prolog is actually pretty friendly when it comes to construction. You can easily force evaluation with an empty left clause, i.e. ":- thing1(x), thing2(y).", and Prolog gives you a lot of tools to control the current database with assert/retract (handy for memoization). Minikanren (which core.logic is based on) is much more restrictive and really wants things to be pure, though it does have the advantage of working as a library in an imperative language as a small runtime.
  - manasij7479 3y ago
    Neat, I wonder if this idea could be developed into a more refined programming experience where you you spend time in the imperative world by default and only express some iterations as logic puzzles to be solved like this.
    - BeautifulSynch 3y ago
      I've actually seen this usage pattern in the practical usage of logic programming libraries. Common Lisp's Screamer [1], for instance, or Clojure's less-mature core.logic [2]. Though to be fair, both of these libraries are in Lisp languages, which inherently support the design pattern of slipping into/out-of DSLs. [1] http://nikodemus.github.io/screamer/ http://nikodemus.github.io/screamer/ [2] https://github.com/clojure/core.logic https://github.com/clojure/core.logic
giraffe_lady 3y ago
This seems right but I think embedded logic programming in the standard lib is way closer to the right solution than expecting to tackle the appropriate tasks with a separate language. Many programs have a sub-problem that is a good fit for logic programming, but it's rare that it be so well encapsulated it's worth deploying an entire separate language for it. Having these tools close at hand the same way we have regex and (more recently) PEGs for grammars definitely makes it more likely that people will reach for them when appropriate, and exposure and familiarity to the practices can grow. I suspect part of the problem is just that minikanren is primarily a learning tool and doesn't prioritize practical ergonomics. I haven't used core.logic but I've used minikanren in this embedded way and it's difficult to do cleanly in ways that have nothing to do with logic programming per se. I may be off but I think it's something that having a high quality professional strength implementation in the stdlib could actually help with.
opportune 3y ago
Prolog comes from the era (the 70s) where computationally interesting and algorithmically complex problems were a proportionately much larger part of the computing scene than they are today, what with our personal computers, data crunching, and web applications. It’s not really that those kinds of computing paradigms are bad so much as they aren’t nearly as relevant as they were. And a typical programmer, even if they do encounter a problem appropriate for that kind of approach, is much better off using the typical software they have tons of experience with, rather than attempting to learn a new paradigm and uncovering all its pitfalls in the process of learning it. Exhaustively searching an exponential space with no heuristics for reducing the search space is obviously gonna be way easier in a familiar language than in a new language. The one use case I do see for prolog and similar tools in the modern day is for Constraint Satisfaction programming. Obviously, exhaustively searching an exponential solution space won’t be better for that, but typically you can use concepts like Edge and Arc consistency (which are core to CSP solvers) to greatly reduce the actual search space. Implementing those algorithms from scratch in an imperative language is annoyingly hard, so reaching for optimized, generalized implementations can be a good choice. For something like a Sudoku solver, edge/arc consistency can greatly improve compute times. If you’re good at sudoku, you are already implementing these techniques when solving puzzles, just like good chess players implement minimax search without having to be told what minimax search is. https://www.sciencedirect.com/topics/computer-science/arc-consistency https://www.sciencedirect.com/topics/computer-science/arc-co...
coldtea 3y ago
>That is to say, a "normal" line of code you type will be O(1) Huh? This isn't remotely true especially today, and for the type of programming most do, where people work with functions and classes from libraries, with each line doing all kinds of O(?) stuff under the hood, and applying those to collections of objects, and so on.

by jerf 3y ago

PaulHoule 3y ago

I took a comparative programming languages class in 1993 and the prof said that he thought Prolog was the future. It had numerous setbacks. The Japanese thought they could parallelize Prolog programs for their Fifth Generation Computing Project in the 1980s but found out quickly that you couldn't. They made a language called KL1 which was parallelizable, but it wasn't as good as Prolog in other respects. The ability to implement simple parsers in the Prolog using its evaluation process impressed me a lot when I didn't know much about parsers, now that I know how to implement parsers it doesn't impress me much. You can write mixed logical/imperative problems in Prolog but boy is it awkward. When I got interested in RDF circa 2010 I was interested in Datalog (a pure logical language) but found nobody else seemed interested in it and it was hard to find literature on it. That situation has changed a lot as Datalog is a pretty clear way to make database query code composable. Production rules engines (say Drools) are another "old A.I." technology that is largely forgotten even though they are heavily used in banks and a few other corners of the business world. These implement “forward chaining” inference distinct from the “backward chaining” inference implemented in Prolog. Between RETE engines and effective indexing structures it is easy to handle 1000x's more rules in your knowledge base in the 1980s but production rules never got standardized like C, FORTRAN or COBOL and no really general answers have come up for questions like controlling the order of execution when that matters.

jerf 3y ago
"The Japanese thought they could parallelize Prolog programs for their Fifth Generation Computing Project in the 1980s but found out quickly that you couldn't." One of the lessons I'm still trying to absorb is how convinced we all were (and many still are) that there must be a ton of implicit parallelism in the world, but once we went looking for it, it turned out there was hardly any. I've been chewing on this for years, trying to figure out whether this is something true about the world, true about the problems we try to solve, or because of the pervasive use of the imperative paradigm which is highly ordered and makes it very easy to impose ordering constraints. Now, clearly, the latter is a non-trivial component... but I still struggle with whether it is a full answer, because when people sat down with clean sheets of paper and tried to solve problems with extensive parallelism, they've largely failed to get more than low single-digit speedup factors. Non-imperative paradigms like logic programming have been tried, especially in these projects. It isn't exactly news that our intuitive beliefs about our code and the real characteristics it has is quite out of whack. This underlies the pervasive advice to just go grab a profiler whenever you're trying to accelerate some code because even experts in the field with decades of experience are routinely completely wrong about what is slow in some bit of code. This is one particular aspect I'm still struggling with. It still feels like there should be so much more parallelism available....
- PaulHoule 3y ago
  Part of the "low code" puzzle is that part of the job of the professional programmer is to determine what sequence events need to happen in time. There are some cases (make and the Spring Framework) where the user specifies the dependencies between things and the framework does a topological sort to figure out what order to do them in. Even though this could be a basis for a whole paradigm of programming, professional programmers usually don't find it hard to figure out how to order things so there is little motivation to address this problem systematically. However, I think it is on the list of problems that non-professional programmers (say the subject matter expert who wants to learn Python to put their skills on wheels) get hung up. Instead it's seen as a special case that makes high-complexity systems scalable (... Spring lets you describe the parts of a system and how they are related without writing structurally unstable initialization code.)

bmitc 3y ago

In my experience, performance concerns have rarely been priority or the primary blocking issue with software development. With Prolog, you can often write entire programs in just a few lines that would require hundreds of lines in another language, which would likely contain the same performance pitfalls of the Prolog code.

Karrot_Kream 3y ago
This hasn't been my experience at all. I personally am great at thinking in logic programming. I often prototype algorithms or services in Prolog (for myself, not for wider circulation) because it matches how I think very well. I've had little trouble using cuts and other techniques to guide the search. But my experience working with others is that a lot of people find the Prolog search algorithm to be inscrutable and very non-intuitive. Sure one could make the argument as some FP advocates do that had we all started learning using logic programming ideas from the start that this would be the default, but in practice I find that most people struggle to structure their program in a way amenable to Prolog-style backtracking search. Working on open source projects with other Prolog enthusiasts is a bit different because that crowd self-selects for being good with Prolog.

manasij7479 3y ago

The issue you have circled around here is a bit deeper and nuanced than trimming down exponential code to something more tractable. In fact, it's often worse, and O(2^n) can be a blessing! The problem with logic programming is the 'logic' part. Modern imperative and functional programming languages are constructive. Logic programming is not, and the expressive power varies with the exact logic being used. Elementary logic gives you the following intuition. Propositional logic -- easy. First order logic -- easy (with caveats). And (some kinds of) second order logic -- only easy if you get lucky with the problem you are trying to solve. For logic based programming languages and systems, both the language implementer and the programmer have to be careful about supporting and using language constructs which boil down to tractable computation. This is much more difficult than it seems like. For example, when using SMT solvers you learn quickly that multiplication and division with constants is very fast while the same operations with variables can be intractable. i.e. reasoning about x * C --easy, while x * y is often (but not always..) going to hang.

slaymaker1907 3y ago
Of the logic programming languages, Prolog is actually pretty friendly when it comes to construction. You can easily force evaluation with an empty left clause, i.e. ":- thing1(x), thing2(y).", and Prolog gives you a lot of tools to control the current database with assert/retract (handy for memoization). Minikanren (which core.logic is based on) is much more restrictive and really wants things to be pure, though it does have the advantage of working as a library in an imperative language as a small runtime.
- manasij7479 3y ago
  Neat, I wonder if this idea could be developed into a more refined programming experience where you you spend time in the imperative world by default and only express some iterations as logic puzzles to be solved like this.
  - BeautifulSynch 3y ago
    I've actually seen this usage pattern in the practical usage of logic programming libraries. Common Lisp's Screamer [1], for instance, or Clojure's less-mature core.logic [2]. Though to be fair, both of these libraries are in Lisp languages, which inherently support the design pattern of slipping into/out-of DSLs. [1] http://nikodemus.github.io/screamer/ http://nikodemus.github.io/screamer/ [2] https://github.com/clojure/core.logic https://github.com/clojure/core.logic

giraffe_lady 3y ago

This seems right but I think embedded logic programming in the standard lib is way closer to the right solution than expecting to tackle the appropriate tasks with a separate language. Many programs have a sub-problem that is a good fit for logic programming, but it's rare that it be so well encapsulated it's worth deploying an entire separate language for it. Having these tools close at hand the same way we have regex and (more recently) PEGs for grammars definitely makes it more likely that people will reach for them when appropriate, and exposure and familiarity to the practices can grow. I suspect part of the problem is just that minikanren is primarily a learning tool and doesn't prioritize practical ergonomics. I haven't used core.logic but I've used minikanren in this embedded way and it's difficult to do cleanly in ways that have nothing to do with logic programming per se. I may be off but I think it's something that having a high quality professional strength implementation in the stdlib could actually help with.

opportune 3y ago

Prolog comes from the era (the 70s) where computationally interesting and algorithmically complex problems were a proportionately much larger part of the computing scene than they are today, what with our personal computers, data crunching, and web applications. It’s not really that those kinds of computing paradigms are bad so much as they aren’t nearly as relevant as they were. And a typical programmer, even if they do encounter a problem appropriate for that kind of approach, is much better off using the typical software they have tons of experience with, rather than attempting to learn a new paradigm and uncovering all its pitfalls in the process of learning it. Exhaustively searching an exponential space with no heuristics for reducing the search space is obviously gonna be way easier in a familiar language than in a new language. The one use case I do see for prolog and similar tools in the modern day is for Constraint Satisfaction programming. Obviously, exhaustively searching an exponential solution space won’t be better for that, but typically you can use concepts like Edge and Arc consistency (which are core to CSP solvers) to greatly reduce the actual search space. Implementing those algorithms from scratch in an imperative language is annoyingly hard, so reaching for optimized, generalized implementations can be a good choice. For something like a Sudoku solver, edge/arc consistency can greatly improve compute times. If you’re good at sudoku, you are already implementing these techniques when solving puzzles, just like good chess players implement minimax search without having to be told what minimax search is. https://www.sciencedirect.com/topics/computer-science/arc-consistency https://www.sciencedirect.com/topics/computer-science/arc-co...

coldtea 3y ago

>That is to say, a "normal" line of code you type will be O(1) Huh? This isn't remotely true especially today, and for the type of programming most do, where people work with functions and classes from libraries, with each line doing all kinds of O(?) stuff under the hood, and applying those to collections of objects, and so on.