Lazy variable-renumbering makes substitution cheap (Q1114386)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Lazy variable-renumbering makes substitution cheap |
scientific article |
Statements
Lazy variable-renumbering makes substitution cheap (English)
0 references
1988
0 references
A new data structure for expressions with many variable bindings is efficient for symbol manipulation involving repeated complex substitution because it avoids making many trivially different copies. It retains variables, permits efficient alpha- and beta-conversion, and is appropriate for program transformation and formal logic.
0 references
variable capture
0 references
lambda calculus
0 references
De Bruijn number
0 references
data structure
0 references
symbol manipulation
0 references
substitution
0 references
