Wednesday, April 21, 2010

Student M overhears the argument between Students A and T. “What seems to be the problem?”

Student T explains, ‘We're at an impasse. I want to be able to change the semantics of the language...’

Student A says “... and I want the semantics to be stable.”

Student T says ‘It seems to me that if the program is a tool for solving a problem, then the language itself is just another tool. I should be able to make changes to the language if it helps solve the problem.’

Student A replies “And I have no problem with that in principle, but when I'm writing a program, I need to know what the language semantics are so I can have some idea about whether my program will work. If the semantics change after I write the program, I won't even know whether I have a program. Mangle the semantics all you want, but then tell me what they are and don't change them!”

Student T says ‘I'm not going to “mangle” the semantics. But I don't want to lock myself out of a solution for your convenience. I want to be able to take whatever baseline semantics we have and tweak them as appropriate, but I can't change the semantics before I write the program the changes them!’

Student A says “This is just impossible.”

Student M interrupts “Time out, everyone. Ok, now let me get this straight. You...” and he points to student A, “want the meaning of your code to be stable, and you...” (he points to student T) “ want to be able to tailor the semantics to suit you. That's simple! Why are you arguing?”

Students A and T look confused. ‘Simple?!’

Student M says, “Of course. You both agree that changing the language will change the semantics, and conversely changing the semantics changes the language...”

Students A and T nod.

Student M turns to student A “So you write your code in your language (let's call it L), and we'll be sure that L has stable, static semantics that never change.”

Student A says “That's what I'm talking about.”

Student T objects ‘Hold on! You're just completely ignoring me! What if I don't like the semantics?’

Student M turns to student T “I'm not done, yet. You want the freedom to morph language L into language L', which is very much like L, but with maybe a few changes...”

Student T interrupts ‘.. or a lot of changes. And not just L', I want L, L', L'', L''', whatever changes I think are necessary and whenever I think they are necessary.’

Student M continues “... or a lot of changes. I get you. Now here's the question: If I have a program in language L, but I have a machine that runs a different language — call it C — what do I do?”

Student T replies ‘Write an interpreter...’

Student A answers “ ... or a compiler.”

Student M says “Bingo! Problem solved. Simply use language L as the base language for an interpreter or compiler for programs in L' (or L'' or L''', etc.)”

Student A thinks for a moment then says “Works for me. If I need to understand code written in L', I can just compile it down to L.”

Student T looks dubious. ‘Wait a second. You're suggesting I write a compiler? What if I want several different language features to mix and match? I'm supposed to write compilers for each of them?!’

Student M shrugs “Well, you're the one that wants to change the language, you can't expect student A to write them. Besides, it isn't that much work.”

Student T protests ‘Not that much work? It's a compiler! Flow control, analysis, register allocation, code generation! I just want to tweak the language, not invent a whole new one from scratch!’

Student M counters “Who said you need to do all that? A compiler is simply a program that translates code from one language to another, right? If you can express the constructs of language L' (or L'' etc.) in terms of language L, then that's all you need to do. If you're really just tweaking the language, then your ‘compiler’ is mostly the identity function.“

‘And the parts that aren't?’


Is student M's solution reasonable?


mquander said...

An important part of a production compiler running on real computers is often optimization. If you make "a lot" of changes to the semantics of the language via macros or through independent cross-compilation between L and L` and L`` and so on, you're probably going to miss out on optimizations that would be easier to perform if you had less translation layers.

Buddha Buck said...

I feel Student M's solution is a reasonable solution to a reasonable problem; I'm just not sure that the problem M is solving is the same problem as either A or T (who might not be talking about the same problem as each other).

M solves the problem of T wanting to program in L', a variant of L, and A not wanting to learn L'. This model works well in the real world, as many languages are slight variations of others (for instance, R4RS, R5RS, and R6RS could be considered Scheme''''', Scheme'''''', and Scheme''''''' under this, um, scheme).

Although one could think of this as a time-varying definition of Scheme, no guarantees are made that an arbitrary Scheme program will be valid or produce the same result when treated as an R4RS or R5RS program.

However it seems to me that that's not the variation that A and T are talking about. A seems to be against reasoning about a program written in L(t) (where the language semantics are a function of time over the lifetime of the execution of the program), while T also wants L to be a function, but hasn't been clear enough (in my opinion) if T wants L(t) or L(x) (where x ranges over the text of the program).

Using M's approach to solve the L(x) problem is still reasonable, as in effect parts of the program are written in L and parts in L'. As long as you can either introduce the macros in the middle of the program, or otherwise indicate to the reader and compiler which language variant is in effect at a given point in the program, M's approach works. Perl 6 uses this approach, allowing the very grammar of the language to be modified in a lexically scoped manner explicitly following the philosophy of "Everything's fair if you predeclare."

I do not believe that M's approach solves the L(t) problem, as it would require the translation of the program from L(t) to L to be time-variant as well. In effect, the translation would have to be self-modifying code. Given A's objections to T's proposal, I suspect that A would also object to self-modifying code.

JBF said...

I'd say M's position is very reasonable, but I don't think he gives T what T wants.

My gut feeling tells me that macros really don't change the meaning of L but rather exposes L' to the programmer. Every form, f, is still written in a fixed L' known before execution of that form (IE (f,L') is fixed at macro expansion time).

That gives you the ability to reason about f at compile time, which is a good thing.

Student T's position that he want to change the semantics however and whenever he feels like it, reduces your options to interpreting his whims step by step just like that student that never finished does.

Perhaps you could argue for three distinct phases of execution, language modification which fixes L and after which the semantics is known, program expansion which fixes P and after which the meaning is known and execution which gives R the result (sometimes).