Olá Apresento a você a terceira parte da minha tradução do guia para implementar minha linguagem de programação JavaScript - PL Tutorial .
Do tradutor
Criaremos nossa própria linguagem de programação - linguagem λ (no original - linguagem λ ). No processo de criação, usaremos muitas técnicas interessantes, como descida recursiva, estilo de transferência de controle e técnicas básicas de otimização. Serão criadas duas versões do intérprete - o regular e o CPS, o transcompilador em JavaScript.
O autor do original é Mihai Bazon , o autor da famosa biblioteca UglifyJS (uma ferramenta para minimizar e formatar o código JS).
PS Existe um erro no interpretador e compilador: em expressões como a() && b() ou a() || b() a() || b() ambas as partes são sempre executadas. Obviamente, isso está errado porque a() falso para o operador && ou falso para o || , o valor de b() não desempenha nenhum papel. Isso não é difícil de corrigir.
Intérprete CPS
Nossa linguagem λ tem duas desvantagens:
- A recursão é limitada à pilha JS, portanto, não temos uma maneira normal de fazer loops.
- O intérprete é lento, então a recursão é muito lenta.
Agora, corrigiremos a primeira falha sem prestar atenção ao fato de que o intérprete se tornará ainda mais lento. Reescreveremos o intérprete no estilo "estilo de passagem de continuação" (CPS).
O que é uma "transferência de continuação"
Você faz isso no NodeJS o tempo todo:
fs.readFile("file.txt", "utf8", function CC(error, data){
A cada passo, há um retorno de chamada que será chamado quando você precisar continuar. O estilo de transferência de continuação torna a transferência de controle "explícita" - você não usa return , throw , break ou continue . Não há saltos implícitos no código. Você não pode nem usar loops for ou while com funções assíncronas. Nesse caso, por que precisamos deles na linguagem de programação?
Escrever código no estilo de transmitir uma continuação é difícil e fácil de cometer erros, mas apenas reescreveremos o intérprete nesse estilo.
evaluate função
A função evaluate receberá três argumentos: expressão (AST), contexto (ambiente) e a função que será chamada quando o resultado for. Aqui está o código, para cada fragmento, há uma explicação:
function evaluate(exp, env, callback) { switch (exp.type) {
Para constantes, apenas retornaremos seu valor. Mas lembre-se, não temos return - apenas chamamos o retorno e passamos o valor.
case "num": case "str": case "bool": callback(exp.value); return;
O nó var também é simples - obtenha a variável do contexto e passe-a para a função:
case "var": callback(env.get(exp.value)); return;
Para assign nós, precisamos obter o valor da expressão esquerda ( right ). Para fazer isso, chamamos de evaluate , passando uma função que obterá o resultado (para o lado direito da expressão). E então chamamos o callback com o valor da variável, configurando a variável no contexto atual:
case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function(right){ callback(env.set(exp.left.value, right)); }); return;
Quase o mesmo para nós do tipo binary , mas aqui precisamos primeiro obter o valor do campo left e, somente então, o valor do campo right . Depois, chamamos o retorno de chamada, passando o resultado da operação:
case "binary": evaluate(exp.left, env, function(left){ evaluate(exp.right, env, function(right){ callback(apply_op(exp.operator, left, right)); }); }); return;
O nó let parece mais complicado, mas na verdade é simples. Temos algum número de variáveis. O campo def (valor inicial) pode estar vazio; nesse caso, o definiremos como false . Mas se houver um valor, precisamos chamar evaluate recursivamente para obtê-lo.
Se você já trabalhou com o NodeJS antes, já fez isso várias vezes. Devido aos retornos de chamada, não podemos usar, portanto, devemos interpretar essas expressões uma por vez (imagine a função de evaluate como assíncrona). A função de loop abaixo (chamada imediatamente) obtém o contexto e o número da definição que precisa ser processada:
- Se esse número for igual ao número de variáveis (
vars.length ), isso significa que já definimos todas as expressões para poder executar o corpo da expressão. Observe que desta vez não ligamos para callback , mas passamos para evaluate , que será chamado. - Se esse número for menor, será necessário calcular a definição atual e passar uma função que chamará
loop(scope, i + 1) , antes de copiar o contexto.
case "let": (function loop(env, i){ if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function(value){ var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return;
O nó lambda será processado em uma função separada, como antes:
case "lambda": callback(make_lambda(env, exp)); return;
Para interpretar if , primeiro interpretamos a condição. Se não for falso, interpretaremos a expressão then , em outro caso, interpretaremos else se houver um ou retornaremos false se não houver. Como antes, por enquanto e apenas passamos o callback como a "ação a ser executada após a execução" da expressão:
case "if": evaluate(exp.cond, env, function(cond){ if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return;
O nó prog é interpretado de maneira semelhante ao nó let , mas com a diferença de que não precisamos copiar o contexto ou definir variáveis. E, novamente, temos uma função de loop que recebe um número de expressão. Quando é igual a prog.length , concluímos todas as expressões e simplesmente retornamos o resultado da última expressão (com a palavra "return", quero dizer que chamamos de callback chamada). Observe que lembramos o último valor passando-o como um argumento para a função loop (no início, é false no caso em que o corpo está vazio):
case "prog": (function loop(last, i){ if (i < exp.prog.length) evaluate(exp.prog[i], env, function(val){ loop(val, i + 1); }); else { callback(last); } })(false, 0); return;
Para um nó do tipo call precisamos interpretar func e, em seguida, todos os argumentos estão em ordem. E, novamente, há uma função de loop que funciona com o mesmo princípio que let ou prog , com a diferença de que agora cria uma matriz como resultado:
case "call": evaluate(exp.func, env, function(func){ (function loop(args, i){ if (i < exp.args.length) evaluate(exp.args[i], env, function(arg){ args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return;
Bem, o final padrão: se não sabemos o que fazer, lance uma exceção:
default: throw new Error("I don't know how to evaluate " + exp.type); } }
Você pode perceber que cada case acima termina com a palavra-chave return . Mas não há valor de retorno - o resultado é sempre passado para a função de callback .
Nova função make_lambda
Nesse intérprete, todas as funções receberão uma “continuação” como o primeiro argumento - a função que devemos chamar para passar o resultado. Depois são os argumentos usuais para a função. Aqui está o novo código para a função make_lambda :
function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { var names = exp.vars; var scope = env.extend(); for (var i = 0; i < names.length; ++i) scope.def(names[i], i + 1 < arguments.length ? arguments[i + 1] : false); evaluate(exp.body, scope, callback); } return lambda; }
Ele não é muito diferente. Ele adiciona novas variáveis a um novo contexto. Além disso, devemos considerar que o primeiro argumento é callback . Finalmente, a função de evaluate é usada para executar o código da função em um novo contexto, mas, como antes, passamos um callback .
A propósito, este é o único lugar que usei o loop for . Isso ocorre porque os valores do argumento já estão calculados quando o nó da call foi processado.
Funções nativas
Nesse intérprete, funções nativas recebem um callback como o primeiro argumento. Devemos lembrar disso quando definimos funções nativas. Aqui está o código de exemplo para o novo intérprete:
var code = "sum = lambda(x, y) x + y; print(sum(2, 3));"; var ast = parse(TokenStream(InputStream(code))); var globalEnv = new Environment();
Little test
Vamos tentar calcular os números de Fibonacci novamente:
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(10)) );
Mas, se tentarmos encontrar o 27º número, obtemos um estouro de pilha. Em geral, a pilha agora está crescendo muito mais rápido, portanto, agora podemos contar o número de Fibonacci apenas até o dia 12 (pelo menos no meu navegador). Isso não é muito bom, então você precisa corrigi-lo de alguma forma.
Protegemos a pilha
Em um intérprete CPS, a pilha cresce muito mais rapidamente porque o intérprete sempre chama funções recursivamente, nunca retornando um resultado. Embora tenhamos return ao intérprete, precisamos deles, mas no caso de recursão muito profunda, nunca os alcançamos.
Vamos imaginar como nossa pilha procura um programa muito simples. Vou mostrar o pseudo-código e não adicionei o env porque ele não desempenha nenhum papel aqui:
print(1 + 2 * 3);
Somente após a última chamada, uma longa sequência de return inútil reduz a pilha. Se usarmos tanto espaço de pilha para um programa simples, é difícil imaginar o que acontecerá com a fib(13) .
Proteção de pilha
Em nosso novo intérprete, a pilha simplesmente não é necessária. Tudo o que precisa ser feito depois que alguma expressão ocorre em um callback , que é passado como argumento. Então, aqui temos uma pergunta: e se o JavaScript tornasse possível "despejar" a pilha. Depois, podemos largar a pilha e a recursão infinitamente profunda funcionará.
Vamos imaginar que temos uma função GUARD que pode fazer isso. Ele obtém dois valores: a função a ser chamada e os argumentos que precisam ser passados. Ele verifica: se a pilha for muito profunda, ela limpará a pilha e chamará a função passada. Em outro caso, ela não faz nada.
Usando a nova função, reescrevemos o intérprete como mostrado abaixo. Não vou comentar sobre cada caso individual, existe o código descrito anteriormente, mas usando a função GUARD :
function evaluate(exp, env, callback) { GUARD(evaluate, arguments); switch (exp.type) { case "num": case "str": case "bool": callback(exp.value); return; case "var": callback(env.get(exp.value)); return; case "assign": if (exp.left.type != "var") throw new Error("Cannot assign to " + JSON.stringify(exp.left)); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(env.set(exp.left.value, right)); }); return; case "binary": evaluate(exp.left, env, function CC(left){ GUARD(CC, arguments); evaluate(exp.right, env, function CC(right){ GUARD(CC, arguments); callback(apply_op(exp.operator, left, right)); }); }); return; case "let": (function loop(env, i){ GUARD(loop, arguments); if (i < exp.vars.length) { var v = exp.vars[i]; if (v.def) evaluate(v.def, env, function CC(value){ GUARD(CC, arguments); var scope = env.extend(); scope.def(v.name, value); loop(scope, i + 1); }); else { var scope = env.extend(); scope.def(v.name, false); loop(scope, i + 1); } } else { evaluate(exp.body, env, callback); } })(env, 0); return; case "lambda": callback(make_lambda(env, exp)); return; case "if": evaluate(exp.cond, env, function CC(cond){ GUARD(CC, arguments); if (cond !== false) evaluate(exp.then, env, callback); else if (exp.else) evaluate(exp.else, env, callback); else callback(false); }); return; case "prog": (function loop(last, i){ GUARD(loop, arguments); if (i < exp.prog.length) evaluate(exp.prog[i], env, function CC(val){ GUARD(CC, arguments); loop(val, i + 1); }); else { callback(last); } })(false, 0); return; case "call": evaluate(exp.func, env, function CC(func){ GUARD(CC, arguments); (function loop(args, i){ GUARD(loop, arguments); if (i < exp.args.length) evaluate(exp.args[i], env, function CC(arg){ GUARD(CC, arguments); args[i + 1] = arg; loop(args, i + 1); }); else { func.apply(null, args); } })([ callback ], 0); }); return; default: throw new Error("I don't know how to evaluate " + exp.type); } }
Para funções anônimas, precisamos adicionar um nome para que possamos passá-los para a função GUARD . Eu usei o nome CC ( current continuation ). Você pode usar arguments.callee , mas esta é uma API desatualizada.
Além disso, a mesma alteração no make_lambda :
function make_lambda(env, exp) { if (exp.name) { env = env.extend(); env.def(exp.name, lambda); } function lambda(callback) { GUARD(lambda, arguments);
A implementação do GUARD muito simples. Como sair de uma chamada profunda? Usando exceções. Para fazer isso, haverá uma variável global que indicará quanto mais recursão podemos fazer. Se chegar a zero, lançamos o objeto Continuation , no qual haverá uma continuação - função e argumentos:
var STACKLEN; function GUARD(f, args) { if (--STACKLEN < 0) throw new Continuation(f, args); } function Continuation(f, args) { this.f = f; this.args = args; }
E no final, precisamos de um loop que capture objetos de Continuation . Devemos chamar o intérprete através deste loop para que tudo funcione:
function Execute(f, args) { while (true) try { STACKLEN = 200; return f.apply(null, args); } catch(ex) { if (ex instanceof Continuation) f = ex.f, args = ex.args; else throw ex; } }
A função Execute aceita a função a ser chamada e os argumentos para ela. Funciona em loop, mas preste atenção para return se a função funcionar sem excesso de pilha, paramos imediatamente. STACKLEN redefinido toda vez que iniciamos uma iteração de loop. Um valor de 200 - se encaixa bem. Quando capturamos o objeto Continuation , substituímos uma nova função e argumentos e continuamos o loop. Além disso, devido a uma exceção, a pilha é limpa, para que possamos continuar.
Para iniciar o intérprete, agora usamos Execute :
Execute(evaluate, [ ast, globalEnv, function(result){ console.log("*** Result:", result); }]);
Teste
A função fib agora funcionará:
fib = λ(n) if n < 2 then n else fib(n - 1) + fib(n - 2); time( λ() println(fib(20)) );
É uma pena, mas se você tentar encontrar a fib(27) , levará cerca de quatro vezes o tempo que um intérprete comum. Mas agora temos recursão infinita:
sum = λ(n, ret) if n == 0 then ret else sum(n - 1, ret + n); # compute 1 + 2 + ... + 50000 time( λ() println(sum(50000, 0)) ); # 1250025000, ~700ms
Obviamente, a linguagem λ é muito mais lenta que o JavaScript. Imagine, todo acesso a uma variável passa por um objeto Environment . Não faz sentido tentar otimizar o intérprete - não obteremos um ganho significativo de desempenho. Para melhorar o desempenho, existe uma solução: compile a linguagem λ em JS, e é isso que faremos. Primeiro, vamos ver o que podemos fazer de interessante com um intérprete do CPS.
Continuação
Agora que o intérprete trabalha no estilo de transmissão de continuação, e todas as funções, funções da linguagem λ e funções JS nativas, recebem a função de continuação como o primeiro argumento a retornar o resultado (esse argumento é necessário para as funções JavaScript, embora seja invisível para as funções da linguagem λ).
O callback variável significa a continuação de todo o programa. Tudo o que o programa fará a seguir. Vamos chamar essa variável de 'continuação atual' ou k no código.
Além disso, se não causarmos uma continuação, o programa será interrompido. Não podemos fazer isso a partir da linguagem λ porque make_lambda chama continuação de qualquer maneira. Mas podemos fazer isso a partir de uma função nativa. Eu criei uma função para mostrar como isso funciona:
globalEnv.def("halt", function(k){});
Esta é uma função que não faz nada. Ela recebe a continuação ( k ), mas não a chama:
println("foo"); halt(); println("bar");
Conclusão:
foo
Se você excluir a chamada halt() , a saída será: foo / bar / ***Result: false (porque o último println retorna false ). Mas com halt() isso apenas gera foo . * Agora não há resultado, porque halt() não causa continuação e, portanto, o retorno de chamada que passamos para evaluate - aquele que exibe a string ***Result , nunca é chamado. A função chamada evaluate não percebe que o programa foi interrompido. No NodeJS, isso seria um tiro no pé.
Imagine que precisamos de uma função sleepe que interrompa um programa sem interromper o navegador (portanto, sem loops estúpidos). Podemos facilmente implementar isso usando uma função nativa:
globalEnv.def("sleep", function(k, milliseconds){ setTimeout(function(){ Execute(k, [ false ]);
Um pequeno inconveniente é que precisamos usar o Execute , pois o setTimeout causará um retorno de chamada, que acionará Continuation , e ninguém o capturará. Veja como usá-lo:
let loop (n = 0) { if n < 10 { println(n); sleep(250); loop(n + 1); } }; println("And we're done");
Conclusão:
0 1 2 3 4 5 6 7 8 9 And we're done ***Result: false
Observe que há um pequeno atraso entre cada linha. Você pode tentar executar esse código no artigo original .
Isso já é algo que você não pode fazer no JavaScript normal, exceto pelo uso da transmissão manual de continuação (e também não é possível usar um loop for ):
(function loop(n){ if (n < 10) { console.log(n); setTimeout(function(){ loop(n + 1); }, 250); } else { println("And we're done");
Imagine como você pode usar a API do NodeJS em uma linguagem λ:
globalEnv.def("readFile", function(k, filename){ fs.readFile(filename, function(err, data){
Uso:
copyFile = λ(source, dest) { writeFile(dest, readFile(source)); }; copyFile("foo.txt", "bar.txt");
E tudo isso funciona de forma assíncrona. Não há mais retorno de chamada.
Aqui está um exemplo mais interessante. Eu escrevi a seguinte função nativa:
globalEnv.def("twice", function(k, a, b){ k(a); k(b); });
O programa usa dois argumentos b e chama continuação duas vezes, uma vez para cada argumento. Vamos tentar chamá-lo:
println(2 + twice(3, 4)); println("Done");
Conclusão:
5 Done ***Result: false 6 Done ***Result: false
A conclusão é estranha se você nunca trabalhou com continuações anteriores, mas tente entender esse código por conta própria. Uma pequena dica: o programa inicia uma vez, mas retorna o resultado duas vezes.
Generalização: CallCC
Costumávamos brincar com o fogo quando escrevíamos funções nativas. Não há nenhuma maneira na linguagem λ para interromper a execução da continuação atual. CallCC ajudará a resolver esse problema. O nome é a abreviação da função de Scheme - call-with-current-continuation (que geralmente é chamada de chamada / cc no esquema).
globalEnv.def("CallCC", function(k, f){ f(k, function CC(discarded, ret){ k(ret); }); });
Ele reifica a continuação atual em uma função que pode ser chamada diretamente da linguagem λ. Esta função ignorará sua continuação discarded original e chamará a continuação que foi passada para a função CallCC .
Usando esta função, podemos implementar (já diretamente na linguagem, não através de funções nativas!) Um grande conjunto de instruções de controle para o fluxo de execução em que nem pensávamos antes - começando pelas exceções e terminando com return . Vamos começar do último.
return implementação
foo = λ(return){ println("foo"); return("DONE"); println("bar"); }; CallCC(foo);
Conclusão:
foo ***Result: DONE
A função foo recebe um argumento que faz o mesmo que return do JavaScript (mas é chamado como uma função regular). Ignora a continuação atual (que produziria 'bar') e sai da função, retornando o valor fornecido ("DONE"). Obviamente, isso só funciona se você chamar uma função usando o CallCC para passar a continuação como return . Podemos criar um wrapper para isso:
with-return = λ(f) λ() CallCC(f); foo = with-return(λ(return){ println("foo"); return("DONE"); println("bar"); }); foo();
Conclusão:
foo ***Result: DONE
A vantagem desse método é que não precisamos mais usar o CallCC quando chamamos foo . Seria bom, é claro, se não precisássemos aceitar return como argumento ou usar a função with-return , mas na linguagem não há como adicionar açúcar sintático diretamente a partir dele, para isso precisamos pelo menos modificar o analisador (+1 para Lisp).
Transições
Por exemplo, precisamos escrever um programa que procure todos os pares de números inteiros positivos de até 100, de modo que, se a multiplicação deles der 84. Esta não é uma tarefa difícil e você poderá imaginar imediatamente dois loops aninhados para resolvê-lo, mas aqui vamos de uma maneira diferente. Vamos criar duas funções: guess e fail . O primeiro escolhe o número e o segundo diz a ela "tente outro número". Vamos usá-los assim:
a = guess(1);
:
fail = λ() false; guess = λ(current) { CallCC(λ(k){ let (prevFail = fail) { fail = λ(){ current = current + 1; if current > 100 { fail = prevFail; fail(); } else { k(current); }; }; k(current); }; }); }; a = guess(1); b = guess(a); if a * b == 84 { print(a); print(" x "); println(b); }; fail();
, , a , 84 , b , 84 / a . guess : start end — . , .
try catch Common Lisp
— catch throw . :
f1 = λ() { throw("foo", "EXIT"); print("not reached"); }; println(catch("foo", λ() { f1(); print("not reached"); }));
catch(TAG, function) , , TAG ', function .throw(TAG, value) , , TAG ' , value .
:
Um exemplo:
catch , , , . , , , CallCC . , . " " — — . , , , catch / throw , .
. , catch . , throw , , catch , . Por exemplo:
exit = false;
Conclusão:
After catch After catch ERROR: No more catch handlers!
'After catch' , 'ERROR: No more catch handlers!'. - , 'After catch' , . , '' , catch . , 'XXX' catch , throw , catch .
( , .)
CallCC (, , CallCC ). , — CallCC .
Yield
, , yield :
foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo());
yield , . , return . , , yield , .
:
fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; });
fib . . yield . , , 50 , 50 .
, , , , .
, .
yield , , . , , return . , , yield , yield , . , . :
with-yield = λ(func) {
yield , . , , , "DONE".
, . , - , , 4 :
println(foo()); foo();
.
№1: yield
, , , , yield ( kyld , , ) :
yield(2); yield(3); "DONE";
yield ? yield , , yield . , . , yield return , :
with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value);
, , yield , yield ( ). yield .
, , println(foo()) :
with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; func(val || yield); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo());
, . , print(foo()); foo() . , println(foo()) ? ...
№2: WTF?
. : , foo() . , ? — .
println(foo());
with-yield :
func(val || yield);
yield , , #... . , , ( "DONE" ), , "DONE" , . foo() , "DONE" . :
println(foo()); println("bar"); println(foo()); println(foo()); foo();
: 1, bar, 2, 3, DONE, bar, DONE, bar, ... .
func - , . , "no more continuations" :
val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val);
:
with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo()); println(foo()); println(foo()); println(foo());
, :
1 2 3 DONE NO MORE CONTINUATIONS NO MORE CONTINUATIONS NO MORE CONTINUATIONS ***Result: false
1, 2, 3, DONE , "NO MORE CONTINUATIONS" . , :
print("A. "); println(foo()); print("B. "); println(foo()); print("C. "); println(foo()); print("D. "); println(foo());
, : , , , , "B." .
, yield , :
with-yield = λ(func) { let (return, yield) { yield = λ(value) { CallCC(λ(kyld){ func = kyld; return(value); }); }; λ(val) { CallCC(λ(kret){ return = kret; val = func(val || yield); func = λ() "NO MORE CONTINUATIONS"; kret(val); }); }; }; }; fib = with-yield(λ(yield){ let loop (a = 1, b = 1) { yield(b); loop(b, a + b); }; });
Conclusão 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074 ***Result: false
, (, ), " ".
: reset shift
yield : reset shift . " " — , . reset , shift , CallCC .
, reset shift — . reset , shift , reset .
, with-yield :
with-yield = λ(func) { let (yield) {
, reset . , , , reset . , . , .
:
with-yield = λ(func) { let (yield) { yield = λ(val) { shift(λ(k){ func = k; val; }); }; λ(val) { reset( λ() func(val || yield) ); }; } }; foo = with-yield(λ(yield){ yield(1); yield(2); yield(3); "DONE"; }); println(foo());
reset shift
, . . . , , , . Scheme ( — Oleg Kiselyov ). .
, ( CallCC ) . :
var pstack = []; function _goto(f) { f(function KGOTO(r){ var h = pstack.pop(); h(r); }); } globalEnv.def("reset", function(KRESET, th){ pstack.push(KRESET); _goto(th); }); globalEnv.def("shift", function(KSHIFT, f){ _goto(function(KGOTO){ f(KGOTO, function SK(k1, v){ pstack.push(k1); KSHIFT(v); }); }); });
, reset , shift _goto , — . . _goto ( KGOTO ). , f ( CallCC ) - KGOTO , . , f , , KGOTO , , .
reset ( KRESET ) _goto(th) . , , , _goto . , , KGOTO KRESET .
, shift KGOTO , KGOTO pstack , SK , , shift ( shift — KSHIFT ). SK — — ( k1 ) . , shift2 , , pstack.push(k1); :
println(reset(λ(){ 1 + shift( λ(k) k(k(2)) ); })); println(reset(λ(){ 1 + shift2( λ(k) k(k(2)) ); }));
Conclusão:
4 3 ***Result: false
shift ( k ), reset . — 1 shift :
1 + [?]
k , ? . — k(k(2)) . 2 , k(2) 3. , k(3) 3 , 4.
shift2 : k(2) .
CallCC
, , CallCC , . , JS, , , . , CallCC , .
— goto , ( ):
pstack = NIL; goto = false; reset = λ(th) { CallCC(λ(k){ pstack = cons(k, pstack); goto(th); }); }; shift = λ(f) { CallCC(λ(k){ goto(λ(){ f(λ(v){ CallCC(λ(k1){ pstack = cons(k1, pstack); k(v); }); }); }); }); }; let (v = CallCC( λ(k){ goto = k; k(false) } )) { if v then let (r = v(), h = car(pstack)) { pstack = cdr(pstack); h(r); } };
— !