From: Bill Richter (richter@math.northwestern.edu) Subject: Re: [OT] Finns and education Newsgroups: comp.lang.scheme Date: 2004-09-05 17:43:51 PST Gustavo Gomez wrote in message news:... Gustavo, you made a good point, and the upshot is that I should credit C-F for me figuring out my definition (of Bill-compositionality), but I should not invoke C-F's authority, as if they said what I say. > From Cartwright/Felleisen's "Extensible Denotational", p 6: > > [The map from syntactic domains to semantic domains] satisfies > the law of compositionality: the interpretation of a phrase is a > function of the interpretation of the sub-phrases. Since Dr. Bill Richter has quoted this lots of times, I got curious an went to read the original document to see what was behind the "[the map from syntactic domains to semantic domains]" Here is [part of] the complete paragraph [more added by me]: The denotational specification of a programming language consists of two parts. The first part defines the syntactic & semantic domains of the language. The domains are subdomains of some universal domains, e.g. P(omega) [...]. The second part is a functional interpreter that maps elements of the syntactic domains to elements in semantic domains. It [here obviously refers to the functional interpreter] is defined in a universal programming language like LAMBDA or KL and satisfies [here, again, we are talking about the functional interpreter, not the map] the law of compositionality: the interpretation of a phrase is a function of the interpretation of the sub-phrases. You're right, and I guess I misread C-F: for C-F, it's a functional interpreter that satisfies the law of compositionality. I've been posting that the maps satisfy compositionality, and I knew, but didn't post, that C-F's maps were supposed to be defined by functional interpreter & LAMBDA, and that C-F's domains were supposed to involve things like P(omega). I figured it was OK to not post that stuff, since we hadn't been discussing it. But I guess that's not really what C-F say! C-F say that the functional interpreter, which defines the semantic maps, satisfies the compositionality. So I shouldn't keep quoting C-F as my source. But what I say makes perfect sense, and I did learn it from C-F: We can define compositionality to be a property of the semantic functions themselves, and as I proved, that's equivalent to saying that the semantic functions have a compositional definition. The fact that no one here believes my proof has nothing to do with the P(omega), functional interpreter & LAMBDA stuff that I elided from C-F. We've been discussing compositionality for months independently of P(omega), functional interpreter and LAMBDA. Surely there is a such a definition of compositionality: we don't only define compositionality in case we have functional interpreter etc. So what is this def? I inferred a def from C-F, by ignoring the P(omega), functional interpreter and LAMBDA stuff. Let's break C-F down sentence by sentence to see how my inference holds up: 1) I'm clearly not giving a denotational specification of C-F's sort, as I use no functional interpreters or languages like LAMBDA. But no one here has insisted on this. That is, we've been discussing the property of compositionality independently of such things. 2) The syntactic & semantic domains are sets, right? Sets like e.g. Scott's P(omega), which both of us elided, right? Let's give them names: B_i & D_i are the syntactic & semantic domains. 3) I , Will, & MB have defined semantic functions, without using domains like P(omega), and no one has said that's important in a discussion about compositionality, or LAMBDA and KL below. 4) So what do we make of C-F's `functional interpreter that maps elements of the syntactic domains to elements in semantic domains'? The only thing that `maps' one set to another is a map, right? In pure Math as well as Schmidt's DS book, map = function. So there are maps, and let's give these maps my names: E_i: B_i ---> D_i. So C-F's `functional interpreter' is something that gives rise to these maps E_i. 5.1) C-F say the functional interpreter is defined in a language like LAMBDA or KL. I know that K & L are 2 combinators, due to Curry I think, and LAMBDA is related to Scott's P(omega) being a model of LC: an LC expression gives a selfmap of P(omega). But I don't know how LAMBDA and KL are programming languages. I should learn. Since the functional interpreter is defined in languages like LAMBDA, and the fun interp defines maps, the maps E_i: B_i ---> D_i are defined in terms of things like P(omega) & LAMBDA. 4.2) you're right, C-F say that the functional interpreter satisfies the the law of compositionality, and not the maps. Good eye. But what about the functional interpreter is needed to say: the interpretation of a phrase is a function of the interpretation of the sub-phrases. You could say that the functional interpreter is some kind of procedure, and then arrive at the cls definition of compositionality: the sem functions have a compositional definition, as Nielson^2, Slonneger-Kurtz, and Tenant seem to define compositionality. And we can do this because a procedure is something like a Scheme define, so we can read of the definition from the procedure (probably written in some kind of LC rather than Scheme). That's fine, that gives us Will's interpretation of C-F, which he got in by inserting 2 words DEFINED BY, rather than saying a functional interpreter is procedure from which we can read off definitions. But either way, I've never vigorously objected to Will's interpretation of C-F. I've only vigorously insisted that I could prove that Will's interpretation of C-F was equivalent to mine: I defined compositionality as a property of the semantic functions themselves, and I proved, that's equivalent to saying that the semantic functions have a cls compositional definition. We don't need the procedure to make sense of this. C-F said above that the functional interpreter maps elements of the syntactic domains to elements in semantic domains. It's only the maps we need for C-F's the interpretation of a phrase is a function of the interpretation of the sub-phrases. We have these semantic maps E_i: B_i ---> D_i, and we have syntax builders explained by Schmidt's Option_ij's, which are maps prod_l B_ijl ---> B_i that describe the sub-phrases of a phrase in B_i. The obvious meaning of C-F here is that the composite prod_l B_ijl -Option_ij--> B_i -E_i--> D_i equals a composite involving Schmidt's function f_ij prod_l B_ijl -prod_l E_ijl--> prod_l D_i -f_ij--> D_i. If that's not what C-F meant, I say they should have, and if they didn't, maybe it's due to me, but I give them a lot of credit. That's a more abstract definition than saying the E_i have a compositional definition. In pure Math, we always think it's better to define properties of the math objects themselves, rather than the definitions of the math objects. Although as Will explained, you can define properties in terms of definitions, e.g. finitely presented groups. There is evidence that he doesn't know what a grammar is, much less a context-free grammar. Absolutely. As I've posted, Schmidt's DS book doesn't use these phrases `grammar' and `context-free grammar'. You don't need these phrases to understand Schmidt's Thm 3.13. You do have to understand Schmidt's BNF via abstract syntax, and I'm sure I understand that, as well as is needed for this Thm 3.13. But I imagine most folks here know a lot about BNF that I don't. But I'm no stranger to BNF, as F-F's mono on LC_v uses BNF freely throughout. BTW for the guy who spanked you for "feeding the troll": I take his advice by not following him up. If you're interested in what someone posts, then respond, even to flame, and if you're not interested, ignore it. It's futile to try to maintain order on a newsgroup by spanking people for posting. Anyone can post, even if only to chant: "4 legs good, 2 legs better. 4 legs good, 2 legs better..."