Как реализовать защищенную рекурсию на строго оцененных языках? - PullRequest
Новая
       63

Как реализовать защищенную рекурсию на строго оцененных языках?

0 голосов
/ 11 мая 2018

Я реализовал кодированный Скоттом тип List в Javascript вместе с перегруженной функцией append, которая имитирует класс типов Semigroup.

append работает просто отлично, но для больших списков это унесет стек. Вот решающая часть моей реализации: 

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));

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

Поскольку эта реализация основана на Haskell, я полагаю, что ленивая оценка и защищенная рекурсия / хвостовая рекурсия по модулю имеют значение: 

(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

При условии, что я правильно понимаю, из-за ленивой оценки (почти) ничего не происходит в Haskell, когда я добавляю список в другой, пока я фактически не сделаю что-то с этим новым списком. В приведенном ниже примере я сложу его.

Что я не понимаю, так это то, как защищенная рекурсия может препятствовать росту рекурсии в стеке вызовов и может ли это поведение быть реализовано явно в строго оцененном языке, таком как Javascript.

Надеюсь, этот вопрос не слишком широк.

Для лучшего понимания, вот полная реализация / пример: 

// type constructor

const Type = name => {
  const Type = tag => Dcons => {
    const t = new Tcons();

    Object.defineProperty(
      t,
      `run${name}`,
      {value: Dcons});

    t[TAG] = tag;
    return t;
  };

  const Tcons =
    Function(`return function ${name}() {}`) ();

  Tcons.prototype[Symbol.toStringTag] = name;
  return Type;
};


const TAG = Symbol("TAG");
const List = Type("List");


// data constructors

const Cons = x => tx => List("Cons") (cases => cases.Cons(x) (tx));
const Nil = List("Nil") (cases => cases.Nil);


// overload binary functions

const overload2 = (name, dispatch) => {
  const pairs = new Map();

  return {
    [`${name}Add`]: (k, v) => pairs.set(k, v),

    [`${name}Lookup`]: k => pairs.get(k),

    [name]: x => y => {
      if (typeof x === "function" && (VALUE in x))
        x = x(y);

      else if (typeof y === "function" && (VALUE in y))
        y = y(x);

      const r = pairs.get(dispatch(x, y));

      if (r === undefined)
        throw new TypeError("...");

      else if (typeof r === "function")
        return r(x) (y);

      else return r;
    }
  }
};


const dispatcher = (...args) => args.map(arg => {
  const tag = Object.prototype.toString.call(arg);
  return tag.slice(tag.lastIndexOf(" ") + 1, -1);
}).join("/");


// Semigroup "typeclass"

const {appendAdd, appendLookup, append} =
  overload2("append", dispatcher);


// List instance for Semigroup

appendAdd("List/List", tx => ty => tx.runList({
  Nil: ty,
  Cons: x => tx_ => Cons(x) (append(tx_) (ty))
}));


// fold

const foldr = f => acc => {
  const aux = tx =>
    tx.runList({
      Nil: acc,
      Cons: x => tx_ => f(x) (aux(tx_))})

  return aux;
};


// data

const tx = Cons(1) (Cons(2) (Nil));
const ty = Cons(3) (Cons(4) (Nil));
const tz = append(tx) (ty);


// run

console.log(
  foldr(x => acc => `${x}${acc}`) (0) (tz) // "12340"
);

1 Ответ

0 голосов
/ 11 мая 2018

Это не настоящий ответ, но выводы, которые я сделал после дальнейшего изучения:

  1. Хвостовая рекурсия по модулю Минусы - TRMC (и «по модулю» для других операций) относится только к строго оцененному контексту, тогда как защищенная рекурсия относится к ленивому вычисленному контексту
  2. TRMC - дорогостоящий метод компиляции, и (вероятно) не имеет смысла внедрять его в пользовательской среде
  3. TRMC требует, чтобы операция была ассоциативной (образует хотя бы полугруппу), чтобы скобки можно было переставить

Эти вопросы и ответы также полезны: функция добавления списка версий с хвостовой рекурсией .

...