summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rwxr-xr-xmonkey/monkey.py100
-rwxr-xr-xmonkey/test.py4
2 files changed, 66 insertions, 38 deletions
diff --git a/monkey/monkey.py b/monkey/monkey.py
index ef4ac2c..cd44bac 100755
--- a/monkey/monkey.py
+++ b/monkey/monkey.py
@@ -8,34 +8,32 @@ from .prolog.engine import test
from .prolog.util import compose, decompose, map_vars, rename_vars, stringify
from .util import PQueue, Token
-# score a program (a list of lines) according to lines distribution
-def score(program, lines):
- result = 1
- for line in program:
- line_normal = list(line)
- rename_vars(line_normal)
- line_normal = tuple(line_normal)
- result *= lines.get(line_normal, 0.01)
-
- if len(program) == 0 or result == 0:
- return 0.01
- return math.pow(result, 1/len(program))
-
-# find a sequence of edits that fixes [code]
+# Starting from [code], find a sequence of [edits] that transforms it into a
+# correct predicate for [name]. Append [aux_code] when testing (available facts
+# and predicates).
+# Return (solution, edits, time spent, #programs checked). If no solution is
+# found within [timeout] seconds, solution='' and edits=[].
def fix(name, code, edits, aux_code='', timeout=30, debug=False):
todo = PQueue() # priority queue of candidate solutions
- done = set() # set of already-analyzed solutions
+ done = set() # programs we have already visited
inserts, removes, changes = classify_edits(edits)
- # Generate states that can be reached from (lines, rules) with one edit.
- def step(lines, rules):
- rule_no = 0
+ # Generate states that can be reached from the given program with one edit.
+ # Program code is given as a list of [lines], where each line is a list of
+ # tokens. Rule ranges are given in [rules] (see prolog.util.decompose).
+ def step(lines, rules, prev=None):
+ # Apply edits in order from top to bottom; skip lines with index lower
+ # than last step.
+ start_line = prev[1] if prev else 0
+
for start, end in rules:
- rule = lines[start:end]
- rule_tokens = [t for line in rule for t in line]
+ rule_lines = lines[start:end]
+ rule_tokens = [t for line in rule_lines for t in line]
for line_idx in range(start, end):
+ if line_idx < start_line:
+ continue
line = lines[line_idx]
line_normal = list(line)
@@ -43,18 +41,18 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
line_normal = tuple(line_normal)
seen = False
+ # Apply each edit that matches this line.
for (before, after), cost in changes.items():
if line_normal == before:
seen = True
mapping = map_vars(before, after, line, rule_tokens)
after_real = tuple([t if t.type != 'VARIABLE' else Token('VARIABLE', mapping[t.val]) for t in after])
new_lines = lines[:line_idx] + (after_real,) + lines[line_idx+1:]
- new_step = ((rule_no, line_idx-start), (tuple(line), after_real))
+ new_step = ('change_line', line_idx, (tuple(line), after_real))
yield (new_lines, rules, new_step, cost)
- # if nothing could be done with this line, try removing it
- # (maybe try removing in any case?)
+ # Remove the current line.
if line_normal in removes.keys() or not seen:
new_lines = lines[:line_idx] + lines[line_idx+1:]
new_rules = []
@@ -63,13 +61,12 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
old_end - (0 if old_end <= line_idx else 1))
if new_end > new_start:
new_rules.append((new_start, new_end))
- new_step = ((rule_no, line_idx-start), (tuple(line), ()))
+ new_step = ('remove_line', line_idx, (tuple(line), ()))
new_cost = removes[line_normal] if line_normal in removes.keys() else 0.9
yield (new_lines, new_rules, new_step, new_cost)
- # try adding a line to this rule… would need to distinguish between
- # head/body lines in transforms
+ # Add a line to the current rule.
for after, cost in inserts.items():
mapping = map_vars([], after, [], rule_tokens)
after_real = [t if t.type != 'VARIABLE' else Token('VARIABLE', mapping[t.val]) for t in after]
@@ -79,20 +76,36 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
for old_start, old_end in rules:
new_rules.append((old_start + (0 if old_start < end else 1),
old_end + (0 if old_end < end else 1)))
- new_step = ((rule_no, end-start), ((), after_real))
+ new_step = ('add_subgoal', end, ((), after_real))
yield (new_lines, new_rules, new_step, cost)
- rule_no += 1
- # try adding a new fact
+ # Add a new fact at the end.
if len(rules) < 2:
for after, cost in inserts.items():
new_lines = lines + (after,)
new_rules = rules + (((len(lines), len(lines)+1)),)
- new_step = ((len(new_rules)-1, 0), (tuple(), tuple(after)))
+ new_step = ('add_rule', len(new_lines)-1, (tuple(), tuple(after)))
yield (new_lines, new_rules, new_step, cost)
+ # Return a cleaned-up list of steps:
+ # - multiple line edits in a single line are merged into one
+ # - check if any lines can be removed from the program
+ def postprocess(steps):
+ new_steps = []
+ i = 0
+ while i < len(steps):
+ if i < len(steps)-1 and \
+ steps[i][0] == 'change_line' and steps[i+1][0] == 'change_line' and \
+ steps[i][1] == steps[i+1][1] and steps[i][2][1] == steps[i+1][2][0]:
+ new_steps.append(('change_line', steps[i][1], (steps[i][2][0], steps[i+1][2][1])))
+ i += 1
+ else:
+ new_steps.append(steps[i])
+ i += 1
+ return new_steps
+
# Add the initial program to the queue.
lines, rules = decompose(code)
todo.push(((tuple(lines), tuple(rules)), (), 1.0), -1.0)
@@ -119,20 +132,35 @@ def fix(name, code, edits, aux_code='', timeout=30, debug=False):
if debug:
print('Cost {:.12f}'.format(path_cost))
- for line, (before, after) in path:
- print('line ' + str(line) + ':\t' + stringify(before) + ' → ' + stringify(after))
+ for step_type, line, (before, after) in path:
+ print('line {}: {} {} → {}'.format(line, step_type, stringify(before), stringify(after)))
# If the code is correct, we are done.
if test(name, code + '\n' + aux_code):
+ path = postprocess(path)
return code, path, total_time, n_tested
n_tested += 1
# Otherwise generate new solutions.
path = list(path)
- for new_lines, new_rules, new_step, new_cost in step(lines, rules):
- new_path = tuple(path + [new_step])
+ prev_step = path[-1] if path else None
+ for new_lines, new_rules, new_step, new_cost in step(lines, rules, prev_step):
new_path_cost = path_cost * new_cost * 0.99
- if new_path_cost > 0.005:
- todo.push(((tuple(new_lines), tuple(new_rules)), new_path, new_path_cost), -new_path_cost)
+ if new_path_cost < 0.005:
+ continue
+ new_path = tuple(path + [new_step])
+ todo.push(((tuple(new_lines), tuple(new_rules)), new_path, new_path_cost), -new_path_cost)
return '', [], total_time, n_tested
+
+# Return a list of character ranges modified by the sequence [edits].
+def fix_ranges(edits):
+ marks = []
+ for step_type, line, (before, after) in edits:
+ if step_type == 'change_line':
+ marks.append(('change', (before[0].pos, before[-1].pos+len(before[-1].val))))
+ elif step_type == 'remove_line':
+ marks.append(('remove', (before[0].pos, before[-1].pos+len(before[-1].val))))
+ elif step_type == 'add_subgoal' or step_type == 'add_rule':
+ marks.append((step_type, line))
+ return marks
diff --git a/monkey/test.py b/monkey/test.py
index 01caf08..4bf5db9 100755
--- a/monkey/test.py
+++ b/monkey/test.py
@@ -52,8 +52,8 @@ def print_hint(solution, steps, fix_time, n_tested):
if solution:
print(colored('Hint found! Tested {} programs in {:.1f} s.'.format(n_tested, fix_time), 'green'))
print(colored(' Edits', 'blue'))
- for line, (before, after) in steps:
- print(' {}:\t{} → {}'.format(line, stringify(before), stringify(after)))
+ for step_type, line, (before, after) in steps:
+ print(' {}: {} {} → {}'.format(line, step_type, stringify(before), stringify(after)))
print(colored(' Final version', 'blue'))
print(indent(compose(*decompose(solution)), 2))
else: