2024-03-28T17:58:44Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000169102020-10-27T05:02:43Z00934:00935:00978:00979
再帰プログラム部分計算のための停止性判定法A Termination Condition for Partial Evaluation of Recursive Programjpn通常論文http://id.nii.ac.jp/1001/00016910/Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=16910&item_no=1&attribute_id=1&file_no=1Copyright (c) 2000 by the Information Processing Society of Japan早稲田大学大学院理工学研究所早稲田大学理工学情報学科早稲田大学理工学情報学科宋立タン二村, 良彦Robert, Glück本稿ではまず,部分計算に関する新しい停止性判定法である再帰条件法を提案する.再帰条件法は,既存の停止性判定法である実引数法と同じく,同相埋め込み(homeomorphic embedding)関係を利用した整列擬順序(well-quasi ordering)に基づく判定法である.実引数法が,実引数の文字列的な順序に関する逆順を調べるのに対して,再帰条件法は,再帰呼出しが起こる場合の条件(再帰条件)に関する指標の文字列的な逆順を調べる.したがって,両者とも,任意の部分計算を必ず止めることのできる停止性判定条件であるが,止まるタイミングは同じとは限らない.どちらが先に止まるかは,実行される部分計算によって異なる.しかし,再帰条件法は意味論的な情報をより多く持つ再帰条件を用いるため,多くの場合に,実引数法よりある意味で都合良く止まることができる.本稿ではこの2つの停止条件の利害得失について詳細に議論する.さらに,本稿では再帰条件法と実引数法の長所を取り入れた混合法を提案する.混合法は,この両者の停止条件をともに満たす場合にのみ停止するので,いかなる場合でも両者よりも早く止まる可能性がない判定法である."In this paper,we present a new termination condition called recursion condition method (RCM) to ensure the termination of specialization.Just like existing termination conditions which we call as actual parameter method or APM,RCM is also a termination condition based on well-quasi ordering using homeomorphic embedding.Compared with using the actual parameters of functions or procedures in APM, the recursion conditions invoking recursive calls are used in RCM. If APM and RCM are used respectively in the specialization of a program, the residual programs may be different for the different termination timing of the two termination conditions.Which termination condition makes specialization terminate earlier or later differs according to source program.However, because RCM uses the recursion conditions containing semantic information of a source program to some extent,it can often produce more efficient residual programs than APM does. Furthermore, we can combine RCM with APM into a new termination condition called combined method or CM.Only if the termination conditions of RCM and APM are satisfied simultaneously,the termination condition of CM is satisfied,so CM will not allow specialization process to terminate earlier than both RCM and APM.AA11464814情報処理学会論文誌プログラミング(PRO)41SIG09(PRO8)37512000-11-151882-78022009-06-30