@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.

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

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.

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

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.

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

Thanks! It is more or less the thing I told @roman.belov, but it is much better to hear it from you.

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

@roman.belov ☝️