Talk:Simple translation

I am working feverishly on this definition. The most recent incarnation doesn't actually enforce that the semantics of the two languages match at all. It is basically a string game. One language could be full of commands that are nothing but NOPs and it could be a ST of a TC language. This is more a question of syntax than semantics. But I think the current definition is much more usable than requiring a definition of isomorphism between two models. If B is a ST of A, then it is assumed that semantics are preserved by the translation tables, but that rule is not enforced explicitly anymore. Orby (talk) 17:03, 6 May 2020 (UTC)

Explanation of deferred parsing tricks

User:Orby, I think I now fully understand the mechanism behind the simple-translation tricks I proposed for picofuck, and this might help clarify the definition and minimisation attempts. I may need some help formulating a better description, but:

Thinking of simple-translations in terms of languages and the machines that can recognise them:

• context-free languages (push-down automata)
• regular languages (finite-state machines)
• any language representing a program in a TC programming language (Turing machines)

A simple-translation attempts to convert any string in CFL A to CFL B using only a finite-state transducer (a FSM).

Because a FST is not able to recognise CFL features, these can only be directly translated in a one-to-one fashion.

A CFL feature of language A can only be directly translated into B if it has the same basic syntax structure in B.

(example: Python's INDENT and DEDENT concepts cannot be translated atomically using a FST unless a comparable syntax exists on the other side)

HOWEVER ... this limitation can be bypassed to retain the 'functionality' of almost any arbitrary featured TC language if the parsing required to map a CFL feature of A to some differently structured CFL feature in B is deferred until runtime. At runtime a more powerful machine is available which can parse language complexity beyond what is possible using a FSM or PDA. Such a machine can be inserted by the FST if it is encoded into the simple-translation table.

The only limit is that the final parsing machine must be inserted into the output in such a way that it has all of the relevant program information present in the input available to it at the point it is executed. A FST cannot recognise a final symbol from its position (only by its face value) so cannot simultaneously encode a final machine and the fact that the input stream is complete based on position alone, nor can the more powerful machine written by the FST access information from the future (unless multi-threading is a feature of language B...). If that information is required for correct parsing of the input program it MUST be translated to the output tape along with a machine that can access and process it. The trick is simply getting access to the data, and any feature of language B can be exploited to do that.

I'm pretty sure you are only interested in the CFL -> CFL feature mapping of semantics for minimisation etc. Thinking about things in this way I think identifies the kinds of CFL syntax that are key to directly translate, and pass through the FST. Comparing grammars may be more relevant than comparing 'commands' or 'symbols'.

i.e. the NF -> RBF simple-translation works because their grammars are translatable by a FST

 s:ss|ε|* |{s}
 s:ss|ε|+>|<(s)

 s:ss|ε|+  |>   |< |(s)
 s:ss|ε|*{}|*{}*|{}|*{}*{s}

I'm not sure how to exclude deferred parsing from the simple-translation definition yet. The more powerful machine can be encoded in a single symbol, or spread out over many. The red flag seems to be the creation of any kind of meta-state at runtime. I do quite like this idea of deferred parsing to enable arbitrary conversions between languages, and now I understand it better I can leverage it more, but I see the value of what you are trying to do with minimisation and statements about semantic equivalence, so being able to clearly delineate translation techniques and meaning is useful. Salpynx (talk) 23:09, 13 May 2020 (UTC)