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