ANN: Landau
44 views
Skip to first unread message
Ivan Dolgakov
Jul 12, 2020, 10:45:15 PM7/12/20
to Racket Users
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
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
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
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
[4] http://cte.eltech.ru/ojs/index.php/cam/article/view/1625
Reply all
Reply to author
Forward
0 new messages