html текст
All interests
  • All interests
  • Design
  • Food
  • Gadgets
  • Humor
  • News
  • Photo
  • Travel
  • Video
Click to see the next recommended page
Like it
Don't like
Add to Favorites

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

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


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

материал с habrahabr.ru

1

      Add

      You can create thematic collections and keep, for instance, all recipes in one place so you will never lose them.

      No images found
      Previous Next 0 / 0
      500
      • Advertisement
      • Animals
      • Architecture
      • Art
      • Auto
      • Aviation
      • Books
      • Cartoons
      • Celebrities
      • Children
      • Culture
      • Design
      • Economics
      • Education
      • Entertainment
      • Fashion
      • Fitness
      • Food
      • Gadgets
      • Games
      • Health
      • History
      • Hobby
      • Humor
      • Interior
      • Moto
      • Movies
      • Music
      • Nature
      • News
      • Photo
      • Pictures
      • Politics
      • Psychology
      • Science
      • Society
      • Sport
      • Technology
      • Travel
      • Video
      • Weapons
      • Web
      • Work
        Submit
        Valid formats are JPG, PNG, GIF.
        Not more than 5 Мb, please.
        30
        surfingbird.ru/site/
        RSS format guidelines
        500
        • Advertisement
        • Animals
        • Architecture
        • Art
        • Auto
        • Aviation
        • Books
        • Cartoons
        • Celebrities
        • Children
        • Culture
        • Design
        • Economics
        • Education
        • Entertainment
        • Fashion
        • Fitness
        • Food
        • Gadgets
        • Games
        • Health
        • History
        • Hobby
        • Humor
        • Interior
        • Moto
        • Movies
        • Music
        • Nature
        • News
        • Photo
        • Pictures
        • Politics
        • Psychology
        • Science
        • Society
        • Sport
        • Technology
        • Travel
        • Video
        • Weapons
        • Web
        • Work

          Submit

          Thank you! Wait for moderation.

          Тебе это не нравится?

          You can block the domain, tag, user or channel, and we'll stop recommend it to you. You can always unblock them in your settings.

          • habrahabr.ru
          • домен habrahabr.ru

          Get a link

          Спасибо, твоя жалоба принята.

          Log on to Surfingbird

          Recover
          Sign up

          or

          Welcome to Surfingbird.com!

          You'll find thousands of interesting pages, photos, and videos inside.
          Join!

          • Personal
            recommendations

          • Stash
            interesting and useful stuff

          • Anywhere,
            anytime

          Do we already know you? Login or restore the password.

          Close

          Add to collection

             

            Facebook

            Ваш профиль на рассмотрении, обновите страницу через несколько секунд

            Facebook

            К сожалению, вы не попадаете под условия акции