Skip to content


Repository files navigation


The Dyna programming language built on R-exprs.

Paper about the internals of this system can be found here.

Install Instructions

git clone
cd dyna-R
python -m venv /tmp/dyna
source /tmp/dyna/bin/activate
pip install -r requirements.txt
python develop

# run tests

# start repl
dyna   OR   python -m dyna.repl

Example interactive session with dyna

./dyna   # start dyna

# define finannaci sequence
fib(X) = fib(X - 1) + fib(X - 2) for X > 1.
fib(0) = 0.
fib(1) = 1.

# set fib to be memoized with an unknown default.
# A value will be compute the first time an entry is required
memoize_unk fib/1

# make a query against fib

Operations are derferred when they would cause non-termination

deleteone([X|Xs], Xs, X).
deleteone([X|Xs], [X|Ys], Z) :- deleteone(Xs, Ys, Z).
permute([], []).
permute(As, [Z|Bs]) :- deleteone(As, Rs, Z), permute(Rs, Bs).

# permute works in both modes due to R-exprs
permute([1,2,3], X)

permute(X, [1,2,3])

Dyna-R includes the ability to perform abstract reasoning in some cases

even([X,Y|Z]) :- even(Z).
odd([X|Y]) :- even(Y).
even_odd(X) :- even(X), odd(X).

# run the optimizer on the program to identify that even_odd(X) is empty
# even & odd represent incompatiable recursive "types" where their intersection is empty.


Simplified API

Document for the Python API can be found here.

              (__)    )
              (..)   /|\
             (o_o)  / | \
             ___) \/,-|,-\
           //,-/_\ )  '  '
              (  ( . \_
           gnv `._\(___`.
                '---' _)/

This is an "academic" implementation. There may be bugs in general, though it is surprisingly robust in a lot of cases. Aka, here be dragons.