Expression parser

I’m trying to port a C package to Julia. The C program uses the “tinyexpr” package to parse expressions provided by the user. For example, a bit of input might look like this:

x = 3
y = 4
z = 2 + 3*x - exp(-y)

The x and y variables get redefined over and over as the program runs, and z has to keep up.

It should be much easier to do in Julia than in C, because of Julia’s metaprogramming features. But I don’t want to evaluate these expressions in the context of the Julia program itself. The x and y values in the user’s code should not conflict with variables of the same name in my own Julia code. Is there a way to evaluate expressions in a context that is isolated from the surrounding Julia program?

Can’t you just ask the user to provide a Julia function (since you’re doing a Julia package, people will have to use Julia) : z(x,y) = 2 + 3*x - exp(-y) ?

E.g. in DifferentialEquations.jl :

using DifferentialEquations
f(u,p,t) = 1.01*u
u0 = 1/2
tspan = (0.0,1.0)
prob = ODEProblem(f,u0,tspan)
1 Like
julia> module UserCode end
Main.UserCode

julia> const UC = Main.UserCode
Main.UserCode

julia> include_string(UC, "x = 3; y = 4; z(x, y) = 2 + 3x - exp(-y)")
z (generic function with 1 method)

julia> x0, y0 = UC.x, UC.y
(3, 4)

julia> UC.z(x0, y0)
10.981684361111267

julia> z
ERROR: UndefVarError: z not defined

This is flexible but dangerous, as it allows the user to run arbitrary code. See this post for other approaches: Evaluate expression in function

1 Like

Thanks for the feedback.

I’m writing an application, not a package, and I can’t change the input syntax, because that is already in use by the C version. Your comments convince me that it’s too dangerous to run user input through Julia’s eval function. I’ll either write my own or wrap the C version.

If your fixed input syntax is also valid Julia syntax, then you can use Julia’s parser without having to use eval:

julia> Meta.parse("z = 2 + 3*x - exp(-y)")
:(z = (2 + 3x) - exp(-y))

julia> dump(Meta.parse("z = 2 + 3*x - exp(-y)"))
Expr
  head: Symbol =
  args: Array{Any}((2,))
    1: Symbol z
    2: Expr
      head: Symbol call
      args: Array{Any}((3,))
        1: Symbol -
        2: Expr
          head: Symbol call
          args: Array{Any}((3,))
            1: Symbol +
            2: Int64 2
            3: Expr
              head: Symbol call
              args: Array{Any}((3,))
                1: Symbol *
                2: Int64 3
                3: Symbol x
        3: Expr
          head: Symbol call
          args: Array{Any}((2,))
            1: Symbol exp
            2: Expr
              head: Symbol call
              args: Array{Any}((2,))
                1: Symbol -
                2: Symbol y

You can then write your own code to manipulate the Exprs returned by Meta.parse, essentially replacing tinyexpr with Julia’s built-in parser. This is a bit of a hack, since the Julia parser will parse all valid Julia syntax, which might not make sense in your context, but it could end up working well.

5 Likes

I’ll give that a try.

Thanks.

Thanks to you all for your suggestions. That is certainly the easiest parser I ever wrote. To parse an expression, I can now do this:

using Main.MyEval
m = Dict( :x => 1.0, :y => 2.0, :z = 3.0)

myeval(Meta.parse("x + y/z", m))

which returns 1.6667. Here’s the implementation:

module MyEval

export myeval

"""
myeval(e::Union{Expr,Symbol,Number}, map::Dict{Symbol,Float64})

Evaluate the result produced by Meta.parse, looking up the values of
user-defined variables in "map". Argument "e" is a Union, because
Meta.parse can produce values of type Expr, Symbol, or Number.
"""
function myeval(e::Union{Expr,Symbol,Number}, map::Dict{Symbol,Float64})
    try
        return f(e, map)
    catch ex
        println("Can't parse \"$e\"")
        rethrow(ex)
    end
end    

# Look up symbol and return value, or throw.
function f(s::Symbol, map::Dict{Symbol,Float64})
    if haskey(map, s)
        return map[s]
    else
        throw(UndefVarError(s))
    end
end    

# Numbers are converted to type Float64.
function f(x::Number, map::Dict{Symbol,Float64})
    return Float64(x)
end    

# To parse an expression, convert the head to a singleton
# type, so that Julia can dispatch on that type.
function f(e::Expr, map::Dict{Symbol,Float64})
    return f(Val(e.head), e.args, map)
end

# Call the function named in args[1]
function f(::Val{:call}, args, map::Dict{Symbol,Float64})
    return f(Val(args[1]), args[2:end], map)
end

# Addition
function f(::Val{:+}, args, map::Dict{Symbol,Float64})
    x = 0.0
    for arg ∈ args
        x += f(arg, map)
    end
    return x
end

# Subtraction and negation
function f(::Val{:-}, args, map::Dict{Symbol,Float64})
    len = length(args)
    if len == 1
        return -f(args[1], map)
    else
        return f(args[1], map) - f(args[2], map)
    end
end    

# Multiplication
function f(::Val{:*}, args, map::Dict{Symbol,Float64})
    x = 1.0
    for arg ∈ args
        x *= f(arg, map)
    end
    return x
end    

# Division
function f(::Val{:/}, args, map::Dict{Symbol,Float64})
    return f(args[1], map) / f(args[2], map)
end    
end # module MyEval
3 Likes