6 ms·

When would you reach for it?

winwang 1y ago
I've seen shops (e.g. Netflix I think) use Datalog for certain query types.
iLemming 1y ago
Scheduling, e.g., course scheduling - allocating rooms, professors, time slots while satisfying constraints; Product configuration systems - helping customers select compatible options for complex products; Genealogical research - querying family relationships and ancestry; Static analysis tools for code - finding bugs or verifying properties without execution; Medical diagnosis systems - inferring conditions from symptoms based on medical knowledge; Travel planning - finding optimal routes with multiple constraints; Legal reasoning systems - determining applicability of laws to specific cases; Natural language interfaces - parsing questions and generating appropriate database queries; Hardware verification - proving correctness of circuit designs; Puzzle solvers - Sudoku, crosswords, logic puzzles; Basically anything that excels when declarative specification of relationships is more natural than imperative algorithms.
- sethhochberg 1y ago
  This all makes perfect sense. The gap I usually have - and I admit its probably something of a skill issue, I have relatively little formal CS background - is how these abstract declarations of rules are integrated into a product. The example code in projects like this is usually pretty dense and intangible. Does anyone have good examples of open source codebases or reading material in this area? Lets imagine I have a set of complex business rules about the way a product can be configured and I want to use a logic programming language to enforce them, called from a web interface based on config data stored in a traditional relational database. Is that... a misunderstanding of how these things are to be used? I've love a good book about how to bring tools and techniques for logical correctness into a Rails ecosystem... or similar language/framework for app dev. I love the promises many of logic languages make but can't rewrite existing applications in them wholesale and it seems like they're a poor fit for that anyways. How are people blending these worlds at large enterprises? Maybe the answer is that nobody really is yet, and thats what makes things like Clolog + Clojure so exciting?
  - iLemming 1y ago
    FWIW I have no formal CS background whatsoever (maybe you shouldn't even listen to me on this matter), but if you want to gain some understanding of rule engines, you probably shouldn't start with core.logic or clolog (I have not looked into this project myself just yet, so my assumptions might be completely misleading) - core.logic imo good for complex constrains and relationships, it's based on miniKanren, but has quite steep learning curve, and not sure if it's worth the effort (as a starting point). oakes/odoyle-rules is a forward-chaining rules engine with a more straightforward approach - for someone already familiar with Clojure, it should be fun to try out. Then maybe check out Clara Rules, if I'm not mistaken the lib is specifically designed for business rules processing. For understanding the theoretical pieces, you probably want to look into forward vs. backward chaining rule systems; pattern matching used in rules engines; understanding how to model domain rules declaratively; Rete algorithm (odoyle lib explains it and iirc links to the paper).
    - ARandomerDude 1y ago
      Great comments, thank you for taking the time to mentor a few interested strangers.
      - iLemming 1y ago
        Awww, thank you. As a Clojurian, I aspire to be kind and helpful. The Clojure community is renowned for its friendly, coaching-oriented attitude. Anyone with questions (even those unrelated to Clojure) should absolutely reach out to Clojuristas — just go to http://clojurians.net http://clojurians.net and don't be shy. I'm forever thankful for Clojure for reigniting my passion for programming, but particularly, I'm indebted to the many individuals in the Clojure community. Whenever I pose a question expecting just straightforward guidance or documentation links, I consistently receive profound, thought-provoking answers that surpass my expectations. Virtually every discussion I initiate with them ends up being incredibly educational, teaching me far more than I initially sought. I can confidently admit - yes, learning Clojure has made a better programmer out of me, but most importantly, it made me a better person.
  - 1y ago
- whartung 1y ago
  Well the bigger question is how big does the system have to be to warrant breaking out a new technique, much less adding a new runtime or other large dependency. Now, I have no direct experience with any of the common logical programming systems. I have familiarity. But anytime I came upon anything that might justify such a system, the need just didn’t seem to justify it. Talking less than 100 rules. Most likely less than a couple dozen. Stacking some IFs and a bit of math, strategically grouped in a couple aptly named wrapper methods to help reduce the cognitive load, and it’s all worked pretty well. And, granted, if I had solid experience using these systems, onboarding cost would be lower. When have you found it to be worth cutting over?
  - iLemming 1y ago
    Absolutely valid and befitting point - adding complexity without clear benefits never should be justified. Most (business) applications have ruleset logic for specific problems not exceeding a dozens of rules - regular code often works fine. Logic systems tend to show the value when rules become complex with many interdependencies or non-linear execution patterns emerge, or rules change frequently or need to be defined at runtime; when you need explanation tools - e.g., why was this conclusion reached?, etc. I agree, situations for when you need to implement a logic system are not extremely common, but maybe I just have not worked in industries where they are - on top of my head I can think of: factory floor scheduling; regulatory compliance (e.g., complex tax rules); insurance systems, risk-calculation (credit approval); strategy games; retail - complex discounting; etc.
  - sterlind 1y ago
    I had the (self-inflicted) problem of modeling systems of linear equations in C#. `x` is a Sym, `x+2` is an Expr, `[2x,3y]` is a TermVector, etc. I wanted the comforts of NumPy, so adding an Int to a SymVector should make an ExprVector by broadcast, you should be able to multiply two IntMatrixes together but not two SymMatrixes (since that's not linear), etc. It would have been a lot of wrapper code to write. Instead, I implemented a minimal set of primitives, and wrote a set of derivation rules (e.g. "if you have X+Y, and Y supports negation, you can derive X-Y by X+(-Y)"), and constraints (operator overloads mustn't have ambiguous signatures, no cycles allowed in the call tree), and set up a code generator. 250 lines of Prolog, plus another 250 of ASP (a dialect of Prolog), and I had a code synthesizer. it was one of the most magical experiences of my entire career. I'd write an optimized version of a function, rerun synthesis and it would use it everywhere it could. I'd add new types and operators and it'd instantly plumb them through. seeing code synthesis dance for you feels amazingly liberating. it's like the opposite of technical debt.
- barrenko 1y ago
  I really don't know not nearly enough about the topic - but couldn't a lot of these be handled with types, so my question is - are types at least adjacent to logical programming? (apologies in advance)
  - iLemming 1y ago
    Yes, afaik there is meaningful relevance between logic programming and type systems - Curry-Howard; Dependent types; SMT solvers (related to SAT solvers mentioned in this discussion). However, constraint problems discussed (scheduling, travel planning, puzzles) would require quite verbose and complex encoding to solve with a type system and significant sophistication - Idris or Coq aren't for the faint-hearted. Type systems would absolutely choke on trying to solve things like: Knowlege representation and querying - imagine medical diagnosis systems with thousands symptoms and conditions; Dynamic constraint solving - where constraints emerge at runtime; Exploratory search problems requiring bfs/dfs of large solution spaces - e.g., route finding with changing conditions; NLP tasks - grammar parsing and understanding; etc.
baq 1y ago
Same reason you’d reach for SQL when querying relations - a good enough tool designed for the job. The problem has always been getting facts into the prolog system. I’ve been looking for a prolog which is as easy to embed in eg Python or node as a Postgres client and… crickets.
- Avshalom 1y ago
  I dunno which postgres client you're thinking of but: https://github.com/tau-prolog/tau-prolog https://github.com/tau-prolog/tau-prolog https://pyswip.org/ https://pyswip.org/ https://www.swi-prolog.org/packages/mqi/prologmqi.html https://www.swi-prolog.org/packages/mqi/prologmqi.html Unfortunately the tau site's certificate seems to have lapsed sometime in the last week or so, but I swear it's actually very good.
- cess11 1y ago
  Prolog has very little syntax, usually it's not particularly hard to serialise your data structure directly into Prolog code and consult it. If your data is streaming you might have to resort to assert/asserta/assertz/retract, depending on your use case. log("2024-10-22", "09:09:23", "Mozilla", "/login"). log("2024-10-23", "09:09:24", "Safari", "/dash"). log("2024-10-24", "09:09:25", "Chrome", "/user"). log("2024-10-25", "09:09:26", "Brave", "/login"). Implementing a transform of a web server log file into Prolog can be as simple as this. In practice you'll have more like ten or twenty fields, of course. Then you can query along the lines of log(Date, Time, "user agent constraint", Resource). and don't have to be as diligent as when stacking grep:s or such. If you already keep all your logs in analytics databases the example isn't very good, but it ought to be easy to see how this trivial technique can be applied elsewhere.

I've seen shops (e.g. Netflix I think) use Datalog for certain query types.

Scheduling, e.g., course scheduling - allocating rooms, professors, time slots while satisfying constraints; Product configuration systems - helping customers select compatible options for complex products; Genealogical research - querying family relationships and ancestry; Static analysis tools for code - finding bugs or verifying properties without execution; Medical diagnosis systems - inferring conditions from symptoms based on medical knowledge; Travel planning - finding optimal routes with multiple constraints; Legal reasoning systems - determining applicability of laws to specific cases; Natural language interfaces - parsing questions and generating appropriate database queries; Hardware verification - proving correctness of circuit designs; Puzzle solvers - Sudoku, crosswords, logic puzzles; Basically anything that excels when declarative specification of relationships is more natural than imperative algorithms.

sethhochberg 1y ago
This all makes perfect sense. The gap I usually have - and I admit its probably something of a skill issue, I have relatively little formal CS background - is how these abstract declarations of rules are integrated into a product. The example code in projects like this is usually pretty dense and intangible. Does anyone have good examples of open source codebases or reading material in this area? Lets imagine I have a set of complex business rules about the way a product can be configured and I want to use a logic programming language to enforce them, called from a web interface based on config data stored in a traditional relational database. Is that... a misunderstanding of how these things are to be used? I've love a good book about how to bring tools and techniques for logical correctness into a Rails ecosystem... or similar language/framework for app dev. I love the promises many of logic languages make but can't rewrite existing applications in them wholesale and it seems like they're a poor fit for that anyways. How are people blending these worlds at large enterprises? Maybe the answer is that nobody really is yet, and thats what makes things like Clolog + Clojure so exciting?
- iLemming 1y ago
  FWIW I have no formal CS background whatsoever (maybe you shouldn't even listen to me on this matter), but if you want to gain some understanding of rule engines, you probably shouldn't start with core.logic or clolog (I have not looked into this project myself just yet, so my assumptions might be completely misleading) - core.logic imo good for complex constrains and relationships, it's based on miniKanren, but has quite steep learning curve, and not sure if it's worth the effort (as a starting point). oakes/odoyle-rules is a forward-chaining rules engine with a more straightforward approach - for someone already familiar with Clojure, it should be fun to try out. Then maybe check out Clara Rules, if I'm not mistaken the lib is specifically designed for business rules processing. For understanding the theoretical pieces, you probably want to look into forward vs. backward chaining rule systems; pattern matching used in rules engines; understanding how to model domain rules declaratively; Rete algorithm (odoyle lib explains it and iirc links to the paper).
  - ARandomerDude 1y ago
    Great comments, thank you for taking the time to mentor a few interested strangers.
    - iLemming 1y ago
      Awww, thank you. As a Clojurian, I aspire to be kind and helpful. The Clojure community is renowned for its friendly, coaching-oriented attitude. Anyone with questions (even those unrelated to Clojure) should absolutely reach out to Clojuristas — just go to http://clojurians.net http://clojurians.net and don't be shy. I'm forever thankful for Clojure for reigniting my passion for programming, but particularly, I'm indebted to the many individuals in the Clojure community. Whenever I pose a question expecting just straightforward guidance or documentation links, I consistently receive profound, thought-provoking answers that surpass my expectations. Virtually every discussion I initiate with them ends up being incredibly educational, teaching me far more than I initially sought. I can confidently admit - yes, learning Clojure has made a better programmer out of me, but most importantly, it made me a better person.
- 1y ago
whartung 1y ago
Well the bigger question is how big does the system have to be to warrant breaking out a new technique, much less adding a new runtime or other large dependency. Now, I have no direct experience with any of the common logical programming systems. I have familiarity. But anytime I came upon anything that might justify such a system, the need just didn’t seem to justify it. Talking less than 100 rules. Most likely less than a couple dozen. Stacking some IFs and a bit of math, strategically grouped in a couple aptly named wrapper methods to help reduce the cognitive load, and it’s all worked pretty well. And, granted, if I had solid experience using these systems, onboarding cost would be lower. When have you found it to be worth cutting over?
- iLemming 1y ago
  Absolutely valid and befitting point - adding complexity without clear benefits never should be justified. Most (business) applications have ruleset logic for specific problems not exceeding a dozens of rules - regular code often works fine. Logic systems tend to show the value when rules become complex with many interdependencies or non-linear execution patterns emerge, or rules change frequently or need to be defined at runtime; when you need explanation tools - e.g., why was this conclusion reached?, etc. I agree, situations for when you need to implement a logic system are not extremely common, but maybe I just have not worked in industries where they are - on top of my head I can think of: factory floor scheduling; regulatory compliance (e.g., complex tax rules); insurance systems, risk-calculation (credit approval); strategy games; retail - complex discounting; etc.
- sterlind 1y ago
  I had the (self-inflicted) problem of modeling systems of linear equations in C#. `x` is a Sym, `x+2` is an Expr, `[2x,3y]` is a TermVector, etc. I wanted the comforts of NumPy, so adding an Int to a SymVector should make an ExprVector by broadcast, you should be able to multiply two IntMatrixes together but not two SymMatrixes (since that's not linear), etc. It would have been a lot of wrapper code to write. Instead, I implemented a minimal set of primitives, and wrote a set of derivation rules (e.g. "if you have X+Y, and Y supports negation, you can derive X-Y by X+(-Y)"), and constraints (operator overloads mustn't have ambiguous signatures, no cycles allowed in the call tree), and set up a code generator. 250 lines of Prolog, plus another 250 of ASP (a dialect of Prolog), and I had a code synthesizer. it was one of the most magical experiences of my entire career. I'd write an optimized version of a function, rerun synthesis and it would use it everywhere it could. I'd add new types and operators and it'd instantly plumb them through. seeing code synthesis dance for you feels amazingly liberating. it's like the opposite of technical debt.
barrenko 1y ago
I really don't know not nearly enough about the topic - but couldn't a lot of these be handled with types, so my question is - are types at least adjacent to logical programming? (apologies in advance)
- iLemming 1y ago
  Yes, afaik there is meaningful relevance between logic programming and type systems - Curry-Howard; Dependent types; SMT solvers (related to SAT solvers mentioned in this discussion). However, constraint problems discussed (scheduling, travel planning, puzzles) would require quite verbose and complex encoding to solve with a type system and significant sophistication - Idris or Coq aren't for the faint-hearted. Type systems would absolutely choke on trying to solve things like: Knowlege representation and querying - imagine medical diagnosis systems with thousands symptoms and conditions; Dynamic constraint solving - where constraints emerge at runtime; Exploratory search problems requiring bfs/dfs of large solution spaces - e.g., route finding with changing conditions; NLP tasks - grammar parsing and understanding; etc.

baq 1y ago

Same reason you’d reach for SQL when querying relations - a good enough tool designed for the job. The problem has always been getting facts into the prolog system. I’ve been looking for a prolog which is as easy to embed in eg Python or node as a Postgres client and… crickets.

Avshalom 1y ago
I dunno which postgres client you're thinking of but: https://github.com/tau-prolog/tau-prolog https://github.com/tau-prolog/tau-prolog https://pyswip.org/ https://pyswip.org/ https://www.swi-prolog.org/packages/mqi/prologmqi.html https://www.swi-prolog.org/packages/mqi/prologmqi.html Unfortunately the tau site's certificate seems to have lapsed sometime in the last week or so, but I swear it's actually very good.
cess11 1y ago
Prolog has very little syntax, usually it's not particularly hard to serialise your data structure directly into Prolog code and consult it. If your data is streaming you might have to resort to assert/asserta/assertz/retract, depending on your use case. log("2024-10-22", "09:09:23", "Mozilla", "/login"). log("2024-10-23", "09:09:24", "Safari", "/dash"). log("2024-10-24", "09:09:25", "Chrome", "/user"). log("2024-10-25", "09:09:26", "Brave", "/login"). Implementing a transform of a web server log file into Prolog can be as simple as this. In practice you'll have more like ten or twenty fields, of course. Then you can query along the lines of log(Date, Time, "user agent constraint", Resource). and don't have to be as diligent as when stacking grep:s or such. If you already keep all your logs in analytics databases the example isn't very good, but it ought to be easy to see how this trivial technique can be applied elsewhere.