O call / cc da Scheme pode implementar todas as estruturas conhecidas de fluxo de controle?

13

A página "Esquema avançado: alguns bits impertinentes" declara:

As continuações são uma poderosa construção de fluxo de controle a partir da qual quase qualquer outra estrutura de fluxo de controle [...] pode ser derivada.

Eu pensei que o esquema call/cc, estando relacionado (*) ao operador J de Peter Landin, pudesse ser usado para implementar qualquer estrutura de fluxo de controle conhecida?

Com a "estrutura de fluxo de controle", estou pensando especificamente na descrição deles da Wikipedia , por exemplo, exceções, corotinas, linhas verdes e assim por diante.

Especificamente, existem exemplos de estruturas de fluxo de controle que não podem ser implementadas usando call/cc?

(*) Não consegui desenterrar nenhum papel que call/ccseja tão poderoso quanto o operador J. Um artigo de Felleisen (que não li e reconhecidamente tenho problemas para entendê-lo completamente) investiga isso e parece concluir que, embora estejam em diferentes classes de complexidade, são formalmente equivalentes.

(Observe também que atualizei a pergunta com base nos comentários abaixo)

Atualizar

Com base na excelente resposta de @Neel abaixo, observei sites comentando continuações delimitadas e não limitadas e , de fato, parece que call/cc, embora não seja limitado, não é suficiente. Enquanto isso, continuações delimitadas de primeira classe (como shift/reset) podem ser usadas, ao que parece, para expressar qualquer estrutura de controle-fluxo.

csl
fonte
5
Qual é a definição formal de uma "estrutura de fluxo de controle"?
Huck Bennett
4
Re: continuações não limitadas. Você leu o artigo referenciado por Hayo Thielecke? A alegação real é que continuações não limitadas, conforme fornecidas por,call/cc não podem expressar exceções na ausência de estado . (Como Thielecke continua a apontar, exceções podem ser implementadas pela passagem de cerca de duas continuações, uma para o programa e outro para o manipulador de exceção, mas que exige mais do que apenas call/cc.)
rici
@Rici: Eu só passei as primeiras páginas. (Ler jornais me leva muito tempo). Obrigado pelo comentário!
CSL
@HuckBennett Não tenho uma definição formal, mas, informalmente, quero dizer o que está descrito em en.wikipedia.org/wiki/Control_flow - especificamente, quero dizer que você pode usar continuações para expressar, e mais importante, para implementar corotinas, threads verdes, exceções, instruções de escape, o amboperador e assim por diante.
CSL
2
@csl Além de tornar mais preciso o que significa "estrutura de fluxo de controle", você também precisa deixar mais claro o que significa "expressar" alguma coisa. Esse é um problema difícil, e a resposta à sua pergunta depende muito do que você conta como expressão. Afinal, você sempre pode, de alguma forma, codificar uma máquina de Turing que codifica um intérprete de uma linguagem com exceções (por exemplo, Java). Mas isso provavelmente não é o que você tem em mente, então você precisa colocar fortes restrições no conceito de "expressão" (por exemplo, composicionalidade e / ou abstração completa).
Martin Berger

Respostas:

11

Nesta resposta, entenderei "expressável" como "macro expressável" no sentido de Felleisen 1991, Sobre o poder expressivo das linguagens de programação . (Intuitivamente, um recurso de idioma é macro expressável se você pode defini-lo como uma transformação de origem local, sem usar uma transformação de programa inteiro.)

Com essa definição, a resposta é não : o controle delimitado não é macro expressável no lambda-calculus + call / cc. Para expressar operadores de controle delimitados usando call / cc. Para implementar os delimitadores de controle (a parte de redefinição de shift / reset), é necessário algum estado para simular as marcas de continuação, essencialmente para codificar uma pilha para simular a vida útil dinâmica das marcas de continuação.

No entanto, o controle delimitado é um efeito universal, no sentido a seguir. Em sua tese de doutorado , Andrzej Filinski mostrou que qualquer efeito colateral expressível é codificado usando continuações delimitadas ou call / cc e uma única célula de estado. Grosso modo, um "efeito colateral expressável" é qualquer efeito cujo tipo monádico pode ser definido em termos dos tipos da linguagem de programação.

Surpreendentemente, essa ideia parece bastante interessante na prática. Durante a última década, Gordon Plotkin e John Power defenderam a idéia de adotar uma semântica algébrica de teorias de efeitos : a idéia é que você especifique as operações de efeito colateral em que está interessado e as equações que espera que sejam satisfeitas. você pode obter genericamente uma semântica assumindo a mônada livre sobre essa teoria.

Matija Pretnar e Andrej Bauer adotaram essa abordagem matemática e a implementaram em sua linguagem Eff para inventar uma nova construção de linguagem chamada "manipuladores de efeito": você pode escrever código que usa um conjunto de recursos imperativos e, em seguida, fornecer uma semântica aos recursos imperativos. escrevendo um conjunto de manipuladores que dizem como implementar cada operação eficaz.

Neel Krishnaswami
fonte
Mas se a definição for: "Você pode implementar qualquer estrutura de fluxo de controle usando Scheme e call / cc" (sem emulação), a resposta deve ser sim ? Olhando para a discussão do LtU lambda-the-ultimate.org/node/966 , parece que Oleg Kiselyouv implementou todos os quatro operadores F no esquema com call / cc: okmij.org/ftp/continuations/… - trecho "O código depende on call / cc para capturar continuações não limitadas e usa uma célula mutável global. Isso é suficiente para implementar [...] os outros operadores F ". ... "-F- a + F + F".
CSL
Eu reconheço seu uso da "macroexpressibilidade" de Felleisen como um quadro para sua resposta, mas como você pode ver, eu já havia mudado minha pergunta para significar especificamente "implementar [no Esquema] usando call / cc". E embora Oleg Kiselyov precise introduzir uma célula mutável global para implementar todos os quatro operadores F para continuações delimitadas, não acho que isso represente uma "grande reestruturação global do programa" - praticamente falando, é claro.
CSL
Eu vou aceitar esta resposta. Eu também gostaria de apontar para o texto em okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim, que possui indicadores adicionais. Parece também que continuações delimitadas de primeira classe, como shift / reset, podem ser usadas para implementar qualquer estrutura de fluxo de controle. No link: "As continuações delimitadas de primeira classe podem expressar qualquer efeito computacional expressável, incluindo exceções e estado mutável".
CSL