Author: sburson Date: Sat Jan 6 18:32:18 2007 New Revision: 1 Added: src/ src/defs.lisp src/gmap.lisp src/new-let.lisp Log: Initial commit. Added: src/defs.lisp ============================================================================== --- (empty file) +++ src/defs.lisp Sat Jan 6 18:32:18 2007 @@ -0,0 +1,17 @@ +;;; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Package: CL-User -*- + +;;; This file is in the public domain. It is provided with ABSOLUTELY +;;; NO WARRANTY. + +(in-package :cl-user) + +(defpackage :new-let + (:use :cl) + (:shadow cl:let cl:cond) + (:export #:let #:cond #:nlet #:bcond)) + +(defpackage :gmap + (:use :cl) + (:export #:gmap) + (:import-from :new-let #:nlet #:bcond)) + Added: src/gmap.lisp ============================================================================== --- (empty file) +++ src/gmap.lisp Sat Jan 6 18:32:18 2007 @@ -0,0 +1,617 @@ +; -*- Mode: Lisp; Syntax: ANSI-Common-Lisp; Package: (GMAP Common-Lisp) -*- +(in-package gmap) + +; +; GMAP, version 3.2, by Scott L. Burson +; +; This file is in the public domain. +; +; The GMAP macro provides a new kind of iteration facility in LISP. +; Basically, it is intended for when you would like to use MAPCAR, but +; can't because the things you want to map over aren't in lists, or you +; need to collect the results of the mapping into something other than a +; list. That is, GMAP is probably the right thing to use when you are +; using iteration to perform the same computation on each element of +; some collection, as opposed to changing your state in some complicated +; way on every iteration of a loop. +; In fact, it's conceptually reasonable to imagine all the iterations of a +; GMAP as happening in parallel, just as you might with MAPCAR. The +; difference is that with GMAP you explicitly say, via keywords, what kinds +; of collections the elements come in and what kind of collection to make +; from the result. For example, the following two expressions are equivalent: +; (mapcar #'foo this-list that-list) and +; (gmap :list #'foo (:list this-list) (:list that-list)) +; The first :list keyword indicates that GMAP is to build a list; the other +; two tell it that this-list and that-list are in fact lists of elements over +; which foo is to be mapped. Other keywords exist besides :list; for +; example, :string, if used as an argument keyword, causes its argument +; to be viewed as a string; the values it "generates" for the function being +; mapped are the successive characters of the string. +; Perhaps the best feature of GMAP is its facility for defining one's own +; keywords. Thus you can adapt it to other kinds of data structures over +; which you would like to iterate. +; +; The overall syntax of GMAP is: +; (gmap <result-spec> <fn> +; <arg-spec-0> +; <arg-spec-1> +; ... ) +; where <fn> is the function being mapped, just like the first argument +; to MAPCAR. The <result-spec> and the <arg-spec-i> are lists, whose first +; element is a keyword indicating the type of result constructor or argument +; generator, and the interpretation of whose subsequent elements depends on +; that type. For example, in: +; (gmap :list #'+ +; (:list '(14 32 51)) +; (:index 3)) +; #'+ is the function to be mapped; +; the result-type of :list specifies that a list is to be constructed containing +; the results; +; the first arg-spec specifies that the first argument to the function +; being mapped will be successive elements of the list '(14 32 51); +; and the second arg-spec says that the second argument will be successive +; integers starting with 3. +; The result, of course, is (17 36 56). +; +; **** Argument generators **** +; Each generator is given one variable in which to maintain its state. We have +; to tell GMAP explicitly how to get from the current value of the state variable +; to a)the value to be generated and b)the next value of the state variable. +; +; The keyword, the first element, of each argument spec tells what kind of +; generator to use. NIL as a keyword specifies that one is defining a generator +; for this instance of GMAP only instead of using one of the predefined ones. +; A NIL-type arg-spec has the following syntax: +; (nil <init> &optional <exitp> <argfn> <nextfn> <let-specs>) +; where <init> is the initial value of the generator's state variable; +; <exitp>, if non-nil, is a function of one argument; when it becomes true of +; [i.e., returns a non-nil value when applied to] the state variable, the +; iteration terminates. If it is absent or nil, this generator has no exit-test. +; If more than one arg-spec supplies an exitp, then the +; first one to finish terminates the entire iteration [just like mapcar, which +; stops when any list runs out]. +; <argfn>, if non-nil, is a function of one argument which is applied to the +; current value of the state variable to get the value the generator actually +; returns on this iteration. +; <nextfn>, if non-nil, is a function of one argument which takes the current +; value of the state variable and returns the next. +; <let-specs> facilitates arbitrary hair and is explained below. +; For example, an arg-spec of (:list foo) is equivalent to +; (nil foo #'null #'car #'cdr) +; where foo is the initial value of the list; #'null is the predicate that says +; when the list has run out; #'car, the argfn, is what is done to the list to +; get the current element; and #'cdr, the nextfn, is what is done to the list +; to get the next list. +; +; An argument generator described this way is conceptually equivalent to +; (let `(state-var ,@<let-specs>) +; #'(lambda () +; (if (<exitp> state-var) +; (*throw 'exit-iteration nil) +; (prog1 (<argfn> state-var) +; (setq state-var (<nextfn> state-var)))))) +; +; Note that if only (nil <init>) is specified, the argument is a constant <init>; +; no more circular-list'ing! +; +; Other predefined argument types include: +; (:constant <value>) +; A more readable version of `(nil <value>)'. +; (:list <list>) +; As shown in examples above: supplies successive elements of <list>. +; (:index <start> &optional <stop> <incr>) +; Provides numbers beginning at <start> and going to (but not including) <stop> +; incrementing by <incr> each time. If <stop> is missing or nil, this generates +; numbers indefinitely. <incr> may be positive or negative and defaults to 1. +; (:index-inc <start> <stop> &optional <incr>) +; "Index, INClusive": like :index, but the numbers generated include <stop>. +; (:vector <vector>) +; Generates successive elements of <vector>. +; (:simple-vector <vector>) +; Generates successive elements of <vector> (which must be simple). +; (:string <string>) +; Generates successive characters of <string>. +; (:simple-string <string>) +; Generates successive characters of <string> (which must be simple). +; (:exp <initial-value> <base>) +; Generates an exponential sequence whose first value is <initial-value>, and +; whose value is multiplied by <base> on each iteration. +; +; **** Result Constructors **** +; Like arg-specs, result-specs begin with a keyword saying what kind of +; constructor to use, i.e., how to put together the results of the function +; being mapped. And again, a keyword of NIL means that no predefined +; constructor is being used. A NIL-type result-spec looks like: +; (nil <init> <resfn> &optional <cleanup> <filterp> <let-specs>) +; where +; <init> is the initial value of the constructor's state variable; +; <resfn> is a function of two arguments, the current value of the state variable +; and the current value returned by the function being mapped; it gives the next +; value of the state variable. +; <cleanup>, if present and non-nil, is a function of one argument that +; translates the final value of the state variable into the value that the GMAP +; actually returns. +; <filterp>, if present and non-nil, is a predicate of one argument; when it is false +; of the current value of the function being mapped, <resfn> is not called on that +; iteration, and the value of the state variable is unchanged. +; <let-specs>, as before, is hairy; I'll get back to it below. +; For example, a res-spec of (:list) is equivalent to +; (nil nil #'(lambda (a b) (cons b a)) #'nreverse) +; -- the state variable starts at nil, gets successive values consed onto it, and +; gets nreversed before being returned. +; +; A result-spec that supplies no arguments may be written without the parens; so +; (:list) and :list are equivalent. +; +; Other predefined result types include: +; :list +; Generates a list, like mapcar, of the values. +; :and +; Returns the first NIL, or the last value if none are NIL. +; :or +; Returns the first non-NIL, or NIL if all values are NIL. +; :sum +; Returns the sum of the values. E.g., to get sum of products, use +; (gmap :sum #'* ...) +; (:array <initial-array>) +; Generates an array of the values. You supply the initial array; the values +; are stored starting with element 0. If the array has a fill pointer, it is +; set upon exit to the number of elements stored. The array itself is returned. +; (:string &optional <length-guess>) +; Generates a string from the values. <length-guess> is the initially allocated +; string size; it defaults to 20. #'array-push-extend is used to append each +; character. +; (:values &rest <result-specs>) +; The function being mapped is expected to return as many values as there are +; result-specs; each value is accumulated separately according to its respective +; result-spec, and finally, all the result values are returned. +; +; **** User-defined argument and result types **** +; A useful feature of GMAP is the provision for the user to define his/her own +; argument generators and result constructors. For example, if in some program you +; commonly iterate over words in a sentence, or lines in an editor buffer, or users +; currently logged on, then define an argument type SENTENCE, or LINES, or USERS. +; And similarly with result-types. The way this is done [which I'm not yet sure is +; entirely satisfactory] is with the two special forms DEF-GMAP-ARG-TYPE and +; DEF-GMAP-RES-TYPE. These have syntax like DEFUN: +; (def-gmap-foo-type <name> (<args>) +; <body>) +; When <name> is seen as the keyword of an arg- or result-spec, and has +; been defined with the appropriate special form, then the function +; #'(lambda (<args>) <body>) is applied to the cdr of the spec; that is, +; the keyword itself has been stripped off. Whatever this returns is interpreted +; as a nil-type spec, except, again, without the keyword "nil". For example, the +; arg-type :list is actually defined by +; (def-gmap-arg-type :list (initial-list) +; `(,initial-list ; init +; #'null #'car #'cdr)) ; exitp, argfn, and resfn +; +; Lists of what arg- and result-types are defined can be found in the variables +; *GMAP-ARG-TYPE-LIST* and *GMAP-RES-TYPE-LIST*. +; +; Now for the promised explanation about let-specs. Sometimes [indeed, fairly +; often] a user-defined type will want to compute values and bind variables +; other than those automatically provided by the iteration. For example, the +; index type goes to some trouble to evaluate its parameters only once. It does +; this by providing a list of specs, i.e., (<var> <value>) pairs, which go into +; a LET that surrounds the entire iteration. Except, that is, for the following +; hack: if you want several dependent initializations, e.g., you want foo to be +; something hairy and bar to be the cdr of foo, you can indicate the dependence +; by the nesting in list structure of the specs: +; ((foo (something-hairy)) +; ((bar (cdr foo)))) +; This will cause a gmap that uses this type to expand into +; (let ((foo (something-hairy))) +; (let ((bar (cdr foo))) +; ... [iteration] ...)) +; For details, see the NLET macro at the end of this file. For examples, +; see some of the types defined herein. + +; Remaining tidbits: +; Many arg- and result-specs take optional parameters, which are defined to do +; something only if both present and non-nil. By "non-nil" here I mean non-nil +; *at expansion time*. +; The function being mapped can itself be nil, subject of course to the above +; considerations; in which case the identity function of the first argument is +; used, and other arguments are ignored. + +; Bugs: +; +; Purists will object to the use of symbols in the keyword package rather than +; the `lisp' package for the arg- and result-types. It would make sense for +; these symbols to come from the package providing the types they refer to; +; among other advantages, this would prevent name collisions (which is, after +; all, the whole point of the package system). Against this very reasonable +; argument is my desire to have it immediately apparent to someone seeing a +; `gmap' form, perhaps for the first time, that it is a macro with somewhat +; unusual syntax; the use of ordinary Lisp symbols (`list', `vector', etc.) +; would tend to disguise this fact. Anyway, there's nothing requiring the arg- +; and result-type names to be in the keyword package; anyone who strongly +; dislikes this is welcome to define names in some other package. + +; The top-level macro. +(defmacro gmap (res-spec fn &rest arg-spec-list) + (gmap>expand fn + (gmap>res-spec-lookup res-spec) + (mapcar #'gmap>arg-spec-lookup arg-spec-list))) + +; This does the real work. +(defun gmap>expand (fn res-specs arg-spec-list) + (let ((param-list + (mapcar #'gmap>param arg-spec-list)) + (result-list (gmap>res>init-clauses res-specs)) + (let-specs (gmap>let-specs arg-spec-list res-specs))) + (let ((one-value-p (null (cdr result-list))) + (fnval-vars (mapcar #'(lambda (ignore) + (declare (ignore ignore)) + (gensym)) + result-list))) + `(nlet ,let-specs + (do (,@param-list + ,@result-list) + ((or ,@(apply #'append (mapcar #'gmap>param>exit-test ; exit test + param-list arg-spec-list))) + ,(gmap>res>cleanup res-specs result-list one-value-p)) + ,(if one-value-p + (if (car fnval-vars) + `(let ((,(car fnval-vars) + ,(apply #'gmap>funcall fn + (mapcar #'gmap>param>arg param-list arg-spec-list)))) + (setq ,(caar result-list) + ,(gmap>res>next (car res-specs) (caar result-list) + (car fnval-vars)))) + #| Null result spec -- just call the function for effect. |# + (apply #'gmap>funcall fn + (mapcar #'gmap>param>arg param-list arg-spec-list))) + `(multiple-value-bind ,fnval-vars + ,(apply #'gmap>funcall fn + (mapcar #'gmap>param>arg param-list arg-spec-list)) + . ,(mapcar #'(lambda (fnval result-pair res-spec) + `(setq ,(car result-pair) + ,(gmap>res>next res-spec (car result-pair) fnval))) + fnval-vars result-list res-specs)))))))) + + +; extract the let-specs. +(defun gmap>let-specs (arg-specs res-specs) + (nconc (mapcan #'fifth arg-specs) (mapcan #'fifth res-specs))) + +; generate the do-variable spec for each argument. +(defun gmap>param (arg-spec) + (let ((param-name (gensym)) + (init (first arg-spec)) + (nextfn (fourth arg-spec))) + `(,param-name + ,init + ,@(if nextfn + `(,(gmap>funcall nextfn param-name)) + nil)))) + +; get the argument to the function being mapped from the do-variable. +(defun gmap>param>arg (param arg-spec) + (let ((param-name (first param)) + (argfn (third arg-spec))) + (gmap>funcall argfn param-name))) + +; get the exit test for the variable. +(defun gmap>param>exit-test (param arg-spec) + (let ((param-name (first param)) + (exitp (second arg-spec))) + (if exitp + `(,(gmap>funcall exitp param-name)) + nil))) + +; get the initial value of the result. +(defun gmap>res>init-clauses (res-specs) + (mapcan #'(lambda (res-spec) (and res-spec (cons (list (gensym) (first res-spec)) nil))) + res-specs)) + +; compute the next value of the result from the current one and the +; current value of the function. +(defun gmap>res>next (res-spec result fnval) + (let ((resfn (second res-spec)) + (filterp (fourth res-spec))) + (if filterp + `(if ,(gmap>funcall filterp fnval) + ,(gmap>funcall resfn result fnval) + ,result) + (gmap>funcall resfn result fnval)))) + +; call the cleanup function on exit. +(defun gmap>res>cleanup (res-specs result-list one-value-p) + (if one-value-p + (gmap>funcall (third (car res-specs)) (caar result-list)) + `(values . ,(mapcar #'(lambda (res-spec result-pair) + (gmap>funcall (third res-spec) (car result-pair))) + res-specs result-list)))) + +; For some reason, the compiler doesn't convert, e.g., (funcall #'car foo) +; to (car foo); thus we lose some efficiency for functions that would normally +; open-code, like car. Hence this function to perform the optimization for it. +(defun gmap>funcall (function &rest args) + (let ((args (copy-list args))) + (cond ((or (null function) (eq function ':id)) + (car args)) + ((and (listp function) + (eq (car function) 'function)) + `(,(cadr function) . ,args)) + (t `(funcall ,function . ,args))))) + + + +(eval-when (:execute :compile-toplevel :load-toplevel) + (defvar *gmap-arg-type-list* nil + "A list of all GMAP arg types that have been defined.") + (defvar *gmap-res-type-list* nil + "A list of all GMAP result types that have been defined.")) + +; define an arg-type. +(defmacro def-gmap-arg-type (name args &body body) + (let ((fn-name (gensym "GMAP-ARG-SPEC-EXPANDER-"))) + `(progn + 'compile + (defun ,fn-name ,args . ,body) + (eval-when (:execute :compile-toplevel :load-toplevel) + (setf (get ',name ':gmap-arg-spec-expander) ',fn-name) + (pushnew ',name *gmap-arg-type-list*))))) + +; define a result-type. +(defmacro def-gmap-res-type (name args &body body) + (let ((fn-name (gensym "GMAP-RES-SPEC-EXPANDER-"))) + `(progn + 'compile + (defun ,fn-name ,args . ,body) + (eval-when (:execute :compile-toplevel :load-toplevel) + (setf (get ',name ':gmap-res-spec-expander) ',fn-name) + (pushnew ',name *gmap-res-type-list*))))) + +; look up an arg type. +(defun gmap>arg-spec-lookup (raw-arg-spec) + (let ((type (car raw-arg-spec))) + (if (null type) + (cdr raw-arg-spec) + (let ((generator (get type ':gmap-arg-spec-expander))) + (if generator + (apply generator (cdr raw-arg-spec)) + (error "Argument spec, ~S, to gmap is of unknown type + (Do you have the package right?)" + raw-arg-spec)))))) + +; look up a result type. +(defun gmap>res-spec-lookup (raw-res-spec) + (if (and (listp raw-res-spec) + (eq (car raw-res-spec) ':values)) + (mapcar #'gmap>res-spec-lookup-1 (cdr raw-res-spec)) + (cons (gmap>res-spec-lookup-1 raw-res-spec) nil))) +(defun gmap>res-spec-lookup-1 (raw-res-spec) + (let ((type (if (listp raw-res-spec) (car raw-res-spec) + raw-res-spec))) + (if (null type) + (cdr raw-res-spec) + (let ((generator (get type ':gmap-res-spec-expander))) + (if generator + (apply generator (and (listp raw-res-spec) (cdr raw-res-spec))) + (error "Result spec, ~S, to gmap is of unknown type + (Do you have the package right?)" + raw-res-spec)))))) + + + +; ******** Predefined argument types ******** +; See above for documentation. + +(def-gmap-arg-type :constant (value) + `(,value)) + +(def-gmap-arg-type :list (initial-list) + `(,initial-list + #'null #'car #'cdr)) + +(def-gmap-arg-type :index (start &optional stop incr) + (let ((incr-temp (gensym)) + (stop-temp (gensym)) + (bounds-fn-temp (gensym))) + `(,start ; init + ,(if stop ; exitp + (if incr + `#'(lambda (val) + (funcall ,bounds-fn-temp val ,stop-temp)) + `#'(lambda (val) (declare (type fixnum val)) + (>= val ,stop-temp))) + 'nil) + nil ; no argfn + ,(if incr ; nextfn + `#'(lambda (val) (declare (type fixnum val)) + (+ val ,incr-temp)) + '#'1+) + (,@(if incr ; and let-specs + `((,incr-temp ,incr) + ((,bounds-fn-temp (if (minusp ,incr-temp) #'<= #'>=))))) + ,@(if stop + `((,stop-temp ,stop))))))) + +(def-gmap-arg-type :index-inc (start &optional stop incr) + (let ((incr-temp (gensym)) + (stop-temp (gensym)) + (bounds-fn-temp (gensym))) + `(,start ; init + ,(if stop ; generate (possibly hairy) exitp + (if incr + `#'(lambda (val) + (funcall ,bounds-fn-temp val ,stop-temp)) + `#'(lambda (val) (declare (type fixnum val)) + (> val ,stop-temp))) + 'nil) + nil ; no argfn + ,(if incr ; nextfn + `#'(lambda (val) (declare (type fixnum val)) + (+ val ,incr-temp)) + '#'1+) + (,@(if incr ; and let-specs + `((,incr-temp ,incr) + ((,bounds-fn-temp (if (minusp ,incr-temp) #'< #'>))))) + ,@(if stop + `((,stop-temp ,stop))))))) + +;;; Deprecated; use `:vector'. +(def-gmap-arg-type :array (array &optional start stop incr) + (let ((array-temp (gensym)) + (incr-temp (and incr (gensym))) + (stop-temp (gensym))) + `(,(or start 0) + #'(lambda (i) (>= i ,stop-temp)) + #'(lambda (i) (aref ,array-temp i)) + #'(lambda (x) (+ x ,(or incr-temp 1))) + ((,array-temp ,array) + ,@(and incr `((,incr-temp ,incr))) + ((,stop-temp ,(or stop `(length ,array-temp)))))))) + +(def-gmap-arg-type :vector (array &optional start stop incr) + (let ((array-temp (gensym)) + (incr-temp (and incr (gensym))) + (stop-temp (gensym))) + `(,(or start 0) + #'(lambda (i) (>= i ,stop-temp)) + #'(lambda (i) (aref ,array-temp i)) + #'(lambda (x) (+ x ,(or incr-temp 1))) + ((,array-temp ,array) + ,@(and incr `((,incr-temp ,incr))) + ((,stop-temp ,(or stop `(length ,array-temp)))))))) + +(def-gmap-arg-type :simple-vector (array &optional start stop incr) + (let ((array-temp (gensym)) + (incr-temp (and incr (gensym))) + (stop-temp (gensym))) + `(,(or start 0) + #'(lambda (i) (declare (type fixnum i)) (>= i ,stop-temp)) + #'(lambda (i) (declare (type fixnum i)) (svref ,array-temp i)) + #'(lambda (i) (declare (type fixnum i)) (+ i ,(or incr-temp 1))) + ((,array-temp ,array) + ,@(and incr `((,incr-temp (the fixnum ,incr)))) + ((,stop-temp (the fixnum ,(or stop `(length ,array-temp))))))))) + +; This is like :array but coerces the object to a string first. +(def-gmap-arg-type :string (string &optional start stop incr) + (let ((string-temp (gensym)) + (incr-temp (and incr (gensym))) + (stop-temp (gensym))) + `(,(or start 0) + #'(lambda (i) (>= i ,stop-temp)) + #'(lambda (i) (char ,string-temp i)) + #'(lambda (x) (+ x ,(or incr-temp 1))) + ((,string-temp (string ,string)) + ,@(and incr `((,incr-temp ,incr))) + ((,stop-temp ,(or stop `(length ,string-temp)))))))) + +(def-gmap-arg-type :simple-string (string &optional start stop incr) + (let ((string-temp (gensym)) + (incr-temp (and incr (gensym))) + (stop-temp (gensym))) + `(,(or start 0) + #'(lambda (i) (>= i ,stop-temp)) + #'(lambda (i) (schar ,string-temp i)) + #'(lambda (x) (+ x ,(or incr-temp 1))) + ((,string-temp (string ,string)) + ,@(and incr `((,incr-temp ,incr))) + ((,stop-temp ,(or stop `(length ,string-temp)))))))) + + +; ******** Predefined result types ******** + +(def-gmap-res-type :list (&optional filterp) + `(nil #'xcons #'nreverse ,filterp)) + +(defun xcons (a b) + (cons b a)) + +(def-gmap-res-type :nconc (&optional filterp) + (let ((result-var (gensym))) ; have to use our own, sigh. + `(nil ; init + #'(lambda (tail-loc new) ; nextfn + (if tail-loc (rplacd tail-loc new) + (setq ,result-var new)) + (if new (last new) tail-loc)) + #'(lambda (ignore) + (declare (ignore ignore)) + ,result-var) + ,filterp + ((,result-var nil))))) + +(def-gmap-res-type :and () + '(t #'(lambda (ignore new) + (declare (ignore ignore)) + (if new new (return nil))))) + +(def-gmap-res-type :or () + '(nil #'(lambda (ignore new) + (declare (ignore ignore)) + (if new (return new) nil)))) + +(def-gmap-res-type :sum () + '(0 #'+)) + +(def-gmap-res-type :count-if () + '(0 #'(lambda (n new) + (if new (1+ n) n)))) + +(def-gmap-res-type :max () + '(nil #'max-with-nil-id)) + +(defun max-with-nil-id (x y) + (if (null x) y + (if (null y) x + (max x y)))) + +(def-gmap-res-type :min () + '(nil #'min-with-nil-id)) + +(defun min-with-nil-id (x y) + (if (null x) y + (if (null y) x + (min x y)))) + +;;; Deprecated; use `:vector'. +(def-gmap-res-type :array (initial-empty-array) + (let ((array-temp (gensym))) + `(0 ; init + #'(lambda (curr-index next-elt) ; nextfn + (setf (aref ,array-temp curr-index) next-elt) + (1+ curr-index)) + #'(lambda (last-index) ; cleanup + (if (array-has-fill-pointer-p ,array-temp) + (setf (fill-pointer ,array-temp) last-index)) + ,array-temp) + nil ; filterp + ((,array-temp ,initial-empty-array))))) ; let-specs + +(def-gmap-res-type :vector (initial-empty-vector) + (let ((vector-temp (gensym))) + `(0 ; init + #'(lambda (curr-index next-elt) ; nextfn + (setf (aref ,vector-temp curr-index) next-elt) + (1+ curr-index)) + #'(lambda (last-index) ; cleanup + (if (vector-has-fill-pointer-p ,vector-temp) + (setf (fill-pointer ,vector-temp) last-index)) + ,vector-temp) + nil ; filterp + ((,vector-temp ,initial-empty-vector))))) ; let-specs + +(def-gmap-res-type :string (&optional (length-guess 20.)) + `((make-array ,length-guess ; init + :element-type :character + :adjustable t :fill-pointer 0) + #'(lambda (string char) ; nextfn + (vector-push-extend char string) + string))) + +(def-gmap-arg-type :exp (initial-value base) + (let ((base-temp (gensym))) + `(,initial-value + nil + nil + #'(lambda (x) (* x ,base-temp)) + ((,base-temp ,base))))) + + +; End of gmap.lisp Added: src/new-let.lisp ============================================================================== --- (empty file) +++ src/new-let.lisp Sat Jan 6 18:32:18 2007 @@ -0,0 +1,327 @@ +(in-package :new-let) + +;;; This file is in the public domain. + +;;; This code implements a new LET macro with expanded syntax and semantics, +;;; a generalization of LET, LET*, and MULTIPLE-VALUE-BIND. Some examples: +;;; +;;; (let ((a (foo)) +;;; ((b (bar a)))) +;;; ...) +;;; +;;; This example illustrates that clause nesting depth is used to indicate +;;; ordering of evaluation and binding. B is bound after A, and its initial +;;; value expression refers to A. +;;; +;;; (let ((a b c (zot)) +;;; ((d (quux a c)) +;;; ((e f (mumble b d)) +;;; (g (mung a)))) +;;; ((h (frobozz c)) +;;; ((i (xyzzy h)))) +;;; (*print-level* 3)) +;;; ...) +;;; +;;; A, B, and C are bound to the first three values of (ZOT), and in parallel, +;;; *PRINT-LEVEL* is bound to 3; then D and H are bound; then E, F, G, and I +;;; are bound. +;;; +;;; As this example illustrates, all bindings at a given nesting level are +;;; done in parallel, with all bindings at a deeper level following. +;;; +;;; Since I like to use multiple values, I find this syntax for binding them +;;; very handy, and I think many will agree. (Those familiar with Dylan +;;; will think that I have borrowed the idea from it, but I wrote the first +;;; version of this macro in 1980.) The value of using nesting to indicate +;;; sequencing will perhaps be less clear. The additional flexibility +;;; provided, compared to LET*, is admittedly rarely of importance in terms +;;; of expressing an idea in fewer keystrokes. Personally, though, I like +;;; being able to indicate clearly the data flow dependences among the +;;; various variables I may be binding in one LET; and I have written LET +;;; expressions of complexity comparable to the second example above. (I +;;; should emphasize that the breaking up of the clauses into groups, as in +;;; that second example, to emphasize their data dependence relationships +;;; is strictly for clarity; in fact, the initial value expression for G, +;;; for instance, is within the scope of H.) +;;; +;;; This code also implements an extension to COND. It is simply this: that +;;; if the predicate expression of a COND clause is a LET form, the scope of +;;; all variables bound by the LET is extended to include the consequent +;;; expressions of the clause. (However, it does not include subsequent +;;; clauses.) This simplifies the writing of somewhat Prolog-like code that +;;; simultaneously tests that an object has a certain structure and binds +;;; variables to parts of that structure in order to do something else. +;;; (In order to be recognized as such, the predicate expression must be +;;; written as a LET form, not a macro invocation that expands to a LET form. +;;; I think this is a feature, but am open to being persuaded otherwise.) +;;; +;;; To use these macros, you must shadow the standard definitions in your +;;; package. This can be done by including the following option clause in +;;; your DEFPACKAGE form: +;;; +;;; (:shadowing-import-from "NEW-LET" "LET" "COND") +;;; +;;; If for some reason you don't want to shadow these, you can access this +;;; version of LET as NLET, and this version of COND as BCOND (the "B" is +;;; for "binding"), by using the following DEFPACKAGE option instead: +;;; +;;; (:import-from "NEW-LET" "NLET" "BCOND") +;;; +;;; Enjoy! +;;; Scott L. Burson 2/18/2005 + + +(defmacro let (clauses &body body) + "A generalization of CL:LET that better supports nested bindings and multiple +values. Syntax: (let (<clause>*) <body>). The <clause> syntax is more general +than for CL:LET: + <clause> ::= <symbol> ; binds to NIL + | ( <symbol> ) ; likewise + | <clause1> + <clause1> ::= ( <symbol>+ <form> ) ; binding + | ( <clause1>+ ) ; nesting +When a clause begins with more than one variable name, they are to be bound to +successive values of the form. The nesting of clauses indicates sequencing of +bindings; more deeply nested clauses may reference bindings of shallower clauses. +All bindings at a given depth are done in parallel. This allows arbitrary +combinations of parallel and sequential binding. Standard declarations at the +head of BODY are handled correctly, though nonstandard ones may not be. If two +variables of the same name are bound at different levels, any declaration +applies to the inner one." + (multiple-value-bind (decls body) + (analyze-decls clauses body) + (car (expand-new-let clauses body decls)))) + +;;; Alternative name for the above. I could have this one expand into that +;;; one, or conversely, but I'd want to duplicate the doc string anyway, and +;;; that's most of the code. +(defmacro nlet (clauses &body body) + "A generalization of CL:LET that better supports nested bindings and multiple +values. Syntax: (let (<clause>*) <body>). The <clause> syntax is more general +than for CL:LET: + <clause> ::= <symbol> ; binds to NIL + | ( <symbol> ) ; likewise + | <clause1> + <clause1> ::= ( <symbol>+ <form> ) ; binding + | ( <clause1>+ ) ; nesting +When a clause begins with more than one variable name, they are to be bound to +successive values of the form. The nesting of clauses indicates sequencing of +bindings; more deeply nested clauses may reference bindings of shallower clauses. +All bindings at a given depth are done in parallel. This allows arbitrary +combinations of parallel and sequential binding. Standard declarations at the +head of BODY are handled correctly, though nonstandard ones may not be. If two +variables of the same name are bound at different levels, any declaration +applies to the inner one." + (multiple-value-bind (decls body) + (analyze-decls clauses body) + (car (expand-new-let clauses body decls)))) + +(defun expand-new-let (clauses body decls) + (labels ((expand-1 (this-level-single this-level-multiple next-level body decls) + (cl:cond ((and this-level-multiple + (null (cdr this-level-multiple)) + (null this-level-single)) + (cl:let ((vars (butlast (car this-level-multiple)))) + (multiple-value-bind (body decls) + (expand-1 nil nil next-level body decls) + (values `((multiple-value-bind ,vars + ,(car (last (car this-level-multiple))) + ,@(bound-decls decls vars) + ,@(and (null next-level) + (mapcar #'(lambda (d) `(declare ,d)) + (cdr decls))) + . ,body)) + (prune-decls decls vars))))) + (this-level-multiple + (let* ((vars (butlast (car this-level-multiple))) + (gensyms (mapcar #'(lambda (x) + (declare (ignore x)) + (gensym)) + vars))) + (multiple-value-bind (body decls) + (expand-1 (append (mapcar #'list vars gensyms) + this-level-single) + (cdr this-level-multiple) next-level body decls) + (values `((multiple-value-bind ,gensyms + ,(car (last (car this-level-multiple))) + ,@(bound-decls decls vars) + ,@(and (null next-level) + (mapcar #'(lambda (d) `(declare ,d)) + (cdr decls))) + . ,body)) + (prune-decls decls vars))))) + (this-level-single + (cl:let ((vars (mapcar #'(lambda (x) (if (consp x) (car x) x)) + this-level-single))) + (multiple-value-bind (body decls) + (expand-1 nil nil next-level body decls) + (values `((cl:let ,this-level-single + ,@(bound-decls decls vars) + ,@(and (null next-level) + (mapcar #'(lambda (d) `(declare ,d)) + (cdr decls))) + . ,body)) + (prune-decls decls vars))))) + (next-level + (expand-new-let next-level body decls)) + (t (values body decls))))) + (multiple-value-bind (this-level-single this-level-multiple next-level) + (split-level clauses nil nil nil) + (expand-1 this-level-single this-level-multiple next-level body decls)))) + +(defun split-level (clauses this-level-single this-level-multiple next-level) + (if (null clauses) + (values (reverse this-level-single) (reverse this-level-multiple) + next-level) + (cl:let ((clause (car clauses))) + (cl:cond ((and (listp clause) (listp (car clause))) + (split-level (cdr clauses) this-level-single this-level-multiple + (append next-level clause))) + ((and (listp clause) (cddr clause)) + (split-level (cdr clauses) this-level-single + (cons clause this-level-multiple) next-level)) + (t + (split-level (cdr clauses) (cons clause this-level-single) + this-level-multiple next-level)))))) + +(defun bound-decls (decls vars) + (let* ((bd-alist (car decls)) + (prs (remove-if-not #'(lambda (pr) (member (car pr) vars)) + bd-alist))) + (and prs `((declare . ,(mapcar #'(lambda (pr) + (if (listp (cdr pr)) + `(,@(cdr pr) ,(car pr)) + `(,(cdr pr) ,(car pr)))) + prs)))))) + +(defun prune-decls (decls vars) + (cl:let ((bd-alist (car decls))) + (cons (remove-if #'(lambda (pr) (member (car pr) vars)) + bd-alist) + (cdr decls)))) + +(defun analyze-decls (clauses body) + "Returns two values. The first value is a cons of: (a) for the bound declarations +at the head of `body', an alist from variable name to a list of declarations +affecting that variable; (b) a list of the remaining (free) declarations. The +second value is `body' with the declarations stripped off." + (labels ((process-declares (body bd-alist free vars) + (if (or (null body) (not (consp (car body))) + (not (eq (caar body) 'declare))) + (values bd-alist free body) + (multiple-value-bind (bd-alist free) + (process-decls (cdar body) bd-alist free vars) + (process-declares (cdr body) bd-alist free vars)))) + (process-decls (decls bd-alist free vars) + (if (null decls) + (values bd-alist free) + (multiple-value-bind (bd-alist free) + (process-decl (car decls) bd-alist free vars) + (process-decls (cdr decls) bd-alist free vars)))) + (process-decl (decl bd-alist free vars) + (cl:cond + ((not (consp decl)) ; defensive programming + (values bd-alist (cons decl free))) + ((member (car decl) '(ignore ignoreable)) + ;; These are always bound. + (values (append (mapcar #'(lambda (x) (cons x (car decl))) + (cdr decl)) + bd-alist) + free)) + ((type-specifier-name? (car decl)) + (process-vars (cdr decl) (list 'type (car decl)) bd-alist free vars)) + ((eq (car decl) 'type) + (process-vars (cddr decl) (list 'type (cadr decl)) bd-alist free vars)) + ((eq (car decl) 'special) + (process-vars (cdr decl) (car decl) bd-alist free vars)) + (t (values bd-alist (cons decl free))))) + (process-vars (decl-vars decl-name bd-alist free vars) + (if (null decl-vars) + (values bd-alist free) + (multiple-value-bind (bd-alist free) + (process-vars (cdr decl-vars) decl-name bd-alist free vars) + (if (member (car decl-vars) vars) + (values (cons (cons (car decl-vars) decl-name) + bd-alist) + free) + (values bd-alist + (cons (list decl-name (car decl-vars)) + free))))))) + (multiple-value-bind (bd-alist free body) + (process-declares body nil nil (new-let-bound-vars clauses)) + (values (cons bd-alist free) body)))) + +(defun new-let-bound-vars (clauses) + (and clauses + (append (cl:let ((clause (car clauses))) + (cl:cond ((symbolp clause) (cons clause nil)) + ((symbolp (car clause)) (butlast clause)) + (t (new-let-bound-vars clause)))) + (new-let-bound-vars (cdr clauses))))) + +(defun type-specifier-name? (x) + (or (member x '(array atom bignum bit bit-vector character compiled-function + complex cons double-float extended-char fixnum float function + hash-table integer keyword list long-float nil null number + package pathname random-state ratio rational real readtable + sequence short-float simple-array simple-bit-vector + simple-string simple-vector single-float standard-char stream + string base-char symbol t vector)) + (find-class x nil))) + + +(defmacro cond (&rest clauses) + "A generalization of CL:COND that makes it convenient to compute a value in +the predicate expression of a clause and then use that value in the consequent. +If the predicate expression is a LET form, then the scope of the variables bound +by the LET is extended to include the consequent expressions. For example: + + (cond ((let ((x (foo))) + (bar x)) + (baz x))) + +Here the X in (BAZ X) is the one bound to the result of (FOO)." + (cl:let ((block-nm (gensym))) + `(block ,block-nm + . ,(mapcar #'(lambda (c) (bcond-clause c block-nm)) clauses)))) + +(defmacro bcond (&rest clauses) + "A generalization of CL:COND that makes it convenient to compute a value in +the predicate expression of a clause and then use that value in the consequent. +If the predicate expression is a LET form, then the scope of the variables bound +by the LET is extended to include the consequent expressions. For example: + + (cond ((let ((x (foo))) + (bar x)) + (baz x))) + +Here the X in (BAZ X) is the one bound to the result of (FOO)." + (cl:let ((block-nm (gensym))) + `(block ,block-nm + . ,(mapcar #'(lambda (c) (bcond-clause c block-nm)) clauses)))) + +(defun bcond-clause (clause block-nm) + (cl:cond ((not (listp clause)) + (error "COND clause is not a list: ~S" clause)) + ((and (listp (car clause)) + ;; Allow NLET and CL:LET in case the user hasn't chosen + ;; to shadow LET. + (member (caar clause) '(let nlet cl:let))) + (bcond-build-clause (caar clause) (cadar clause) + `(progn . ,(cddar clause)) + (cdr clause) block-nm)) + (t + (bcond-build-clause nil nil (car clause) (cdr clause) block-nm)))) + +(defun bcond-build-clause (let-sym let-clauses pred consequents block-nm) + (cl:let ((body (if consequents + `(if ,pred (return-from ,block-nm (progn . ,consequents))) + (cl:let ((temp-var (gensym))) + `(cl:let ((,temp-var ,pred)) + (if ,temp-var (return-from ,block-nm ,temp-var))))))) + (if let-clauses + `(,let-sym ,let-clauses ,body) + body))) + + +