Language syntax

Grim has a single data structure: symbolic expression trees. A Grim expression is either of the following:

• An atom (atomic expression), being either:
• An integer literal, like 0, 1 or -42.
• A symbol, like x, Pi, Sin or Integral.
• A Unicode string, like "A grim expression: 😀".
• A non-atom (non-atomic expression), having the form f(x1, x2, ..., xn) where f, x1, x2, ..., xn are expressions. The expression f is called the head and x1, x2, ..., xn are called the arguments of the expression.

Example

An entry in Fungrim is represented by a single Grim expression that contains various metadata as well as the main formula as subexpressions. For example:

Entry(ID("22dc6e"),
    Formula(Equal(Fibonacci(n), Add(Fibonacci(Sub(n, 1)), Fibonacci(Sub(n, 2))))),
    Variables(n),
    Assumptions(Element(n, ZZ)))

The formula is the recurrence relation for Fibonacci numbers: $F_{n} = F_{n - 1} + F_{n - 2}$. The metadata in this case specifies the Fungrim entry ID (22dc6e, as a string), lists the free variables in the formula (here the single variable n), and provides conditions on the variables ("assumptions"), in this case $n \in \mathbb{Z}$, such that the formula represents a theorem.

Some points of caution

• Grim distinguishes between the atomic expression f and the non-atomic expression f() where f is called with an empty argument list.
  • TODO: should atoms also have a head (e.g. Integer, Symbol, Text)?
• The head of an expression need not be an atom; f(g(a))(x, y) is valid.
• Symbol names at this time are limited to ASCII Latin letters, digits and underscores, where a digit may not appear as the first character. Since symbol names cannot start with digits or the minus symbol, integer literals can also just be thought of as a distinguished class of symbols.
  • TODO: should probably allow Unicode

String representation and infix operators

Every Grim expression has a canonical string representation, for example Add(3, Mul(-5, x)). The simple syntax ensures that Grim expressions are syntactically valid in common programming languages. Pygrim simply embeds Grim as a domain-specific language within Python, using Python's native integer literals and function call syntax (the necessary symbols have to be created as Python variables).

Because function-call syntax is clumsy for complex arithmetic expressions, we frequently write Grim expressions in an extended syntactical form using infix arithmetic operators (+, -, *, /, **) as well as parentheses for grouping and with use of parentheses and brackets for tuples and lists. Pygrim supports this syntax by overloading the Python-level arithmetic operators (with the operator precedence rules of Python). We need to be careful: for example, we can do x / 3 to construct the Grim expression Div(x, 3) in Python when x is a Grim symbol, but 1 / 3 in Python does not give Div(1, 3).

Symbols available for variables

Symbols reserved for builtin objects (such as Add and ZZ) start with an uppercase letter and are at least two characters long, so all single-letter symbols and all symbols beginning with a lowercase character can be used for variables.

Most Greek letter names are available as symbols and are recognized by the LaTeX converter. There are some exceptions: Gamma is reserved for the gamma function, and Pi is reserved for the constant π; one should use GreekGamma and GreekPi for the Greek capital letters as variables. The alternative spelling lamda / Lamda is used for "lambda" since lambda is a reserved keyword in Python.

As a convenience hack: a symbol name ending with an underscore results in function calls being rendered as subscripts (but watch out as a_ is not the same symbol as a, and the symbols are not implicitly connected.