O que isso realmente significa que uma linguagem de programação é stackless?

Question

De acordo com esta resposta

https://stackoverflow.com/questions/551950/what -stackless-programação-línguas-são-available / 671296 # 671296

todas estas linguagens de programação são stackless

• Stackless Python
• PyPy
• Lisp
• Esquema
• Tcl
• Lua
• Parrot VM

O que isso realmente significa para eles ser stackless? Será que isso significa que eles não usam uma pilha de chamadas? Se eles não usam uma pilha de chamadas, o que eles usam?

Answer 1

O que isso realmente significa para eles ser stackless? Será que isso significa que eles não usam uma pilha de chamadas?

Sim, isso é certo.

Se eles não usam uma pilha de chamadas, o que eles usam?

A implementação exata, é claro, variam de língua para língua. Em Stackless Python, há um despachante que inicia o interpretador Python utilizando o quadro de nível superior e seus resultados. Os opcodes processos intérprete como uma necessária em um tempo até que ele atinja um opcode CALL_FUNCTION, o sinal de que você está prestes a entrar em uma função. Isso faz com que o despachante para construir um novo quadro com as informações relevantes e retorno ao despachante com a bandeira descontrair. A partir daí, o despachante começa de novo, apontando o intérprete no quadro superior.

Stackless idiomas Evite pilhas de chamadas para um número de razões, mas em muitos casos é usado para que determinadas construções de programação tornará muito mais fácil de implementar. A única canônica é continuações . Continuações são estruturas de controle muito poderoso, muito simples que podem representar qualquer uma das estruturas de controle usuais você provavelmente já está familiarizado com (while, do, if, switch, et cetera).

Se isso é confuso, você pode querer tentar envolver sua cabeça em torno do artigo de Wikipedia, e em particular o cutesy continuação sanduíche analogia :

Digamos que você está na cozinha na frente da geladeira, pensando em um sanduíche. Você toma uma continuação ali mesmo e colá-la em seu bolso. Então você começa um pouco de peru e pão fora da geladeira e tornar-se um sanduíche, que agora está sentado no balcão. Você invoca a continuação em seu bolso, e você encontrar-se em pé na frente da geladeira de novo, pensando em um sanduíche. Mas, felizmente, há um sanduíche no balcão, e todos os materiais utilizados para torná-la sumiram. Então você comê-lo.

Answer 2

Eles não usam uma pilha de chamadas, porque operam em de continuação passando estilo . Se você não estiver familiarizado com otimização de chamada de cauda, ??que é provavelmente um bom primeiro passo para entender o que isso significa.

Para emular a tradicional chamada / retorno sobre este modelo, em vez de empurrar um endereço de retorno e esperando o restante do quadro para permanecer intocados os fecha chamador sobre o restante do seu código e todas as variáveis ??que ainda são necessários (o resto são libertado). Em seguida, realiza uma chamada de cauda para o receptor, passando essa continuação como um argumento. Quando os callee "retornos", ele faz isso chamando essa continuação, passando o valor de retorno como um argumento para isso.

Quanto ao acima vai, é apenas uma forma complicada de fazer chamadas de função. No entanto, ele generaliza muito bem para cenários mais complexos:

1. exceção / finalmente / etc blocos são muito facilmente modelados - se você pode passar uma continuação de "retorno" como um argumento, você pode passar 2 (ou mais) com a mesma facilidade. lisp-y blocos "manipulador condição" (que pode ou não retornar o controle para o chamador) também são fáceis -. passam uma continuação para o restante desta função, que pode ou não ser chamado
2. Múltiplos valores de retorno são feitas da mesma forma fácil -. Passam vários argumentos para a continuação
3. temporários Retorno / cópia já não são diferentes do que passar argumento da função. Isso muitas vezes faz com que seja mais fácil para eliminar temporários.
4. otimização de recursão de cauda é trivial -. O chamador simplesmente passa sobre a continuação de "retorno" que recebeu em vez de capturar um novo