How does a levelless language work?

Question

I have heard of harmless languages. However, I do not know how such a language will be implemented. Can someone explain?

Answer 1

Modern operating systems that we have (Windows, Linux) work with what I call the "large stack model". And this model is erroneous, sometimes, and motivates the need for "non-compact" languages.

The "large stack model" assumes that the compiled program will allocate "stock frames" for function calls in an adjacent memory region, using machine instructions to quickly configure registers containing a stack pointer (and an optional stack frame pointer). This leads to a quick function call / return, at the price of having a large contiguous area for the stack. Since 99.99% of all programs running under these modern operating systems work well with a large stack model, compilers, loaders, and even the OS "know" about this area of ​​the stack.

One of the common problems that all such applications face is "how big should my stack be?" Since memory is cheaper, the main thing is that a large chunk is allocated for the stack (MS defaults to 1 MB), and the typical structure of application calls never approaches its use. But if the application really uses all of this, it dies with an illegal memory link ("I'm sorry, Dave, I can't do this"), thanks to reaching the end of its stack.

Most so-called “non-compact” languages ​​are not really stacked. They simply do not use the continuous stack provided by these systems. Instead, they populate the stack stack from the heap each time the function is called. The cost of calling one function increases slightly; if the functions are usually complex or the language is interpreted, this additional cost is negligible. (You can also define DAG calls in the program call graph and select a heap segment to cover the entire DAG, so you get both the heap distribution and the speed of the classic calls of the large stack functions for all calls inside the DAG calls).

There are several reasons for using heap allocation for stack frames:

1) If the program performs deep recursion, depending on the specific problem, it solves, it is very difficult to pre-allocate the area of ​​the "large stack" in advance, because the required size is unknown. It is inconvenient to organize function calls to check if there is enough stack left, and if not, redistribute the larger fragment, copy the old stack and adjust all the pointers to the stack; which is so inconvenient that I do not know any implementations. The allocation of stack frames means that the application should never be upset until literally no allocated memory appears.

2) The forks subtask program. Each subtask requires its own stack and therefore cannot use a single "large stack". Thus, you need to allocate stacks for each subtask. If you have thousands of possible subtasks, you may need thousands of “big stacks,” and the memory demand suddenly becomes ridiculous. Highlighting stack frames solves this problem. Often, subtasks "stacks" refer to parent tasks for implementing lexical coverage; as a fork subtask, a "lookup tree" called a "cactus glass" is created.

3) Your language has sequels. They require that the data in the lexical domain, visible to the current function, is somehow stored for later reuse. This can be done by copying the parent stack frames, raising the cactus stack, and continuing.

PARLANSE programming langauge I implemented 1) and 2). I am working on 3).

Answer 2

Stackless Python still has a Python stack (although it may have tail call optimization and other call merge tricks), but it is completely parsed from the interpreter C stack.

Haskell (as commonly implemented) does not have a call stack; The score is based on a shorter schedule

Answer 3

There is a good article on the Parrot at language structure at http://www.linux-mag.com/cache/7373/1.html . Parrot does not use the stack to call, and this article explains the technique a bit.

Answer 4

In contactless environments, I am more or less familiar with (Turing machine, assembly, and Brainfuck), usually to implement my own stack. There is nothing fundamental in the fact that a language is built into the stack.

In the most practical of them, the assembly, you simply select the memory area available to you, set the stack register to the bottom, then increase or decrease to realize your clicks and pop-ups.

EDIT: I know that some architectures have dedicated stacks, but they are not needed.

Answer 5

There is an easy to understand description of the sequels in this article: http://www.defmacro.org/ramblings/fp.html

Continuations are something that you can pass to a function in a stack-based language, but which can also be used by the language’s own semantics to make it "unstable." Of course, the stack still exists, but, as Ira Baxter described, this is not one large adjacent segment.

Answer 6

Call me ancient, but I remember when the FORTRAN and COBOL standards did not support recursive calls and therefore did not require a stack. Indeed, I recall implementations of machines in the CDC 6000 series where there was no stack, and FORTRAN will do strange things if you try to call a subroutine recursively.

To record instead of a set of calls, the CDC 6000 series instruction set used an RJ instruction to call a routine. This saved the current PC value at the destination of the call and then answered the next location. In the end, the routine would perform an indirect jump to the destination of the call. This rebooted the saved PC, effectively returning to the caller.

Obviously this does not work with recursive calls. (And my recollection is that the CDC FORTRAN IV compiler generates broken code if you try to do recursion ...)

Answer 7

Suppose you wanted to implement stackable C. The first thing to understand is that this does not require a stack:

a == b 

But this?

 isequal(a, b) { return a == b; } 

No. Because the smart compiler will call isequal calls, turning them into a == b . So why not just insert everything? Of course, you will generate more code, but if you get rid of the stack is worth what you need, then this is easy with a little compromise.

How about recursion? No problems. Tail-recursive function type:

 bang(x) { return x == 1 ? 1 : x * bang(x-1); } 

It can still be nested, because in reality it is just a loop:

 bang(x) { for(int i = x; i >=1; i--) x *= x-1; return x; } 

In theory, a really smart compiler could figure this out for you. But a less intelligent person can still smooth it out like goto:

 ax = x; NOTDONE: if(ax > 1) { x = x*(--ax); goto NOTDONE; } 

There is one case where you need to make a small compromise. This cannot be specified:

 fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); } 

Stackless C just can't do it. Do you refuse a lot? Not really. This is that normal C cannot succeed either. If you do not believe me, just call fib(1000) and find out what is happening with your precious computer.

Answer 8

Please feel free to correct me if I am wrong, but I think that allocating memory on the heap for each function frame will cause an extreme memory alteration. In the end, the operating system must manage this memory. I would think that a way to avoid this memory overflow would be a cache for call frames. Therefore, if you need a cache anyway, we could make it contiguous in memory and call it a stack.