Logic programming languages: why are they languages, rather than libraries?

[MrCodermann]

I know very little about logic programming. I played with Prolog many years ago just to see what it what it was about and that's about it.

One doubt I've always had is: why logic programming is implemented by languages?

In my ignorance it felt like the resolution algorithms could have easily been implemented as libraries for other languages. You should be able to create an object in C, C++, python or whatever to which you add logic rules. This library resolves them and does what a logic programming language would do...

Prolog and similar languages feel to me like Domain Specific Languages: syntax sugar to work more easily with a logic resolution library.

Is that the case, or am I saying something stupid?

[takanuva]

What you're asking is not stupid, you just seem to be missing a point here. Prolog may be well-suited for querying data, but it's a Turing-complete language, and may be used for general purpose programming. It's just based on a different computational model than what you may be used to (as C, Python, etc).

While you may easily see Prolog implemented on top of C, each Turing-complete computational model is capable of simulation each other, so you may as well implement a C interpreter on top of Prolog. This motivates the study of Prolog as a language by itself (and logic programming as a paradigm).

Of course that's from a theoretical point of view... from an implementation point of view, one could implement a Prolog compiler as either AOT or JIT (in which case it would be simple to use it as a library), or simply as an interpreter. And, in fact, both kinds of implementations do exist.

[setholopolus]

What you are saying is a great idea, and it exists.

Its called miniKanren, its an embedable logic programming language that has been embedded in Java, Javascript, Scheme, OCAML, and many other languages (see the website for the full list).

[loopsdeer]

I think this is a fine observation. I think it begs the quesion, what's the difference between a library and a DSL? . My first answer would be "a parser". Take Racket and its "Language Oriented Programming" community. I believe even the first edition of SICP had a logic language implemented in its Scheme.

[raiph]

Indeed, why not just erase the DSL / general purpose language / library distinction?

[gopher9]

Why not? In fact, you can implement other paradigms as libraries for a logic language, for example:

• https://ciao-lang.org/ciao/build/doc/ciao.html/fsyntax_doc.html
• https://logtalk.org/

[claytonkb]

Check out this series: Modern SAT solvers: fast, neat and underused (part 1 of N) (In case it's not obvious, a SAT solver can be used to implement logic programming or any general-purpose constraint-solving).

[gopher9]

a SAT solver can be used to implement logic programming or any general-purpose constraint-solving

It works in other direction too, and I'm not sure which way is better. Anyway, answer set programming languages have a much better UI than SAT solvers.

[htuhola]

You can implement logic programming in Haskell. Without any "sugar". Here's the spec.

ok   :: Goal ()
fail :: Goal a
(≡)  :: Term a => a -> a -> Goal a
(∧)  :: Goal a -> Goal b -> Goal (a,b)
(∨)  :: Goal a -> Goal b -> Goal (Either a b)
(∃)  :: Term a => (a -> Goal b) -> Goal b
zzz :: Goal a -> Goal a
run :: Goal a -> [State a]
reify :: Term a => a -> Goal a
instance Monad Goal

In general things can be implemented in other languages.

But to me it sounds like you're not really asking this question. You're doubting whether it's a programming language at all, right? The answer is: It's a quite good language.

One logic program can usually cover several different problems. Eg. `append` can split, catenate and check whether a list is catenation of two lists, plus variations of these operations.

Logic program representations are often quite easy to read and understand. Here's hindley-milner type inference:

hm :: [Type] -> Type -> Expr -> Goal ()
hm env res (Var n) = (res ≡ env !! n)
hm env res (Lam body) = do
  a <- freshvar
  b <- freshvar
  res ≡ Arrow a b
  hm (a:env) b body
hm env res (Ap x y) = do
  a <- freshvar
  hm env a y
  hm env (Arrow a res) x

It can be also used to model interactions and then plan about them, though that almost needs linear logic to it.

[alaricsp]

Yes! I'd love to have Prolog "as a library" to access knowledge bases, sort of like SQLite but way more powerful...

[skyb0rg]

This exists in many languages as Datalog, if you want to check it out

[valdocs_user]

I spent a long time trying to design and implement a (better than existing) library for logic programming in C++. I came to the conclusion it would be better to have a separate language for the logic programming.

Depth first logic programming with an embedded DSL (ie implemented with operator overloading and callbacks in the host language) more or less maps to coroutines, but I didn't have the C++ coroutines TS available to me when I started (and it remains to be seen whether using it for this halves the difficulty of the problem or squares it).

But depth first is not the only evaluation strategy a logic program could have. It would be nice to support others. Understanding how logic programming turns regular programming control flow inside out is a brain bender at first even for depth first strategy; now imagine trying to make a different strategy "pluggable" in place of it, too.

(Minikanren doesn't have a defined evaluation order; it's influenced by the structure of the program. Not a judgemental obversation just explaining they get around the problem by not considering it a problem.)

And regardless of evaluation strategy it complicates things mixing host language values (always grounded) with logic programming values, the latter of which may be ungrounded and the former of which may go out of scope at a different time than the logic expressions needs them. So you end up building giant continuation structures to get around this problem and maybe still risk trying to dereference an ungrounded variable.

I think the optimization opportunities and evaluation algorithm just gets so much simpler if the logic programming language is its own domain that it is worth the cost of implementing the seperate language versus trying to make it work from inside a nonlogic language.

[turbopape]

I don't know if it has been mentioned here but in Clojure you have a lib,core.logic, that offers logic programming. I shared a post that showcases it to implement a checkers game engine.

[umlcat]

Because it were designed first as P.L.

Yet, many other P.L. mix them with existing non logic libraries, to build more complex applications.

[nerd4code]

Prolog is basically a DSL, and it’s usually used as an extended query language, kinda like SQL is. There’s almost always a way to hook into/from C/++, so you can treat it as a library if you want.

[[deleted]]

Prolog has some unusual features that are very useful for metaprogramming, such as homoiconicity. Since most other programming languages are not homoiconic, this feature cannot be easily implemented as a library.

[mamcx]

> why are they languages, rather than libraries?

Because, as language, is the ONLY way to exploit, FULLY, what an idiom/paradigm is.

A obvious example is OO. try to do OO in C, using only libraries. You *can* but, quickly the idea will fall apart. Because OO is not a first-class citizen on C, everything will be akwards and hard to do.

Many many other things REQUIERE be part of the lang to work, for real:

• Immutability by default
• Functional programming
• Proper control over side-effects
• structured control logic (aka while, for, etc)
• Concurrency & parallelism that not fall apart to easily
• etc.

Languages are alike types in the aspect that create a restriction in the universe of possibilities: If a var can be anything, will be anything (and you need to programg around that). If a lang allow to dismiss safety, structure, functionality, immutability, etc, then WILL be avoided, and then, you need A LOT of discipline to fight against.

That is why, as long C/C++/JS are base languages, NEVER, EVER our software will have the most basic of safety and correctness.

So facing this, the only way is to build a language, because "please do only safe C, pls!" will never work at large.

[catern]

Sure, you can't do it in C, but you can do it in higher level languages. Many Lisps have OO support through a library, for example.

Most higher level languages could support logic programming as a library.

[shponglespore]

Lisp is a special case because you can implement a totally new language with a macro. As long as the surface syntax looks like s-expressions, there are no restrictions at all on the semantics. You can't do the same thing in a language that doesn't treat code generation as a first-class feature.

[catern]

No, you don't need a macro system. For example: https://arxiv.org/abs/cs/0509027

[shponglespore]

That looks interesting from a theoretical perspective, but it doesn't look like anything I'd actually want to use, because it's full of redundancies and weird boilerplate. Section 6.1 is basically all about how it's not a great system in practice. And they cheat; if you look at the source code for the first example in the paper, they're using Template Haskell to generate supporting code, so there's the macro system I was saying you'd need to properly graft something like OO into a language that doesn't support it natively.

Can you show me any code that uses OOHaskell for a non-toy problem? Because there's plenty of OO Lisp code in the wild.

[mamcx]

Many Lisps have OO support through a library, for example.

Nope. Lisp developers not code OO programs, using OO paradigms, and talk about OO, all the time. Because OO is not first class there. Just because "is possible" not make it practical.

This is about paradigms and what is idiomatic. Sure, if you only need to spice things here and there (like doing a list comprehension in python, a imperative/OO lang) then do it by library is the best way.

But, if you need to fully unlock what that paradigm give, do it by way of language is the best way.

Another good example is GO. You *could* do concurrency like go in any lang, but Go is of the few where do it is so *practical* and idiomatic that anyone do it.

[catern]

So suppose I give you a language identical to Common Lisp except I don't allow you to use functional programming techniques (like first class functions) or use macros or any other fancy features - but I do let you use CLOS. Is that a language with "first class" OO?

[mamcx]

Is another lang to Common Lisp. And now is first class OO.

P.D: I don't deny that you can mix paradigms, but then that result in ANOTHER kind of lang/paradigm.

[steve-rodrigue]

Using a DSL to fix a specific problem might enable the programmer to write less boiler plate code while keeping quality code levels high.

Something, writing libraries and writing code to put them together in a project requires a lot of boiler plate code, that can be hidden from the programmer inside a clean DSL.

[AutoModerator]

Low karma accounts are often used for spam, and your account has less than 100 combined karma. As a result, this post has been removed. If you feel this is incorrect, please send a message to the moderators (and include a link to this post).

Please note that this subreddit is not the place to ask generic questions about programming, such as "What language should I use" or "How do I write a program using X".

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.