You are looking at historical revision 11255 of this page. It may differ significantly from its current revision.

## Introduction

The `varsubst` library provides support for variable substition in user-defined languages. It contains a collection of routines for managing substitution environments and a generalized substitution procedure.

## Library procedures

`subst?:: OBJECT -> BOOL`

A predicate that returns true if the given argument is a substitution environment.

`subst-empty:: () -> SUBST`

Returns an empty substitution environment.

`subst-empty?:: SUBST -> BOOL`

Returns true if the given argument is an empty substitution environment, false otherwise.

`subst-includes?:: K * SUBST -> BOOL`

Returns true if the given symbol `K` is contained in the given substitution environment, false otherwise.

`subst-lookup:: K * SUBST -> TERM`

Looks up symbol `K` in the given substitution environment, and returns the term associated with it.

`subst-extend:: K * V * SUBST -> SUBST`

Adds the binding `K * V` to the given substitution environment, and returns the resulting substitution environment.

`subst-map:: PROC * SUBST -> SUBST`

For each binding `K * V` in the given substitution environment, applies procedure `PROC` to `V` and adds the new binding `K * (PROC V)` to the environment. Returns the resulting substitution environment.

`subst-driver:: VAR? * BIND? * VAR-PROC * BIND-PROC * SUBST-PROC [* PREFIX] -> (LAMBDA T SUBST)`

Generalized substitution procedure. Predicates `VAR?` and `BIND?` are used to determine if a given term is a variable or a binding, respectively. Procedure `VAR-PROC` takes a symbol and creates a variable term. Procedure `SUBST-PROC` substitues variables in the terms of the user-defined language. Optional variable `PREFIX` specifies the prefix for fresh variable names.

## Example

(use syntax-case matchable varsubst) (define(subst-term t subst k) (match t (('ifc t e) `(if,(k c subst) ,(k t subst) ,(k e subst))) (('letbs e) (k `(let,(map (lambda(b) `(,(car b) ,(k (cadr b) subst))) bs) ,e) subst)) ((f . es) (cons (k f subst) (map (lambda(e) (k e subst)) es))) ((? atom? ) t))) (define(binding? t) (and (list? t) (eq? 'let(car t)) (cdr t))) (define(bind ks vs e) `(let,(zip ks vs) ,e)) (definedriver (subst-driver (lambda(x) (and (symbol? x) x)) binding? identity bind subst-term)) (print (driver `(let((a 1) (b 2)) (+ a (let((a (+ b 5))) (+ a b)))) subst-empty))

## Authors

Ivan Raikov

## Version

- 1.0
- Initial version

## License

Copyright 2008 Ivan Raikov and the Okinawa Institute of Science and Technology.

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

A full copy of the GPL license can be found at <http://www.gnu.org/licenses/>.