# Parsing selection syntax

**URL:** <https://discourse.julialang.org/t/parsing-selection-syntax/43632>\
**Category:** General Usage\
**Created:** [July 24, 2020, 7:03pm UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632 "2020-07-24T19:03:57Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2020, 7:03pm UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/1 "2020-07-24T19:03:57Z")

</div>

My question is not exclusively about Julia, but Julia is one language in which I see a possible solution.

What I want is to implement a natural syntax to select items from a list (actually atoms from a molecular system), using something like:

```julia
selection = select("index < 1000 and not water and (name C or name N)",atoms)

```

where `atoms` is a vector of elements of type `atom`, which might be something like:

```julia
struct Atom
    name 
    index
    element
    coordinates
end

```

and, of course, we could define functions like `iswater(atom)` to deal with with the `not water` condition, for example.

I thought that I could simply parse such a statement “index \< …” converting it to a Julia-code, with  
something like

```julia
function convert(selection)
  expr = ""
  for keyword in split(selection)
    if keyword == "index"
      expr = expr*" atom.index "
    elseif keyword == "and"
      expr = expr*" && " 
    elseif keyword == "not"
      expr = expr*" ! "
    elseif keyword == "water"
      expr = expr*" iswater(x) "
    else
      expr = expr*" $keyword "
    end
  end
  return expr
end

```

such that

```julia
convert("index < 100 and not water")

```

returns

```julia
" atom.index < 100 && ! iswater(x) "

```

From that, I could use something like:

```julia
function select(atoms,selection)
  expr = convert(selection)
  selection = Vector{Atoms}(undef,0)
  for atom in atoms
    if eval(Meta.parse(expr))
      append(selection,atom)
    end
  end
  return selection
end
# Obs: actually this function does not work, because the 
# interpolation of the atom variable on "eval" fails, but
# I need yet to understand that. But probably the idea of what
# I aim to obtain is clear.

```

So, my general question is: is this strategy (of generating meta-codes) a reasonable choice to tackle this problem? Writing an actual interpreter of the user-provided syntax seems too complicated.

The more specific question, if the approach is reasonable, is how to evaluate the generated expression for each element of an array, as it seems to work for a single element, but when inside a loop or function, the variable is no longer recognized:

```julia
julia> expr = :(x < 1);
julia> y = [0, 1];
julia> for x in y
         eval(expr)
       end
ERROR: UndefVarError: x not defined

```

(a third possibility is that someone knows of a package that does that already, I could not find one).

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [July 24, 2020, 7:48pm UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/2 "2020-07-24T19:48:43Z")

</div>

Metaprogramming is not magic. You should not try to use `eval` for this. It’ll be strictly slower than other methods.

In fact, there’s nothing magical. You always need to do the same amount of work and the only thing julia may help here is syntax.

The first question for you is that what **is** your input. Does it have to be a random string that is only known at runtime, for example if you are prompting the user for input from a REPL? If yes then you should just go with however you do it in other language. You may try to encode the parsed result in a type to speed up repeated execution but that’s the extend you can do.

If the string is not free-formed, but rather is always constant at construction or with limited templating syntax on top, then you should just make the user construct the code, as function callback or other types encoding the result, directly, and this is exactly what you can do in most other languages as well. The only difference julia/metaprogramming can make is to write a macro/string macro so that you can do your own parsing to generate such an object.

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [July 24, 2020, 7:58pm UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/3 "2020-07-24T19:58:47Z")

</div>

this gives off pandas.query vibe… (which I dislike, whenever I need to re-visit or re-use them it’s always a mess).  
[https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.query.html](https://pandas.pydata.org/pandas-docs/stable/reference/api/pandas.DataFrame.query.html)

---

<div class="post-metadata">

**Author:** ![tisztamo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tisztamo/32/16200_2.png) [@tisztamo](https://discourse.julialang.org/u/tisztamo)\
**Post date:** [July 24, 2020, 8:04pm UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/4 "2020-07-24T20:04:28Z")

</div>

Maybe helpful: [Write You A Query Language · MLStyle.jl](https://thautwarm.github.io/MLStyle.jl/v0.3.1/tutorials/query-lang/)

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2020, 9:24pm UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/5 "2020-07-24T21:24:42Z")

</div>

The input is variable, of course, it will be an user input, which will be parsed from an input file.

The user is not expected to know anything about programming, he/she might not even notice that the package is written in Julia. What I want is to reproduce the same selection syntax of popular packages for molecular simulations.

The selection function does not need to very fast, that is far from being the computationally expensive part of the code.

What I think that meta-programing can give in this case is not speed, it just a very simple way to translate the syntax of a selection into a code to be evaluated in Julia.

So, to be clearer:

The function `convert` above, translates the syntax `index < 100 and not water`, which is familiar to the user, to the corresponding Julia code for the same conditional: `atom.index < 100 && ! iswater(atom)`.

In principle, I can write a file with the following function, given that result:

```julia
f -> atom -> atom.index < 100 && ! iswater(atom)

```

My code could continue simply including that file, and aftewards the selection of the atoms could be done with

```julia
selection = filter(f,atoms)

```

The meta-programing part of the story is to avoid writing a file to disk and having to include that file afterwards.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 24, 2020, 9:29pm UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/6 "2020-07-24T21:29:18Z")

</div>

Maybe I can ask a very simple question:

Given the string

`s = "x > 1"`.

Is there a simple way to use this string to define a function, such as:

```julia
f = x -> x > 1

```

I tried different forms of interpolation, but I am a quite lost in the documentation of the meta-programing part. Maybe that is not even what meta-programing is thought for, and a simpler way to do that exists, of course not involving writing and including files from disk.

EDIT: This works:

```julia
s = "x > 1"
f = eval(Meta.parse("x -> "*s))
f(2)
true

```

Such that it is possible to use the code above with:

```julia
selection_expression = convert("index < 100 and not water")

```

if it returns, by adding `atom ->` as the first string and `Meta.parse(expr)` at the end, the `expr`:

```julia
:(atom -> atom.index < 100 && ! iswater(atom))

```

With that it is possible to define, in the REPL, the selection function:

```julia
f = eval(expr)

```

and use it in

```julia
filter(f,atoms)

```

I found some threads warning about the use of eval with expressions provided by users, which can result very unexpected results, which is true. So I will keep searching for a better solution.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 25, 2020, 1:23am UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/7 "2020-07-25T01:23:16Z")

</div>

The final result is the one below, used in a simple example where I use the selection to compute the center of the coordinates of a subset of atoms of an atom list.

Actually I like the result. It is fast wherever that matters, which is in the function that actually does the computations.

If anyone thinks that I am doing something highly non-recommendable, I will be glad to get the advice.

```julia

# Structure with its properties
struct Atom
  index
  element
  coor
end

# One specific function that might be used for selection
function ismetal(atom :: Atom)
  if atom.element == "Fe"
    true
  else
    false
  end
end

# Function that converts the natural expression to the Julia conditional
function select_expr(selection :: String)
  expr = "atom -> "
  for keyword in split(selection)
    if keyword == "index"
      expr = expr*" atom.index "
    elseif keyword == "and"
      expr = expr*" && "
    elseif keyword == "not"
      expr = expr*" ! "
    elseif keyword == "metal"
      expr = expr*" ismetal(atom) "
    else
      expr = expr*" $keyword "
    end
  end
  return Meta.parse(expr)
end

# And this converts the above to the function
select(string) = eval(select_expr(string))

# Example of use: a function that computes the center of coordinates
# of the selected atoms
function center(atoms,selection_function)
  center = zeros(3)
  nsel = 0
  for atom in atoms
    if selection_function(atom)
      center[1] = center[1] + atom.coor[1]
      center[2] = center[2] + atom.coor[2]
      center[3] = center[3] + atom.coor[3]
      nsel = nsel + 1
    end
  end
  @. center = center / nsel
  return center
end

# Let us define the atoms:
atoms = Vector{Atom}(undef,100)
for i in 1:100
  atoms[i] = Atom(i,rand(["Fe","C"]),rand(3))
end

# Choose some of them with the natural syntax (actually defines
# the function)
sel = select("index < 80 and not metal")

# What is passed to the function that computes the center is the
# function, thus this will be fast
c = center(atoms,sel)

println(c)

```

I reinforce that, in my case, I will not change the selection function many times, and this is not important for the speed of the code in general. I only need a parser for a natural syntax, not a very efficient code to define selections. That is why this solution is acceptable for me. I still have no idea how I would have to manage this without meta-programing.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [July 25, 2020, 2:46am UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/8 "2020-07-25T02:46:34Z")

</div>

> [@lmiq](#):
>
> What I think that meta-programing can give in this case is not speed, it just a very simple way to translate the syntax of a selection into a code to be evaluated in Julia.

No that’s not what metaprogramming is for. This will one of the worst way to do it.

> [@lmiq](#):
>
> The meta-programing part of the story is to avoid writing a file to disk and having to include that file afterwards.

That is just as bad and will give you exactly the error you get otherwise. Writing to a file and include is nothinng more than `include_string` or parse and eval that code.

> [@lmiq](#):
>
> Is there a simple way to use this string to define a function, such as:

That’s parse and eval by definition.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [July 25, 2020, 2:51am UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/9 "2020-07-25T02:51:39Z")

</div>

> [@lmiq](#):
>
> I reinforce that, in my case, I will not change the selection function many times, and this is not important for the speed of the code in general. I only need a parser for a natural syntax, not a very efficient code to define selections. That is why this solution is acceptable for me. I still have no idea how I would have to manage this without meta-programing.

Those are all good reasons that you should not use this. The single good thing about creating a function like this is if you actually care about how fast it evaluate many times later. This is also not really any more metaprograming than what you’ll do in any other language. The better way to do this, same as what all other language would use, is to simply do the thing instead emitting a string to do anything. You are generating a straight line expression, meaning that you basically only need to keep track of a few values as you evaluate the string.

---

<div class="post-metadata">

**Author:** ![CameronBieganek](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cameronbieganek/32/6915_2.png) [@CameronBieganek](https://discourse.julialang.org/u/CameronBieganek)\
**Post date:** [July 25, 2020, 5:10am UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/10 "2020-07-25T05:10:50Z")

</div>

I think the approach you are taking will be difficult to generalize to a more complicated query grammar. Here’s an approach that avoids metaprogramming.

The idea is to build up an Abstract Syntax Tree (AST). But I don’t mean a Julia AST, I mean an AST for your query language. The AST for your query language can be represented by nested tuples.

### Atom code

```julia
struct Atom
	index::Int
	iswater::Bool
	isiron::Bool
end

iswater(a::Atom) = a.iswater
isiron(a::Atom) = a.isiron

a = Atom(50, true, false)
b = Atom(200, false, false)
c = Atom(200, false, true)

```

### Example query to parse

```julia
s = "index < 100 or not water and not iron"

```

### Parsing function

The following function `parse_query` parses a query string into a nested tuple that represents the AST of your query. Each tuple represents an [S-expression](https://en.wikipedia.org/wiki/S-expression) where the first argument of the tuple is a function and the remaining arguments of the tuple are the arguments of that function.

A couple things to note:

- `parse_query` is a recursive function, because the query could have arbitrarily nested `and`s, `or`s, and `not`s.
- The if-else block is ordered from lowest operator precedence to highest operator precedence, with `"or"` being the lowest precedence and function application (like `iswater`) the highest precedence.

```julia
function parse_query(s)
    if occursin("or", s)
        (|, parse_query.(split(s, "or"))...)
    elseif occursin("and", s)
        (&, parse_query.(split(s, "and"))...)
    elseif occursin("not", s)
        rest = match(r".*not(.*)", s)[1]
        (!, parse_query(rest))
    elseif occursin("index <", s)
        k = parse(Int, match(r"index < ([0-9]*)", s)[1])
        a -> a.index < k
    elseif occursin("water", s)
        iswater
    elseif occursin("iron", s)
        isiron
    else
        error("Parsing error!")
    end
end

```

Let’s run this on the query string and see what we get:

```julia
julia> q = parse_query(s)
(|, var"#5#6"{Int64}(100), (&, (!, iswater), (!, isiron)))

```

So we see that we get our AST as a nested tuple! Now we need a way to apply the AST to an atom.

### Apply parsed query to atom

```julia
function apply_query(q, a)
	if !(q isa Tuple)
		q(a)
	else
		f, args = Iterators.peel(q)
		f(apply_query.(args, Ref(a))...)
	end
end

```

This function recursively calls the first argument of each tuple with the remaining arguments of the tuple. When `apply_query` gets down to a point in the AST where `q` is not a tuple, it assumes that `q` is a function (e.g., either `iswater`, `isiron`, or `a -> a.index < k`) and it calls that function on the atom `a`.

Now let’s apply our parsed query to an atom:

```julia
julia> apply_query(q, a)
true

julia> apply_query(q, b)
true

julia> apply_query(q, c)
false

```

It works, and all without using any metaprogramming!

EDIT:  
I had my operator precedence wrong in the initial post, so I’ve fixed that.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 25, 2020, 10:11pm UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/11 "2020-07-25T22:11:53Z")

</div>

Thank you very much. I have to study to understand exactly how that works, and particularly how to deal with parenthesis, but it is clear what I have to do.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 26, 2020, 4:24am UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/12 "2020-07-26T04:24:04Z")

</div>

> [@lmiq](#):
>
> particularly how to deal with parenthesis

If acceptable with the users, [S-expressions](https://en.wikipedia.org/wiki/S-expression) may be easiest to parse.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 27, 2020, 1:05am UTC](https://discourse.julialang.org/t/parsing-selection-syntax/43632/13 "2020-07-27T01:05:07Z")

</div>

Just to mention that I found out now that the “Chemfiles.jl” package has a pretty powerful selection syntax, which is quite similar to what I want:

[http://chemfiles.org/Chemfiles.jl/latest/tutorials/#Using-selections](http://chemfiles.org/Chemfiles.jl/latest/tutorials/#Using-selections)

Thus, I almost certainly will go with that.