Dyna – Logic Programming for Machine Learning

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.

> 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.

Chapter 2 of my dissertation covers a lot about the syntax of Dyna https://matthewfl.com/papers/mfl-dissertation.pdf

As refset said in the other comment, In Dyna, terms return values like a function in a functional programming language. Hence, when you write

  word(I)

  word(0) = "Hello".

  foo(X, bar(Y))

In Dyna, we provide square brackets to create structured-terms as both calling the term "bar" and creating the structured-term bar can be useful. E.g. the Prolog expression `foo(X, bar(Y))` would be equivalent to the dyna `foo(X, bar[Y])`.

For the aggregator `max=`, this is looping over the different possible values on the right-hand-side and selecting the value that is the max. Hence in

  phrase(X,I,K) max= phrase(Y,I,K) \* rule(X,Y).

  phrase(X,I,I+1) max= rule(X, word(I)).

My background was high-assurance systems that are provably correct. The field found that designing something for easy analysis and verification was the opposite of for efficiency. So, the solution became to verify the high-level description (formal specifications) first. Then, verify equivalence to a lower-level, efficient form which was probably designed side by side with the other one to make that easier.

Having only read the abstract and example code, I see your work being most valuable as what we called an "executable, spefication language." Those were specs or models close to original, mathematical description that could actually run for exploration and testing. They were also, in theory, easy to modify by the researcher who could focus on intended behavior rather than low-level code.

You are already using transformations to produce low-level implementation. My brainstorm would be to do a bottom-up approach of making common operations on GPU's, in libraries like Jax, and rules about how to integrate them. Then, synethesize combinations of them with constraints on combinations with the system further specializing the components as it went on. (It will be interesting to see what you did.)

I think HLS on ASIC's, Cray's Chapel, and high-level libraries in machine learning show such an approach could make implementations fast enough to test theories on small models. I think someone should build on these concepts trying to connect them to primitives in Chapel or Jax or something already designed to itself synthesize or abstract away many low-level details. Then, implement pieces of common, useful models in it with pre-synthesized implementations.

Shorter version: I think it's neat work.worth further exploration which might accelerate development and validation of ML algorithms even with sub-optimal, runtime performance.

(And I still haven't read the papers. This is just independent brainstorming I do first to see if our ideas are converging any which has its own value.)