問 題 解 決 と プ ロ グ ラ み 言 語

問 題 解 決 と プ ロ グ ラ み 言 語

若 林 信 夫

1.序 一

あ る問題 が与 え られ た ときそ の解 が一 意 な こ とがわ か っ てい て も,そ の解 決 に は さ まざ まな過 程 が あ る。 解 を導 く途 中経 過を特 に重 視す る とき,人 工 知 能 の 分野 では 「問題 解 決」 とい う概 念 を 用 い る。 解 が 高 々,非 多項 式 時 間で 見 出 され る問題 をrNP」 問題 といい,通 常,高 速 な電 子 計 算機 な しに は解 を見 出 す こ とは で きな い。 また,計 算機 の利 用 のた めに は プ ログ ラム言 語 を介 す る。

プ ログ ラム言 語 は 問題 解 決者 と計 算機 の間 の単 な る通信 の一 媒 介 手段 では な く,問 題 解 決 の方 法 論 を模 索 す る上 で の事 前 的 な手段 に な り うる。 例 えば,再 帰 を 許 さない言 語 で 思 考す るか,再 帰 を 許す 言 語 で思 考す るか,あ るいは 豊 富

な制 御構 造 文 を もつ 言語 で思 考す るか ど うか で 問題 解 決 に差 異 を もた らす 。 現 在,ど ん な計 算機 施 設 で も多数 の プ ログ ラム言語 を保 有 し,ま た計 算機 関

'

連 学 科 は 多 数 の プ ロ グ ラ ム言 語 を 学 生 に 教 育 し て い る。 そ の さ い,ど の 言 語 を どん な 順 序 で ど の よ うに 選 択 ・使 用 す るか は 重 要 な 問 題 に な っ て い る。

現 在,本 学 の 計 算 セ ソ タ ー のMELCOM‑COSMO700で 公 私 問 わ ず に 利 用 で き る プ ログ ラ ム言 語 の 主 な もの は 以 下 の 通 りで あ る。 ア セ ソ ブ ラ レベ ル で は Metasymbo1が 学 生 に 公 開 され て い な い め で,手 作 りのMIX,SAMOS,Z80,

INTEL8080ア セ ソ ブ ラ,MAP,そ し てINTCODE(BCPLの 中 間 語)が あ る。 マ ク ロ ア セ ソ ブ ラ と して は,や は り手 作 りの,GPM,が あ る。 会 話 型 専 門

原稿受領 日1979年1月22日

*本 稿 は文部省科学研 究費一般研 究D(No.368110‑861)の 成果 の一部 であ る。

また,プ ログラム言語 の移植 に際 し,若 林 ゼ ミナ リステ ソの援 助 を得 た。記 して感謝

し た い 。

[78]

、

商 学 討 究 第29巻 第4号 ⁷⁹

の 高 水 準 言 語 に はBASICとAPLが 提 供 され て い る。Pascal‑SやLISPIイ ソ タ プ リー タは 端 末 利 用 を 目的 に 作 成 し,使 用 され て い る。 数 値 計 算 向 き の, ALGOL60,FORTRAN】V(FLAG),事 務 計 算 向 き のCOBOL,両 方 に 向 い たPI/1,Pascal,記 号 処 理 向 き のLISP1.5,SNOBOL.4,シ ス テ ム プ ロ グ ラ ム

く ユ

向 き で 手 作 りの.Plan,BCPLが あ る。

本 稿 は,通 常 の プ ロ グ ラ ミ ソ グ の コ ー ス で 採 択 さ れ る有 名 な 「ハ ノイ の 塔 の 問 題 」 を 上 記 の プ ロ グ ラ ム言 語 か ら13種 選 び コ ー デ ィ ジ グ し,若 干 の べ ソチ マ ー ク テ ス トを 行 な っ て い る。 そ の 経 験 か らプ ロ グ ラ ミ ソ グ教 育 の 観 点 か らプ ロ グ ラ ム 言 語 の 暫 定 的 な 比 較 ・評 価 を 試 み る。 そ の 結 果 は 若 干 の 留 保 条 件 を 必 要 とす るに せ よ,他 の 計 算 機 施 設 に お い て も妥 当 す る こ とが 期 待 で き る。

2.ハ ノ イ の 塔 の 問 題

問 題 解 決 の 例 題 と して 「ハ ノ イ の塔 」 の 問 題 を と りあ げ る。 こ の 問 題 は 周 知 の よ うに 単 な る遊 び に と ど ま らず,オ ペ レ ー シ ョ ソズ リサ ー チ の 最 短 路 問 題, 事 務 処 理 や コ ソパ イ ラ作 成 の 各 種 の 分 類 探 索 技 法(heapsort,treesort,tree

search)と 密 接 な 関 連 が あ る。

ハ ノイ の塔 は フ ラ ソ ス の 数 学 者EdouardLucasに よ り発 見 され,1883年 M.Clausに よ り商 品 化 され た とい わ れ,現 在,ハ ノイ の塔,TowerofTrouble,

TreePuzzleの 名 で 玩 具 と して 製 造 ・販 売 され て い る6ハ ノ イ の塔 に は 次 の物 語 が 結 び つ け られ る。 「ベ ナ レス の 大 き な 寺 院 に 世 界 の 中 心 を 示 す とい う ドー

ムが あ 帆 そ の 下 に 三 本 の ダ イ ヤ モ ソ ドの 針 を 固 定 した 真 ち ゅ うの 台 が あ っ た 。 各 々 の 針 は 約30cmの 高 さ で 適 当 な 厚 み が あ っ た 。 創 世 の 時,神 は64枚 の純 金 の 円盤 を 大 き な も の が 下 に な る よ うに 順 番 に 一 本 の 針 に さ した 。 これ が 婆 羅 門 の 塔 で あ る。 昼 夜 休 む こ とな く,僧 侶 は この 円 盤 を 他 の 針 に 移 しか え る。 一 回 に 一 枚,し か も ど の 円盤 もそ れ よ り大 きな 円 盤 が 上 に こな い よ うに す る。 こ

(1)作 成中 または計画段階 の ものに,C,ICON,RATFOR,INTERLISP,PL360,360

アセ ンブラ/シ ミュ レー タが あ り・Algo168・Simula67・ConcurrenちPascalな ど も考慮中で あ る。

の仕事 が完 了す る とき,塔 も寺 院 も僧侶 もす べ て灰 塵 に帰 し,雷 鳴 と と もに こ の世 は 消失 して しま う」([3⊃ 。

ハ ノイ の塔 の問題 は 上 記 の物 語 の 中 に あ る よ うに ,1)一 回に 一 枚ず つ,2) 小 さい 円盤 は大 きな 円盤 の上 にだ け置 け,3)3本 の針 の どれ で も補 助 に使 え

る とい う規 則 の下 で 円盤 を あ る針 か ら別 の針 に移 しか え るに は ど うい う手 順 を 踏 む か とい うこ とで あ る(図1)。

図1.ハ ノ イ の 塔

翻

^、

この 問 題 は 円 盤 の 枚 数 が 少 な け れ ば 試 行 錯 誤 的 に(trialanderror,rule

ofthumb,seat‑of‑pantsmethod)容 易 に 解 け る。N枚 の と き の 一 般 的 な 解 法 は プ ロ グ ラ ミソ グの分 野 で 再 帰 法(recursion)と 呼 ば れ る解 法 で あ る。 しか

し,再 帰 に よ らな い 反 復 法 もあ り,多 数 の 解 法 が あ る。

ま ず,再 帰 に よ る解 法 か ら説 明 す る。 針 をS(source),A(auxiliary),

D(destination)と 名 付 け,Sの 針 にn枚 の 円 盤 が 小 さ い 円 盤 は 大 き な 円 盤 の 上 に 置 か れ 小 さ い 方 か ら順 に1,2,…,nと 番 号 が 付 け られ て い る とす る。

p番 目の 円 盤 がDに うま く行 け た とす る(こ の うま くで き た と考 え る の が 再 帰, の要 点 で あ る)。 そ の と きは,Dの 上 に は 円 盤 は 一 つ もな い 状 態 で あ るは ず で あ る。 また,n番 目 の 円 盤 の 上 に も円 盤 が な い は ず で あ る。 従 っ て,Sの 上 の 1か らn‑1ま で のn‑1枚 の 円盤 がAに 移 され て い てn番 目の 円 盤 をSか ら Dに 移 し,そ してAのn‑‑1枚 を 今 度 はSを 補 助 にDに 移 せ ば この 仕 事 は 完 了 す る。n‑1枚 の 円盤 をAか らSを 経 由 してDに 移 しか え るの はnか らn‑1

〆

/

商 学 討 究 第29巻 第4号81 に 減 っ た だ け で 前 と 同様 な 再 帰 的 な 過 程 を 踏 む こ とに な る。

い ま,記 号S→Dに よ っ て 針Sか ら針Dに 移 しか え る こ とを 表 わ し,HANOI (N,S→D)は 上 のN枚 を ブ ロ ッ ク単 位 に 移 しか え る こ とを 表 わ す とす る。 そ の

と き,N=i,2,3の 場 合,HANOI(N,S→D)はAを 補 助 に 次 の操 作 を も た らすQ

N=1の と き,HANOI(1,S→D)=S→D

N=2の と き,HANOI(2,S→D)=1)S→A=HANOI(1,S→A) 2}S→D

3)A→D=HANOI(1,A→D) N=3の と き,HANOI(3,S→D)=

ii竪}一一 際::::認 、 監

4)S→D

劇 脚 一 蹴 ∴∵

以上を図式化す ると次図の よ うな連続的変化① ②③が得 られ る。

1

N‑1く

㌧

枚 め

『 MOVE(N‑1,

①

S→A)爪

' ' ^、_、

、 ③

、

' '

ノMOVE(N

‑1 ,A→D),' /一 「"

ノ

!

チ2/

A

、

、

、

＼

、

、

＼

＼

＼

、 〉/

/

/ ノ

/

＼

㍉＼

、

、

、

、

S .LA②S→DD

N枚 の 円 盤 を 移 動 さ ぜ る 手 間 くaN、 を 計 算 す る と,aN・aN.、+1+aN‑1,ai=1

の 差 分 方 程 式 よ りaN=2N‑1を 得 る 。N=3の と き 確 か にa3=2L1=7(回 、 で あ っ た 。物 語 に 出 て く るN=64枚 で は,264‑1・=18,446,744,073,709,551,615

くカ

≒18×1018で あ る。 一一枚 の 円 盤 を 移 動 させ る ゐ に0.1秒 の 速 さ で で き る 名 僧 侶 で も1年 は 約32×106秒 で あ る か ら5億 世 紀 以 上 か か る こ とに な る。

N=4枚 の 円 盤 に つ い て の 再 帰 的 プ ロ グ ラ ム は 次 節 で 各 種 の 言 語 に よ りプ ロ グ ラ ミ ソ グ され る 。 次 節 で わ か る よ うに,針 を 英 字S,A,Dで な く1,2,3 とす れ ば,(1,2,3)の 置 換 の 性 質S+A+D=6を 用 い て 引 数 を1つ 減 らす こ とが で き る。 次 に 再 帰 を 用 い な い 解 法 に つ い て 説 明 し よ う。 そ れ は 少 な くと も 三 種 類 の 方 法 が あ る 。

第 一 の 解 法 は 再 帰 プ ロ グ ラ ムを パ ラ メ ー タを ス タ ッ ク に 保 存 させ る こ と に よ っ て 非 再 帰 の プ ロ グ ラ ム に 変 換 す る もの で あ る。 再 帰 を 許 さ な い ア セ ソ ブ ラ (MD【),BASICで 使 わ れ て い る 。

第 二 の 解 法 は 整 数 論 の応 用 に よ る 直 接 法 で あ る。 既 に 回 数 が わ か っ て い る こ とが 前 提 で あ る が,1か ら2"‑1ま で の 数 字 を 基 数3で 表 現 で き る 性 質 を 用 い る。 移 動 対 象 の 円 盤 は1か ら2"‑1を2で わ った 余 りに 関 係 す る。FORTRAN

とSAMOSプ ロ グ ラ ムで 用 い られ て い る が,iは 円 盤jが 既 に 済 ませ た 移 動 回 数 を 表 わ し て い る。

第 三 の 解 法 は 第 二 の 方 法 と類 似 して い る が グ ラ フ理 論 に 依 拠 して い る 。 そ れ は ハ ミル トソ線 を 求 め る こ とに 帰 着 す る 。 次 数2nの ハ ミル トソ グ ラ フは 平 面 上 のn次 立 方 体 をn組 の 頂 点 と 辺 に よ っ て 表 わ した グ ラ フで あ る。n次 立 方 体 の2つ の 頂 点 が 互 い に 隣 接 し て い る必 要 か つ 十 分 条 件 は 対応 す るn組 が 一 '項 だ け 異 な

っ て い る と き で あ る。 例 と して,n=3(3枚 の 円 盤)の ハ ミル ト ソ グ ラ フは23=・8個 の 頂 点 を も ち,各 頂 点 は み つ 組(ai,b,,Ci)に 対 応 して い る 。 こ こ で,ai,b,,Ciは 円 盤 を 小 さ い 方 か らa,b,cと 名 付 け,各 項 は0ま た は1を と る,そ の と き,ハ ミル トソ線 は(0,0,0)→(1,0,0)→(1,1,0)

→(0,1,0)→(O,1,1)→(1,1,1)→(1,0,1)→(0,0,1)と な り,一 回 の (2)2ab(aは1か ら9,bは0か ら9の 値)の 簡便 な十 進概 算値 を求 め るには,最 初

のaが1000単 位(,000)が 下 にa個 あ って,次 の2bで 最 初 の1000進 の数値 とすれば よい。 例 えば,215は,000が1個 あ り,先 頭 に25=32が くるか ら約32,000(実 際 は 32,768)と な り,231は,000が3個 あ り先頭 が2で あ るか ら約2,000,000,000(実 際 は2,147,483,648)で あ る。

商 学 討 究 第29巻 第4号 83 移 しか え で 次 の 状 態 に 進 む 様 子 を 表 わ して い る(図2)Qこ の 方 法 の プ ロ グ ラ'

く コ

ムは次 節 に現 わ れ て い ないo

図2.ハ ミ ル ト ン 線(n=3)

(o,1,1) (1,1,1)

(O,O,1) (1,0,1)

3.,各 種 の プ ロ グ ラ ム 言 語 と プ ロ グ ラ ム

前 節 で 「ハ ノイの塔 の問題 」 の説 明 とそ の解 法 に つ い て述 べ た。 そ れ は2n (非 多項 式)の オ ー ダの計 算 の手 間 を要 す るので 大 きな計 算機 の使 用 に よって 解 き うる。

本 節 は,わ れわ れ の計 算機(112K語)上 に あ る実 用 的 な各種 の プnグ ラ ム言

ゆ

語 を 概 説 し(ア ル フ ァ ベ ッ ト順),上 記 の 問 題 をN=4枚 に 対 し,そ れ ぞ れ の

言 語 で コ ー デ ィ ソ グ し 結 果 を 得 た も の を 掲 げ る 。 出 力 結 果 は 例 え ば,APLプ

ロ グ ラ ム の 実 行 結 果(84ペ ー ジ)に み ら れ る 。

(3)ハ ノ イ の 塔 問 題 の 最 初 の プ ロ グ ラ ム はIPL‑Vで 書 か れ た 。A.'M.Hormann,

"P

rogramsforMachineLearning.Partll,"1カformationandControl.Vol.7,‑

No.1(March,1964)参 照 。 又,Peck[8コ 参 照 。

(4)プ ロ グ ラ ム 言 語 の 歴 史 に つ い て 最 も 権 威 の あ る 文 献 は[1]で あ ろ う。ALGOL60, APL,APT,BASIC,COBOL,FORTRAN,GPSS,JOSS,JOVIAL,LISP,PL/1,

SIMULA,SNOBOLの1'3種 類 に つ い て 各 開 発 者 が 詳 細 に 記 録 し て い る 。

、

〔1〕ALGOL60(ALGOlgorithmicLangnage60)

ALGOL60は 米 国 と ヨ ー一ロ ッパ で 共 同 で 開 発 され た 言 語 で 数 値 計 算 や 論 理 計 算 を 解 くの に 適 して い る 。ALGOL60はS.Rosenが 言 うよ うに([9]),

「多 分 す べ て の プ ロ グ ラ ム言 語 の な か で も っ と も広 く議 論 され,も っ と も注 意 深 く研 究 され て き た 。Algo1の 完 全 か つ 詳 細 な 知 識 な しに は,だ れ も プ ロ グ ラ

ム言 語 の 分 野 で 専 門 家 で あ る と主 張 す る こ とは で き な い 。 い ま のAlgo160が よ りよ い,よ り強 力 な 言 語 で 置 きか え られ て も一 結 局 は お きか え られ るべ き で あ るが この こ とは 今 後 当 分 の 間,変 わ らな い で あ ろ う」 。

ALGOL60は1962年4月,IFIP62(ロ ー マ)で 完 全 な 定 義 を 与 え たRevised Reportに 基 礎 づ け られ て い る。 しか し,経 済 学 的,社 会 学 的,生 態 学 的 投 資

の不 足 の た め に 流 行 しな くな っ た 。'

わ れ わ れ のALGOL60は 拡 張ALGOL60と 称 せ られ,1972年3月,

G.Hayman,G.Hansen,お よ びR.Cookに よ っ てXDS計 算 機 用 に 作 製 さ れ た も の で あ る[6]。ALGOL60の 拡 張 と し て,大 き な 複 雑 な プ ロ グ ラ ムの 処 理 を 容 易 に し,弾 力 的 な 入 出 力,倍 精 度 演 算,ス ト リソ グ処 理,デ バ ッ グ機 能,ビ ッ ト操 作 等 を 可 能 に した 。 た だ し,入 出 力 がFORTRANの 書 式 仕 様 を 採 用 して い る こ と,オ ー パ レイ構 造 の コ ソパ イ ラで あ る こ とに 不 満 が 残 る。 ハ ノイ の 塔 のALGOL60の プ ロ グ ラ ムは 次 の よ うに な る。 特 に 出 力 部 分 に 注 意 され た い 。 実 行 時 間 は 後 に 一 括 した 。

**M‑700EXTENDEDALGOL‑60*t

1.

2.

3.

4.・

5.

6. 、 7.

8.

9.

10.

11.

BEGIN

FORMATF(X,'MOVEPIECE',15,'FROM',A1,'Tσ',A1,'.');

PROCEDUREHANOI(N,A,B,C);VALUEN;

INTEGERN;STRINGA,B,C;

IFN>OTHEN

BEGINHANOI(N‑1,A,C,B); .

WRITE(F,N,A,C);

HANor(N‑1,B,A,C) ENDHANOI;

HANOI(4,'A','B',℃') END

ALGOL60の プ ロ グ ラ ム

㌧

商 学 討 究 第29巻 第4号 ⁸⁵

〔2ゴAPL(AProrgammingLanguage)

APLは1956年 頃,K.E.Iversonに よ り考 え られ た プ ロ グ ラ ム言 語 で,極' め て 簡 単 な 構 文 を もち な が ら強 力 な 言 語 で,数 学 の 問 題 解 決 に 適 して い る。

APLの 特 徴 と して 次 の 点 が あ げ られ る 。 ・

1.構 文 が 極 め て 簡 単 で,電 卓 の よ うな 使 用 も高 水 準 プ ロ グ ラ ム言 語 の よ う な 使 い 方 もで き る(再 帰 プ ロ グ ラ ム も コル ー チ ソ も可 能)。

2.・ 意 味 的 規 則 が 少 な い 。 演 算 の 右 優 先 規 則 も慣 れ れ ば 便 利 で あ る。

3.言 語 の プ リ ミテ ィ ブ な 対 象 は 配 列(リ ス ト,テ 「 ブル,テ ーtブル の リス ト等)で あ る。 た と え ば,A+Bは 任 意 の 配 列AとBに 対 して 有 効 で あ る。 ベ ク トル,行 列,テ ー ブル 演 算 が 能 率 的 に 書 け る。

4.修 飾 演 算 子 を 用 い た 原 関 数 は 系 統 的,能 率 的 に 所 望 の 結 果 を もた らす 。 四 則 演 算 か ら整 列,書 式 制 御 ま で 多 様 な操 作 を 含 む 。

5.会 話 的 に 行 わ れ,編 集 機 能 もあ る。

わ れ わ れ のAPLは,こ れ らの特 徴 を もつ 反 面,APL端 末 が な い の で 殆 ん'

s

オi卜{臼{'{1=ll ,[

il・i'ii:=i

:Xl:i:̲き ….i季:縄 縫

[;E::3、 ・ 、:ミ::・H‑1:笠 三:ll:;ii≡=i

鷺=i…1::=:!1・ 星i:…1慧=il・ 一:::・

弱 葺:li…:一 ・・一::ゴ:1;!=},

茗葦

・詳}遷1:塾i[:::i工 響5iii;

..‑v"一 一":i、 三・ll:;一 一}il:litt

:[:i工!就:まi、1=1・ 一 一}

羅iき 謹il・・一 瀞

:P工E・;1:f"y:i::1‑一:::・!ii::=

縦:1しlli:達::肛 雲Oiiとy:1:1‑‑1::・1:::iu

言・書〔1りlii:1・1::1王1き ζ:,1.yl三;一 一:::・1=:it:' :躍1ヨ 礁 ・=凄tlt:[':一 …}:￡;,, .

f"ylで1‑:::一:il㍉

・:;iiごll}::it・ 一一h.N:1:‑f:::;窪

211:i=i‑・ 一}liiil#・

1:i1!三1=::ヨ 鮮i=ト …::ド:ii、t 縦1り ε1:Ilf:;1=:烹 ・i…1;一 一:::・1=≧鎚' 撞 コL肥P路c;il:タ:1‑1;… 一 〉 二ii駆

纈=1いEPI3〔:1ジ 臼 一 … 二:・ 鯛 、

どす べ て 代 替 文 字 を 用 い 入 力 しな け れ ば な らな い 難 点 を もつ 。APLの 「単 一 の 読 み や す く書 き易 い 新 しい 記 号 の 導 入 」 が 逆 に 作 用 して い る。 また,多 量 の 入 出 力 が 不 可 能 な 欠 点 もあ る。 ハ ノ イ の 塔 の プ ロ グ ラ ム は 前 頁 の よ うで,見 に

くい が 簡 潔 で あ る。 演 算 時 間 は 極 め て 速 い 。

〔3〕BASIC(Beginner'sAll‑purposeSymbolicInstructionCode)

BASICは1963‑1964年 ダ ー トマ ス大 学 のT.EKurtzとJ.G.Kemeny

に よ っ て 開 発 さ れ た 。 は じめ は14個 の 文 しか な か っ た が 現 在 は 大 型 機 か らマ イ ク ロ コ ソ ピ ュ ー タ ま で か な り強 力 な 機 能 を 備 え,時 分 割 的 に 使 用(編 集,実 行) す る こ とが で き る。

単 純 な 言 語 で 覚 え や す く 実 行 も 速 い の で,初 等 的 な 数 値 計 算 や 文 字 処 理 に 適 し て い る 。 反 面,制 御 文 の 不 足 か ら 構 造 的 な プ ロ グ ラ ム が 書 き に く い こ と が 致 命 的 で,エ ラ ー 発 見 に 手 間 ど る 。 サ ブ ル ー チ ソ の パ ラ メ ー タ が な い こ と,行 番 号 の 整 頓,変 数 が 同 一 の 有 効 範 囲(ス コ ー プ)に あ る こ と な ど も 欠 陥 で あ る 。 わ れ わ れ のBASIC(TimeShare社 の も の に 近 い)で プ ロ グ ラ ム し た も の は 次 の 通 り で あ る 。

LIST

1000DIMF(25),T(25),1(25),R(25) 1010LETN=4

1020LETN=N十1 1030LETF(N)=1 1040LETI(N)=2 1050LETT(N)=3 1060GOSUB3010 1070STOP

3000REMARK:GO,…SUBROUTINETOPERFORMIT.

3010LETN=N‑1 30201FN〈=OTHEN3510 3030LETR(N)=2 3040LETF(N)==F(N十1) 3050LETT(N)=1(N十1) 3060LETI(N)=・T(N十1) 3070GOTO3010

3080REMARK:GOUPTHESTACK 3510LETN=・N十1

35201FR(N)==2THEN3700

'

!

商 学 討 究 第29巻 第4号 ⁸⁷

35231FR(N)=3THEN3510 3526GOTO3900 3700LETD3=N

3710PRINT"MOVEPIECE";D3;"FROM";F(N十1);"TO";T(N十1) 3720LETR(N)=3

3730REMARKMOVEPIECEAROUND 3740LETF(N)・=1(N十1) 3750LETT(N)=T(N十1) 3760LETI(N)=F(N十1) 3770GOTO3010 3900RETURN/*TOCALLER

BASICの プ ロ グ ラ ム

〔4〕BCPL(BasicCombinedProgrammingI」anguage)

1968年 頃,英 国 ケ ソ ブ リ ッ ジ 大 学 のM.RichardsがStracheyら のCPL

を基 礎的 に 設 計 し直 した もの で シ ス テ ム プ ロ グラ ムの 記 述 を 目 的 とす る。

BCPLの 特 徴 は 既 に 述 べ た 〔11コの で,早 速,わ れ わ れ のBCPLで 書 い た プ ロ グ ラ ム とINTCODEを 提 示 す る。

(BCPL)

12345678

GLOBAL¥(START:1;PRINT:65;NEWLINE:63¥) LETHANOI(N,S,b)BE

¥(IFN〈=ORETURN HANOI(N‑1,S,6‑(S十D))

PRINT('MOVEDISC:N,:N‑一 〉:N*C',N,S,D) HANOI(N‑1,6‑(S十D))

¥)

ANDSTART()BE¥(HANOI(4,1,3)¥) (INTCODE)

JL4¥HANOIlLIP2LOXFMLsX4LIP2L1≦X9SP7LIP3SP8L6SP9 LIP4PIP3SPALIP9LIPAXgSP9×18HL2H5LLIF3SP7LIP2SP8LIP3 SP9LIP4SPAXH81H5LIP2LIX9SP7L6SP8LIP4PIP3SPgLIP8

LIP9×9SP8×18HL2H5×4 ヒ へ

¥START3L4SP4LISP5L3SP6×18HL2H2×44

2HLIIF311BI2012014DI4FI5614512014414915314312013AI4E I2CI2013AI4EI2012DI2DI2DI3EI2013AI4EIDG41L3Z

上 の プPグ ラ ムか らわ か る よ うにBCPLは ル ー チ ソ と関 数 が 基 本 単 位 で そ れ らをGLOBAL数 で制御 す る。PRINT文 が他 の 言語 には 見 られ ない構 文 を

プ 、

もつ 。 す なわ ち,PRINT(FORMAT,出 力 変 数 の リス ト)の 構 文 を も ち,

FORMAT中 の:Nは 数 値 と して 印 刷 し,*Cは 改 行 を 行 う。

BCPLは ソ ー ス プ ロ グ ラ ムをAE木 に変 換 しそ れ をOCODEに,続 い て INTCODEに 変 換 しイ ソ タ プ リー タ(Pascal版 とFortran版 が あ る)で INTCODEを 実 行 す る の で,処 理 系 作 成 の 容 易 さ の 反 面,実 行 時 間 が か か る。

〔5〕COBOL(CommonBusinessOrientedLanguage)

COBOLは1959年5月Pentagonで のCODASYL運 営 委 員 会 に 始 ま り, も と も と事 務 ・デ ー タ処 理 を 指 向 した 高 水 準 言 語 で あ る。 そ れ は 単 に 簿 記 的 な 仕 事 に と ど ま らず,初 期 の 頃 か ら,機 械 翻 訳 や 文 献 検 索 の仕 事 に 適 用 さ れ て き

た の で,'・ ノ イ の 塔 をCOBOLで 書 くこ と も不 可 能 で は な い(下 図)。 一 目 瞭 然 に外 側 の皮 ば か り厚 い感 じがす るの は 否 め ない。

灘㎜灘朧㎜㎜㎜ 01234567890121111111111222㎜㎝㎜㎝㎝㎜㎝㎜㎝㎝㎜㎜㎝

00023 00024 00025 00026

COBOLLS,GO

IDENTIFICATIONDIVISION.

PROGRAM‑ID.TOWER‑OF‑HANOI.

AUTHOR.NOBUOWAKABAYASHI.

DATE‑WRITTEN.300CT1978,

DATE‑COMPILED.NOVO2ゴ1978. 、 ＼

SECURITY.BLANKET.

,ENVIONMENTDIVISION.

CONFIGURATIONSECTION.

SOURCE‑COMPUTER.MELCOM.

OBJECT‑COMPUTER.COSM(}

DATADIVISION..

WORKING‑STORAGESECTION.

77DISK‑NOUSAGEDISPLAYPICZZZ9.

'77FROM ‑PEGUSAGEDISPLAYPICA .

77TO‑PEGUSAGEDISPLAYPICA.

77NUSAGEビCOMPUTATIONALPICS9999.

77MUSAGECOMPUTATIONALPICS9999.

01STACKS.=

02FROM‑SOCCURS25TIMESUSAGEDISPLAYPICA.

02TO‑SOCCURS25TIMESUSAGEDISPLAYPICA.

021NT‑SOCCURS25TIMESUSAGEDISPLAYPICA.

02RETURN‑SOCCURS25TIMESUSAGECOMPUTATIONAL PICS9999.

PROCEDUREDIVISION.

SET‑UPSECTION.

HANOI‑BEGINNING.

MOVE4TON.

、

'

＼

商 学 討 究 第29巻 第4号 ⁸⁹

00027 00028 00029 00030 00031 00032、

00033 00034 00035 00036 00037 00038.

OQO39 00040 00041

00042 00043 00044 00045 00046 0∞47 00048 00049 00050 00051 00052

00053 00054 00055 00056 00057 00058 00059 00060

,

ADDlTON.

MOVE'A'TOFROM‑S(N).

MOVE'B'TOINT‑S(N).

MOVE'C'TOTO‑S(N).

PERFORMHANOI.

STOPRUN.

HANOISECTION.

COMPUTE‑FIRST.SUBTRACTlFROMN.

IF翼NNOT>OGOTOC15.

MOVE2TORETURN‑S(N).

ADD1,NGIVINGM.

MovEFRoM‑s(M)ToFRdM‑s(N).

MOVETO‑S(M)TOINT‑S(N).

MOVEINT‑S(M)TOTO‑S(N).

NOTEWEHAVEJUSTAeCOMPLISHEDSOMEDISK MOVING.

GOTOCOMPUTE‑FIRST.

C15.ADDlTON.NOTEWEAREGOINGUPTHESTACK.

IFRETURN‑S(N)=2GOTOC12.

IFRFTURN‑S(N)=3GOTOC15, GOTOCOMPUTE‑LAST.

C12.「

MOVENTODISK‑NO.MOVENTOM.

ADDlTOM.

MOVEFROM‑S(M)TOFROM‑PEG.

MOVETO‑S(M)TOTO‑PEG.

DISPLAY'MOVEDISK'DISK‑NO'FROM'FROM‑PEG' TO'TO‑PEG.、.

MOVE3TORETURN‑S(N).

NOTETHATWENOWDOSOMEMOREDISKMOVING.

MOVEINT‑S(M)TOFROM‑S(N).

MOVETO‑S(M)TOTO‑S(N).

MOVEFROM‑S(M)TOINT‑S(N).

GOTOCOMPUTE‑FIRST.

COMPUTE‑LAST.

EXIT.

[6]FORTRANIV(FORmula、TRANslator),FLAG(FORTRAN

LoadAndGo)

FORTRANは 周 知 の よ うに広 く科 学 技術計 算を 意 図 した言語 で,1954年,

IBM704に 対 し,JohnBackusがH.Herrick,R.A.Nelson,工Zillerと 共

、

̀

1

に 独 立 に 開 発 した 初 め て の コ ン パ イ ラ 言語 で あ る。FORTRANIVはIBM

の 成 長 と と もに 科 学 技 術 計 算 や 教 育 の 場 で70%以 上 の 使 用 者 が い る とい わ れ る 程 浸 透 して い るが,近 年,や や 支 持 率 が 低 下 して い る。FORTRANIVの も つ 種 々 の欠 陥(RATFORの よ うな構 文 を 豊 富 に させ た プ リプ ロセ ッサ も開 発 さ れ て い るが)と,他 言 語 の 拾 頭(例 えばPascal,PL/1)に よ る。

FLAGはFORTRANIVの1パ ス型 くloadandgo、 で,処 理(翻 訳 ・実 行)時 間 が 速 く学 生 演 習 に 適 して い る。

FORTRANは 再 帰・を 許 さ な い の で,・ ・ノイ の 塔 は 前 記 の 方 法(2)か サ ブ ルr チ ソ 展 開 に よ る。

3

5

091

CALLHANOI(4) STOP END

SUBROUTINEHANOI(N) DIMENSIONID(3) DATAID/,A,,'B∵Cソ IF(N.LE.0)RETURN M=2窯 家N‑1 DO9K=1,M

KK=K J=1

1F(MOD(KK,2).NE.0)GOTO5 KK=KK/2

J=J+1、

GOTO3 1=KK/2

1NCJ=2‑MOD(N十J,2) JOLD=MOD(1零INCJ,3) JNEW=MODてJOLD十INCJ,3)

WRITE(6,10)J,ID(JOLD十1),ID(JNEW十1) FORMAT('MOVEPIECE',13,'FROM',A1,'TO',A1)

CONTINUE RETURN

END,

,︑

商 学 討 究 第29巻 第4号 91

FORTRAN

GCCG㎜器麗㎜㎜朧㎜㎜㎜㎜㎜朧藩㎜㎜㎜麗朧躍㎜器㎜騰

CALLMρVE4(1HA,1HB,1HC) STOP

END

SUBROUTINEMOVE4(X,Y,Z) MOVE4FROMXTOY.

CALLMOVE3(X,Z,Y) WRITE(6,6)X,Y

6FORMAT(1H,12HMOVE4FROM,A1,4HTO,A1) CALLMOVE3(Z,Y,X)'

RETURN END

SUBROUTINEMOVE3(X,Y,Z) MOVE3FROMXTOY.

CALLMdVE2(x,z,Y) WRITE(6,6)X,Y

6FORMAT(1H,12HMOVE3FROM,A1,4HTO,A1) CALLMOVE2(Z,Y,X)

RETURN END

SUBROUTINEMOVE2(X,Y,Z) MOVE2FROMXTOY

CALLMOVE1(文,Z,Y)

6FORMAT(1H,12HMOVE2FROM,A1,4HTO,A1) WRITE(6,6)X,Y

CALLMOVE1(Z,Y,X) RETURN

END

SUBROUTINEMOVE1(X,Y,Z) MOVElFROMXTOY

WRITE(6,6)X,Y

6FORMAT(1H象12HMOVElFROM,A1,4HTO,A1) RETURN

END

/ '

〔7〕GPM(GeneralPurposeMacro‑generator)'

GPMは1965年C・Stracheyに よ り発 表 さ れ た マ ク ロ ジ ェネ レー タ で 入 力 も出 力 も記 号 列 の 形 を と る記 号 列 プ ロ セ ッサ で あ る。GPMの 実 現 は[10コ で CPLで 粛 述 して い るの でBCPLの 動 く所 で は 容 易 に 移 植 す る こ とが で き る。

GPMは プnグ ラ ム の見 ば え は よ くな い が 再 帰 関 数 や 条 件 式 の よ うな 機 能 を

92問 題 解 決 と プ ロ グ ラ ム 言 語

もつ の で,マ ク ロ プ ロ セ ッサ の 教 育 日的 に は 有 効 で あ る。

$DEF,一,($DEC,$BAR,一,$BIN,.1;,$BIN,.2;;;);

$DEF,EQ,($.1,$DEF,.1,.4;$DEF,.2,.3;;);

$DEF,HANOI,($EQ,.1,0,,($HANOIs$一).1(,1:,).2(,).4(,).3(

MOVEDISC).1(FROM).2(TO).4(

$]E[ANOI,$一,).1(,1;,).3(,).2(,).4(;););

$HANOI,4,S,A,D;>

GPMに よ る プ ロ グ ラ ム

〔8〕LISP1.5(HStProcessor、,LISPI(イ ン タ プ リ ー タ)

LISPは1958年 秋,MITの 助 教 授 に な っ た ば か り のJohnMcCarthyに

よ っ てIBM704計 算 機 に 対 しAdviceTakerと 呼 ば れ る シ ス テ ム の 実 験 を 容

易 に す る た め に 開 発 さ れ た い わ ゆ る 記 号 処 理 プ ロ グ ラ ミ ソ グ シ ス テ ム で あ る 。

LISPIはPascal(約550行)で 書 か れ たLISP1.5の イ ン ,タ プ リ ー タ で あ り

そ の 利 用 目 的 はTinyLISPの 演 習 を 含 む 実 験 的 な 言 語 処 理 系 の 作 成 で あ る 。

LISPはLk)tsofIrritatingandStupidParenthesesProcessorと かLots

ofInsipidStupidParenthesesの 略 で あ る と 悪 く い わ れ る よ う に か っ こ の 対

応 に 悩 ま さ れ,適 切 な デ バ ッ グ 機 能 や プ リ テ ィ プ リ ン タ が 整 備 さ れ な い 限 り, 問 題 解 決 の 永 続 的 な 使 用 は 困 難 で あ ろ う 。

わ れ わ れ のUSP1.5がEVQ‑LISPで あ る の に 対 し,LISPIイ ソ タ プ リ ー タ 、

「

はEV‑LISPで あ り,LISP1.5の プ ロ グ ラ ム の み 以 下 に 示 す 。

DEFINE((

(HANOI

(LAMBDA(NABC) (COND((ZEROPN)NIL) ((QUOTET)(APPEND

(HANOI(SUBIN)ACB), (CONS

(PRINT(LIST(QUOTEMOVE)N(QUOTEFROM)A(QUOTETO)C)) (HANOI(SUBIN)BAC)

) )))) )))

HANOI(4123)

LISP1.5に よ る プ ロ グ ラ ム

阜

・商 学 討 究 第29巻 第4号93

〔9〕MIX/700(MIXは10009の ロ ー マ 字 化)、h

MIXはDE.Knuth[7]の1.3.1節 で 記 述 さ れ て い る 仮 想 のMIX計 算 機 ・ に 対 す る ア セ ソ ブ ラ と シ ミ ュ レ ー タ で あ る 。MIX/700はPascal700(約 千 行) で 実 現 さ れ た1パ ス の ア セ ソ ブ ラ で あ る 。 す な わ ち,MIXAL言 語 で 書 い た ソ t・一一・ス プ ロ グ ラ ム を 受 け 入 れ ,仮 想 の 機 械 語 に 変 換 し,そ れ をPascalで 解 釈 実 行 し て い る 。MD(ALプ ロ グ ラ ム を 終 了 さ せ るENDヵ 一 ド の あ と に 制 御 カ ー ドを 置 く こ と に よ り 目 的 プ ロ グ ラ ム を 出 力 し た り,シ ミ ュ レ ー タ を 呼 ん で 実 行 し た り,ポ ス トモ ー テ ム ダ ソ プ を 出 力 す る こ と が で き る 。

MIX/700とMIXの 相 違 点 は 次 の 通 り で あ る 。

1.現 在,機 番16(M:SDと 機 番18(M:LO)だ け が シ ミ ュ レ ー トさ れ て い る 。

2.浮 動 小 数 点 演 算 は シ ミ ュ レ ー ト さ れ て い な い 。

3.文 字 コ ー ドはCDC順 序 に 従 い,一(ア ソ ダ ラ イ ソ),"(ダ ブ ル ク ォ ー ト)

%(パ ー セ ソ ト),&(ア ソ パ サ ソ ド),#(ハ ッ シ ュ マ ー ク),?(疑 問 符),

!(雨 だ れ)も 許 す 。'

4.二 項 演 算 は+,一,*,/だ け が 許 さ れ//と:は 組 込 ま れ て い な い 。 5.ア セ ソ ブ リ は は じ め3000に セ ッ トさ れ た ロ ケ ー一・・一シ ョ ソ*で 表 わ さ れ た 値 を

ダ

利 用 す る。*の 値 は0と3999(最 大 番 地)の 間 を と る。

次 に ハ ノイ の塔 のMIXプ ロ グ ラ ムを 示 す 。

1'*TdwEROFHANoI

2LP

・3DATA 4STACK 5HANOI 6 7 8 9 10 11 12

/ EQU18LINEPRINTER EQU5

EQU100 STJSTACK十4,6 STrSTACK,6 ST2STACK十1,6 ST3STACK十2,61 ST4、STACK十3,6 1NC65

J4ZWAKABA LD2STACK‑3,6

t

,

噸

94 問 題 解 決 と プ ロ グ ラ ム 言 語

13 14 15 16 17 18 19 20 21 22・

23 24 25 26 27WAKABA 28 29 30 31 32 33 34 35

36START 37 38 39 40 41 42 43 44 45 46」

47PRINT、

48 49DISC

50 51FROM 52 53TO 54

跳襲㎜㎝謡罵㎜㎜㎜m㎜羅血羅

STACK‑4,6 1 HANOI

27 DISC(2:2) 27 FROM TO PRINT(LP) TO TO FROM

l HANOI

10 STACK,6 STA(K十1,6 STACK十2,6

STA .CK十3,6 5

STACK十4,6(1:2) 象十1(1:2)

*

ENTIDATA INC127 ST125(1:2) ENTIl ENT22 ENT33 ENT4DATA ENT65 JMPHANOI HLT ALFMOVE ALFDISC ALF ALFFROM

ALF ALFTO ALF ENDSTART

MIXプ ロ グ ラ ム

'

L

、

̀

商 ・学 討 究 第29巻 第4号 ⁹⁵

〔10〕Pascal(数 学 者Pascalに 由 来,Pascal700),Pascal‑S

Pascalの 概 説 は[11コ で 行 な っ た の で こ こ で はPascal‑Sを 中 心 に 述 べ る 。 Pascal‑Sの 一SはSubsetofの 意 で,N,Wirthが1976年 に,Pascalの よ り 教 育 目 的 な 部 分 集 合 を 設 計 し 配 布 し た も の で あ り,わ れ わ れ はPascal700で

移 植 し た 。

Pasca1が そ の 全 容 を20数 ペ ー ジ で 述 べ る こ と が で き た に せ よ,Pascalの 機 能 と 応 用 範 囲 は 彪 大 で あ る た め 全 部 を 短 期 間 で マ ス タ ー す る こ と は 不 可 能 で あ る 。Pascal‑Sは こ の 観 点 か ら 通 常 の プ ロ グ ラ ミ ソ グ コ ー ス の 内 容 を カ バ ー で き る 必 要 限 度 の も の を 含 ま せ,さ ら にPaSCalら し い 部 分 を 残 し た も め で あ る 。 例 え ば,デ ー タ 型 はinteger,rea1,Boolean,charが あ り,ス カ ラ ■・・一・型 や 部 分 範 囲 型 は な い 。 デ ー タ 構 造 はarrayとrecordの2種 類 だ け で,file型 や 動 的 な レ コ ー ド型(pointer型)は 除 か れ た 。

くうセ

Pascal‑Sの 動 き 出 し た 当 初 はPascal700が 端 末 装 置 上 で 実 行 で き な か っ た の で 利 用 価 値 が 大 き か っ た 。 ま た,エ デ ィ タ,フ ォ ー マ ッ タ,グ ラ フ 出 力,プ

リ テ ィ プ リ ソ タ 等 の ソ フ ト ウ ェ ア ツ ー ル を 一 括 し た ソ フ ト ウ ェ ア 環 境 の 整 備 に 有 用 で あ るQI

Pasca1も 他 の 主 要 言 語 の よ う に プ ロ グ ラ ム 言 語 規 格 委 員 会(ANSのX3J6)

が 発 足 し て い る の で 小 ず れ,標 準 規 格 が 作 ら れ る だ ろ う 。Pascalの 最 新 情 報 に

つ い て はPascalNeWS誌 が 有 用 で あ る 。 ・ ノ

次 にPascalプ ロ グ ラ ム を 再 帰 型 と 非 再 帰 型 の2種 類 示 す 。

(5)Pascal700.は ・ミッ チ 処 理 で しか 利 用 で き な か っ た が 現 在 は 端 末 装 置(CRT,遠 隔 タ イ プ ラ イ タ,回 線 利 用 に よ る タイ プ ラ イ タ 等)か ら実 行 す る こ とが で き る 。 ジ ョ ブ 制 御 の 構 成 は 次 の 通 りで あ る。

(コ ソ パ イ ル)!P700.ソ ー ス フ ァ イ ル 名ONま た はOVER ノ

オ ブ ジ ェ ク トフ ァ イ ル 名 垣Lh璽LI (リ ン ク)!LYNXオ ブ ジ ェ ク トフ ァ イ ル 名ONま た はOVER

ロ ー ドモ ジ ュ ー ル 名;PASCLIBl巫1

(実 行) ̲1ロ ー ドモ ジ ュ ー ル 名.デ ー タ フ ァ イ ル 名1亘1

な お,デ ー タ フ ァ イ ル はinputか ら 読 む デ ー タ が 入 っ た フ ァ イ ル で あ る か ら,も しデ ー タ が な い 場 合,逗1を2回 押 下 す る 。

(再 帰 プ ロ グ ラ ム)

電

1PROGRAMBARMAH(OUTPUT);

2PROCEDUREHANOI(N,S,】[M.INTEGER);

3'BEGINIFN>OTHEN

4BEGINHANOI'(N‑1,S,6‑(S十D));

5WRITELN('MOVEDISCt,N:2,S:2,L‑〉',D:2);

6tHANOI(N‑1;6‑(S十D),D)

7END 8END;

9BEGINHANOI(4,1,3)END.

(非 再 帰 プ ロ グ ラ ム) 1PROGRAMTOWEROFHANOI(OUTPUT);

2CONSTN=10;

3TYPETASK昌RECORDDISC:工NTEGER;

4SOURCE,DEST:1..3END;

5VARJOB=TASK;

6PROCEDUREHANOI(HJOB:TASK);

7VARSTACK=ARRAY(.α;N.)OFTASK;

8PILE:TASK;P:INTEGER;

9BEGINPILE:=HJOB;P:=0;

10.WHILE(PILE.DISC<>0)OR(P>0)DO llBEGINWHILEPILE.DISC〈>ODO

12、BEGINSTA(K(.P.):=PILE;P:・=P十1;

13WITHPILEDO

14BEGINDISC:=DISC‑1;DEST:=6‑SOURCE‑DESTEND 15END;

16P:=P‑1;PILE:=STACK(.P.);置 17WITHPILEDO

18BEG工N

19WRITELN('MOVEDISC',DISC:2∴',SOURCE:2,L>',DEST:2);

20DISC:=DISC‑1;SOURCE:=6‑SOURCE‑DEST 21ENDENDENDr,

22BEGIN(象MAIN零) 23WITHJOBDO

24BEGINDISC:=4;SOUR(E:=1;DEST:=・3END;

25HANOI(JOB)

26END. 〉

Pasca1プ ロ グ ラ ム 。

〔11〕PL/1(ProgrammingLanguageone)

PL/1は 次 の2段 階 で 開 発 さ れ た 。 第 一 段 階 は,1963年10月,SHARE(ユ

商 学 討 究 第29巻 第4号 ⁹⁷ 一一一一・ザ 団 体)とIBM(プ ロジ ェ ク トリー ダ はG .Radin)の 連 合 委 員 会 で,NPL (NewProgrammingLanguage)の 仕 様 が 作 られ た こ と,第 二 段 階 はIBM

自身 がNPLの や や 不 完 全 な 仕 様 を 精 緻 化 す る こ とに よっ て 開 発 した こ と で あ る。

PL/1の 特 徴 は,周 知 の よ うに 二 つ の要 因 に よ り強 く影 響 さ れ た 。 一 つ は, 事 務 計 算,科 学 技 術 計 算,実 時 間,シ ス テ ム プ ロ グ ラ ム記 述 等 の 要 求 を み た す

こ と,第 二 に,従 来 のFORTRAN,COBOL,ALGOLの 特 徴 を 備 え て い る こ と で あ る。 そ の 結 果,か な り大 きな 能 力 を もっ た 言 語 が 出 来 上 が っ た が,プ ロ グ ラ マ に とっ て は そ れ だ け 複 雑 さを 管 理 しな け れ ば な らな くな っ た 。 教 育 目的 に は,PL/C(数 値 計 算 用),XPL(シ ス テ ム プ ロ グ ラ ム用)・の よ うな 派 生 言 語 を 使 用 す る の が 妥 当 で あ ろ う。

PL/1で 書 い た ハ ノ イ の 塔 問 題 の プ ロ グ ラ ム は 次 の よう で あ る。

¶⊥9︼34轟一bρ07唇9∩V11

1⊥‑■

H:PROCOPTIONS(MAIN);

HANOI=PROC(N,A,B,C)RECURSIVE;

DCLNFIXEDDECIMAL(3),(A,B,C)CHAR(1);

IFN>OTHENDO;

CALLHANOI(N‑1,A,C,B);

PUTFILE(SYSPRINT)EDIT('MOVEPIECE',N,'FROM', A,'TO',C,'.')(COL(1),A,F(3),5A);

CALLHANOI(N‑1,B,A,C);END;

END;

CALLHANOI(4,'A','B','C');

END;

PL/1プ ロ グ ラ ム

〔12〕SAMOS

セ イ モ ス

SAMOSはMD(よ りもは るか に 小 規 模 の 仮 想 の 計 算 機 の ア セ ソ ブ ラ(機 械 語)で あ り,1969年,A.1.Forsytheeta1[4コ 用 に 作 られ た 。

SAMOSはFORTRAN,Pascal等 で 書 か れ た い くつ か の シ ミ ュ レ ー タが 実 在 して い る の で機 械 語 に よ る プ ロ グ ラ ミ ソ グ の 実 習 を 行 な う こ と が で き る。 し か し現 在 の 計 算 機 とは 程 遠 い 機 能 しか な い の で 小 さな プ ロ グ ラ ム演 習 に と どめ

φ

るべ きで あ る 。わ れ わ れ の 問 題 に 対 す る プ ロ グ ラ ムを トリ ビア ル で あ るが 記 す 。

NO

1234567891011121314151617181920212223以2526勿%29.3031323334353637銘3940414243

.

ADDRESS

1234567891011121314151617181920212223242526幻28四30313233343536訂383940414243

＼

SAMOS‑℃ODE

LDA,,102 STO,,200 LDA,,102 STO,,300 LDA,,200 STO,・,210 DIV,,103 STO,,220 MPY,,103 SUB,,210 BMI,,18 LDA,,300 ADD,,102 STO,,300 LDA,,220 STO,,210 BRU,,7 LDA,,100 ADD,,300 STO,,310 DIV,,103 MPY,,103 SUB,,310 ADD,,103 STO,,500 MPY,,220 STO,,510 DIV,,104 MPY,,104 STO,,520 LDA,,510 SUB,,520 STO,,530.

ADD,,102 STO,,600 LDA,,530 ADD,,500 STO;,540 DIV,,104 MPY,,104 STO,,550 LDA,,540 SUB,,550

COMMENT K==1

J=1 KK=K

J1=KK/2

IF(MOD(KK,2).EQ.0)GOTO18 J=J+1

KK・=KK/2

NJ=N+J

INCJ=2‑MOD(N十J,2)

(INCJ)

JOLD=MOD((KK/2)零 】〔NCJ,3)

JJ=JOLD十1

JNEW=MOD(JOLD十INCJ,3)十1

m4445464748弱5051525354茄565758掬6061

ADDRESS 44 45 46 47 48 49 50 51 52 53 54 55 100 101 102 103 104

商 学 討 究 第29巻 第4号 SAMOS‑CODE

ADD,,102 STO,,610 WWD,,300 WWD,,600 WWD,,610 WWD,, LDA, ADD, STO, SUB, BMI, HLT, 十 十 十 十 十

#END

,200 ,102 ,200

,101 ,3

,

4 16

1 2 3

COMMENT

DWLEONTJJτ﹂

K=K十1

IF(K.LT.16)GOTO3

〔13〕SNOBOL4(StriNgOrientedsymBOIicI、anguage)

99

SNOBOLは 文 字 通 り,文 字 列 の 操 作 に 重 点 を お い た 言 語 で あ り,RE.Gris‑

woldが1962年 頃Bell電 話 研 究 所 でPolonskyら と設 計 ・作 製 した こ とに 始 ま

る 。SNOBOL4は 文 字 ・ス ト リ ソ グ演 算,再 帰 関 数,テ ー ブル 構 造,ユ ーザ 定 義 デ ー タタイ プ,再 定 義 可 能 演 算 が あ る の で,コ ンパイ ラ作 成,記 号処 理,テ キス ト作 成, 自 然 言 語 翻 訳,言 語 学,音 楽 分 析 の よ うな 分 野 に 有 用 な ツ ール と な っ て きた[5コ 。

わ れ わ れ のSNOBOL4はCalvinBarker(テ キ サ ス大 学 ア ー リ ソ トソ校 機 械 工 学 科 教 授)がXDS用 にMetasymbolで 作 製 した も の で あ る。LOAD

関 数 以 外 はSNOBOL4の フル セ ッ トを 実 現 して い る の で 方 言 の 違 い が な く安 心 して使 え る。 た だ し,速₉ 度 が 若 干 遅 い こ と,:(、,:F(),:S()F()に

代 表 され る行 き先欄 か ら起 こ る制御 の流 れ が混 乱 しやす い こ と,ブ ロ ッ ク構 造

く コ

が な い こ と な ど は,広 範 に 使 用 さ れ な い 理 由 で あ ろ う。

(6)彼 の テ キ サ ス 大 学 で もGriswoldの ア リ,ゾナ 大 学 で もSNOBOL4は 隠 退 し,高 速SNOBOL(SPITBOL)が 稼 動 して い る 。 ま た,ア リ ゾ ナ 大 学 で は 筆 者 の 訪 問 し た1978年10月,ポ ス トSNOBOLと し てICONが 盛 ん に 宣 伝 さ れ 教 育 用 に 使 用 さ れ て い た 。ICONはCに ス ト リ ソ グ 機 能 を 付 加 し,実 行 時 の 記 憶 管 理 を 強 め た 言 語

で 興 味 が あ る の で,わ れ わ れ も移 植 の 作 業 を 試 み て い る 。

/

SNOBOL4で 書 い た プ ロ グ ラ ム を 示 す 。

DEFINE('HANOI(N,A,B,C)'):(MAIN) HANOILT(N,1):S(RETURN)

HANOI(N‑1,A,C,B)

0がTPUT='MOVEDISC'N"A‑一 一'〉'C'.'

HANOI(N‑1,C,A,B):(RETURN) MAINHANOI(4,'A','B',℃')

END

SNOBOL4の プ ロ グ ラ ム

1234昂b67

4.評 価 と 展 望

前 節 で は 各 種 の プ ロ グ ラ ム言 語 の概 説 とそ れ らの ハ ノ イ の 塔 の 問 題 の プ ロ グ ラ ムを 提 示 した 。 表1に,各 種 の プ ロ グ ラ ム言 語 の パ ー フ ォ マ ソス の 比 較(行 数 と総CPU時 間)を 示 した 。 こ の表 は 厳 格 に 解 釈 さ るべ きで は な く一 応 の 目

安 を 与 え て い る こ とに 注 意 す べ き で あ る。 な ぜ な らハ ノ イ の 塔 の 問 題 は 特 殊 な 例 題 に 過 ぎ な い し,解 法 も さ ま ざ ま あ る。 プ ロ グ ラ ム の 行 数 は さ らに減 少 し う

る こ と,CPU時 間 もマ ル チ プ ロ グ ラ ミ ソ グ シ ス テ ム で 走 っ て い る の で 空 い た 時 間 と混 雑 した 時 間 で は 差 異 が で る。 ま た,オ ブ ジ ェ ク トコ ー ドの 長 さや コ ー デ ィ ソ グ時 間 な ど も表 に 盛 る べ きで あ ろ う。

に もか か わ らず,表1か ら次 の よ うな 暫 定 的 な 結 論 を ひ き出 す こ とが で き る 同 じ問 題 に 直 面 しな が ら プ ロ グ ラ ム行 数 が10行 以 内 で 済 む もの は プ ロ グ ラ ム が 書 き易 く,ま た 読 み や す く プ ロ グ ラ ム の検 証 が 容 易 で あ る。 特 に,最 小 行 数 で 達 成 で き るAPLは 問 題 解 決 ま た は 算 法 の教 育 とい う 目的 に 適 して い る。

実 行 速 度 も速 く,バ ッチ もTSS処 理 も可 能 とい う長 所 が 加 わ っ て い る。GPM は プ ロ グ ラ ムが 短 か く書 け,マ ク ロ プ ロセ ッサ の 醍 醐 味 が 味 え る点 で 興 味 深 い が,考 え に くい とかCPU時 間 が か か る難 点 の 方 が 大 き い 。SNOBOL4,BCPL,

Pascal,ALGOL60,PL/1は プ ロ グ ラ ム 行 数 か ら殆 ん ど 同一 で あ り,構 文 も似 て い る。PascalはALGOL60,BCPL,PL/1の 思 想 を 吸収 ・超 越 して い る の で 問 題 解 決 に は 最 も適 して い る。 何 よ りも トッ プ ダ ウ ソ(下 向 き)に プ ロ グ ラ ムで き る の が よい 。 わ れ わ れ のPasca1やALGOLの コ ソバ ィ ラは オ ー バ レ