Deriving a Functional Knuth-Morris-Pratt Algorithm by Transformation
スポンサーリンク
概要
- 論文の詳細を見る
We show how a functional program for the Knuth-Morris-Pratt algorithm can be derived from a naive algorithm in a few transformation steps. Included also is an implementation technique for efficient memo-ization. The idea behind the transformation is simple but novel and specific to functional programming; we use partial parametrization of higher-order functions and memo-jzation by data structures. Partial parametrization corresponds to precomputation, which is a common optimization technique in procedural programming, and memo-ization is similar to tabulation, which replaces an expensive computation by a simple table lookup. Mathematical reasoning is provided for the transformation rules.
- 一般社団法人情報処理学会の論文
- 1991-02-10
著者
-
Takeichi Masato
Department Of Mathemetical Engineering And Information Physics Faculty Of Engineering University Of
-
Takeichi Masato
Department Of Computer Science The University Of Electro-communications
-
AKAMA YOJI
Department of Mathemetical Engineering and Information Physics, Faculty of Engineering, University o
-
Akama Yoji
Department Of Mathemetical Engineering And Information Physics Faculty Of Engineering University Of
関連論文
- Derivation of Efficient Pattern Matching Algorithms by Fully Lazy Evaluation with Lazy Memo-ization
- 3M-5 Bidirectional XML Transformation with Bi-X
- 3M-4 依存関係記述スキーマによる双方向XMLアプリケーションの開発(リーディングプロジェクト e-society:高信頼プログラミング言語と構造化文書変換技術,一般セッション,リーディングプロジェクト e-society)
- 3M-3 双方向変換に基づくウェブパブリッシング支援システムVu-X(リーディングプロジェクト e-society:高信頼プログラミング言語と構造化文書変換技術,一般セッション,リーディングプロジェクト e-society)
- A Java Library for Bidirectional XML Transformation
- 神経系の双方向マルチスケールシミュレーションと100時間ワークショップ : 東京大学21世紀COEプログラム「情報科学技術戦略コア」
- 2. 情報科学技術戦略コア(21世紀卓越した情報研究拠点プログラムの目指す研究(前編))
- 情報科学技術戦略コア
- 1.マルチコア計算機と基本的な並列化技法(マルチコアを活かすお手軽並列プログラミング)
- 並列プログラムの候補生成と適合性検査による並列化
- 補関数の生成による複製機能付きプログラムの自動双方向化
- 6.双方向変換による高信頼構造化文書処理(第1部:高い生産性を持つ高信頼ソフトウェア作成技術の開発,学と産の連携による基盤ソフトウェアの先進的開発)
- Generator-of-generators に基づく Fortress ライブラリ
- リスト上の最大マーク付け問題を解く並列プログラムの導出
- 木スケルトンによるXPathクエリの並列化とその評価
- 東京大学 情報理工学系研究科 創造情報学専攻の紹介(ラボラトリー)
- 木上の双方向変換を利用したファイルマネージャの実現
- 木上の双方向変換を利用したファイルマネージャの実現
- データマイニングのアルゴリズム記述を容易にする拡張行列演算の提案
- 閻魔 Webインタフェースによるプログラミング教育支援システム
- 決定論的2階パターンとプログラム変換への応用
- 木変換言語の双方向化に関する事例研究(サイバー増大ページ論文概要,新しいソフトウェアの実現,サイバー増大号)
- Relationship between Lambda Hoisting and Fully Lazy Lambda Lifting
- Deriving a Functional Knuth-Morris-Pratt Algorithm by Transformation
- An Alternative Scheme for Evaluating Combinator Expressions
- Consistent Annotations for Scope Rules
- Name Identification for Languages with Explicit Scope Control