スタック構造
計算機科学における「スタック」は、ハードウェアとソフトウェアの両方で重要な役割を果たす概念です。それぞれのスタックについて説明します。
- ハードウェア・スタック: ハードウェア・スタックは、コンピュータのCPU(中央処理装置)によって直接管理されるメモリ領域です。主にプログラムの実行時に使用され、サブルーチン(関数)の呼び出し、局所変数の割り当て、復帰アドレスの保持など、プログラムの実行フローを管理するために利用されます。通常、スタックポインタと呼ばれるレジスタがスタックのトップを示し、プッシュおよびポップ命令によってスタック上でデータを操作します。ハードウェア・スタックは、プログラムの制御フローに関連した低レベルの操作に使用されます。
- ソフトウェア・スタック: ソフトウェア・スタックは、プログラミング言語やアプリケーションソフトウェア内で使用される抽象化されたデータ構造です。通常、動的メモリの一部として実装され、プログラムの実行中に必要なデータや関数呼び出しの情報を保持します。ソフトウェア・スタックは、関数の呼び出しと復帰、ローカル変数の格納、式の評価など、高レベルのプログラムの実行に使用されます。プログラミング言語や実行環境によっては、ソフトウェア・スタックが自動的に管理され、プログラマが明示的にスタック操作を行う必要がない場合もあります。
ハードウェア・スタックとソフトウェア・スタックは、異なるレベルでプログラムの実行を支援し、プログラムの制御フローやデータ管理に不可欠な役割を果たします。
スタックの基本
[編集]スタックは、データを一時的に保持するためのデータ構造であり、後入れ先出し(LIFO: Last In, First Out)の原則に基づいて動作します。これは、最後に追加された要素が最初に取り出されることを意味します。
スタックの操作
[編集]スタックは通常、次の2つの基本操作で構成されます:
- プッシュ(Push): 新しい要素をスタックに追加します。新しい要素はスタックの一番上に配置されます。
- ポップ(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)アルゴリズムなどの多くのアルゴリズムは、再帰的に呼び出す代わりに、スタックを使用して反復的に解決することができます。
逆ポーランド記法とスタック
[編集]逆ポーランド記法(逆ポーランド記号法または逆ポーランド式)は、数式や式を表現するための一種の記法です。この記法では、演算子が対応するオペランドの後に置かれます。これにより、括弧の使用や演算子の優先順位の考慮が不要になり、簡潔で計算機で処理しやすい式を得ることができます。
逆ポーランド記法を処理するための効率的な方法の一つが、スタックを利用することです。具体的には、式を左から右にスキャンし、オペランドを見つけるたびにスタックにプッシュします。演算子を見つけた場合は、スタックから必要な数のオペランドをポップし、その演算子を実行して結果をスタックにプッシュします。このプロセスを繰り返し、最終的にスタックには計算結果が残ります。
以下は、逆ポーランド記法をスタックを用いて評価するアルゴリズムの概要です:
- 式を左から右にスキャンします。
- オペランドを見つけた場合、スタックにプッシュします。
- 演算子を見つけた場合、スタックから必要な数のオペランドをポップし、その演算子を実行して結果をスタックにプッシュします。
- スキャンが終了したら、スタックに残っている要素が計算結果となります。
逆ポーランド記法をスタックを用いて評価することで、演算子の優先順位や括弧の管理などの複雑な処理を省略し、比較的単純なアルゴリズムで式を評価することができます。このため、計算機やプログラミング言語のコンパイラなどで広く利用されています。
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
の3重まで対応しています。
また、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
各スタックフレームには、再帰的な呼び出しに関連する情報が含まれます。 この情報には、関数名、引数、および戻りアドレス(再帰が終了した後に戻るべき呼び出し元のアドレス)が含まれます。 再帰が進むにつれて、スタックに新しいフレームが追加され、再帰が終了するとスタックからフレームがポップされます。
トピックス
[編集]スタックに関連する他のトピックには、以下のようなものがあります:
- キュー (Queue): スタックと同様に、キューもデータを保持するためのデータ構造ですが、キューは先入れ先出し(FIFO: First In, First Out)の原則に基づいて動作します。キューは、例えば、待ち行列やバッファなどで使用されます。
- 再帰: スタックと再帰の関係については既に説明しましたが、再帰は関数が自分自身を直接または間接的に呼び出すことを指します。再帰の実行中には、各関数呼び出しがスタックに新しいフレームとしてプッシュされます。
- スタックの実装: スタックは、リストや配列を用いて簡単に実装することができます。リストや配列の操作(push/pop)を利用して、スタックの基本的な機能を実現します。
- スタックの最適化: スタックの操作を効率的に行うために、特定のアルゴリズムやデータ構造が使用される場合があります。例えば、動的配列を用いた実装や、スタックポインタを使用してスタックの領域を動的に確保する方法などがあります。
- スタックの応用: スタックは、プログラミングやアルゴリズムのさまざまな分野で使用されます。例えば、深さ優先探索(DFS)、バックトラック法、構文解析、計算機の評価スタックなどが挙げられます。
これらのトピックは、スタックに関連する概念や応用について更に深く理解する上で重要です。
ユースケース
[編集]スタックは、関数の呼び出し、式の評価、ブラウザの履歴管理、Undo/Redo操作など、さまざまなユースケースで使用されます。また、プログラム内で一時的なデータを保持するための一般的な手段としても使用されます。
ベストプラクティス
[編集]スタックを使用する際のベストプラクティスには、以下が含まれます:
- スタックの容量を適切に管理し、オーバーフローを防止する。
- データの整合性を維持するため、プッシュとポップの対を正確に管理する。
- 適切なデータ構造やアルゴリズムを選択し、効率的なスタック操作を実行する。
イディオム
[編集]スタックを使用する際には、特定のプログラミング言語やコーディングスタイルに固有のイディオムが存在します。例えば、Pythonではリストをスタックとして使用することがよくありますが、特定のメソッド(例えば、append()
やpop()
)を使用することで、スタック操作を簡潔に実現することができます。
これらの基本的な概念やユースケースを理解し、適切に活用することで、プログラムの効率性やメモリ管理の向上に貢献することができます。