6 ms·

Let's assume I'm a hipster and I wanted an excuse to embed a logic programming DSL in my application. What is a valid excuse / usecase? Does anyone here have an

Let's assume I'm a hipster and I wanted an excuse to embed a logic programming DSL in my application. What is a valid excuse / usecase? Does anyone here have any real-world success stories from something like this? Logic programming always appealed to me, but I always felt like I never understood what to actually do with it other than write toy programs about parent-child relationships (I tried learning Prolog a few times, but stopped for this reason).

giraffe_lady 4y ago
Yeah I've had the same questions for a while. What specific concrete problem can you solve with this, that does not have as-good solutions available in any language powerful enough to easily implement it? I am kind of half-considering it for mud scripting? Each line from the mud represents a fact or relation so this could be used to query for specific information as needed. For this case though, it doesn't really seem better than writing a regex-based DSL though, something I'm far more familiar with and that is better supported.
- ModernMech 4y ago
  Logic languages are great for expressing database queries, so you can treat your program like a database. And if your program is a database you can do database-y things on it like using transactions to "rewind" the program state. Or in the context of distributed programming, well... distributed databases are a thing, and we know how to handle updates to databases in that context, so writing your distributed logic program is as easy as forming a series of database queries, and you can let the DBMS do the magic of distributing it. I guess I think of logic languages as SQL but I actually want to write my whole program in it.
- rscho 4y ago
  Constraint programming. Everyone will tell you that C++ and Java solvers are so much faster. That's true, but prolog for example is incredibly easy to use in comparison, and in fact not that slow. So if you're prototyping or aiming for something exotic that doesn't easily fit into existing libs, LP will be miles ahead. Generally speaking, you'll see the same pattern for any problem involving searching a space of potential solutions. In a word, the strength of LP is flexibility when facing the unkown (future feature requirement). EDIT: you mention parsing. If you're planning anything context-sensitive, you have to check out eDCGs. You probably won't use them, but they'll give you an idea of what's possible.
  - giraffe_lady 4y ago
    Ahhhh this is extremely helpful, thank you. I've been puzzling at the mud parsing thing because while it's in the shape of natural language (and somewhat annotated in it eg there is spurious "decorative" information), it does represent a 1:1 mapping with computation already. This feels like a much better path than trying to get it into an AST with like yacc or whatever. But since it isn't actually natural language NLP didn't seem right either. I've got a lot of reading to do but this is very interesting.
    - YeGoblynQueenne 4y ago
      I started a comment about DCGs also before seeing rscho's and mncharity's comments above which covered it. If you're going to do any parsing, I don't think there's any better tool than DCGs. It blows my mind that everyone is still trying to kludge their way around regexes instead, when there is such a better tool around. Your mud language is probably a "Controlled Natural Language", btw: https://en.wikipedia.org/wiki/Controlled_natural_language https://en.wikipedia.org/wiki/Controlled_natural_language Game languages often are.
  - mncharity 4y ago
    > you have to check out eDCGs. https://github.com/kamahen/edcg https://github.com/kamahen/edcg , https://occasionallycogent.com/prolog_edcgs/index.html https://occasionallycogent.com/prolog_edcgs/index.html
  - mncharity 4y ago
    > You probably won't use them, Curious - I fuzzily recall usually ending up manually threading state (eg, doing a Perl-Compatible Regular Expression engine (apropos "why LP?" - it was just a page of code, with good performance)), but I don't recall what drove that decision...
- deleted 4y ago
  [deleted]
qsort 4y ago
You have to find a valid assignment of resources according to some business rules that are unstable/partially unknown/very likely to change. You have to solve some kind of 3-SAT-reducible problem that would be difficult to implement otherwise. You have to do some heavy pattern-matching. Closely related: https://en.wikipedia.org/wiki/Answer_set_programming https://en.wikipedia.org/wiki/Answer_set_programming
rscho 4y ago
You want pure I/O in an untyped language. DCGs are the easiest way to have that (although they also have their limits).
- nerdponx 4y ago
  What do you mean by "pure I/O" in this case? And how does logic programming help with that? I've seen things like this in the context of "algebraic effects", where instead of performing I/O (and instead of using monadic I/O) you build up what amounts to an execution graph of effectful operations, which is then "interpreted" at runtime. Is that what you're describing?
  - rscho 4y ago
    No, what I'm describing is the "monadic" behaviour of `phrase_from_file/2` and similar predicates. In conjunction with definite clause grammars, this means that your I/O operations either conform to the provided spec or fail. This is a "hot topic" (if LP topics can really still be "hot") and sees active development in new prolog systems. Check this out for prolog: https://youtu.be/Dqpxy4W7fAo https://youtu.be/Dqpxy4W7fAo https://www.swi-prolog.org/pldoc/man?section=pio https://www.swi-prolog.org/pldoc/man?section=pio https://github.com/mthom/scryer-prolog/blob/084fc845902f7b435b0e5e44aaeba023bc28958f/src/lib/pio.pl https://github.com/mthom/scryer-prolog/blob/084fc845902f7b43... "New" stuff in the MiniKanren world: https://staff.fnwi.uva.nl/c.u.grelck/nl-fp-talks/kourzanov.pdf https://staff.fnwi.uva.nl/c.u.grelck/nl-fp-talks/kourzanov.p... https://ifl2014.github.io/submissions/ifl2014_submission_18.pdf https://ifl2014.github.io/submissions/ifl2014_submission_18....
    - YeGoblynQueenne 4y ago
      (Not the OP) Thanks for the links, because 14 years after I first started coding in Prolog I'm still not sure what Pure I/O is or why it is. I mean, my intuition is that a file is a stream of bytes and wading through that stream is not going to be "pure" no matter what, just because a byte is not a concept in First Order Logic. But, OK, "pure" Prolog is not the same as FOL anyway, and so I may be convinced otherwise when I have the chance to peruse your links. So thanks again and sorry for any negative vibes emanating from my comment.
deleted 4y ago
[deleted]
lukev 4y ago
One thing I'd love to see logic programming used for is in an infrastructure-as-code platform to provision cloud resources. I don't want to have to define security groups, subnets, route tables, etc. Instead, I want to declaratively say "Service A must communicate with Service B", and based on the properties of those services, all the correct cloud resources will be defined. Subject, of course, to constraints around security, etc. We are tantalizingly close to this with current IaC tools (CDK, Pulumi, etc) but at the end of the day you still need to define each granular cloud resource (even if the code to do so can be tucked away in a library abstraction.) I'm busy with my current gig now, but if you forced me to launch a startup at gunpoint, this would definitely be it.
evnc 4y ago
I'm casually exploring using logic programming to define rules for games, as an embedded scripting language in a game engine, which would handle input and rendering etc. and be written in a more "conventional" language. We'll see if performance is an issue, but the space I'm most interested in is turn based strategy / board games, where it doesn't seem to be a big deal if things are as fast as possible. It feels like a pretty natural fit, e.g.: can_move_to(unit_id, tile) :- Unit(unit_id), Tile(tile), reachable_to(unit_id, tile, move_cost), unit_move_points_remaining(unit_id, mv), move_cost <= mv. You can define a lot of rules from basic unit movement to "what happens when you activate Super Special Rule-Bending Ability" this way, and it's pretty easy to change the definitions if you want to experiment with different game rules / logic. In practice, you want various syntactic sugar. Haven't got a chance to take this very far yet, just casual experimentation, but it seems like there's potential.
- YeGoblynQueenne 4y ago
  Oh yeah, encoding game rules is a killer app for Prolog's declarative style. See my sibling comment- I've done this with M:tG and WH40k. With M:tG in particular, translating from the rulebook to Prolog, to code a rules engine, is a breeze, just because the M:tG rules are in such strict, formal language already. The jump from a well-written, unambiguous and precise set of board game rules and its translation in Prolog is a tiny step, that could even be automated with some elbow grease. Now, you mention "rendering" and that, on the other hand, I'm not sure is a very good application for Prolog. Nothing to do with speed, but arithmetic in Prolog is a bit meh, and if you want to do stuff like matrix arithmetic, you have to roll your own. Most Prologs don't even have arrays, as such (they kind of do but it's a bit of a hack).
- convolvatron 4y ago
  top-down datalog can almost certainly be compiled to something quite reasonable. you also might enjoy looking at incremental datalog (differentiating rules and operating on events). this generally does a really good job of touching just what need to update the global state. this is a great application
YeGoblynQueenne 4y ago
Here's some stuff I've written in Prolog, some for my own enjoyment, one for my degree project. Most of the benefits I found come down to two things: a) Prolog, like the various kanrens, is a relational language so a program is effectively a database. There's no need to do anything special to glue together a data layer and a logic layer, because you have both written in Prolog. No object-relational impedance mismatch whatsoever. b) Prolog's declarative style makes translating rules and directives into code a breeze. The three projects below are all games and benefit heavily from this feature. The same would go for business logic of any shape or form. 1. Warhammer 40K simulation: https://github.com/stassa/wh40ksim https://github.com/stassa/wh40ksim Runs simulations of combat between WH40k units. 2. Gleemin, a Magic: the Gathering expert system: https://github.com/stassa/Gleemin https://github.com/stassa/Gleemin Doesn't work anymore! Because backwards compatibility. Includes a) a parser for the rules text on M:tG cards written in Prolog's Definite Clause Grammars notation, b) a rules engine and c) a (primitive) AI player. The parser translates rules text from cards into rules engine calls. The cards themselves are Prolog predicates. Your data and your program are one and now you can also do stuff with them. 3. Nests & Insects, a roguelike TTRPG: https://github.com/stassa/nests-and-insects https://github.com/stassa/nests-and-insects WIP! Here I use Prolog to keep the data about my tabletop rpg organised, and also to automatically fill-in the character sheets typeset in the rulebook. The Prolog code runs a character creation process and generates completed character sheets. I plan to do the same for enemies' stat blocks, various procedural generation tables, etc. I also use Prolog to typeset the ASCII-styled rulebook, but that's actually not a good application of Prolog (too imperative). You asked about "logic programming" in general and not miniKanren in particular. I haven't actually used miniKanren, so I commented about the logic programming language I've used the most, Prolog. I hope that's not a thread hijack! All three of the projects above are basically games. I have more "serious" stuff on my github but I am currently experiencing a certain shortfall of gravitas.
- nerdponx 4y ago
  Thanks for the examples! I will have to review these.
sterlind 4y ago
I attempted to use Microkanren for type deduction in a transpiler I had to build at work. I wasn't actually trying to be a hipster, I just had to compile a dynamic language into the strictest possible static types. I'd reinvented unification, remembered Kanren which is built on that, so I reached for it. It didn't work out in my case. I found it really fiddly to work with, and the implementation I was loosely working from was very idiomatic Lisp.
protomyth 4y ago
For normal enterprise programming, they are fairly good for writing rules that normal business folks can eventually figure out. Every business has jargon to describe their business.
rad_gruchalski 4y ago
RBAC. Google Zanzibar comes to mind.
lukashrb 4y ago
If I recall correctly: cisco threat grid is using core.logic

giraffe_lady 4y ago

Yeah I've had the same questions for a while. What specific concrete problem can you solve with this, that does not have as-good solutions available in any language powerful enough to easily implement it? I am kind of half-considering it for mud scripting? Each line from the mud represents a fact or relation so this could be used to query for specific information as needed. For this case though, it doesn't really seem better than writing a regex-based DSL though, something I'm far more familiar with and that is better supported.

ModernMech 4y ago
Logic languages are great for expressing database queries, so you can treat your program like a database. And if your program is a database you can do database-y things on it like using transactions to "rewind" the program state. Or in the context of distributed programming, well... distributed databases are a thing, and we know how to handle updates to databases in that context, so writing your distributed logic program is as easy as forming a series of database queries, and you can let the DBMS do the magic of distributing it. I guess I think of logic languages as SQL but I actually want to write my whole program in it.
rscho 4y ago
Constraint programming. Everyone will tell you that C++ and Java solvers are so much faster. That's true, but prolog for example is incredibly easy to use in comparison, and in fact not that slow. So if you're prototyping or aiming for something exotic that doesn't easily fit into existing libs, LP will be miles ahead. Generally speaking, you'll see the same pattern for any problem involving searching a space of potential solutions. In a word, the strength of LP is flexibility when facing the unkown (future feature requirement). EDIT: you mention parsing. If you're planning anything context-sensitive, you have to check out eDCGs. You probably won't use them, but they'll give you an idea of what's possible.
- giraffe_lady 4y ago
  Ahhhh this is extremely helpful, thank you. I've been puzzling at the mud parsing thing because while it's in the shape of natural language (and somewhat annotated in it eg there is spurious "decorative" information), it does represent a 1:1 mapping with computation already. This feels like a much better path than trying to get it into an AST with like yacc or whatever. But since it isn't actually natural language NLP didn't seem right either. I've got a lot of reading to do but this is very interesting.
  - YeGoblynQueenne 4y ago
    I started a comment about DCGs also before seeing rscho's and mncharity's comments above which covered it. If you're going to do any parsing, I don't think there's any better tool than DCGs. It blows my mind that everyone is still trying to kludge their way around regexes instead, when there is such a better tool around. Your mud language is probably a "Controlled Natural Language", btw: https://en.wikipedia.org/wiki/Controlled_natural_language https://en.wikipedia.org/wiki/Controlled_natural_language Game languages often are.
- mncharity 4y ago
  > you have to check out eDCGs. https://github.com/kamahen/edcg https://github.com/kamahen/edcg , https://occasionallycogent.com/prolog_edcgs/index.html https://occasionallycogent.com/prolog_edcgs/index.html
- mncharity 4y ago
  > You probably won't use them, Curious - I fuzzily recall usually ending up manually threading state (eg, doing a Perl-Compatible Regular Expression engine (apropos "why LP?" - it was just a page of code, with good performance)), but I don't recall what drove that decision...
deleted 4y ago
[deleted]

qsort 4y ago

You have to find a valid assignment of resources according to some business rules that are unstable/partially unknown/very likely to change. You have to solve some kind of 3-SAT-reducible problem that would be difficult to implement otherwise. You have to do some heavy pattern-matching. Closely related: https://en.wikipedia.org/wiki/Answer_set_programming https://en.wikipedia.org/wiki/Answer_set_programming

rscho 4y ago

You want pure I/O in an untyped language. DCGs are the easiest way to have that (although they also have their limits).

nerdponx 4y ago
What do you mean by "pure I/O" in this case? And how does logic programming help with that? I've seen things like this in the context of "algebraic effects", where instead of performing I/O (and instead of using monadic I/O) you build up what amounts to an execution graph of effectful operations, which is then "interpreted" at runtime. Is that what you're describing?
- rscho 4y ago
  No, what I'm describing is the "monadic" behaviour of `phrase_from_file/2` and similar predicates. In conjunction with definite clause grammars, this means that your I/O operations either conform to the provided spec or fail. This is a "hot topic" (if LP topics can really still be "hot") and sees active development in new prolog systems. Check this out for prolog: https://youtu.be/Dqpxy4W7fAo https://youtu.be/Dqpxy4W7fAo https://www.swi-prolog.org/pldoc/man?section=pio https://www.swi-prolog.org/pldoc/man?section=pio https://github.com/mthom/scryer-prolog/blob/084fc845902f7b435b0e5e44aaeba023bc28958f/src/lib/pio.pl https://github.com/mthom/scryer-prolog/blob/084fc845902f7b43... "New" stuff in the MiniKanren world: https://staff.fnwi.uva.nl/c.u.grelck/nl-fp-talks/kourzanov.pdf https://staff.fnwi.uva.nl/c.u.grelck/nl-fp-talks/kourzanov.p... https://ifl2014.github.io/submissions/ifl2014_submission_18.pdf https://ifl2014.github.io/submissions/ifl2014_submission_18....
  - YeGoblynQueenne 4y ago
    (Not the OP) Thanks for the links, because 14 years after I first started coding in Prolog I'm still not sure what Pure I/O is or why it is. I mean, my intuition is that a file is a stream of bytes and wading through that stream is not going to be "pure" no matter what, just because a byte is not a concept in First Order Logic. But, OK, "pure" Prolog is not the same as FOL anyway, and so I may be convinced otherwise when I have the chance to peruse your links. So thanks again and sorry for any negative vibes emanating from my comment.

deleted 4y ago

[deleted]

lukev 4y ago

One thing I'd love to see logic programming used for is in an infrastructure-as-code platform to provision cloud resources. I don't want to have to define security groups, subnets, route tables, etc. Instead, I want to declaratively say "Service A must communicate with Service B", and based on the properties of those services, all the correct cloud resources will be defined. Subject, of course, to constraints around security, etc. We are tantalizingly close to this with current IaC tools (CDK, Pulumi, etc) but at the end of the day you still need to define each granular cloud resource (even if the code to do so can be tucked away in a library abstraction.) I'm busy with my current gig now, but if you forced me to launch a startup at gunpoint, this would definitely be it.

evnc 4y ago

I'm casually exploring using logic programming to define rules for games, as an embedded scripting language in a game engine, which would handle input and rendering etc. and be written in a more "conventional" language. We'll see if performance is an issue, but the space I'm most interested in is turn based strategy / board games, where it doesn't seem to be a big deal if things are as fast as possible. It feels like a pretty natural fit, e.g.: can_move_to(unit_id, tile) :- Unit(unit_id), Tile(tile), reachable_to(unit_id, tile, move_cost), unit_move_points_remaining(unit_id, mv), move_cost <= mv. You can define a lot of rules from basic unit movement to "what happens when you activate Super Special Rule-Bending Ability" this way, and it's pretty easy to change the definitions if you want to experiment with different game rules / logic. In practice, you want various syntactic sugar. Haven't got a chance to take this very far yet, just casual experimentation, but it seems like there's potential.

YeGoblynQueenne 4y ago
Oh yeah, encoding game rules is a killer app for Prolog's declarative style. See my sibling comment- I've done this with M:tG and WH40k. With M:tG in particular, translating from the rulebook to Prolog, to code a rules engine, is a breeze, just because the M:tG rules are in such strict, formal language already. The jump from a well-written, unambiguous and precise set of board game rules and its translation in Prolog is a tiny step, that could even be automated with some elbow grease. Now, you mention "rendering" and that, on the other hand, I'm not sure is a very good application for Prolog. Nothing to do with speed, but arithmetic in Prolog is a bit meh, and if you want to do stuff like matrix arithmetic, you have to roll your own. Most Prologs don't even have arrays, as such (they kind of do but it's a bit of a hack).
convolvatron 4y ago
top-down datalog can almost certainly be compiled to something quite reasonable. you also might enjoy looking at incremental datalog (differentiating rules and operating on events). this generally does a really good job of touching just what need to update the global state. this is a great application

YeGoblynQueenne 4y ago

Here's some stuff I've written in Prolog, some for my own enjoyment, one for my degree project. Most of the benefits I found come down to two things: a) Prolog, like the various kanrens, is a relational language so a program is effectively a database. There's no need to do anything special to glue together a data layer and a logic layer, because you have both written in Prolog. No object-relational impedance mismatch whatsoever. b) Prolog's declarative style makes translating rules and directives into code a breeze. The three projects below are all games and benefit heavily from this feature. The same would go for business logic of any shape or form. 1. Warhammer 40K simulation: https://github.com/stassa/wh40ksim https://github.com/stassa/wh40ksim Runs simulations of combat between WH40k units. 2. Gleemin, a Magic: the Gathering expert system: https://github.com/stassa/Gleemin https://github.com/stassa/Gleemin Doesn't work anymore! Because backwards compatibility. Includes a) a parser for the rules text on M:tG cards written in Prolog's Definite Clause Grammars notation, b) a rules engine and c) a (primitive) AI player. The parser translates rules text from cards into rules engine calls. The cards themselves are Prolog predicates. Your data and your program are one and now you can also do stuff with them. 3. Nests & Insects, a roguelike TTRPG: https://github.com/stassa/nests-and-insects https://github.com/stassa/nests-and-insects WIP! Here I use Prolog to keep the data about my tabletop rpg organised, and also to automatically fill-in the character sheets typeset in the rulebook. The Prolog code runs a character creation process and generates completed character sheets. I plan to do the same for enemies' stat blocks, various procedural generation tables, etc. I also use Prolog to typeset the ASCII-styled rulebook, but that's actually not a good application of Prolog (too imperative). You asked about "logic programming" in general and not miniKanren in particular. I haven't actually used miniKanren, so I commented about the logic programming language I've used the most, Prolog. I hope that's not a thread hijack! All three of the projects above are basically games. I have more "serious" stuff on my github but I am currently experiencing a certain shortfall of gravitas.

nerdponx 4y ago
Thanks for the examples! I will have to review these.

sterlind 4y ago

I attempted to use Microkanren for type deduction in a transpiler I had to build at work. I wasn't actually trying to be a hipster, I just had to compile a dynamic language into the strictest possible static types. I'd reinvented unification, remembered Kanren which is built on that, so I reached for it. It didn't work out in my case. I found it really fiddly to work with, and the implementation I was loosely working from was very idiomatic Lisp.

protomyth 4y ago

For normal enterprise programming, they are fairly good for writing rules that normal business folks can eventually figure out. Every business has jargon to describe their business.

rad_gruchalski 4y ago

RBAC. Google Zanzibar comes to mind.

lukashrb 4y ago

If I recall correctly: cisco threat grid is using core.logic