Как реализовать продолжения в динамическом языке, таком как JavaScript? - PullRequest
2 голосов
/ 06 июня 2019

Мне нужны некоторые хитрости, как мне нужно реализовать и реализовать продолжение для губ в JavaScript (мой lisp почти как схема, за исключением без продолжений и оглавления).

Вот моя функция оценки:

function getFunctionArgs(rest, { env, dynamic_scope, error }) {
    var args = [];
    var node = rest;
    markCycles(node);
    while (true) {
        if (node instanceof Pair && !isEmptyList(node)) {
            var arg = evaluate(node.car, { env, dynamic_scope, error });
            if (dynamic_scope) {
                arg = unpromise(arg, arg => {
                    if (typeof arg === 'function' && isNativeFunction(arg)) {
                        return arg.bind(dynamic_scope);
                    }
                    return arg;
                });
            }
            args.push(arg);
            if (node.haveCycles('cdr')) {
                break;
            }
            node = node.cdr;
        } else {
            break;
        }
    }
    return resolvePromises(args);
}
// -------------------------------------------------------------------------
function evaluateMacro(macro, code, eval_args) {
    if (code instanceof Pair) {
        //code = code.clone();
    }
    var value = macro.invoke(code, eval_args);
    return unpromise(resolvePromises(value), function ret(value) {
        if (value && value.data || !value || selfEvaluated(value)) {
            return value;
        } else {
            return quote(evaluate(value, eval_args));
        }
    });
}
// -------------------------------------------------------------------------
function evaluate(code, { env, dynamic_scope, error = () => {} } = {}) {
    try {
        if (dynamic_scope === true) {
            env = dynamic_scope = env || global_env;
        } else if (env === true) {
            env = dynamic_scope = global_env;
        } else {
            env = env || global_env;
        }
        var eval_args = { env, dynamic_scope, error };
        var value;
        if (isNull(code)) {
            return code;
        }
        if (isEmptyList(code)) {
            return emptyList();
        }
        if (code instanceof Symbol) {
            return env.get(code, { weak: true });
        }
        var first = code.car;
        var rest = code.cdr;
        if (first instanceof Pair) {
            value = resolvePromises(evaluate(first, eval_args));
            if (isPromise(value)) {
                return value.then((value) => {
                    return evaluate(new Pair(value, code.cdr), eval_args);
                });
                // else is later in code
            } else if (typeof value !== 'function') {
                throw new Error(
                    type(value) + ' ' + env.get('string')(value) +
                        ' is not a function while evaluating ' + code.toString()
                );
            }
        }
        if (first instanceof Symbol) {
            value = env.get(first, { weak: true });
            if (value instanceof Macro) {
                var ret = evaluateMacro(value, rest, eval_args);
                return unpromise(ret, result => {
                    if (result instanceof Pair) {
                        return result.markCycles();
                    }
                    return result;
                });
            } else if (typeof value !== 'function') {
                if (value) {
                    var msg = `${type(value)} \`${value}' is not a function`;
                    throw new Error(msg);
                }
                throw new Error(`Unknown function \`${first.name}'`);
            }
        } else if (typeof first === 'function') {
            value = first;
        }
        if (typeof value === 'function') {
            var args = getFunctionArgs(rest, eval_args);
            return unpromise(args, function(args) {
                var scope = dynamic_scope || env;
                var result = resolvePromises(value.apply(scope, args));
                return unpromise(result, (result) => {
                    if (result instanceof Pair) {
                        return quote(result.markCycles());
                    }
                    return result;
                }, error);
            });
        } else if (code instanceof Symbol) {
            value = env.get(code);
            if (value === 'undefined') {
                throw new Error('Unbound variable `' + code.name + '\'');
            }
            return value;
        } else if (code instanceof Pair) {
            value = first && first.toString();
            throw new Error(`${type(first)} ${value} is not a function`);
        } else {
            return code;
        }
    } catch (e) {
        error && error(e, code);
    }
}

ПРИМЕЧАНИЯ:

// unpromise and resolvePromises is just used ot unwrap any promise
// inside list and return new promise for whole expression if found
// any promise and not found it just return value as is
// markCycles is used to prevent of recursive printing of list cycles
// if you create graph cycles using `set-cdr!` or `set-car!`

Нужно ли создавать стек при оценке выражения для продолжений?Как я могу это сделать?Я думал, что я создаю какой-то класс Continuation, который будет в двух режимах: один в заполненном, когда он может быть вызван как Macro, и в другом, ожидая, когда будет заполнен оператором оценки с кодом, который должен быть выполнен, я также не уверен, какя должен идти и не оценивать код перед выражением, которое вызывает продолжение, например:

(* 10 (cont 2))

(* 10 x) нужно игнорировать

Я также не уверен, как мне поступитьи создайте call/cc как функцию.Должен ли он возвращать некоторую промежуточную структуру данных с аргументом, хранящимся в этой структуре данных, чтобы он мог быть вызван при помощи метода вычисления с продолжением?

'call/cc': function(lambda) {
   return new CallCC(lambda);
}

и если eval найдет экземпляр CallCC, он получит продолжение (пока не уверен, как)используйте

if (value instanceof CallCC) {
   value.call(new Continuation(stack));
}

Это как вы это сделаете?В общем, мой вопрос о стеке.Это нужно для продолжения?Если это необходимо, то как это должно быть создано?

Я нашел эту статью Написание Lisp: Продолжения , которые показывают, как реализовать продолжения, но это трудно понять, потому что это на Haskell,

Ответы [ 2 ]

2 голосов
/ 06 июня 2019

Один из способов реализации продолжений в интерпретаторе - заставить этот интерпретатор использовать свой собственный явный стек для вызова / возврата функций и передачи параметров.Если вы используете стек основного языка, и у этого языка нет продолжений, то все будет сложно.

Если вы используете свой собственный явный стек, вы можете превратить его в «стек спагетти» для продолжения,«Стек спагетти» очень похож на обычные представления лексической среды.Он содержит кадры, которые указывают на родительские кадры.Захват продолжения сводится к сохранению указателя на такой кадр и некоторого кода.Возобновление продолжения означает, более или менее, восстановление стека в этом кадре и выполнение до этой точки в коде.Переводчик для языка не работает.Когда интерпретируемый язык вложен или рекурсивен, интерпретатор выполняет итерацию и просто выталкивает и выталкивает явный стек для отслеживания состояния.

Альтернативный подход - использовать линейный стек, но копировать его при создании продолжения.Чтобы возобновить продолжение, вы можете восстановить весь стек из скопированного снимка.Это полезно для продолжений с разделителями, которые могут избежать копирования всего стека, но только той его части, которая ограничена (и восстанавливать ее поверх существующего стека, а не путем замены).Я реализовал продолжения с разделителями в языке, который использует базовый стек C.Сегмент стека C memcpy -d в объект, который живет в куче.При восстановлении продолжения этот сохраненный сегмент стека обрабатывается поверх текущего стека.Конечно, указатели должны быть скорректированы, потому что сегмент теперь находится по другому адресу, а «висячие кабели» должны быть подключены для правильной интеграции этого сегмента стека в стек.

Если языкобрабатывается компиляцией в CPS (стиль передачи продолжения), затем продолжения появляются бесплатно.Каждая функция имеет скрытый аргумент: продолжение, которое она получила.Функция возврата компилируется в вызов этого продолжения.Если блок кода в функции должен вычислить текущее продолжение, он просто должен составить небольшое локальное вычислительное будущее (представляемое как лямбда) с этим входящим продолжением (будущее вычисление, которое произойдет, когда локальная часть вернется).Генри Бейкер написал статью, основанную на наблюдении, что в CPS, поскольку ни одна функция никогда не возвращает (возвращает компиляцию в хвостовые вызовы продолжения), старые фреймы стека никогда не пересматриваются.Стек можно просто увеличить, а когда он достигнет предела, его можно «перемотать» обратно наверх.Цыпленок Схема реализует концепцию;это стоит исследовать, если вы заинтересованы в продолжении.Chicken Scheme компилируется в C-код, который использует обычный C-стек.Однако сгенерированные функции никогда не возвращаются: они имитируют возврат, вызывая продолжения, и поэтому стек увеличивается.Еще более увлекательно то, что объекты, которые мы обычно понимаем как динамический материал, также выделяются из стека.Поскольку ничего не возвращается, эти объекты в безопасности.При достижении определенного предела стека все находящиеся в стеке объекты перемещаются в кучу, и указатель стека перематывается обратно наверх.

1 голос
/ 08 июня 2019

Сначала. У всех языков есть продолжения. Когда вы делаете 7 + n * 5, JavaScript переупорядочивает это в mul_k(n, 5, (_v) => (add _v 7 k), где k - это функция, которая делает все, что радует после этого выражения.

Теперь первый аргумент mul_k является продолжением. Ничего страшного в этом нет, кроме одного маленького размышления. Вы никогда больше ничего не вернете. Каждое «возвращение» просто передается его продолжению, которое всегда является хвостовым вызовом.

Рекурсивная функция, которая сама по себе не является хвостовой рекурсией, будет создавать новое замыкание на каждом шаге и вкладывать следующий. Они хранятся в куче, поэтому не хвостовые рекурсивные функции превращаются в хвостовые вызовы с множеством созданных вложенных замыканий.

Вот небольшой пример:

(define (get-c) (call/cc (lambda (cont) cont)))

(let ((example (get-c)))
  (displayln example)
  (if (procedure? example)
      (example 10)
      "done"))

Давайте представим, что это целая программа. Давайте просто напишем это в JavaScript.

// simple CPS version of displayln
const displayln = (arg, k) k(console.log(arg));

// simple CPS version of procedure?
const isProcedure = (arg, k) k(arg instanceOf Function);

// Simple CPS version of call/cc
const callCC = (userFun, callCCK) 
  => userFun((result, actualK) => callCCK(result), callCCK);

// simple top level continutation. Not a CPS function.
const kTopLevel = console.log;

// the user function get-c transformed into CPS
const getC = getCK => callCC((cont, k) => k(cont), getCK);

// the let code transformed into CPS
getC((example) => // c1
  displayln(example, (_undefined) => // c2 
    isProcedure(example, (result) => // c3
      result ? example(10, kTopLevel) : kTopLevel("done"))

Вот что происходит:

  • getC получает полное продолжение (c1) и вызывает callCC
  • callCC звонки c1 с получением (result, _) => c1(result) как example
  • display печатает example, продолжение, передает свое неопределенное возвращаемое значение своему продолжению c2
  • isPorcedure на example и, будучи продолжением, он передает true как result продолжению c3
  • будучи true, он вызывает example(10, kTopLevel), который становится c1(10), таким образом 10 как пример
  • display отпечатки, например , the number 10 , passes its underfined return value to its continuation c2`
  • isProcedure на example передает false как result в продолжение c3
  • Быть false это вызывает TopLevel("dome")
  • Печать верхнего уровня "сделано"

Как видите. call/cc легко сделать, если код преобразуется в CPS до выполнения . JavaScript очень хорошо поддерживает CPS.

Чтобы помочь с тем, как преобразовать код в CPS, Мэтт Майт сделал это бесчисленное количество раз в своих эссе Ищите продолжения в этом списке. Он даже сделал это в JavaScript .

Теперь, если ваша реализация нуждается в интерпретации, вы можете сделать то же преобразование в Scheme и интерпретировать его вместо пользовательского кода. Если у вас есть барьеры продолжения, вам нужен CPS от call/cc до барьера.

...