関数型プログラミング言語における遅延評価機構

成 瞑 大 学 理 工 学 研 究 報 告 J.Fac.Sci.Tech.,SeikeiUniv. Vol.53No.2(2016)pp.21-24

関 数 型 プ ログ ラ ミン グ言 語 に お け る遅 延 評 価 機 構

高 野 保 真*1

LazyEvaluationofFunctionalProgrammingLanguages

YasunaoTAKANO*1

ABSTRACT:Lazyevaluationisanevaluationstrategyinprogramminglanguages.Lazyevaluationdelays

theevaluationofanexpressionuntilitsvalueisneeded.Withlazyevaluation,therearesomeadvantages.

Oneoftheadvantagesenablestoavoidunnecessaryevaluations.Anotheradvantageenablestohelp

programmerswriteclearprograms.Incaseoflinkedlist,programmerscandividefUnctionsintotwokinds,

generationoflistandconsumeoflist.Inthispaper,weintroduceanoverviewoflazyevaluationandour

continuousresearchforlazyfUnctionalprogramminglanguages.

KeywordsProgramminglanguages,Functionalprogramming,Lazyevaluation

(ReceivedOctober21,2016)

1.は じ め に

複 雑 な ソフ トウェ ア を 開 発 す るた め に,プ

ロ グ ラ ミン

グ 言 語 が 提 供 す る抽 象 化機 構 は,ま す ま す 重 要 にな っ て

き て い る.そ の 点 に 注 目 して,プ

ロ グ ラム の モ ジ ュー ル

化 や 記 述性 を 重 視 した 関 数 型 プ ロ グ ラ ミン グ言 語 の 研 究

が進 み,関 数 型 プ ロ グ ラ ミン グ言 語 を用 い て プ ロ グ ラ ミ

ン グ を 記 述 す る 関 数 プ ロ グ ラ ミン グ が盛 ん に な っ て い

る.

関数 プ ログ ラ ミ ン グで は,処 理 を関 数 とい う単 位 に分

け て 定 義 し,関 数 を 組 み 合 わ せ る こ とで,よ

り高 い 抽 象

度 で プ ログ ラム を 記 述 す る。 以 下 に,関 数 プ ロ グ ラ ミン

グ の 主 な 特 徴 を 挙 げ る.

●

宣 言 的 な 記 述

数 式 の よ うに,関 数 を 宣 言 的 に 記 述 す る.つ ま り,

計 算機 が 何 を す るか とい う手 続 き を記 述 す るの で は

な く,プ ログ ラム で解 く問題 の性 質 を 記 述 す る.

●

副 作 用 の な い 関 数

変数 へ の 代 入 の よ うな 副 作 用 が な く,関 数 は 参 照 透

明(referenciallytransparent)で あ る.

●

抽 象 デ ー タ 型 に よ る処 理

処 理 の 対 象 を 抽 象 デ ー タ型 と して,計 算 機 上 で の 実

*1:理 工 学 部 情 報 科 学 科 助 教(yasunao _-takano@st .seikei.acjp)

際 の表 現 を 隠蔽 して扱 う.

この よ うな特 徴 か ら,関 数 プ ログ ラ ミ ング は,遅 延 評 価

(lazyevaluation)と 相 性 が よ い.

遅 延 評 価 とは,値 が 実 際 に 必 要 に な るま で 計 算 を遅 ら

せ る評 価 戦 略 で あ る.必 要 に な った 値 か ら計 算 す る た め,

最 終 結 果 を求 め るた め に は 不 要 な 計 算 を 除 去 す る こ とが

で き る.ど の値 が必 要 とな るか とい う判 断 を処 理 系 に任

せ る こ とが で き るた め,プ

ロ グ ラマ が 計 算 の 順 序 に 頼 っ

た プ ログ ラ ム を記 述 す る必 要 が な くな る とい う利 点 が あ

る.

本 報 告 で は,関 数 型 プ ロ グ ラ ミ ン グ言 語 お け る遅延 評

価 に つ い て紹 介 す る と と もに,我 々 が これ ま で行 っ て き

た研 究 に つ い て概 要 を述 べ る.筆 者 の これ ま で の仕 事 を

総 括 す る論 文 で あ る性 質 上,自 分 の 論 文 を多 く引 用 して

い る 点 は ご容 赦 い た だ き た い.ま た,そ れ ぞ れ の研 究 の

詳 細 につ い て は,参 考文 献 を参 照 され た い.

2.遅

延 評 価

2.1遅

延評 価 とは

遅 延 評 価 は,式 の評 価 を そ の値 が 必 要 に な るま で 遅 ら

せ る プ ログ ラ ミ ング言 語 の評 価 戦 略 で あ る.基 本 的 な 遅

延 の対 象 は,関 数 や デ ー タ構 成 子 の 引数 で あ り,遅 延 を

表 す 構 文 を導 入 す る場 合 もあ る.た と えば,引 数 が 遅延

一21一

成 践 大 学 理 工 学 研 究 報 告

Vol.52No.2(2015.12)

の 対 象 で あ る と き,あ る 関 数 適 用 の 引 数 に 与 え ら れ る 式 の 計 算 は 遅 延 さ れ,遅 延 さ れ た 計 算 は,そ の 値 が 実 際 に 必 要 に な っ た と き に 初 め て 処 理 さ れ る. プ ロ グ ラ ム の 実 行 を 要 求 駆 動 的 に 進 め る こ と が で き る た め,主 に 以 下 の よ うな 利 点 が あ る. ● 無 駄 な 計 算 を 除 去 す る こ と に よ る 実 行 効 率 の 向 上 ● 宣 言 的 な 記 述 を 用 い る こ と に よ る 記 述 性 の 向 上 ま ず,一 つ 目 の 項 目 に 関 し て,最 終 結 果 に 寄 与 しな い 無 駄 な 計 算 を 省 く こ と が で き れ ば,Cな ど の 手 続 き 型 言 語 に 代 表 さ れ る 先 行 評 価 の 言 語 に 比 べ て,潜 在 的 に は 実 行 効 率 が 良 い.た と え ば,以 下 の よ うに 定 義 さ れ る 単 純 な 関 数firstを 考 え る. first::Int->Int→Int firstab=a こ の 関 数 はaとbと い う2つ のInt型 の 引 数 を 受 け と り,第 一 引 数 を 返 す.つ ま り,第 二 引 数 は 結 果 に 関 係 な い.遅 延 評 価 に 基 づ く 言 語 で は,関 数 の 実 引 数 は 遅 延 の 対 象 で あ る の で,firstO(heavyl)と い う呼 び 出 しが あ っ た と き に は,実 引 数 の0とheavylは す ぐ に は 計 算 さ れ な い.こ こ で,heavy1の 計 算 が 非 常 に 時 間 の か か る と き に は,計 算 せ ず に 済 ま せ る こ と が で き,遅 延 評 価 を 採 用 し た こ と に よ る 効 果 が 大 き く な る. 次 に,二 つ 目 の 項 目 に 関 して,プ ロ グ ラ ム の 実 行 順 序 を 処 理 系 に 任 せ る こ と が で き る こ と に よ り,プ ロ グ ラ ム に は 処 理 の 手 順 を 記 述 す る の で は な く,そ の プ ロ グ ラ ム の 性 質 を 記 述 す る こ と が 可 能 と な る.そ の た め,プ ロ グ ラ ム は 宣 言 的 に な り,モ ジ ュ ー ル 化 を 促 進 す る こ と が で き る[1].特 に,こ の 特 徴 は 抽 象 デ ー タ 構 造 を 扱 う際 に 有 効 で あ る.つ ま り,あ る デ ー タ 構 造 に 対 して,そ の デ ー タ を 生 成 す る プ ロ グ ラ ム 記 述 と,そ の デ ー タ を 読 み 進 め る プ ロ グ ラ ム 記 述 を 分 離 で き,プ ロ グ ラ ム の 見 通 しが よ く な る. 遅 延 評 価 に は 多 く の 利 点 が あ る 一 方 で,以 下 の よ うな 欠 点 も 挙 げ ら れ る. ● ● ●

処 理 を 手続 き 的 に 追 うこ とは難 しい

代 入 な どの 副 作 用 の あ るプ ロ グ ラ ミン グ言 語 と相 性

が 悪 い

プ ロ グ ラ ミ ン グ言 語 処 理 系 を実 現 す る際 に効 率 の よ

い 実 装 が難 しい

2.2遅 延 評 価 に 基 づ く 関 数 型 プ ロ グ ラ ミ ン グ 言 語 遅 延 評 価 に 基 づ く 関 数 型 プ ロ グ ラ ミ ン グ 言 語 の 歴 史 は 古 く,70年 代 後 半 か ら80年 代 に か け て 研 究 が 始 ま っ た [2].1985年 に,ResearchSoftware社 の プ ロ グ ラ ミ ン グ 言 語Miranda◎[3]が 現 在 の 関 数 プ ロ グ ラ ミ ン グ の 基 礎 と な る 特 徴 を 持 っ た 言 語 で あ っ た.Mirandaの 文 法 は, 等 式 に よ る 関 数 の 定 義,パ タ ー ン マ ッ チ ン グ,リ ス ト内 包 表 記(listcomprehensions)な ど の 要 素 に よ り,記 述 の 簡 潔 さ を 考 え た も の で あ っ た. そ のMirandaの 流 れ を 受 け たHaskell[4]と い う言 語 が 現 在 最 も広 く利 用 され て い る 遅 延 評 価 に 基 づ く 関 数 型 プ ロ グ ラ ミ ン グ 言 語 で あ る.Haskellの プ ロ グ ラ ミ ン グ 言 語 と し て の 特 徴 は,遅 延 評 価 に 加 え て,代 数 的 デ ー タ 構 造 を 用 い た 高 い 記 述 性,静 的 型 付 け と型 推 論 に よ る 高 い 信 頼 性 な ど,多 く の 理 論 的 背 景 を 持 っ た 機 能 を積 極 的 に 採 用 し て い る こ と で あ る 。 当 初 は 研 究 的 側 面 が 強 い 言 語 で あ っ た が,最 近 で は, 実 用 的 な 場 面 で もHaskellが 用 い ら れ る よ う に な っ て き た.た と え ば,金 融 取 引 にHaskellを 用 い た 例[5]や シ ス テ ム の 管 理 にHaskellを 用 い た 例[6]な ど が あ り, 幅 広 い 分 野 に 渡 っ てHaskellが 使 わ れ は じ め て い る 。

3.ImprovingSequence

前 節 で 述 べ た 遅 延 評 価 の 記 述 性 に お け る利 点 を 生 か す 研 究 と し て,我 々 はImprovingSequence(IS)[7]と 呼 ば れ る デ ー タ 構 造 を 利 用 し,探 索 問 題 を 記 述 す る研 究 を 行 っ て き た. ISと は,あ る 順 序 関 係 の 意 味 に お い て 単 調 で,徐 々 に 真 の 値 に 近 づ い て い く近 似 値 の 列 を 表 現 す る デ ー タ構 造 で あ る.IS上 の 近 似 値 が 全 順 序 関 係 の 意 味 に お い て 単 調 で あ る こ と に よ り,真 の 値 に よ る結 果 と 同 じ 結 果 を あ る 時 点 で の 近 似 値 で 求 め る こ と が で き,そ の 場 合 に は,そ の 時 点 以 降 の 真 の 値 へ と 至 る 計 算 を 枝 刈 りす る こ と が で き る. た と え ば,文 字 列"seikeiuniversity"の 長 さ を1文 字 ず つ 順 に 前 か ら数 え る場 合 を 考 え る 。 こ の と き,ま ず`s' と い う文 字 を 数 え た と き に は,こ の 文 字 列 は 少 な く と も 1の 長 さ が あ る と分 か る た め,1を 全 体 の 長 さ の 近 似 値 と考 え る こ と が で き る 。そ の た めISは1と い う近 似 値 と残 り の 文 字 列"eikeiuniversity"を 組 と す る デ ー タ構 造 と な る.そ のISに 続 け て 次 の`e'を 読 め ば 少 な く と も 2の 長 さ が あ る と分 か り 近 似 値 は 実 際 の 長 さ に 近 づ く. つ ま り,近 似 値 で あ る 部 分 的 な 長 さ は く の 関 係 の も と で 単 調 に 増 加 す る.こ の 性 質 を 利 用 す れ ば,も し 上 の 文 字 列 が5よ り 大 き い か 知 り た い と き に は"seikei"と い う と こ ろ ま で 文 字 の 長 さ を 数 え れ ば,少 な く と も6文 字 あ り,そ こ か ら 単 調 に 増 え て い く だ け で あ る た め,残 り の 文 字 列 の 長 さ を 数 え る 必 要 が な い.つ ま り,す べ て の 文 字 列 を 数 え ず に 計 算 を 枝 刈 り し て 結 果 を 求 め る こ と が 一22一

成 践 大 学 理 工 学 研 究 報 告

Vol.52No.2(2015.12)

で き るの で あ る.

以 上 の 文 字 列 の 長 さを 比 較 す る例 は,最

も単 純 な 例 で

あ るが,同 様 の 考 え方 でISを

用 い る こ とで,巡 回 セ ー

ル ス マ ン問題 や 編集 距 離 や8パ

ズル を解 くプ ログ ラ ム,

探 索 木 を 用 い た オ セ ロの プ ロ グ ラム な どが 簡 潔 に記 述 す

る こ とが で き る.

ISに 関す る研 究 の 中 で も筆 者 は,ISを

効 率 よ く処 理

で き る プ ロ グ ラ ミ ン グ言 語 処 理 系 の設 計 と実 装[8]を

中 心 に研 究 して き た.論 文[8]に

お い て は,プ ロ グ ラム

の コ ンパ イ ル 時 にISの

単 調 性 を解 析 した うえ で,コ ー

ド生 成 を す るプ ロ グ ラ ミ ン グ言 語 処 理 系 を設 計 し実 装 し

た.こ の研 究 で 得 られ た 着 想 が,次 節 で 述 べ る遅 延 デ ー

タ構 造 の 遅延 に 必 要 な メ モ リ割 当量 の 削 減 が 可 能 で あ る

とい うア イ デ ア の き っ か け とな っ た.

4.遅

延 評 価 に基 づ く関 数 型 プ ロ グ ラ ミ ン グ 言 語

に お け る メモ リ割 当量 の 削 減

遅 延 評 価 に お い て は,計 算 の 遅 延 に 必 要 と な る オ ブ ジ ェ ク ト(遅 延 オ ブ ジ ェ ク ト,以 下 サ ン ク と 呼 ぶ)を 処 理 系 内 に 生 成 す る.式 を 評 価 す る 代 わ りに サ ン ク を 割 り 当 て る が,こ の こ と は 時 間 的 ・空 間 的 に コ ス トが か か る 操 作 で あ る.た と え 遅 延 評 価 に よ り結 果 に 寄 与 しな い 計 算 を 除 去 で き る と し て も,プ ロ グ ラ ム の 実 行 時 の オ ー バ ヘ ッ ドが 大 き く な っ て し ま う と い う問 題 点 が あ る.そ の た め,効 率 的 に 遅 延 評 価 を 行 う言 語 処 理 系 に お い て は,サ ン ク の 生 成 を 抑 制 す る た め に,様 々 な 静 的 解 析 手 法 が 開 発 さ れ て き た. 我 々 は サ ン ク の 削 減 を 目 指 し た 一 手 法 と して,リ ス ト の よ うに 線 形 に 定 義 さ れ る 再 帰 的 デ ー タ 構 造 に 注 目 し, 既 存 の サ ン ク を 再 利 用 し て サ ン ク の 生 成 を 抑 え る 手 法 (以 下,ThunkRecyclingと 呼 ぶ)に つ い て 研 究 して き た. ThunkRecyclingの 目的 は,す で に 割 り 当 て ら れ て い る サ ン ク の 内 容 を 破 壊 的 に 更 新 し て 再 利 用 し,新 た な 遅 延 オ ブ ジ ェ ク ト の 生 成 を 抑 え る こ と で あ る.Thunk Recyclingを 用 い れ ば,た と え ば,代 表 的 な 再 帰 的 デ ー タ 構 造 で あ る線 形 リス トで は,後 続 の リス トの 遅 延 に 必 要 と な る サ ン ク を 再 利 用 す る こ と が で き る. ま た,ThunkRecyclingは,サ ン ク の 内 容 を 破 壊 的 に 書 き 換 え る こ と に よ り,矛 盾 が 生 じ な い よ う に す る機 構 も 合 わ せ 持 つ.具 体 的 に は,コ ン パ イ ル 時 の 静 的 な プ ロ グ ラ ム 変 換 に よ り,再 利 用 す る サ ン ク へ の 参 照 が 単 一 で あ る よ うに す る. 我 ・々 は,以 下 の よ うなThunkRecyclingに 関 す る 一 連

の研 究 を これ ま で行 っ て き た.

● ● ● ThunkRecyclingを 提 案 し た.[9] ThunkRecyclingの 形 式 的 な 定 義 を 与 え,そ の 正 し さ を 証 明 し た.こ こ で い う 正 し さ と は,Thunk Recyclingを 適 用 し た プ ロ グ ラ ム が,適 用 前 の プ ロ グ ラ ム と 同 じ ふ る ま い を し て 同 じ 結 果 を 導 く こ と を い う.[10] Haskellの 代 表 的 な 処 理 系 で あ るGlasgowHaskell Compiler(GHC)上 にThunkRecyclingを 設 計 し,実 装 し た.[11] ベ ン チ マ ー ク プ ロ グ ラ ム に よ る 実 験 に よ り,再 利 用 の お よ ぼ す 影 響 を 確 認 し た.図1と 図2に 結 果 を 示 す. 伽

響 璽糖欝 欝 轡看

轡 轡 鳳

響篭

繰 資

鵬

[1

川

Il

図1:総 メ モ リ割 当 量

竃

継 ∼

黙欝 驚 響 吾

轡 繁墾驚 篭

糧 轡

ら 篇 図2:実 行 時 間 横 軸 に ベ ン チ マ ー ク 、縦 軸 にThunkRecyclingの 導 入 前 の GHCを100%と した と き の 値 を と っ て い る.総 メ モ リ 割 当 量 を 見 る と 多 く の ベ ン チ マ ー ク で 効 果 が み ら れ,最 も効 果 が あ る も の で は 導 入 前 の 半 分 以 下 の 総 メ モ リ割 当 で 実 行 で き た.一 方,実 行 時 間 の 観 点 か ら 見 る と,適 用 す る プ ロ グ ラ ム を 選 ぶ も の で あ っ た. 6.む す び

本 報 告 で は我 々 が これ ま で行 っ て き た 遅延 評 価 に 基 づ

く関数 型 プ ログ ラ ミ ング言 語 に 関 す る取 り組 み に つ い て

紹 介 した.遅 延 評 価 は潜 在 的 な利 点 が 数 多 くあ る一 方 で,

ま だ課 題 の 多 い技 術 で あ る.そ の た め,今 後 の さ らな る

研 究 に よ り改 善 を 目指 して い くべ き研 究課 題 で あ る.

一23一

成 践 大 学 理 工 学 研 究 報 告

参考文献

[1]J.Hughes.WhyFunctionalProgrammingMatters.The ComputerJoumal,Vbl.32,No.2,pp.98-107,1989. [2]P.Hudak,J.Huges,S.PeytonJones,andP.Wadler.A HistoryofHaskell:BeingLazywithClass.Proc.the3rd ConferenceonHistoryofProgrammingLanguages (HOPL-III),pp.1-55.ACM,2007. [3]D.A.Turner.Miranda:aNon-strictFunctionalLanguage withPolymorphicTypes.Proc.the2ndACMConference onFunctionalProgrammingLanguagesandCom-puter Architecture(FPCA1985),pp.1-16.ACM,1985. [4]S.PeytonJones.Haskell98:Introduction.Joumalof FunctionalProgramming,Vol.13,pp.i-6,2003. [5]S.Frankau,D.Spinellis,N.Nassuphis,andC.Burgard. Commercialuses:Goingfunctionalonexotictrades. JournalofFunctionalProgramming,Vol.19,No.1,pp. 27-45,2009. [6]1.Pop.Experiencereport:Haskellasareagent:resultsand observationsontheuseofHaskellinapythonproject.In Proc.theInternationalConferenceonFunctional Programming,pp.369-374.ACM,2010. [7]H.Iwasaki,T.Morimoto,andYTakano.Pruningwith ImprovingSequencesinLazyFunctionalPrograms. Higher-OrderandSymbolicComputation,Vol.24,No.4, pp.281-309,2011. [8]高 野 保 真,岩 崎 英 哉ImprovingSequenceを 第 一 級 の 対 象 と す るSchemeコ ン パ イ ラ.第8回 プ ロ グ ラ ミ ン グ お よ び プ ロ グ ラ ミ ン グ 言 語 ワ ー ク シ ョ ッ プ, pp.153-162.日 本 ソ フ ト ウ ェ ア 科 学 会,2006. [9]高 野 保 真,岩 崎 英 哉,鵜 川 始 陽.GlasgowHaskell Compilerに お け る 再 帰 的 デ ー タ 構 造 の た め の 遅 延 オ ブ ジ ェ ク ト の 再 利 用.情 報 処 理 学 会 論 文 誌 プ ロ グ ラ ミ ン グ,Vol.5,No.2,pp.67-78,2012. [10]YTakano,H.Iwasaki.ThunkRecyclingfbrLazy FunctionalLanguages:OperationalSemanticsand Correctness.Proc.30thACM/SIGAPPSymposiumon AppliedComputing,pp.2079-2086,Salamanca,Spain. 2015. [11]高 野 保 真,岩 崎 英 哉,佐 藤 重 幸.GlasgowHaskell Compiler上 の 遅 延 オ ブ ジ ェ ク ト の 再 利 用 手 法 の 設 計 と 実 装.コ ン ピ ュ ー タ ソ フ ト ウ ェ ア,Vol.32,No.1, PP.253-287,2015. 一24一

Vol.52No.2(2015.12)