Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 27 Apr 87 15:09:04 EDT Date: Mon, 27 Apr 87 14:58:50 EDT From: Jonathan A Rees Subject: match questions To: cth@IUCS.CS.INDIANA.EDU cc: rrrs-authors@MC.LCS.MIT.EDU In-reply-to: Msg of Wed 22 Apr 87 14:53:10 est from Chris Haynes Message-ID: <191716.870427.JAR@AI.AI.MIT.EDU> Date: Wed, 22 Apr 87 14:53:10 est From: Chris Haynes 7. Should MATCH be required, optional, or "Yellow Pages". Yellow pages. Let's get macros into the language so that this is possible! Received: from STONY-BROOK.SCRC.Symbolics.COM (TCP 30002424620) by MC.LCS.MIT.EDU 26 Apr 87 15:56:53 EDT Received: from RIO-DE-JANEIRO.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 124764; Sun 26-Apr-87 15:55:20 EDT Date: Sun, 26 Apr 87 15:54 EDT From: Kent M Pitman Subject: match questions To: cth@iucs.cs.indiana.edu cc: rrrs-authors@mc.lcs.mit.edu In-Reply-To: The message of 22 Apr 87 15:53 EDT from Chris Haynes Message-ID: <870426155448.6.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM> When you say you think we want a matcher, does the "we" refer to Scheme designers or to Scheme users? In my experience, users want virtually anything that will save them work. So any user who's got a matching problem would want a matcher. Of course, users get to wipe clean their assumptions every time they start over on a new project so they tend to have a more short-sighted view of things. On the other hand, a language designer is pretty much stuck with anything he puts in his language forever after. For that reason, he must be more particular. If you're thinking of adding a match facility to Scheme, you must first decide at what level you were going to add it. If you add it as linguistic glue (as, for example, in Prolog), you have a lot of work ahead of you figuring out how to weave it into the fabric of the language so that it doesn't end up feeling hastily tacked on. If you just want to add a tool that isn't integrated at the glue level, you should be ready to justify why you chose to add that tool and not the myriad of other possible tools that Common Lisp and company have adopted while Scheme has steadfastly shunned as contrary to the goals of a simple and elegant language. By the way, Jonathan has convinced me that a graceful matcher is possible so I'm not trying to talk you completely out of it. I just think there's no good argument for it being anywhere but in the Yellow Pages unless you're willing to go the extra mile and make the language really use it at a very low level... and I don't see anyone going that extra mile (nor do I expect that if they did the others would accept it). Received: from Sushi.Stanford.EDU (TCP 4402000065) by MC.LCS.MIT.EDU 24 Apr 87 21:18:56 EDT Date: Fri 24 Apr 87 18:22:11-PDT From: Andy Freeman Subject: Re: match questions To: wand%corwin.ccs.northeastern.edu@RELAY.CS.NET cc: rrrs-authors@MC.LCS.MIT.EDU, cth%indiana.csnet@RELAY.CS.NET In-Reply-To: Message from "wand%corwin.ccs.northeastern.edu@RELAY.CS.NET" of Fri 24 Apr 87 17:07:43-PDT Message-ID: <12297190001.12.ANDY@Sushi.Stanford.EDU> Before I forget. I don't think structures are a counter-proposal to matchers. They're for problems that matchers aren't the right tool for and are completely inappropriate for the things that matchers do best. Actually, I was serious about the hokey accessor syntax award. I don't like it, there are lots of better syntaxes, but it does illustrate my point. The following defstruct only defines a predicate function and accessor syntax. (defstruct (branch left right) (left (or leaf branch)) (right (or leaf branch))) The predicate is branch? and the accessor syntax "verb" is branch. (branch tree left) is syntax for accessing the left of tree's value (which is a branch), but left isn't evaluated. (This order obviously has problems.) Left is recognized as a field name in that position by the branch accessor syntax. Other structs can have a left and left can be used for other purposes without confusion. Yes, each instance of a struct in my proposal does add three names to the namespace, but that's independent of the number of fields. (I didn't mention creators.) On the other hand, one could define a create syntax, (create branch left x right y), so that no creator name is added to the namespace. This create would be global syntax that recognizes struct names and fields. Similar games can be played with accessor syntax and predicates so that no names are added to the namespace by a definition. (I think they'd be silly, but ....) I don't understand the less-local objection. Either you know what you want out of the struct or you don't. Matchers rely on positional notation, structures rely on names. The real bug with my proposal is that any user of a structure can see everything in it; matchers have this problem too. "private" fields and the like are the solution, but I don't have a syntax. -andy ------- Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 24 Apr 87 19:53:45 EDT Received: from relay2.cs.net by RELAY.CS.NET id aa00914; 24 Apr 87 20:05 EDT Received: from northeastern.edu by RELAY.CS.NET id ab03143; 24 Apr 87 20:00 AST Received: from corwin.ccs.northeastern.edu by nuhub.acs.northeastern.edu; Fri, 24 Apr 87 16:37 EST Received: by corwin.CCS.Northeastern.EDU (5.51/5.17) id AA04605; Fri, 24 Apr 87 10:31:40 AST Date: Fri, 24 Apr 87 10:31:40 AST From: wand%corwin.ccs.northeastern.edu@RELAY.CS.NET To: ANDY@SUSHI.STANFORD.EDU Cc: rrrs-authors@MC.LCS.MIT.EDU, cth%indiana.csnet@RELAY.CS.NET In-Reply-To: "Andy Freeman"'s message of Thu 23 Apr 87 15:36:18-PDT Subject: match questions Much as I like pattern matching as proposed by Chris, I think Andy may be on to something, though I don't completely understand it. treenum ::= Leaf num | Branch treenum treenum sumtree :: treenum -> num sumtree (Leaf x) = x sumtree (Branch xt yt) = sumtree xt + sumtree yt To my mind, the following commonlispish program is superior. For one thing, I can change the things that are in a branch without changing the sumtree program. Note the absense of positional notation/ information. (defstruct (leaf weight) (weight number)) ;;; since this is lisp, type decls are optional (defstruct (branch left right) (right (or leaf branch)) (left (or leaf branch))) ; This may win the hokiest accessor syntax award but it does ; suggest an obvious extension if multiple values are introduced.... (define (sumtree tree) (cond ((leaf? tree) (leaf tree weight)) ((branch? tree) (+ (sumtree (branch tree left)) (sumtree (branch tree right)))) (else ))) I guess I don't completely understand this. If I understand it, the second defstruct exports the following global definitions: [Let's not argue about the word "global" and what happens if the defstruct appears in an interior scope, OK?] branch? branch left right I guess I don't understand why there is both "branch" and "left/right" here. If I understand it correctly, I couldn't have another defstruct that had a different "left". Is that right? What Chris and I most commonly use matching for is as a rough-and-ready device for decomposing variant record structures. In general, one needs an interface between the design of the record structure and the code that uses that design. There are a number of conflicting design goals: 1. Locality of reference. The code that uses the record should be readable without reference to a textually-distant definition of the record structure. 2. Control of the namespace. The interface should garbage as little of the global namespace as possible. Pattern-matching scores heavily on both these counts; in particular, it uses no globally named access functions. Andy's proposal seems deficient, though again I'm not sure I understand it. 3. Modifiability. Changes in the record definition should not require rewriting the code that uses that definition. This is where pattern-matching loses: user code must be rewritten whenever fields are reordered or added. This is where defstruct's (eg Common Lisp's) are on the right track. Reordering or adding fields does not require recoding of user functions. Common Lisp defstruct (and Chez Scheme define-structure) also do pretty well on the side of not garbaging the global namespace: the names of the access functions form a distinguished sublanguage (identifiers of the form structname-fieldname, though I'd probably prefer structname->fieldname), so the only "really global" identifiers established are structname (and structname?). I think it is possible to get something at a higher level than defstruct that still has the right properties, while increasing locality of reference, but I haven't figured it out well enough to share it quite yet. --Mitch Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 23 Apr 87 22:54:52 EDT Date: Thu, 23 Apr 87 23:12:36 EDT From: Jonathan A Rees Subject: The verdict: 27-28 June To: rrrs-authors@MC.LCS.MIT.EDU Message-ID: <190062.870423.JAR@AI.AI.MIT.EDU> Many more people seem to dislike 2-3 July than dislike 27-28 June. Therefore, since no one else seems to be stepping forward to take responsibility, I have reserved the MIT EECS Dept.'s Grier Room for 9 am to 5 pm on Saturday 27 and Sunday 28 June. My apologies to those of you who can't make it then. You should feel free to try to work out a different date with the group if you want; I certainly have no more claim to authority than anyone else on this matter, nor do I want it.... Jonathan Received: from Sushi.Stanford.EDU (TCP 4402000065) by MC.LCS.MIT.EDU 23 Apr 87 20:02:16 EDT Date: Thu 23 Apr 87 15:36:18-PDT From: Andy Freeman Subject: Re: match questions To: rrrs-authors@MC.LCS.MIT.EDU In-Reply-To: Message from "Chris Haynes " of Thu 23 Apr 87 14:33:37-PDT Message-ID: <12296897659.45.ANDY@Sushi.Stanford.EDU> I think that all of the scheme match proposals I've seen during the last two weeks, as well as Miranda and other languages favored by the functional programming community and logic programming languages (any other oxen to gore?), confuse some things that I work very hard to keep separate. Unfortunately, I don't have a word for them, but I can illustrate my point with one of Wadler's examples. He wrote: treenum ::= Leaf num | Branch treenum treenum sumtree :: treenum -> num sumtree (Leaf x) = x sumtree (Branch xt yt) = sumtree xt + sumtree yt To my mind, the following commonlispish program is superior. For one thing, I can change the things that are in a branch without changing the sumtree program. Note the absense of positional notation/ information. (defstruct (leaf weight) (weight number)) ;;; since this is lisp, type decls are optional (defstruct (branch left right) (right (or leaf branch)) (left (or leaf branch))) ; This may win the hokiest accessor syntax award but it does ; suggest an obvious extension if multiple values are introduced.... (define (sumtree tree) (cond ((leaf? tree) (leaf tree weight)) ((branch? tree) (+ (sumtree (branch tree left)) (sumtree (branch tree right)))) (else ))) (Yes, some people want to push the cond into the function calling mechanism but since I usually have procedures with multiple arguments, I don't like to go that far.) One "feature" of this idea is that it doesn't support "generic" information, ie things that are common to a number of different "type", such as printer, since the accessors specify the "type." This suggests that T's limited object-oriented style is a big win because it allows (left tree) to do the right thing even though lots of "types" have a "left." On the other hand, perhaps common/inherited components are rare enough that they should be handled via a separate mechanism. I agree that T's destructure, and match-like generalizations of it, are great, but they're for different problems. I'd rather use a different hammer for compound-object problems. -andy ------- Received: from iucs.cs.indiana.edu (TCP 30003147315) by MC.LCS.MIT.EDU 23 Apr 87 17:02:54 EDT Date: Thu, 23 Apr 87 16:20:27 est From: Chris Haynes To: rrrs-authors@mc.lcs.mit.edu Subject: match questions From: "Guillermo J. Rozas" I'm sorry, but I fail to see the point of a MATCH extension to the language. Every time I've wanted pattern matching, I've built my own, because the constraints and requirements were different, so a fixed utility would do me no good. My experience, which reflects what I've done with Scheme (I've never written an emacs), is simply different. I've seldom felt the need for optional arguments, and never a pressing need for more than the '.' rest feature we already have. Thus my don't care attitude toward the optional argument proposals, except for a general desire that all that mechanism not be added to the language when I don't expect to use it. But I respect the desires of the many who do use optional arguments, at least as long as the facility is optional. What I don't understand is why more people don't find use for MATCH (or maybe they do, and we just haven't heard from them). I find a constant need for destructuring (I hate car/cdr chains), and frequent need for matching. Many a COND expression would look better if it were a MATCH expression. I, and others here, have found the simple sort of match facility I've outlined to be quite adequate for almost all our needs. And people seldom build their own matches, but instead use car/cdr chains and COND at every turn. The functional programming community (broadly speaking, including languages like ML) certainly goes for matching in a big way (and not optional arguments). Why is the Lisp community traditionally so different? We might as well try to agree on a UNIFY facility. It would probably be more useful. Not at all. Unification requires logic variables, which are a significant semantic addition to any language (whereas MATCH is semantically trivial). Also, it isn't clear how much unification is worth without backtracking (multiple values, Prolog style), and that is pretty clearly a step into another language. Chris Received: from iucs.cs.indiana.edu (TCP 30003147315) by MC.LCS.MIT.EDU 23 Apr 87 16:25:00 EDT Date: Thu, 23 Apr 87 15:29:04 est From: Chris Haynes To: philbin-jim@YALE.ARPA Cc: rrrs-authors@mc.lcs.mit.edu In-Reply-To: James F Philbin's message of Thu, 16 Apr 87 17:31:11 EDT <8704162131.AA11569@yale-celray.arpa> Subject: Scheme pattern matcher For those who would like to look at and perhaps try out a simple match facility, here's mine. The Scheme84 MATCH has a bit different syntax and a very different implementation, due to Bruce Duba. He uses Eugene's extend-syntax in clever ways to compile MATCH expressions to conditional expressions (rather than the interpretive approach I use). It is available via anonymous ftp as part of pub/scheme84/synstd.s on cs.indiana.edu. ;; match: Chez Scheme pattern matching and destructuring facility. ;; ;; Author: Chris Haynes (haynes@cs.indiana.edu) ;; ;; ;; (match ( ...) ...) ;; ;; ::= ;; | | | | | (quote ) ;; | #( ...) ;; | #& ; Chez Scheme box (reference) ;; | (? ) ;; | ( ...) ;; | ( ... . ) ;; ;; MATCH is a fairly general pattern matching and destructuring ;; facility. is evaluated and its value is matched against the ;; s in order until a matching pattern is found. An error is ;; signaled if no pattern matches. When a match is found, the value ;; of is destructured with the variables in the matching pattern ;; bound to the corresponding components of 's value. The ;; expressions of the matching pair are then evaluated in an ;; environment formed by extending the environment of the MATCH ;; expression with these new bindings. The value of the last ;; expression is returned as the value of the MATCH expression. ;; ;; The symbols QUOTE and ? are used in patterns to identify literals ;; and predicate tests, so they may not be used as pattern variables. ;; Number, string, boolean, character and quoted literal s must ;; be EQUAL? to corresponding components of s value, or the ;; pattern fails. expressions should evaluate (in the ;; environment of the MATCH expression) to unary functions that are ;; applied to the corresponding component of s value when ;; matching of the ? pattern is attempted. If the predicate returns ;; false, the pattern fails. Otherwise, the value applied to the ;; predicate is matched against the pattern following the predicate. ;; ;; ;; (match '(2 . 3) ((a . b) (* a b))) ==> 6 ;; ;; (match '(1 2) ((a) a) ((a b) (+ a b)) (c c)) ==> 3 ;; ;; (match (list 33 "string" #\c (not #t) #(1 2)) ;; ((33 "string" #\c #f #(a b)) (cons a b))) ==> (1 . 2) ;; ;; (let ((num 3)) ;; (match (cons 'x 4) ;; (((? (lambda (v) (or (symbol? v) (and (number? v) (= v num)))) ;; c) ;; . (? number? d)) (list c d)))) ==> (x 4) ;; ;; (match '(bar 3 4 5) ;; (('foo x y) (cons x y)) ;; (('bar x y . z) (list x y z)) ;; (else (error "didn't match: " else))) ==> (3 4 (5)) ;; (define matcher (lambda (exp pairs-info) (if (null? pairs-info) (error 'match "no pattern for: ~s" exp) (let ((pat (caar pairs-info)) (fn (cadar pairs-info)) (preds (cddar pairs-info)) (fail (lambda () (matcher exp (cdr pairs-info))))) (let loop ((exp exp) (pat pat) (succeed (lambda (args) (apply fn args)))) (cond ((or (null? pat) (number? pat) (char? pat) (string? pat) (boolean? pat)) (if (equal? pat exp) (succeed '()) (fail))) ((symbol? pat) (succeed (list exp))) ((box? pat) (if (box? exp) (loop (unbox exp) (unbox pat) succeed) (fail))) ((vector? pat) (if (vector? exp) (let ((len (vector-length pat))) (if (= len (vector-length exp)) (let inner ((n 0) (args '())) (if (= n len) (succeed args) (loop (vector-ref exp n) (vector-ref pat n) (lambda (car-args) (inner (+ 1 n) (append! args car-args)))))) (fail))) (fail))) ((eq? (car pat) 'quote) (if (equal? (cadr pat) exp) (succeed '()) (fail))) ((eq? (car pat) '?) (if ((car preds) exp) (begin (set! preds (cdr preds)) (loop exp (caddr pat) succeed)) (fail))) ((pair? exp) (loop (car exp) (car pat) (lambda (car-args) (loop (cdr exp) (cdr pat) (lambda (cdr-args) (succeed (append! car-args cdr-args))))))) (else (fail)))))))) (define-macro! match (exp . pairs) (let ((ids&preds-of (lambda (pat) (let* ((preds '()) (ids (let loop ((pat pat)) (cond ((or (null? pat) (number? pat) (char? pat) (string? pat) (boolean? pat)) '()) ((symbol? pat) (list pat)) ((box? pat) (loop (unbox pat))) ((vector? pat) (loop (vector->list pat))) ((eq? (car pat) 'quote) '()) ((eq? (car pat) '?) (set! preds (cons (cadr pat) preds)) (loop (caddr pat))) (else (let ((cdrids (loop (cdr pat)))) (append! (loop (car pat)) cdrids))))))) (cons ids preds))))) `(matcher ,exp (list . ,(map (lambda (pair) (let ((pattern (car pair)) (body (cdr pair))) (let ((ids&preds (ids&preds-of pattern))) `(cons ',pattern (cons (lambda ,(car ids&preds) . ,body) (list . ,(cdr ids&preds))))))) pairs))))) Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 23 Apr 87 15:50:55 EDT Received: from relay2.cs.net by RELAY.CS.NET id ad20226; 23 Apr 87 15:53 EDT Received: from tektronix.tek.com by RELAY.CS.NET id bb08194; 23 Apr 87 15:45 AST Received: by tektronix.TEK.COM (5.51/6.20) id AA13695; Thu, 23 Apr 87 11:28:07 PDT Received: by tekchips.TEK.COM (5.31/6.19) id AA13316; Thu, 23 Apr 87 11:28:52 PDT Message-Id: <8704231828.AA13316@tekchips.TEK.COM> To: cth%indiana.csnet@RELAY.CS.NET Cc: rrrs-authors@MC.LCS.MIT.EDU, willc%tekchips.tek.com@RELAY.CS.NET Subject: Re: match questions In-Reply-To: Your message of Wed, 22 Apr 87 14:53:10 est. <8704230115.AA05069@tekchips.TEK.COM> Date: 23 Apr 87 11:28:50 PDT (Thu) From: willc%tekchips.tek.com@RELAY.CS.NET Chris's questions give me a welcome chance to express my personal views on this matter. 1. Do we want a match facility? No. 2. Given a match facility, do we need optional arguments? Yes. Optional arguments are in the standard library already, and that example encourages people to write new procedures with optional arguments. The problem is that optional arguments must now be implemented either by rest arguments, which leads to poor error-checking because few people take the trouble to check for excess arguments, or by implementation-specific and therefore non-portable hacks. Using rest arguments to implement optional arguments is also inefficient. The worst of it is that the inefficiency biases people toward omitting optional arguments, when people should be encouraged to write them explicitly: WRITE-CHAR with two arguments conses, but WRITE-CHAR with one argument doesn't. If you don't think that a single cons per character matters, then the implementation you've been using isn't fast enough. I would not be opposed to demoting the "." rest flag to optional or nonexistent status if it were replaced with #!optional and #!rest, or equivalent. 3. Should patterns be in read format (with quote), e.g. ('x 1 y), or in construction expression format, e.g. (list 'x 1 y)? Read format would be `(X 1 ,Y). The above "read format" corresponds to no existing syntax. It would be a new sublanguage, like Common Lisp's FORMAT though less silly. "Construction expression format" is sensible only if you have a meaningful notion of static type. Without static types, patterns based on construction expression format offer all the embarrassments of Common Lisp's SETF. For example, what would the pattern (LIST 'X 1 Y) mean inside (LET ((LIST VECTOR)) ...)? Even if you have static types, construction expression format generalizes only to free constructors, as even Philip Wadler observed in the SIGPLAN Notices article that seems to have given impetus to this particular crusade. 4. Can we define a good way of declaring additional constructors, to get more of an ML like matching mechanism? Sure, but first you have to turn Scheme into a statically typed language. Even then it would only work for free constructors like CONS, and would not work for constructors like ADJOIN. An ML-like matcher is far too much machinery when you consider that it does't generalize beyond a small set of rudimentary data types. 5. Do we want to be able to embed arbitrary predicates in patterns, and if so, with what syntax? No. To paraphrase Marie Antoinette, let them use COND. 6. Should the match facility be an abstraction (lambda) or local binding (let) form, or should it provide both? Neither. It would be ok as a library procedure. 7. Should MATCH be required, optional, or "Yellow Pages". Yellow pages, if at all. Unlike optional arguments, it can be implemented in terms of what we already have at no cost in efficiency or reliability. It is not a thing I need, and if I ever find myself wanting it I'd be happy to include it from a source library. By the way, I have written perhaps half a dozen specialized matchers for my own programs, some of them fairly powerful, but I don't believe the proposed facility would have saved me from writing any of them. My matchers have generally been written to simplify the construction of mini-compilers for application-specific languages. Thank you for requesting my opinions. Peace, Will Received: from grape.ads.ARPA (TCP 1200400070) by MC.LCS.MIT.EDU 23 Apr 87 14:06:57 EDT Received: by hobbes.ads.arpa (3.2/SMI-3.2) id AA29550; Thu, 23 Apr 87 11:23:04 PDT Date: Thu, 23 Apr 87 11:23:04 PDT From: andy%hobbes@ads.ARPA (Andy Cromarty) Message-Id: <8704231823.AA29550@hobbes.ads.arpa> To: rrrs-authors@MC.LCS.MIT.EDU Subject: Re: match questions I agree with Jinx and CPH. Matching, special handling of optionals, etc. can be convenient when they happen to provide what you want, but let's get more experience with matching facilities within Scheme, and more reports of such experience from more people, before we commit to a specific construct (if any is needed at all). If we have a standard macro definition capability, and especially if we allow any token at all to be redefinable (including, e.g., LET), then there's no need to build matching facilities into the language definition. Advocates of alternative matching and destructuring techniques can build the macro packages and distribute them informally to entice the rest of us to adopt their view of the importance of such constructs as a part of the language. asc Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 23 Apr 87 12:23:04 EDT Date: Thu, 23 Apr 87 12:24:52 EDT From: Chris Hanson Subject: match questions To: cth@IUCS.CS.INDIANA.EDU cc: rrrs-authors@MC.LCS.MIT.EDU In-reply-to: Msg of Wed 22 Apr 87 14:53:10 est from Chris Haynes Message-ID: <189657.870423.CPH@AI.AI.MIT.EDU> I agree with Jinx. A match facility is neither needed nor is it a desirable addition to the core language. I find optional arguments useful but unnecessary. Received: from geneva (TCP 2206400372) by MC.LCS.MIT.EDU 22 Apr 87 19:20:15 EDT Received: by GENEVA.AI.MIT.EDU; Wed, 22 Apr 87 17:39:43 est Date: Wed, 22 Apr 87 17:39:43 est From: jinx@GENEVA.AI.MIT.EDU (Guillermo J. Rozas) Message-Id: <8704222239.AA05975@geneva> To: cth@iucs.cs.indiana.edu Cc: rrrs-authors@mc.lcs.mit.edu In-Reply-To: Chris Haynes's message of Wed, 22 Apr 87 14:53:10 est <8704222223.AA05964@geneva> Subject: match questions Reply-To: jinx@zurich.ai.mit.edu 1. Do we want a match facility? No. Unless it involves adding no new special forms. I won't object to a couple of utility procedures in the Yellow pages for the people who use this sort of thing. 2. Given a match facility, do we need optional arguments? We don't need them as it is. I'd much rather agree on something for optional arguments (which I use regularly), than on some facility I find no use for. 3. Should patterns be in read format (with quote), e.g. ('x 1 y), or in construction expression format, e.g. (list 'x 1 y)? I could not care less. 4. Can we define a good way of declaring additional constructors, to get more of an ML like matching mechanism? I don't know. Whatever it is, I feel it should simultaniously define constructor, predicate and destructuring functions. The obvious approaches I've thought of seem a bit clunky, and I question whether we want to add that much mechanism to Scheme. Adding a match facility is adding too much mechanism as it is. 5. Do we want to be able to embed arbitrary predicates in patterns, and if so, with what syntax? I could not care less. 6. Should the match facility be an abstraction (lambda) or local binding (let) form, or should it provide both? The only way I'll be happy with it is if it involves no special forms. Then users can write their own syntactic extensions to make it convenient if they need it. 7. Should MATCH be required, optional, or "Yellow Pages". Definitely Yellow Pages if at all. It seems hard to come up with definitive answers to some of these questions. However, I don't see any indication that the issues here are deep, so we should be able to agree on something satisfactory without a whole lot of research. So let's try to do it in time for the July (?) meeting. I'm sorry, but I fail to see the point of a MATCH extension to the language. Every time I've wanted pattern matching, I've built my own, because the constraints and requirements were different, so a fixed utility would do me no good. We might as well try to agree on a UNIFY facility. It would probably be more useful. Received: from iucs.cs.indiana.edu (TCP 30003147315) by MC.LCS.MIT.EDU 22 Apr 87 15:55:31 EDT Date: Wed, 22 Apr 87 14:53:10 est From: Chris Haynes To: rrrs-authors@mc.lcs.mit.edu Subject: match questions Here are some questions that we need to answer before adopting a matching facility, along with my answers. I hope they generate debate. 1. Do we want a match facility? YES, very much so. 2. Given a match facility, do we need optional arguments? No, but something like OPTIONALS might be in the Yellow Pages. In fact, we could get demote the '.' rest feature to optional status, or even eliminate it. (Yeh!) 3. Should patterns be in read format (with quote), e.g. ('x 1 y), or in construction expression format, e.g. (list 'x 1 y)? I currently favor read format, but not by much, and if we can get a satisfactory answer to the next question, I'd probably favor construction format. 4. Can we define a good way of declaring additional constructors, to get more of an ML like matching mechanism? I don't know. Whatever it is, I feel it should simultaniously define constructor, predicate and destructuring functions. The obvious approaches I've thought of seem a bit clunky, and I question whether we want to add that much mechanism to Scheme. Without this, the matching facility is pretty simple and does not clutter up the rest of the language. (In fact, it can eliminate the optional arguments clutter.) Still, it would be very nice and may well be worth the mechanism. I just don't want to see resistance to this mechanism nix agreement on a simpler match facility. 5. Do we want to be able to embed arbitrary predicates in patterns, and if so, with what syntax? Yes, but I don't feel strongly about this. The (? ) syntax I proposed isn't wonderful, but it does the job. Note that ? (and quote) may still be used as literals, e.g. ('? 'quote foo). It is only their use as pattern variables that is prohibited. 6. Should the match facility be an abstraction (lambda) or local binding (let) form, or should it provide both? Local binding. A MATCH-LAMBDA form might be optional (I could certainly imagine wanting it), but it's probably better to have only one abstraction form, and keep it as simple as possible. If anyone wants MATCH-LAMBDA badly enough, it is easy to define given MATCH and any syntactic extension mechanism. 7. Should MATCH be required, optional, or "Yellow Pages". Optional, since it is not very hard to implement with required facilities, we want to keep the required base language simple, and we want to avoid changes to the base if possible so existing implementations are not invalidated. "Yellow Pages" status would be better than nothing, but quite dissapointing. I think it's a feature that should be widely available and much used. It seems hard to come up with definitive answers to some of these questions. However, I don't see any indication that the issues here are deep, so we should be able to agree on something satisfactory without a whole lot of research. So let's try to do it in time for the July (?) meeting. Chris Received: from RELAY.CS.NET (TCP 1201000005) by MC.LCS.MIT.EDU 20 Apr 87 11:48:20 EDT Received: from relay2.cs.net by RELAY.CS.NET id aa10812; 20 Apr 87 11:40 EDT Received: from ti-csl by RELAY.CS.NET id ao16289; 20 Apr 87 11:32 AST Received: from Nero (nero.ARPA) by tilde id AA08324; Mon, 20 Apr 87 10:30:10 cdt To: Jonathan A Rees Cc: RRRS-Authors@MC.LCS.MIT.EDU From: David Bartley Subject: Re: meeting dates/times Date: 20-Apr-87 10:29:18 Sender: BARTLEY%Nero%ti-csl.csnet@RELAY.CS.NET Message-Id: I'm pretty open to meeting at either end of the week. I hope to attend the SIGPLAN meeting in St. Paul June 24-26, though, so meeting Saturday won't work out for me. Although I hesitate to travel on the 4 July weekend, the Thursday-Friday choice may be best. (I may just plan to stay in Boston over the weekend!) --db-- Received: from AI.AI.MIT.EDU (CHAOS 3130) by MC.LCS.MIT.EDU 16 Apr 87 19:20:35 EDT Date: Thu, 16 Apr 87 19:19:38 EDT From: Jonathan A Rees Subject: meeting dates/times To: rrrs-authors@MC.LCS.MIT.EDU Message-ID: <186340.870416.JAR@AI.AI.MIT.EDU> I have heard from very few of you. Please let me know if you are planning to attend and whether you have any conflicts. Two different possibilities are being considered: A. Saturday - Sunday, 27-28 June. B. Thursday - Friday, 2-3 July. So far, the only person who has reported a definite conflict is Dan Friedman, who absolutely can't make it before July 1. Other data: - Mitch Wand would prefer not to meet on Saturday. - Kent Pitman would prefer not to meet Monday-Friday, but does not have a definite conflict. - Friday the 3rd might be difficult for Norman Adams due to approach of 4th of July. - Kent Pitman and Bill Rozas have suggested that the approach of the 4th might present problems for some people; I would encourage such people to speak up now. I am inclined now to suggest that we meet Thursday-Friday so that we can accomodate Mitch and Dan. Please reply with your preferences if you have not done so already. If you are mute you will be ignored. Jonathan Received: from iucs.cs.indiana.edu (TCP 30003147315) by MC.LCS.MIT.EDU 16 Apr 87 16:21:57 EDT Date: Thu, 16 Apr 87 15:16:57 est From: Chris Haynes To: JAR@AI.AI.MIT.EDU Cc: rrrs-authors@MC.LCS.MIT.EDU In-Reply-To: Jonathan A Rees's message of Wed, 15 Apr 87 12:41:00 EDT <185067.870415.JAR@AI.AI.MIT.EDU> Subject: Pattern matching, not optional arguments Date: Wed, 15 Apr 87 12:41:00 EDT From: Jonathan A Rees Phil Wadler recently complained in SIGPLAN that Scheme has no built-in pattern matching like ML and its affiliates do. I think there may be something to what he says. Yes indeed. Phil's article was one of my motivations to push for pattern matching (the other was what I saw happening to lambda). Some of the ways in which Phil finds Miranda superior to Scheme I disagree with, feeling they are simply different; for example quote. I'd like to see strong type checking widely used in Scheme, but that is a very difficult matter. The one respect in which I feel Miranda is clearly superior, and that we can address with relatively little effort, is pattern matching. Yours treats lists and vectors asymmetrically, and doesn't allow for additional constructors without redefining the macro. You should consider going even closer to ML, which you could do by changing the last two alternatives to be | (list ...) | (list* ... ) Did you mean | (list* . ) ? (In ML you'd write ,,... instead of (list ...), and :: instead of (cons ).) So let's also add | (cons ), which is the same as | (list* . ). This eliminates the reserved word problem; it is possible to take a list apart and name its car VECTOR, and it is possible to make MATCH understand new kinds of constructors without causing old code to break due to name conflicts. Another way to eliminate the reserved word VECTOR would be to replace the vector line with | #( ...) This is consistant with the rest of the approach I took, which is to have patterns match the print syntax, rather than the construction expression syntax, as you would have it. (I recall originally wishing I could use the vector syntax above, but being forced to the VECTOR keyword syntax because I was working in Scheme84 at the time and it does not support the standard vector notation. Sorry I neglected to correct this damage before making the proposal public.) The use of construction pattern syntax certainly is an alternative worth consideration. It also has the big advantage that quote becomes completely consistent with the pattern style; e.g. (list 'x var) is more natural than ('x var). The ability to add new constructors in a smooth way if constructor syntax is used is potentially a big win. But to do it right (something like the clarification of your proposal below) complicates the match mechanism substantially. It also makes it clunkier to use when only lists and vectors are involved, which I expect will be the vast majority of the time. It's much like the difference between making things with list and cons vs. using quasiquote. (Actually, quasiquote might be used to make constructor syntax patterns. Argh!) If matching is to be much used for such things as optional arguments (where only lists are involved), the simplicity of the print syntax is a real plus. It's a hard choice. In fact, if you changed (? ) to ((? ) ) then you could change the syntax to be simply ::= | | | (quote