2021/05/23/Denotational-Semantics-Takeaways

[utterances-bot]

Denotational Semantics Takeaways | Computing Simplicity

Takeaways abstractions for describing control flow

https://computingsimplicity.neocities.org/2021/05/23/Denotational-Semantics-Takeaways.html

[RAbraham]

Condition Descriptors in Orthogonal Code Generation is a bit hard to find online. If you think it's a worthwhile thing to learn, could you give some idea as how it works?

[guitarvydas]

Update: the original thesis is CSRI Technical Report CSRI-177 (Jan, 1986). I haven't found an online copy yet. Condition Descriptors are described in Section 5.2 on page 5-7. Condition Descriptors have probably been subsumed by CPS and Denotational Semantics. CPS is a general technique and, therefore, harder to understand. Condition Descriptors are specialized to the problem-at-hand (describing branching control flow) and, hence, are easier to understand - the DI (Design Intent) is clear and not muddied by generality and abstraction. A Condition Descriptor is a tuple {c, Label[true], Label[false], Label[merge]} where "c" is a branch condition eq, gt, lt, always. All other conditions are created on-the-fly by flipping the labels around, for example "not {eq, A, B, M} --> {neq, B, A, M}". In more modern versions using CPS, we carry tuples of Continuations and flip them around. (If you look at Denotational Semantics, you will see the similarities, but shrouded in complexity and mystery). GOTOs use Labels as branch points for control-flow change. Continuations are uber-GOTOs. Continuations carry control-flow AND data in them, you can change control-flow, and, at the same time, change the data environment (the set of variables). Continuations are necessary in Denotational Semantics, but, like GOTOs, should not be used by mortal programmers. (using different words: imagine that the PC (program counter) was stored in the heap instead of on the stack ; also, imagine that all locals for a function are stored in the heap instead of on the stack ; a Continuation is just a heap object that contains, both, the PC and the locals. In fact, this is the way that IBM360s used to work before The Stack was hard-wired into every CPU. IBM360s had a BALR (branch and link (register)) instruction that was used to create call/return blobs. Now that we have The Stack wired into the hardware, it turns out that we have to implement a BALR-like thing (/CC) anyway. Deja Vu all over again.)

[RAbraham]

thanks Paul