Evaluate expression with local variables

Question

I'm writing a genetic program in order to test the fitness of randomly generated expressions. Shown here is the function to generate the expression as well a the main function. DIV and GT are defined elsewhere in the code:

function create_single_full_tree(depth, fs, ts)                                                                                                                                         
"""                                                                                                                                                                                 
Creates a single AST with full depth                                                                                                                                                
Inputs                                                                                                                                                                              
    depth   Current depth of tree. Initially called from main() with max depth                                                                                                      
    fs      Function Set - Array of allowed functions                                                                                                                               
    ts      Terminal Set - Array of allowed terminal values                                                                                                                         
Output                                                                                                                                                                              
    Full AST of typeof()==Expr                                                                                                                                                      
"""                                                                                                                                                                                 

# If we are at the bottom                                                                                                                                                           
if depth == 1                                                                                                                                                                       
    # End of tree, return function with two terminal nodes                                                                                                                          
    return Expr(:call, fs[rand(1:length(fs))], ts[rand(1:length(ts))], ts[rand(1:length(ts))])                                                                                      
else                                                                                                                                                                                
    # Not end of expression, recurively go back through and create functions for each new node                                                                                      
    return Expr(:call, fs[rand(1:length(fs))], create_single_full_tree(depth-1, fs, ts), create_single_full_tree(depth-1, fs, ts))                                                  
end                                                                                                                                                                                 
end                                                                                                                                                                                     

function main()                                                                                                                                                                         
    """                                                                                                                                                                                 
    Main function                                                                                                                                                                       
    """                                                                                                                                                                                 

    # Define functional and terminal sets                                                                                                                                               
    fs = [:+, :-, :DIV, :GT]                                                                                                                                                            
    ts = [:x, :v, -1]                                                                                                                                                                   
    # Create the tree                                                                                                                                                                   
    ast = create_single_full_tree(4, fs, ts)                                                                                                                                            
    #println(typeof(ast))                                                                                                                                                               
    #println(ast)                                                                                                                                                                       
    #println(dump(ast))                                                                                                                                                                                                                                                                                 
    x = 1                                                                                                                                                                               
    v = 1                                                                                                                                                                               
    eval(ast)  # Error out unless x and v are globals                                                                                                                                                                  
end                                                                                                                                                                                     
main()

I am generating a random expression based on certain allowed functions and variables. As seen in the code, the expression can only have symbols x and v, as well as the value -1. I will need to test the expression with a variety of x and v values; here I am just using x=1 and v=1 to test the code.

The expression is being returned correctly, however, eval() can only be used with global variables, so it will error out when run unless I declare x and v to be global (ERROR: LoadError: UndefVarError: x not defined). I would like to avoid globals if possible. Is there a better way to generate and evaluate these generated expressions with locally defined variables?

Answer 1

Thanks Arda for the thorough response! This helped, but part of me thinks there may be a better way to do this as it seems too roundabout. Since I am writing a genetic program, I will need to create 500 of these ASTs, all with random functions and terminals from a set of allowed functions and terminals (fs and ts in the code). I will also need to test each function with 20 different values of x and v.

In order to accomplish this with the information you have given, I have come up with the following macro:

macro create_function(defs)                                                                                       
        for name in eval(defs)                                                                                    
        ex = quote                                                                                                
            function $(Symbol(name))(x,v)                                                                         
                fs = [:+, :-, :DIV, :GT]                                                                          
                ts = [x,v,-1]                                                                                     
                return create_single_full_tree(4, fs, ts)                                                         
            end                                                                                                   
        end                                                                                                       
        eval(ex)                                                                                                  
    end                                                                                                           
end

I can then supply a list of 500 random function names in my main() function, such as ["func1, func2, func3,.....". Which I can eval with any x and v values in my main function. This has solved my issue, however, this seems to be a very roundabout way of doing this, and may make it difficult to evolve each AST with each iteration.

Answer 2

In the Metaprogramming part of the Julia documentation, there is a sentence under the eval() and effects section which says

Every module has its own eval() function that evaluates expressions in its global scope.

Similarly, the REPL help ?eval will give you, on Julia 0.6.2, the following help:

Evaluate an expression in the given module and return the result. Every Module (except those defined with baremodule) has its own 1-argument definition of eval, which evaluates expressions in that module.

I assume, you are working in the Main module in your example. That's why you need to have the globals defined there. For your problem, you can use macros and interpolate the values of x and y directly inside the macro.

A minimal working example would be:

macro eval_line(a, b, x)
  isa(a, Real) || (warn("$a is not a real number."); return :(throw(DomainError())))
  isa(b, Real) || (warn("$b is not a real number."); return :(throw(DomainError())))
  return :($a * $x + $b) # interpolate the variables
end

Here, @eval_line macro does the following:

Main> @macroexpand @eval_line(5, 6, 2)
:(5 * 2 + 6)

As you can see, the values of macro's arguments are interpolated inside the macro and the expression is given to the user accordingly. When the user does not behave,

Main> @macroexpand @eval_line([1,2,3], 7, 8)
WARNING: [1, 2, 3] is not a real number.
:((Main.throw)((Main.DomainError)()))

a user-friendly warning message is provided to the user at parse-time, and a DomainError is thrown at run-time.

Of course, you can do these things within your functions, again by interpolating the variables --- you do not need to use macros. However, what you would like to achieve in the end is to combine eval with the output of a function that returns Expr. This is what the macro functionality is for. Finally, you would simply call your macros with an @ sign preceding the macro name:

Main> @eval_line(5, 6, 2)
16
Main> @eval_line([1,2,3], 7, 8)
WARNING: [1, 2, 3] is not a real number.
ERROR: DomainError:
Stacktrace:
 [1] eval(::Module, ::Any) at ./boot.jl:235

EDIT 1. You can take this one step further, and create functions accordingly:

macro define_lines(linedefs)
  for (name, a, b) in eval(linedefs)
    ex = quote
      function $(Symbol(name))(x) # interpolate name
        return $a * x + $b # interpolate a and b here
      end
    end
    eval(ex) # evaluate the function definition expression in the module
  end
end

Then, you can call this macro to create different line definitions in the form of functions to be called later on:

@define_lines([
  ("identity_line", 1, 0);
  ("null_line", 0, 0);
  ("unit_shift", 0, 1)
])

identity_line(5) # returns 5
null_line(5) # returns 0
unit_shift(5) # returns 1

EDIT 2. You can, I guess, achieve what you would like to achieve by using a macro similar to that below:

macro random_oper(depth, fs, ts)
  operations = eval(fs)
  oper = operations[rand(1:length(operations))]
  terminals = eval(ts)
  ts = terminals[rand(1:length(terminals), 2)]
  ex = :($oper($ts...))
  for d in 2:depth
    oper = operations[rand(1:length(operations))]
    t = terminals[rand(1:length(terminals))]
    ex = :($oper($ex, $t))
  end
  return ex
end

which will give the following, for instance:

Main> @macroexpand @random_oper(1, [+, -, /], [1,2,3])
:((-)([3, 3]...))

Main> @macroexpand @random_oper(2, [+, -, /], [1,2,3])
:((+)((-)([2, 3]...), 3))

Answer 3

Here is an example for generating an (anonymous) function. The result of eval can be called as a function and your variable can be passed as parameters:

myfun = eval(Expr(:->,:x,  Expr(:block, Expr(:call,:*,3,:x) )))
myfun(14)
# returns 42

The dump function is very useful to inspect the expression that the parsers has created. For two input arguments you would use a tuple for example as args[1]:

  julia> dump(parse("(x,y) -> 3x + y"))
  Expr
    head: Symbol ->
    args: Array{Any}((2,))
      1: Expr
        head: Symbol tuple
        args: Array{Any}((2,))
          1: Symbol x
          2: Symbol y
        typ: Any
      2: Expr
 [...]

Does this help?