6 ms·

I'm really fascinated by the resurgence of some of these old languages. I vaguely understand that the paradigm behind Prolog is quite different compared to oops

by jp0d 5y ago

I'm really fascinated by the resurgence of some of these old languages. I vaguely understand that the paradigm behind Prolog is quite different compared to oops or functional languages. Can anyone please help me understand where is this really useful? As everything is data oriented these days, is Prolog a good language for doing statistics or ML or scientific computing?

deleted 5y ago
[deleted]
mikelevins 5y ago
Prolog is well suited to transformations, representing and processing rules, and searching. It's a good fit for any program that can be expressed as a transformations or implications. Compilers and other programs that transform data are a good fit, as are rules engines, and pretty much anything that behaves like them. It turns out that transformations and rules engines are pretty generally useful, so Prolog makes a decent general-purpose programming language. It does take some getting used to, because its mode of operation is different from imperative and functional languages. You don't say, "do this, do that," and you don't present a functional expression for reduction to normal form. Instead, you write a set of facts and rules, then supply some initial conditions and let Prolog compute all the results that your rules imply. It can be a little brain-bending at first because most people seem to have an easier time with "do this, do that" than "this imples that, that implies the other thing." On the other hand, for problems that are naturally represented as transformations or rules engines, it can be sort of magical. One fun detail is that, since you can specify the logical relations between terms and not an order of operations, you can commonly write Prolog programs that can be run "forward" and "backward" -- that is, given a transformation between A and B, if you supply A it computes B, and if you supply B it computes A.
- sjg007 5y ago
  Deep learning may fit in the prolog paradigm in terms of finding programs to compute the output from the input. I am sure people are working on it, it is one aspect of differentiable programming.. This is similar to functional approaches as well. The search here is for the function f that computes f(A)=B ... Today we specify the state space as a CNN or transformer models. Prolog knows how to do deductions from logical statements so you'd need something similar for mapping f I guess.
  - YeGoblynQueenne 5y ago
    >> Deep learning may fit in the prolog paradigm in terms of finding programs to compute the output from the input. That's interesting, but my hunch is that you'd need two deep learning models to do what a single Prolog program could do: one model to map inputs to outputs and one to map outputs to inputs. One way to describe deep neural nets is to say that they are function approximators. Now, functions have well-defined inputs and outputs, although I don't think that's actual mathematical terminology. Functions are basically mappings from the elements of one or more sets _to_ the elements of another (or more) sets. But a function mapping is uni-directional. If you have a function ƒ: X → Y, it maps elements of X to Y, but it doesn't map elements of Y to X. So for instance, if you have a function that maps the set of integers from 1 to 24 to the set of letters in the English alphabet, you don't simultaneously have a function that maps letters to integers- you need another function. This is true both in mathematical terms and in programming terms. Suppose for instance that you have a Pseudocode function with signature: int_char(int: n) -> char: c You can call int_char() as: int_char(2) And get out "b", but you can't call it the other way: int_char("b") And expect to get 2 in return. In Prolog on the other hand there are no functions. Rather, every expression is a predicate, or in other words an n-ary relation. Now, the concept of relation is a generalisation of the concept of function, so in Prolog you could write int_char() above with the signature: int_char(N,C). And call it with either or both arguments instantiated... or none: ?- int_char(2,C). C = b. ?- int_char(N,b). N = 2. ?- int_char(2,b). true. ?- int_char(N,C). N = 1, C = a ; N = 2, C = b ; N = 3, C = c ; % ... etc Which you can't easily do with other languages. Well, you can do it in, say, C if you write a Prolog interpeter in C :-) Anyway, deep learning learns functions, not relations, so its models can't go back-and-forth between sets in mappings. In theory anyway; deep neural net often don't really care about theory.
spinningslate 5y ago
It's really quite different, and I don't think I can fully do it justice in a comment. I will give my favourite example though: it certainly helped me get the "aha" moment. Let's say you have a collection of cities, and a collection of roads between them. And you want to answer the question: "is there a route from City A to City E?" A solution in prolog would look something like this: /* First, the roads */ road("A", "B"). road("B", "C"). road("C", "D"). road ("D","E"). /* Now the algoritm */ route(From, To) :- road(From, To). route(From, To) :- road(From,Intermediate), route(Intermediate,To). That's it. There's no need to loop/iterate/check conditions. Simply state the facts, ask the question, and the prolog interpreter will search for an answer: ?- route("A", "E"). yes.
- bear8642 5y ago
  Why do you need route? Can't you just use the roads you've got as the base case and then say road(X, Z) :- road(X,Y), road(Y,Z)
  - spinningslate 5y ago
    > Why do you need route? Because it creates a left-recursive call that will eventually cause a stack overflow. If you want to try it out, there's Swish[0] - an online prolog editor and interpreter. [0]: https://swish.swi-prolog.org/ https://swish.swi-prolog.org/
rscho 5y ago
No, prolog is weak for things involving concrete calculations. It is absolutely stellar for anything involving using/building a logical transformation framework, such as building provers, compilers, solvers and the like. Most people will tell you it's slow, but that's comparing very specialized solvers built in C++ and the like. The yield/effort ratio of prolog programs for suitable problems is very high.
nerdponx 5y ago
I'm a Prolog newbie myself, but an experienced ML practitioner. Doing "high-level" model-building in a Prolog-like DSL might be interesting, but lower-level numerical code seems like a chore. The real "value" of Prolog (in my novice estimation) is querying data (i.e. Datalog), transforming between data formats, and building "logic-driven" applications like command-line tools, API clients, etc.
- YeGoblynQueenne 5y ago
  >> I'm a Prolog newbie myself, but an experienced ML practitioner. How experienced? Inductive Logic Programming has been a thing since 1991 :-)
  - nerdponx 5y ago
    Let's go with "ML as in applied statistics", not the traditional stuff.
    - YeGoblynQueenne 5y ago
      Fair enough, that's the common interpretation.
      - nerdponx 5y ago
        I should have known to be careful with that term in a Prolog thread!
        YeGoblynQueenne 5y ago
        Nah, I'm just a compulsive pedant :P
tannhaeuser 5y ago
> I'm really fascinated by the resurgence of some of these old languages. Not wanting to take away from your fascination ;) but even though Prolog is from 1972 (which may or may not be old, depending on your PoV), core Prolog syntax is pretty much a minimal language for representing terms and term unification. Doesn't get anymore straightforward than that, whether modern or not. Prolog is by itself no language for number crunching or SIMD, nor does it usually deal with memory alignment, sparse matrices, or other data layout concerns in the way C++ for CUDA does. OTOH, Inductive Learning (ILP) has been a major application of Prolog as recent as 2012 (ProGolem, Aleph, etc., some of which have been taken into commercial endeavors). But I'm not familiar enough with ML to contrast with last decades's ML push/approaches, let alone have an opinion.
trott 5y ago
> is Prolog a good language for doing statistics or ML or scientific computing? Not really, but the interesting thing about Prolog is ILP (inductive logic programming). ILP does things current deep learning can not: learning compact models, in a data-efficient manner, while utilizing explicit background knowledge. It has its own limitations though, related to noise tolerance, scalability and efficiency.
- YeGoblynQueenne 5y ago
  It is true that these were problems with ILP. But, have a look at the Top Program Construction paper: https://arxiv.org/abs/2101.05050 https://arxiv.org/abs/2101.05050 The experiments section shows one example of learning a program with a few thousand clauses and one example of learning with classification noise (i.e. misclassified examples), all in polynomial time and without "magic parameters" to overcome noise. P.S. Er, actually I'm the corresponding author of that paper so eh, take my comment with a grain of salt as usual when researchers promote their research...
  - rscho 5y ago
    I am very interested by ILP for some medical meta research, e.g. learning clinical guidelines (= care pathway for a particular condition) from papers on a topic. Do you think the current state of the art makes that possible? Would you be interested in such a thing (am european academic MD)? There would be a lot of noise, but there are big databases where the conclusions of clinical papers are already in predicate form.
    - YeGoblynQueenne 5y ago
      >> There would be a lot of noise, but there are big databases where the conclusions of clinical papers are already in predicate form. What, really? Well in that case, that's ideal. To clarify: yes, it's very very possible with the current state of the art. If you had unstructured text you'd have to do a lot of leg work to put it into a structured form, but if it's already in some kind of formal er form, then that's perfect. I am interested, but I'm on the final year of my PhD and about to start on my thesis (I have a second paper to submit in May 1st, then it's thesis writing time after that). Which means I don't know exactly how much I can justify other work. But I would be definitely interested to demonstrate a real-world application of the system described in the paper I link to above. Or, if you're more interested in a different system, I can at least advise you how to use it. Would you like to get in touch using the email in my profile? I trust you'll know how to use vim :-)
ookdatnog 5y ago
I think that, in a better version of this world, we'd be using logic programming for interacting with databases. Logic programming specializes in describing relations between data, so to me it seems like the perfect paradigm for database queries. Some people at google seem to be working on this idea: https://opensource.googleblog.com/2021/04/logica-organizing-your-data-queries.html https://opensource.googleblog.com/2021/04/logica-organizing-...
YeGoblynQueenne 5y ago
Statistics, no. Machine learning, yes. The most successful inductive programming approaches (learning programs from data) are Inductive Logic Programming approaches that basically learn Prolog programs from data. Prolog as a language with an automated deductive theorem prover as an interpreter is uniquely suited to learning new prorgams, because, it turns out, induction (learning new theories from observations and existing theories) is the inverse of deduction (explaining observations with existing theories). For some modern examples of learning Prolog programs with Prolog see: 1. Metagol: https://github.com/metagol/metagol https://github.com/metagol/metagol 2. Louise: https://github.com/stassa/louise https://github.com/stassa/louise 3. Popper: https://arxiv.org/abs/2005.02259 https://arxiv.org/abs/2005.02259 The first repo has a list of biblio right at the end, though it's a bit too formal maybe. Full disclosure: I started my PhD on Metagol and Louise is my work. For scientific computing, check out this paper: Using logic programming for theory representation and scientific inference https://www.sciencedirect.com/science/article/pii/S0732118X20302130?via%3Dihub https://www.sciencedirect.com/science/article/pii/S0732118X2... And see repo with code here: https://jeanchristopherohner.github.io/theory-toolbox-2/ https://jeanchristopherohner.github.io/theory-toolbox-2/
jp0d 5y ago
Thanks a ton for all these answer. Definitely had a couple of a-ha moments from these. Although I don't have enough time in hand at the moment to learn Prolog. But it's definitely one of the things I'll experiment with. Thank you all again. :)

by jp0d 5y ago

deleted 5y ago

[deleted]

mikelevins 5y ago

Prolog is well suited to transformations, representing and processing rules, and searching. It's a good fit for any program that can be expressed as a transformations or implications. Compilers and other programs that transform data are a good fit, as are rules engines, and pretty much anything that behaves like them. It turns out that transformations and rules engines are pretty generally useful, so Prolog makes a decent general-purpose programming language. It does take some getting used to, because its mode of operation is different from imperative and functional languages. You don't say, "do this, do that," and you don't present a functional expression for reduction to normal form. Instead, you write a set of facts and rules, then supply some initial conditions and let Prolog compute all the results that your rules imply. It can be a little brain-bending at first because most people seem to have an easier time with "do this, do that" than "this imples that, that implies the other thing." On the other hand, for problems that are naturally represented as transformations or rules engines, it can be sort of magical. One fun detail is that, since you can specify the logical relations between terms and not an order of operations, you can commonly write Prolog programs that can be run "forward" and "backward" -- that is, given a transformation between A and B, if you supply A it computes B, and if you supply B it computes A.

sjg007 5y ago
Deep learning may fit in the prolog paradigm in terms of finding programs to compute the output from the input. I am sure people are working on it, it is one aspect of differentiable programming.. This is similar to functional approaches as well. The search here is for the function f that computes f(A)=B ... Today we specify the state space as a CNN or transformer models. Prolog knows how to do deductions from logical statements so you'd need something similar for mapping f I guess.
- YeGoblynQueenne 5y ago
  >> Deep learning may fit in the prolog paradigm in terms of finding programs to compute the output from the input. That's interesting, but my hunch is that you'd need two deep learning models to do what a single Prolog program could do: one model to map inputs to outputs and one to map outputs to inputs. One way to describe deep neural nets is to say that they are function approximators. Now, functions have well-defined inputs and outputs, although I don't think that's actual mathematical terminology. Functions are basically mappings from the elements of one or more sets _to_ the elements of another (or more) sets. But a function mapping is uni-directional. If you have a function ƒ: X → Y, it maps elements of X to Y, but it doesn't map elements of Y to X. So for instance, if you have a function that maps the set of integers from 1 to 24 to the set of letters in the English alphabet, you don't simultaneously have a function that maps letters to integers- you need another function. This is true both in mathematical terms and in programming terms. Suppose for instance that you have a Pseudocode function with signature: int_char(int: n) -> char: c You can call int_char() as: int_char(2) And get out "b", but you can't call it the other way: int_char("b") And expect to get 2 in return. In Prolog on the other hand there are no functions. Rather, every expression is a predicate, or in other words an n-ary relation. Now, the concept of relation is a generalisation of the concept of function, so in Prolog you could write int_char() above with the signature: int_char(N,C). And call it with either or both arguments instantiated... or none: ?- int_char(2,C). C = b. ?- int_char(N,b). N = 2. ?- int_char(2,b). true. ?- int_char(N,C). N = 1, C = a ; N = 2, C = b ; N = 3, C = c ; % ... etc Which you can't easily do with other languages. Well, you can do it in, say, C if you write a Prolog interpeter in C :-) Anyway, deep learning learns functions, not relations, so its models can't go back-and-forth between sets in mappings. In theory anyway; deep neural net often don't really care about theory.

spinningslate 5y ago

It's really quite different, and I don't think I can fully do it justice in a comment. I will give my favourite example though: it certainly helped me get the "aha" moment. Let's say you have a collection of cities, and a collection of roads between them. And you want to answer the question: "is there a route from City A to City E?" A solution in prolog would look something like this: /* First, the roads */ road("A", "B"). road("B", "C"). road("C", "D"). road ("D","E"). /* Now the algoritm */ route(From, To) :- road(From, To). route(From, To) :- road(From,Intermediate), route(Intermediate,To). That's it. There's no need to loop/iterate/check conditions. Simply state the facts, ask the question, and the prolog interpreter will search for an answer: ?- route("A", "E"). yes.

bear8642 5y ago
Why do you need route? Can't you just use the roads you've got as the base case and then say road(X, Z) :- road(X,Y), road(Y,Z)
- spinningslate 5y ago
  > Why do you need route? Because it creates a left-recursive call that will eventually cause a stack overflow. If you want to try it out, there's Swish[0] - an online prolog editor and interpreter. [0]: https://swish.swi-prolog.org/ https://swish.swi-prolog.org/

rscho 5y ago

No, prolog is weak for things involving concrete calculations. It is absolutely stellar for anything involving using/building a logical transformation framework, such as building provers, compilers, solvers and the like. Most people will tell you it's slow, but that's comparing very specialized solvers built in C++ and the like. The yield/effort ratio of prolog programs for suitable problems is very high.

nerdponx 5y ago

I'm a Prolog newbie myself, but an experienced ML practitioner. Doing "high-level" model-building in a Prolog-like DSL might be interesting, but lower-level numerical code seems like a chore. The real "value" of Prolog (in my novice estimation) is querying data (i.e. Datalog), transforming between data formats, and building "logic-driven" applications like command-line tools, API clients, etc.

YeGoblynQueenne 5y ago
>> I'm a Prolog newbie myself, but an experienced ML practitioner. How experienced? Inductive Logic Programming has been a thing since 1991 :-)
- nerdponx 5y ago
  Let's go with "ML as in applied statistics", not the traditional stuff.
  - YeGoblynQueenne 5y ago
    Fair enough, that's the common interpretation.
    - nerdponx 5y ago
      I should have known to be careful with that term in a Prolog thread!
      - YeGoblynQueenne 5y ago
        Nah, I'm just a compulsive pedant :P

tannhaeuser 5y ago

> I'm really fascinated by the resurgence of some of these old languages. Not wanting to take away from your fascination ;) but even though Prolog is from 1972 (which may or may not be old, depending on your PoV), core Prolog syntax is pretty much a minimal language for representing terms and term unification. Doesn't get anymore straightforward than that, whether modern or not. Prolog is by itself no language for number crunching or SIMD, nor does it usually deal with memory alignment, sparse matrices, or other data layout concerns in the way C++ for CUDA does. OTOH, Inductive Learning (ILP) has been a major application of Prolog as recent as 2012 (ProGolem, Aleph, etc., some of which have been taken into commercial endeavors). But I'm not familiar enough with ML to contrast with last decades's ML push/approaches, let alone have an opinion.

trott 5y ago

> is Prolog a good language for doing statistics or ML or scientific computing? Not really, but the interesting thing about Prolog is ILP (inductive logic programming). ILP does things current deep learning can not: learning compact models, in a data-efficient manner, while utilizing explicit background knowledge. It has its own limitations though, related to noise tolerance, scalability and efficiency.

YeGoblynQueenne 5y ago
It is true that these were problems with ILP. But, have a look at the Top Program Construction paper: https://arxiv.org/abs/2101.05050 https://arxiv.org/abs/2101.05050 The experiments section shows one example of learning a program with a few thousand clauses and one example of learning with classification noise (i.e. misclassified examples), all in polynomial time and without "magic parameters" to overcome noise. P.S. Er, actually I'm the corresponding author of that paper so eh, take my comment with a grain of salt as usual when researchers promote their research...
- rscho 5y ago
  I am very interested by ILP for some medical meta research, e.g. learning clinical guidelines (= care pathway for a particular condition) from papers on a topic. Do you think the current state of the art makes that possible? Would you be interested in such a thing (am european academic MD)? There would be a lot of noise, but there are big databases where the conclusions of clinical papers are already in predicate form.
  - YeGoblynQueenne 5y ago
    >> There would be a lot of noise, but there are big databases where the conclusions of clinical papers are already in predicate form. What, really? Well in that case, that's ideal. To clarify: yes, it's very very possible with the current state of the art. If you had unstructured text you'd have to do a lot of leg work to put it into a structured form, but if it's already in some kind of formal er form, then that's perfect. I am interested, but I'm on the final year of my PhD and about to start on my thesis (I have a second paper to submit in May 1st, then it's thesis writing time after that). Which means I don't know exactly how much I can justify other work. But I would be definitely interested to demonstrate a real-world application of the system described in the paper I link to above. Or, if you're more interested in a different system, I can at least advise you how to use it. Would you like to get in touch using the email in my profile? I trust you'll know how to use vim :-)

ookdatnog 5y ago

I think that, in a better version of this world, we'd be using logic programming for interacting with databases. Logic programming specializes in describing relations between data, so to me it seems like the perfect paradigm for database queries. Some people at google seem to be working on this idea: https://opensource.googleblog.com/2021/04/logica-organizing-your-data-queries.html https://opensource.googleblog.com/2021/04/logica-organizing-...

YeGoblynQueenne 5y ago

Statistics, no. Machine learning, yes. The most successful inductive programming approaches (learning programs from data) are Inductive Logic Programming approaches that basically learn Prolog programs from data. Prolog as a language with an automated deductive theorem prover as an interpreter is uniquely suited to learning new prorgams, because, it turns out, induction (learning new theories from observations and existing theories) is the inverse of deduction (explaining observations with existing theories). For some modern examples of learning Prolog programs with Prolog see: 1. Metagol: https://github.com/metagol/metagol https://github.com/metagol/metagol 2. Louise: https://github.com/stassa/louise https://github.com/stassa/louise 3. Popper: https://arxiv.org/abs/2005.02259 https://arxiv.org/abs/2005.02259 The first repo has a list of biblio right at the end, though it's a bit too formal maybe. Full disclosure: I started my PhD on Metagol and Louise is my work. For scientific computing, check out this paper: Using logic programming for theory representation and scientific inference https://www.sciencedirect.com/science/article/pii/S0732118X20302130?via%3Dihub https://www.sciencedirect.com/science/article/pii/S0732118X2... And see repo with code here: https://jeanchristopherohner.github.io/theory-toolbox-2/ https://jeanchristopherohner.github.io/theory-toolbox-2/

jp0d 5y ago

Thanks a ton for all these answer. Definitely had a couple of a-ha moments from these. Although I don't have enough time in hand at the moment to learn Prolog. But it's definitely one of the things I'll experiment with. Thank you all again. :)