Fast way to evaluate arithmetic and logical expressions at run time

#1

I have some expressions generated at run time, for example, :(3.4 - 1.0 > 1.2 - 1.4^2) and :(2.3^4 - 3.4^3 + 1.2^3). They do not involve any symbols, they just deal with numbers. Is there any efficient way to evaluate them at run time? (eval is not an option). I tried JuliaInterpreter.@interpret with no success because I would need some sort of interpret function and not a macro.

#2

How are they being generated at runtime? You need to provide more context.

You mentioned something about “user input” in another thread. What is the UI? Why can’t the user just pass a function directly?

1 Like
#3

Why isn’t eval an option ? That’s kind of what it’s for. Alternatively you might want to use a package like this one which is designed to manipulate formal mathematical expressions.

1 Like
#4

The user provides conditionals to specify a set of points in a 3d space, something like: select(points, :(x>1)) or select(points, :(y+x==4)). Due to numerical errors the expressions are modified at run time to include a tolerance. Thus they become: :(x>1+tol) and :(abs(y+x-4)<tol). Later for each conditional a function is defined (using eval) and finally invoked for all point coordinates.
An input function would be ideal instead of expressions, however it would be cumbersome for the user to think about tolerances each time a selection is made.

I know that eval provides performance issues and defining a function at run time triggers recompilation. That is why I am looking for an alternative approach.

#5

I found that Base.Cartesian.exprresolve_conditional() almost does what I want and it seems to be very fast. It can evaluate expressions like :(3.0 < 4.0) but not :(3.0 + 1.0 < 5.0)

#6

I would do something like this: the user specifies a closure (you can make this easier with a macro that transforms

@something x > 1

to

x -> x > 1

etc), your implementation defines a wrapper type

struct Tolerant{T}
    x::T
end

Base.(<)(x::Tolerant, y) = x < y + tol

and wraps all the inputs before calling that closure.

1 Like
#7

That’s interesting. Thus may be I can do something like

select(points, @makefun(x==1 && y>1) )

that is transformed to

select(points, (x,y,tol) -> (abs(x-1)<tol && y>1+tol) )
#8

Close, but as I said, don’t add tol at the expression level, let dispatch take care of it. It is much easier to implement, debug, and maintain.

#9

Great!, then I think I have to define a set of arithmetic operators:

Base.(+)(x::Tolerant, y) = x.x + y
Base.(-)(x::Tolerant, y) = x.x - y
Base.(*)(x::Tolerant, y) = x.x * y
Base.(<)(x::Tolerant, y) = x.x < y + tol
Base.(>)(x::Tolerant, y) = x.x > y - tol
and so on...
#10

Precisely. This has the advantage that the user cannot “escape” your mini-DSL, for methods that you did not define.

You can also simplify the generation of the above with a macro.

1 Like
#11

Thanks a lot @Tamas_Papp and thanks all for the advice!

#12

Why not just have the user specify inequality constraints of the form f(x)<=0 and/or equality constraints of the form h(x)==0 — that is, the user supplies the functions f and/or h as ordinary functions (not expressions). Then you can internally check f(x) <= tol and abs(h(x))<= tol as desired.

This way, the user can define arbitrary Julia functions as complicated as they want, not restricted to symbolic expressions that you know how to analyze.

Furthermore, instead of using a heuristic tolerance, you could alternatively use interval arithmetic: pass an instance of an interval type for x, and then you can check rigorously whether the output may possibly satisfy the constraints up to roundoff errors.

2 Likes
#13

That’s a nice solution also. Thanks a lot :wink: