https://kotlinlang.org logo
Join Slack
Powered by
<@U0BA5R9KL> We are in a process of adding AST fun...
# mathematics
a
@breandan We are in a process of adding AST functionality to kmath: https://github.com/mipt-npm/kmath/tree/adv-expr/kmath-ast/src/commonMain/kotlin/scientifik/kmath/ast (inspired by a great contribution by @Iaroslav Postovalov). In KotlinGrad you are probably using something for AST representation. Could you reference tha place in the code and any comments if you have them? I also wonder if we can connect kmath and kotlingrad via AST. We will be able to generate computable expressions from AST for any Algebras and it is possible in some cases to decompile existing expressions to AST.
👍 4
b
This is a high level description of how we implemented it: https://github.com/breandan/kotlingrad#algebraic-data-types I recently found out this a fairly common pattern called the interpreter pattern: https://en.m.wikipedia.org/wiki/Interpreter_pattern Here is our current implementation of function evaluation: https://github.com/breandan/kotlingrad/blob/b306e634d71df311c6bf3447e883e554ff0aee67/core/src/main/kotlin/edu/umontreal/kotlingrad/experimental/Scalar.kt#L280 I have some other comments about normalization and lambda calculus but maybe take a look and let me know if something is unclear first
I think our current implementation could be improved quite a bit, I’m trying to figure out how to remove the 
with(Precision){...}
context and match the type conversion semantics of Java/Kotlin. It would be nice if Kotlin allowed import on demand from objects, but we’re going to have to figure out some way around that. The interface between Kotlin numerical types and the KG DSL is very messy right now, and requires wrapping everything in a numerical context.
This context holds the wrapping and unwrapping logic for type conversion. It is pretty brittle and should be replaced by something more flexible: https://github.com/breandan/kotlingrad/blob/b306e634d71df311c6bf3447e883e554ff0aee67/core/src/main/kotlin/edu/umontreal/kotlingrad/experimental/Scalar.kt#L400
Open to ideas how this should be done
There is no explicit syntax tree, we directly construct a DAG using operator overloading. It performs subgraph substitution whenever the invoke operator is called with a binding. This either expands the graph (if variable substitution) or collapses the graph under evaluation
a
Thanks for the explanation. As you know, we were doing the same in kmath, but right now I am thinking about two major points: implicit interoperability between algrbras and string parsers. Both require an ability to call algebra methods dynamically. There are also very nice features we need to keep in mind: 1. implicit implementation substitution in jupyter notebook (I am going to write an article about that after the recording of the lection by @roman.belov is out). There are very interesting posibilites for kotlingrad with that feature. 2. The dynamic ASM-based optimization done by @Iaroslav Postovalov. It requires at least some dynamic features.
K 3
I am not sure yet, but it seems like dynamic AST manypulation could give us a way to perform some nice runtime optimizations like replacing the boxing algebra by non-boxing one during expression evaluation. Also it should be possible to dynamically replace regular expression by an AD one.
As for numerical contexts, I do not think they are available. The only way I see is emulating something like emulation of file-level or package-level recievers, so you load a package with appropriate extensions. Like @Peter Klimai done here: https://github.com/mipt-npm/kmath/tree/dev/kmath-for-real
👍 1
b
I really think there are good opportunities for staged compilation with these kinds of eDSLs. Although it is tempting to go the Arrow/Jetpack compose route and implement special semantics as a compiler plugin or notebook extension, I prefer to work inside the host language as an ordinary library and do everything at runtime. Sometimes it introduces additional complexity when the language does not directly support some semantics, but I believe it saves confusion in the long run
a
I completely agree. My current position is to do a language-based solution and used staged compilation and other features to substitute implementation and improve performance in crytical places.
By the way, It would be nice if you could explain how staged compilation could benefit kotlingrad since the DS team was really interested in potential applications.
b
This paper has a pretty good explanation of multistage programming using Java as an example: https://sci-hub.tw/https://doi.org/10.1007/978-3-662-44202-9_16 Basically, as your host program runs, nothing "happens" -- it just accumulates eDSL code into some data structure (e.g. stack, queue, AST DAG). At periodic intervals, you compile down an "intermediate representation" with some optimizations (e.g. constant propagation, common subexpression elimination) and maybe specialize it to another architecture (outputting e.g. CUDA, webasm). Then at some predetermined time, you execute the whole chunk at once. You could also do this for each line of code (in which case, it's just an interpreter) but the execution of the eDSL does not necessarily need to follow the program counter of the host program. The benefit is mainly performance -- instead of carrying around the original data structure and executing exactly what the user wrote, you're translating the eDSL code into some specialized machine code on the fly. There's been lots of progress in making these things run fast, at close to native speeds. I guess the benefit for Kotlingrad is that it could leverage the GPU. There's been some discussion about it here: https://github.com/breandan/kotlingrad/issues/8
a
Thanks! It is more or less the thing I told @roman.belov, but it is much better to hear it from you.
b
This is another good resource if you're familiar with ML syntax, I guess Kotlin is kind of like ML http://ocamllabs.io/iocamljs/staging.html
I wrote a little summary of our staging design and evaluation criteria: https://github.com/breandan/kotlingrad#multi-stage-programming
a
@roman.belov ☝️
5 Views
Open in Slack
PreviousNext
Powered by