# Can a programming language be designed to use a fixed amount of memory?

I have been toying around with the idea of creating a programming language as a side-project, specifically trying to get extreme performance out of a machine.

I have been thinking about the efficiency-memory tradeoff, and was wondering if it would be at all possible to design a language which always uses a fixed amount of memory. That is, it allocates a large chunk of memory (16K, 64K, 1M, depending on the task), and instead of allocating from a heap, just gives some more memory out of the block we've already allocated.

The idea here is not to be practical, but rather to pose a challenge: design a fast algorithm that works on a fixed amount of memory.

If this sounds like a fun project, please let me know and I'll get on it.

If, however, this is a very naive thing to say (I don't know much about the inner workings of programming languages), I would very much appreciate some resources as to where I can learn more.

• There are problem instances with sizeable input. – greybeard Nov 20 '19 at 6:50
• C and asm code written for embedded systems is often written in a way that uses no dynamic memory allocation at all. – qwr Nov 20 '19 at 7:15
• Your system which allocates memory from a 16K chunk instead of allocating from a heap is called... a heap. – user253751 Jan 20 '20 at 12:33
• Regarding the last paragraph of your question, a more interesting project, IMHO, is designing a programming language that helps programmers to predict the amount of memory that a program will use. The amount depends on input data, of course. I heard that Rust is such a programming language. – beroal Feb 27 '20 at 15:36

Yes. At least one variant of C supports this. Its call stacks are bounded in size: you can't call functions within functions indefinitely. It is used for embedded devices.

• In fact all variants of C work the way you described. – user253751 Sep 9 '20 at 15:44

There is No need to create a new language. Use as example c. Get a chunk of memory with malloc() and do wharever you wish with it.

On a typical operating system today you might need to use low level OS functions of you want to keep the memory from beeing swapped due to virtual memory.

• With this approach, it may still be very hard to prove that your program never uses more than a given amount of memory. (It's undecidable in general.) E.g. you have to prove nested function calls cannot nest deeper than a certain bound. You need certain constraints on how functions can be called before you can prove this for every case. – reinierpost Dec 20 '19 at 12:05

Can a programming language be designed to use a fixed amount of memory?

Yes. Brainf*ck works on an array of $$30,000$$ memory cells.

But, it's an esoteric language. Meaning, you're not supposed to use it for professional purposes.

• Modern Brainf*ck implementations do not have this limit. – user253751 Sep 9 '20 at 15:45