Welcome to Yoshihiko Futamura's Website.

Yoshihiko Futamura = Futamura (Yoshihiko Futamura) because YF=F(YF)
This is not the Futamura Projection !!!

Yoshihiko Futamura, Ph.D. was born in 1942. He is a Professor of Department of Information and Computer Science and the director of the Institute for Software Production Technology (ISPT) of Waseda University. He received his BS in mathematics from Hokkaido University in 1965, MS in applied mathematics from Harvard University in 1973 and Ph.D. degree from Hokkaido University in 1985. He joined Hitachi Central Research Laboratory in 1965 and moved to Waseda University in 1991. He was a visiting professor of Uppsala University from 1985 to 1986 and a visiting scholar of Harvard University from 1988 to 1989. Automatic generation of computer programs and programming methodology are his main research fields. He is the inventor of the Futamura Projections in partial evaluation and PAD (Problem Analysis Diagram PDF1MB). PAD has been adopted as an international standard (ISO8631) and a national standard of China (GB13502). He was an editor of the Journal of New Generation Computing (1982-1995). He has been an Advisory Board member of the Journal of New Generation Computing from 1996 and an Advisory Board member of the Journal of Higher Order and Symbolic Computation from 2002. During more than 30 years of his career, he has contributed more than 200 research papers and patents on Programming Methodology, Software Engineering and Theoretical Computer Science.

email: futamura@waseda.jp
Japanese page : http://www.futamura.info.waseda.ac.jp/~futamura/index-j.html
 

Recent Useful Software We Developed

Random Graph Server (RGS):
Random Graph Server generates connected undirected graphs with specified numbers of vertices and edges. Generated graphs are edge-weighted, and the weight follows uniform distribution in the range [0,1). The generation time is O(m log m) where m stands for number of edges.

Random Data Server (RDS):
Random Data Server generates a uniform random permutation with length n and leaves m in O(n) time and O(1) space. The leaf of a sequence stands for an element in the sequence that does not have any smaller neighbor than it. Generated permutations are useful for performance evaluation of leaf-adaptive algorithms such as sorting (Theory of RDS translated from our Japanese paper is in PDF111KB)

MRPOD SYSTEM
MRPOD SYSTEM is an automatic program transformation system for Mutual Recursive Program with One Descent Function (MRPOD). This includes T(n) Solver which  is an automatic solver of a recurrence the type of which is T(n)=c₁(n)*T(d(n))+c₂(n).

Recent Publications in English

• Yoshihiko Futamura, Zenjiro Konishi, Kazuaki Maeho, Masahiko Kawabe: Automatic Generation of a Suffix Trie from a Naive Pattern Matcher and a Text by Partial Evaluation, 1A2，Proc. of JSSST, September, 2003. (PDF120KB)
   
• Y. Futamura, Z. Konishi, R. Glueck: WSDFU: Program Transformation System Based on Generalized Partial Computation, The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones, Lecture Notes in Computing Science 2566, 2002, pp357-377.
   
• Y. Futamura, Z. Konishi, R. Glueck: Automatic Generation of Efficient String Matching Algorithms by Generalized Partial Computation, (Invited Talk) Proc.of ACM SIGPLAN ASIA-PEPM 2002, September 12-14, 2002,  pp1-8. (PDF128KB)
   
• Y. Futamura, Z. Konishi, R. Glueck: Program Transformation System Based on Generalized Partial Computation, New Generation Computing, Vol.20 No.1, Nov 2001. pp75-99.
   
• Yoshihiko Futamura: Partial Evaluation of Computation Process --- An approach to a Compiler-Compiler, Higher-Order and Symbolic Computation, Volume 12, December 1999, pp381-391. (Reproduction of the 1971 paper).(PDF54KB)
   
• Yoshihiko Futamura: Partial Evaluation of Computation Process Revisited, Higher-Order and Symbolic Computation, Volume 12, December 1999, pp377-380.(PDF22KB)

Important Patents

• Yoshihiko Futamura, Kenroku Nogi: PROGRAM TRANSFORMATION BASED ON GENERALIZED PARTIAL COMPUTATION, 5241678, US-Patent, Aug. 31, 1993.
• Yoshihiko Futamura, Kenroku Nogi: PROGRAM TRANSFORMATION BASED ON GENERALIZED PARTIAL COMPUTATION, 2922207, Japan-Patent, Jul 19, 1999.

Futamura's Personal PE Museum

24 Aug. 1969:  Source Program and Results of Test Runs of Self Applicable PE (PDF10MB This is a very large PDF file.) and Supporting Documentation (PDF2MB).

Aug. 1971: Original Japanese Paper (PDF876KB): Partial Evaluation of Computation Process --- An approach to a Compiler-Compiler, Vol.54-C, No.8 of Transactions of the Institute of Electronics and Communication Engineers of Japan, pp.721–728, in August 1971.

4 Nov. 1971: Draft of unpublished paper written with John K. Dixon (PDF2.7MB).

24 Jan. 1973: EL1 PARTIAL EVALUATOR Progress Report submitted to Dr. Ben Wegbreit at Harvard (PDF700KB).

19 Jan. 1978: A Letter from A.P. Ershov (PDF88KB).