はじめに
本記事シリーズは母国語のプログラミング言語が存在するという文化的価値をアピールするためのもので、プログラミング一般の入門を意図するものではありません。とはいっても題材としては定番アルゴリズムのいくつかを疑似言語ではなくコンパイル・実行可能なプログラミング言語の日本語で書いてみようというたてつけとなります。
Mind(マインド)
プログラミング言語Mind(マインド)は自然な日本語で記述できるスタック指向の軽量中間コードコンパイラ言語です。ただし単語間の分かち書きが必須であくまで形式言語です。逆ポーランド記法1の範囲で分かち書きされた日本語単語の語順が自然と日本語の語順となるという意味の「自然さ」で書くことができ、独自の軽量中間コードのランタイム実行で非常に高速です。実装言語はCまたはMind。初版の登場は1985年で2025年は生誕40周年となりました。
Mind(マインド)の入手方法
無償版のMind version 8 (windows版linux版)を下記の公式サイトからダウンロードできます。フリーメールでかまいませんのでメールアドレスをご登録くださいませ。
定番アルゴリズム:循環キューとは
アルゴリズムは、問題を解決するための手順や計算方法を意味します。アルゴリズムにはいくつかの定番ロジックが存在します。
ここではその中のひとつ「循環キュー」を扱ってみます。「循環キュー」(またはただの「キュー」)は先に入れた要素から順に取り出すデータ構造とロジックです。
この「キュー」には大きくわけて「線形キュー」と「循環キュー」の2つがあります。
「循環キュー」は空いたキューを使いまわしていきますが、「線形キュー」は使いまわさないシンプルなロジックです。今回は「循環キュー」を扱います。
「線形キュー」は、こちらの記事をご参照ください。
お題のソースコード
下図のようなインデックス構造を構築します。循環の様子をわかりやすくするため、キューの最大深さは5とします。
index: 1 2 3 4 5 ...
ではなく
index: 1 2 3 4 5
ということになります。
Mindの配列の基数は1です。基数0の配列を使った一般的なプログラミング言語の実装とはインデックスの扱いが異なる点にご留意ください。
まず、初期状態ではheadが1を指していて、tailは1となっています。
初期状態
index: 1 2 3 4 5
↑
head (取出位置)
↑
tail (挿入位置)
線形キューではtailの初期値は0でしたが循環キューでは1です。(線形キューでもtailの初期値1で実装はできます。)
3つデータを挿入(tailが4へ移動)
index: 1 2 3 4 5
↑
head (取出位置)
↑
tail (挿入位置)
3つデータを挿入すると、tailが4に移動します。このときキューサイズは3に増加します。ここで「キューサイズ」といっているのは値の入っているキューの数を意味します。
1つデータを取出すると、
1つデータを取出(headが2へ移動)
index: 1 2 3 4 5
↑
head (取出位置)
↑
tail (挿入位置)
headが1のデータを返し、headは2へ移動します。キューサイズは1つ減少し2になります。
もう1つデータを取出すると、
もう1つデータを取出(headが3へ移動)
index: 1 2 3 4 5
↑
head (取出位置)
↑
tail (挿入位置)
headが2のデータを返し、headは3へ移動します。キューサイズは1つ減少し1になります。
もう1つデータを取出すると、
もう1つデータを取出(headが4へ移動)
index: 1 2 3 4 5
↑
head (取出位置)
↑
tail (挿入位置)
headが3のデータを返し、headは4へ移動します。キューサイズは1つ減少し0になります。このとき取出位置と挿入位置が同じポジションとなりますが、初期状態が右に3つ移動しているととらえることができます。
ここで再度3つデータを挿入します。ここからが循環の説明です。
3つデータを挿入(tailが2へ移動)
index: 1 2 3 4 5
↑
head (取出位置)
↑
tail (挿入位置)
再度3つデータを挿入すると、tailが2に移動します。このときキューサイズは3に増加します。
3つデータを挿入の1回目で tailが4に挿入してtailが5に移動
3つデータを挿入の2回目で tailが5に挿入してtailが1に移動
3つデータを挿入の3回目で tailが1に挿入してtailが2に移動
データを格納する入れ物は数値の場合は1次元配列の変数とします。インデックスの位置を先頭と尻尾で管理する変数も設けます。キューサイズは別の変数で管理してデータの挿入の都度一つ増加、取り出しの都度一つ減少させます。
下記がソースコード全文となります。今回は他のロジック実装から利用しやすいようライブラリとして定義して、テスト用のメイン部分を別ソースとしました。
ライブラリ
キュー深さ最大は 定数 5。
キュー値は キュー深さ最大の 変数。
キュー先頭は 変数。
キュー尻尾は 変数。
キューサイズは 変数。
キューを初期化するとは (・ → ・)
キュー先頭を セットし
キュー尻尾を セットし ※線形キューはクリア
キューサイズを クリアすること。
キューに入れるとは (キュー値 → ・)
キューサイズが キュー深さ最大に 等しい
ならば 「キューがオーバーフローしました。」で 重大エラー つぎに
(キュー値を) キュー値(キュー尻尾)に 入れ
キュー尻尾を 一つ増加し
※キュー尻尾を循環させる
キュー尻尾が キュー深さ最大より 大きい ならば キュー尻尾を セットし つぎに
キューサイズを 一つ増加すること。
キューから出すとは (・ → 先頭キュー値)
キューサイズが 0に 等しい
ならば 「キューは空です。」で 重大エラー つぎに
キュー値(キュー先頭)を 返し (→ 先頭キュー値)
キュー先頭を 一つ増加し
※キュー先頭を循環させる
キュー先頭が キュー深さ最大より 大きい ならば キュー先頭を セットし つぎに
キューサイズを 一つ減少すること。
キューは空?とは (・ → 真偽)
キューサイズが 0に 等しい。
キューの内部状態を表示するとは (・ → ・)
「インデックス:」を 表示し
キュー深さ最大で 回数指定し
回数を 数値表示し 「 」を 表示し
繰り返す
改行し
「キューの値 :」を 表示し
キュー深さ最大で 回数指定し
キュー値(回数)を 数値表示し 「 」を 表示し
繰り返し
改行すること。
キュー値配列の「キュー深さ最大」は循環しやすいよう説明文と同じ大きさに確保してあります。取り出す前の挿入回数が「キュー深さ最大」を超えた場合はエラーになります。
この実装でも取り出されたデータ領域(取り出し後のインデックスのキュー値)はクリアされません。新しい値が挿入されるまでは、取り出されたインデックスの値の再取り出しは想定していない一般的な実装です。
キュー値配列の状態を表示する「キューの内部状態を表示する」を設けています。
テスト実行用メインプログラム
"queuecirculer"を コンパイルする。
メインとは (・ → ・)
キューを初期化し
「キューの初期状態」を 一行表示し
キューの内部状態を表示し
3で 回数指定し
回数を 数値表示し 「回目」を 一行表示し
「キュー挿入 :」を 表示し
4で 回数指定し
回数を 数値表示し 「 」を 表示し
回数を キューに入れ
繰り返し
改行し
「キューの状態 1,2,3,4を挿入 」を 一行表示し
キューの内部状態を表示し
「キュー取出 :」を 表示し
ここから
キューが空? ならば 打ち切り つぎに
キューから出して 数値表示し 「 」を 表示し
繰り返し
改行し
「キューの状態 4回取り出し 」を 一行表示し
キューの内部状態を表示し
繰り返すこと。
説明文でキューに3つ値を入れていますが、テストプログラムでは4つ値を入れて、4つ取り出しをして、それを3回繰り返しています。
お題のソースコードをコンパイル
では、コンパイルしてみます。Mind8によるコンパイル結果です。
C:\developments\vscode\mind9\algorithm>mind queuecirculertest file
日本語プログラミング言語 Mind Version 8.07 for Windows
Copyright(C) 1985 Scripts Lab. Inc.
コンパイル中 .. 終了
Coping.. c:\pmind\bin\mindex.exe --> queuecirculertest.exe
実行結果
実行結果です。
C:\developments\vscode\mind9\algorithm>queuecirculertest
キューの初期状態
インデックス:1 2 3 4 5
キューの値 :0 0 0 0 0
1回目
キュー挿入 :1 2 3 4
キューの状態 1,2,3,4を挿入
インデックス:1 2 3 4 5
キューの値 :1 2 3 4 0
キュー取出 :1 2 3 4
キューの状態 4回取り出し
インデックス:1 2 3 4 5
キューの値 :1 2 3 4 0
2回目
キュー挿入 :1 2 3 4
キューの状態 1,2,3,4を挿入
インデックス:1 2 3 4 5
キューの値 :2 3 4 4 1
キュー取出 :1 2 3 4
キューの状態 4回取り出し
インデックス:1 2 3 4 5
キューの値 :2 3 4 4 1
3回目
キュー挿入 :1 2 3 4
キューの状態 1,2,3,4を挿入
インデックス:1 2 3 4 5
キューの値 :3 4 4 1 2
キュー取出 :1 2 3 4
キューの状態 4回取り出し
インデックス:1 2 3 4 5
キューの値 :3 4 4 1 2
相当かなり芸のない出力ですが、キューが循環していることが(かろうじて
)わかります
(取り出されても元の値が残っているのでちょっとわかりにくいですね。)
おわりに
いかがでしたでしょうか?わたしはわが国に母語によるプログラミング言語が存在することを誇りに思っております。言語は文化。こんにちの日本語のポップスやアニメソングなどが海外でそのまま歌われるような近況を鑑みますと、純然たる技術基盤として超強力な米欧発プログラミング言語勢と存在意義を争うこともなく、日本語の文化として海外でも日本語プログラミング言語の愛される日が来るのやもしれません。
-
演算子を被演算子の中間に記述する中置記法 1 + 2、前に記述する前置記法(ポーランド記法)+ 1 2、後に記述する後置記法(逆ポーランド記法)1 2 +がある。日本語は1と 2を 足す。 ↩