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.

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