[Editor's note: This is the complete text of yet another message by Bill Richter. It was in the original thread, but I added it to the FAQ because it contains a denial of one of my editor's notes.] From: Bill Richter (richter@math.northwestern.edu) Subject: Re: interpreters & semantics Newsgroups: comp.lang.scheme Date: 2004-08-24 20:01:09 PST Joe Marshall responded to me in message news:... Joe, first I'll respond to Will: 3) As I keep saying, Bill's first definition of his semantic functions is not compositional. But the new definition I just gave is compositional: I used Thm 3.13 to produce a compositional definition of my E_i, which of course I originally defined otherwise. [Editor's note: Bill's definition of E is not compositional, so he introduced an irrelevant structural induction by using Schmidt's Theorem 3.13 to define a family of identity functions E_i (for i > 1) while defining E_1 = E. His definition of the identity functions is compositional, and E_1 is E composed with identity functions, so he concludes that his definition of E_1 is compositional.] This is false, and it's essentially the third time in a row that Will has made the same mistake, so I will not look at Will's RichterFAQ again. I'll refute once again, but first let me express my gratitude to Will for my extended cls tutorial. I've learned a lot from Will, not about compositionality, but about my failures to understand the ZFC formalization of pure Math. I mean to rectify the axiomatic ZFC ignorance that Will's posts unearthed. There's another way in which my correspondence with Will here was positive: It's almost as if Will was considering me as a thesis student. Will's from the old school, the school of hard knocks, and that's the school I'm used to as well, where an advisor grills a new student mercilessly. So if there are any kids reading on cls thinking about attending Northeastern and working with Will, I recommend this highly. A good question for such kids to ask is, "If Will could teach so much to a top-notch pure mathematician like Richter, I wonder how much he teach me?" Refutation, sentence by sentence: [Editor's note: Bill's definition of E is not compositional, so he introduced an irrelevant structural induction by using Schmidt's Theorem 3.13 to define a family of identity functions E_i (for i > 1) while defining E_1 = E. His definition of the identity functions is compositional, and E_1 is E composed with identity functions, so he concludes that his definition of E_1 is compositional.] 1) yes, my original definition of my sem functions E_i is not compositional, and I'm introducing a structural induction by using Schmidt's Theorem 3.13, but I don't think it's irrelevant. I'm trying to prove a point: that my sem functions E_i have a compositional definition. And yes, for i > 1, E_i = identity. Will finally posted the truth about E_1 vs E yesterday, and he said it well: E_1 is E composed with a quotient map Q, so E_1 = E \circ Q. Today he went back to saying that E_1 = E, but that's a pardonable typo. I think Will's already explained that when he says `E_1 is E composed with identity functions', he means E_1 = E \circ Q. I'm not sure what Will means by `` while defining E_1 = E''. The Thm 3.13 structural induction produce some "new" sem functions, which aren't new at all, they're the same sem functions I had all along. So the 1st sem function produced is E_1. Maybe that's what Will means. Maybe Will's pointing out that I'm not producing any new sem functions by my invocation of Thm 3.13. That's certainly true! 2) No, I concludes that that my family E_i have a compositional definition because Thm 3.13 produces these functions, given the input of my f_ij. There are some some identity functions floating around, and near-identity functions (the quotient map Q), but it has nothing to do with my argument. It's a general fact that I'm using: Bill-compositional sem functions E_i have a denotational definition. To be Bill-comp means there are f_ij functions that satisfy the Schmidt equations with the E_i. Then plugging these f_ij into Thm 3.13 produces the E_i again, by the uniqueness of Thm 3.13! Therefore the E_i have a denotational definition: the functions f_ij. This example was so simple that there were lots of identity maps, but that's not a factor in my proof. Will, thanks again, you can respond on cls if you like, or someone else can read your (very humorous!) RichterFAQ and paraphrase some of your arguments, but if not, I bid you adieu for now. Thanks again. > Joe, I don't know what it means to "compute the partial function > curly-E[e]: U x S x K ---> A in a finite number of steps." Why > don't you just tell me? Curly-E is a total function that maps expressions to partial functions. A `step' in this case can mean one of these operations: 1. Determining whether an expression is atomic or compound. 2. Determining the appropriate partial function (U x S x K ---> A) for an atomic expression. 3. Decomposing a compound expression into its immediate constituent subexpressions. 4. Composing two partial functions into an appropriate single partial function: (U x S x K ---> A) x (U x S x K ---> A) ---> (U x S x K ---> A) For any finite expression `e', there exists an integer n such that with n or fewer applications of the above steps one can determine the partial function (U x S x K ---> A) that Curly-E maps e to. Joe, you just told me what the steps are, but you didn't answer my question, and of course that may well be my fault. I wanted to know what it means for the function curly-E[e] to be computed. You told me what the steps were. I think you answer that question here: > If it means "produce a procedure that computes this partial > function", then I already know how to do it. As you said, it's just > currying the procedure for the Scheme interpreter > Exp x U x S x K ---> A. Just so. So when we say we've computed curly-E[e]: U x S x K ---> A we mean exactly that we've produced a procedure which computes curly-E[e]? I know what that procedure is! And when you & Will say that curly-E: Exp ---> (U x S x K -> A) is computable, it mean exactly that it's adjoint is computable curly-E: Exp x U x S x K ---> A ? If so, then I think I can explain why my noncomputable function E: LC_vExp ---> Value_bottom stands at no disadvantage to curly-E. I think I can replace E by a function whose images are procedures rather than elements, so my new version of E will essentially be F-F's computable partial function |--->>_v: LC_vExp ---> Value Thanks for all the references & citations, but it wasn't relevant to my question. That's interesting you've done all this reading... Suppose Person A has access to the set which is the function curly-E[e]: U x S x K ---> A and Person B has the procedure which computes this function. You may now interview both A and B and ask them questions about the function. What question could you ask that can distinguish between them? The burning question to me is, "What's the actual domain of curly-E[e]?"