Hacker News Reader

Comment by myu701 | Hacker News Reader

If a language like this were to take off, I could see linter-style errors pop up that are not currently possible.

"ERROR: maximum memory usage computed to be XYZ MB, which is higher than the speicified limit of 500MB"

Now that would help keep the RAM bloat down!

My functional language Winter has errors like that. You can compute the maximum memory usage of the program and then throw an error if it exceeds some threshold.

Edit: I'll add that there are lots of programs the prover can't effectively handle right now, so can't compute a good memory bound. It works fine for some relatively simple programs however.

> there are lots of programs the prover can't effectively handle right now

And always will be, due to Rice's Theorem. Can still be useful though - various formal methods techniques are like this.

Winter is not a Turing equivalent language, so technically Rice's theorem doesn't apply (I think). Nevertheless practically speaking you are right, there will always be valid programs that the prover can't prove are correct.

As long as it still allows for arbitrary-length vectors - which I can't imagine it not - this would be impossible due to the halting problem. Or I guess, maybe you could derive a lower bound on memory usage, but you could not get an upper bound/exact number.

What about allocation is only possible when you can prove the upper limit. So this is possible

    if (sz < 1e6)
        vec = vector<int>(sz)
    else
        throw "Size exceeds upper limit"

I'm saying you could know "it will use at least X memory", but you could never know "it will use at most X memory" unless you seriously cripple the language's capabilities

Maybe there could be a compiler flag. You let any program compile normally, but if you enable the flag, it only allows programs to compile if the maximum memory usage can be computed, and if there are under the limit you specify.

That means the language isn't always crippled, but you can get compiler enforcement for certain embedded programs.

It would effectively become a stack-only language (heap allocations' sizes would always have to be known at compile time, just like on the stack). I could see that serving an interesting special subset of use-cases, but I was under the impression we were talking about a general programming language, which that would not be.

Fortran didn't have dynamic memory allocation until Fortran 90. If you wanted to run a problem larger than the original code's author had anticipated, you needed to recompile the source with larger values. This could indeed be an annoying restriction. But you might be surprised how much software was successfully written in Fortran.

For example MISRA C disallows dynamic memory allocations completely and still pretty complex applications have been written to that spec. Similar guidelines are pretty common in other high reliability or safety critical software specifications. Another example is "JPL Institutional Coding Standard for the C Programming Language", which specifies "Do not use dynamic memory allocation after task initialization"

Ada/SPARK does not allow for dynamic allocations, all of them must be proven at compile time.

This is Ada behaviour when doing stack allocations actually.

You can already do this with certain forms of type-level programming. We did it in the Rust-based OS we created atop seL4. It started out as using types to track setup processes and kernel objects at compile-time to bring some of the guarantees seL4 provides only at run-time, and also to provide guard rails to ensure that you're not accidentally creating unsecure systems using the tools seL4 gives you. After some exposure to doing this it became clear that we could also track memory allocations this way, so we created an allocator to do exactly that.

It basically ensures at compile-time that every allocation in the program will succeed given some expected usable footprint, which also has the benefit of ensuring that we kill the kernel/OS immediately at bootstrapping if the machine/environment doesn't have enough memory to make sure our proof-carrying code can meet its expectations.

One huge problem with this approach though is that it doesn't scale well. Where "scale" is in the dimension of revising your programs because the type-parameters tend to bleed all over the place and don't compose well/at-all. So, it's great if you're sure you've got your design locked-in, but it's kind of a nightmare if you're still prototyping & refactoring.

There is a Rust tool that computes the maximum stack usage of a program (if such maximum is bound). You can use it to make sure that your microcontroller running Rust doesn't run out of stack space.

Reply on news.ycombinator.com