Someone interested in PL theory might want to chec...

# mathematics

[breandan]

Someone interested in PL theory might want to check out this stuff:

• Describing the syntax of programming languages using conjunctive and Boolean grammars
• Formal languages over GF(2)
One thing we were trying to do with Kotlingrad was build a mathematically sound representation between functions and fields. The direct way is (1) to define Fun<X>: Field<X> where X is a member of some algebra over the reals equipped with the usual operators (when you apply an operator, it is evaluated and you get X back). Another way is (2) to treat the function as a member of a field whose elements are themselves functions, e.g. Fun<X>: Field<Fun<X>>, and instead of returning X, applying an operator instead returns Fun<X> which can be later evaluated by calling invoke(...), returning X (so X and Fun<X> are both fields).

It turns out the second representation comes from finite field theory, which has important implications for expression parsing and language design. It would be useful to understand this connection more deeply.

[altavir]

We actually done something like thant in kmath with Expression algebras and AST representations. It would be nice to join efforts on this one. The major limitation is that when you add a function to the algebra, you also need to add the function to all algebras using it. There are ways to fix this problem with KEEP-176, but without it the only solution to add those manually or use dynamic ast resolution. You can try to look through experimental adv-exp branch of kmath: https://github.com/mipt-npm/kmath/tree/adv-expr/kmath-ast

[altavir]

My current idea is to provide universality by generating AST (I call it MST, because it is rather limited AST for mathematics) in runtime and then use it to compute expressions or values (including auto-diffs) in runtime on specific algebra. It is not quite safe, because one can't know in advance which special functions are present in the algebra. On the other hand, one can do beautiful things with an MST, including runtime bytecode generation like the one done by @Iaroslav Postovalov. A limited type safety is provided by the context