研究者詳細

教職員基本情報
氏名
Name
横山 哲郎 ( ヨコヤマ テツオ , YOKOYAMA Tetsuo )
所属
Organization
理工学部ソフトウェア工学科
職名
Academic Title
准教授
個人または研究室WebページURL
URL
http://www.tetsuo.jp
専攻分野
Area of specialization

コンピュータサイエンス(計算機科学)

学会活動
Academic societies

日本ソフトウェア科学会 会員 2003.9–現在に至る
ACM 会員 2008.10–現在に至る
情報処理学会 プログラミング研究会(IPSJ SIGPRO) 運営委員 2009.4–2013.3
情報処理学会会員 2011.4–現在に至る
情報処理学会 組込みシステム研究会(IPSJ SIGEMB) 運営委員 2011.4–2015.3
情報処理学会 ESSロボットチャレンジ2011 運営委員長
情報処理学会 ソフトウェア工学研究会(IPSJ SIGSE) 運営委員 2012.4–現在に至る

日本ソフトウェア科学会 プログラミングおよびプログラミング言語ワークショップ(PPL) プログラム委員 第16回, 第17回
情報処理学会 組込みシステムシンポジウム プログラム委員 2011, 2012, 2013, 2014, 2015, 2016
Program Committee Member, ACM SIGPLAN 2008 Workshop on Partial Evaluation and Program Manipulation
Program Committee Member, The Workshop on Reversible Computation 2009, 2010, 2011, 2013, 2014, 2015, 2016
Program Co-chair, The Workshop on Reversible Computation 2012

社会活動
Community services

大学コンソーシアムせと協議会副会長2012.4-2013.3 http://cus.lineup.jp/

著書・学術論文数
No. of books/academic articles
総数 total number (0)
著書数 books (0)
学術論文数 articles (0)

出身学校
学校名
Univ.
卒業年月(日)
Date of Graduation
卒業区分
Graduation
   Classification2
東京大学工学部計数工学科数理情報工学コース 2001年03月  卒業 
詳細表示
出身大学院
大学院名
Grad. School
修了課程
Courses
   Completed
修了年月(日)
Date of Completion
修了区分
Completion
   Classification
東京大学大学院情報理工学系研究科数理情報学専攻終了 博士後期課程  2006年03月  修了 
東京大学大学院理工学系研究科数理情報学専攻 修士課程  2003年03月  修了 
詳細表示
取得学位
     
学位区分
Degree
   Classification
取得学位名
Degree name
学位論文名
Title of Thesis
学位授与機関
Organization
   Conferring the Degree
取得年月(日)
Date of Acquisition
博士 博士(情報理工学)  Deterministic Higher-order Matching for Program Transformation  東京大学大学院情報理工学系研究科数理情報学専攻博士後期課程  2006年03月 
修士 修士(情報理工学)  Functional Meta-programming for Program Calculation  東京大学大学院情報理工学系研究科数理情報学専攻博士前期課程  2003年03月 
学士 工学士  最左最右関係を用いた最長部分列問題の解法の発展とその有効性  東京大学工部計数工学科  2001年03月 
詳細表示
研究経歴
長期研究/短期研究
Long or Short
   Term research
研究課題名
Research Topic
長期研究  プログラミングの方法論 

概要(Abstract) 計算機プログラムおよび計算機アーキテクチャを数理的にとらえて、プログラミングの方法論にあらたな視点を与える。 

詳細表示
著書
年度
Year
著書名
Title of the books
著書形態
Form of Book
NeoCILIUS
   請求番号/資料ID
Request No
出版機関名 Publishing organization,判型 Book Size,頁数 No. of pp.,発行年月(日) Date
2012  Reversible Computation  共編著   
Springer-Verlag  , その他  , X, 241 p.  , 2013/01   

概要(Abstract)  

備考(Remarks) Lecture Notes in Computer Science, Vol.7581 

詳細表示
学術論文
年度
Year
論文題目名
Title of the articles
共著区分
Collaboration
   Classification
NeoCILIUS
   請求番号/資料ID
Request No
掲載誌名 Journal name,出版機関名 Publishing organization,巻/号 Vol./no.,頁数 Page nos.,発行年月(日) Date
2017  可逆プログラムのための償却定数時間かつ定数ゴミ使用量のメモ化  単著   
電子情報通信学会和文論文誌D  , 電子情報通信学会  , 2017/06   

概要(Abstract) メモ化アルゴリズムの可逆版を提案する.本手法により得られるクリーン可逆プログラムは,可逆二進計数器を抽象解釈とする.単射な隣接2項間漸化式で表される任意の数列に対して償却定数時間で定数ゴミ使用量の可逆プログラムを得る方法を示す. 

備考(Remarks)  

2017  ハミルトン曲面流に対応する語の列挙アルゴリズム  共著   
電子情報通信学会和文論文誌D  , 電子情報通信学会  , 2017/06   

概要(Abstract) ハミルトン曲面流に関する極大語の自然な分類が有限個であることを示し,その各分類の下での全ての極大語の列挙アルゴリズムの構成法を明らかにした.また,各分類において極大語の総数を求める方法を形式言語理論を応用して示した.
 

備考(Remarks)  

2017  A Minimalist's Reversible While Language  共著   
IEICE on Information and Systems  , Institute of Electronics, Information and Communication Engineers  , Vol.E100-D/No.5  , 2017/05   

概要(Abstract)  

備考(Remarks)  

2016  A Linear-Time Self-Interpreter of a Reversible Imperative Language  共著   
Computer Software  , Japan Society for Software Science and Technology (JSSST)  , 3  , pp. 108–128   , 2016/08/10   

概要(Abstract) A linear-time reversible self-interpreter in an r-Turing complete reversible imperative language is presented. The proposed imperative language has reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter data structures are dynamically allocated and enable reversible simulation of programs of arbitrary size and space consumption. As self-interpreters are used to show a number of fundamental properties in classic computability and complexity theory, the present study of an efficient reversible self-interpreter is intended as a basis for future work on reversible computability and complexity theory as well as programming language theory for reversible computing. Although the proposed reversible interpreter consumes superlinear space, the restriction of the number of variables in the source language leads to linear-time reversible simulation. 

備考(Remarks) http://doi.org/10.11309/jssst.33.3_108 

2015  Fundamentals of reversible flowchart languages  共著  doi:10.1016/j.tcs.2015.07.046 
Theoretical Computer Science  , Elsevier  , 611  , 87-115  , 2016/01/18   

概要(Abstract) This paper presents the fundamentals of reversible flowcharts. Reversible flowcharts are intended to naturally represent the structure and control flow of reversible (imperative) programming languages in a simple computation model in the same way classical flowcharts do for conventional languages. Although reversible flowcharts are superficially similar to classical flowcharts, there are crucial differences: atomic steps are limited to locally invertible operations, and join points require an explicit orthogonalizing conditional expression.

Despite these constraints, we show that reversible flowcharts are both expressive and robust: reversible flowcharts can simulate irreversible ones by adapting reversibilization techniques to the flowchart model. Thus, reversible flowcharts are r-Turing-complete, meaning that they can compute exactly all injective computable functions. Furthermore, structured reversible flowcharts are as expressive as unstructured ones, as shown by a reversible version of the classic Structured Program Theorem.

We illustrate how reversible flowcharts can be concretized with two example programming languages, complete with syntax and semantics: a low-level unstructured language and a high-level structured language. We introduce concrete tools such as program inverters and translators for both languages, which follow the structure suggested by the flowchart model. To further illustrate the different concepts and tools brought together in this paper, we present two major worked examples: a reversible permutation-to-code algorithm attributed to Dijkstra, and a simulation scheme for reversible Turing machines. By exhibiting a wide range of uses, we hope that the proposed reversible flowcharts can serve as a springboard for further theoretical research in reversible computing. 

備考(Remarks) http://dx.doi.org/10.1016/j.tcs.2015.07.046 

2015  Programming Techniques for Reversible Comparison Sorts  共著  10.1007/978-3-319-26529-2_22 
Lecture Notes in Computer Science  , Springer-Verlag  , 9458  , pp. 407-426  , 2015/12/09   

概要(Abstract) A common approach to reversible programming is to reversibly simulate an irreversible program with the desired functionality, which in general puts additional pressure on the computational resources (time, space.) If the same running time is required, ensuring a minimal space overhead is a significant programming challenge.

We introduce criteria for the optimality of reversible simulation: A reversible simulation is faithful if it incurs no asymptotic time overhead and bounds the space overhead (the garbage) by some function g(n), and hygienic if g is (asymptotically) optimal for faithful simulation.

We demonstrate the programming techniques used to develop faithful and hygienic reversible simulations of several well-known comparison sorts, e.g. insertion sort and quicksort, using representations of permutations in both the output and intermediate additional space required. 

備考(Remarks) https://doi.org/10.1007/978-3-319-26529-2_22 

2014  Designing Garbage-Free Reversible Implementations of the Integer Cosine Transform  共著   
ACM Journal on Emerging Technologies in Computing Systems  , 11  , pp. 1-15  , 2014/11   

概要(Abstract) Discrete linear transformations are important tools in information processing. Many such transforms are injective and therefore prime candidates for a physically reversible implementation into hardware. We present here reversible integer cosine transformations on n input integers. The resulting reversible circuit is able to perform both the forward transform and the inverse transform. The detailed structure of such a reversible design strongly depends on the odd prime factors of the determinant of the transform: whether those are of the form 2k ± 1 or of the form 2k ± 2l ± 1 or neither of these forms. 

備考(Remarks)  

2014  可逆プログラミング言語の引数渡し機構の拡張  共著   
情報処理学会論文誌:プログラミング  , 情報処理学会  , 7  , 21-36  , 2014/08   

概要(Abstract) 本稿では,可逆プログラミング言語Janusの引数渡し機構を拡張して,その拡張言語が可逆であることを示す.参照渡しのモデル化には,同一の参照を持つかもしれない複数の変数名が同じ記憶場所を指せるメモリモデルが必要である.これは既存のJanusで用いられていた状態モデルでは直接には扱うことができない.この問題を解決するために,我々は,環境・記憶域モデルを導入して意味論を改良した.この結果,プロシージャの実引数には,局所変数や局所配列変数だけでなく大域変数や添字付き配列変数の参照,および同一の参照を持つ複数の構文対象も渡せるようになった.拡張言語が可逆であることの保証には,環境と記憶域の更新が可逆であることの保証が必要である.これらの更新は,制限された可逆操作のみ用いて実現されることで,可逆であることが保証される.我々は,拡張言語がほかにも既存のJanusの良い性質を保っていることを示す.すなわち,任意の文やプロシージャ呼び出しの逆実行ができること,および任意の文に対して逆文が存在してそれを求めるプログラム逆変換器が構成できることを示す.さらに,我々は,プログラミング言語を可逆にするために課されていた代入の構文上の制限を緩和する.このことが原因で起こる記憶域の不正な更新は,大域のプログラム解析をしなくても,効率的に検知することができる. 

備考(Remarks)  

2012  Minimizing Garbage Size by Generating Reversible Simulations  共著   
Reversibility, cellular automata, and unconventional computation. Proceedings.  , IEEE Computer Society  , 379–387  , 2012/12/05   

概要(Abstract) Reversible simulations can realize any irreversible computation on any r-Turing complete reversible computation model at the expense of additional garbage output. The problem of minimizing the garbage size is an important issue in reversible simulations. We discuss the notion of the minimal garbage size of reversible simulations. Then, we propose a three-stage reversible simulation for minimizing garbage size, the first stage generates specialized irreversible programs, the second translates them into reversible simulations, and the third performs reversible simulation using the generated reversible programs. Two case studies on sorting algorithms suggest that the proposed method generates solutions with minimal garbage size. 

備考(Remarks) http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6424599&isnumber=6424528 

2011  Optimizing Input-Erasing Clean Reversible Simulation for Injective Functions  共著   
Multiple-Valued Logic and Soft Computing  , Old City Publishing  , Vol.18/no.1  , 5–24  , 2012/01   

概要(Abstract) Bennett showed that a clean reversible simulation of injective programs is possible without returning the input of a program as additional output. His method involves two computation and two uncomputation phases. This paper proposes an optimization of Bennett’s simulation that requires only half of the computation and uncomputation steps for a class of injective programs. A practical consequence is that the reversible simulation runs twice as fast as Bennett’s simulation. The proposed method is demonstrated by developing lossless encoders and decoders for run-length encoding and range coding. The range-coding program is further optimized by conserving the model over the text-generation phase. This paper may thus provide a new view on developing efficient reversible simulations for a certain class of injective functions. 

備考(Remarks) http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-18-number-1-2012/mvlsc-18-1-p-5-24/ 

詳細表示
その他研究業績
年度
Year
題名等
Titles
カテゴリ
Category
細目
Authorship
掲載雑誌名等 Publishing Magazine,発行所 Publisher,巻/号 Vol./no.,頁数 Page nos.,発行年月(日) Date
2015  プログラミング言語 R-WHILE の処理系およびオンラインインターフェース  ソフトウェア  単著 
2015   

概要(Abstract)  

備考(Remarks) 以下のページでオンラインインタプリタとソースコードを公開している。
http://tetsuo.jp/rwhile-playground/
https://github.com/tetsuo-jp/rwhile-C-ocaml 

2015  プログラミング言語 JANUS のオンラインインターフェースと整列プログラム  ソフトウェア  共著 
2015   

概要(Abstract)  

備考(Remarks) http://tetsuo.jp/janus-playground/ 

2011  エンドユーザがプログラム可能な Wiki エンジン  学会発表  単著 
情報処理学会研究報告  , 一般社団法人情報処理学会  , 2011-5-(3)  , 6 p.  , 2012/03/15   

概要(Abstract) Wiki は,誰でも自由にウェブブラウザ上でウェブサイトを書き換えることができる手軽さから広く活用 されてきている.Wiki 文書は,HTTP サーバ上では Wiki 記法で記述されており,ウェブブラウザなどか らの要求があるとハイパーテキストに変換されて,エンドユーザから閲覧される.さらに,エンドユーザ は閲覧時にフォームなどから Wiki 記法で Wiki 文書を自由に編集することができる.しかし,Wiki エン ジンが稼働するサーバ上で実行可能であるソースコードは,通常,Wiki 文書には記述できない.この理由 の 1 つは,管理者の意図しない悪意のある動作をするソースコードをサーバ上で実行できないようにする というセキュリティ上の制約である.我々は潜在的に危険をともなう IO アクションを分離して管理する ことにした.プログラミング言語 Haskell を Wiki エンジンの実装言語として選択して,IO モナド内でエ ンドユーザの記述した任意のコードを実行させないことで,管理者の意図しない悪意のある動作を防ぐと いうアプローチをとった.プログラマブルな Wiki ページは,プログラミング言語レベルのモジュールに 対応して,互いに参照し合うことができる.技術上の関心から極力 Wiki エンジンの深い部分まで,その Wiki 上でプログラミングができるように設計を試みた.プログラムの入力は,通常の Wiki 上のフォーム から可能であり,エンドユーザはクライアントに特別な環境を準備しなくても,その Wiki エンジンの開 発にリアルタイムに協調的に携わることが可能である.Wiki 文書において記述された副作用のある任意の アクションが実行されないことは Haskell のクラスを用いて静的型検査によって保証される. 

備考(Remarks) A wiki, a web application for modifying a website by web browsers easily and cooperatively, is now man- aged by many companies and organizations and many wiki clones are publicly available. Wiki documents are described under Wiki notation. Ordinary wikis are not able to execute part of Wiki documents, which are in part prevented by a potential security risk of the execution of arbitrary malicious codes. We eliminate such a risk by imposing restriction on all the actions under IO monads in end-users’ programs. Programmable wiki pages are literate Haskell programs that are language-level modules and can refer to one another. We design the architecture of the proposed wiki engine to be programmable by end users as much as possible. The development of a wiki engine on itself does not require the developing environment in the client computers. Type checking ensures the absence of arbitrary actions with side effects in end-users’ programs using Haskell’s type class and static type checking. 

2011  電池駆動システムにおけるプログラミング言語が与える消費エネルギーへの影響  学会発表  単著 
情報処理学会研究報告  , 一般社団法人情報処理学会  , Vol.2011-EMB-21(4)  , 5 p.  , 2011/03/10   

概要(Abstract) プログラミング言語の選択による情報通信端末の消費エネルギーの変化を定量的に評価する試みについて報告する.本稿では,アプリケーションの実装プログラミング言語ごとの消費電力への影響を,実情報端末において電力計で実測することにより確かめた.その結果,インタープリタ言語では消費電力の大きな揺れが観測されたが,コンパイル言語と同様の平均消費電力を示し,電池に与える影響の変化は限られた.われわれが実験を行った範囲では,プログラミング言語およびアプリケーションを変化させたときの1秒ごとの平均消費電力の変化は高々20%未満であり,その影響は軽微であることが確かめられた.われわれの知る範囲では,プログラミング言語ごとに消費電力/消費エネルギーの比較を行った報告は限られており,本研究で得られた基礎データは低消費エネルギーアルゴリズムや低消費エネルギープログラミングの研究を行う上での参考データとして貴重である.The trial of finding the programming language effects of energy consumption on a battery-powered system is presented. By means of a digital power meter, we measured the energy consumption of an information device on which different applications implemented in various programming languages run. While the power consumption fluctuated substantially when an interpretive language run on the device, the average power consumption of an interpretive language was not much different from that of a compiler language. The experimental results showed that the effects of what programming languages to use were limited; The change of the power consumption was up to approximately 20%. To the best of our knowledge the report on power/energy consumption of each programming language implementation has been limited and the result data is useful for studying the theoretical model of energy consumption and exploring energy efficient algorithms and programming. 

備考(Remarks) http://ci.nii.ac.jp/naid/110008583143 

2010  Optimization of Input-Erasing Clean Reversible Simulation for Injective Functions  学会発表  その他 
Preliminary Proceedings of Reversible Computation  , 17–24  , 2010/07   

概要(Abstract)  

備考(Remarks)  

2010  消費エネルギーを意識した可逆圧縮データ受信  国内学会発表  その他 
情報処理学会  , Vol.2011-EMB-20 No.1  , 1-6   

概要(Abstract) 情報通信端末において,データ受信と可逆データ解凍を逐次的に行うよりも,パイプライン化した方が消費エネルギーの最適化が実現されるケースが存在することが明らかになった.パイプライン化によって,マルチパスの圧縮コマンド bunzip2 では消費エネルギーは悪化してしまったが,ストリーム処理が可能な LZ(Lempel-Ziv) 系のアルゴリズムの場合,顕著なエネルギー最適化が達成された.データ受信が安定的に行える環境下で,情報通信端末の消費電力を電力測定器によって計測したところ,逐次処理と比較してパイプライン処理は最大 22.8% の消費エネルギー削減が達成された.It has been shown that there is a certain case in which the pipeline processing is more energy efficient than the sequential processing. Because of pipelining processes, LZ (Lempel-Ziv) family algorithms achieved significant energy savings while multi-path compression command bunzip2 suffered energy degradation. The experimentation has been performed on a commercial data transmission device connected to a digital power meter under the stable data transmission. A pipelining processing outperformed a sequential processing by 22.8% in terms of energy consumption. 

備考(Remarks) http://ci.nii.ac.jp/naid/110008583287 

2010  Reversible Computation and Reversible Programming Languages  国際学会発表  その他 
Dagstuhl Seminar   

概要(Abstract)  

備考(Remarks)  

2009  AndroidプラットフォームにおけるDalvikバイトコードのCPU負荷量の解析  国内学会発表  その他 
組込み技術とネットワークに関するワークショップ  , 2010/03   

概要(Abstract) 本稿では,ハードウェア独立な Dalvik バイトコードトレースから得られる情報を活用し,Android プラットフォームにおける CPU 負荷量の解析を行う.各 Dalvik バイトコードの CPU 負荷量を正確に精度良く解析するため,マイクロベンチマークの生成方法および実施方法を提示する.マイクロベンチマークの CPU 負荷量は,バイトコードの種類により最大 67 倍,引数のレジスタ値により最大 10 倍の差が存在した.したがって,アプリケーションの CPU 負荷量の正確なモデル化を行うためには,バイトコードの発行数のみならず,種類・引数を考慮する必要があることが明らかになった.以上により確立された解析手法を用いて,アプリケーション開発者に改善を提案するケーススタディを行った.実際に CPU 負荷量の削減方法を示唆できたことから,本解析手法の有効性が示された.We present a CPU load analysis method on Android platform by using hardware-independent trace information of Dalvik bytecodes. For the purpose of analysis, methods for generating and executing micro-benchmarks which issue the sequence of each Dalvik bytecode are introduced. The experimental results showed that the CPU load of micro-benchmarks was largely affected by the types arguments of bytecodes. Specifically, the variation of CPU load was up to 67 times over the types and 10 times over the arguments of given bytecodes. Therefore, not only the number of issued bytecode but also the types of bytecode and given arguments should be considered to construct an accurate CPU load model. Through a case study, the effectiveness of our approach for reducing CPU load has been validated. 

備考(Remarks) http://ci.nii.ac.jp/naid/110007993166 

2009  Modeling Power Consumption of Applications in Wireless Communication Devices Using OS Level Profiles  国際学会発表  その他 
Proc. International SoC Design Conference  , IEEE  , 253-256  , 2009/11/00   

概要(Abstract) We propose a novel system level power estimation method for wireless communication devices. The method estimates the power consumption of a processor and external devices by only using OS level profile information (i.e., the system call information), and is applicable to both off-line and online power optimizations. Evaluations on a commercial wireless communication device showed that the method achieves an estimation error of less than 10%. 

備考(Remarks) http://dx.doi.org/10.1109/SOCDC.2009.5423795 

2009  OSレベルのプロファイリング情報を用いた携帯端末アプリケーションの消費電力モデリング  国内学会発表  その他 
電子通信情報学会技術研究報告  , 電子通信情報学会  , Vol.108 No.478  , 49-54   

概要(Abstract) 通信端末のシステムレベルの消費電力予測を行う手法を提案する.本手法はプロセッサと周辺デバイスの消費電力を OS レベルのプロファイル情報のみを用いて予測するため,オフラインとオンラインの両者に適応可能である.商用の通信端末において通信を伴うアプリケーションを実行した評価では,本手法による予測消費電力の実測値に対するフィッティング誤差は 10% 以内に収まった.We propose a novel system level power estimation method for wireless communication devices. The method estimates the power consumption of processors and external devices by only using OS level profile information provided by system calls. The proposed method is applicable to on-line power estimation as well as off-line power estimation. Evaluations on a commercial wireless communication device showed that the method achieved an estimation error of less than 10 %. 

備考(Remarks) http://ci.nii.ac.jp/naid/110007995028 

詳細表示
学術関係受賞
年度
Year
受賞学術賞名
Name of award
受賞対象となった研究/業績/活動等
Activity for which award given
受賞年月(日)
Date
授与機関
Award presenter
2008  The Best Paper Award  2008年に発表した論文  2008年11月 
LG Electronics 

備考(Remarks)  

2003  高橋奨励賞    2010年03月15日 
日本ソフトウェア科学会 

備考(Remarks)  

詳細表示
研究発表
年度
Year
題目又はセッション名
Title or Name of Session
細目
Authorship
発表年月(日)
Date
発表学会等名称 Name, etc. of the conference at which the presentation is to be given, 主催者名称 Organizer, 掲載雑誌名等 Publishing Magazine,発行所 Publisher,巻/号 Vol./no.,頁数 Page nos.
2016  可逆プログラミング言語R-WHILEによる万能可逆チューリング機械の構成  共同  2017/03/16 
情報処理学会第79回全国大会  , 情報処理学会  , 1J-04  , 2   

概要(Abstract) 可逆プログラミング言語R-WHILEの計算モデルは,万能可逆チューリング機械と同じ計算能力があるとされている.しかし,筆者の知る限りにおいて,その具体的な証明についてはこれまで報告が無かった.本稿では任意の可逆チューリング機械を,意味が同じR-WHILEプログラムに変換できることを示す.このことにより,可逆万能チューリング機械のR-WHILEプログラムが構成できることを示す. 

備考(Remarks) https://www.gakkai-web.net/gakkai/ipsj/79/program79.html 

2016  Clean Reversible Simulation of Ranking Binary Trees  共同  2017/03/10 
The 19th JSSST Workshop on Programming and Programming Languages  , JSSST   

概要(Abstract) We propose clean reversible simulations of ranking binary trees and unranking as reversible algorithms for reversible computing systems, which are useful for enumerating and randomly generating binary trees. Algorithms for ranking binary trees and their inverses have been studied since the 1970s. Each of them can be made to be a reversible simulation by saving all the data and control information otherwise lost, and each pair of ranking and unranking reversible programs can be combined to realize a clean reversible simulation. However, such a clean reversible simulation requires multiple traversal of the given data and/or intermediate data as well as additional storage proportional to the length of the computation. We show that for Knott's ranking and unranking algorithms the additional storage usage can be reduced by using the proper assertions of reversible loops in embedded reversible simulations. We also show a clean reversible simulation that involves only one traversal. The running time and memory usage of the proposed clean reversible simulations are asymptotically equivalent to those of the original programs by Knott. All the reversible programs presented in this paper can be run on an interpreter of the reversible programming language Janus. 

備考(Remarks)  

2016  二分木のランク計算のクリーン可逆シミュレーション  共同  2016/09/07 
日本ソフトウェア科学会第33回大会  , 日本ソフトウェア科学会   

概要(Abstract) 可逆計算システムで用いる可逆アルゴリズムのひとつとして,二分木の列挙やランダム生成に有用な二分木のランク・アンランク計算のクリーン可逆シミュレーションを提案する.二分木のランク計算やその逆計算を行う非可逆アルゴリズムは1970年代から研究が行われてきており,これらの成果を用いてランク計算の関数とその逆関数のそれぞれの可逆シミュレーションを組み合わせてクリーン可逆シミュレーションを行うことはできる.しかし,こうした可逆シミュレーションでは,複数回のパスおよびに実行時間に比例した大きさのメモリが必要である.これに対してわれわれの可逆シミュレーションは,1パスで,漸近的な実行時間とメモリ使用量が元のアルゴリズムと同じである.本稿中の可逆プログラムは,可逆言語Janusの処理系で動作を確認できる. 

備考(Remarks)  

2015  On the Theory of Reversible Flowchart Languages  単独  2015/06/10 
Quantum Programming and Circuits Workshop  , University of Waterloo   

概要(Abstract) Flowcharts are a fundamental tool used pervasively in computer science. In this talk, we survey the fundamental properties of reversible flowcharts, which are classical flowcharts with restrictions on join points and atomic step operators. Reversible flowcharts are as expressive as any reversible computation models such as reversible Turing machines and are able to simulate any irreversible computation. The theoretical basis of structured programming in high-level reversible languages is provided by a reversible version of the Structured Program Theorem. We illustrate the design of high-level and low-level reversible programming languages and their translators, based on the reversible flowchart model. We highlight their features by demonstrating a reversible version of Dijkstra's permutation-to-code algorithm. 

備考(Remarks) https://uwaterloo.ca/institute-for-quantum-computing/conferences/quantum-programming-and-circuits-workshop 

2014  A Linear-Time Reversible Self-Interpreter  共同  2015/3/06 
第17回プログラミングおよびプログラミング言語ワークショップ  , 日本ソフトウェア科学会  , pp. 1-18   

概要(Abstract) This paper explores a novel combination of language features in re- versible programming languages. The two imperative languages that we introduce have reversible structured control flow operators and symbolic tree-structured data (S-expressions). The latter allows to model many familiar data structures in an easy way, which is more difficult in existing reversible imperative languages, which so far only provide integers, stacks and arrays as data types. Most importantly, it is shown for the first time in a most expressive reversible imperative language that tree-structured data enable efficient self-interpretation in the sense of Jones. We prove that the languages are r-Turing complete (most expressive), i.e. they are computationally as powerful as any reversible language can get, and cleanly reversible, i.e. programs can run backward without first tracing a forward computation. The languages presented here are two new versatile instances of our structured reversible flowchart paradigm, and intended to serve as a basis for future studies of reversible programming languages, transformation and algorithms. 

備考(Remarks) http://www-kb.is.s.u-tokyo.ac.jp/ppl2015/ 

2013  可逆プログラミング言語の引数渡し機構の拡張  共同  2014/03/18 
第98回プログラミング研究会  , 情報処理学会  , 2013-5-(6)   

概要(Abstract) 本稿では,可逆プログラミング言語Janus の引数渡し機構を拡張して,その拡張言語が可逆であることを示す.参照渡しのモデル化には,同一の参照をもつかもしれない複数の変数名が同じ記憶場所を指せるメモリモデルが必要である.これは既存のJanus で用いられていた状態モデルでは直接には扱うことができない.この問題を解決するために,われわれは,環境・記憶域モデルを導入して意味論を改良した.この結果,プロシージャの実引数には,局所変数や局所配列変数だけでなく大域変数や添字付き配列変数の参照,および同一の参照をもつ複数の構文対象も渡せるようになった.拡張言語が可逆であることの保証には,環境と記憶域の更新が可逆であることの保証が必要がある.これらの更新は,制限された可逆操作のみ用いて実現することで,可逆であることを保証する.われわれは,拡張言語が他にも既存のJanusの良い性質を保っていることを示す.すなわち,任意の文やプロシージャ呼び出しの逆実行ができること,および任意の文に対して逆文が存在してそれを求めるプログラム逆変換器が構成できることを示す.さらに,われわれは,プログラミング言語を可逆にするために課されていた代入の構文上の制限を緩和する.このことが原因で起こる記憶域の不正な更新は,大域のプログラム解析をせずとも,効率的に検知することができる.われわれが新たに定義した意味論は,既存の構文では同一の意味が与えられるという点で,既存言語からの単純な拡張となっている. 

備考(Remarks)  

2013  リストの可逆分割アルゴリズムを利用したゴミ情報が最適な可逆クイック整列法の生成  共同  2014/03/13 
第76回全国大会  , 情報処理学会   

概要(Abstract) 本論文では文献[1] におけるゴミ情報の生成・マージの手法を応用し,より一般性の高い手法を提案する.文献[1] では,ゴミ情報量が最適なリストの可逆分割アルゴリズムを提案している.ここではさらに提案したアルゴリズムを利用してクイックソートを生成し,分割の際のゴミ情報量が最適であること,再帰呼び出しの際にゴミ情報の最適な伝播が実現できていることの2 点を示している.しかし,この手法はクイックソートに特有のサブプロシージャに対して最適なゴミ情報の生成を保証することにより実現されており,この手法をそのまま他のアルゴリズムに応用することが難しい.そこで,本研究ではアルゴリズムのより小さな構成要素に最適なゴミ情報を生成させ,それらの最適性を保ったままより大きな構成要素へとマージを行う手法を提案し,既存の手法の応用性を高める.なお,ここではゴミ情報とは非可逆アルゴリズムを可逆化する際に記録する必要があり,可逆化する前の非可逆アルゴリズムにおいては記録する必要のない情報を表す. 

備考(Remarks)  

2013  引数渡し機構をもつ可逆プログラミング言語の可逆性  共同  2014/03/11 
第76回全国大会  , 情報処理学会   

概要(Abstract) 計算過程が可逆とは,任意の状態でその直前と直後の状態が存在すればそれぞれ必ず一意に定まることをいう.可逆プログラミング言語とは,そのプログラムの実行過程が必ず可逆になるような言語設計がなされているプログラミング言語であり,可逆論理回路の設計[1] やプログラミング言語理論の研究対象[2] として使われている.そうした言語のひとつであるJanusでは,構文規則や意味規則における制限によって可逆性を実現しており,その結果,可逆プログラムでのみ可能な逆実行をするための機構を備えている.現在のJanus[3] は,引数機構が未整備のために可読性や簡潔性が欠如していると考えられる点がある.原因のひとつとして,状態モデルによって識別子のみを渡すことのできる引数渡し機構が用いられていることが挙げられる.このため,識別子以外の式の評価値や参照を渡すことが困難であった.そこで,我々は左辺値を意味領域に含むことのできる環境・記憶域モデルを採用し,可逆性をもつ値渡しと参照渡しの機構を実現する.Janus では,複合代入演算の左辺に出現した識別子が右辺に出現してはならないという制約があるが,この拡張により,プログラム全域のプログラム解析をしなくてもその複合代入演算文の実行時にその文の情報だけからこの制約の確認ができるようになる.また,引数を伴うプロシージャ呼出しが,より読みやすく簡潔に記述できるようになる.本稿では,引数渡し機構を拡張して表現力の増したJanus が可逆性をもつことの説明の概略を示す. 

備考(Remarks)  

2011  A High-Level Reversible Programming Language  単独  2011/12/12 
Dagstuhl Seminar on Design of Reversible and Quantum Circuits   

概要(Abstract)  

備考(Remarks)  

詳細表示
研究助成
年度
Year
助成名称または科学研究費補助金研究種目名
Name of grant or research classification for scientific research funding
研究題目
Research Title
役割(代表/非代表)
Role
助成団体
Granting body
助成金額
Grant amount
2013  科学研究費補助金  関数型の視点からの効率的可逆シミュレーションおよび可逆プログラミング方法論の拡張 
  独立行政法人 日本学術振興会  4,030,000円 

研究内容(Research Content)  

備考(Remarks) https://kaken.nii.ac.jp/d/r/80456631.en.html 

2010  科学研究費補助金  可逆計算系と可逆プログラミング言語の設計と実現に関する研究 
代表  独立行政法人 日本学術振興会  2,730,000円 

研究内容(Research Content)  

備考(Remarks)  

2004  科学研究費補助金  プログラム運算の記述言語の設計及びその実現に関する研究 
代表  独立行政法人 日本学術振興会   

研究内容(Research Content)  

備考(Remarks)  

詳細表示
教育活動
年度
Year
タイトル
Title
内容等
Content
活動期間
Period of Activities
2016  模擬授業 

以下の内容で模擬授業を行いました。
------------------------------------
模擬授業のタイトル:プログラムはどうやって動くのか
模擬授業の内容:
コンピュータとのつき合い方には、使えればいいというものと、原理や歴史から知りたいというものがあります。本授業では後者のアプローチを取ってコンピュータにまつわることを見ていきます。また、わが国でたった一つのソフトウェア工学科において学べること、そして将来のキャリアについて考えます。 

2016/07/16 
2016  公開講座 

以下の内容で公開講座を実施しました。活発な質疑応答の時間をもてました。
------------------------------------------------------
公開講座のタイトル:プログラムはどうやって動くのか
公開講座の内容:
本講座では、コンピュータをただ使えればいいというのではなく、原理や歴史から知るというアプローチをとります。そもそも情報・計算とは何か、他の工業技術の発展と比較してコンピュータに関する技術の発展はどういった特徴があるのかを概観します。また、わが国でたった一つのソフトウェア工学科が生まれた背景を、社会・地域のニーズと南山大学におけるソフトウェア工学のカリキュラムや教育の実践といった両面からご紹介します。

. 情報とは?
. 何でも0と1で表せる
. プログラムでコンピュータを動かす
. 価値ある先端企業はIT・ソフトウェア系だ
. 研究紹介 

2015/07/26 
2015  「愛知からくりくふう展in刈谷」におけるレゴライントレースカーのプログラミング体験教室 

「愛知からくりくふう展in刈谷」で小中高に対して「レゴライントレースカーのプログラミング体験教室」を開催しました。
https://www.city.kariya.lg.jp/event/moyooshi/karakurikariya.html
http://www.city.kariya.lg.jp/shisei/kohokariya/simindayori/2016dayori0401.files/20160401_02.pdf 

2016/03/12 
2015  総合的な学習 出張講義「レゴマインドストーム(ロボット)で学ぶソフトウェア開発技術」 

以下の内容の出張講義を市内の高校で行いました。
=======================
本学の理工学部2年生は、レゴマインドストームを題材にした実習を通して、ソフトウェア開発技術を学ぶ。模擬授業では、この実習で行われているロボットの組み立て、ソフトウェアの設計・開発などの実演を見て概観を体験できる。さらに、実際の講義で用いる教材や実習における競技会の映像を見て、社会・地域のニーズを受けて産まれた日本で唯一のソフトウェア工学科においてどういった授業が行われているかを知れる。
======================= 

2015/11/12 
2015  学生による授業評価 

2015年度秋学期専門科目ソフトウェア工学科必修科目「ソフトウェア工学実習[SE]2」において実施いたしました学生による授業評価では,学部平均値を大きく上回る4.32という評価を受けました。
http://office.nanzan-u.ac.jp/kyoken/jugyou/ 

2015/09/01〜2016/03/31 
2015  ソフトウェア工学演習 教材,補講 

2015年度秋学期「ソフトウェア工学演習」の教材を,2015年度の受講生の学習状況を踏まえて改訂しました。特に,熱意ある約半数の受講生からの要望により補講を実施しました。

補講とその前後の授業のために,以下の資料を今年度に新たに作成しました。

http://tetsuo.jp/lecture/sw_ensyu/2015/lec_note/hoko_2015.pdf 

2015/09/01〜2016/01/31 
2015  ソフトウェア工学実習 教材作成 

2015年度秋学期前半,専門科目ソフトウェア工学科必修科目「ソフトウェア工学実習[SE]1」の授業のための教材を,授業計画に即して新たに作成しました。

2015年度秋学期後半,専門科目ソフトウェア工学科必修科目「ソフトウェア工学実習[SE]2」の教材を,2015年度秋学期後半の受講生の学習状況を踏まえて改訂しました。受講生からの要望を受けて下記アドレスに講義資料を公開しました。
http://tetsuo.jp/lecture/sw_jisyu/ 

2015/09/00〜2016/01/00 
2015  大学院生懇談会 

「大学院生懇談会」において,大学院生の皆さんと大学院の講義,カリキュラム,学生生活について話し合うことができました。 

2015/01/15 
2013  教育業績賞 

担当科目「プログラミング基礎実習」における取り組みが学部の発展に大きく寄与するものとして,「Teaching Award 情報理工学部教育業績賞」として学部長より表彰を受けました。 

2013/04/01~2013/07/10 
詳細表示
著書・学術論文に関する統計情報
年度
Academic Year
学術研究著書の件数
No. of Academic Books
学会誌・国際会議議事録等に掲載された学術論文の件数
No. of Academic Articles in Journals/Int'l Conference Papers
学内的な紀要等に掲載された学術論文の件数
No. of Academic Articles Pub'd in University Bulletins
学会受賞等の受賞件数
No. of Academic Awards Received
国際学会でのゲストスピーカーの件数
No. of Times as Guest Speaker at Int'l Academic Conferences
国際学会での研究発表の件数
No. of Presentations of Papers at Int'l Academic Conferences
国内学会でのゲストスピーカーの件数
No. of Times as Guest Speaker at National Academic Conf.
国内学会での研究発表の件数
No. of Papers Presented at National Academic Conf.
2017 
2016 
2015 
2014 
2013 
2012 
2011 
2010 
2009 
2008 
詳細表示

2017/06/09 更新