Number literals in Rust

This notebook demonstrates how to use a subset of the grammar that defines the programming language Rust in order to evolve different Rust number literals that all evaluate to the same decimal number.

References

In [1]:
import os
import subprocess
import tempfile

import alogos as al
import unified_map as um

Preparation

1) Run shell commands

This is needed to use the Rust compiler rustc and to execute the compiled binary file.

In [2]:
def run_shell_command(cmd, timeout_in_sec=1):
    proc = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=subprocess.DEVNULL, shell=True)
    out, err = proc.communicate(timeout=timeout_in_sec)
    return out.decode()[:-1]

2) Compile and run Rust code from Python

In [3]:
rust_template = """
fn main() {{
  let expr = {};
  println!("{{}}", expr);
}}
"""

def compile_and_run_rust(code):
    with tempfile.NamedTemporaryFile('w') as fp:
        fp.write(code)
        fp.flush()
        src = fp.name
        trg = src + '.out'
        run_shell_command('rustc {} -o {} 2> /dev/null'.format(src, trg))
        output = run_shell_command(trg)
        os.remove(trg)
    return output

def exec_rust_expression(expr):
    code = rust_template.format(expr)
    output = compile_and_run_rust(code)
    return output
In [4]:
exec_rust_expression('0b10')
Out[4]:
'2'
In [5]:
exec_rust_expression('0o10')
Out[5]:
'8'
In [6]:
exec_rust_expression('10')
Out[6]:
'10'
In [7]:
exec_rust_expression('0x10')
Out[7]:
'16'

Definition of search space and goal

1) Grammar

This grammar defines the search space: a Rust number literal as defined in the Rust Reference.

In [8]:
ebnf_template = """
EXPRESSION = {chosen_expression}

FLOAT_LITERAL = DEC_LITERAL "."
   | DEC_LITERAL FLOAT_EXPONENT
   | DEC_LITERAL "." DEC_LITERAL FLOAT_EXPONENT?
   | DEC_LITERAL ("." DEC_LITERAL)? FLOAT_EXPONENT? FLOAT_SUFFIX
FLOAT_EXPONENT = ("e"|"E") ("+"|"-")? (DEC_DIGIT|"_")* DEC_DIGIT (DEC_DIGIT|"_")*
FLOAT_SUFFIX = "f32" | "f64"

INTEGER_LITERAL = ( DEC_LITERAL | BIN_LITERAL | OCT_LITERAL | HEX_LITERAL ) INTEGER_SUFFIX?
DEC_LITERAL = DEC_DIGIT (DEC_DIGIT|_)*
BIN_LITERAL = "0b" (BIN_DIGIT|_)* BIN_DIGIT (BIN_DIGIT|_)*
OCT_LITERAL = "0o" (OCT_DIGIT|_)* OCT_DIGIT (OCT_DIGIT|_)*
HEX_LITERAL = "0x" (HEX_DIGIT|_)* HEX_DIGIT (HEX_DIGIT|_)*
BIN_DIGIT = "0" | "1"
OCT_DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" 
DEC_DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 
HEX_DIGIT = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" |
            "a" | "b" | "c" | "d" | "e" | "f" |
            "A" | "B" | "C" | "D" | "E" | "F"
INTEGER_SUFFIX = "u8" | "u16" | "u32" | "u64" | "u128" | "usize" | "i8" | "i16" | "i32" | "i64" | "i128" | "isize"
"""


def generate_grammar(chosen_expression):
    ebnf_text = ebnf_template.format(chosen_expression=chosen_expression)
    grammar = al.Grammar(ebnf_text=ebnf_text)
    return grammar


grammar_num = generate_grammar(chosen_expression='INTEGER_LITERAL | FLOAT_LITERAL')

grammar_float = generate_grammar(chosen_expression='FLOAT_LITERAL')
grammar_int = generate_grammar(chosen_expression='INTEGER_LITERAL')

grammar_dec = generate_grammar(chosen_expression='DEC_LITERAL')
grammar_bin = generate_grammar(chosen_expression='BIN_LITERAL')
grammar_oct = generate_grammar(chosen_expression='OCT_LITERAL')
grammar_hex = generate_grammar(chosen_expression='HEX_LITERAL')

2) Objective function

The objective function gets a candidate solution (=a string of the grammar's language) and returns a fitness value for it. This is done by 1) inserting the Rust number literal into a Rust program that prints the number 2) compile and run that Rust program, and 3) compute how much it deviate from a target number.

In [9]:
target = 42

def objective_function(string):
    number = float(exec_rust_expression(string))
    return abs(number-target)

Generation of a random solution

Check if grammar and objective function work as intended.

In [10]:
for _ in range(10):
    random_string = grammar_num.generate_string()
    print(random_string)

5.7e-11f64
0b10i64
0b1
0xe6
0x2
0.
1.9E___91
0b00
84usize
0E-_0886
In [11]:
objective_function(random_string)
Out[11]:
42.0

Search for an optimal solution

Evolutionary optimization with random variation and non-random selection is used to find increasingly better candidate solutions.

Find a binary literal that evaluates to decimal 42

In [12]:
ea = al.EvolutionaryAlgorithm(
    grammar_bin, objective_function, 'min', max_or_min_fitness=0.0, population_size=8, offspring_size=8,
    verbose=True, evaluator=um.univariate.parallel.futures)
best_ind = ea.run()

Progress         Generations      Evaluations      Runtime (sec)    Best fitness    
..... .....      10               69               4.0              2.0
..... .....      20               117              8.3              1.0
..... .....      30               151              12.0             1.0
....

Finished         34               166              13.8             0.0
In [13]:
string = best_ind.phenotype
print('Rust expression:', string)

Rust expression: 0b101010
In [14]:
program = rust_template.format(string)
print('Rust program:', program)

Rust program: 
fn main() {
  let expr = 0b101010;
  println!("{}", expr);
}

Find an octal literal that evaluates to decimal 42

In [15]:
ea = al.EvolutionaryAlgorithm(
    grammar_oct, objective_function, 'min', max_or_min_fitness=0.0, population_size=8, offspring_size=8,
    verbose=True, evaluator=um.univariate.parallel.futures)
best_ind = ea.run()

Progress         Generations      Evaluations      Runtime (sec)    Best fitness    
..... .....      10               75               3.3              3.0
....

Finished         14               95               5.4              0.0
In [16]:
string = best_ind.phenotype
print('Rust expression:', string)

Rust expression: 0o52
In [17]:
program = rust_template.format(string)
print('Rust program:', program)

Rust program: 
fn main() {
  let expr = 0o52;
  println!("{}", expr);
}

Find a hexadecimal literal that evaluates to decimal 42

In [18]:
ea = al.EvolutionaryAlgorithm(
    grammar_hex, objective_function, 'min', max_or_min_fitness=0.0, population_size=8, offspring_size=8,
    verbose=True, evaluator=um.univariate.parallel.futures)
best_ind = ea.run()

Progress         Generations      Evaluations      Runtime (sec)    Best fitness    
..... .....      10               80               2.6              768633.0
..... .....      20               141              7.4              14.0
..... .....      30               188              11.6             6.0
..... .....      40               231              15.8             1.0
...

Finished         43               244              17.5             0.0
In [19]:
string = best_ind.phenotype
print('Rust expression:', string)

Rust expression: 0x2A
In [20]:
program = rust_template.format(string)
print('Rust program:', program)

Rust program: 
fn main() {
  let expr = 0x2A;
  println!("{}", expr);
}