Como funciona uma linguagem stackless?

Question

Já ouvi falar de línguas Stackless. No entanto, eu não tenho nenhuma idéia de como esse tipo de linguagem um seria implementado. Alguém pode explicar?

Answer 1

Os sistemas operacionais modernos que temos (Windows, Linux) operam com o que eu chamo de "modelo de pilha grande". E esse modelo está errado, às vezes, e motiva a necessidade de linguagens "Stackless".

O "modelo de pilha grande" assume que um programa compilado irá alocar "os quadros de pilha" para chamadas de função em uma região contígua de memória, usando instruções de máquina para ajustar registros contendo o ponteiro da pilha (e ponteiro quadro de pilha opcional) muito rapidamente. Isto leva a chamada de função rápido / retorno, ao preço de ter um grande, região contígua para a pilha. Porque 99,99% de todos os programas executados no âmbito destes sistemas operacionais modernos funcionam bem com o modelo big stack, os compiladores, carregadores, e até mesmo o sistema operacional "saber" sobre esta área pilha.

Um problema comum todas essas aplicações têm é, "quão grande deve minha stack ser?" . Com a memória ser barato sujeira, principalmente o que acontece é que uma grande parte é reservada para a pilha (padrão MS para 1Mb) e estrutura de call aplicação típica nunca fica perto de usá-lo para cima. Mas se um aplicativo usa tudo, ele morre com uma referência de memória ilegal ( "Desculpe Dave, eu não posso fazer isso"), em virtude de se chegar fora do fim da sua stack.

A maioria chamada chamadas línguas "Stackless" não são realmente stackless. Eles simplesmente não usam a pilha contígua fornecidas por esses sistemas. O que eles fazem é alocar um quadro de pilha da pilha em cada chamada de função. O custo por chamada de função sobe um pouco; se as funções são tipicamente complexo, ou a linguagem é interpretativa, este custo adicional é insignificante. (Pode-se também determinar DAGs chamada no gráfico de chamadas programa e alocar um segmento de pilha para cobrir todo o DAG, desta forma você tem as duas alocação de pilha e da velocidade da grande-stack chamadas clássicas de função para todas as chamadas dentro da DAG chamada) <. / p>

Existem várias razões para usar alocação de pilha de quadros de pilha:

1) Se o programa faz recursão profunda dependente do problema específico que está resolvendo, é muito difícil de pré-alocar uma área de "big stack" com antecedência, pois o tamanho necessário não é conhecido. Pode-se desajeitadamente organizar chamadas de função de verificar para ver se há pilha suficiente, e se não, realocar um pedaço maior, copiar a antiga pilha e reajustar todos os ponteiros na pilha; isso é tão estranho que eu não sei de qualquer implementações. Alocando quadros de pilha significa que o aplicativo não tem a dizer sua pena até que haja literalmente nenhuma memória allocatable esquerda.

2) Os garfos programa subtarefas. Cada sub-tarefa requer sua própria pilha, e, portanto, não pode usar o "big stack" fornecido. Então, é preciso alocar pilhas para cada subtarefa. Se você tem milhares de possíveis sub-tarefas, você pode agora precisa de milhares de "big stacks", ea demanda de memória de repente fica ridículo. Alocando quadros de pilha resolve este problema. Muitas vezes, a subtarefa "stacks" remeter para as tarefas de pais para implementar escopo lexical; como subtasks garfo, uma árvore de "subpilhas" é criado chamado de "pilha cacto".

3) Sua linguagem tem continuações. Estes exigem que os dados no escopo léxico visível para a função atual de alguma forma ser preservado para posterior reutilização. Isso pode ser implementado copiando quadros de pilha pai, subindo a pilha cacto, e prosseguir.

O PARLANSE langauge programação implementei faz 1) e 2). Eu estou trabalhando em 3).

Answer 2

Stackless Python ainda tem uma pilha Python (embora possa ter a otimização de chamada de cauda e outros truques quadro chamada fusão ), mas é completamente divorciada da pilha C do intérprete.

Haskell (como comumente implementado) não tem uma pilha de chamadas; avaliação baseia- gráfico redução .

Answer 3

Há um artigo agradável sobre o quadro linguagem Parrot em http: // www .linux-mag.com / cache / 7373 / 1.html . O papagaio não usam a pilha para chamar e este artigo explica a técnica um pouco.

Answer 4

Nos ambientes Stackless Eu sou mais ou menos familiarizados com (Máquina de Turing, montagem e Brainfuck), é comum para implementar sua própria pilha. Não há nada fundamental sobre ter uma pilha construído dentro da linguagem.

No mais prático destes, montagem, basta escolher uma região de memória disponível para você, definir o registo pilha para apontar para a parte inferior, em seguida, acréscimo ou decréscimo de implementar seus empurra e pops.

EDIT:. Eu sei algumas arquitecturas têm pilhas dedicados, mas eles não são necessários

Answer 5

Há um fácil de entender de continuações neste artigo: http: // www. defmacro.org/ramblings/fp.html

Continuations são algo que você pode passar para uma função em uma linguagem baseada em pilha, mas que também pode ser usado por própria semântica de uma língua para torná-lo "stackless". É claro que a pilha ainda está lá, mas como Ira Baxter descrito, não é um grande segmento contíguo.

Answer 6

Diga que queria implementar stackless C. A primeira coisa a entender é que este não precisa de uma pilha:

a == b

Mas, faz isso?

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

No. Porque um compilador inteligente vai in-line chamadas para isequal, transformando-os em a == b. Então, por que não apenas em linha tudo? Claro, você vai gerar mais código, mas se se livrar da pilha vale a pena para você, então isso é fácil com uma pequena desvantagem.

E sobre recursão? Sem problemas. Uma função cauda-recursivo como:

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

Ainda pode ser embutido, porque realmente é apenas um loop for disfarçado:

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

Em teoria um compilador muito inteligente poderia descobrir isso para você. Mas um menos-smart ainda pode achatar-lo como um goto:

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

Há um caso onde você tem que fazer um pequeno off comércio. Isso não pode ser embutido:

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

Stackless C simplesmente não pode fazer isso. Você está dando um monte? Na verdade não. Isso é algo C normal não pode fazer bem muito também. Se você não acredita em mim apenas chamar fib(1000) e ver o que acontece com o seu precioso computador.

Answer 7

Chamada me antigo, mas eu me lembro quando as normas Fortran e COBOL não suportar chamadas recursiva, e, portanto, não requerem uma pilha. Na verdade, eu me lembro das implementações para CDC 6000 máquinas da série onde não havia uma pilha, e Fortran faria coisas estranhas se você tentou chamar uma sub-rotina de forma recursiva.

Para o registro, em vez de um call-stack, o CDC 6000 conjunto de instruções série usada a instrução RJ para chamar uma sub-rotina. Isto salvou o valor PC atual no local de destino da chamada e ramos, em seguida, para o local seguintes ele. No final, uma sub-rotina iria realizar um salto indireta ao local de destino chamada. Isso PC recarregado salvo, efetivamente retornando ao chamador.

Obviamente, isso não funciona com chamadas recursivas. (E minha lembrança é que o compilador Fortran CDC IV iria gerar o código quebrado se você fez tentativa de recursão ...)

Answer 8

Por favor, fique à vontade para me corrija se eu estiver errado, mas eu acho que a alocação de memória na pilha para cada quadro chamada de função causaria surra memória extrema. O sistema operacional faz depois de tudo tem que gerenciar essa memória. Gostaria de pensar que o caminho para evitar este surra memória seria um cache para quadros de chamada. Então, se você precisa de um cache de qualquer maneira, que poderia muito bem fazê-lo contigous na memória e chamá-lo de uma pilha.