Commits

Anonymous committed 934f45d

Place in public domain. Convert CRLF -> LF in README.

Comments (0)

Files changed (8)

-The Arboretuum Programming Language
-===================================
-
-March 2008, Chris Pressey, Cat's Eye Technologies.
-
-Description
------------
-
-Arboretuum is a language based on an experimental variant of
-tree-rewriting which we call forest-rewriting. Appropriate to its name,
-during forest-rewriting, multiple trees (specifically, a finite set) are
-rewritten. Each tree is labelled with a name; a rewriting pattern can
-refer to multiple trees, and must match all of them simultaneously in
-order for a replacement to occur.
-
-As an experiment, Arboretuum was not entirely a success.
-Forest-rewriting unfortunately turned out to be insufficient for what I
-wanted to apply it to, namely compiler specification. The idea was to
-have each tree associated with some data structure used in the
-compilation process (AST, symbol table, output buffer, etc.) However, it
-became apparent that, by itself, forest-rewriting could not synchronize
-the data across the trees the way it would need to be synchronized in a
-real compiler. I plan to tackle the problem again, with a different
-variation on rewriting, in a future project.
-
-Regardless, Arboretuum is Turing-complete, as tree-rewriting is simply a
-special case of forest-rewriting: just have one tree in the forest.
-
-Implementation
---------------
-
-I will refer you to the reference implementation of Arboretuum for
-details on the semantics of the language. Ordinarily I frown upon this
-sort of practice — normatively defining a language by an implementation
-rather than by a specification — but the interests of brevity, the
-experimental tack of the project, the unsuccessful outcome of the
-experiment, and the relative well-definedness of the implementation
-language (the purely functional subset of R5RS Scheme) conspire to
-make the consequences of this choice less painful than usual.
-
-The reference implementation comprises the following files:
-
--   `preprocess.scm`
-
-    Pre-processes the input program into an internal format suitable for
-    forest-rewriting.
-
--   `unify.scm`
-
-    Implementation of the unification algorithm which is used to match
-    the pattern part of rewriting rules to the forest.
-
--   `forest-rewrite.scm`
-
-    Implements the forest-rewriting process proper.
-
--   `utils.scm`
-
-    Miscellanous support procedures, including `mergesort`,
-    `vector-store` (a side-effect-free alternative to `vector-set!`),
-    `print` and `test`.
-
-In addition, the following supplementary files which are not definitive
-w.r.t. the Arboretuum language are included in the project:
-
--   `tests.scm`
-
-    Gives a set of unit tests to confirm the absence of certain
-    erroneous behaviours. (Obviously, no number of unit tests could
-    confirm the absence of *errors*...)
-
--   `tree-rewrite.scm`
-
-    Some basic tree-rewriting code, to provide contrast between it's
-    complexity and that of forest rewriting.
-
-Note that the Scheme implementation of algorithms in the above files are
-to be taken as *pedantic* rather than *efficient*. They are meant to be
-read (perhaps even enjoyed?) and only incidentally to be executed.
-
-History
--------
-
-This project was begun in January 2006. I'd been meaning to release it
-for a while before actually doing so in March of 2008.
-
-Happy forest-rewriting!
-
--Chris Pressey  
-Cat's Eye Technologies  
-March 4, 2008  
-Chicago, Illinois, USA
+The Arboretuum Programming Language
+===================================
+
+March 2008, Chris Pressey, Cat's Eye Technologies.
+
+Description
+-----------
+
+Arboretuum is a language based on an experimental variant of
+tree-rewriting which we call forest-rewriting. Appropriate to its name,
+during forest-rewriting, multiple trees (specifically, a finite set) are
+rewritten. Each tree is labelled with a name; a rewriting pattern can
+refer to multiple trees, and must match all of them simultaneously in
+order for a replacement to occur.
+
+As an experiment, Arboretuum was not entirely a success.
+Forest-rewriting unfortunately turned out to be insufficient for what I
+wanted to apply it to, namely compiler specification. The idea was to
+have each tree associated with some data structure used in the
+compilation process (AST, symbol table, output buffer, etc.) However, it
+became apparent that, by itself, forest-rewriting could not synchronize
+the data across the trees the way it would need to be synchronized in a
+real compiler. I plan to tackle the problem again, with a different
+variation on rewriting, in a future project.
+
+Regardless, Arboretuum is Turing-complete, as tree-rewriting is simply a
+special case of forest-rewriting: just have one tree in the forest.
+
+Implementation
+--------------
+
+I will refer you to the reference implementation of Arboretuum for
+details on the semantics of the language. Ordinarily I frown upon this
+sort of practice — normatively defining a language by an implementation
+rather than by a specification — but the interests of brevity, the
+experimental tack of the project, the unsuccessful outcome of the
+experiment, and the relative well-definedness of the implementation
+language (the purely functional subset of R5RS Scheme) conspire to
+make the consequences of this choice less painful than usual.
+
+The reference implementation comprises the following files:
+
+-   `preprocess.scm`
+
+    Pre-processes the input program into an internal format suitable for
+    forest-rewriting.
+
+-   `unify.scm`
+
+    Implementation of the unification algorithm which is used to match
+    the pattern part of rewriting rules to the forest.
+
+-   `forest-rewrite.scm`
+
+    Implements the forest-rewriting process proper.
+
+-   `utils.scm`
+
+    Miscellanous support procedures, including `mergesort`,
+    `vector-store` (a side-effect-free alternative to `vector-set!`),
+    `print` and `test`.
+
+In addition, the following supplementary files which are not definitive
+w.r.t. the Arboretuum language are included in the project:
+
+-   `tests.scm`
+
+    Gives a set of unit tests to confirm the absence of certain
+    erroneous behaviours. (Obviously, no number of unit tests could
+    confirm the absence of *errors*...)
+
+-   `tree-rewrite.scm`
+
+    Some basic tree-rewriting code, to provide contrast between it's
+    complexity and that of forest rewriting.
+
+Note that the Scheme implementation of algorithms in the above files are
+to be taken as *pedantic* rather than *efficient*. They are meant to be
+read (perhaps even enjoyed?) and only incidentally to be executed.
+
+History
+-------
+
+This project was begun in January 2006. I'd been meaning to release it
+for a while before actually doing so in March of 2008.
+
+Happy forest-rewriting!
+
+-Chris Pressey  
+Cat's Eye Technologies  
+March 4, 2008  
+Chicago, Illinois, USA
+This is free and unencumbered software released into the public domain.
+
+Anyone is free to copy, modify, publish, use, compile, sell, or
+distribute this software, either in source code form or as a compiled
+binary, for any purpose, commercial or non-commercial, and by any
+means.
+
+In jurisdictions that recognize copyright laws, the author or authors
+of this software dedicate any and all copyright interest in the
+software to the public domain. We make this dedication for the benefit
+of the public at large and to the detriment of our heirs and
+successors. We intend this dedication to be an overt act of
+relinquishment in perpetuity of all present and future rights to this
+software under copyright law.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
+OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
+ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+OTHER DEALINGS IN THE SOFTWARE.
+
+For more information, please refer to <http://unlicense.org/>

src/forest-rewrite.scm

 ; Forest Rewriting
 ; Chris Pressey, late January 2006
 ;
-
-; Copyright (c)2008 Cat's Eye Technologies.  All rights reserved.
+; This work is in the public domain.  See the file UNLICENSE for more
+; information.
 ;
-; Redistribution and use in source and binary forms, with or without
-; modification, are permitted provided that the following conditions
-; are met:
-;
-; 1. Redistributions of source code must retain the above copyright
-;    notices, this list of conditions and the following disclaimer.
-; 2. Redistributions in binary form must reproduce the above copyright
-;    notices, this list of conditions, and the following disclaimer in
-;    the documentation and/or other materials provided with the
-;    distribution.
-; 3. Neither the names of the copyright holders nor the names of their
-;    contributors may be used to endorse or promote products derived
-;    from this software without specific prior written permission. 
-;
-; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-; ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
-; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
-; FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
-; COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
-; INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
-; BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-; CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
-; ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-; POSSIBILITY OF SUCH DAMAGE.
 
 ;
 ; Given a term, a pattern to look for in that term, a replacement pattern,

src/preprocess.scm

 ; Preprocessor for Forest Rewriter
 ; Chris Pressey, sometime late January 2006
 ;
-
-; Copyright (c)2008 Cat's Eye Technologies.  All rights reserved.
+; This work is in the public domain.  See the file UNLICENSE for more
+; information.
 ;
-; Redistribution and use in source and binary forms, with or without
-; modification, are permitted provided that the following conditions
-; are met:
-;
-; 1. Redistributions of source code must retain the above copyright
-;    notices, this list of conditions and the following disclaimer.
-; 2. Redistributions in binary form must reproduce the above copyright
-;    notices, this list of conditions, and the following disclaimer in
-;    the documentation and/or other materials provided with the
-;    distribution.
-; 3. Neither the names of the copyright holders nor the names of their
-;    contributors may be used to endorse or promote products derived
-;    from this software without specific prior written permission. 
-;
-; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-; ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
-; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
-; FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
-; COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
-; INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
-; BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-; CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
-; ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-; POSSIBILITY OF SUCH DAMAGE.
 
 ;
 ; The goal here is to allow the compound-rules to be specified in a nicer,
 ; Test suite for forest-rewriting project
 ; Chris Pressey, sometime late January 2006
 ;
-
-; Copyright (c)2008 Cat's Eye Technologies.  All rights reserved.
+; This work is in the public domain.  See the file UNLICENSE for more
+; information.
 ;
-; Redistribution and use in source and binary forms, with or without
-; modification, are permitted provided that the following conditions
-; are met:
-;
-; 1. Redistributions of source code must retain the above copyright
-;    notices, this list of conditions and the following disclaimer.
-; 2. Redistributions in binary form must reproduce the above copyright
-;    notices, this list of conditions, and the following disclaimer in
-;    the documentation and/or other materials provided with the
-;    distribution.
-; 3. Neither the names of the copyright holders nor the names of their
-;    contributors may be used to endorse or promote products derived
-;    from this software without specific prior written permission. 
-;
-; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-; ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
-; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
-; FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
-; COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
-; INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
-; BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-; CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
-; ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-; POSSIBILITY OF SUCH DAMAGE.
 
 
 (load "utils.scm");--------------------------------------------------------

src/tree-rewrite.scm

 ; Bottom-Up Tree-Rewriting (Term-Rewriting)
 ; Chris Pressey, sometime late January 2006
 ;
-
-; Copyright (c)2008 Cat's Eye Technologies.  All rights reserved.
+; This work is in the public domain.  See the file UNLICENSE for more
+; information.
 ;
-; Redistribution and use in source and binary forms, with or without
-; modification, are permitted provided that the following conditions
-; are met:
-;
-; 1. Redistributions of source code must retain the above copyright
-;    notices, this list of conditions and the following disclaimer.
-; 2. Redistributions in binary form must reproduce the above copyright
-;    notices, this list of conditions, and the following disclaimer in
-;    the documentation and/or other materials provided with the
-;    distribution.
-; 3. Neither the names of the copyright holders nor the names of their
-;    contributors may be used to endorse or promote products derived
-;    from this software without specific prior written permission. 
-;
-; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-; ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
-; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
-; FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
-; COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
-; INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
-; BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-; CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
-; ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-; POSSIBILITY OF SUCH DAMAGE.
 
 ;
 ; Try unifying the pattern part of the given rule with the given term;
 ; Simple support for unification & pattern matching
 ; Chris Pressey, late January 2006
 ;
-
-; Copyright (c)2008 Cat's Eye Technologies.  All rights reserved.
+; This work is in the public domain.  See the file UNLICENSE for more
+; information.
 ;
-; Redistribution and use in source and binary forms, with or without
-; modification, are permitted provided that the following conditions
-; are met:
-;
-; 1. Redistributions of source code must retain the above copyright
-;    notices, this list of conditions and the following disclaimer.
-; 2. Redistributions in binary form must reproduce the above copyright
-;    notices, this list of conditions, and the following disclaimer in
-;    the documentation and/or other materials provided with the
-;    distribution.
-; 3. Neither the names of the copyright holders nor the names of their
-;    contributors may be used to endorse or promote products derived
-;    from this software without specific prior written permission. 
-;
-; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-; ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
-; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
-; FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
-; COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
-; INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
-; BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-; CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
-; ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-; POSSIBILITY OF SUCH DAMAGE.
 
 ;
 ; Return #t if the given pattern is a variable, #f otherwise.
 ; Utility functions used by forest-rewriting project
 ; Chris Pressey, late January 2006
 ;
-
-; Copyright (c)2008 Cat's Eye Technologies.  All rights reserved.
+; This work is in the public domain.  See the file UNLICENSE for more
+; information.
 ;
-; Redistribution and use in source and binary forms, with or without
-; modification, are permitted provided that the following conditions
-; are met:
-;
-; 1. Redistributions of source code must retain the above copyright
-;    notices, this list of conditions and the following disclaimer.
-; 2. Redistributions in binary form must reproduce the above copyright
-;    notices, this list of conditions, and the following disclaimer in
-;    the documentation and/or other materials provided with the
-;    distribution.
-; 3. Neither the names of the copyright holders nor the names of their
-;    contributors may be used to endorse or promote products derived
-;    from this software without specific prior written permission. 
-;
-; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-; ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
-; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
-; FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
-; COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
-; INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
-; BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-; CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
-; ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-; POSSIBILITY OF SUCH DAMAGE.
 
 ;
 ; Sort a list using mergesort.