# How to write a simple interpreter / DSL with Wolfram Language?

I am specifically trying to write an interpreter for Mathematica predicates to MongoDB aggregation stages, but I wanted to phrase the question a bit more generically because I can see many times one might want to write translate their Mathematica code to something else and it seems the processing should be fairly re-usable.

Here's a simple (wrong) start:

"something" == 2 && "somethingelse" == 5 /.
And[x___] :> <|"$and" -> {x}|> // ExportString[#, "JSON"] &  which produces { "$and":[
false
]
}


It should eventually produce something like this, though obviously I have not even made it to processing each term yet.

{
"$and":[ { "something":2 }, { "somethingelse":5 } ] }  I've tried several variants of HoldAll, etc but I can't seem to prevent it from immediately evaluating "something"==2 and returning false. So one thing is assistance with holding/inactivating the expression. The other that I know I will hit is managing complexity, even once I get this And[] version working I will be then trying to handle combinations of ORs and "element of" and so on -- if anyone has done something like this and has suggestions for how to structure it so it doesn't become a rat's nest I would gladly take any advice. EDIT Adding a few more examples: 70 < "score" < 90 || "views" >= 1000  to { "$or":[
{
"score":{
"$gt":70, "$lt":90
},
"views":{
"$gte":1000 } } ] }  • I may post some answer tomorrow, but for now, you can look how SQL expression compiler has been written for relational databases functionality, to get an idea: <<GeneralUtilities; <<Databases; PrintDefinitions @DatabasesDatabaseDBExprToAST;. You can use this function as, for example: DatabasesDatabase$DBInPlaceEvaluation = False; DatabasesDatabaseDBExprToAST[ "something" == 2 && "somethingelse" == 5 && Max["yetSomethingElse"] > 3]. The resulting astSymbol is an inert symbol representing AST node of resulting code representation, which you can then convert to e.g. JSON May 22 '21 at 22:24
• Ok, I see how that works and I guess as the old car repair manuals would say, "simply reverse the procedure" (i.e., a function with pattern match for each leaf node type etc.). I did try to just do the simple replacement thing (after dropping Max for now) and I got <|"$and" -> {Association["something" -> 2], Association["somethingelse" -> 5], Association["$gt" -> {"yetSomethingElse", 3}]}|> which looks right, but ExportJSON says it can't export Association (but if I just type an Association it does export it, something weird going on.). Thank you for the pointer!
– Dan
May 22 '21 at 22:50
• Sure thing. It would be helpful if you could include perhaps 3-5 (or more) additional simple query examples in your question, which would be representative for what you need. That would allow to post an answer with some toy interpreter which would show the general structure. May 23 '21 at 1:33

#### The current status of this answer

I intend to return back to this very exciting question with a better answer, when I have it, but for now there will be something here to get you started.

## General aspects of WL DSL creation

### The main steps in creating a WL DSL

There are a few steps in WL DSL creation which seem to be universal and applicable to most cases:

• Identify syntactic primitives and their mapping (these are primitives that syntactically compose. This typically concerns expressions)
• Identify expression - building primitives in target language (MongoDB query language in this case)
• Identify WL counterparts for these primitives (the mapping)
• Add / introduce missing WL counterparts as some new symbols or expressions (symbols may be existing symbols or new ones if none of the existing ones fits)
• Identify semantic primitives and their mapping (these are primitives which define semantics. They are different and usually higher-level / larger building blocks. This typically concerns what can be called "operations", and possibly their interaction with expressions)
• Identify semantic primitives in the target language

• Identify their WL counterparts and the mapping

• Note that this part in general is non-trivial, since the mapping in general will be between sub-trees of the AST in source (WL) and target languages.

• Note also that in some cases, such mapping may be non-local, in the sense that entire AST will be needed for the source language, in order to determine the transform to the target one.

• Identify necessary AST / tree transformations

• Design the custom type system / identify type mapping
• This step is optional, but often desirable or required, particularly if DSL is going to be compiled rather than interpreted
• Here, one should identify the mapping between core WL types and target language types, and possibly introduce custom WL types to match those target types, for which WL does not have direct counterparts
• Implement WL expression parser / compiler to the target language
• In the simplest case, it can be done directly
• In more complex cases (which is the general situation), one may need intermediate AST / inert code representation
• Often, this would also involve type checks / inference
• In some cases, one may want to also implement a symbolic optimizer, which would convert a generic output of the compiler to simpler forms for certain special cases.

### The main problems / hardest parts

#### Using sensible WL constructs

One important thing to keep in mind is that, while the WL DSL is not intended to be evaluated directly by WL evaluator (but rather to be compiled or interpreted), it is best to design it such that its syntax and semantics make sense for WL.

One example that I like, for this aspect, is the introduction of EntityFunction in the Entity framework. While it is a general construct, its introduction was motivated by the needs of SQL / relational database functionality development. We had a choice of how to represent SQL expressions in WL. We could've used just inert expressions, perhaps wrapped in some holding wrapper. But EntityFunction was capturing exactly, what that expression was from WL viewpoint. It was both function-like and property-like. It made it clear that the expression is bound to certain row of a (real or derived / virtual) table (or entire table in the case of aggregation). By introducing EntityFunction, we made the connection to WL's functional composition explicit, and also had a very natural way to express correlated subqueries, join conditions and other similar tasks.

#### WL vs. target language semantics support - fighting the language impedance mismatch

Perhaps the most problematic thing in constructing the DSL is to actually find the best set of WL primitives, which would semantically combine well together, in the sense that they would

• Make sense in WL semantically, for all or most of those combinations
• Cover the vast majority of important use cases in the target language
• Cover also the use cases that WL users would expect to work from WL-side viewpoint

The key point here is the combinatory nature of the chosen primitives. If they make sense in isolation, they should also work in combinations.

It is usually hard to cater to both sets of cases, and one has to choose, which of the two has higher priority. From a practical viewpoint, one often has to bias in favor of the target system / language typical workflows. If this is stretched too far though (and one can be tempted to, since this is simpler), then the result would be a WL driver for a given system (MongoDB here), not a DSL. From a WL perspective, that may of course mean a less seamless / lower level integration with the rest of WL.

OTOH, pushing too much in the direction of supporting the usual WL semantics may make the DSL less useful for a large number of practically important cases, for which WL alone does not have primitives to exactly express the semantics of those cases / workflows in the target language / system. To give one example, within the confines of Entity framework, one can't currently get direct access to raw UNION, UNION ALL, INTERSECT operators in SQL - essentially because Entity framework lacks (intentionally) explicit projection operator, and the semantics of Intersection, Union and Complement on sets of entities is more complicated than the corresponding raw SQL operations - while in some cases the users may want that exact functionality (for the record, within Entity framework, now one may be able to use EmbeddedSQLEntityClass to work around that particular limitation).

This is generally a hard design problem. One possible solution is to introduce two layers. One is lower-level and much closely following the semantics of the target language, while the other is higher-level, built on top of the first one (or, if we talk about languages, compiled into it), and follows more closely the semantics of WL. Such split will not magically solve all impedance mismatch problems, but may at least simplify the problem by providing two different APIs for two class of problems and / or two types of users.

#### Actual implementation and efficient / readable code generation

The other thing which can be hard, is to actually implement the transformation, that would compile the source code into the target code, which would not be too inefficient and / or ugly. The good thing is that WL's powerful symbolic capabilities seriously simplify the task of writing symbolic code optimizers, which can process the resulting inert symbolic representation of target language code AST, and perform various optimizations.

## Expression parsers

### What are expression parsers

Expression parsers are a category of WL functions (built-in or user-defined), which decompose and / or transform input expressions / code, in possibly non-trivial ways. The defining feature of expression parsers is that they typically descend into an expression recursively, being careful to not evaluate its parts prematurely (or at all).

### Advantages with respect to ReplaceAll / ReplaceRepeated

Expression parsers are a general solution which works well for problems, that require complex expression transformations. They become necessary when simple strategies, based on finding a set of replacement rules that can be globally applied to an entire expression (possibly repeatedly), break down (which has been also mentioned in the question).

The main advantage of expression parsers is that they operate locally, and therefore are in general far more secure, while replacement rules are applied to an entire expression, and may match incorrectly. The other danger of globally applied rules is that they may apply in the wrong order. At the same time, expression parsers are still using rules and rule-based machinery, so they can take full advantage of the pattern matcher.

The second big advantage of expression parsers is that it is far easier to control evaluation there, than for "global" rule application approach. And even when one introduces an evaluation leak in an expression parser (which in practice happens often enough), that leak will also be local, and thus typically will be much easier to find and fix.

The last significant advantage of expression parsers to mention here is easy extensibility. And again, the key is locality of application of any given rule or set of rules. The point is, that adding new rules / extending the parser, is typically a very straightforward process, where rules interact weakly, and as long as some minimal thought is given, new rules are unlikely to break something non-locally. One surely still can break things, but such local bugs will be relatively easy to find and fix. This is not the case for "global" rule application with ReplaceAll / ReplaceRepeated, where one can have pretty hard-to-find non-local regressions when extending the rule set.

### Examples of expression parsers

The aforementioned in comments DatabasesDatabaseDBExprToAST function is a very good example of an expression parser (which in this particular case converts a subset of WL expressions into an intermediate inert symbolic representation for subsequent SQL generation). Some other examples of simpler expression parsers I could find off hand are 1, 2, 3, 4, 5 (I apologize to all those authors, whose posts I wasn't able to recall, since all these links happen to point to my posts - for a trivial reason that I remember them. All are welcome to add to this list).

### A simple concrete example

A typical setup for an expression parser is to not use Replace and / or ReplaceAll, to globally transform expression. Instead, it typically descends recursively into an expression, going from top (main expression) to bottom (parts and sub-parts). The simplest way to do that is to use a HoldAll symbol as a main parser / function.

Here is, for example, a simple serializer for WL expressions, which is an expression parser:

ClearAll[toRules]
SetAttributes[toRules, HoldAll]

toRules[expr_ /; AtomQ[Unevaluated[expr]]] :=

toRules[expr_] := Throw[$Failed, toRules]  For example: {toRules[For[i = 1; t = x, i < 10, i++, Print[t]]]} // ExportString[#, "JSON"] & (* { "For":{ "CompoundExpression":{ "Set":{ "Symbol":"i", "Integer":"1" }, "Set":{ "Symbol":"t", "Symbol":"x" } }, "Less":{ "Symbol":"i", "Integer":"10" }, "Increment":{ "Symbol":"i" }, "Print":{ "Symbol":"t" } } } *)  (this is actually a string, I am not showing string form with escape characters). This simple expression parser has most of the important ingredients of a typical expression parser: • The transition from expression to subexpressions often involves Map[parser, Unevaluated[{parts}] • The atoms are treated differently • One has to be careful to avoid "evaluation leaks" (that is, premature evaluation of parts of an expression being decomposed). This is often achieved using Unevaluated, but in more complex cases also other tools and idioms for working with unevaluated code are useful. • The catchall definition should somehow report an error in the case of an unparseable expression that didn't match all the other rules. Such errors should not pass silently. The only thing it lacks is a bunch of special cases / rules, added before more general ones, to do something special for special types of input / (sub)expressions - this is very typical for expression parsers (see also the links I gave above, for more examples). ## The case at hand - simplest direct implementation ### Notes For the case at hand, that is, WL DSL for MongoDB aggregation stages, there are a number of things that complicate the problem. Most or all of them are related to the semantics of MongoDB aggregation. In a sense, it is simpler (design-wise) to implement a general case - which is aggregation, not find(), and then write an optimizer which would simplify the generated MongoDB query for certain special cases. But since this is significantly more work and also more code, I will follow a technically simpler route and implement a much more limited spec, for now - which would be a subset of the .find() filtering spec (excluding in particular $expr spec), not a spec for .aggregate() stages. The advantage is that the code is small and simple. The downsides are that a very limited subset of valid filter expressions can be used, and that I will not be able to illustrate harder design / implementation challenges, because they will only become apparent for a more complete implementation / coverage.

I will also not use an intermediate inert code representation (IR), which will most definitely be necessary for a more "real" thing. The main advantage of IR is that it allows to perform multiple passes and more complex code tree transformations in a simpler and more transparent way, and completely without fear of uncontrolled (sub)expression evaluations and evaluation leaks.

As mentioned at the start of this post, I will revisit this later if / when I have a more complete implementation that would illustrate these aspects.

For simplicity, we will restrict ourselves to expressions, which can be built from field expressions (such as F["someField"]), literals (numbers, strings) logical binary comparison operators, and standard logical operators And, Or and Not. Moreover, we will not allow comparisons between different fields, since that would require $expr spec, that we are not prepared to implement right now (this last condition I do not enforce in the implementation, but the generated code will simply be wrong in the case of comparison between two fields). Following one of the steps described above, we should identify all syntactic primitives. Most are obvious for our very limited subset of allowed expressions, but one extra thing we will need is to change the DSL's syntax, to avoid expressions like 70 < "score" < 90 || "views" >= 1000  because such expressions are, while legit, semantically meaningless in WL. Instead, we will introduce an inert symbol (we will call it F, for "field"), that will be wrapped around the field names. So, the above query would become 70 < F["score"] < 90 || F["views"] >= 1000  It may well be that the more complete design would dictate an introduction of some analog of EntityFunction with a bound variable (which would represent the "current" document), where this expression may look like e.g. MongoDocumentFunction[doc, 70 < doc["score"] < 90 || doc["views"] >= 1000]  but for now, the expression version with F will suffice. ### Implementation Without further ado, here is a simple implementation of a very restricted MongoDB .find() method filter spec: $$operatorTranslations = <| And -> "$$and", Or -> "$$or", Equal -> "$$eq", Unequal -> "$$ne", Less -> "$$lt", Greater -> "$$gt", LessEqual -> "$$lte", GreaterEqual -> "$gte"
|>;

ClearAll[CompileMongoQuery, compileMQ]
SetAttributes[{CompileMongoQuery, compileMQ}, HoldAll]

compileMQ[(h: And | Or)[args___]] :=
{$operatorTranslations[h] -> Map[compileMQ, Unevaluated @ {args}]} compileMQ[Not[arg_]] := {"$not" -> compileMQ[arg]}

compileMQ[F[fieldName_String] == rhs_] := {fieldName -> compileMQ[rhs]}

compileMQ[lhs_ == F[fieldName_String]] := {fieldName -> compileMQ[lhs]}

compileMQ[
(oper: Unequal | Less | LessEqual | Greater | GreaterEqual)[F[fieldName_String], rhs_]
] :=
{fieldName -> {$operatorTranslations[oper] -> compileMQ[rhs]}} compileMQ[ (oper: Equal | Unequal | Less | LessEqual | Greater | GreaterEqual)[lhs_, f:(F[_String])] ] := With[{ o = Replace[oper, { Less -> Greater, Greater -> Less, GreaterEqual -> LessEqual, LessEqual -> GreaterEqual }] }, compileMQ[o[f, lhs]] ] compileMQ[ (oper: Equal | Unequal | Less | LessEqual | Greater | GreaterEqual)[ lhs_, m: F[fieldName_String], rhs_ ] ] := GroupBy[ {compileMQ[oper[lhs, m]], compileMQ[oper[m, rhs]]}, First @* First -> Last @* First, Catenate ] compileMQ[F[fieldName_String]] := fieldName compileMQ[a_] /; AtomQ[Unevaluated[a]] := a compileMQ[expr_] := Return[$Failed, CompileMongoQuery]

CompileMongoQuery[expr_] := # & @ compileMQ[expr]


where the main work is done inside an expression parser compileMQ, whereas CompileMongoQuery is the public function. The 2-argument Return, used here to bail early in the case of an error, is explained in this excellent post (a somewhat less exotic alternative would've been to throw an exception in compileMQ and catch it in CompileMongoQuery).

### Examples

Some examples

The simplest possible example

CompileMongoQuery[F["a"] > 1]//ExportString[#,"JSON"]&

(*
{
"a":{
"$gt":1 } } *)  First example from the question CompileMongoQuery[ F["something"]==2 && F["somethingelse"]==5 ]//ExportString[#,"JSON"]& (* { "$and":[
{
"something":2
},
{
"somethingelse":5
}
]
}
*)


The second example from the question

CompileMongoQuery[
70 < F["score"]  < 90 || F["views"] >= 1000
]//ExportString[#,"JSON"]&

(*
{
"$$or":[ { "score":{ "gt":70, "lt":90 } }, { "views":{ "$$gte":1000
}
}
]
}
*)


### Remarks

This is certainly a very limited implementation. If one tries to extend it, one will very soon hit a few obstacles. Some of them come from the shortcuts taken here (such as the lack of intermediate representation), while others are inherent in MongoDB query language, in the sense that one should probably start directly with full syntax / feature set, available for the MongoDB aggregation framework, and then reduce the set for .find() method. And here I even didn't come to support the full \$expr spec - which would've still been more narrow, than the full aggregation spec.

Such design / implementation strategy would also have other advantages. For example, in the above toy implementation, there is a rule for ternary form of operators such as Greater, Less, GreaterEqual, LessEqual, with a field in between literal values. I have included that rule to be able to tackle the second example in the question. Such rule would not be necessary in the better implementation, in the sense that it would not be independent. It would rather be reduced to, e.g., And[low < F[name], F[name] < high], which would then be compiled normally. At the end, an optimizer would look at generated code, and reduce it back to a simpler form. This would allow to avoid certain redundancy and decrease the chance of bugs.

## Summary

In this answer, I tried to provide a very basic illustration of how WL DSL can be implemented, and also mention some general ideas and steps that are typical. Some of the most interesting and important aspects which I didn't cover, include

• Introducing intermediate inert code representation
• Types and type checks
• Proper error reporting (so that the user would know exactly what part of the query contains an error)
• Introducing and implementing non-trivial primitives and code tree transformations
• Developing an optimizer for the generated code / query

I hope to return to these topics in the future, if / when I have a more complete implementation. OTOH, the post is already pretty long, and complete coverage of all these aspects would definitely not sit well with the M SE Q/A format.