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¶
Wikipedia
-
Binary: base 2
Octal: base 8
Decimal: base 10
Hexadecimal: base 16
-
[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.
[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¶
[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
[4]:
exec_rust_expression('0b10')
[4]:
'2'
[5]:
exec_rust_expression('0o10')
[5]:
'8'
[6]:
exec_rust_expression('10')
[6]:
'10'
[7]:
exec_rust_expression('0x10')
[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.
[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.
[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.
[10]:
for _ in range(10):
random_string = grammar_num.generate_string()
print(random_string)
4e_454f64
0o41u16
271.41e+82
0b10
0x0E
0b0010000i64
90e6
4u8
0o3usize
2
[11]:
objective_function(random_string)
[11]:
40.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¶
[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
..... ....
Finished 9 55 3.8 0.0
[13]:
string = best_ind.phenotype
print('Rust expression:', string)
Rust expression: 0b101010
[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¶
[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 79 2.3 39.0
..... ..... 20 129 6.8 3.0
..... ..... 30 158 10.1 1.0
..... ..... 40 183 12.8 1.0
.....
Finished 45 194 14.2 0.0
[16]:
string = best_ind.phenotype
print('Rust expression:', string)
Rust expression: 0o52
[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¶
[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 76 1.9 3504.0
..... ..... 20 145 5.6 1.0
....
Finished 24 167 7.8 0.0
[19]:
string = best_ind.phenotype
print('Rust expression:', string)
Rust expression: 0x2A
[20]:
program = rust_template.format(string)
print('Rust program:', program)
Rust program:
fn main() {
let expr = 0x2A;
println!("{}", expr);
}