XY-Transformation

How do you translate? Oh yes, I am talking about translating one language into another. Let me throw few jargons at you…have you heard of 'grammar'? I am sure you do have. What about 'Syntax Tree'?... 'Binding'?... 'XY-tranformation'? Ok! Ok! Let me first mention my target audience. If you don't know what is a 'Context Free Grammar' (CFG) then you probably don't have a Computer Science background. That, however, does not disqualify you from reading ahead. But lemme clarify that, If you don't know what's a programming language, you may leave!

Let me begin with the problem. We have programming languages A and B. Our aim, when we say translation, is to produce an equivalent code in B for any given code in A.

Let me simplify the problem to a great extent by assuming, for every semantic construct in A, there exist at least one semantic construct in B. Hah, You perhaps now realise that it's a very easy problem. In fact the translation is carried out as a linear tranformation of the syntax-tree-A to syntax-tree-B. You may recall, the linear being synonymous with Y=mx+c.

I call it, the XY-Transformation. The Y-axis transformation means the change in syntactic placement and the X-axis transformation handles the binding or scoping.

Let's start with this simple example:

A piece of code in Language-A (Well, I couldn't gather the patience to describe the whole language A here, but I assume that one has good observational skills to learn any programming language by example; so going to the example directly):

var3 := var2 := var1 := 2 + 3;
var4 := var2 * var1 + var3;

The equivalent code in Language-B:

add 2 and 3
assign_to var1
assign_to var2
assign_to var3
multiply var2 and var1
add var3
assign_to var4

The above example just shows the Y transformation. Color has been used to distinguish keywords from the variables or place-holders. The transformation seems to follow a logical pattern in replacing the constructs in A. Try translating "var4 := var2 * (var1 + var3);" into B as an exercise.

Now the moment I introduce block-execution (say, procedures or functions), we need to care about the scoping rules. Mostly the scoping rules followed by the programming languages are similar. The difference is in accessing-semantics and scope-resolution syntax. It's just my perspective. But this helps in visualizing the translation (the scoping part) as X transformation.

Consider SQL (as language A). The SELECT constructs are meant to project or throw you some tuples (or records). The scoping-rules in SQL bother a nice, innocent SQL programmar only when is comes to sub-queries or otherwise when he or she supplies range variables (what he or she might call as aliasing). Say for instance,

SELECT COL1, COL2
FROM TAB1
WHERE COL1 < (SELECT COL3 * COL2 FROM TAB2)

Let the TAB1 contain only two columns COL1 and COL2, where as the sub-query-table TAB2 contains COL3. The scoping rules say, if COL2 is also present in TAB2, then the COL2 referred in the sub-query is bound to this one (the one of TAB2). Otherwise, if there's no COL2 in TAB2, then the binding of the sub-query-COL2 is done to the one in TAB1 (since, the immediate parent query has COL2, else the process of searching continues till there exists a parent query with COL2 in one of it's tables in the FROM clause; this mostly happening in case of huge nested queries). The latter case we discussed, is called a co-related subquery.

TO BE CONTINUED...