4 ms·

Dyna – Logic Programming for Machine Learning

163 points by matteodelabre 1y ago

tomrod 1y ago
Would this be useful in a production system today?
- matthewfl 1y ago
  The focus of this work was a research project. IMO, a mature system would require a several more person years of work. However, there is nothing stopping you from using it in a production system if you find it useful (there is a python, clojure, and java api).
refset 1y ago
> Dyna3 — A new implementation of the Dyna programming language written in Clojure There are some epic looking Clojure namespaces here, e.g. this JIT compiler https://github.com/argolab/dyna3/blob/master/src/clojure/dyna/rexpr_jit_v2.clj https://github.com/argolab/dyna3/blob/master/src/clojure/dyn...
- brokencode 1y ago
  I'd be fascinated to hear about the author's experience using Clojure for something as complex as a compiler. Was the lack of types an issue? Or was the simplicity and flexibility of the language worth the tradeoff?
  - binary132 1y ago
    I believe lisps are commonly thought of as being good for writing compilers, and Clojure has more features than your average lisp.
    - lo_zamoyski 1y ago
      In certain respects, but the lack of static types can become a burden very fast. And compilers are a compelling use case for statically typed languages given the frequency with which constructors can appear.
  - f1shy 1y ago
    Not author, but I made the experience of writing a compiler, linker and assembler for a little programable ASIC. We did it in CL, because we had only 1 month. The big advantage of a lisp for a compiler, is that you don’t need to make a parser: if you accept to follow lisp syntax, you can reuse the reader. For making the linker is helped to have all in structs and lists structures. Each compiled piece of code was a list with actual binary code, where it had prepended the information as symbol name, pointers to where to change for relocation, etc. The dynamic typing (sorry if I’m pedantic, but lisp is typed, even strong typed, but dynamic) played in favor. As a matter of fact, after we did 90% of the work we decided to change the type of some parts of the structures, it was almost no work. Had it been a static typed language, it would had been a MAJOR rewrite. The fact that CL can also be static typed helped with performance, as for some thing we forced long int.
  - matthewfl 1y ago
    Author here. In picking Clojure, there were two main things that I was looking for in a language: compile-time macros and a runtime eval function. The reason for wanting compile time macros is that without them, you essentially create another DSL to generate code in you language of choice (e.g. tablegen and pdll in the llvm project). As such I was mainly considering at LISP-like language for the implementation of dyna3. Clojure's emphasis on immutable data structures also fit nicely with the design for R-exprs. Lack of types in Clojure wasn't an issue in terms of getting things working. However, I did end up getting very annoyed with the runtime speed and quality of the generated code from the Clojure implementation. Features such as `^:dynamic` and `defprotocol` were too slow, so I rolled my own by wrapping a Java class and using macros. I also had to replace Clojure's builtin map with my own implementation of a map for performance-critical code. The R-exprs themselves are implemented using `deftype`, which generates a Java class rather than using maps to hold the relevant data.
matthewfl 1y ago
It's nice to discover my PhD research trending on Hacker news. https://matthewfl.com/phd https://matthewfl.com/phd https://matthewfl.com/papers/mfl-dissertation.pdf https://matthewfl.com/papers/mfl-dissertation.pdf https://github.com/argolab/dyna3 https://github.com/argolab/dyna3 https://www.youtube.com/watch?v=sXRvba2yjY0 https://www.youtube.com/watch?v=sXRvba2yjY0
- YeGoblynQueenne 1y ago
  Can you please explain Dyna? I'm trying to understand it using what I know about Prolog. For example, what does this rule (?) do? phrase(X,I,I+1) max= rule(X, word(I)). What is the 'max=' operator(?). Is phrase/3 an interface to Definite Clause Grammars as in Prolog? How about this one? phrase(X,I,K) max= phrase(Y,I,K) * rule(X,Y). Is the * operator (?) to be interpreted as a multiplication? As a disjunction or other logical operation? If a multiplication, what is it multiplying? Thanks! Edit: I'm struggling with the Fibonacci example. The text says that Dyna 2.0 uses unification "like Prolog" but I can't make head or tails of how the first-order terms in the following rule would unify: fib(N) := fib(N-1) + fib(N-2). It seems that 'N-1' and 'N-2' are meant to be replaced by their values. In that case, when does unification happen? Are the terms evaluated, then their values unified? Obviously those values would (eventually) be constants, so where is the unification happening? Is this something to do with lazy evaluation? Or is unification here only used as a value-passing mechanism, to propagate the value of N through the expression?
  - refset 1y ago
    The dissertation covers extensive details, but on your last point at least it describes: > 2.2.1 Evaluation by Default. One of the major syntactic differences between Dyna and other logic programming languages is that Dyna evaluates an expression in place by default. The reason for this change is that most terms have a meaningful value, much like how a function returns a value in a functional programming language. Conversely, in logic programming languages such as Prolog or Datalog, terms only “return” the value of true.
    - deleted 1y ago
versteegen 1y ago
This language seems quite similar to Scallop [1], which was recently posted to HN [2]. Both are extensions of Datalog to arbitrary semirings, meaning that they generalise assigning merely true or false to relational statements, allowing probabilistic reasoning and more (almost arbitrary tagging of statements). Scallop is further focused on being differentiable and being able to integrate Scallop code into a PyTorch function. Both seem to have quite a bit of work put into them and have JIT compilers (Scallop also has a GPU implementation). I like the sound of "I have further modernized Dyna to support functional programming with lambda closures and embedded domain-specific languages." [3] Going to try it out. [1] https://www.scallop-lang.org/ https://www.scallop-lang.org/ [2] https://news.ycombinator.com/item?id=43443640 https://news.ycombinator.com/item?id=43443640 [3] https://matthewfl.com/research#phd https://matthewfl.com/research#phd
- ProofHouse 1y ago
  Same lineage (weighted/semiring logic programming for ML), but different system. Francis Landau’s work (Dyna) is a term rewriting implementation is of a weighted logic language with bag relational semantics, dynamic programming, and a tracing JIT. Scallop is a Datalog style neurosymbolic language built on provenance semirings with differentiable/relaxed semantics intended for e2e training with NNs. Consider Scallop a variation branch in the lineage optimized for differentiable neurosymbolic learning vs Dyna is a more general weighted logic programming framework with a different execution mode
aeonik 1y ago
I just finished a bit of spelunking in the Clojure Repo of Dyna3, and I got the distinct feeling that I had just stumbled upon an alien artifact from the future. https://github.com/argolab/dyna3 https://github.com/argolab/dyna3
- jdnier 1y ago
  And it has a Python wrapper, https://github.com/argolab/dyna3/tree/master/dyna_python_module https://github.com/argolab/dyna3/tree/master/dyna_python_mod....
sieabahlpark 1y ago
[dead]

163 points by matteodelabre 1y ago

tomrod 1y ago

Would this be useful in a production system today?

matthewfl 1y ago
The focus of this work was a research project. IMO, a mature system would require a several more person years of work. However, there is nothing stopping you from using it in a production system if you find it useful (there is a python, clojure, and java api).

refset 1y ago

> Dyna3 — A new implementation of the Dyna programming language written in Clojure There are some epic looking Clojure namespaces here, e.g. this JIT compiler https://github.com/argolab/dyna3/blob/master/src/clojure/dyna/rexpr_jit_v2.clj https://github.com/argolab/dyna3/blob/master/src/clojure/dyn...

brokencode 1y ago
I'd be fascinated to hear about the author's experience using Clojure for something as complex as a compiler. Was the lack of types an issue? Or was the simplicity and flexibility of the language worth the tradeoff?
- binary132 1y ago
  I believe lisps are commonly thought of as being good for writing compilers, and Clojure has more features than your average lisp.
  - lo_zamoyski 1y ago
    In certain respects, but the lack of static types can become a burden very fast. And compilers are a compelling use case for statically typed languages given the frequency with which constructors can appear.
- f1shy 1y ago
  Not author, but I made the experience of writing a compiler, linker and assembler for a little programable ASIC. We did it in CL, because we had only 1 month. The big advantage of a lisp for a compiler, is that you don’t need to make a parser: if you accept to follow lisp syntax, you can reuse the reader. For making the linker is helped to have all in structs and lists structures. Each compiled piece of code was a list with actual binary code, where it had prepended the information as symbol name, pointers to where to change for relocation, etc. The dynamic typing (sorry if I’m pedantic, but lisp is typed, even strong typed, but dynamic) played in favor. As a matter of fact, after we did 90% of the work we decided to change the type of some parts of the structures, it was almost no work. Had it been a static typed language, it would had been a MAJOR rewrite. The fact that CL can also be static typed helped with performance, as for some thing we forced long int.
- matthewfl 1y ago
  Author here. In picking Clojure, there were two main things that I was looking for in a language: compile-time macros and a runtime eval function. The reason for wanting compile time macros is that without them, you essentially create another DSL to generate code in you language of choice (e.g. tablegen and pdll in the llvm project). As such I was mainly considering at LISP-like language for the implementation of dyna3. Clojure's emphasis on immutable data structures also fit nicely with the design for R-exprs. Lack of types in Clojure wasn't an issue in terms of getting things working. However, I did end up getting very annoyed with the runtime speed and quality of the generated code from the Clojure implementation. Features such as `^:dynamic` and `defprotocol` were too slow, so I rolled my own by wrapping a Java class and using macros. I also had to replace Clojure's builtin map with my own implementation of a map for performance-critical code. The R-exprs themselves are implemented using `deftype`, which generates a Java class rather than using maps to hold the relevant data.

matthewfl 1y ago

It's nice to discover my PhD research trending on Hacker news. https://matthewfl.com/phd https://matthewfl.com/phd https://matthewfl.com/papers/mfl-dissertation.pdf https://matthewfl.com/papers/mfl-dissertation.pdf https://github.com/argolab/dyna3 https://github.com/argolab/dyna3 https://www.youtube.com/watch?v=sXRvba2yjY0 https://www.youtube.com/watch?v=sXRvba2yjY0

YeGoblynQueenne 1y ago
Can you please explain Dyna? I'm trying to understand it using what I know about Prolog. For example, what does this rule (?) do? phrase(X,I,I+1) max= rule(X, word(I)). What is the 'max=' operator(?). Is phrase/3 an interface to Definite Clause Grammars as in Prolog? How about this one? phrase(X,I,K) max= phrase(Y,I,K) * rule(X,Y). Is the * operator (?) to be interpreted as a multiplication? As a disjunction or other logical operation? If a multiplication, what is it multiplying? Thanks! Edit: I'm struggling with the Fibonacci example. The text says that Dyna 2.0 uses unification "like Prolog" but I can't make head or tails of how the first-order terms in the following rule would unify: fib(N) := fib(N-1) + fib(N-2). It seems that 'N-1' and 'N-2' are meant to be replaced by their values. In that case, when does unification happen? Are the terms evaluated, then their values unified? Obviously those values would (eventually) be constants, so where is the unification happening? Is this something to do with lazy evaluation? Or is unification here only used as a value-passing mechanism, to propagate the value of N through the expression?
- refset 1y ago
  The dissertation covers extensive details, but on your last point at least it describes: > 2.2.1 Evaluation by Default. One of the major syntactic differences between Dyna and other logic programming languages is that Dyna evaluates an expression in place by default. The reason for this change is that most terms have a meaningful value, much like how a function returns a value in a functional programming language. Conversely, in logic programming languages such as Prolog or Datalog, terms only “return” the value of true.
  - deleted 1y ago

versteegen 1y ago

This language seems quite similar to Scallop [1], which was recently posted to HN [2]. Both are extensions of Datalog to arbitrary semirings, meaning that they generalise assigning merely true or false to relational statements, allowing probabilistic reasoning and more (almost arbitrary tagging of statements). Scallop is further focused on being differentiable and being able to integrate Scallop code into a PyTorch function. Both seem to have quite a bit of work put into them and have JIT compilers (Scallop also has a GPU implementation). I like the sound of "I have further modernized Dyna to support functional programming with lambda closures and embedded domain-specific languages." [3] Going to try it out. [1] https://www.scallop-lang.org/ https://www.scallop-lang.org/ [2] https://news.ycombinator.com/item?id=43443640 https://news.ycombinator.com/item?id=43443640 [3] https://matthewfl.com/research#phd https://matthewfl.com/research#phd

ProofHouse 1y ago
Same lineage (weighted/semiring logic programming for ML), but different system. Francis Landau’s work (Dyna) is a term rewriting implementation is of a weighted logic language with bag relational semantics, dynamic programming, and a tracing JIT. Scallop is a Datalog style neurosymbolic language built on provenance semirings with differentiable/relaxed semantics intended for e2e training with NNs. Consider Scallop a variation branch in the lineage optimized for differentiable neurosymbolic learning vs Dyna is a more general weighted logic programming framework with a different execution mode

aeonik 1y ago

I just finished a bit of spelunking in the Clojure Repo of Dyna3, and I got the distinct feeling that I had just stumbled upon an alien artifact from the future. https://github.com/argolab/dyna3 https://github.com/argolab/dyna3

jdnier 1y ago
And it has a Python wrapper, https://github.com/argolab/dyna3/tree/master/dyna_python_module https://github.com/argolab/dyna3/tree/master/dyna_python_mod....

sieabahlpark 1y ago

[dead]