3 ms·

SSA makes me think of a few interesting points: Considering it's a functional language (bar memory access bits), and most procedural languages can target this,

SSA makes me think of a few interesting points: Considering it's a functional language (bar memory access bits), and most procedural languages can target this, we can say that a lot of procedural code can be compiled down to functional code - so procedural programming is syntactic sugar on top of a functional framework Also functional programmers have a couple of pet peeves - tail recursion to implement infinite recursion and loops being one. SSA uses a completely different paradigm - phi nodes - to achieve looping. Considering I don't particularly like tail recursion, as for example the naive recursive implementation of fibonacci is not tail recursive (and thus dangerous, a property that a functional program should never have), and trying to make it tail recursive looks very much like a transformation a compiler should do, which goes against the spirit of functional programming. I think functional programmers should think of other constructs to achieve infinite recursion or looping, considering I suspect there are infinitely many possible, I guess we could discover ones that are less inherently dangerous and easier to reason about as mere mortals.

JonChesterfield 1y ago
The transition from one basic block to another is to copy the live values to some common location, jump the instruction counter, then copy the values out of that location to give the results of the phi nodes. The transition from one function to another is to copy the arguments to some common location, jump the instruction counter, then copy the values our of that location to give the initial values of the parameters. These are the same thing, except that the branch in the first case is always at the end of the block. In the tail position. Your preferred looping construct of branching between basic blocks is _identically_ tail calls between functions, except that some of the block arguments are represented as phi nodes. This is because the blocks are functions.
- torginus 1y ago
  I see your point - tail calls are identical to MLIR-style phi nodes, where not the branch source determines the value, but it's passed explicitly as a function argument. I still think that tail recursion is too low level a construct for functional programmers to interact with, but it's wrapped into something like a reduce operation, which allows to write an identical fibonacci impl, as you would in a procedural language.
  - JonChesterfield 1y ago
    That "tail recursion" is a thing in it's own right is more a sign of people getting their implementation wrong than anything else. Specifically, if calling a function at the end of your current function _doesn't_ clean up the call stack first, what you've got is a space leak. That C's ABI on various architectures gives you this behaviour is a bad thing. The space leak sucks there too. You get functions with a tailcall: label at the top and `goto tailcall;` written in the body as a workaround when functional programmers collide with this. Related is RAII in C++ - implicitly calling things on leaving scope mostly means the function call in the "tail" position has to do more stuff after it returns, so it isn't in the tail position, and you burn memory on keeping track of the work still to do. This takes the initial mistake from C and really leans into it. If your language doesn't make that implementation mistake, you just have function calls that work fine. Tree style recursion is still a problem, but it's an out of memory one and at least only one side of the tree is eating memory, and in proportion to the book keeping needed to find the other side of the tree. In the olden days, _function calls_ in Fortran didn't work, because they put their local state in global memory, not on a stack. So if foo called bar called foo, broken. We don't tolerate that any more, everyone has a call stack. But we still tolerate "ah, let's just leak this stack frame for a while, we've always done it like that" at present.
    - LegionMammal978 1y ago
      If you want automatic implicit tail calls for literally everything, then you need a solution for { FooObject foo = FooObject(123); return foo.bar(); } ending up in a UAF when FooObject::bar() tries accessing the receiver "this". Or any other case of the tail function accessing a pointer to something the caller has put on the stack. Short of some kind of crazy dependency tracking (or shoving stuff onto the heap and using a GC), at the end of the day the programmer will have to explicitly work around the stack frame no longer existing in most return statements. To which the only workaround would be doing some circumlocutions specifically to avoid the tail-call recognition.
      - JonChesterfield 1y ago

JonChesterfield 1y ago

The transition from one basic block to another is to copy the live values to some common location, jump the instruction counter, then copy the values out of that location to give the results of the phi nodes. The transition from one function to another is to copy the arguments to some common location, jump the instruction counter, then copy the values our of that location to give the initial values of the parameters. These are the same thing, except that the branch in the first case is always at the end of the block. In the tail position. Your preferred looping construct of branching between basic blocks is _identically_ tail calls between functions, except that some of the block arguments are represented as phi nodes. This is because the blocks are functions.

torginus 1y ago
I see your point - tail calls are identical to MLIR-style phi nodes, where not the branch source determines the value, but it's passed explicitly as a function argument. I still think that tail recursion is too low level a construct for functional programmers to interact with, but it's wrapped into something like a reduce operation, which allows to write an identical fibonacci impl, as you would in a procedural language.
- JonChesterfield 1y ago
  That "tail recursion" is a thing in it's own right is more a sign of people getting their implementation wrong than anything else. Specifically, if calling a function at the end of your current function _doesn't_ clean up the call stack first, what you've got is a space leak. That C's ABI on various architectures gives you this behaviour is a bad thing. The space leak sucks there too. You get functions with a tailcall: label at the top and `goto tailcall;` written in the body as a workaround when functional programmers collide with this. Related is RAII in C++ - implicitly calling things on leaving scope mostly means the function call in the "tail" position has to do more stuff after it returns, so it isn't in the tail position, and you burn memory on keeping track of the work still to do. This takes the initial mistake from C and really leans into it. If your language doesn't make that implementation mistake, you just have function calls that work fine. Tree style recursion is still a problem, but it's an out of memory one and at least only one side of the tree is eating memory, and in proportion to the book keeping needed to find the other side of the tree. In the olden days, _function calls_ in Fortran didn't work, because they put their local state in global memory, not on a stack. So if foo called bar called foo, broken. We don't tolerate that any more, everyone has a call stack. But we still tolerate "ah, let's just leak this stack frame for a while, we've always done it like that" at present.
  - LegionMammal978 1y ago
    If you want automatic implicit tail calls for literally everything, then you need a solution for { FooObject foo = FooObject(123); return foo.bar(); } ending up in a UAF when FooObject::bar() tries accessing the receiver "this". Or any other case of the tail function accessing a pointer to something the caller has put on the stack. Short of some kind of crazy dependency tracking (or shoving stuff onto the heap and using a GC), at the end of the day the programmer will have to explicitly work around the stack frame no longer existing in most return statements. To which the only workaround would be doing some circumlocutions specifically to avoid the tail-call recognition.
    - JonChesterfield 1y ago