varsubst

Note: This is taken from the Chicken Wiki, where a more recent version could be available.

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

Using string comparison because equal? on the same symbols sometimes fails.

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