I’m very confused by the claim “ But in some interesting target languages, including JavaScript and WebAssembly, intraprocedural control flow can be expressed only in structured ways, using loops, conditionals, and multilevel breaks or exits.” Has it been proven that these languages’ control flow CANNOT be represented by an arbitrary directed graph? Is this due to Continuation Passing Style meaning that functions do not represent fixed vertexes in the graph? If so does this mean that no modern languages with first class functions can use a control flow graph?
It seems to me, that these languages can still be represented as multi-graphs though, where concrete functions and control flow “end” at the first class function calls. And in the end, they can be represented as a dynamic control flow graph which changes as the running program processes events. In a way, you could see it as a kind of fold, where there is an initial state of the control flow graph known at compile time, and that graph will be a disconnected multigraph, and as the program runs and processes events, that graph will evolve and the connections will be exposed/change.
Either WebAssembly not JavaScript have primitives for intraprocedural flow control outside of structured programming. This is annoying if you want to lower a language like C, which has intraprocedural goto, to them. Any arbitrary unstructured CFG on basic blocks within a function can be lowered to structured control flow, so there won’t a proof that this is not possible and that was precisely what Relooper did. Unfortunately that lowering may be O(n^2) (from memory), so there is a strong desire for approaches that have better worst (and average) case complexity.
This is one of my least favourite design choices in WebAssembly, because it adds a lot of complexity in the front end and doesn’t actually buy you anything useful for verification.
Try to compile to ECMAScript or WebAssembly. You’ll find that anything which relies on goto soup is inexpressible directly, and has to be re-encoded somehow. This paper expands on the need for Relooper in WebAssembly.
I guess I actually misread the sentence. I didn’t realize that we were talking about javascript as a target language rather than a source language. In any case, regarding java script as a target langauge, while GOTO’s may be impossible, it is possible to create an array of first class functions and pass state in an object. I’m not sure of the performance penalty of doing so is, but we successfully trialed this when trying to figure out how to avoid stack overflows in Elmlang.
I’m very confused by the claim “ But in some interesting target languages, including JavaScript and WebAssembly, intraprocedural control flow can be expressed only in structured ways, using loops, conditionals, and multilevel breaks or exits.” Has it been proven that these languages’ control flow CANNOT be represented by an arbitrary directed graph? Is this due to Continuation Passing Style meaning that functions do not represent fixed vertexes in the graph? If so does this mean that no modern languages with first class functions can use a control flow graph?
It seems to me, that these languages can still be represented as multi-graphs though, where concrete functions and control flow “end” at the first class function calls. And in the end, they can be represented as a dynamic control flow graph which changes as the running program processes events. In a way, you could see it as a kind of fold, where there is an initial state of the control flow graph known at compile time, and that graph will be a disconnected multigraph, and as the program runs and processes events, that graph will evolve and the connections will be exposed/change.
Either WebAssembly not JavaScript have primitives for intraprocedural flow control outside of structured programming. This is annoying if you want to lower a language like C, which has intraprocedural goto, to them. Any arbitrary unstructured CFG on basic blocks within a function can be lowered to structured control flow, so there won’t a proof that this is not possible and that was precisely what Relooper did. Unfortunately that lowering may be O(n^2) (from memory), so there is a strong desire for approaches that have better worst (and average) case complexity.
This is one of my least favourite design choices in WebAssembly, because it adds a lot of complexity in the front end and doesn’t actually buy you anything useful for verification.
Try to compile to ECMAScript or WebAssembly. You’ll find that anything which relies on
gotosoup is inexpressible directly, and has to be re-encoded somehow. This paper expands on the need for Relooper in WebAssembly.I guess I actually misread the sentence. I didn’t realize that we were talking about javascript as a target language rather than a source language. In any case, regarding java script as a target langauge, while GOTO’s may be impossible, it is possible to create an array of first class functions and pass state in an object. I’m not sure of the performance penalty of doing so is, but we successfully trialed this when trying to figure out how to avoid stack overflows in Elmlang.
This paper was recommended to me after I whined in a non-specific manner on Mastodon. Their other recommended paper is also good.