Почему матчинг в scheme никогда не будет стандартизован
От: Mr.Cat  
Дата: 05.02.09 23:02
Оценка: 23 (2)
С похожим вопросом я решил обратиться к #scheme на freenode, и вот какой разговор из этого вышел (думаю, мои собеседники не будут против, если я это тут выложу).

[00:42:59] <Mr-Cat_> Btw, does anybody know, why wasn't pattern matching included in r6rs?
[00:43:56] <Mr-Cat_> Seems, there is no such srfi either
[00:44:02] <slom_> Mr-Cat_: bc/ its just a macro away
[00:44:23] <slom_> and there are different match packages ...
[00:44:38] <slom_> at least two which are quite different, afaik
[00:45:17] <Riastradh> It is not clear that any one choice of pattern matching abstraction is generally preferable.
[00:45:23] <Riastradh> Quite the opposite is clear, indeed.
[00:47:15] <Mr-Cat_> Still, r6rs incorporates, say, records which also have different implementaions
[00:48:11] <Mr-Cat_> Or do I overestimate the usefullness of pattern matching in scheme?
[00:48:19] <slom_> well records can not be provided simply as a library
[00:48:32] <slom_> pattern matching can
[00:49:30] <Riastradh> I think instead you underestimate the diversity in approaches to pattern matching.
[00:49:52] <Riastradh> Records are a low-level stratum on which one can readily build more elaborate abstractions.
[00:50:28] <Riastradh> Many different approaches to pattern matching have no such common ground.
[00:51:36] <zbigniew> there exists the psyntax library, and yet syntax-case was still mandated in r6rs
[00:52:17] <Riastradh> Syntax is a special domain for pattern matching.
[00:53:26] <Mr-Cat_> Riastradh: Well, before starting to learn scheme, I had some background in erlang and nemerle. Those didn't discuss different approaches, but just offered a tool and that was convenient...
[00:53:38] <zbigniew> and...?
[00:54:32] <slom_> psyntax integrates with the evaluator/library system
[00:54:55] <slom_> and libraries where the top goal for r6rs ... so that makes sense
[00:54:56] <Riastradh> (...yes, there's much more to SYNTAX-CASE than just pattern matching.)
[00:55:49] <Mr-Cat_> So, Is the absence of matching in scheme specs just a consequence of disagreement on how matching should look (though, the only matching approach, I've seen is that from chicken and plt — can anyone provide me a link to a different one please?) or the absence of need of pattern matching in real-world scheme apps?
[00:56:24] <Riastradh> It's not a matter of disagreement. There is no generally best approach to pattern matching.
[00:56:30] <slom_> Mr-Cat_: search for UI-match
[00:57:06] <Riastradh> For example, I could use foof's MATCH, which is convenient for working with simple list structures and which simplifies writing a large collection of COND clauses.
[00:57:23] <jlongster> Mr-Cat_: http://okmij.org/ftp/Scheme/macros.html#first-class-macros
[00:58:22] <Riastradh> (Um, that article is wrong and confused.)
[00:59:09] <Riastradh> When I'm working with foof's MATCH, I can't create a new data structure and tell MATCH how to pattern-match on it, however.
[00:59:27] <Riastradh> (The same is true in Erlang, ML, and Haskell -- there is a fixed set of structures for which patterns exist.)
[01:00:01] <jlongster> Oleg wrong? never! (I've never had the chance to try it, it looked interesting though)
[01:00:07] <Riastradh> Foof's MATCH also requires that every pattern be statically written at the place where the matching occurs. Thus I can't incrementally update a database of rules. Here's an example of such a database of rules:
[01:01:03] <Riastradh> <http://cvs.savannah.gnu.org/viewvc/mit-scheme/v7/src/compiler/machines/i386/rules1.scm?revision=1.24&amp;root=mit-scheme&amp;view=markup&gt;
[01:01:04] *rudybot NOTICE: http://tinyurl.com/auf55j
[01:02:12] <Riastradh> With a large database of rules such as that, it is easy for the semantics of the database to be sensitive to the order in which the rules occur.
[01:02:49] <zbigniew> [To be fair, you can match against data structures created with define-record or define-record-type]
[01:03:20] <Riastradh> So even if we defined DEFINE-RULE to basically run (SET! STATEMENT-RULES (LET ((SR STATEMENT-RULES)) (LAMBDA (X) (MATCH X (<pattern> <result>) (ELSE (SR X], our database might not work very well, and we might have very obscure bugs that depend on the order in which we write the DEFINE-RULE forms.
[01:04:03] <Riastradh> zbigniew, that's not true in general. It's true in Chicken. But even so, records are one of a fixed set of structures for which foof's MATCH provides patterns.
[01:05:52] <Riastradh> In order to make our rule database insensitive to the order of the DEFINE-RULE forms, we might want to organize the patterns so that we can lexicographically order them by specificity. That restricts the set of patterns that we can use, though; arbitrary predicates, which foof's MATCH allows us to insert into our patterns, cannot generally be ordered by specificity.
[01:07:49] <Mr-Cat_> Riastradh: I know, that there is no silver bullet. And I also understand, that simple solutions don't work in complex cases (like in your example)/ But still, there usually is a typical usecase, that covers a considerable percent of programmer's need. I.e. syntax-rules (that's just an example, I don't mean, that it also does some matching) is not omnipotent, but it's suitable for many common cases and still relatively simple. So, If a similar (similar in coverage of usecases) form of pattern-matching existed in spec, scheme could benefit from that.
[01:09:45] <Mr-Cat_> Riastradh: Btw, your example looks more like a knowledge base, not a pattern matching usecase. It seems to be worth a logic-oriented DSL, something like prolog...
[01:12:31] <Riastradh> There is no `typical' use case for pattern matching. SYNTAX-RULES (or SYNTAX-CASE) is a very specific use case, and it is deficient in several respects. (For example, try to express a pattern for LET that requires the left-hand sides of the bindings to be names.)
[01:13:32] <Riastradh> There's no unification in the rule database I mentioned; it's very straightforward pattern matching.
[01:13:55] <slom_> (match x ((let (((? identifier? name) value) ...) body) #t))
[01:14:16] <Riastradh> Express using SYNTAX-RULES, slom_, not using Wright's / foof's MATCH.
[01:14:30] <sjamaan> I think there's a hack that allows you to do that
[01:14:40] <sjamaan> But it wasn't designed to
[01:14:45] <Riastradh> There is a hack by which it can be done, but it's not straightforward.
[01:15:46] <Riastradh> It is also not expressible solely in a SYNTAX-RULES pattern.
[01:16:31] <Mr-Cat_> Riastradh: But how it comes, that many languages have a common pattern matching usecase and scheme does not?
[01:16:47] <Riastradh> You can see some of the hoops through which one must jump to check such things in <http://mumble.net/~campbell/darcs/foof-loop/loop.scm&gt;.
[01:17:29] <Riastradh> Mr-Cat_, because their designers were happier than Scheme's with inflexible, inextensible languages. A Lisp is a toolkit for building languages.
[01:17:53] <slom_> riastradh: you *can* check for identifiers, so it *should* be possible in pure syntax-rules
[01:17:58] <slom_> not?
[01:18:23] <Riastradh> There is no SYNTAX-RULES pattern that matches only if a subterm is a name.
[01:18:56] <sjamaan> It's odd that MATCH never got standardized in a SRFI, though
[01:19:26] <Mr-Cat_> sjaaman: I noticed that too
[01:19:41] <Riastradh> Are you volunteering to write one, sjamaan? Be aware that if you do, there will be many discussions about the notation, extensibility, and general applicablity of pattern matching, just as I discussed here.
[01:19:46] <Mr-Cat_> Strange, that something like records happened to be
[01:19:58] <Riastradh> Records cannot be implemented in a portable macro.
[01:20:59] <Mr-Cat_> Riastradh: Does not, for example, MIT's define-datatype have a portable implementation?
[01:21:14] <Riastradh> I don't know what `MIT's DEFINE-DATATYPE' is.
[01:21:14] <Mr-Cat_> Well, I might be mistaken...
[01:21:27] <slom_> Riastradh: match-check-identifier in Alex Shins match
[01:21:37] <slom_> is that not what you want?
[01:21:41] <Riastradh> There is no portable way, short of SRFI 9's DEFINE-RECORD-TYPE, to create disjoint types.
[01:21:50] <Riastradh> slom_, please read carefully what I wrote.
[01:22:30] <Riastradh> slom_, why does the existence of MATCH-CHECK-IDENTIFIER in foof's MATCH, or SYNTACTIC-NAME? in (my) foof-loop, not contradict my assertion?
[01:23:00] <slom_> because it's not *one* pattern, but recursive macro calls?
[01:23:06] <Riastradh> Yes.
[01:23:25] <slom_> got it
[01:23:30] <Mr-Cat_> Riastradh: define-datatype — I mean a kind of records that is used in EoPL for example
[01:23:56] *** saccade_ has joined the room as a participant and a member
[01:23:57] <Riastradh> Does DEFINE-DATATYPE create disjoint types?
[01:24:25] <Mr-Cat_> If I knew what 'disjoint types' is, I could answer your question
[01:24:26] <Riastradh> (The term `disjoint type' has a precise meaning explained in the R5RS.)
[01:24:53] *Mr-Cat_ opens r5rs and reads
[01:25:41] <Mr-Cat_> But I guess, the answer would be 'no'
[01:28:18] *Mr-Cat_ thinks, that he understood, what disjointness of types is
[01:30:37] <Mr-Cat_> Well, now I'm surprised, that scheme has some specs at all
[01:32:28] <sjamaan> What's that supposed to mean?
[01:39:37] <Mr-Cat_> sjaaman: Nm. I don't think, there is much point in insisting, that in many srfis people came to an agreement with many complex things, like multithreading, but they still didn't come to an agreement with pattern matching. I think, I'll return to that question in 20 years (or more), when I have enough experiens to argue with Riastradh on such stuff.
[01:39:59] <Riastradh> I don't think I'd call SRFI 8 `agreement on multithreading'.
[01:40:03] <Mr-Cat_> s/experiens/experience/
[01:40:04] <Riastradh> SRFI 18, even.
[01:40:25] <Riastradh> How many Scheme systems actually support it? I'm aware of two.
[01:41:03] <Mr-Cat_> I think it's better to ask, how much scheme systems support multithreading at all...
[01:41:12] <Riastradh> More than two.
[01:41:19] <Mr-Cat_> Hm...
[01:41:22] <sjamaan> heh
[01:41:57] <sjamaan> Mr-Cat_: I think that most of the Scheme world agrees to disagree
[01:42:38] <Riastradh> I hope my point is not lost that the issue of pattern matching is not a matter of disagreement.
[01:42:55] <Mr-Cat_> Riastradh: It is not lost
[01:43:03] <sjamaan> Indeed
[01:44:14] <Mr-Cat_> Well, maybe I'm too used to languages with a single dictating designer
[01:44:17] <Riastradh> For example, there was much disagreement about the design of a condition system, and there have been at least four SRFIs claiming that territory. All four differ from what one finds in the R6RS, which I think is still badly designed. That's a matter of disagreement.
[01:45:11] <sjamaan> Mr-Cat_: A lot of languages have only one defining implementation. There simply isn't anyone around to argue
[01:45:24] <Riastradh> (There are also similar issues of orthogonality in condition systems (does one use the same condition system by which CAR signals an error if you pass it 3, as one uses to deliver keyboard interrupts and other asynchronous signals?), but disagreement is still more of an issue in the design of condition systems than in the design of pattern matching.)
[01:45:28] <sjamaan> And because there's no spec it's hard to make a compatible other version
[01:46:20] <Mr-Cat_> sjaaman: For example?
[01:46:54] <sjamaan> python, ruby, java
[01:47:06] <sjamaan> (though Java might have a spec, I'm not sure there)
[01:47:43] <Mr-Cat_> sjaaman: Well, python has several implementations...
[01:47:52] <sjamaan> So does Ruby
[01:47:56] <sjamaan> But not for a long time
[01:48:14] <Mr-Cat_> Riastradh: cndition system — you mean the one from r6rs-standard libraries-7.2?
[01:48:20] <slom_> the python spec is called CPython
[01:48:36] <slom_>
[01:48:45] <sjamaan> slom_: Exactly my point
[01:48:46] <Riastradh> Yes, Mr-Cat_, that's one.
[01:48:57] <slom_> sjamaan: I know
[01:49:29] <Riastradh> You'll find a similar one in SRFI 34, another similar one in SRFI 18, (possibly yet another in the `real-time' multithreading SRFI), and yet another one in another SRFI, perhaps 20 or so.
[01:49:29] <slom_> still no spec might be better than a bad spec ...
[01:50:05] <slom_> see eg. the 3(?) implementations of the r6rs library system ....
[01:50:32] <Riastradh> And in SRFI 35 you'll find a mechanism for describing conditions, and it wouldn't surprise me if it were different from the one you'll find in the R6RS.
[01:51:01] *Riastradh vanishes.

Подождите ...
Пока на собственное сообщение не было ответов, его можно удалить.