Реализация стека за счёт … стека вызовов

Пришла мне однажды идея: есть стек вызовов и стек как структура данных. А нельзя ли использовать стек вызовов для хранения данных?
Немного поразмыслив я понял, что можно, только с ограничениями: во первых для обработки значений придётся использовать колбеки (ведь пока значение на стеке, нельзя выходить из того вызова, в котором мы его сохранили). Во вторых доступ строго LIFO.
Реализация — под катом.

В качестве языка я решил использовать Nemerle — знакомый мне .NET + удобство функционального стиля.

Сама реализация внешне проста:

variant StackAction[T]{
  | Push{
    value : T;
    next : void -> StackAction[T];
  }
  | Pop {
    next : T -> StackAction[T];
  }
}

module StackStack{
  public Enter[T](current : StackAction[T].Push) : StackAction[T]{
    def processNext(next : StackAction[T]): StackAction[T]{
      match(next){
      | push is StackAction[T].Push => processNext(Enter(push));
      | pop is StackAction[T].Pop => pop.next(current.value);
      }
    } 
    processNext(current.next());
  }  
}

Для незнакомых с синтаксисом Nemerle:
variant StackAction[T] описывает вариантный generic тип, переменные которого могут принимать значения либо Push, либо Pop. Причём если значение Push, то должны быть поля value (собственно значение, которое мы кладём на стек), и next — колбэк, с пустым списком параметров, возвращающий следующий StackAction. А если Pop, то у него должен быть колбек принимающий в качестве аргумента значение с вершины стека, и также возвращающий следующий StackAction.

Функция Enter реализует саму логику работы со стеком. Внутри неё объявлена локальная функция processNext, которая получает current в качестве замыкания. Тело processNext состоит из одного блока match (сопоставление с образцом). push и pop синонимы next в зависимости от того, какой реальный тип примет значение.

В итоге логика работы Enter: вызвать current.next и передать возвращаемое значение в processNext, возвращаемое из processNext значние вернуть. (В nemerle нет оператора return, и функция возвращает значение из последнего выражения, а match из выполенной ветки)
processNext проверяет переданное ей значение. Если Push, то она вызвает с этим значением Enter, а с результатом выполнения Enter — себя. Таким образом получается цикл — пока колбек не вернёт Pop, выхода из текущего вызова Enter не будет. Если значение next — Pop, то в колбек передаётся из замыкания текущее значение current.value (при этом сама processNext могла уже быть несколько раз рекурсивно вызвана).

В итоге получаем ещё один недостаток: если Pop возьмёт со стека последнее значение и стек опустеет, то вызванный в клиентском коде Enter вернёт то, что вернул последний Pop. Таким образом для работы с нижним значением стека нужно делать отдельный цикл.

В качестве примера использования возьмём вычисление выражения в обратной польской нотации.

def items =  "7 2 3 * -".Split(array[' ']);
mutable currentPosition = 0;

def processNextToken(){
  def action(operation : double * double -> double){
    StackAction.Pop(fun(y){
      StackAction.Pop(fun(x){
        StackAction.Push(operation(x, y), processNextToken);
      });
    });
  }

  if(currentPosition >= items.Length){
    StackAction.Pop(fun(x){
      StackAction.Push(x, fun(){throw Exception("Bad input, not enough operations.")});
    });
  }else{
    currentPosition++;
    mutable value : double;
    match(items[currentPosition-1]){
    | strVal when (Double.TryParse(strVal, out value)) => StackAction.Push(value, processNextToken);
    | "+" => action(_ + _);
    | "-" => action(_ - _);
    | "/" => action(_ / _);
    | "*" => action(_ * _);
    | token => throw Exception($"bad token $token");
    }
  }
}


def calc(current : StackAction[double]){
  match(current){
  | StackAction.Push (_, next) when (next == processNextToken) 
      => calc(StackStack.Enter(current :> StackAction[double].Push));
  | StackAction.Push (res, _) => WriteLine($"Result = $res");
  | StackAction.Pop => throw Exception("Bad input, not enough arguments.");
  }
}

calc(processNextToken());

Краткое пояснение начиная с конца:
calc реализует логику работы с нижним элементом стэка: если вывалился Push с колбеком processNextToken то снова вызываем calc, если вывалился Push с другим колбеком (fun(){throw Exception(«Bad input, not enough operations.»)), значит вся запись обработана и функция вернула конечный результат. Если вывалился Pop, значит последнему действию не хватило аргументов.

processNextToken обрабатывает токены по порядку. Если достигнут конец записи, берём последнее значение со стека и возвращаем его в calc. Если на стеке больше 1 значение будет вызвана анонимная функция fun(){throw Exception(«Bad input, not enough operations.»)}. Если есть ещё токены, берём текущий. Числовой литерал кладём на стек, для арифметических действий вызываем action. Записи _ + _ — особая магия nemerle — частичное выполнение. В данном случае превращает арифметические операторы в функции с двумя аргументами.

action берёт 2 значения со стека, выполняет с ними переданную ей функцию и кладёт результат на стек.

Довольно запутано правда? Можно сделать класс с привычным интерфейсом стека, если перенести стек, хранящий значения в другой поток.

enum Action{
  | Push
  | Pop
}

public class StackEmptyException : Exception{
  public this(message : string){
    base(message);
  }
}

public class ThreadStack[T] : IDisposable{

  class Resident{        
    public mutable volatile action : Action;
    public mutable volatile value : T;
    public mutable volatile exception : Exception;
    public syncIn = AutoResetEvent(false);
    public syncOut = AutoResetEvent(false);

    public start() : void{
      exception = null;
      try{
        mutable current = next();
        while(true){
          match(current){
          | act is StackAction[T].Push => current = StackStack.Enter(act : StackAction[T].Push);
          | StackAction.Pop => throw StackEmptyException("Stack is empty");                    
          }                    
        }
      }catch{
      | e => {exception = e; _ = syncOut.Set();}
      }
    }

    next() : StackAction[T]{
      _ = syncOut.Set();
      _ = syncIn.WaitOne();
      match(action){
      | Push => StackAction.Push(value, next);
      | Pop => StackAction.Pop(fun(x){
        value = x;
        next();});
      }
    }
  }

  private resident : Resident = Resident();
  private thread : Thread;

  public this(){
    thread = Thread(ThreadStart(resident.start));
    thread.Start();
  }

  public Dispose() : void implements IDisposable.Dispose {
    try{
      thread.Abort();
      _ = resident.syncIn.Set();
      thread.Join();
      (resident.syncIn : IDisposable).Dispose();
      (resident.syncOut : IDisposable).Dispose();
    }finally{}
  }

  private checkException() : void{
    when(resident.exception != null) {
      throw resident.exception;
    }
  }

  private exec() : void{
    _ = resident.syncIn.Set();
    _ = resident.syncOut.WaitOne();
    checkException();
  }

  public Push(val : T) : void{
    resident.value = val;
    resident.action = Action.Push;
    exec();
  }

  public Pop() : T{        
    resident.action = Action.Pop;
    exec();
    resident.value;
  }
}

И хотя кода гораздо больше я думаю он уже должен быть понятен тем, кто знает C#. Единственне: конструкция "_ =" сообщает компилятору, что мы игнорируем возваращаемое значение.

А вот и та же обратная польская нотация:

def items =  "7 2 3 * -".Split(array[' ']);
mutable currentPosition = 0;

mutable stack : ThreadStack[double];
try{
  stack = ThreadStack();
  mutable onStack = 0;
  def execOperation(operation : double * double -> double){
    def y = stack.Pop();
    def x = stack.Pop();
    stack.Push(operation(x, y));
    onStack--;
  }

  currentPosition = 0;            
  while(currentPosition < items.Length){
    currentPosition++;
    mutable value : double;
    match(items[currentPosition-1]){
    | strVal when (Double.TryParse(strVal, out value)) => { onStack++; stack.Push(value);}
    | "+" => execOperation(_ + _);
    | "-" => execOperation(_ - _);
    | "/" => execOperation(_ / _);
    | "*" => execOperation(_ * _);
    | token => throw Exception($"bad token $token");
    }
  }
  when(onStack > 1){
    throw Exception("Bad input, not enough operations.");
  }
  WriteLine("Result: " + stack.Pop());            
}catch{
  | e is StackEmptyException => throw Exception("Bad input, not enough arguments.");
}finally{
  stack.Dispose();
}

Ну и конечно статье нужен вывод: даже такие извращения на функциональном языке получаются достаточно ёмкими и понятными (если иметь навык работы с ними). Императивный стиль оказывается многословнее, но всё же для неподготовленного читателя понятнее.