Dear Racketeers, We are glad to present you a new differentiable programming language called Landau.
https://gitlab.iaaras.ru/iaaras/landau # Description Landau is a LANguage for Dynamical systems with AUtomatic differentiation. Landau is a Turing-incomplete statically typed domain-specific differentiable language. The Turing incompleteness allows a sophisticated source code analysis and, as a result, an optimized compiled code. Landau's syntax supports functions, compile-time ranged `for` loops, `if`/`else` branching constructions, integer and real variables and arrays, and the ability to manually `discard` calculations where automatic derivatives values are expected to be negligibly small. Despite the restrictions, the language is rich enough to express and differentiate cumbersome paper-equations with practically no effort. ## Simplest code sample ``` const int k = 3 # some constant parameter[k] x0 # Parameters w.r.t which derivatives should be taken real[k * k] func(real[k] x, real[k * k] dxdx0) { x[:] ' x0[:] = dxdx0[:] # Tell the compiler about dx/dx0 Jacobian real[k] f = 2 * sin(x[:]) + x[:] # Do the actual work func[:] = f[:] ' x0[:] # Return the values of df/dx0 Jacobian } ``` ## More examples `spacecraft.dau` [1] is a Landau program for modeling spacecraft movement around a planet. Spacecraft's initial position and velocity, as well as the gravitational parameter of the planet, are supposed to be determined by an external nonlinear optimization method. Derivatives of the right-hand side of the equation w.r.t. the initial state vector and the planet mass are handled by Landau. As soon as you have installed Landau (see Installation below), generating C code should be as simple as ``` $ racket spacecraft.dau -c -extfl Success. The output is written to [path]/spacecraft.c ``` Other code examples are available at [2]. ## Differentiation method Landau uses a hybrid approach to calculating derivatives: symbolic differentiation at the expression level and automatic (forward mode) at the assignation level. ## Implementation The Landau transpiler is built on top of the Racket platform and consists of two main parts: the syntax analyzer and the code generator. The job of the syntax analyzer is to: - unroll all loops into an assignation sequence; - trace dependencies of variables and their derivatives; - check the program for correctness, e.g. catch out-of-range errors. The code generator is capable to emit Racket and ANSI C code. It is possible to use 80-bit floating-point numbers (extended precision) without changing the Landau source. ## Landau advantages Landau facilitates the development of dynamical models used in celestial mechanics and possibly other areas. Landau: - generates highly-efficient C code (or less efficient Racket syntax objects which are useful if you are programming in Racket); - exempts user of C pointer managing trouble and low-level debugging; - allows easy notation of mathematical equations, while also allowing loops and functions; - and, of course, provides first-class automatic derivatives (while you can use Landau without them, too). The Landau-generated C code is portable to Windows, Linux, and MacOS compilers. ## Key decisions There are AD approaches where an initial program is unrolled into assignation sequences (Wengert list) and AD problem is solved in linear algebra formalism. The initial problem is reduced to a sparse linear equations system. Even though there are known lots of sparse matrix algorithms, it is not obvious whether it is a good idea to unroll all loops to a giant sparse matrix. In Landau, we decided to take another code generation approach which preserves the initial program's loops, i.e. a Landau loop is transformed into a C or Racket loop whose body is augmented with a derivative calculation code if needed. Unlike other AD tools, Landau allows to annotate derivatives inside a program to be able to predict the number of nonzero derivatives and reduce machine resources used for Jacobian computation and storage. Other AD tools often do not use annotations and hence, make it impossible to perform radical compile-time optimizations of array's derivatives computations. We chose to use a compression technique that stores only nonzero Jacobian values row by row. The sparsity is handled by packing useful Jacobian elements into smaller arrays and generating mappings from the packed derivative indexes to the original ones and inverse mappings, which map the original indexes to the packed ones. # Development in Landau The model development consists of three stages: 1. Manual model description in Landau language (`model.dau`) 2. Transpiling to ANSI C (code generation `model.c`) 3. Compiling to a shared library for a specific platform (`model.dll`, `model.so`, `model.dylib`) ## Publications - I. Dolgakov, D. Pavlov. “Landau: language for dynamical systems with automatic differentiation”. Zap. Nauch. Sem. POMI 485 (2019) [3] - I. Dolgakov, D. Pavlov. “Using capabilities of Racket to implement a domain-specific language”. Computer Assisted Mathematics 1 (2019) [4] # Installation 1. Download and install Racket. 2. Clone repository: `git clone https://gitlab.iaaras.ru/iaaras/landau.git`. 3. Link Landau as a package: `cd landau/ && raco link landau`. # Configuraiton `config.json`: ``` { // Language to compile .dau file to "target_language": "racket" | "ansi-c", // Whether to use 80-bit floating point "use_extfloat": true | false, // Where to write output .c file, // in case `target_language` is "ansi-c" "output_directory": DIRECTORY_PATH } ``` # Planned improvements ## Syntax - FFI (calling C functions inside a Landau program); - complex numbers; - syntactic sugar for array operations; - multidimensional arrays. ## Core While being close to optimal in terms of computation time, the chosen AD algorithm is not very memory efficient. The main problem is that inverse mapping of a single array cell takes O(maxidx) in space, where maxidx is a maximal index of nonzero derivative for the array element. So a better Jacobian compression algorithm is under consideration. ## Static analysis Unrolling all loops and evaluating all compile-time computable variables is a simple but inefficient approach. We are looking for better ways of performing static syntax analysis. ## Code generation - Generate AVX intrinsic functions for the C backend; - generate unsafe vector operations for the Racket backend. # References [1] https://gitlab.iaaras.ru/iaaras/landau/blob/master/tests/spacecraft.dau [2] https://gitlab.iaaras.ru/iaaras/landau/tree/master/tests [3] <http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=znsl&paperid=6869&option_lang=eng> http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=znsl&paperid=6869&option_lang=en <http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=znsl&paperid=6869&option_lang=eng> g [4] http://cte.eltech.ru/ojs/index.php/cam/article/view/1625 -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/5322b07f-0a8c-4b5d-b006-1f59b47c5008o%40googlegroups.com.
