4 ms·

Has anyone tried to define a subset of Python, JS, C, Go, etc. that is SSA and actually write programs in it? Is it annoying or natural? I feel like I mostly

by chubot 8y ago

Has anyone tried to define a subset of Python, JS, C, Go, etc. that is SSA and actually write programs in it? Is it annoying or natural? I feel like I mostly do it in python but I have no way to machine-check it. Is the problem that you can’t do any aliasing of mutable containers? That is useful for many problems.

luddy 8y ago
Yes, mutation of containers is definitely a problem. The natural semantics in SSA is something like container' = F(container, key, value). But of course this functional semantics straightaway diverges from the physical realization we expect as programmers, namely not a new thing called container', but the original container whose state has changed. SSA is terribly overworked. It was a great formulation for certain compiler problems. To my mind, the problem for which it was perfectly suited was value numbering. Doing it in SSA form made it not only fast, but gave it a deeper power, as it became possible to easily "reach back" to deeper levels of input to an expression. But for a reason that's unclear to me, it was pushed into all kinds of applications where it's much less obvious that it's a good choice. Treating it as a programming language (lol) is, I guess, kind of the limit of wishful thinking about its universality.
- chubot 8y ago
  Hm that is an interesting viewpoint. It seems like compilers are converging on it though? LLVM and GCC both use it. I recall this talk being good: GopherCon 2017: Keith Randall - Generating Better Machine Code with SSA https://www.youtube.com/watch?v=uTMvKVma5ms&t=1s https://www.youtube.com/watch?v=uTMvKVma5ms&t=1s Go has built-in mutable containers, and no const, yet they still use SSA. Is there a real alternative? I guess it is mainly for speeding up code that uses a lot of integers and doubles and so forth, and not code that uses a lot of strings and containers?
  - luddy 8y ago
    >> Go has built-in mutable containers, and no const, yet they still use SSA. Right, as you say, compilers are converging on SSA, and almost all languages have mutable containers. All it means is that there's a mismatch between the semantics of the IL and the semantics of the language. That's a fairly common situation; there are lots of semantics (like concurrency and associated memory consistency) that can't be captured in an IL as they occur in reality, in the language being compiled. It's just a thing that has to be worked around.
XMPPwocky 8y ago
The issue is mostly the need for phi nodes everywhere for "true" SSA. Might get away with something like- and I cite Rust here because I know it well, but these features are probably from ML- > let x = if foo { 1 } else { 2 }; Loops are trickier- maybe you could write them as "unfolds"- where the loop body is effectively a fn foo(T) -> T, where T is a struct containing all the variables "modified" by the loop. Then evaluate iteratively, starting from the live values on entry. On exit, the live values are the result of the final invocation
- chubot 8y ago
  Yeah now I remember from reading this paper a few weeks ago: An important point is that SSA is not executable!!! The Phi nodes need to be removed I suppose. I will have to read this paper about Appel to see how that comes into play. SSA form cannot be directly interpreted in order to generate code. Therefore it must be destructed before compilation can continue. This involves using an algorithm that converts phi-functions into appropriately-placed copy instructions. Intermediate representations in imperative compilers: A survey https://scholar.google.com/scholar?cluster=15761365096026414559&hl=en&as_sdt=0,5&as_vis=1 https://scholar.google.com/scholar?cluster=15761365096026414...
  - nickpsecurity 8y ago
    Like with parallel DFS, I always look for anything people say is not possible. Here's my first hit on Google with a super-quick skim indicating it runs with phi instructions: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.9046&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.... May or may not be what you're looking for. Probably interesting nonetheless.
    - chubot 8y ago
      Thanks, that does look interesting. The fact that interpreting SSA requires a paper means it's nontrivial, which lends credence to the original statement :) In the abstract it says they present a variant of SSA. I will take a look.
mattnewport 8y ago
I tend to write C++ in a sort of limited SSA form a lot of the time: almost all local variables and parameters const, class members all initialized in the constructor initializer list, mutation confined to small functions or lambdas. If you're not familiar with const in C++, using it for locals and parameters gives you compiler checking that you're not modifying variables after assignment. This is one of the biggest things I miss from C++ when writing C#. Containers can make things a bit trickier but using algorithms and confining most mutation to helper functions makes it doable a lot of the time. The new ranges library being standardized for C++ 20 makes it more convenient to use containers in this style.
- pjmlp 8y ago
  I am with you on const.
marssaxman 8y ago
I tried something along those lines with a language called "radian", which was explicitly inspired by the Appel paper. I let the domain expire a while ago so all the design discussion is gone, but you can see the remnants of the project here: http://www.github.com/marssaxman/radian.git http://www.github.com/marssaxman/radian.git It was not a strict subset of anything, but it was heavily inspired by Python. The goal was to constrain the language such that every for-loop could be decomposed into a map-reduce over an lazy iterator, so that the runtime could transparently schedule computation across all available cores. It all worked out well enough, and nothing feels more natural than coding in a language designed precisely to suit one's individual taste; but the idiosyncratic requirements of the memory and processor model meant there was very little opportunity to reuse existing library code, and I wound up spending most of my time on yak-shaving expeditions and getting very little done. I got around the mutable containers problem by not having any; the language included, as primitives, an ordered container based on finger trees and an associative container based on... hm... AVL trees maybe? It's been a while.

by chubot 8y ago

luddy 8y ago

Yes, mutation of containers is definitely a problem. The natural semantics in SSA is something like container' = F(container, key, value). But of course this functional semantics straightaway diverges from the physical realization we expect as programmers, namely not a new thing called container', but the original container whose state has changed. SSA is terribly overworked. It was a great formulation for certain compiler problems. To my mind, the problem for which it was perfectly suited was value numbering. Doing it in SSA form made it not only fast, but gave it a deeper power, as it became possible to easily "reach back" to deeper levels of input to an expression. But for a reason that's unclear to me, it was pushed into all kinds of applications where it's much less obvious that it's a good choice. Treating it as a programming language (lol) is, I guess, kind of the limit of wishful thinking about its universality.

chubot 8y ago
Hm that is an interesting viewpoint. It seems like compilers are converging on it though? LLVM and GCC both use it. I recall this talk being good: GopherCon 2017: Keith Randall - Generating Better Machine Code with SSA https://www.youtube.com/watch?v=uTMvKVma5ms&t=1s https://www.youtube.com/watch?v=uTMvKVma5ms&t=1s Go has built-in mutable containers, and no const, yet they still use SSA. Is there a real alternative? I guess it is mainly for speeding up code that uses a lot of integers and doubles and so forth, and not code that uses a lot of strings and containers?
- luddy 8y ago
  >> Go has built-in mutable containers, and no const, yet they still use SSA. Right, as you say, compilers are converging on SSA, and almost all languages have mutable containers. All it means is that there's a mismatch between the semantics of the IL and the semantics of the language. That's a fairly common situation; there are lots of semantics (like concurrency and associated memory consistency) that can't be captured in an IL as they occur in reality, in the language being compiled. It's just a thing that has to be worked around.

XMPPwocky 8y ago

The issue is mostly the need for phi nodes everywhere for "true" SSA. Might get away with something like- and I cite Rust here because I know it well, but these features are probably from ML- > let x = if foo { 1 } else { 2 }; Loops are trickier- maybe you could write them as "unfolds"- where the loop body is effectively a fn foo(T) -> T, where T is a struct containing all the variables "modified" by the loop. Then evaluate iteratively, starting from the live values on entry. On exit, the live values are the result of the final invocation

chubot 8y ago
Yeah now I remember from reading this paper a few weeks ago: An important point is that SSA is not executable!!! The Phi nodes need to be removed I suppose. I will have to read this paper about Appel to see how that comes into play. SSA form cannot be directly interpreted in order to generate code. Therefore it must be destructed before compilation can continue. This involves using an algorithm that converts phi-functions into appropriately-placed copy instructions. Intermediate representations in imperative compilers: A survey https://scholar.google.com/scholar?cluster=15761365096026414559&hl=en&as_sdt=0,5&as_vis=1 https://scholar.google.com/scholar?cluster=15761365096026414...
- nickpsecurity 8y ago
  Like with parallel DFS, I always look for anything people say is not possible. Here's my first hit on Google with a super-quick skim indicating it runs with phi instructions: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.9046&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74.... May or may not be what you're looking for. Probably interesting nonetheless.
  - chubot 8y ago
    Thanks, that does look interesting. The fact that interpreting SSA requires a paper means it's nontrivial, which lends credence to the original statement :) In the abstract it says they present a variant of SSA. I will take a look.

mattnewport 8y ago

I tend to write C++ in a sort of limited SSA form a lot of the time: almost all local variables and parameters const, class members all initialized in the constructor initializer list, mutation confined to small functions or lambdas. If you're not familiar with const in C++, using it for locals and parameters gives you compiler checking that you're not modifying variables after assignment. This is one of the biggest things I miss from C++ when writing C#. Containers can make things a bit trickier but using algorithms and confining most mutation to helper functions makes it doable a lot of the time. The new ranges library being standardized for C++ 20 makes it more convenient to use containers in this style.

pjmlp 8y ago
I am with you on const.

marssaxman 8y ago

I tried something along those lines with a language called "radian", which was explicitly inspired by the Appel paper. I let the domain expire a while ago so all the design discussion is gone, but you can see the remnants of the project here: http://www.github.com/marssaxman/radian.git http://www.github.com/marssaxman/radian.git It was not a strict subset of anything, but it was heavily inspired by Python. The goal was to constrain the language such that every for-loop could be decomposed into a map-reduce over an lazy iterator, so that the runtime could transparently schedule computation across all available cores. It all worked out well enough, and nothing feels more natural than coding in a language designed precisely to suit one's individual taste; but the idiosyncratic requirements of the memory and processor model meant there was very little opportunity to reuse existing library code, and I wound up spending most of my time on yak-shaving expeditions and getting very little done. I got around the mutable containers problem by not having any; the language included, as primitives, an ordered container based on finger trees and an associative container based on... hm... AVL trees maybe? It's been a while.