6 ms·

Using Prolog as the AST

156 points by mpweiher 3y ago

simplify 3y ago
Consider using Datalog (the incredible subset of Prolog) for this perfect use case. Compared to Prolog, you get: 1. Free de-duplication. No more debugging why a predicate is returning the same result more than once. 2. Commutativity. Order of predicates does not change the result. Finally, true logic programming! 3. Easy static analysis. There are many papers that describe how to do points-to analysis (and other similar techniques) with Datalog rules that fit on a single page :O Souffle[0] is a mature Datalog that is highly performant and has many nice features. I highly recommend playing with it! [0] https://souffle-lang.github.io https://souffle-lang.github.io
- all2 3y ago
  Souffle seems to suffer from the standard small language issue of no code examples front and center. Also, no "how is this better than X" or "example of usage in Y". To those who have used Prolog, is the description sufficient to know what it does and if it will be useful? I've never use prolog and I don't know the lingo.
  - simplify 3y ago
    I recommend starting with the simple example[0], then taking a look at the tutorial[1]. But I do agree that being familiar with Prolog is a big help in understanding what Souffle is. For a quick intro to Prolog, I recommend this video[2], which speaks from a "industry practical" point of view, and introduces concepts that almost all apply to Datalog :) [0] https://souffle-lang.github.io/simple https://souffle-lang.github.io/simple [1] https://souffle-lang.github.io/tutorial https://souffle-lang.github.io/tutorial [2] https://twitter.com/ThePrologClause/status/1500642533940023302 https://twitter.com/ThePrologClause/status/15006425339400233...
    - bmacho 3y ago
      [2] leads to https://share.descript.com/view/snZvbV85LdN https://share.descript.com/view/snZvbV85LdN
  - trott 3y ago
    Prolog is Turing-complete, and Datalog isn't. In light of this, I think it's a bit of a stretch to call it a (logic) programming language. But people seem to do that.
    - tonyg 3y ago
      Many perfectly reasonable subturing PLs exist. For example Gallina, the total functional language at the heart of Coq.
    - simplify 3y ago
      Turing completeness is not a requirement of a programming language! Just because you can't do infinite computation doesn't mean you can't do infinitely useful computation :) That said, Souffle is touring complete due to its adding of constructors to the language.
    - gnulinux 3y ago
      Turing completeness is a bug, not a feature. After writing code in Agda for some years I was convinced that Turing completeness does more harm than good. Non-TC languages have a killer feature: their halting problem is solvable which means you can get arbitrarily strong guarantees from the compiler. The fact that you can't encode "while(true) { }" without putting "unsafe" doesn't make the language impractical, you can still implement algorithms without Turing completeness. Moreover, using various forms of coinduction you can encode infinite computation even in non-TC languages.
      - deleted 3y ago
        [deleted]
      - all2 3y ago
        Ok, ok I understand theoretically what this means in terms of programming languages. But what does it mean practically? What features are removed? How does this work out when you're implementing a program?
      - trott 3y ago
        Agda's been around for 24 years, according to Wikipedia, and it hasn't exactly revolutionized software development: I'm not aware of any notable software written in it, or of anyone so much as winning a programming competition while using it (and some of those are designed to promote functional programming) So, frankly, I'm skeptical that Agda's trade-offs in the performance-convenience-correctness space are good.
  - crdrost 3y ago
    So in the great scheme of programming languages, you had imperative languages like Fortran, eventually there was a paper “GOTO considered harmful” which ushered in a scaling-back of complexity to “structured programming” where you had named cells in which you could store values, and looping constructs like `while` and `for` to walk through them and manipulate them. Then we added on lexical closures over environments, which also take the form of “methods on objects” and “dynamic dispatch,” a bunch of different names for different forms of single-threaded OOP. Languages like GIL-ed Python and Ruby and Node.js continue this tradition today, while other languages add threading to have shared-state concurrent programming, with its vocabulary of locks and race conditions and cache invalidation and transactions and commits and consensus algorithms and now CRDTs... But, other visions of programming have coexisted with this main educational vortex, including logic programming like Prolog. Actually, if you have heard of any of these alternates, you have probably heard of functional programming, which can be ahistorically understood as saying “hey these locks and races and all that, it's actually very complicated, maybe we could have a simpler model of programming for 90% of our work and only break out the Java when we really need it.” And you’re like “what will you replace it with?” and they respond “Template substitutions! It's all the power of lexicographic scopes, all the power of looping (via recursion), but when you want to express the really complex stuff you need templates that have side effects when substituted, we can give those scary names.” So you give me a sunbeam and a raincloud and I give you back a rainbow. If that's the functional programming idea then logic programming takes the same idea but adds unification and search. The idea is “ok but why do I have to fill in all the parameters to a template before I use it? I should just say “if light shines on a droplet-cloud it makes a rainbow, a sunbeam is a light, a raincloud is a droplet-cloud, hey language, what are all the things that make a rainbow?” Functional programming was based on the function, the template, the “I take these args and produce a structure looking like such-and-so.” Logic programming is based on the Horn clause, “X verbs Y, for some entities X and Y that I maybe know about and some verb that I am being introduced to.” Basic things that logic programming does very well, OOP kind of struggles with. You can kind of understand this if you have written a SQL query. The verbs can be thought of as tables that foreign-key to X and to Y, if you want to write OOP to solve a logic puzzle you have to choose explicit ways to search or brute force... SQL DBs come with B-trees and indexes to solve a lot of these problems. Whereas with Prolog you just write the pattern to match and the new pattern to emit. It's a rather different take on what the building blocks should be.
  - crabbone 3y ago
    I was in the same group when I wanted to try Mercury (another Prolog-like language, but with ML-like types). Someone on Mercury's mailing list took pity on me, and told me to just straight up try some Prolog. Prolog, at least the basics, isn't hard at all, and it takes maybe a day to get you to write something that works. Of course, every language has its inconsistencies, dark corners and unexpected turns, and, sometimes some very deep and general pieces of wisdom that aren't on the surface. But, really, if you want to understand any Prolog derivative, the best way I can think about, is to learn some Prolog. It's the most efficient way to the goal. It doesn't really take long.
- oldsecondhand 3y ago
  > 2. Commutativity. Order of predicates does not change the result. Finally, true logic programming! I'm not sure this is a good selling point. The fact that predicate order matters in Prolog allows performance optimization and more transparent debugging.
  - simplify 3y ago
    It's a great one! From a logical perspective, it's ideal for the order of constraints to not affect the outcome. This missing behavior becomes a quirk quite early on when working with Prolog. That said, order of constraints can affect performance. But since reordering doesn't affect outcome, you are free resort them as you wish in effort to optimize for better performance :)
JimmyRuska 3y ago
Racket made a prolog implementation that is currently used in the compiler, or at least I thought I heard that in one of their talks. Might be worth trying, since its model is a language for making languages https://docs.racket-lang.org/datalog/ https://docs.racket-lang.org/datalog/ https://docs.racket-lang.org/racklog/ https://docs.racket-lang.org/racklog/
- Blackthorn 3y ago
  That looks pretty cool. Whenever I see the words "prolog-style" I always ctrl+f for "cut", and this one passes!
yowlingcat 3y ago
Asking this earnestly and not as a rhetorical question: what do I get from Prolog that I can't get from using SQL? Is it speed, is it ergonomics, is it the ability to do computations that are otherwise intractable? And if there are any such advantages, at what level of complexity of abstraction do they come up, and at which level would I not see the value of using prolog?
- 4ad 3y ago
  I am not sure how you could meaningfully compare Prolog and SQL. Both are declarative languages, but that's where the similarities end. SQL is for interacting with databases, whereas Prolog is, more or less, a language that you can write regular programs in. Perhaps the Prolog terminology of "queries" and "database" gave you the impression it has something to do with databases that store data. It doesn't. The query is over logical terms, and the database is a collection of Prolog facts.
  - ngruhn 3y ago
    Both languages are relational, which is fairly unique among programming languages. For example you can define a graph in Prolog like this: edge(1, 2). edge(2, 3). edge(3, 4). These edges are naturally undirected. Similarly, in SQL you can have a table "Edges": +——-+——-+ | 1 | 2 | | 2 | 3 | | 3 | 4 | +——-+——-+ which also imposes no strict direction. In non-relational languages you have to define maps for both directions. However, in Prolog you can easily define something like reachability using recursion: reachable(V, V). reachable(V, W) :- edge(V, U), reachable(U, W). In SQL you would have to join the "Edges" table with itself an unknown number of times. I suspect this is possible somehow but definitely less natural.
    - Epa095 3y ago
      The reachable predicate on your 'naturally undirected edges' treat them as directed;-) I would rather say that your edges are naturally directed, and then you can add a clause to make them undirected.
    - 3y ago
daitangio 3y ago
Erlang first implementation was based on Prolog, which is the mahor reason of its syntax
iot_devs 3y ago
As very long term goal, I want to work on a project like this but on much larger scale. I have a tiny prototype based on Go and soufflé. The overall goal would be to figure out classical error conditions like nill pointers deference. If I can figure out if a pointer will be nil in some execution branch, there is no reason why a computer cannot do the same. However it is very hard work and the part I am currently stuck in is creating a reasonable abstraction level where I can reason (in soufflé) about code and not about an AST. I personally would see this as an human race level upgrades. Imagine feeding your code to a CI that spit back something like: "you will have a panic at line 156 when your input is > 4" Moreover we will be able to check the "real code" starting from main down to all execution paths. Which is much more powerful than current static analysis that usually analyse a single function without considering how the function itself is invoked. Beside the actual implementation difficulties, the other big elephant in the room is the amount of resources needed to run this kind of analysis. (I am less concerned about that as computation resources exploded due to AI and solving SAT is getting faster and faster)
- dackerlunghack 3y ago
  [dead]
- nextaccountic 3y ago
  > The overall goal would be to figure out classical error conditions like nill pointers deference. > If I can figure out if a pointer will be nil in some execution branch, there is no reason why a computer cannot do the same. Note, this is called flow-sensitive typing (also called type narrowing) and I think that typescript does it. https://en.wikipedia.org/wiki/Flow-sensitive_typing https://en.wikipedia.org/wiki/Flow-sensitive_typing > I personally would see this as an human race level upgrades. Imagine feeding your code to a CI that spit back something like: "you will have a panic at line 156 when your input is > 4" A model checker can do that! See this https://model-checking.github.io/kani/tutorial-kinds-of-failure.html https://model-checking.github.io/kani/tutorial-kinds-of-fail... Other techniques are also possible https://github.com/viperproject/prusti-dev#quick-example https://github.com/viperproject/prusti-dev#quick-example (Here I could link a lot of things, I just selected two Rust projects to illustrate) This works better if you are able to provide contracts in your API that says which guarantees you provide. Alternatively, asserts are useful too.
throwaway42534 3y ago
Meta develops a system based on similar ideas https://glean.software https://glean.software https://www.youtube.com/watch?v=eFglEyb-KfM&t=4s https://www.youtube.com/watch?v=eFglEyb-KfM&t=4s
forward-slashed 3y ago
Oh, this is great. This article and conversation with Marcelle led me down a rabbit hole of Prolog, Minikanren, and Reasoned Schemer. Not quite out yet. I am thinking about using this idea of Prolog as AST to build an ai-first, reactive IDE. DM me at @eating_entropy on Twitter or email me at joshcho@stanford.edu if you are interested.
- conartist6 3y ago
  What would the point of any of the formal logic tools be for an "ai-first" IDE? Aren't current IDEs "reactive"?
  - anonzzzies 3y ago
    To make software actually better instead of worse when we get worse-than-the-worst code generated by AI's to maintain the coming years?
  - forward-slashed 3y ago
    Hey conartist6, thanks for the interest. I'll share once I get something going.
_a_a_a_ 3y ago
> For example when I’m traversing the AST when I’m looking at the node { type: "num", value: 10 }, without doing extra work to go back up the tree I have no way to tell that it belongs to the name “ten”. There's a very easy way to do it, simply add a pointer from the child back up to the parent. It means you can't share AST nodes but it's damn fast and, once debugged, very easy to maintain. I've done this on my personal project and so a question to everyone: when I originally heard of using datalog in compilers it seemed like a very good idea, like it was promising some real value somewhere, but I've seen examples that show you can do trivial type checking – but I do that myself and it's very, very easy. Perhaps I'm looking at this wrong? If I'd used data log then I could knock at a few hundred lines of code scattered around the AST objects, but surely I can do more than that with datalog? I feel I'm missing something, and the crowd here seems knowledgeable so any good pointers (good = simple, because I'm a n00b) would be incredibly helpful! (I am aware of some really advanced stuff like BDDBDDB (https://suif.stanford.edu/bddbddb/ https://suif.stanford.edu/bddbddb/), so advanced I can't even follow it, I'm looking for something between the triviality of type checking and the complexity of full dataflow – the problem here may be a personal one, in that I might need to have to write a dataflow implementation to get a really good 'feel' for it, and then I might 'get' the value of using e.g. datalog, I don't know, but any guidance welcome) this will feed into an actual working project).
vonwoodson 3y ago
I remember the first time I saw a declarative language, I also immediately saw it as an AST. It’s so validating to see it being explored by other people too.
sriram_malhar 3y ago
Here's Niko Matsakis's embeddable logic engine in rust, to be used in the rust compiler's type system. https://github.com/nikomatsakis/chalk-ndm https://github.com/nikomatsakis/chalk-ndm

156 points by mpweiher 3y ago

Consider using Datalog (the incredible subset of Prolog) for this perfect use case. Compared to Prolog, you get: 1. Free de-duplication. No more debugging why a predicate is returning the same result more than once. 2. Commutativity. Order of predicates does not change the result. Finally, true logic programming! 3. Easy static analysis. There are many papers that describe how to do points-to analysis (and other similar techniques) with Datalog rules that fit on a single page :O Souffle[0] is a mature Datalog that is highly performant and has many nice features. I highly recommend playing with it! [0] https://souffle-lang.github.io https://souffle-lang.github.io

all2 3y ago
Souffle seems to suffer from the standard small language issue of no code examples front and center. Also, no "how is this better than X" or "example of usage in Y". To those who have used Prolog, is the description sufficient to know what it does and if it will be useful? I've never use prolog and I don't know the lingo.
- simplify 3y ago
  I recommend starting with the simple example[0], then taking a look at the tutorial[1]. But I do agree that being familiar with Prolog is a big help in understanding what Souffle is. For a quick intro to Prolog, I recommend this video[2], which speaks from a "industry practical" point of view, and introduces concepts that almost all apply to Datalog :) [0] https://souffle-lang.github.io/simple https://souffle-lang.github.io/simple [1] https://souffle-lang.github.io/tutorial https://souffle-lang.github.io/tutorial [2] https://twitter.com/ThePrologClause/status/1500642533940023302 https://twitter.com/ThePrologClause/status/15006425339400233...
  - bmacho 3y ago
    [2] leads to https://share.descript.com/view/snZvbV85LdN https://share.descript.com/view/snZvbV85LdN
- trott 3y ago
  Prolog is Turing-complete, and Datalog isn't. In light of this, I think it's a bit of a stretch to call it a (logic) programming language. But people seem to do that.
  - tonyg 3y ago
    Many perfectly reasonable subturing PLs exist. For example Gallina, the total functional language at the heart of Coq.
  - simplify 3y ago
    Turing completeness is not a requirement of a programming language! Just because you can't do infinite computation doesn't mean you can't do infinitely useful computation :) That said, Souffle is touring complete due to its adding of constructors to the language.
  - gnulinux 3y ago
    Turing completeness is a bug, not a feature. After writing code in Agda for some years I was convinced that Turing completeness does more harm than good. Non-TC languages have a killer feature: their halting problem is solvable which means you can get arbitrarily strong guarantees from the compiler. The fact that you can't encode "while(true) { }" without putting "unsafe" doesn't make the language impractical, you can still implement algorithms without Turing completeness. Moreover, using various forms of coinduction you can encode infinite computation even in non-TC languages.
    - deleted 3y ago
      [deleted]
    - all2 3y ago
      Ok, ok I understand theoretically what this means in terms of programming languages. But what does it mean practically? What features are removed? How does this work out when you're implementing a program?
    - trott 3y ago
      Agda's been around for 24 years, according to Wikipedia, and it hasn't exactly revolutionized software development: I'm not aware of any notable software written in it, or of anyone so much as winning a programming competition while using it (and some of those are designed to promote functional programming) So, frankly, I'm skeptical that Agda's trade-offs in the performance-convenience-correctness space are good.
- crdrost 3y ago
  So in the great scheme of programming languages, you had imperative languages like Fortran, eventually there was a paper “GOTO considered harmful” which ushered in a scaling-back of complexity to “structured programming” where you had named cells in which you could store values, and looping constructs like `while` and `for` to walk through them and manipulate them. Then we added on lexical closures over environments, which also take the form of “methods on objects” and “dynamic dispatch,” a bunch of different names for different forms of single-threaded OOP. Languages like GIL-ed Python and Ruby and Node.js continue this tradition today, while other languages add threading to have shared-state concurrent programming, with its vocabulary of locks and race conditions and cache invalidation and transactions and commits and consensus algorithms and now CRDTs... But, other visions of programming have coexisted with this main educational vortex, including logic programming like Prolog. Actually, if you have heard of any of these alternates, you have probably heard of functional programming, which can be ahistorically understood as saying “hey these locks and races and all that, it's actually very complicated, maybe we could have a simpler model of programming for 90% of our work and only break out the Java when we really need it.” And you’re like “what will you replace it with?” and they respond “Template substitutions! It's all the power of lexicographic scopes, all the power of looping (via recursion), but when you want to express the really complex stuff you need templates that have side effects when substituted, we can give those scary names.” So you give me a sunbeam and a raincloud and I give you back a rainbow. If that's the functional programming idea then logic programming takes the same idea but adds unification and search. The idea is “ok but why do I have to fill in all the parameters to a template before I use it? I should just say “if light shines on a droplet-cloud it makes a rainbow, a sunbeam is a light, a raincloud is a droplet-cloud, hey language, what are all the things that make a rainbow?” Functional programming was based on the function, the template, the “I take these args and produce a structure looking like such-and-so.” Logic programming is based on the Horn clause, “X verbs Y, for some entities X and Y that I maybe know about and some verb that I am being introduced to.” Basic things that logic programming does very well, OOP kind of struggles with. You can kind of understand this if you have written a SQL query. The verbs can be thought of as tables that foreign-key to X and to Y, if you want to write OOP to solve a logic puzzle you have to choose explicit ways to search or brute force... SQL DBs come with B-trees and indexes to solve a lot of these problems. Whereas with Prolog you just write the pattern to match and the new pattern to emit. It's a rather different take on what the building blocks should be.
- crabbone 3y ago
  I was in the same group when I wanted to try Mercury (another Prolog-like language, but with ML-like types). Someone on Mercury's mailing list took pity on me, and told me to just straight up try some Prolog. Prolog, at least the basics, isn't hard at all, and it takes maybe a day to get you to write something that works. Of course, every language has its inconsistencies, dark corners and unexpected turns, and, sometimes some very deep and general pieces of wisdom that aren't on the surface. But, really, if you want to understand any Prolog derivative, the best way I can think about, is to learn some Prolog. It's the most efficient way to the goal. It doesn't really take long.
oldsecondhand 3y ago
> 2. Commutativity. Order of predicates does not change the result. Finally, true logic programming! I'm not sure this is a good selling point. The fact that predicate order matters in Prolog allows performance optimization and more transparent debugging.
- simplify 3y ago
  It's a great one! From a logical perspective, it's ideal for the order of constraints to not affect the outcome. This missing behavior becomes a quirk quite early on when working with Prolog. That said, order of constraints can affect performance. But since reordering doesn't affect outcome, you are free resort them as you wish in effort to optimize for better performance :)

JimmyRuska 3y ago

Racket made a prolog implementation that is currently used in the compiler, or at least I thought I heard that in one of their talks. Might be worth trying, since its model is a language for making languages https://docs.racket-lang.org/datalog/ https://docs.racket-lang.org/datalog/ https://docs.racket-lang.org/racklog/ https://docs.racket-lang.org/racklog/

Blackthorn 3y ago
That looks pretty cool. Whenever I see the words "prolog-style" I always ctrl+f for "cut", and this one passes!

yowlingcat 3y ago

Asking this earnestly and not as a rhetorical question: what do I get from Prolog that I can't get from using SQL? Is it speed, is it ergonomics, is it the ability to do computations that are otherwise intractable? And if there are any such advantages, at what level of complexity of abstraction do they come up, and at which level would I not see the value of using prolog?

4ad 3y ago
I am not sure how you could meaningfully compare Prolog and SQL. Both are declarative languages, but that's where the similarities end. SQL is for interacting with databases, whereas Prolog is, more or less, a language that you can write regular programs in. Perhaps the Prolog terminology of "queries" and "database" gave you the impression it has something to do with databases that store data. It doesn't. The query is over logical terms, and the database is a collection of Prolog facts.
- ngruhn 3y ago
  Both languages are relational, which is fairly unique among programming languages. For example you can define a graph in Prolog like this: edge(1, 2). edge(2, 3). edge(3, 4). These edges are naturally undirected. Similarly, in SQL you can have a table "Edges": +——-+——-+ | 1 | 2 | | 2 | 3 | | 3 | 4 | +——-+——-+ which also imposes no strict direction. In non-relational languages you have to define maps for both directions. However, in Prolog you can easily define something like reachability using recursion: reachable(V, V). reachable(V, W) :- edge(V, U), reachable(U, W). In SQL you would have to join the "Edges" table with itself an unknown number of times. I suspect this is possible somehow but definitely less natural.
  - Epa095 3y ago
    The reachable predicate on your 'naturally undirected edges' treat them as directed;-) I would rather say that your edges are naturally directed, and then you can add a clause to make them undirected.
  - 3y ago

daitangio 3y ago

Erlang first implementation was based on Prolog, which is the mahor reason of its syntax

iot_devs 3y ago

As very long term goal, I want to work on a project like this but on much larger scale. I have a tiny prototype based on Go and soufflé. The overall goal would be to figure out classical error conditions like nill pointers deference. If I can figure out if a pointer will be nil in some execution branch, there is no reason why a computer cannot do the same. However it is very hard work and the part I am currently stuck in is creating a reasonable abstraction level where I can reason (in soufflé) about code and not about an AST. I personally would see this as an human race level upgrades. Imagine feeding your code to a CI that spit back something like: "you will have a panic at line 156 when your input is > 4" Moreover we will be able to check the "real code" starting from main down to all execution paths. Which is much more powerful than current static analysis that usually analyse a single function without considering how the function itself is invoked. Beside the actual implementation difficulties, the other big elephant in the room is the amount of resources needed to run this kind of analysis. (I am less concerned about that as computation resources exploded due to AI and solving SAT is getting faster and faster)

dackerlunghack 3y ago
[dead]
nextaccountic 3y ago
> The overall goal would be to figure out classical error conditions like nill pointers deference. > If I can figure out if a pointer will be nil in some execution branch, there is no reason why a computer cannot do the same. Note, this is called flow-sensitive typing (also called type narrowing) and I think that typescript does it. https://en.wikipedia.org/wiki/Flow-sensitive_typing https://en.wikipedia.org/wiki/Flow-sensitive_typing > I personally would see this as an human race level upgrades. Imagine feeding your code to a CI that spit back something like: "you will have a panic at line 156 when your input is > 4" A model checker can do that! See this https://model-checking.github.io/kani/tutorial-kinds-of-failure.html https://model-checking.github.io/kani/tutorial-kinds-of-fail... Other techniques are also possible https://github.com/viperproject/prusti-dev#quick-example https://github.com/viperproject/prusti-dev#quick-example (Here I could link a lot of things, I just selected two Rust projects to illustrate) This works better if you are able to provide contracts in your API that says which guarantees you provide. Alternatively, asserts are useful too.

throwaway42534 3y ago

Meta develops a system based on similar ideas https://glean.software https://glean.software https://www.youtube.com/watch?v=eFglEyb-KfM&t=4s https://www.youtube.com/watch?v=eFglEyb-KfM&t=4s

forward-slashed 3y ago

Oh, this is great. This article and conversation with Marcelle led me down a rabbit hole of Prolog, Minikanren, and Reasoned Schemer. Not quite out yet. I am thinking about using this idea of Prolog as AST to build an ai-first, reactive IDE. DM me at @eating_entropy on Twitter or email me at joshcho@stanford.edu if you are interested.

conartist6 3y ago
What would the point of any of the formal logic tools be for an "ai-first" IDE? Aren't current IDEs "reactive"?
- anonzzzies 3y ago
  To make software actually better instead of worse when we get worse-than-the-worst code generated by AI's to maintain the coming years?
- forward-slashed 3y ago
  Hey conartist6, thanks for the interest. I'll share once I get something going.

_a_a_a_ 3y ago

> For example when I’m traversing the AST when I’m looking at the node { type: "num", value: 10 }, without doing extra work to go back up the tree I have no way to tell that it belongs to the name “ten”. There's a very easy way to do it, simply add a pointer from the child back up to the parent. It means you can't share AST nodes but it's damn fast and, once debugged, very easy to maintain. I've done this on my personal project and so a question to everyone: when I originally heard of using datalog in compilers it seemed like a very good idea, like it was promising some real value somewhere, but I've seen examples that show you can do trivial type checking – but I do that myself and it's very, very easy. Perhaps I'm looking at this wrong? If I'd used data log then I could knock at a few hundred lines of code scattered around the AST objects, but surely I can do more than that with datalog? I feel I'm missing something, and the crowd here seems knowledgeable so any good pointers (good = simple, because I'm a n00b) would be incredibly helpful! (I am aware of some really advanced stuff like BDDBDDB (https://suif.stanford.edu/bddbddb/ https://suif.stanford.edu/bddbddb/), so advanced I can't even follow it, I'm looking for something between the triviality of type checking and the complexity of full dataflow – the problem here may be a personal one, in that I might need to have to write a dataflow implementation to get a really good 'feel' for it, and then I might 'get' the value of using e.g. datalog, I don't know, but any guidance welcome) this will feed into an actual working project).

vonwoodson 3y ago

I remember the first time I saw a declarative language, I also immediately saw it as an AST. It’s so validating to see it being explored by other people too.

sriram_malhar 3y ago

Here's Niko Matsakis's embeddable logic engine in rust, to be used in the rust compiler's type system. https://github.com/nikomatsakis/chalk-ndm https://github.com/nikomatsakis/chalk-ndm