A Weighted, Declarative, Logic Programming Language Dyna
About the Dyna Programming Language
Dyna is a programming language designed by and for machine learning researchers. Dyna builds on the paradigm of logic programming languages such as Datalog and Prolog. However, Dyna goes much further in that it allows for flexible execution orders and for rules in the program to be "weighted". This means that we can efficiently express complicated programs in a few lines of code without having to worry about how the program will execute and only focus on what we want computed. For example, we can write our matrix multiplication in a single line of code, as well as the fibonacci sequence, CKY parsing, and even an "infinite" neural network in a few lines of code as shown below.
% Dyna rule for multiplying the matrix `a` and `b` together c(I,K) += a(I,J) * b(J,K). % The fibonacci sequence fib(N) := fib(N-1) + fib(N-2). % recursive step fib(0) := 0. % override recursive step for 0 and 1 fib(1) := 1. % CKY Parsing phrase(X,I,K) max= phrase(Y,I,J) * phrase(Z,J,K) * rule(X,Y,Z). % binary CKY rule phrase(X,I,K) max= phrase(Y,I,K) * rule(X,Y). % uniary CKY rule phrase(X,I,I+1) max= rule(X, word(I)). % terminal rule % A Neural Network defined in terms of edges sigma(X) = 1/(1+exp(-X)). % define sigmoid function out(J) = sigma(in(J)). % apply sigmoid function in(J) += out(I) * edge(I,J). % vector-matrix product loss += (out(J) - target(J))**2. % L2 loss edge(input(X,Y),hidden(X+DX,Y+DY)) = weight(DX,DY). % define edges in terms of weight matrix weight(DX,DY) := random(-1,1) for DX:-4..4, DY:-4..4. % random initialization for matrix % To see more example Dyna programs, please checkout our research papers.
History of the Dyna Project
The Dyna project was initially started in 2004 as an umbrella project to make a programming language for Machine Learning (ML) researchers. Most algorithms that ML researchers implement are expressible in a few lines of math. In the process of researching new algorithms, researchers often have to iterate many times. This means that they revise the mathematical concept of their algorithm and then recode their program to match. The Dyna project hopes to help this process by reducing the distance between mathematical concepts and executable code.
The discrepancy between non-executable mathematical notation and executable programs was the central motivation for the Dyna project and led to the development of Dyna 1.0 (Paper 1, Paper 2) Dyna 1.0 extended Datalog by replacing the boolean semiring used in logic programming to allow any semiring. In other words, this meant that Dyna 1.0 was a notation for expressing and running dynamic programs. As such, Dyna 1.0 was successfully used in a number of research papers.
On the heels of Dyna 1.0 success, Dyna 2.0 was proposed to rectify many of the limitations of Dyna 1.0 (Paper). Dyna 1.0 requires everything to use the same semiring, Dyna 2.0 removes this restriction, instead, it has functions. Dyna 1.0 is a dialect of Datalog and as such, requires all terms to only contain ground values. This allowed the Dyna 1.0 compiler to generate programs that loop over the entire domain of an expression---much like a scan of a database table. Dyna 2.0 has no such restriction. Instead, Dyna 2.0 allows for variables in the program to remain free. Dyna 2.0 performs unification similar to Prolog, where expressions like a(X)=a(Y) unifies X and Y together without knowing the value of X or Y . Dyna 2.0 also supports both lazy expressions allowing for expressions like X+Y=Z to remain "unevaluated". Dyna 2.0 can also eagerly compute and memoize any expression to avoid recomputing the same expression many times. Dyna 2.0 also introduced a prototype-based inheritance (dynabases) which is useful for building larger programs.
Ongoing Research about Dyna
Relational Algebra and Term Rewriting to build a Flexible, Complete Implementation — The execution of a Dyna program is non-trivial and can not be implemented using the same techniques used to implement Datalog and Prolog engines. In this research, we are looking into new ways in which declarative programming languages can be implemented using term-rewriting on top of a relational algebra which can represent a Dyna program.
— The execution of a Dyna program is non-trivial and can not be implemented using the same techniques used to implement Datalog and Prolog engines. In this research, we are looking into new ways in which declarative programming languages can be implemented using term-rewriting on top of a relational algebra which can represent a Dyna program. Reinforcement Learning used to find an Optimal Execution Strategy — One of the major differences between Dyna compared to other programming languages is that Dyna does not guarantee the order in which expressions are evaluated. This, in turn, provides us with opportunities to "rearrange" to program to improve the program's runtime. In this work, we are investigating how reinforcement learning and heuristic search strategies can be used to automatically make a program more efficient.
Select Published Research Papers
Additional talks about Dyna can be found here.
Downloads / Different Implementations of Dyna