Connects a recursion with sequences it should recurse over.

Description

This function parses a dynamic programming recursion expression and evaluates it, returning the table that the recursions specify.

Usage

recursion %where% ranges

Arguments

Value

A filled out dynamic programming table.

Examples

# Fibonnaci numbers
fib <- {
  F[n] <- 1 ? n <= 2
  F[n] <- F[n-1] + F[n-2]
} %where% {
  n <- 1:10
}
fib

# Edit distance
x <- c("a", "b", "c")
y <- c("a", "b", "b", "c")
edit <- {
    E[1,j] <- j - 1
    E[i,1] <- i - 1
    E[i,j] <- min(
        E[i - 1,j] + 1,
        E[i,j - 1] + 1,
        E[i - 1,j - 1] + (x[i - 1] != y[j - 1])
    )
} %where% {
    i <- 1:(length(x) + 1)
    j <- 1:(length(y) + 1)
}
edit

Evaluate an entire dynprog recursion.

Description

This function takes the ranges and recursions of a specification and evaluate the dynprog expression, returning a filled out dynamic programming table.

Usage

eval_recursion(ranges, recursions)

Arguments

Value

The filled out dynamic programming table

Extract the table name from a pattern.

Description

We generally assume that patterns are on the form table[exprs] where table is the name of the dynamic programming table. This function extract that name.

Usage

get_table_name(patterns)

Arguments

Value

The table part of the pattern.

Translate condition expressions into calls that test them.

Description

Takes the full dynprog expression and construct a list of condition tests for each component of the recursion.

Usage

make_condition_checks(ranges, patterns, conditions, recursions)

Arguments

Value

A list of calls, one per recursion, for testing conditions.

Translate a pattern into a predicate that checks the pattern.

Description

Takes a pattern from the DSL and make a comparison of the pattern specification against range variables.

Usage

make_pattern_match(pattern, range_vars)

Arguments

Value

An expression that tests pattern against range_vars.

Make pattern tests for all patterns.

Description

This function calls make_pattern_match() for each pattern in patterns and return a list of all the pattern test expressions.

Usage

make_pattern_tests(patterns, range_vars)

Arguments

Value

A list of pattern check expressions.

Construct a test for a case in the recursion

Description

This function creates an if-statement for testing if a case can be applied.

Usage

make_recursion_case(test_expr, value_expr, continue)

Arguments

Value

An if-statement for checking and potentially evaluating one case.

String together the case if-statements of a recursion.

Description

String together the case if-statements of a recursion.

Usage

make_update_expr(ranges, patterns, conditions, recursions)

Arguments

Value

A series of if-⁠else⁠-statements for evaluating a recursion.

Parser for the ranges part of a specification.

Description

Parses the ranges and return a list of index variables an the values they should iterate over. The ranges are returned as a list with the range variables as its names and the range values as the list components.

Usage

parse_ranges(ranges)

Arguments

Value

A parsed specification for ranges.

Parser for the recursion part of a specification.

Description

Parse the recursion part of an expressions.

Usage

parse_recursion(recursion)

Arguments

Details

The parser return a list with the following components:

• recursion_env: The environment in which expressions should be evaluated.

• patterns: A list of patterns, one per recursion case.

• conditions: A list of conditions, one per recursion case.

• recursions: A list of expressions, one per recursion case.

Value

A parsed specification for recursions.