# Isao Sasano

Ph.D. (March 2002, University of Tokyo)
Associate Professor, Department of Information Science and Engineering, College of Engineering, Shibaura Institute of Technology

## Research Interests

Program development system, Algorithm derivation, Program transformation, Functional graph algorithm

## Publications

1. Tsubasa Matsushita, Isao Sasano, Detecting code clones with gaps by function applications, ACM SIGPLAN 2017 Workshop on Partial Evaluation and Program Manipulation (PEPM 2017), Paris, France, January 16-17, 2017. (presented on January 16, 2017) Code clone detection tool based on the algorithms presented in the paper

2. Isao Sasano, A tool for visualizing buffer overflow with detecting return address overwriting, BICT 2015 Special Track on Modularization for Practical Software Engineering (MPSE2015), New York City, New York, United States, December 3-5, 2015. (presented on December 5, 2015) This paper is also available here.

3. Isao Sasano, Toward modular implementation of practical identifier completion on incomplete program text, BICT 2014 Special Track on Modularization for Practical Software Engineering (MPSE2014), Boston, Massachusetts, United States, December 1-3, 2014. (presented on December 2, 2014) An Emacs-mode based on the approach presented in the paper

Author's version: Copyright ©ICST, 2014. This is the author's version of the work. It is posted here by permission of ICST for your personal use. Not for redistribution. The definitive version was published in the ACM digital library.

4. Isao Sasano, Takumi Goto, An approach to completing variable names for implicitly typed functional languages, Higher-Order and Symbolic Computation, Volume 25, Issue 1, pp. 127-163, August 2013. Springer. (This is a journal version of the paper in PEPM 2012 below.)

5. Takumi Goto, Isao Sasano, An approach to completing variable names for implicitly typed functional languages, ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation (PEPM 2012), pp. 131-140, Philadelphia, Pennsylvania, USA, January 23-24, 2012. An Emacs-mode based on the algorithm presented in the paper

Author's version: Copyright ©ACM, 2012. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM SIGPLAN 2012 Workshop on Partial Evaluation and Program Manipulation (PEPM'12), January 23-24, 2012, Philadelphia, Pennsylvania, USA, http://doi.acm.org/10.1145/2103746.2103771.

6. Yota Kogure, Isao Sasano, Masaomi Kimura, A Topic Maps Query Language supporting Composite and Recursive Queries, 12th International Symposium on Advanced Intelligent Systems (ISIS 2011), SA1-3, LA VIE D'OR Resort, Suwon, Korea, September 28-October 1, 2011.

7. Soichiro Hidaka, Zhenjiang Hu, Kazuhiro Inaba, Hiroyuki Kato, Kazutaka Matsuda, Keisuke Nakano, Isao Sasano, Marker-directed optimization of UnCAL graph transformations, 21st International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2011), Odense, Denmark, July 18-20, 2011. Lecture Notes in Computer Science, Vol. 7225, pp. 123-138, Springer Verlag.

8. Isao Sasano, Zhenjiang Hu, Soichiro Hidaka, Kazuhiro Inaba, Hiroyuki Kato, Keisuke Nakano, Toward bidirectionalization of ATL with GRoundTram, International Conference on Model Transformation (ICMT 2011), Zurich, Switzerland, June 27-28, 2011. Lecture Notes in Computer Science, Vol. 6707, pp. 138-151, Springer Verlag.

9. Atsushi Ohori, Isao Sasano, Lightweight Fusion by Fixed Point Promotion, The 34th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2007), pp. 143-154, Nice, France, January 17-19, 2007. ACM Press.

10. Isao Sasano, Mizuhito Ogawa, Zhenjiang Hu, Maximum Marking Problems with Accumulative Weight Functions, International Colloquium on Theoretical Aspects of Computing (ICTAC2005), Hanoi, Vietnam, October 17-21, 2005. Lecture Notes in Computer Science, Vol. 3722, pp. 562-578, Springer Verlag.

11. Mizuhito Ogawa, Zhenjiang Hu, Isao Sasano, Iterative-Free Program Analysis, Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming ( ICFP2003), pp. 111-123, Uppsala, Sweden, August 25-29, 2003. ACM Press.

Abstract Program analysis is the heart of modern compilers. Most control flow analyses are reduced to the problem of finding a fixed point in a certain transition system, and such fixed point is commonly computed through an iterative procedure that repeats tracing until convergence. This paper proposes a new method to analyze programs through recursive graph traversals instead of iterative procedures, based on the fact that most programs (without spaghetti goto) have well-structured control flow graphs, graphs with bounded tree width. Our main techniques are; an algebraic construction of a control flow graph, called SP Term, which enables control flow analysis to be defined in a natural recursive form, and the Optimization Theorem, which enables us to compute optimal solution by dynamic programming. We illustrate our method with two examples; dead code detection and register allocation. Different from the traditional standard iterative solution, our dead code detection is described as a simple combination of bottom-up and top-down traversals on SP Term. Register allocation is more interesting, as it further requires optimality of the result. We show how the Optimization Theorem on SP Terms works to find an optimal register allocation as a certain dynamic programming.

12. Isao Sasano, Generation of Efficient Algorithms for Maximum Marking Problems, Ph. D. thesis, University of Tokyo, 2002.

Abstract In existing work on graph algorithms, it is known that a linear time algorithm can be derived mechanically from a logical formula for a class of optimization problems. But this has a serious problem that the derived algorithm has huge constant factor. In this work, we redefine this problem on recursive data structures as a maximum marking problem and propose method for deriving a linear time algorithm for that. In this method, specification is given using recursive functions instead of logical formula, which results in a practical linear time algorithm. This method is mechanical and in fact, based on this deriving method, we make a system which automatically generates a practical linear time algorithm from specification for a maximum marking problem.

13. Tetsuo Yokoyama, Isao Sasano, Zhenjiang Hu, Masato Takeichi, Automatic Generation of Programs Based on High Level Strategy Description, IPSJ Transactions on Programming, Vol. 43, No. SIG 3(PRO 14), pp. 62-77, March 2002. (in Japanese)

14. Isao Sasano, Zhenjiang Hu, Masato Takeichi, Mizuhito Ogawa, Derivation of Linear Algorithm for Mining Optimized Gain Association Rules, JSSST Computer Software, Vol. 19, No. 4, pp. 39-44, 2002. Iwanami Shoten.

Abstract Data mining, which is a technology for obtaining useful knowledge from large database, has been gradually recognized as an important subject. Algorithms for data mining have to be efficient since target database is often huge, and various kinds of efficient algorithms for data mining are individually investigated. This paper shows that an efficient linear time algorithm for mining optimized gain association rules can be systematically derived from a simple specification by reducing it to an instance of the {\it maximum marking problem}. Our approach not only automatically guarantees the correctness of the derived algorithm, but also is easy to derive new algorithms for modification of the problem.

15. Isao Sasano, Zhenjiang Hu, Masato Takeichi, Generation of Efficient Programs for Solving Maximum Multi-Marking Problems, Workshop on the Semantics, Applications, and Implementation of Program Generation ( SAIG2001 ), Firenze, Italy, September 6, 2001. Lecture Notes in Computer Science, Vol. 2196, pp. 72-91, Springer Verlag.

Abstract Program generation has seen an important role in a wide range of software development processes, where effective calculation rules are critical. In this paper, we propose a more general calculation rule for generation of efficient programs for solving maximum marking problems. Easy to use and implement, our new rule gives a significant extension of the rule proposed by Sasano {\em et al.}, allowing multiple kinds of marks as well as more general description of the property of acceptable markings. We illustrate its effectiveness using several interesting problems.

16. Isao Sasano, Zhenjiang Hu, Masato Takeichi, Mizuhito Ogawa, Solving a Class of Knapsack Problems on Recursive Data Structures, JSSST Computer Software, Vol. 18, No. 2, pp. 59-63, 2001. Iwanami Shoten. (in Japanese)

17. Isao Sasano, Zhenjiang Hu, Masato Takeichi, Mizuhito Ogawa, Calculating Linear Time Algorithms for Solving Maximum Weightsum Problems, JSSST Computer Software, Vol. 18, No. 5, pp. 1-16, 2001. Iwanami Shoten. (in Japanese)

• International conference version: Isao Sasano, Zhenjiang Hu, Masato Takeichi, Mizuhito Ogawa, Make it Practical: A Generic Linear-Time Algorithm for Solving Maximum-Weightsum Problems, Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming ( ICFP2000 ), pp.137-149, Montreal, Canada, September 18-20, 2000. ACM Press.

Abstract In this paper we propose a new method for deriving a practical linear-time algorithm from the specification of a maximum-weightsum problem: From the elements of a data structure $x$, find a subset which satisfies a certain property $p$ and whose weightsum is maximum. Previously proposed methods for automatically generating linear-time algorithms are theoretically appealing, but the algorithms generated are hardly useful in practice due to a huge constant factor for space and time. The key points of our approach are to express the property $p$ by a {\em recursive\/} boolean function over the structure $x$ rather than a usual logical predicate and to apply program transformation techniques to reduce the constant factor. We present an {\em optimization theorem}, give a calculational strategy for applying the theorem, and demonstrate the effectiveness of our approach through several nontrivial examples which would be difficult to deal with when using the methods previously available.

• Preliminary version appeared in the informal proceedings of the Second JSSST Workshop on Programming and Programming Languages (PPL'00), pp. 14-25, Hamanako, Shizuoka, Japan, March 20-22, 2000.

• Summary was presented at an informal workshop: The Third Program Transformation Workshop (PTW'00), Hakone, Japan, March 15-17, 2000.

18. Isao Sasano, Zhenjiang Hu, Masato Takeichi, A General Recursive Form for Graph Traversals and its Transformations, JSSST Computer Software, Vol. 17, No.3, pp.2-19, 2000. Iwanami Shoten. (in Japanese)

19. Isao Sasano, Zhenjiang Hu, Masato Takeichi, Constructive Approach to Deriving Graph Algorithms, 15th Conference Proceedings Japan Society for Software Science and Technology, pp. 269-272, The University of Electro-Communications, September 8-11, 1998. (in Japanese)

## Presentations not listed in the above

1. Isao Sasano, Bidirectionalization of ATL with GRoundTram: Transformation algorithms, Atlanmod-BiG Joint workshop on Bidirectionality in Model Transformations, MINES ParisTech Ecole Nationale Superieure des Mines de Paris, September 15, 2012, Mercure Paris Place d'Italie, September 16, 2012.
2. Isao Sasano, Model Query Language MQL, Workshop on Bidirectional Transformation (BT 2010), National Institute of Informatics, Tokyo, Japan, March 15, 2010.
3. Isao Sasano, Generic solution for maximum marking problems in Generic Haskell, Workshop on Robust Software Construction (WRSC 2003), Oral presentation, International Productivity Center, Hayama, Kanagawa, Japan, February 28 - March 2, 2003.
4. Mizuhito Ogawa, Zhenjiang Hu, Isao Sasano, and Masato Takeichi, Algebraic construction of graphs with bounded tree width and its applications -- Catamorphic Approach to Program Analyses, The Third Asian Workshop on Programming Languages and Systems (APLAS 2002), pp. 58-73, Shanghai Jiao Tong University, Shanghai, China, November 29 - December 1, 2002.
5. Isao Sasano, Zhenjiang Hu, and Masato Takeichi, Solving more general maximum-marking problems on recursive data structures, The 5th program transformation workshop (PTW 2001), Oral presentation, Yokohama Techno Tower Hotel, Yokohama, Japan, March 15 - 16, 2001.
6. Isao Sasano, Zhenjiang Hu, Masato Takeichi, and Mizuhito Ogawa, Make it practical: A generic linear-time algorithm for solving maximum-weightsum problems, The 4th program transformation workshop, Oral presentation, Oxford University Computing Laboratory, UK, August 29 - 31, 2000.

## Personal history

I am an associate professor in Department of Information Science and Engineering, College of Engineering, Shibaura Institute of Technology from October 2012.
I was an assistant professor in Shibaura Institute of Technology from October 2008 until September 2012.
I was a research associate (assistant professor from April 2007) in Ohori lab, RIEC, Tohoku University from June 2005 until September 2008.
I was a research associate in JAIST from April 2003 until May 2005.
I was a visitor of Oxford University Computing Laboratory from April 2002 until January 2003.
I was a research fellow of the Japan Society for the Promotion of Science from April 2001 until March 2003.
I was a student at IPL in the University of Tokyo from April 1997 until March 2002.
I received Ph.D. from the University of Tokyo in March 2002.
I received the Master of Engineering from the University of Tokyo in March 1999.
I received the Bachelor of Engineering in Mathematical Engineering and Information Physics from the University of Tokyo in March 1997.