chickadee » varsubst

Outdated egg!

This is an egg for CHICKEN 4, the unsupported old release. You're almost certainly looking for the CHICKEN 5 version of this egg, if it exists.

If it does not exist, there may be equivalent functionality provided by another egg; have a look at the egg index. Otherwise, please consider porting this egg to the current version of CHICKEN.

varsubst

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 parameterized substitution procedure.

Library procedures

subst?:procedure

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

subst-empty:procedure

Returns an empty substitution environment.

subst-empty?:procedure

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

subst-includes?:procedure

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

subst-lookup:procedure

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

subst-extend:procedure

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

subst-remove:procedure

Removes all bindings with key K from the given substitution environment and returns the resulting substitution environment.

subst-map:procedure

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:procedure

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.3
Added subst-remove
1.2
Ported to Chicken 4
1.1
Using string comparison because equal? on the same symbols sometimes fails.
1.0
Initial version

License

Copyright 2008-2012 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/>.

Contents »