Introduction (historical revision 11255)

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
	 (('if c t e)
	  `(if ,(k c subst) ,(k t subst) ,(k e subst)))
	 (('let bs 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))

(define driver  (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

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/>.