Osmarkscalculator

**osmarkscalculator**
Paradigm(s)	Expression rewriting
Designed by	osmarks
Appeared in	2022
Computational class	Probably Turing-complete
Reference implementation	[1]
Influenced by	Computer algebra systems, Lisp
File extension(s)	none

osmarkscalculator is an esolang based on rewrite rules.

Syntax

osmarkscalculator expressions can be numbers (nonnegative integers in base 10), identifiers (made of any sequence of characters not reserved for anything else), operator invocations (parsed using standard infix notation) or function calls (which look like FunctionName[arg1, arg2]). Brackets can be used to alter precedence. Semicolons or newlines act as breaks, which break statements. Standard infix notation is used for operators, with the following precedences:

Precedence table
Level	Operator	Operator
0	0
1	+	-
2	*	/
3	^ (left-associative)
4	#

After parsing, operator invocations are treated as two-argument functions.

Semantics

When given an input expression, osmarkscalculator attempts to transform it into another expression by applying rewrite rules from its rulesets: if the result of this is a "statement" (x=y, PushRuleset[name] or SetStage[stage]) this is then executed (by adding the rule x=y to the ruleset, adding the ruleset to the current stage or setting the current stage of the current ruleset). Rewriting is done in stages: "pre_norm", "norm", "post_norm", "pre_denorm", "denorm" and "post_denorm". There are some rules applied in all stages: the arithmetic operators, Mod and Subst, as well as things like 0*a=0. Normalization (the norm stage) tries to convert powers to multiplication, convert division to negative powers, expand brackets (by applying distributivity), and rewrite subtraction as addition. Denormalization undoes this. Numbers are always represented as 128-bit integers. The last rule to be defined is applied first, so more general rules should generally be defined before specific rules.

Pattern Matching

Pattern matching and thus rule application is defined recursively. A rule is applied if its left hand side (the pattern) matches the input or parts of it, and the bindings generated are then substituted into the right hand side.

Matching rules
Pattern	Input	Result
Number	Number	Matches iff equal value.
Fn1[arguments1...] if Fn1 is associative and match is at top level	Fn2[arguments2...]	Matches iff Fn1 = Fn2 and arguments1 matches some contiguous sublist of arguments2.
Fn1[a, b, c] otherwise	Fn2[a, b, c]	Matches iff Fn1 = Fn2 and a, b, c match a, b, c (generalizes to any number of arguments).
x#Predicate	y	Matches iff x matches y and predicate(s) is (are) satisfied (see below).
Identifier	x	Always matches, unless the LHS identifier has already been bound to something within the current match.
Anything else	Anything else	No match.

Predicates
Predicate	Descripotion
x#Not	Inverts current match success.
x#Ident	Sets match success to false if x is not an identifier.
x#And[a, b, c]	Sets match success to false if x does not match all of a, b, c.
x#Or[a, b, c]	Sets match success to true if x matches any of a, b, c.
x#Gte[y]	Sets match success to false if x is not greater than or equal to y.
x#Eq[a, b, c]	Sets match success to false if a, b, c do not all evaluate equal to each other.

Examples

Recursively defines a factorial function:

Fac[n] = Fac[n-1]*n
Fac[0] = 1
Fac[17]

Expands brackets:

(a+b)*(c+d)*(e+f)*(g+h)

Basic predicate use:

IsEven[x] = 0
IsEven[x#Eq[Mod[x, 2], 0]] = 1
IsEven[3] - IsEven[4]

Simplification:

Negate[a+b] + b

Bracket expansion:

(a+b)^3*(b+c)-d

The built-in definition of derivatives:

SetStage[all]
D[x, x] = 1
D[a#Num, x] = 0
D[f+g, x] = D[f, x] + D[g, x]
D[f*g, x] = D[f, x] * g + D[g, x] * f
D[a#Num*f, x] = a * D[f, x]
PushRuleset[differentiation]

Power

osmarkscalculator is probably Turing-complete, since it looks like it ought to be possible to compile Brainf*** into it by using a nested expression as a tape. However, I do not want to prove this.