Рекурсивные стратегии с дополнительными параметрами в гипотезе - PullRequest
0 голосов
/ 06 апреля 2019

Используя recursive, я могу генерировать простые AST, например,

from hypothesis import *
from hypothesis.strategies import *

def trees():
    base = integers(min_value=1, max_value=10).map(lambda n: 'x' + str(n))

    @composite
    def extend(draw, children):
        op = draw(sampled_from(['+', '-', '*', '/']))
        return (op, draw(children), draw(children))

    return recursive(base, draw)

Теперь я хочу изменить его, чтобы я мог генерировать логические операции в дополнение к арифметическим.Моя первоначальная идея - добавить параметр в trees:

def trees(tpe):
    base = integers(min_value=1, max_value=10).map(lambda n: 'x' + str(n) + ': ' + tpe)

    @composite
    def extend(draw, children):
        if tpe == 'bool':
            op = draw(sampled_from(['&&', '||']))
            return (op, draw(children), draw(children))
        elif tpe == 'num':
            op = draw(sampled_from(['+', '-', '*', '/']))
            return (op, draw(children), draw(children))

    return recursive(base, draw)

Хорошо, пока.Но как мне их смешать?То есть мне также нужны операторы сравнения и троичный оператор, которые потребовали бы, так сказать, «вызова children с другим параметром».

Деревья должны быть хорошо типизированы: если операция выполняется'||' или '&&', оба аргумента должны быть логическими, аргументы '+' или '<' должны быть числами и т. Д. Если бы у меня было только два типа, я мог бы просто использовать filter (учитывая type_of function):

if op in ('&&', '||'):
    bool_trees = children.filter(lambda x: type_of(x) == 'bool')
    return (op, draw(bool_trees), draw(bool_trees))

но в реальном случае это было бы неприемлемо.

Поддерживает ли recursive это?Или есть другой способ?Очевидно, я могу напрямую определить trees рекурсивно, но это сталкивается с стандартными проблемами .

Ответы [ 2 ]

2 голосов
/ 10 апреля 2019

Решением, которое я использовал на данный момент, является адаптация сгенерированных деревьев, например, если дерево num генерируется, когда операции требуется bool, я также рисую оператор сравнения op и константу const иreturn (op, tree, const):

def make_bool(tree, draw):
    if type_of(tree) == 'bool':
        return tree
    else type_of(tree) == 'num':
        op = draw(sampled_from(comparison_ops))
        const = draw(integers())
        side = draw(booleans())
        return (op, tree, const) if side else (op, const, tree)

// in def extend:
if tpe == 'bool':
    op = draw(sampled_from(bool_ops + comparison_ops))
    if op in bool_ops:
        return (op, make_bool(draw(children), draw), make_bool(draw(children), draw))
    else:
        return (op, make_num(draw(children), draw), make_num(draw(children), draw))

К сожалению, он специфичен для AST и будет означать, что определенные виды деревьев генерируются чаще.Так что я все равно был бы рад видеть лучшие альтернативы.

2 голосов
/ 10 апреля 2019

Вы можете просто описать деревья, где сравнение производится из любого набора операций - в этом случае тривиально, используя выборку из ['&&', '||', '+', '-', '*', '/'].

def trees():
    return recursive(
        integers(min_value=1, max_value=10).map('x{}'.format),
        lambda node: tuples(sampled_from('&& || + - * /'.split()), node, node)
    )

Но, конечно, это не будетхорошо напечатан (за исключением, возможно, редкого совпадения).Я думаю, что лучший вариант для хорошо типизированных AST:

  1. Для каждого типа определите стратегию для деревьев, которые оценивают этот тип.Базовый случай - это просто (стратегия) значение этого типа.
  2. Расширение заключается в предварительном вычислении возможных комбинаций типов и операций, которые могут генерировать значение этого типа, с использованием взаимной рекурсии через st.deferred.Это выглядело бы примерно так ...
bool_strat = deferred(
    lambda: one_of(
        booleans(),
        tuples(sampled_from(["and", "or"], bool_strat, bool_strat), 
        tuples(sampled_from(["==", "!=", "<", ...]), integer_strat, integer_strat),
    )
)
integer_strat = deferred(
    lambda: one_of(
        integers(),
        tuples(sampled_from("= - * /".split()), integer_strat, integer_strat),
    )
)
any_type_ast = bool_strat | integer_strat

И это будет работать как по волшебству: D

(с другой стороны, это немного сложнее -если ваш обходной путь работает на вас, не чувствуйте себя обязанным делать это вместо этого!)

Если вы видите проблемные выбросы по размеру - что должно быть очень редко, так как у двигателя было много работыс тех пор как эта статья была написана - честно говоря, с этим мало что можно сделать.Пропуская предел глубины через все это и уменьшая его, каждый шаг работает как последнее средство, но работать с ним нехорошо.

...