スタック構造

計算機科学における「スタック」は、ハードウェアとソフトウェアの両方で重要な役割を果たす概念です。それぞれのスタックについて説明します。

1. ハードウェア・スタック: ハードウェア・スタックは、コンピュータのCPU（中央処理装置）によって直接管理されるメモリ領域です。主にプログラムの実行時に使用され、サブルーチン（関数）の呼び出し、局所変数の割り当て、復帰アドレスの保持など、プログラムの実行フローを管理するために利用されます。通常、スタックポインタと呼ばれるレジスタがスタックのトップを示し、プッシュおよびポップ命令によってスタック上でデータを操作します。ハードウェア・スタックは、プログラムの制御フローに関連した低レベルの操作に使用されます。
2. ソフトウェア・スタック: ソフトウェア・スタックは、プログラミング言語やアプリケーションソフトウェア内で使用される抽象化されたデータ構造です。通常、動的メモリの一部として実装され、プログラムの実行中に必要なデータや関数呼び出しの情報を保持します。ソフトウェア・スタックは、関数の呼び出しと復帰、ローカル変数の格納、式の評価など、高レベルのプログラムの実行に使用されます。プログラミング言語や実行環境によっては、ソフトウェア・スタックが自動的に管理され、プログラマが明示的にスタック操作を行う必要がない場合もあります。

ハードウェア・スタックとソフトウェア・スタックは、異なるレベルでプログラムの実行を支援し、プログラムの制御フローやデータ管理に不可欠な役割を果たします。

スタックの基本

スタックは、データを一時的に保持するためのデータ構造であり、後入れ先出し（LIFO: Last In, First Out）の原則に基づいて動作します。これは、最後に追加された要素が最初に取り出されることを意味します。

スタックの操作

スタックは通常、次の2つの基本操作で構成されます：

1. プッシュ（Push）: 新しい要素をスタックに追加します。新しい要素はスタックの一番上に配置されます。
2. ポップ（Pop）: スタックから要素を取り出します。取り出されるのは常にスタックの一番上にある要素です。

様々なプログラミング言語におけるスタックとその操作

ほとんどのプログラミング言語には、スタックを操作するための組み込み関数や標準ライブラリがあります。例えば、C言語では配列を用いてスタックを実装することが一般的です。JavaやPythonなどの高水準言語では、スタックを抽象化したクラスやライブラリが提供されています。

以下は、様々なプログラミング言語におけるスタックの標準的な実装方法の表です。

言語毎のスタックの標準的な実装方法

プログラミング言語	スタックの実装方法
JavaScript	配列 (Array)
Python	リスト (List)
Ruby	配列 (Array)
Java	java.util.Stack クラス
C++	std::stack コンテナ
Rust	std::collections::VecDeque
Go	スライス (Slice)
Scheme	リスト (List)
C#	System.Collections.Generic.Stack クラス
Kotlin	java.util.Stack クラス
Scala	scala.collection.mutable.Stack クラス
Swift	配列 (Array)
Haskell	リスト (List)

これらの実装方法は、それぞれの言語で一般的なものであり、要素の追加、削除、参照、空のチェック、サイズの取得などの操作を提供します。

反復処理

スタックは、再帰的なアルゴリズムを反復的に解決するのに役立ちます。例えば、深さ優先探索（DFS）アルゴリズムなどの多くのアルゴリズムは、再帰的に呼び出す代わりに、スタックを使用して反復的に解決することができます。

逆ポーランド記法とスタック

逆ポーランド記法（逆ポーランド記号法または逆ポーランド式）は、数式や式を表現するための一種の記法です。この記法では、演算子が対応するオペランドの後に置かれます。これにより、括弧の使用や演算子の優先順位の考慮が不要になり、簡潔で計算機で処理しやすい式を得ることができます。

逆ポーランド記法を処理するための効率的な方法の一つが、スタックを利用することです。具体的には、式を左から右にスキャンし、オペランドを見つけるたびにスタックにプッシュします。演算子を見つけた場合は、スタックから必要な数のオペランドをポップし、その演算子を実行して結果をスタックにプッシュします。このプロセスを繰り返し、最終的にスタックには計算結果が残ります。

以下は、逆ポーランド記法をスタックを用いて評価するアルゴリズムの概要です：

1. 式を左から右にスキャンします。
2. オペランドを見つけた場合、スタックにプッシュします。
3. 演算子を見つけた場合、スタックから必要な数のオペランドをポップし、その演算子を実行して結果をスタックにプッシュします。
4. スキャンが終了したら、スタックに残っている要素が計算結果となります。

逆ポーランド記法をスタックを用いて評価することで、演算子の優先順位や括弧の管理などの複雑な処理を省略し、比較的単純なアルゴリズムで式を評価することができます。このため、計算機やプログラミング言語のコンパイラなどで広く利用されています。

Rubyでの実装

Rubyで逆ポーランド記法を評価するための実装を示します。この実装では、スタックを用いて逆ポーランド記法の式を評価します。

Rubyで逆ポーランド記法を評価する実装

# frozen_string_literal: true

# RPNクラスは逆ポーランド記法（Reverse Polish Notation）の式を評価するためのクラスです。
# スタック構造を使用して式を解析し、結果を計算します。
# Rubyでは、Arrayクラスがpop,pushなどのスタックとしてのメソッドが完備されているので継承しました。
class RPN < Array
  # 与えられた逆ポーランド記法の式を評価し、結果を返します。
  # @param expression [String] 評価する式
  # @return [Numeric] 式の評価結果
  def eval(expression)
    expression.split.each do |token|
      case token
      when /\A-?\d+\z/, # 十進数
           /\A[+-]?0[Bb][01]+\z/, # 2進数
           /\A[+-]?0[Oo][0-7]+\z/, # 8進数
           /\A[+-]?0[Xx][0-9A-Fa-f]+\z/ # 10進数
        push Integer(token)
      when /\A-?\d+(\.\d+)?([eE][-+]?\d+)?\z/ # 浮動小数点数
        push(token.to_f)
      when *%w[+ - * / % ** & | ^ << >> == !=] # 二項演算子
        left, right = pop(2)
        push left.send(token.to_sym, right)
      when *%w[~ ! abs to_i to_f to_r to_c] # 単項演算子
        push pop.send(token.to_sym)
      else
        raise RuntimeError, "Invalid operator: #{token}"
      end
    end

    # 最終的な結果はスタックの一番上に残る
    peek
  end

  # スタックの一番上の値を返しますが、スタックから削除しません。
  # @return [Numeric, nil] スタックの一番上の値。スタックが空の場合はnilを返します。
  alias peek last
end

require 'minitest/spec'

describe RPN do
  let(:rpn) { RPN.new }

  describe '#eval' do
    it 'returns the evaluation result of the given RPN expression' do
      expect(rpn.eval('5')).must_equal 5
      expect(rpn.eval('3 +')).must_equal 8
      expect(rpn.eval('2 -')).must_equal 6
      expect(rpn.eval('4 *')).must_equal 24
      expect(rpn.eval('14 3 /')).must_equal 4
      expect(rpn.eval('14 3 %')).must_equal 2
      expect(rpn.eval('2 3 **')).must_equal 8
      expect(rpn.eval('2 0.5 **')).must_equal 1.4142135623730951
      expect(rpn).must_equal [24, 4, 2, 8, 1.4142135623730951]
    end

    it 'eval ^' do
      expect(rpn.eval('5 ~')).must_equal -6
    end
    
    it 'eval == != !' do
      expect(rpn.eval('5 5 ==')).must_equal true
      expect(rpn.eval('5 5 !=')).must_equal false
      expect(rpn.eval('5 5.0 ==')).must_equal true
      expect(rpn.eval('5 5.0 !=')).must_equal false
      expect(rpn.eval('5 5.5 ==')).must_equal false
      expect(rpn.eval('5 5.5 !=')).must_equal true
      expect(rpn.eval('5 5 == !')).must_equal false
      expect(rpn.eval('5 5 != !')).must_equal true
    end
    
    it 'eval abs to_i to_f' do
      expect(rpn.eval('-5 abs')).must_equal 5
      expect(rpn.eval('5 abs')).must_equal 5
      expect(rpn.eval('3.14 to_i')).must_equal 3
      expect(rpn.eval('5 to_f 2 /')).must_equal 2.5
    end
    
    it 'eval abs to_r to_c' do
      expect(rpn.eval('-5 to_r 3 /')).must_equal -5r/3
      expect(rpn.eval('-2 to_c 0.5 **')).must_equal '0.0+1.4142135623730951i'.to_c
    end

    it 'raises an error for invalid expressions' do
      expect { rpn.eval('2 +') }.must_raise TypeError
    end

    it 'raises an error for invalid operator' do
      expect { rpn.eval('@') }.must_raise RuntimeError
    end
  end

  describe '#peek' do
    it 'returns the top element of the stack without removing it' do
      rpn.eval('1 2 3 + +')
      expect(rpn.peek).must_equal 6
    end

    it 'returns nil for an empty stack' do
      expect(rpn.peek).must_be_nil
    end
  end

  describe 'special cases' do
    it 'returns NaN when dividing zero by zero' do
      rpn.eval('0.0 0 /')
      expect(rpn.peek.nan?).must_equal true
      expect { rpn.eval('0 0 /') }.must_raise ZeroDivisionError
    end

    it 'returns Infinity or -Infinity when dividing by zero with proper signs' do
      rpn.eval('1.0 0 /')
      expect(rpn.peek).must_equal Float::INFINITY

      rpn.eval('-1.0 0 /')
      expect(rpn.peek).must_equal(-Float::INFINITY)

      rpn.eval('1 -0.0 /')
      expect(rpn.peek).must_equal(-Float::INFINITY)

      rpn.eval('-1 -0.0 /')
      expect(rpn.peek).must_equal Float::INFINITY

      expect { rpn.eval('-1 -0 /') }.must_raise ZeroDivisionError
    end
  end
end

Minitest.run if $PROGRAM_NAME == __FILE__

このコードは、逆ポーランド記法（RPN）の式を評価するためのRPNクラスを提供します。逆ポーランド記法は、演算子がそのオペランドの後に現れる形式であり、括弧や優先順位の概念がないため、計算が比較的容易になります。

このRPNクラスは、内部的にスタックを使用して式を評価します。式を分割し、各トークンを処理することで、演算子とオペランドを適切に処理し、計算を実行します。

クラスは、Arrayクラスを継承しており、push,popなどのメソッドはArrayの実装を引き継いでいます。

RPNクラスは次のメソッドを提供します：

• eval(expression): 与えられた逆ポーランド記法の式を評価し、結果を返します。
• peek: スタックの一番上の値を返しますが、スタックから削除しません。

テストケースは、Minitestを使用して実装されており、RPNクラスが正しく機能することを確認します。 異常なケースもテストされており、0で割った場合や無限大を扱う場合の振る舞いも検証されています。

Forthとスタック

Forthは、スタック指向のプログラミング言語です。これは、他の言語とは異なり、計算や処理の中心にスタック（stack）を置いています。スタックは、データを一時的に保存するためのメモリ構造であり、LIFO（Last In, First Out）の原則に従います。つまり、最後に追加されたデータが最初に取り出されます。

Forthのプログラミングスタイルは、このスタックを活用しています。Forthのプログラムは、主に単純な命令（ワードと呼ばれます）の連続で構成され、これらの命令は主にスタックの上で動作します。Forthの命令は、スタックに対する操作を行うものであり、通常はスタックに値を積み上げ（push）たり、取り出したり（pop）、その値を操作したりします。

例えば、2つの数値を足すForthのコードを考えてみましょう。この場合、最初に2つの数値をスタックにプッシュし、それから加算の命令を使ってそれらの数値をポップアップして加算します。

5 3 + .

この例では、最初に5と3がスタックにプッシュされ、次に加算命令（+）が実行されて、結果である8が表示される（.は結果を表示するForthの命令です）。

このように、Forthはシンプルで直感的なスタック指向のプログラミングスタイルを採用しており、これによりコードの記述が簡潔で効率的になります。

RubyでForthを実装

Forthは比較的小さな言語なので、サブセットを実装するのは容易です。

実際に Rubyでサンプル実装してみました。

この実装では、dup などのForth基本語彙とユーザー定義ワードは実装済みで、再帰も行えますForthで一般的なリターンスタックではなく、辞書にラムダ式を埋め込んで実現しています。

制御構造は、if-else-then, case-of-endof-endcase, do-loopと ?do-loop を実装し、多重ループには I, J, K の３重まで対応しています。

また、Rubyの演算子とメソッドをワードとして取り込んでいます。 同様にMathモジュールからもワードを取り込んでいます。

forth.rb

# frozen_string_literal: true

class Forth < Array
  Call = Struct.new :addr
  class Return end
  class ReturnFalse end
  Branch = Struct.new :offset
  BranchFalse = Struct.new :offset
  class Case end
  Of = Struct.new :offset
  class EndCase end

  def initialize
    super
    # ループカウンタスタック（I/J/Kを記憶）
    @lcstack = []

    # ループ先頭ワードスタック do/?do - loop/+loop で使用
    @lwstack = []

    # 中間コード列
    @codespace = []
    
    # Rスタック
    @rstack = []

    # 定数辞書
    @constants = {}

    # 変数辞書
    @variables = {}
    @varnames = []

    @words = {
      '.' => ->(x) { print "#{x} " }, # Print the top value of the stack
      '.s' => -> { p self }, # Print the entire stack
      'clear' => -> { clear },
      'cr' => -> { puts },
      'depth' => -> { push size },
      'drop' => ->(x) {},
      'dup' => -> { push peek },
      'nip' => ->(_x1, x2) { push(x2) }, # ( x1 x2 -- x2 ) Drop the second item on the stack
      'over' => ->(x1, x2) { push(x1, x2, x1) }, # ( x1 x2 -- x1 x2 x1 )Copy the second item on the stack to the top
      'rot' => lambda { |x1, x2, x3|
                 push(x2, x3, x1)
               }, # ( x1 x2 x3 -- x2 x3 x1 ) Rotate the top three values on the stack
      '-rot' => lambda { |x1, x2, x3|
                  push(x3, x1, x2)
                }, # ( x1 x2 x3 -- x3 x1 x2 ) Reverse rotate the top three values on the stack
      'swap' => ->(x1, x2) { push(x2, x1) }, # ( x1 x2 -- x2 x1) Swap the top two values of the stack
      'tuck' => lambda { |x1, x2|
                  push(x2, x1, x2)
                }, # ( x1 x2 -- x2 x1 x2 ) Insert a copy of the top item below the second item on the stack
      '2drop' => ->(x1, x2) {}, # ( x1 x2 -- ) スタックの上位2つの値を削除します。
      '2dup' => ->(x1, x2) { push(x1, x2, x1, x2) }, # ( x1 x2 -- x1 x2 x1 x2 ) スタックの上位2つの値を複製します。
      '2nip' => ->(_x1, _x2, x3) { push(x3) }, # ( x1 x2 x3 -- x3 ) スタックの上位2つの値を削除し、3番目の値を残します。
      '2over' => lambda { |x1, x2, x3, x4| # ( x1 x2 x3 x4 -- x1 x2 x3 x4 x1 x2 ) スタックの3番目と4番目の値をコピーして最上位に置きます。
                   push(x1, x2, x3, x4, x1, x2)
                 },
      '2rot' => lambda { |x1, x2, x3, x4, x5, x6| # ( x1 x2 x3 x4 x5 x6 -- x3 x4 x5 x6 x1 x2 ) スタックの上位6つの値を回転させます。
                  push(x3, x4, x5, x6, x1, x2)
                },
      '2swap' => lambda { |x1, x2, x3, x4| # ( x1 x2 x3 x4 -- x3 x4 x1 x2 ) スタックの上位4つの値を交換します。
                   push(x3, x4, x1, x2)
                 },
      '2tuck' => lambda { |x1, x2, x3, x4| # ( x1 x2 x3 x4 -- x3 x4 x1 x2 x3 x4 ) スタックの3番目と4番目の値を2番目と1番目の値の間に挿入します。
                   push(x3, x4, x1, x2, x3, x4)
                 },
      'min' => ->(x1, x2) { push [x1, x2].min },
      'max' => ->(x1, x2) { push [x1, x2].max },
      'nan?' => ->(x) { push x.nan? },
      'words' => lambda do
        @words.select { |k| k.instance_of? String }.keys.sort.each do |k|
          v = @words[k]
          puts "#{k}: ( #{v.parameters.map { |x|
                            case x
                            in [:req, Symbol => x]
                              x.to_s
                            else nil
                            end
                          } * ' ' } )"
        end
        @words.select { |k| k.instance_of? Proc }.keys.each_with_index do |k, index|
          v = @words[k]
          puts "<lamda #{index}>: ( #{v.parameters.map { |x|
                                        case x
                                        in [:req, Symbol => x]
                                          x.to_s
                                        else nil
                                        end
                                      } * ' ' } )"
        end
      end,
      'I' => -> { push @lcstack[-1] },
      'J' => -> { push @lcstack[-2] },
      'K' => -> { push @lcstack[-3] },
      'INFINITY' => -> { push Float::INFINITY },
      '-INFINITY' => -> { push(-Float::INFINITY) },
      'NAN' => -> { push Float::NAN },
      'EPSILON' => -> { push Float::EPSILON },
      'PI' => -> { push Math::PI },

      'constant' => lambda {
        @evalstack.push(lambda { |word|
          if @constants.include? word
            puts "duplicate define #{word}"
          else
            @constants[word] = pop
          end
          @evalstack.pop
        })
      },
      'variable' => lambda {
        @evalstack.push(lambda { |word|
          @variables[word] = nil
          @evalstack.pop
        })
      },
      ':' => lambda { # ワード定義
        push ':'
        define_word
      }

    }

    # Import from Numeric
    %w[negative? zero? [] abs rationalize class
       to_c to_f to_i to_r
       ! != == < <= > >= -@ ~
       + - * / % divmod **].each do |word|
      m = word.to_sym
      ary_ = [1.0, 1, 1r, 1i]
      q = ary_.each { |n| break n if n.respond_to? m }
      next if q == ary_

      case q.method(m).parameters
      in [] then @words[word] = ->(x) { push x.send(m) }
      in [[:rest]] => a then @words[word] = ->(x1, x2) { push x1.send(m, x2) }
      in [[:req]] then  @words[word] = ->(x1, x2) { push x1.send(m, x2) }
      else
      end
    end

    # Import from Math module
    %w[sin cos tan sqrt cbrt].sort.each do |word|
      m = word.to_sym
      case Math.method(m).parameters
      in [[:req]] then @words[word] = ->(x) { push Math.send(m, x) }
      in [[:rest]] then @words[word] = ->(x) { push Math.send(m, x) }
      in [[:req], [:req]] then @words[word] = ->(x1, x2) { push Math.send(node, x1, x2) }
      else
      end
    end

    # ワードに別名を定義
    {
      'negate' => '-@',
      'invert' => '~',
      '=' => '==',
      '<>' => '!='
    }.each { |key, value| @words[key] = @words[value] }

    # ワード定義中に有効なワード
    @keywords = {
      ';' => lambda {
        name, *body = slice!(rindex(':')..-1).drop(1)

        start = @codespace.size
        body.each { |word| @codespace.push word }
        @codespace.push Return.new
        @words[name] = Call.new(start)

        # @words[name] = -> { body.each { |word| eval word } }
        enddef_word
      },
      'if' => lambda {
        push 'if'
        define_word
      },
      'then' => lambda {
        body = slice!(rindex('if')..-1).drop(1)
        _then = body.take_while { |word| word != 'else' }
        _else = body.drop_while { |word| word != 'else' }.drop_while { |word| word == 'else' }

        start = @codespace.size
        if _else.size > 0
          _then.push Return.new
          @codespace.push BranchFalse.new _then.size
          _then.each { |word| @codespace.push word }
          _else.each { |word| @codespace.push word }
          @codespace.push Return.new
        else
          @codespace.push ReturnFalse.new
          _then.each { |word| @codespace.push word }
          @codespace.push Return.new
        end

        name = Call.new(start)
        push(name)
        @words[name] = name # XXX
        enddef_word
      },
      'case' => lambda {
        push 'case'
        @casestack ||= []
        @casestack.push []
        define_word
      },
      'of' => lambda {
        stmt = @casestack.last.empty? ? 'case' : 'endof'
        _when = slice!(rindex(stmt)..-1).drop(1)
        @casestack.last << _when
        push 'of'
      },
      'endof' => lambda {
        body = slice!(rindex('of')..-1).drop(1)
        @casestack.last.last[1] = body
        push 'endof'
      },
      'endcase' => lambda {
        default_ = slice!(rindex('endof')..-1).drop(1)
        tbl = @casestack.pop

        start = @codespace.size

        @codespace.push Case.new
        tbl.each do |w, body|
          @codespace.push w
          body.push EndCase.new
          @codespace.push Of.new body.size
          body.each { |word| @codespace.push word }
        end
        default_.each { |word| @codespace.push(word) }
        @codespace.push EndCase.new
        
        word = Call.new start

        push(word)
        @words[word] = word
        enddef_word
      },
      'do' => lambda {
        push 'do'
        @lwstack.push 'do'
        define_word
      },
      '?do' => lambda {
        push '?do'
        @lwstack.push '?do'
        define_word
      },
      'loop' => lambda {
        stmt = @lwstack.pop
        body = slice!(rindex(stmt)..-1).drop(1)

        word = case stmt
               in 'do'
                 lambda { |limit, start|
                   level = @lcstack.size
                   @lcstack.push start
                   loop do
                     body.each { |word| eval(word) }
                     @lcstack[level] += 1
                     break unless @lcstack[level] <= limit
                   end
                   @lcstack.pop
                 }
               in '?do'
                 lambda { |limit, start|
                   level = @lcstack.size
                   @lcstack.push start
                   while @lcstack[level] <= limit
                     body.each { |word| eval(word) }
                     @lcstack[level] += 1
                   end
                   @lcstack.pop
                 }
               end
        push(word)
        @words[word] = word
        enddef_word
      },
      '+loop' => lambda {
        stmt = @lwstack.pop
        body = slice!(rindex(stmt)..-1).drop(1)
        word = case stmt
               in 'do'
                 lambda { |limit, start|
                   level = @lcstack.size
                   @lcstack.push start
                   eval(body.last)
                   step = pop
                   loop do
                     body.each { |word| eval(word) }
                     @lcstack[level] += step
                     break unless @lcstack[level] <= limit
                   end
                   @lcstack.pop
                 }
               in '?do'
                 lambda { |limit, start|
                   level = @lcstack.size
                   @lcstack.push start
                   eval(body.last)
                   step = pop
                   while @lcstack[level] <= limit
                     body.each { |word| eval(word) }
                     @lcstack[level] += step
                   end
                   @lcstack.pop
                 }
               end

        push(word)
        @words[word] = word
        enddef_word
      },
      '."' => lambda {
        push '."'
        @evalstack.push(lambda do |word|
          case word
          when /(.*)"$/
            push ::Regexp.last_match(1)
            body = slice!(rindex('."')..-1).drop(1)
            word = -> { push body * ' ' }
            push(word)
            @words[word] = word
            @evalstack.pop
          else
            push(word)
          end
        end)
      },
      '(' => lambda {
        push '('
        @evalstack.push(lambda do |word|
          case word
          when ')'
            slice!(rindex('(')..-1).drop(1)
            @evalstack.pop
          else
            push(word)
          end
        end)
      }
    }

    # キーワードに別名を定義
    {
      'endif' => 'then'
    }.each { |key, value| @keywords[key] = @keywords[value] }

    # evaluator stack
    @evalstack = [method(:eval)]
  end
  alias peek last

  def eval(word)
    case word
    in /\A-?\d+\z/ # Decimal integer
      push Integer(word)
    in /\A[+-]?0[Bb][01]+\z/ # Binary integer
      push Integer(word)
    in /\A[+-]?0[Oo][0-7]+\z/ # Octal integer
      push Integer(word)
    in /\A[+-]?0[Xx][0-9A-Fa-f]+\z/ # Hexadecimal integer
      push Integer(word)
    in /\A[+-]?\d+(\.\d+)?([eE][-+]?\d+)?\z/ # Floating point number
      push Float(word)
    else
      if @constants.include? word
        push @constants[word]
        return
      end

      if @variables.include? word
        @varnames.push word
        @evalstack.push(lambda { |word|
          case word
          in '!'
            @variables[@varnames.pop] = pop
          in '@'
            push @variables[@varnames.pop]
          end
          @evalstack.pop
        })
        return
      end

      case @words[word]
      in Proc => proc then
        n = proc.parameters.reduce(0) do |result, el|
          el.first == :req ? result + 1 : result
        end
        proc[*pop(n)]
      in Call => call then
        addr = call.addr
        ip = addr
        loop do
          word = @codespace[ip]
          case word
          in Return then break
          in ReturnFalse then
            break unless pop
          in BranchFalse => bf then
            ip += bf.offset unless pop
          in Case => _case then
            @rstack.push pop
          in Of => of then
            ip += of.offset unless @rstack.last == pop
          in EndCase => endcase then
            @rstack.pop
            break
          else
            eval(word)
          end
          ip += 1
        end
      else
        raise "#{__method__}: Unknown word(#{word}(#{word.class}))"
      end
    end
    self
  end

  def eval_line(line)
    line.split.each { |word| @evalstack.last[word] }
    self
  end

  def repl
    while (line = gets)
      eval_line(line)
    end
  end

  private

  def define_word
    @evalstack.push(lambda do |word|
      @keywords[word] ? @keywords[word][] : push(word)
    end)
  end

  def enddef_word = @evalstack.pop
end

require 'minitest/spec'

# 標準出力をキャプチャして文字列として返す
def capture_stdout
  original_stdout = $stdout
  $stdout = StringIO.new
  yield
  $stdout.string
ensure
  $stdout = original_stdout
end

describe Forth do
  before do
    @forth = Forth.new
  end

  describe 'basic operation' do
    it 'initialize' do
      _(@forth.eval_line('')).must_equal []
    end

    it '.' do
      actual_output = capture_stdout { @forth.eval_line('123 .') }
      _(actual_output).must_equal '123 '
    end

    it '.s' do
      actual_output = capture_stdout { @forth.eval_line('123 .s') }
      _(actual_output).must_equal "[123]\n"
    end

    it 'words' do
      skip
      @forth.eval_line(': cube dup dup * * ;')
      @forth.eval_line(%(: sign dup 0 < if -1 else dup 0 > if 1 else 0 then then ;))
      @forth.eval_line(%(: d34 3 1 do 4 1 do I J loop loop ; d34))
      actual_output = capture_stdout { @forth.eval_line('words') }
      _(actual_output).must_equal ''
    end

    it 'stack op.' do
      _(@forth.eval_line('1')).must_equal [1]
      _(@forth.eval_line('2')).must_equal [1, 2]
      _(@forth.eval_line('+')).must_equal [3]
    end

    it 'to_i' do
      _(@forth.eval_line(%(3.1415926536))).must_equal [3.1415926536]
      _(@forth.eval_line(%(to_i))).must_equal [3]
    end

    it 'to_f' do
      _(@forth.eval_line(%(3))).must_equal [3]
      _(@forth.eval_line(%(to_f))).must_equal [3.0]
    end

    it 'to_c' do
      _(@forth.eval_line(%(-2))).must_equal [-2]
      _(@forth.eval_line(%(to_c))).must_equal [-2]
      _(@forth.eval_line(%(0.5 **))).must_equal [(0.0 + 1.4142135623730951i)]
    end

    it 'to_r' do
      _(@forth.eval_line(%(12))).must_equal [12]
      _(@forth.eval_line(%(to_r))).must_equal [12]
      _(@forth.eval_line(%(18 /))).must_equal [Rational(2, 3)]
      _(@forth.eval_line(%(0.0 /))).must_equal [Float::INFINITY]
      _(@forth.eval_line(%(0.0 to_r 0.0 / nan?))).must_equal [Float::INFINITY, true]
      _ { @forth.eval_line(%(12 to_r 0 /)) }.must_raise ZeroDivisionError
    end

    it 'extensive func.' do
      _(@forth.eval_line(%(9 5 divmod))).must_equal [[1, 4]]
      _(@forth.eval_line(%(clear 27 cbrt))).must_equal [3]
      _(@forth.eval_line(%(clear PI 4 / sin))).must_equal [0.7071067811865475]
      _(@forth.eval_line(%(clear 0.0 zero?))).must_equal [true]
      _(@forth.eval_line(%(clear 0b1111 0 []))).must_equal [1]
      _(@forth.eval_line(%(clear 0b1111 1 []))).must_equal [1]
      _(@forth.eval_line(%(clear 0b1111 2 []))).must_equal [1]
      _(@forth.eval_line(%(clear 0b1111 3 []))).must_equal [1]
      _(@forth.eval_line(%(clear 0b1111 4 []))).must_equal [0]
      _(@forth.eval_line(%(clear 73 42 rationalize class))).must_equal [Rational]
    end
  end

  describe 'Basic words' do
    it 'should execute . correctly' do
      output = capture_stdout { @forth.eval_line(%(123 .)) }
      _(output).must_equal '123 '
    end

    it 'should execute .s correctly' do
      output = capture_stdout { @forth.eval_line(%(1 2 3 .s)) }
      _(output).must_equal "[1, 2, 3]\n"
    end

    it 'should execute clear correctly' do
      @forth.eval_line(%(1 2 3 clear))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[]\n"
    end

    it 'should execute depth correctly' do
      @forth.eval_line(%(1 2 3 depth))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 2, 3, 3]\n"
    end

    it 'should execute drop correctly' do
      @forth.eval_line(%(1 2 3 drop))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 2]\n"
    end

    it 'should execute dup correctly' do
      @forth.eval_line(%(1 2 dup))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 2, 2]\n"
    end

    it 'should execute nip correctly' do
      @forth.eval_line(%(1 2 3 nip))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 3]\n"
    end

    it 'should execute over correctly' do
      @forth.eval_line(%(1 2 over))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 2, 1]\n"
    end

    it 'should execute rot correctly' do
      @forth.eval_line(%(1 2 3 rot))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[2, 3, 1]\n"
    end

    it 'should execute -rot correctly' do
      @forth.eval_line(%(1 2 3 -rot))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[3, 1, 2]\n"
    end

    it 'should execute swap correctly' do
      @forth.eval_line(%(1 2 swap))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[2, 1]\n"
    end

    it 'should execute tuck correctly' do
      @forth.eval_line(%(1 2 tuck))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[2, 1, 2]\n"
    end

    it 'should execute 2drop correctly' do
      @forth.eval_line(%(1 2 3 4 2drop))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 2]\n"
    end

    it 'should execute 2dup correctly' do
      @forth.eval_line(%(1 2 2dup))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 2, 1, 2]\n"
    end

    it 'should execute 2nip correctly' do
      @forth.eval_line(%(1 2 3 4 2nip))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 4]\n"
    end

    it 'should execute 2over correctly' do
      @forth.eval_line(%(1 2 3 4 2over))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[1, 2, 3, 4, 1, 2]\n"
    end

    it 'should execute 2rot correctly' do
      @forth.eval_line(%(1 2 3 4 5 6 2rot))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[3, 4, 5, 6, 1, 2]\n"
    end

    it 'should execute 2swap correctly' do
      @forth.eval_line(%(1 2 3 4 2swap))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[3, 4, 1, 2]\n"
    end

    it 'should execute 2tuck correctly' do
      @forth.eval_line(%(1 2 3 4 2tuck))
      _(capture_stdout { @forth.eval_line('.s') }).must_equal "[3, 4, 1, 2, 3, 4]\n"
    end
  end

  describe 'arithmetic operations' do
    it 'should perform arithmetic operations correctly' do
      _(@forth.eval_line(%(5 3 + 2 *))).must_equal [16]
    end

    it '!' do
      _(@forth.eval_line(%(clear 1 !))).must_equal [false]
      _(@forth.eval_line(%(clear 0 !))).must_equal [false]
      _(@forth.eval_line(%(clear 0 1 < !))).must_equal [false]
    end

    it '!= ==' do
      _(@forth.eval_line(%(clear 1 1 !=))).must_equal [false]
      _(@forth.eval_line(%(clear 1 1 ==))).must_equal [true]
      _(@forth.eval_line(%(clear 0 1 !=))).must_equal [true]
      _(@forth.eval_line(%(clear 0 1 ==))).must_equal [false]
      _(@forth.eval_line(%(clear 1 1.0 !=))).must_equal [false]
      _(@forth.eval_line(%(clear 1 1.0 ==))).must_equal [true]
      _(@forth.eval_line(%(clear 0 1.0 !=))).must_equal [true]
      _(@forth.eval_line(%(clear 0 1.0 ==))).must_equal [false]
      _(@forth.eval_line(%(clear 1.0 1 !=))).must_equal [false]
      _(@forth.eval_line(%(clear 1.0 1 ==))).must_equal [true]
      _(@forth.eval_line(%(clear 0.0 1 !=))).must_equal [true]
      _(@forth.eval_line(%(clear 0.0 1 ==))).must_equal [false]
      _(@forth.eval_line(%(clear NAN 1 ==))).must_equal [false]
      _(@forth.eval_line(%(clear NAN 1 !=))).must_equal [true]
      _(@forth.eval_line(%(clear NAN NAN ==))).must_equal [false]
      _(@forth.eval_line(%(clear NAN NAN !=))).must_equal [true]
    end

    it 'abs' do
      _(@forth.eval_line(%(4 abs))).must_equal [4]
      _(@forth.eval_line(%(clear -4 abs))).must_equal [4]
      _(@forth.eval_line(%(clear -9 to_c 0.5 ** 4 + abs))).must_equal [5]
    end

    it 'min max' do
      _(@forth.eval_line(%(4 1 min))).must_equal [1]
      _(@forth.eval_line(%(4 max))).must_equal [4]
    end

    it 'negate invert' do
      _(@forth.eval_line(%(1 negate))).must_equal [-1]
      _(@forth.eval_line(%(negate))).must_equal [1]
      _(@forth.eval_line(%(4 invert))).must_equal [1, -5]
    end

    it 'negative?' do
      _(@forth.eval_line(%(clear -1 negative?))).must_equal [true]
      _(@forth.eval_line(%(clear 0 negative?))).must_equal [false]
      _(@forth.eval_line(%(clear 1 negative?))).must_equal [false]
      _(@forth.eval_line(%(clear -1.0 negative?))).must_equal [true]
      _(@forth.eval_line(%(clear 0.0 negative?))).must_equal [false]
      _(@forth.eval_line(%(clear 1.0 negative?))).must_equal [false]
      _(@forth.eval_line(%(clear -0.0 negative?))).must_equal [false]
    end
  end
  describe 'comparison operations' do
    it 'should compare values correctly' do
      _(@forth.eval_line(%(5 3 < 5 3 > 5 5 ==))).must_equal [false, true, true]
    end
  end

  describe 'dup' do
    it 'should duplicate the top value of the stack' do
      _(@forth.eval_line(%(5 dup))).must_equal [5, 5]
    end
  end

  describe 'drop' do
    it 'should remove the top value from the stack' do
      _(@forth.eval_line(%(5 drop))).must_equal []
    end
  end

  describe 'swap' do
    it '( x1 x2 -- x2 x1 ) should swap the top two values of the stack' do
      _(@forth.eval_line(%(5 10 swap))).must_equal [10, 5]
    end
  end

  describe 'over' do
    it 'should copy the second item on the stack to the top' do
      _(@forth.eval_line(%(5 10 over))).must_equal [5, 10, 5]
    end
  end

  describe 'rot' do
    it 'should rotate the top three values on the stack' do
      _(@forth.eval_line(%(5 10 15 rot))).must_equal [10, 15, 5]
    end
  end

  describe '-rot' do
    it 'should reverse rotate the top three values on the stack' do
      _(@forth.eval_line(%(5 10 15 -rot))).must_equal [15, 5, 10]
    end
  end

  describe 'nip' do
    it '( x1 x2 -- x2 ) should drop the second item on the stack' do
      _(@forth.eval_line(%(5 10 nip))).must_equal [10]
    end
  end

  describe 'tuck' do
    it 'should insert a copy of the top item below the second item on the stack' do
      _(@forth.eval_line(%(5 10 tuck))).must_equal [10, 5, 10]
    end
  end

  describe 'constant' do
    it 'define constant' do
      _(@forth.eval_line(%(42 constant C1))).must_equal []
      _(@forth.eval_line(%(12 C1))).must_equal [12, 42]
      actual_output = capture_stdout do
        _(@forth.eval_line(%(34 constant C1))).must_equal [12, 42, 34]
      end
      _(actual_output).must_equal "duplicate define C1\n"
    end
  end

  describe 'variable' do
    it 'define variable' do
      _(@forth.eval_line(%(variable v1))).must_equal []
      _(@forth.eval_line(%(12 v1 !))).must_equal []
      _(@forth.eval_line(%(v1 @ ))).must_equal [12]
    end
  end

  describe 'if-then-else' do
    it 'should execute if-then blocks correctly' do
      _(@forth.eval_line(%(: xxx if 2 + then ;))).must_equal []
      _(@forth.eval_line(%(0 5 3 > xxx))).must_equal [2]
      _(@forth.eval_line(%(5 3 < xxx))).must_equal [2]
    end
    
    it 'should execute if-else-then blocks correctly' do
      _(@forth.eval_line(%(: ttt 5 3 > if 2 2 + else 3 3 + then ;))).must_equal []
      _(@forth.eval_line(%(ttt))).must_equal [4]
      _(@forth.eval_line(%[clear : sss ( n -- ) if ." true" else ." false" then ;])).must_equal []
      _(@forth.eval_line(%(1 2 < sss))).must_equal ['true']
    end

    it 'should execute if-else-endif blocks correctly' do
      _(@forth.eval_line(%(: ttt 5 3 > if 2 2 + else 3 3 + endif ;))).must_equal []
      _(@forth.eval_line(%(ttt))).must_equal [4]
      _(@forth.eval_line(%[clear : sss ( n -- ) if ." true" else ." false" endif ;])).must_equal []
      _(@forth.eval_line(%(1 2 < sss))).must_equal ['true']
    end

    it 'should execute if-then-else nested blocks correctly' do
      _(@forth.eval_line(%(: c dup dup * * ; 3 c))).must_equal [27]
      _(@forth.eval_line(%(clear))).must_equal []
      _(@forth.eval_line(%(: sign dup 0 < if -1 else dup 0 > if 1 else 0 then then ;))).must_equal []
      _(@forth.eval_line(%(123 sign))).must_equal [123, 1]
      _(@forth.eval_line(%(clear -123 sign))).must_equal [-123, -1]
      _(@forth.eval_line(%(clear 0.0 sign))).must_equal [0.0, 0]
      _(@forth.eval_line(%(clear 0 sign))).must_equal [0.0, 0]
    end
  end

  describe 'case _ of ... endof _ of ... endof default endcase' do
    it 'should execute case-endcase correctly' do
      _(@forth.eval_line(%(: t case 1 of 111 endof 2 of 222 endof 3 of 333 endof 999 endcase ;))).must_equal []

      _(@forth.eval_line(%(clear 2 t ))).must_equal [222]
      _(@forth.eval_line(%(clear 1 t ))).must_equal [111]
      _(@forth.eval_line(%(clear 3 t ))).must_equal [333]
      _(@forth.eval_line(%(clear 0 t ))).must_equal [999]
      _(@forth.eval_line(%(clear 2.0 t ))).must_equal [222]
      _(@forth.eval_line(%(clear 1.0 t ))).must_equal [111]
      _(@forth.eval_line(%(clear 3.0 t ))).must_equal [333]
      _(@forth.eval_line(%(clear 0.0 t ))).must_equal [999]
    end
  end

  describe 'do loop' do
    it 'should execute do loops correctly' do
      _(@forth.eval_line(%(: d3 3 1 do I loop ; d3))).must_equal [1, 2, 3]
    end

    it 'should execute do +loops correctly' do
      _(@forth.eval_line(%(: d15 15 1 do I 5 +loop ;))).must_equal []
    end

    it 'should execute do loops nested correctly' do
      _(@forth.eval_line(%(: d34 3 1 do 4 1 do I J loop
                                      loop ; d34))).must_equal [1, 1, 2, 1, 3, 1, 4, 1, 1, 2, 2, 2, 3, 2, 4, 2, 1, 3,
                                                                2, 3, 3, 3, 4, 3]
    end

    it 'should execute do loops nested correctly w/ stdout' do
      actual_output = capture_stdout do
        @forth.eval_line(%(: d34 3 1 do 4 1 do I . J . ." ," . loop
                                      cr loop ; d34))
      end
      _(actual_output).must_equal <<~EOS
        1 1 , 2 1 , 3 1 , 4 1 ,#{' '}
        1 2 , 2 2 , 3 2 , 4 2 ,#{' '}
        1 3 , 2 3 , 3 3 , 4 3 ,#{' '}
      EOS
    end

    it 'should execute do do +loop loop nested correctly' do
      _(@forth.eval_line(%(: d34 3 1 do 4 1 do I J 2 +loop I
                                      loop ; d34 ))).must_equal [1, 1, 2, 3, 1, 2, 1, 1, 2, 2, 3, 2, 2, 2, 1, 3, 2, 3,
                                                                 3, 2, 3]
    end
  end
end

Minitest.run

再帰的呼び出しとスタック

再帰的呼び出しは、関数やメソッドが自分自身を呼び出すことを指します。このような再帰的呼び出しは、基底ケースと呼ばれる条件で停止するまで、何度も繰り返されます。再帰的なアルゴリズムは、問題をより小さな部分問題に分割し、その結果を組み合わせて全体の解を得るために使用されます。

再帰的呼び出しでは、各関数呼び出しがスタックフレームとしてスタックにプッシュされます。スタックフレームには、関数の引数、ローカル変数、および戻りアドレスなどの情報が含まれます。これにより、再帰的な関数がどこに戻るべきかが確保されます。

再帰的呼び出しのプロセス中、スタックは関数呼び出しの連鎖として構築されます。基底ケースに達すると、再帰呼び出しの連鎖は終了し、スタックは戻り始めます。各関数呼び出しが戻るとき、対応するスタックフレームがポップされ、その関数の実行が終了します。このように、スタックは再帰的呼び出しのために必要な情報を管理し、再帰アルゴリズムの正常な実行を可能にします。

例えば、階乗を計算する再帰関数を考えてみましょう。

def factorial(n)
  return 1 if n == 0
  return n * factorial(n - 1)
end

puts factorial(5) # 出力: 120

この再帰関数では、各呼び出しでスタックに新しいフレームが追加され、nが0になるまで関数が再帰的に呼び出されます。そして、基底ケースに到達したときに再帰が終了し、スタックから各フレームが順番にポップされていきます。

以下は、再帰呼び出しのイメージを表組みで示したものです。

スタックフレーム	関数名	引数	戻りアドレス
Frame 1	factorial	5	Return Address 1
Frame 2	factorial	4	Return Address 2
Frame 3	factorial	3	Return Address 3
Frame 4	factorial	2	Return Address 4
Frame 5	factorial	1	Return Address 5
Frame 6	factorial	0	Return Address 6

各スタックフレームには、再帰的な呼び出しに関連する情報が含まれます。 この情報には、関数名、引数、および戻りアドレス（再帰が終了した後に戻るべき呼び出し元のアドレス）が含まれます。 再帰が進むにつれて、スタックに新しいフレームが追加され、再帰が終了するとスタックからフレームがポップされます。

トピックス

スタックに関連する他のトピックには、以下のようなものがあります：

1. キュー (Queue): スタックと同様に、キューもデータを保持するためのデータ構造ですが、キューは先入れ先出し（FIFO: First In, First Out）の原則に基づいて動作します。キューは、例えば、待ち行列やバッファなどで使用されます。
2. 再帰: スタックと再帰の関係については既に説明しましたが、再帰は関数が自分自身を直接または間接的に呼び出すことを指します。再帰の実行中には、各関数呼び出しがスタックに新しいフレームとしてプッシュされます。
3. スタックの実装: スタックは、リストや配列を用いて簡単に実装することができます。リストや配列の操作（push/pop）を利用して、スタックの基本的な機能を実現します。
4. スタックの最適化: スタックの操作を効率的に行うために、特定のアルゴリズムやデータ構造が使用される場合があります。例えば、動的配列を用いた実装や、スタックポインタを使用してスタックの領域を動的に確保する方法などがあります。
5. スタックの応用: スタックは、プログラミングやアルゴリズムのさまざまな分野で使用されます。例えば、深さ優先探索（DFS）、バックトラック法、構文解析、計算機の評価スタックなどが挙げられます。

これらのトピックは、スタックに関連する概念や応用について更に深く理解する上で重要です。

ユースケース

スタックは、関数の呼び出し、式の評価、ブラウザの履歴管理、Undo/Redo操作など、さまざまなユースケースで使用されます。また、プログラム内で一時的なデータを保持するための一般的な手段としても使用されます。

ベストプラクティス

スタックを使用する際のベストプラクティスには、以下が含まれます：

• スタックの容量を適切に管理し、オーバーフローを防止する。
• データの整合性を維持するため、プッシュとポップの対を正確に管理する。
• 適切なデータ構造やアルゴリズムを選択し、効率的なスタック操作を実行する。

イディオム

スタックを使用する際には、特定のプログラミング言語やコーディングスタイルに固有のイディオムが存在します。例えば、Pythonではリストをスタックとして使用することがよくありますが、特定のメソッド（例えば、append()やpop()）を使用することで、スタック操作を簡潔に実現することができます。

これらの基本的な概念やユースケースを理解し、適切に活用することで、プログラムの効率性やメモリ管理の向上に貢献することができます。