5 ms·

The Spiral Language v2

48 points by Kinrany 6y ago

Kinrany 6y ago
Previously on HN: https://news.ycombinator.com/item?id=17519138 https://news.ycombinator.com/item?id=17519138 (2018)
throwaway894345 6y ago
What does inlining have to do with heap allocation? I would have thought the opposite of heap allocation was "stack allocation"? In particular, I would expect that inlining would produce no effect on the number or size of heap allocations?
- wyager 6y ago
  Inlining pattern matches allows you to eliminate the value being matched on, preventing an allocation. It transforms an allocation into a function call.
  - wahern 6y ago
    > Inlining pattern matches allows you to eliminate the value being matched on, preventing an allocation. Where is the return type state stored?
    - wyager 6y ago
      What do you mean “return type state”? If you mean the return value, that depends on the semantics/ABI of the language, but if it would result in an allocation, that can be eliminated by another round of inlining. Functional compilers typically have to deal with the tradeoff between code size and compile time (from lots of inlining) and runtime allocation.
- chubot 6y ago
  Not sure if this is what the OP is referring to, but escape analysis determines whether a variable can be on the stack of a single function, or if it must be the heap (because it "escapes" the function's lifetime). So if you can inline more functions, then you can allocate more objects on the stack rather than the heap.
- deleted 6y ago
  [deleted]
- abstractcontrol 6y ago
  If you have a function, there is a certain equivalence (in terms of compilation) where you can either allocate it as a closure at runtime or emulate the effect of that by just tracking it fully at compile time and inlining it a the site of use. If you do the later, you can avoid having to do a heap allocation that having a runtime closure would require. I said it is an equivalence in terms of compilation because, whether it is allocated as a closure on the heap, or tracked at compile time has no bearing on the correctness of the program. It only affect its memory allocation and performance profile. If you are a C programmer, or working at a similar level of abstraction, this concern over heap allocations might seem academic, but to a functional programmer such as myself there is a lot of importance because we use function composition for all of our abstractions and don't want them to heap allocate as closures. The more abstract the code we are writing is, the more inlining matters. The way I am describing this is confusing because inlining is not an event that happens. Rather inlining is the default. Tracking functions at compile time is the default. Heap allocation of them and their conversion into closures is an event, after which the compiler stops tracking variables of a function on an individual basis and keeps track of them at a lower resolution. > I would have thought the opposite of heap allocation was "stack allocation"? | Stack | Heap ------|------------- Full | x | Box | | x To get a full picture of how Spiral's partial evaluator sees functions and recursive unions, it consider the table above. Spiral is designed so that it is very easy to go between the fully known and boxed. You don't actually control heap and stack allocations explicitly, but instead shift the perspective of the partial evaluator through the dyn patterns and control flow. It just so happens that a very natural way of generating code for fully known functions is to leave their variables as they are on the stack. If the function needs to be tracked at runtime, then those variables are used to make a closure. The natural way of compiling things that are fully known (functions, unboxed unions) is to put them the stack. While things that are boxed (closures, boxed recursive unions) are on the heap. This is just on the F# backend. If I were compiling to LLVM for example, I would not use a stack, but the infinite amount of virtual registers instead. And non-recursive union types are compiled as structs, meaning they should be on the stack even in boxed mode. This view of memory is more complicated than the usual heap vs stack allocation one, because I am playing a game here where I attach a bunch of other concepts to it, but it is very useful and simplifies actual programming.
svnpenn 6y ago
Jesus that's maybe the largest readme I have ever seen. Split that up
pharmakom 6y ago
He's back! very excited to dig into this. For anyone new, read the commit log. it's a very entertaining insight into the thought process of creative programming.
- dilDDoS 6y ago
  > I'd like a chance to demonstrate its capabilities. For that I'd like to receive access to your hardware and a monthly stipend. Bold. I almost feel dirty for reading these, like I'm reading someone's diary without their permission.
rrampage 6y ago
This tutorial linked in the commit log gives a good overview on the language : http://www.spiral.net/doc/pdf/spiral-tutorial2019.pdf http://www.spiral.net/doc/pdf/spiral-tutorial2019.pdf
- abstractcontrol 6y ago
  Sorry, that Spiral is an entirely different language that has nothing to do with mine! The only reason I linked to it is because somebody in the Reddit PL sub thread brought my attention to it. The docs on the main page are what you want.

48 points by Kinrany 6y ago

Previously on HN: https://news.ycombinator.com/item?id=17519138 https://news.ycombinator.com/item?id=17519138 (2018)

What does inlining have to do with heap allocation? I would have thought the opposite of heap allocation was "stack allocation"? In particular, I would expect that inlining would produce no effect on the number or size of heap allocations?

wyager 6y ago
Inlining pattern matches allows you to eliminate the value being matched on, preventing an allocation. It transforms an allocation into a function call.
- wahern 6y ago
  > Inlining pattern matches allows you to eliminate the value being matched on, preventing an allocation. Where is the return type state stored?
  - wyager 6y ago
    What do you mean “return type state”? If you mean the return value, that depends on the semantics/ABI of the language, but if it would result in an allocation, that can be eliminated by another round of inlining. Functional compilers typically have to deal with the tradeoff between code size and compile time (from lots of inlining) and runtime allocation.
chubot 6y ago
Not sure if this is what the OP is referring to, but escape analysis determines whether a variable can be on the stack of a single function, or if it must be the heap (because it "escapes" the function's lifetime). So if you can inline more functions, then you can allocate more objects on the stack rather than the heap.
deleted 6y ago
[deleted]
abstractcontrol 6y ago
If you have a function, there is a certain equivalence (in terms of compilation) where you can either allocate it as a closure at runtime or emulate the effect of that by just tracking it fully at compile time and inlining it a the site of use. If you do the later, you can avoid having to do a heap allocation that having a runtime closure would require. I said it is an equivalence in terms of compilation because, whether it is allocated as a closure on the heap, or tracked at compile time has no bearing on the correctness of the program. It only affect its memory allocation and performance profile. If you are a C programmer, or working at a similar level of abstraction, this concern over heap allocations might seem academic, but to a functional programmer such as myself there is a lot of importance because we use function composition for all of our abstractions and don't want them to heap allocate as closures. The more abstract the code we are writing is, the more inlining matters. The way I am describing this is confusing because inlining is not an event that happens. Rather inlining is the default. Tracking functions at compile time is the default. Heap allocation of them and their conversion into closures is an event, after which the compiler stops tracking variables of a function on an individual basis and keeps track of them at a lower resolution. > I would have thought the opposite of heap allocation was "stack allocation"? | Stack | Heap ------|------------- Full | x | Box | | x To get a full picture of how Spiral's partial evaluator sees functions and recursive unions, it consider the table above. Spiral is designed so that it is very easy to go between the fully known and boxed. You don't actually control heap and stack allocations explicitly, but instead shift the perspective of the partial evaluator through the dyn patterns and control flow. It just so happens that a very natural way of generating code for fully known functions is to leave their variables as they are on the stack. If the function needs to be tracked at runtime, then those variables are used to make a closure. The natural way of compiling things that are fully known (functions, unboxed unions) is to put them the stack. While things that are boxed (closures, boxed recursive unions) are on the heap. This is just on the F# backend. If I were compiling to LLVM for example, I would not use a stack, but the infinite amount of virtual registers instead. And non-recursive union types are compiled as structs, meaning they should be on the stack even in boxed mode. This view of memory is more complicated than the usual heap vs stack allocation one, because I am playing a game here where I attach a bunch of other concepts to it, but it is very useful and simplifies actual programming.

svnpenn 6y ago

Jesus that's maybe the largest readme I have ever seen. Split that up

pharmakom 6y ago

He's back! very excited to dig into this. For anyone new, read the commit log. it's a very entertaining insight into the thought process of creative programming.

dilDDoS 6y ago
> I'd like a chance to demonstrate its capabilities. For that I'd like to receive access to your hardware and a monthly stipend. Bold. I almost feel dirty for reading these, like I'm reading someone's diary without their permission.

rrampage 6y ago

This tutorial linked in the commit log gives a good overview on the language : http://www.spiral.net/doc/pdf/spiral-tutorial2019.pdf http://www.spiral.net/doc/pdf/spiral-tutorial2019.pdf

abstractcontrol 6y ago
Sorry, that Spiral is an entirely different language that has nothing to do with mine! The only reason I linked to it is because somebody in the Reddit PL sub thread brought my attention to it. The docs on the main page are what you want.