[Courses and Seminars] [Fall12: Algorithms | Asynchronous Systems | Seminar in Languages] [Other Pointers]
My primary research interests are in the areas of programming languages, compilers, and software systems. I am particularly interested in general and systematic methods for improving computation efficiency and software productivity. This includes (1) program analysis and transformation techniques for incremental computation and for parallel and concurrent computation, (2) applications in optimizing compilers, language-based interactive systems, real-time and reactive systems, algorithm design, program development, and software maintenance, and (3) supporting tools and user interfaces that allow convenient and efficient implementation of program analyses and transformations and facilitate their applications. My major research project, Incrementalization for Efficiency Improvement, together with derived projects, mainly on program dependence analysis and time and space analysis, encompasses all three aspects above.
I have strong other interests in database management, semantic web, distributed systems, and security. These include, in particular, query languages and query optimization, incremental view maintenance, intelligent information retrieval, property detection for distributed systems, systematic approaches for fault-tolerance, information flow analysis, and access control and trust management frameworks. I have also worked on uncertainty reasoning and expert systems.
¶ Y. A. Liu and S. D. Stoller. From Datalog Rules to Efficient Programs with Time and Space Guarantees. ACM Transactions on Programming Languages and Systems (TOPLAS), 31(6)1-38, August 2009. (at ACM |pdf) An earlier version appeared in Proceedings of the 5th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP), 2003. (at ACM |ps.gz | pdf)
¶ Y. A. Liu, S. D. Stoller, N. Li, and T. Rothamel. Optimizing aggregate array computations in loops. ACM Transactions on Programming Languages and Systems (TOPLAS), 27(1):91-125, January 2005. (at ACM |pdf) An earlier version appeared as Liu and Stoller, Loop optimization for aggregate array computations, in Proceedings of the 1998 IEEE International Conference on Computer Languages (ICCL). (at IEEE |abstract |ps.gz |pdf |slides.ps.gz)
¶ Y. A. Liu and S. D. Stoller. Dynamic programming via static incrementalization. Higher-Order and Symbolic Computation (HOSC), 16(1-2):37-62, March-June 2003. Special issue in memory of Bob Paige. (at Springer |ps.gz |pdf) An earlier version appeared in Proceedings of the 8th European Symposium on Programming (ESOP), 1999. (at Springer |abstract |ps.gz |pdf |slides.ps.gz)
¶ Y. A. Liu and S. D. Stoller. Eliminating dead code on recursive data. Science of Computer Programming (SCP), 47(2-3):221-242, May-June 2003. (at Elsevier |ps.gz |pdf) An earlier version appeared in Proceedings of the 6th International Static Analysis Symposium (SAS), 1999. (at Springer |abstract |ps.gz |pdf)
¶ Y. A. Liu and G. Gomez. Automatic accurate cost-bound analysis for high-level languages. IEEE Transactions on Computers (TC), 50(12):1295-1390, December 2001. (at IEEE |ps.gz |pdf) An earlier version appeared as Automatic accurate time-bound analysis for high-level languages, in Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), 1998. (at Springer |ps.gz |pdf)
¶ Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Strengthening invariants for efficient computation. Science of Computer Programming (SCP), 41(2):139-172, October 2001. (at Elsevier |ps.gz |pdf) An earlier version appeared as Discovering auxiliary information for incremental computation, in Conference Record of the 23rd Annual ACM Symposium on Principles of Programming Languages (POPL), 1996. (at ACM |ps.gz |pdf)
¶ Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Transactions on Programming Languages and Systems (TOPLAS), 20(3):546-585, May 1998. (at ACM |ps.gz |pdf) An earlier version appeared as Liu and Teitelbaum, Caching intermediate results for program improvement, in Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM), 1995. (at ACM |ps.gz |pdf)
¶ Y. A. Liu and T. Teitelbaum. Systematic derivation of incremental programs. Science of Computer Programming (SCP), 24(1):1-39, February 1995. (at Elsevier |ps.gz |pdf)
Some recent technical reports:
¶ From clarity to efficiency for distributed algorithms (LSLG-OOPSLA 12) (pdf)
¶ High-level executable specifications of distributed algorithms (LSL-SSS 12) (pdf)
¶ More efficient Datalog queries: Subsumptive tabling beats magic sets (TL-SIGMOD 11) (pdf)
¶ Precise complexity analysis for efficient Datalog queries (TL-PPDP 10) (pdf)
¶ Graph queries through Datalog optimizations (TGL-PPDP 10) (pdf)
¶ Composing transformations for instrumentation and incrementalization (GLSR-PEPM 12) (pdf)
¶ Alias analysis for optimization of dynamic languages (GLSRT-DLS 10) (pdf)
¶ A language and framework for invariant-driven transformations (LGS-GPCE 09) (pdf)
¶ Model checking linearizability via refinement (LCLS-FM 09) (pdf)
¶ From Datalog rules to efficient programs with time and space guarantees (LS-TOPLAS 09) (pdf)
¶ Generating incremental implementations of object-set queries (RL-GPCE 08) (pdf)
¶ Analysis and transformations for efficient query-based debugging (GTRSL-SCAM 08) (pdf)
¶ Generating specialized rules and programs for demand-driven analysis (THL-AMAST 08) (pdf)
¶ Efficient runtime invariant checking: A framework and case study (GRLS-WODA 08) (pdf)
¶ Efficient trust management policy analysis from rules (HTL-PPDP 07) (pdf)
¶ Efficient implementation of tuple pattern based retrieval (RL-PEPM 07) (pdf)
¶ Generating optimized code from SCR specifications (RLHL-LCTES 06) (pdf)
¶ Efficient type inference for secure information flow (HRLS-PLAS 06) (pdf)
¶ Core role-based access control: efficient implementations by transformations (LWGRCZZ-PEPM 06) (pdf)
¶ Role-based access control: a corrected and simplified specification (LS-ONR book 07) (slightly revised: pdf)
¶ Improved algorithm complexities for linear temporal logic model checking of pushdown systems (HL-VMCAI 06) (pdf)
¶ Querying complex graphs (LS-PADL 06) (pdf)
¶ Incrementalization across object abstraction (LSGRL-OOPSLA 05) (pdf)
¶ Parametric regular path queries (LRYSH-PLDI 04) (ps.gz |pdf)
¶ Iterate, incrementalize, and implement: A systematic approach to efficiency improvement and guarantees (Liu-ICC 03, abstract for an invited talk) (ps.gz |pdf)
¶ Optimizing Ackermann's function by incrementalization (LS-PEPM 03) (ps.gz |pdf)
¶ Optimized live heap bound analysis (USL-VMCAI 03) (ps.gz |pdf)
¶ A systematic incrementalization technique and its application to hardware design (JLZ-STTT 03) (ps.gz |pdf)
¶ Solving regular path queries (LY-MPC 02) (ps.gz |pdf)
¶ Program optimization using indexed and recursive data structures (LS-PEPM 02) (ps.gz |pdf)
¶ Automatic time-bound analysis for a higher-order language (GL-PEPM 02) (ps.gz |pdf)
¶ Automated software engineering using concurrent class machines (GLSSY-ASE 01) (ps.gz |pdf)
¶ Solving regular tree grammar based constraints (LLS-SAS 01) (ps.gz |pdf)
¶ Automatic live memory analysis for garbage-collected languages (USL-LCTES 01) (ps.gz |pdf)
¶ From recursion to iteration: what are the optimizations? (LS-PEPM 00) (ps.gz |pdf |slides.ps.gz)
¶ Efficiency by incrementalization: an introduction (Liu-HOSC 00) (ps.gz |pdf)
[a more complete list] [DBLP] [Google Scholar]
¶ DistAlgo. A language for programming distributed algorithms. SUNY Stony Brook, 2010-.
¶ InvTL/InvTS. An invariant-driven program transformation language and system. SUNY Stony Brook, 2005-.
¶ A system for generating efficient implementations from Datalog rules. SUNY Stony Brook, 2003-.
¶ MultiRunner and MultiQuery. Assistants for traversing links and answering queries on the Web. SUNY Stony Brook, 2001-2006.
¶ ALPA. An automatic language-based performance analysis system that generates accurate worst-case time and space given bounds on input sizes. Indiana University and SUNY Stony Brook, 1997-2006.
¶ CACHET continued. A program transformation system for drastic program optimization based on automated incrementalization and powerful program analysis. Indiana University, 1997-2000.
¶ CACHET. An incremental-attribution-based interactive system that uses systematic program analysis and transformation techniques to derive efficient incremental programs. Cornell University, 1993-1996.
¶ OGGEB. An expert system for evaluation of oil and gas generation in basins, with interfaces to several graphical tools for geochemical analysis. Research Institute of Petroleum Exploration and Development (CD-RIED) and Tsinghua University, 1988-1990.
Pervasive, intensive, and critical computations today require computer software to be highly efficient and reliable. Studies on this topic span almost all branches of computer science but have been relatively isolated in each area. The goal of our work has been to bring all techniques together in order to develop general systematic approaches and supporting tools for improving the efficiency of computations and facilitating the assurance of their correctness. This has involved exploring program analysis and transformation techniques and domain-specific knowledge for incrementalization.
Incrementalization transforms batch programs into efficient and correct incremental programs that exploit (1) the result of, (2) the intermediate results computed in, and (3) auxiliary information about a previous computation. Since every non-trivial computation proceeds by iteration or recursion, the approach can be used for achieving efficient computations by incrementalizing loops and recursions. This method has been applied to problems in list processing, graph algorithms, VLSI design, image processing, database queries, program analysis, and so on, which were previously solved in ad hoc and often error-prone ways. A prototype system, Cachet, for incrementalization has been under development. New methods for program dependence analysis and time and space analysis have been studied to support incrementalization and other program manipulation needs. An overview of all work is given below. A description with more details about the earlier parts was given earlier.
Work is in progress on refining all analysis and transformation aspects of the incrementalization approach to provide programming methods and compiler technologies for drastic program optimizations. Based on techniques of the Synthesizer Generator and APTS, originally developed by the groups of Professor Tim Teitelbaum at Cornell and Professor Bob Paige at NYU, respectively, we are also studying implementation frameworks and algorithms that support efficient, complex program analyses and transformations. As an application, we are investigating issues, including incremental state updates and interplay between optimization and abstraction (via objects and classes, components, or modules), for generating efficient code from higher-level, more declarative specifications for reactive systems and complex data manipulation systems. Another goal of this research is to develop methods for parallel and concurrent computations by incrementalizing across processors and analyzing asynchronous computations.
These projects have been supported in part by ONR, NSF, Motorola, etc. Some of them have been performed jointly with colleagues Radu Grosu, Steve Johnson, Bob Paige, Scott Smolka, Scott Stoller, and Tim Teitelbaum and PhD students Jon Brandvein, Gustavo Gomez, Michael Gorbovitski, Katia Hristova, Ning Li, Bo Lin, Byron Long, Tom Rothamel, Tuncay Tekle, Leena Unnikrishnan, Sean Yu, and Yuchen Zhang.
[some MS projects]
¶ CSE373/MAT373: Analysis of Algorithms, Stony Brook, Fall 2012.
¶ CSE535: Asynchronous Systems, Stony Brook, Fall 2012.
¶ CSE645: Seminar in Languages, Stony Brook, ... Fall 2012.
¶ CSE307: Principles of Programming Languages, Stony Brook, Spring 2007, 2009, 2011, 2012.
¶ CSE393/690: Concurrent and Distributed Algorithms, Stony Brook, Spring 2011 (CSE690), 2012,
¶ CSE/ISE308: Software Engineering, Stony Brook, Fall 2001, 2004, Spring 2010.
¶ CSE614: Advanced Programming Languages, Stony Brook, Spring 2008, 2010.
¶ CSE592: Protocol Design and Analysis, Stony Brook, Spring 2009.
¶ ITS102: How to Solve Them, Stony Brook, Spring 2007, 2008, 2009.
¶ CSE/ISE315: Database Transaction Processing Systems, Stony Brook, Spring 2006.
¶ CSE690: Program Design and Optimization, Stony Brook, Spring 2006.
¶ CSE526: Principles of Programming Languages, Stony Brook, Spring 2001, 2005.
¶ CSE591: Security Policy Frameworks, Stony Brook, Spring 2005.
¶ CSE391: Web Queries: Methods and Tools, Stony Brook, Spring 2004.¶ CSE352: Artificial Intelligence, Stony Brook, Spring 2003.
¶ CSE626: Advanced Programming Languages, Stony Brook, Spring 2003.
¶ CSE532: Advanced Database Systems, Stony Brook, Fall 2002.
¶ CSE/ISE305: Principles of Database Systems, Stony Brook, Spring 2002.
¶ CSE667: Design and Analysis Research Seminar, Stony Brook, Fall 2001.
¶ CSE675: Program Transformation and Program Analysis, Stony Brook, Fall 2000.
¶ B629 (Fall '99): Language-Based Algorithm Design and Analysis, Indiana U.
¶ P523 (Spring '99): Programming Language Implementation, Indiana U.
¶ B629 (Spring '99): Program Analysis and Program Transformation, Indiana U.
¶ (Fall 1998, Spring 1999): Computer Science Department Colloquium, Indiana U.
¶ C212/A592 (Fall 1997, 1998): Introduction to Software Systems (using Java), Indiana U.
¶ B629 (Spring '98): Language-Based Performance Analysis and Improvement, Indiana U.
¶ B403 (Spring '97): Introduction to Algorithm Design and Analysis, Indiana U.
¶ B629 (Spring '97): Program Transformation and Programming Environments, Indiana U.
¶ (Fall '96): Programming Languages Seminar, Indiana U.
¶ AMS SS 2013: Joint Mathematics Meetings AMS Special Session on Mathematical Underpinnings of Multivariate Complexity Theory and Algorithm Design, and Its Frontiers and the Field of Incrementalization, San Diego, CA, January 9-12, 2013.
¶ ESOP 2013: The 23nd European Symposium on Programming, Rome, Italy, March 16-24, 2013.
¶ GPCE 2012: The 11th International Conference on Generative Programming and Component Engineering, Dresden, Germany, September 24-27, 2012.
¶ Datalog 2.0: The Datalog 2.0 Workshop, Vienna, Austria, September 11-13, 2012.
¶ LCTES 2012: ACM SIGPLAN/SIGBED 2012 Conference on Languages, Compilers, Tools and Theory for Embedded Systems, Beijing, China, June 12-13, 2012.
¶ LADA 2012: Workshop on Languages for Distributed Algorithms, Philadelphia, USA, January 23-24, 2012 (with POPL 2012).
¶ GPCE 2011: The 10th International Conference on Generative Programming and Component Engineering, Portland, Oregon, October 22-23, 2011 (collocated with SPLASH 2011).
¶ LOPSTR 2011: The 21st International Symposium on Logic-Based Program Synthesis and Transformation, Odense, Denmark, July 18-20, 2011.
¶ SCOPES 2011: The 14th International Workshop on Software and Compilers for Embedded Systems, Schloss Rheinfels, St. Goar, Germany, June 27-28, 2011
¶ LCTES 2011: ACM SIGPLAN/SIGBED 2011 Conference on Languages, Compilers, Tools and Theory for Embedded Systems, Chicago, IL, April 12-14, 2011.
¶ CC 2011: The 20th International Conference on Compiler Construction, Saarbrucken, Germany, March 26-April 4, 2011.
¶ WG2.1 Meeting: The 66th Meeting of IFIP Working Group 2.1 on Algorithmic Languages and Calculi, Atlantic City, NJ, Sept 19-24, 2010.
¶ Some past events; plus one for a PLDI PC meeting, Portland OR, Jan. 19, 2002: taxi | firetruck | passengers
¶ CS Bib: DBLP | The Collection | CiteSeer | Dictionary: FOLDOC | Other: Compiler Construction Tools | W3C
¶ Computing Societies: ACM SIGPLAN SIGSOFT SIGMOD | IEEE CS TC-RTS | IFIP TC2 WG2.1 | EAPLS | CRA
¶ Directions to my office | My previous homepage at Indiana University
Last updated: Nov 28, 2012.