HerbCore.jl Documentation

Represents a constraint for a AbstractGrammar. Concrete implementations can be found in HerbConstraints.jl.

AbstractGrammar

Abstract type representing all grammars. It is assumed that all grammar structs have at least the following attributes:

• rules::Vector{Any}: A list of RHS of rules (subexpressions).
• types::Vector{Symbol}: A list of LHS of rules (types, all symbols).
• isterminal::BitVector: A bitvector where bit i represents whether rule i is terminal.
• iseval::BitVector: A bitvector where bit i represents whether rule i is an eval rule.
• bytype::Dict{Symbol,Vector{Int}}: A dictionary that maps a type to all rules of said type.
• domains::Dict{Symbol, BitVector}: A dictionary that maps a type to a domain bitvector. The domain bitvector has bit i set to true iff the ith rule is of this type.
• childtypes::Vector{Vector{Symbol}}: A list of types of the children for each rule.

If a rule is terminal, the corresponding list is empty.

• log_probabilities::Union{Vector{Real}, Nothing}: A list of probabilities for each rule.

If the grammar is non-probabilistic, the list can be nothing.

For concrete types, see ContextSensitiveGrammar within the HerbGrammar module.

AbstractHole <: AbstractRuleNode

A AbstractHole is a placeholder where certain rules from the grammar can still be applied. The domain of a AbstractHole defines which rules can be applied. The domain is a bitvector, where the ith bit is set to true if the ith rule in the grammar can be applied.

abstract type AbstractRuleNode end

Abstract type for representing expression trees. An AbstractRuleNode is expected to implement the following functions:

• isfilled(::AbstractRuleNode)::Bool. True iff the grammar rule this node holds is not ambiguous, i.e. has domain size 1.
• isuniform(::AbstractRuleNode)::Bool. True iff the children of this node are known.
• get_rule(::AbstractRuleNode)::Int. Returns the index of the grammar rule it represents.
• get_children(::AbstractRuleNode)::Vector{AbstractRuleNode}. Returns the children of this node.

Expression trees consist of RuleNodes and AbstractHoles.

• A RuleNode represents a certain production rule in the AbstractGrammar.
• A AbstractHole is a placeholder where certain rules in the grammar still can be applied.

Hole <: AbstractHole

An AbstractUniformHole is a placeholder where certain rules from the grammar can still be applied, but all rules in the domain are required to have the same childtypes.

Hole <: AbstractHole

• domain: A bitvector, where the ith bit is set to true if the ith rule in the grammar can be applied.

HoleReference

Contains a hole and the path to the hole from the root of the tree.

RuleNode <: AbstractRuleNode

A RuleNode represents a node in an expression tree. Each node corresponds to a certain rule in the AbstractGrammar. A RuleNode consists of:

• ind: The index of the rule in the AbstractGrammar which this node is representing.
• _val: Field for caching evaluations of RuleNodes, preventing multiple unnecessary evaluations. The field can be used to store any needed infromation.
• children: The children of this node in the expression tree

RuleNode(ind::Int, _val::Any)

Create a RuleNode for the AbstractGrammar rule with index ind, _val as immediately evaluated value and no children

RuleNode(ind::Int, children::Vector{AbstractRuleNode})

Create a RuleNode for the AbstractGrammar rule with index ind and children as subtrees.

UniformHole <: AbstractHole

• domain: A bitvector, where the ith bit is set to true if the ith rule in the grammar can be applied. All rules in the domain are required to have the same childtypes.
• children: The children of this hole in the expression tree.

@rulenode

Construct a RuleNode using the shorthand notation RuleNodes and AbstractHoles are printed with using Base.show.

Does not yet support AbstractHoles defined outside of HerbCore.

Examples

julia> @rulenode 1{4{5,6},1{2,3}}
1{4{5,6},1{2,3}}

julia> @rulenode 1
1

julia> @rulenode 1{2, 3}
1{2,3}

julia> @rulenode UniformHole[1, 1, 0, 0]{2,3}
UniformHole[Bool[1, 1, 0, 0]]{2,3}

julia> @rulenode Hole[1, 1, 0, 0]
Hole[Bool[1, 1, 0, 0]]

Base.isless(rn₁::AbstractRuleNode, rn₂::AbstractRuleNode)::Bool

Compares two RuleNodes. Returns true if the left RuleNode is less than the right RuleNode. Order is determined from the index of the RuleNodes. If both RuleNodes have the same index, a depth-first search is performed in both RuleNodes until nodes with a different index are found.

Base.length(root::RuleNode)

Return the number of nodes in the tree rooted at root.

contains_hole(rn::RuleNode) = any(contains_hole(c) for c ∈ rn.children)

Checks if an AbstractRuleNode tree contains a AbstractHole.

contains_index(rulenode::RuleNode, index::Int)

Returns true if the rulenode contains the index.

contains_nonuniform_hole(rn::RuleNode)

Checks if an AbstractRuleNode tree contains a Hole.

depth(root::RuleNode)::Int

Return the depth of the AbstractRuleNode tree rooted at root. Holes do count towards the depth.

get_children(rn::AbstractRuleNode)

Returns the children of the given AbstractRuleNode

get_node_at_location(root::AbstractRuleNode, location::Vector{Int})

Retrieves a RuleNode at the given location by reference.

get_node_at_location(root::Hole, location::Vector{Int})

Retrieves the current hole, if location is this very hole. Throws error otherwise.

get_path(root::AbstractRuleNode, node::AbstractRuleNode)

Returns the path from the root to the targetnode. Returns nothing if no path exists.

get_rule(rn::AbstractRuleNode)

Returns the index of the rule that this AbstractRuleNode represents

get_rulesequence(node::RuleNode, path::Vector{Int})

Extract the derivation sequence from a path (sequence of child indices) and an AbstractRuleNode. If the path is deeper than the deepest node, it returns what it has.

function hasdynamicvalue(rn::AbstractRuleNode)::Bool

Returns true iff the rule has a _val field set up.

have_same_shape(node1::AbstractRuleNode, node2::AbstractRuleNode)

Returns true iff node1 and node2 have the same shape Example: RuleNode(3, [ RuleNode(1), RuleNode(1) ]) and RuleNode(9, [ RuleNode(2), Hole(domain) ]) have the same shape: 1 root with 2 children.

is_domain_valid(x, n_rules::Integer)
is_domain_valid(x, grammar::AbstractGrammar)

Check if the domain for the given object x (ex: RuleNode, Hole or AbstractConstraint) is valid given the provided grammar or number of rules.

If isfilled(x) and x has children, it checks if all children are valid.

isfilled(node::AbstractRuleNode)::Bool

Returns whether the [AbstractRuleNode] holds a single rule. This is always the case for RuleNodes. Holes are considered to be "filled" iff their domain size is exactly 1.

issame(a, b)

Returns whether the two given objects a and b (ex: RuleNode, Hole or AbstractConstraint) are the same.

isuniform(rn::AbstractRuleNode)

Returns true iff the children of the AbstractRuleNode are known.

node_depth(root::AbstractRuleNode, node::AbstractRuleNode)::Int

Return the depth of node for an AbstractRuleNode tree rooted at root. Depth is 1 when root == node.

number_of_holes(rn::AbstractRuleNode)::Int

Recursively counts the number of holes in an AbstractRuleNode

rulesoftype(node::RuleNode, grammar::AbstractGrammar, ruletype::Symbol[, ignoreNode::AbstractRuleNode])

Returns every rule of nonterminal symbol ruletype from the grammar that is also used in the AbstractRuleNode tree, but not in the ignoreNode subtree.

rulesoftype(node::RuleNode, ruleset::Set{Int}[, ignoreNode::AbstractRuleNode])
rulesoftype(node::RuleNode, rule_index::Int[, ignoreNode::AbstractRuleNode])

Returns every rule in the ruleset that is also used in the AbstractRuleNode tree, but not in the ignoreNode subtree.

rulesonleft(expr::RuleNode, path::Vector{Int})::Set{Int}

Finds all rules that are used in the left subtree defined by the path.

swap_node(expr::AbstractRuleNode, new_expr::AbstractRuleNode, path::Vector{Int})

Replace a node in expr, specified by path, with new_expr. Path is a sequence of child indices, starting from the root node.

swap_node(expr::RuleNode, node::RuleNode, child_index::Int, new_expr::RuleNode)

Replace child i of a node, a part of larger expr, with new_expr.

update_rule_indices!(...)

Updates the rule indices of the given rule node, hole or grammar constraint when the grammar changes.

update_rule_indices!(hole::AbstractHole, n_rules::Integer, mapping::AbstractDict{<:Integer, <:Integer})

Updates the domains of hole and its children according to mapping. For AbstractHoles, this updates both the size of the domain BitVector and the rule indices. Errors if the length of the domain vector exceeds new n_rules.

Arguments

• hole: The current AbstractHole being processed
• n_rules: The new number of rules in the grammar
• mapping: A dictionary mapping the old rule indices to new ones

update_rule_indices!(node::AbstractHole, n_rules::Integer)

Resize the domains of hole and its children. Errors if the length of the domain vector exceeds new n_rules.

Arguments

• hole: The current AbstractHole being processed
• n_rules: The new number of rules in the grammar

update_rule_indices!(node::RuleNode, n_rules::Integer, mapping::AbstractDict{<:Integer, <:Integer})

Remap the rule indices of node and its children according to the provided mapping. Errors if the rule index exceeds new n_rules.

Arguments

• node: The current RuleNode being processed
• n_rules: The new number of rules in the grammar
• mapping: A dictionary mapping old rule indices to new rule indices

update_rule_indices!(node::RuleNode, n_rules::Integer)

Updates the node as required when grammar size changes. Errors if the rule index exceeds new n_rules.

Arguments

• node: The current RuleNode being processed
• n_rules: The new number of rules in the grammar