-
Notifications
You must be signed in to change notification settings - Fork 4
/
Copy pathREADME.Rmd
137 lines (101 loc) · 5.57 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
---
output: github_document
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
```{r setup, include = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>",
fig.path = "man/figures/README-",
out.width = "100%"
)
library(dynprog)
```
# dynprog - Domain-specific language for specifying dynamic programming computations
[](https://www.gnu.org/licenses/gpl-3.0.en.html)
[](http://www.repostatus.org/#active)
[](https://www.tidyverse.org/lifecycle/#maturing)
[)`-orange.svg)](/commits/master)
[](commits/master)
[](https://travis-ci.org/mailund/dynprog)
[](https://ci.appveyor.com/project/mailund/dynprog)
[](https://codecov.io/github/mailund/dynprog?branch=master)
[](https://coveralls.io/github/mailund/dynprog?branch=master)
[](https://cran.r-project.org/package=dynprog)
[](https://cran.r-project.org/package=dynprog)
[](https://cran.r-project.org/)
The `dynprog` package implements a small domain-specific language for specifying dynamic programming algorithms. It allows you to specify a computation as a recursion and it will then use this recursion to fill out a table and return it to you.
As a very simple example, you can specify a dynamic programming computation of [Fibonnaci numbers](https://en.wikipedia.org/wiki/Fibonacci_number) using
```{r}
fibs <- {
F[1] <- 1
F[2] <- 1
F[n] <- F[n - 1] + F[n - 2]
} %where% {
n <- 1:10
}
fibs
```
As shown in the example, the expression consists of two parts, the first, before the `%where%` operator, describes a recursion and the second, after the `%where%` operator, the range the variable `n` should iterate over.
Formally, a `dynprog` expression is on the form
```
DYNPROG_EXPR ::= RECURSIONS '%where%' RANGES
RECURSIONS ::= '{' PATTERN_ASSIGNMENTS '}'
RANGES ::= '{' RANGES_ASSIGNMENTS '}'
```
where `PATTERN_ASSIGNMENTS` describe the recursion and `RANGES_ASSIGNMENTS` the variables to recurse over and the values those variables should take.
Ranges are the simplest of the two.
```
RANGES_ASSIGNMENTS ::= RANGES_ASSIGNMENT
| RANGES_ASSIGNMENT ';' RANGES_ASSIGNMENTS
RANGES_ASSIGNMENT ::= RANGE_INDEX '<-' RANGE_EXPRESSION
```
where `RANGE_INDEX` is just a variable and `RANGE_EXPRESSION` an expression that should evaluate to a list or vector. You can specify more than one variable if these are separated by `;` or newlines (the grammar only says `;` but I am not too formal here). An example with two range variables, of computing the [edit distance](https://en.wikipedia.org/wiki/Edit_distance) between two strings, is shown below.
The actual recursions are specified in `PATTERN_ASSIGNMENTS`:
```
PATTERN_ASSIGNMENTS ::= PATTERN_ASSIGNMENT
| PATTERN_ASSIGNMENT ';' PATTERN_ASSIGNMENTS
```
where
```
PATTERN_ASSIGNMENT ::= PATTERN '<-' RECURSION
| PATTERN '<-' RECURSION '?' CONDITION
```
```
PATTERN ::= TABLE '[' INDICES ']'
```
Here, `TABLE` is just a variable and `INDICES` should be a comma-separated lists of values/expressions or variables. When recursions are evaluated, the range variables are tested against the patterns. If a pattern contains a range variable as a variable, the variable is free to take any value, but if it takes on a value, the range variable must have that value.
To the right of the assignment in `PATTERN_ASSIGNMENTS` we have `RECURSION`, which cna be any R expression and an optional `CONDITION`, which should be an R expression that evaluates to a boolean value.
The semantics of the recursions are that the patterns are tested in the order they are provided, and if both the patterns match the range variables and the condition evaluates to `TRUE`, then the entry in the table will get assigned the result of evaluating `RECURSION`.
For more information, see
> Mailund, T. (2018) [Domain-Specific Languages in R](https://amzn.to/2DRmFXb),
> Apress. ISBN 1484235878
## Installation
You can install the released version of `dynprog` from [CRAN](https://CRAN.R-project.org) with:
``` r
install.packages("dynprog")
```
and the development version from [GitHub](https://github.com/) with:
``` r
# install.packages("devtools")
devtools::install_github("mailund/dynprog")
```
## Example
You can compute the [edit-distance](https://en.wikipedia.org/wiki/Edit_distance) between two strings like this:
```{r}
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
```