dds: A Home-made Toolkit for Discrete Dynamical Systems in Racket
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Sergiu Ivanov 906d339508 README: Update the strategy for conversion to Typed Racket. 12 hours ago
example Minor updates to some figures. 6 months ago
scribblings utils.scrbl: Add the note about Typed Racket. 12 hours ago
LICENSE Add the GNU GPL licence file. 2 years ago README: Update the strategy for conversion to Typed Racket. 12 hours ago Add a code block for opening the documentation. 1 day ago
functions.rkt functions: Always use named test-cases in tests. 2 years ago
generic.rkt generic: Use collect-by-key/sets to collect the labels for state graphs. 2 years ago
info.rkt info.rkt: List all package dependencies. 12 hours ago
networks.rkt sbn-interaction-graph: Use zero-edges and declare it in the contract. 6 months ago
rs.rkt rs: Add pretty-print-reduced-state-graph. 1 year ago
utils.rkt utils: Add Variable and VariableMapping. 12 hours ago

dds: A Home-made Toolkit for Discrete Dynamical Systems in Racket

This is a toolkit for playing with various discrete dynamical systems in Racket. A discrete dynamical system is a system which evolves from a discrete state to some other discrete states (many or one). The systems are discrete in the sense that we can identify successive states with no other states in between. Equivalently, the phase state of the system is discrete (and is often called the state graph). These constraints imply the possibility of associating discrete, possibly branching timelines to any evolution of the system.

DISCLAIMER: I develop this toolkit as a support for my research on discrete dynamical systems. The primary objective for this framework is to fit my approach to these systems. Essentially, this framework should fit to the "shape of my mind", which is not necessarily the same as yours.

Currently, the toolkit includes the following files:

  • generic.rkt: The generic interface for a discrete dynamical system, with functions for constructing state graphs.

  • utils.rkt: Misc utility functions.

  • networks.rkt: Implements network-based models, which generalise Boolean networks, threshold Boolean automata networks, multivalued networks, etc.

  • rs.rkt: Implements reaction systems, a variant of set rewriting.

The toolkit is designed with Emacs Org-mode interoperability in mind. The file example/ explains the features available for interaction with Org-mode.


Here is my current roadmap for this toolkit, in order. The first element is what I am currently working on. The degree of certainty that I work on the subsequent items decreases with their position in the list.

TODO Convert dds to Typed Racket

Rewriting dds with Typed Racket will be a major refactoring, consisting in the following 3 phases which will happen more or less in parallel:

  • define types, add type signatures, add types for functions I import from graph;

  • transfer the comments from the source files to Scribble documentation;

  • redefine the generic interface for dynamics, which is currently in generics.

I plan to implement the new dynamics interface as a classes, since Typed Racket can now type classes. I didn't really like generics: they are quite cumbersome, and I think I can do more with classes.

People on Racket Users suggested using structures with fields containing functions, but it does not seem to get me to my goal of having type-level methods/functions.

The order in which I will convert the modules:

  1. utils

  2. functions

  3. dynamics (currently generics)

  4. networks

  5. rs

I will convert the modules one by one by first creating a typed section (a submodule) and re-exporting its functions together with the untyped functions. I will then move the functions one by one from the untyped section to the typed section. When the untyped section is empty, I will convert the language of the entire module to Typed Racket and remove the submodule.

TODO Implement a shorter syntax for defining Boolean functions

Right now, this is how one defines the Boolean function:

(define (update-go st)
(or (and (not :Go) :new-x) (and :Go :old-x))))

It would be nice and probably not too difficult to implement a macro allowing for a syntax like the following one:

(define-pbf my-pbf (or (and (not :Go) :new-x) (and :Go :old-x)))

TODO Implement monotone?

monotone? would verify whether a given Boolean function is monotone according to the definition in the book Boolean Functions: Theory, Algorithms, and Applications by Crama and Hammer.

TODO Submit update-graph to stchang

TODO Split networks into general networks and threshold Boolean networks

TODO Implement the BN → RS conversion

TODO Implement the minimisation of TBF/SBF

TODO Contribute to Racket

  • Make sequence-filter allow multivalued sequences, provided the arity of the predicate is consistent with the arity of the sequence.

  • Add a sequence->hash function that accepts a multivalued sequence of keys and values (exactly like what in-hash produces) and copies them into a hash table.

TODO Test network inference with Racklog