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

от автора

Пришла мне однажды идея: есть стек вызовов и стек как структура данных. А нельзя ли использовать стек вызовов для хранения данных?
Немного поразмыслив я понял, что можно, только с ограничениями: во первых для обработки значений придётся использовать колбеки (ведь пока значение на стеке, нельзя выходить из того вызова, в котором мы его сохранили). Во вторых доступ строго 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(); } 

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

ссылка на оригинал статьи http://habrahabr.ru/post/178311/


Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *