HerbGrammar.jl Documentation

ContextSensitiveGrammar <: AbstractGrammar

Represents a context-sensitive grammar. Extends AbstractGrammar with constraints.

Consists of:

• 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.
• bychildtypes::Vector{BitVector}: A bitvector of rules that share the same childtypes for each rule
• log_probabilities::Union{Vector{Real}, Nothing}: A list of probabilities for each rule. If the grammar is non-probabilistic, the list can be nothing.
• constraints::Vector{AbstractConstraint}: A list of constraints that programs in this grammar have to abide.

Use the @csgrammar macro to create a ContextSensitiveGrammar object. Use the @pcsgrammar macro to create a ContextSensitiveGrammar object with probabilities.

NodeLoc A helper struct that points to a node in the tree via its parent such that the child can be easily swapped out. If i is 0 the node pointed to is the root node and parent is the node itself.

SymbolTable

Type alias for a Dict that maps terminal symbols in the AbstractGrammar to their Julia interpretation.

@cfgrammar

This macro is deprecated and will be removed in future versions. Use @csgrammar instead.

@csgrammar

A macro for defining a ContextSensitiveGrammar. AbstractConstraints can be added afterwards using the addconstraint! function.

Example usage:

grammar = @csgrammar begin
	R = x
	R = 1 | 2
	R = R + R
end

Syntax:

• Literals: Symbols that are already defined in Julia are considered literals, such as 1, 2, or π. For example: R = 1.
• Variables: A variable is a symbol that is not a nonterminal symbol and not already defined in Julia. For example: R = x.
• Functions: Functions and infix operators that are defined in Julia or the Main module can be used with the default evaluator. For example: R = R + R, R = f(a, b).
• Combinations: Multiple rules can be defined on a single line in the grammar definition using the | symbol. For example: R = 1 | 2 | 3.
• Iterators: Another way to define multiple rules is by providing a Julia iterator after a | symbol. For example: R = |(1:9).

Related:

• @pcsgrammar uses a similar syntax to create probabilistic ContextSensitiveGrammars.

@pcsgrammar

A macro for defining a probabilistic ContextSensitiveGrammar.

Example usage:

grammar = @pcsgrammar begin
	0.5 : R = x
	0.3 : R = 1 | 2
	0.2 : R = R + R
end

Syntax:

The syntax of rules is identical to the syntax used by @csgrammar:

• Literals: Symbols that are already defined in Julia are considered literals, such as 1, 2, or π. For example: R = 1.
• Variables: A variable is a symbol that is not a nonterminal symbol and not already defined in Julia. For example: R = x.
• Functions: Functions and infix operators that are defined in Julia or the Main module can be used with the default evaluator. For example: R = R + R, R = f(a, b).
• Combinations: Multiple rules can be defined on a single line in the grammar definition using the | symbol. For example: R = 1 | 2 | 3.
• Iterators: Another way to define multiple rules is by providing a Julia iterator after a | symbol. For example: R = |(1:9).

Every rule is also prefixed with a probability. Rules and probabilities are separated using the : symbol. If multiple rules are defined on a single line, the probability is equally divided between the rules. The sum of probabilities for all rules of a certain non-terminal symbol should be equal to 1. The probabilities are automatically scaled if this isn't the case.

Related:

• @csgrammar uses a similar syntax to create non-probabilistic ContextSensitiveGrammars.

get(root::AbstractRuleNode, loc::NodeLoc) Obtain the node pointed to by loc.

insert!(loc::NodeLoc, rulenode::RuleNode) Replaces the subtree pointed to by loc with the given rulenode.

add_rule(grammar, tree)

Extends a given grammar with an AbstractRuleNode. The type of the rule is inferred from the root-type.

Arguments

• grammar::AbstractGrammar: the grammar to extend
• tree::RuleNode: the Herb tree

add_rule!(g::AbstractGrammar, e::Expr)

Adds a rule to the grammar.

Usage:

    add_rule!(grammar, :("Real = Real + Real"))

The syntax is identical to the syntax of @csgrammar and @cfgrammar, but only single rules are supported.

add_rule!(g::AbstractGrammar, p::Real, e::Expr)

Adds a probabilistic derivation rule.

addconstraint!(grammar::ContextSensitiveGrammar, c::AbstractConstraint)

Adds a AbstractConstraint to a ContextSensitiveGrammar.

child_types(grammar::AbstractGrammar, rule_index::Int)

Returns the types of the children (nonterminals) of the production rule at rule_index.

child_types(grammar::AbstractGrammar, node::RuleNode)

Returns the list of child types (nonterminal symbols) in the production rule used by node.

cleanup_removed_rules!(g::AbstractGrammar)

Removes any placeholders for previously deleted rules. This means that indices get shifted.

Clear all constraints from the grammar

containedin(vec1::Vector, vec2::Vector)

Checks if elements of vec1 are contained in vec2 in the same order (possibly with elements in between)

contains_returntype(node::RuleNode, grammar::AbstractGrammar, sym::Symbol, maxdepth::Int=typemax(Int))

Returns true if the tree rooted at node contains at least one node at depth less than maxdepth with the given return type or nonterminal symbol.

expr2csgrammar(ex::Expr)::ContextSensitiveGrammar

A function for converting an Expr to a ContextSensitiveGrammar. If the expression is hardcoded, you should use the @csgrammar macro. Only expressions in the correct format (see @csgrammar) can be converted.

Example usage:

grammar = expr2csgrammar(
	begin
		R = x
		R = 1 | 2
		R = R + R
	end
)

expr2pcsgrammar(ex::Expr)::ContextSensitiveGrammar

Function for converting an Expr to a ContextSensitiveGrammar with probabilities. If the expression is hardcoded, you should use the @pcsgrammar macro. Only expressions in the correct format (see @pcsgrammar) can be converted.

Example usage:

grammar = expr2pcsgrammar(
	begin
		0.5 : R = x
		0.3 : R = 1 | 2
		0.2 : R = R + R
	end
)

expr2rulenode(expr::Expr, grammar::AbstractGrammar, startSymbol::Symbol)

Converts an expression into a AbstractRuleNode corresponding to the rule definitions in the grammar.

expr2rulenode(expr::Expr, grammar::AbstractGrammar)

Converts an expression into a AbstractRuleNode corresponding to the rule definitions in the grammar.

expr2rulenode(expr::Symbol, grammar::AbstractGrammar, startSymbol::Symbol)

Converts an expression into a AbstractRuleNode corresponding to the rule definitions in the grammar.

expr2rulenode(expr::Symbol, grammar::AbstractGrammar)

Converts an expression into a AbstractRuleNode corresponding to the rule definitions in the grammar.

get_childtypes(rule::Any, types::AbstractVector{Symbol})

Returns the child types/nonterminals of a production rule.

get_domain(g::AbstractGrammar, type::Symbol)::BitVector

Returns the domain for the hole of a certain type as a BitVector of the same length as the number of rules in the grammar. Bit i is set to true iff rule i is of type type.

get_domain(g::AbstractGrammar, rules::Vector{Int})::BitVector

Takes a domain rules defined as a vector of ints and converts it to a domain defined as a BitVector.

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.

grammar2symboltable(grammar::AbstractGrammar, mod::Module=Main)

Returns a SymbolTable populated with a mapping from symbols in the AbstractGrammar to symbols in module mod or Main, if defined.

init_probabilities!(grammar::AbstractGrammar)

If the grammar is not probabilistic yet, initializes the grammar with uniform probabilities per type. If the grammar is already probabilistic, no changed are made.

iscomplete(grammar::AbstractGrammar, node::RuleNode)

Returns true if the expression represented by the RuleNode is a complete expression, meaning that it is fully defined and doesn't have any Holes.

iseval(grammar::AbstractGrammar, index::Int)::Bool

Returns true if the production rule at rule_index contains the special _() eval function.

iseval(grammar::AbstractGrammar)::Bool

Returns true if any production rules in grammar contain the special _() eval function.

iseval(rule)

Returns true if the rule is the special evaluate immediately function, i.e., _()

isprobabilistic(grammar::AbstractGrammar)::Bool

Function returns whether a AbstractGrammar is probabilistic.

isterminal(grammar::AbstractGrammar, node::AbstractRuleNode)::Bool

Returns true if the production rule used by node is terminal, i.e., does not contain any nonterminal symbols.

isterminal(grammar::AbstractGrammar, rule_index::Int)::Bool

Returns true if the production rule at rule_index is terminal, i.e., does not contain any nonterminal symbols.

isterminal(rule::Any, types::AbstractVector{Symbol})

Returns true if the rule is terminal, i.e., it does not contain any of the types in the provided vector. For example, :(x) is terminal, and :(1+1) is terminal, but :(Real + Real) is typically not.

isvariable(grammar::AbstractGrammar, ind::Int, mod::Module)::Bool

Return true if the rule with index ind represents a variable.

Taking into account the symbols defined in the given module(s).

isvariable(grammar::AbstractGrammar, ind::Int)::Bool

Return true if the rule with index ind represents a variable.

isvariable(grammar::AbstractGrammar, node::RuleNode, mod::Module)::Bool

Return true if the rule used by node represents a variable.

Taking into account the symbols defined in the given module(s).

isvariable(grammar::AbstractGrammar, node::RuleNode)::Bool

Return true if the rule used by node represents a variable in a program (essentially, an input to the program)

log_probability(grammar::AbstractGrammar, index::Int)::Real

Returns the log probability for the rule at index in the grammar.

max_arity(grammar::AbstractGrammar)::Int

Returns the maximum arity (number of children) over all production rules in the AbstractGrammar.

max_rulenode_log_probability(rulenode::AbstractRuleNode, grammar::AbstractGrammar)

Calculates the highest possible probability within an AbstractRuleNode. That is, for each node and its domain, get the highest probability and multiply it with the probabilities of its children, if present. As we operate with log probabilities, we sum the logarithms.

merge_grammars!(merge_to::AbstractGrammar, merge_from::AbstractGrammar)

Adds all rules and constraints from merge_from to merge_to.

mindepth(grammar::AbstractGrammar, typ::Symbol, dmap::AbstractVector{Int})

Returns the minimum depth achievable for a given nonterminal symbol. The minimum depth is the depth of the lowest tree that can be made using typ as a start symbol. dmap can be obtained from mindepth_map.

mindepth_map(grammar::AbstractGrammar)

Returns the minimum depth achievable for each production rule in the AbstractGrammar. In other words, this function finds the depths of the lowest trees that can be made using each of the available production rules as a root.

nchildren(grammar::AbstractGrammar, rule_index::Int)::Int

Returns the number of children (nonterminals) of the production rule at rule_index.

nchildren(grammar::AbstractGrammar, node::RuleNode)::Int

Returns the number of children in the production rule used by node.

nonterminals(grammar::AbstractGrammar)::Vector{Symbol}

Returns a list of the nonterminals or types in the AbstractGrammar.

normalize!(grammar::ContextSensitiveGrammar, type::Union{Symbol, Nothing}=nothing)

A function for normalizing the probabilities of a probabilistic ContextSensitiveGrammar. If the optional type argument is provided, only the rules of that type are normalized. If the grammar is not probabilistic, i.e. grammar.log_probabilities==nothing, a uniform distribution is initialized.

parse_probabilistic_rule(e::Expr)

Parses a single (potentially shorthand) derivation rule of a probabilistic ContextSensitiveGrammar. Returns nothing if the rule is not probabilistic, otherwise a Tuple of its type and a Vector of probability-rule pairs it expands into.

probability(grammar::AbstractGrammar, index::Int)::Real

Return the probability for a rule in the grammar. Use log_probability whenever possible.

read_csg(grammarpath::AbstractString, constraintspath::OptionalPath=nothing)::ContextSensitiveGrammar

Reads a ContextSensitiveGrammar from the files at grammarpath and constraintspath.

read_pcsg(grammarpath::AbstractString, constraintspath::OptionalPath=nothing)::ContextSensitiveGrammar

Reads a probabilistic ContextSensitiveGrammar from the files at grammarpath and constraintspath.

remove_rule!(g::AbstractGrammar, idx::Int)

Removes the rule corresponding to idx from the grammar. In order to avoid shifting indices, the rule is replaced with nothing, and all other data structures are updated accordingly.

return_type(grammar::AbstractGrammar, rule_index::Int)::Symbol

Returns the type of the production rule at rule_index.

return_type(grammar::AbstractGrammar, node::RuleNode)

Gives the return type or nonterminal symbol in the production rule used by node.

return_type(grammar::AbstractGrammar, hole::UniformHole)

Gives the return type or nonterminal symbol in the production rule used by hole.

rootnodeloc(root::RuleNode) Returns a NodeLoc pointing to the root node.

rulenode2expr(rulenode::AbstractRuleNode, grammar::AbstractGrammar)

Converts an AbstractRuleNode into a Julia expression corresponding to the rule definitions in the grammar. The returned expression can be evaluated with Julia semantics using eval().

rulenode_log_probability(node::RuleNode, grammar::AbstractGrammar)

Calculates the log probability associated with a rulenode in a probabilistic grammar.

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

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

store_csg(g::ContextSensitiveGrammar, grammarpath::AbstractString, constraintspath::OptionalPath=nothing)

Writes a ContextSensitiveGrammar to the files at grammarpath and constraintspath. The grammarpath file will contain a ContextSensitiveGrammar definition, and the constraintspath file will contain the AbstractConstraints of the ContextSensitiveGrammar.

subsequenceof(vec1::Vector{Int}, vec2::Vector{Int})

Checks if vec1 is a subsequence of vec2.

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.