3 ms·

> trivially written imperatively or functionally as combinatorial or permutational recursive searches with pruning In other words: an ad hoc, informally-specif

> trivially written imperatively or functionally as combinatorial or permutational recursive searches with pruning In other words: an ad hoc, informally-specified, bug-ridden, slow implementation of half of Prolog. I agree that Prolog would probably fare better as an embedded language like Lua, though - it's best suited to things like rules engines and parsers, rather than whole applications.

barrkel 16y ago
No, you don't need a general-purpose solution for this kind of problem, so you don't need to implement an inference engine - so you wouldn't have an implementation of Prolog. Most of these kinds of problems are only about 100 lines of code even in fairly verbose languages, depending on how complicated the set you need to permute / select from is, and how complicated your clauses are. I speak from experience here, solving packing problems in programming competition questions. Pretty much any high school / college programming competition includes one of these kinds of problems, and the time budget is rarely a lot more than an hour, as it's usually one of the simpler questions.
- fogus 16y ago
  If only reality was based on timed competitions that 15-year-olds win. However, the problem that my colleague was solving was a lot more complicated than stacking a bunch of static boxes in a idealized compartment. In fact, the type of "boxes" and the containment structures were not known at the time of the application development. Instead, he only knew that each could be described along various parameters. For example, there are these things called Foo and they can never be stacked on top of a Bar unless there was a Baz in between, but even then only if the transport was could support that load. These were very complex logistics rules. I suppose you could have written that all in a C loop, but you'd be toast when the new Quuxes were released and new ships were developed, or yada yada yada. As it turns out Prolog worked great. I guess programming an open-ended system would have taken the 15-year-olds an extra 6-7 minutes.
  - barrkel 16y ago
    The more open-ended the clauses are, the more complex it gets, for sure, because you end up embedding a DSL to encode the rules (e.g. expression trees with a simple interpreter); and the more you push up that complexity, the more sense a niche solution like Prolog makes. What a lot of this ends up coming down to is the domain expertises of the code author. If you're uncomfortable with recursion, or writing simple interpreters, then Prolog is a much bigger win. Otherwise, it has a higher hurdle to climb. Interpreters themselves are pretty trivial. Writing a parser and interpreter for a simple expression language (no control flow or anything like that, just a predicate possibly with some arguments) should by itself take no more than an hour. I know from past experience it takes me about 25 minutes, as it's one of the first things I do when I learn a new language.
- silentbicycle 16y ago
  You know what? You're right, certainly moreso than people are giving you credit for. Writing a backtracking, depth-first-search brute-forcer really isn't that hard (especially if you have continuations). It's once you've also added e.g. unification that you're well on the way to reimplementing Prolog. Shame on me for being snarky.

barrkel 16y ago

No, you don't need a general-purpose solution for this kind of problem, so you don't need to implement an inference engine - so you wouldn't have an implementation of Prolog. Most of these kinds of problems are only about 100 lines of code even in fairly verbose languages, depending on how complicated the set you need to permute / select from is, and how complicated your clauses are. I speak from experience here, solving packing problems in programming competition questions. Pretty much any high school / college programming competition includes one of these kinds of problems, and the time budget is rarely a lot more than an hour, as it's usually one of the simpler questions.

fogus 16y ago
If only reality was based on timed competitions that 15-year-olds win. However, the problem that my colleague was solving was a lot more complicated than stacking a bunch of static boxes in a idealized compartment. In fact, the type of "boxes" and the containment structures were not known at the time of the application development. Instead, he only knew that each could be described along various parameters. For example, there are these things called Foo and they can never be stacked on top of a Bar unless there was a Baz in between, but even then only if the transport was could support that load. These were very complex logistics rules. I suppose you could have written that all in a C loop, but you'd be toast when the new Quuxes were released and new ships were developed, or yada yada yada. As it turns out Prolog worked great. I guess programming an open-ended system would have taken the 15-year-olds an extra 6-7 minutes.
- barrkel 16y ago
  The more open-ended the clauses are, the more complex it gets, for sure, because you end up embedding a DSL to encode the rules (e.g. expression trees with a simple interpreter); and the more you push up that complexity, the more sense a niche solution like Prolog makes. What a lot of this ends up coming down to is the domain expertises of the code author. If you're uncomfortable with recursion, or writing simple interpreters, then Prolog is a much bigger win. Otherwise, it has a higher hurdle to climb. Interpreters themselves are pretty trivial. Writing a parser and interpreter for a simple expression language (no control flow or anything like that, just a predicate possibly with some arguments) should by itself take no more than an hour. I know from past experience it takes me about 25 minutes, as it's one of the first things I do when I learn a new language.
silentbicycle 16y ago
You know what? You're right, certainly moreso than people are giving you credit for. Writing a backtracking, depth-first-search brute-forcer really isn't that hard (especially if you have continuations). It's once you've also added e.g. unification that you're well on the way to reimplementing Prolog. Shame on me for being snarky.