Quoting Difficulties

In my last post I discussed DSLs for database querying in Clojure. These typically take the form of data structures.

I also discussed how some query languages, like SPARQL and Datomic, use variables in their queries, and that these appear in Clojure as symbols. That post also demonstrated using quoting to embed symbols easily into a structure, and unquoting to use values inside those same structures.

Some of it got messy.

Symbol Reuse

A colleague was recently trying to build SPARQL queries using Flint. This is a library that allows SPARQL queries that look very similar to Datomic queries.

He was trying to programmatically build query fragments that could be appended to each other to form a complete query. Each fragment was generated by functions that returned a small structure that could be added into the query.

In most cases, he could use quoting to return his structure. For instance, the following fragment might be used to find the name of a person who had changed an entity:

[[entity :data/modifiedBy ?person] [?person :data/firstName ?name]]

This is not the final form though, since he wanted to both pass in a value for entity, while also quoting the symbols in his structure.

Using the techniques from the last post, this is relatively straightforward:

(defn modifier-name
 [entity]
 [[entity :data/modifiedBy '?person]
  ['?person :data/firstName '?name]])

However, there are occasions where the entity might be modified more than once, and so multiple names should be returned. This will need a configurable name variable:

(defn modifier-name
 [entity name-var]
 [[entity :data/modifiedBy '?person]
  ['?person :data/firstName name-var]])

This would let a developer call something like:

(concat (modifier-name '?entity '?name1) (modifier-name '?entity '?name2))

(note: There are overlaps between what ?name1 and ?name2 will bind to. This is just for illustration.)

Autogensym

Unfortunately, this has a bug. In both cases, the ?person variable is used, meaning that both ?name1 and ?name2 will always be bound to the same values. One way to address this is to generate a new symbol for the query.

Since we're been using quoting, then a common way to generate symbols is to use a syntactic feature called an autogensym inside a quote. This uses a symbol name with a trailing # character:

(defn modifier-name
 [entity name-var]
 `[[~entity :data/modifiedBy ?person#]
   [?person# :data/firstName ~name-var]])

This version is using syntax quoting, and embedding entity and name-var, as discussed in the previous post.

However, this version has a bug too. The appearance of ?person# in the code tells the Clojure reader to generate a new symbol.

user=> (modifier-name '?entity '?name)
[[?entity :data/modifiedBy ?person__2__auto__]
 [?person__2__auto__ :data/firstName ?name1]]

Each new use of this ?person# expression (in a new context) should result in a new symbol. However, this symbol gets reused when the function gets called again.

user=> (concat (modifier-name '?entity '?name1)
               (modifier-name '?entity '?name2))
([?entity :data/modifiedBy ?person__2__auto__]
 [?person__2__auto__ :data/firstName ?name1]
 [?entity :data/modifiedBy ?person__2__auto__]
 [?person__2__auto__ :data/firstName ?name2])

The symbol ?person__2__auto__ was returned from both calls, because the generation actually occurred when the function was read, not when it was executed.

This is the same issue that was discussed in an Ask Clojure Question. Syntax quoting and autogensyms are most often used in macros, and the scope of a generated value is typically restricted so that any generated symbols cannot interact with each other. The case discussed in that Clojure question was when a macro was recursive. In that case, the symbols generated during recursion were all the same, since they all shared scope.

Our query is not using recursion, but instead it is capturing the name of this symbol and returning it to the calling scope. This means that the scope of the generated name is extended to the calling context, allowing it to interfere with other generated names in that context. i.e. the scope "escaped".

In other words, despite autogensyms being common when quoting expressions (most commonly in macros), they are not appropriate for anything that can escape the current context.

Addressing the issue

One solution to this is to generate a symbol on each execution of the function. This can be done manually, rather than using the autogensym syntax:

(defn modifier-name
 [entity name-var]
 (let [?person (gensym "?person")]
   [[entity :data/modifiedBy ?person]
    [?person :data/firstName name-var]])

This creates a new value every time.

Recap

Using functions to generate fragments of queries can result in conflicting fragments, particularly in graph languages that have variables in their syntax. In these cases, a new variable is needed for each fragment.

Clojure has a facility for creating new variable names easily, called "autogensym". However, the new name is only generated when the code is read, meaning that any function using this construct will always return the same symbol. "Autogensym" can be helpful, but only if the context of the generated symbol can never overlap with the context of another call to the same autogensym.

Query Mess

In the first post I mentioned that macros can simplify a query DSL. The next post will demonstrate this.