Hai (Paul) Liu

Computer Science Department
P.O.Box 208285
Yale University
New Haven, CT 06520

Phone: (203) 432 1267
Resume · Publications · Projects · Code Snippets · Random Stuff

I'm a final year phD student at Yale University doing research in Programming Languages, with a focus on Functional Reactive Programming (FRP), and Domain Specific Languages (DSL). I'm part of the Yale Haskell Group, and my advisor is Professor Paul Hudak. I can be reached at hai dot liu at yale dot edu or paul at thev dot net.

Publications

Zhijing G. Mou, Hai Liu, and Paul Hudak. Compress-and-Conquer for Optimal Multicore Computing. The Fifth Workshop on Declarative Aspects of Multicore Programming (DAMP2010), Madrid, Spain. January 2010. (to appear) [ abstract | bibtex | pdf ]

We propose a programming paradigm called compress-and-conquer (CC) that leads to optimal performance on multicore platforms. Given a multicore system of $p$ cores and a problem of size $n$, the problem is first reduced to $p$ smaller problems, each of which can be solved independently of the others (the compression phase). From the solutions to the $p$ problems, a compressed version of the same problem of size $O(p)$ is deduced and solved (the global phase). The solution to the original problem is then derived from the solution to the compressed problem together with the solutions of the smaller problems (the expansion phase).

The CC paradigm reduces the complexity of multicore programming by allowing the best-known sequential algorithm for a problem to be used in each of the three phases. In this paper we apply the CC paradigm to a range of problems including scan, nested scan, difference equations, banded linear systems, and linear tridiagonal systems. The performance of CC programs is analyzed, and their optimality and linear speedup are proven. Characteristics of the problem space subject to CC are formally examined, and we show that its computational power subsumes that of scan, nested scan, and mapReduce.

The CC paradigm has been implemented in Haskell as a modular, higher-order function, whose constituent functions can be shared by seemingly unrelated problems. This function is compiled into low-level Haskell threads that run on a multicore machine, and performance benchmarks confirm the theoretical analysis.

Hai Liu, and Paul Hudak. An Ode to Arrows. Twelfth International Symposium on Practical Aspects of Declarative Languages - PADL'10. Madrid, Spain. January 2010. (to appear) [ abstract | bibtex | pdf ]

We study a number of embedded DSLs for autonomous ordinary differential equations (autonomous ODEs) in Haskell. A naive implementation based on the lazy tower of derivatives is straightforward but has serious time and space leaks due to the loss of sharing when handling cyclic and infinite data structures. In seeking a solution to fix this problem, we explore a number of DSLs ranging from shallow to deep embeddings, and middle-grounds in between. We advocate a solution based on arrows, an abstract notion of computation that offers both a succinct representation and an effective implementation. Arrows are ubiquitous in their combinator style that happens to capture both sharing and recursion elegantly. We further relate our arrow-based DSL to a more constrained form of arrows called causal commutative arrows, the normalization of which leads to a staged compilation technique improving ODE performance by orders of magnitude.

Hai Liu, Eric Cheng, and Paul Hudak. Causal Commutative Arrows and Their Optimization. Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP 2009). Edinburgh, Scotland. August 2009.   [ abstract | bibtex | pdf | slides ]

Arrows are a popular form of abstract computation. Being more general than monads, they are more broadly applicable, and in particular are a good abstraction for signal processing and dataflow computations. Most notably, arrows form the basis for a domain specific language called Yampa, which has been used in a variety of concrete applications, including animation, robotics, sound synthesis, control systems, and graphical user interfaces.

Our primary interest is in better understanding the class of abstract computations captured by Yampa. Unfortunately, arrows are not concrete enough to do this with precision. To remedy this situation we introduce the concept of commutative arrows that capture a kind of non-interference property of concurrent computations. We also add an init operator, and identify a crucial law that captures the causal nature of arrow effects. We call the resulting computational model causal commutative arrows.

To study this class of computations in more detail, we define an extension to the simply typed lambda calculus called causal commutative arrows (CCA), and study its properties. Our key contribution is the identification of a normal form for CCA called causal commutative normal form (CCNF). By defining a normalization procedure we have developed an optimization strategy that yields dramatic improvements in performance over conventional implementations of arrows. We have implemented this technique in Haskell, and conducted benchmarks that validate the effectiveness of our approach. When combined with stream fusion, the overall methodology can result in speed-ups of greater than two orders of magnitude.

Hai Liu, and Paul Hudak. Plugging a Space Leak with an Arrow. Electronic Notes in Theoretical Computer Science. 193 (Nov. 2007), 29-45.   [ abstract | bibtex | pdf ]

The implementation of conceptually continuous signals in functional reactive programming (FRP) is studied in detail. We show that recursive signals in standard implementations using streams and continuations lead to potentially serious time and space leaks under conventional call-by-need evaluation. However, by moving to the level of signal functions, and structuring the design around arrows, this class of time and space leaks can be avoided. We further show that the use of optimal reduction can also avoid the problem, at the expense of a much more complex evaluator.

Hao Wang, Yang Richard Yang, Paul H. Liu, Jia Wang, Alex Gerber, and Albert Greenberg. Reliability as an Interdomain Service. In Proceedings of ACM SIGCOMM, Kyoto, Japan, August 2007. [ abstract | bibtex | pdf ]

Reliability is a critical requirement of the Internet. The availability and resilience of the Internet under failures can have significant global effects. However, in the current Internet routing architecture, achieving the high level of reliability demanded by many mission critical activities can be costly. In this paper, we first propose a novel solution framework called reliability as an interdomain service (REIN) that can be incrementally deployed in the Internet and may improve the redundancy of IP networks at low cost. We then present robust algorithms to efficiently utilize network redundancy to improve reliability. We use real IP network topologies and traffic traces to demonstrate the effectiveness of our framework and algorithms.

K.Y. Leong, H. Liu, O.P. Wu. Unicode, Java and Input Methods, Twelfth International Unicode Conference, Tokyo, Japan. (Apr 1998)

Projects

Here are some software projects that I've worked on. They may be school or work related, or just of personal interest. Only open source projects are listed here although some are yet to be made public. A more complete list can be found in my resume.

CCA is a pre-processor and optimizer for Causal Commutative Arrows, which is a more constrained class of Arrows with two additional laws: commutativity and product. It implements the normalization algorithm presented in our paper using Template Haskell to provide staged compilation of generic CCA arrows, with speedups sometimes over two orders of magnitude. The pre-processor is based on Paterson's arrowp preprocessor but specialized to deal with CCA. Latest development version can be found in its darcs repository.

Euterpea is a new Haskell library for computer music applications developed at the Yale Haskell Group. It is a descendent of Haskore and HasSound, and is intended for both educational purposes as well as serious computer music development. Euterpea is a wide-spectrum library, suitable for high-level music representation, algorithmic composition, and analysis; mid-level concepts such as MIDI; and low-level audio processing, sound synthesis, and instrument design. The name Euterpea is derived from Euterpe, who was one of the nine Greek Muses (goddesses of the arts), specifically the Muse of Music. My contribution include the real-time MIDI I/O, as well as a Musical User Interface that enables a set of computer-music specific GUI widgets such as keyboards, guitar frets, knobs, sliders, and so on. Yale ITS had an article about our work behind this. The software is under active development and can be obtained from its darcs repository.

Hwiki is a custom Wiki engine written in Haskell to provide online book editing and sharing, and PDF publication to e-ink reader devices including iRex iLiad, Sony Reader, Amazon Kindle DX and a few others. It runs as a SCGI program, serves an AJAX interface (borrowed from Orchid), and relies on Pandoc to parse Markdown syntax. Notable features include automatic segmentation of big files into smaller chunks, and a built-in special purpose revision control system that supports millons of small files because neither git or darcs is up to the task.

LambdaINet is an experimental Interaction Net evaluator written in Haskell that implements optimal evaluation for Lambda calculus based on Lambdascope. It features an interactive graphical user interface that helps understanding optimal as well as other reduction strategies. Not included at the moment is a prototypical implementation of a fine-grain parallel reduction system (complete with a concurrent garbage collector) for Interaction Nets that is both lock-free and wait-free. Few implementations exist for optimal evaluation, I'm proud that this is one of them.

GLFW is a is a Haskell module for GLFW OpenGL framework. It provides an alternative to GLUT for OpenGL based Haskell programs. I initially started this project as an effort to port SOE software to a modern cross-platform graphics interface. The latest version is a cabal install away from Hackage DB, and its development is now coordinated through the mailinglist and darcs repsitory.

The following are past projects no longer being maintained. Source codes are distributed as they are, and I have no knowledge whether they still compile or work at all.

Incremental Garbage Collector is a patch for Lua 4.0 that implements a tri-color algorithm so as to reduce apparent GC pause during Lua script execution, and to meet critical requirements for applications like games. The patch was written and released in 2002, and obsoleted by Lua 5.1 when the latter came out in 2005 with a built-in incremental collector.

GEEP is a multi-channel communication protocol to replace TCP, or put in another way, a reliable data transport layer on top of UDP, developed at GIME International in 2001. It features minimal connection maintenance overhead, built-in multi-channel control within same connection, selective acknowledgement to reduce network load, and enhanced Vegas transmission control mechanisms to speed up transfer by fully utilizing available bandwidth. GEEP has served well as data protocol between game client and server, as well as in a generic software auto-update service.

GIME is a generic engine that supports multi-threading, internationalization, database, multiple interfaces including web, telnet and graphic clients on which massive multi-user interactive applications could be built with little effort. It was the first open technology developed at GIME International back in 2001. Its SourceForge repository provides the backend server (written in Pike), frontend GUI tools (written in Lua and C), and a demo groupware built with GIME (also with Roxen webserver). There was also a later unreleased version written in Haskell which served a WAP game for cellphones, but that was more of an experiment than a real product.

SGZ MUD is a text-based Chinese MUD (Multi-User Dungeon) with a background set in the Three Kingdoms era. It started in 1998 after I localized a version of Lima Mudlib in Chinese, and soon became a rare gem among popular Chinese MUDs at the time due to its unique strategy play. The enthusiasm about the game led us to start a company to develop it further to eventually become the GIME engine and the Century of Three Kingdoms MMOG. SGZ mudlib (excluding player data) is made available as LPC source codes, and you need a version of MudOS driver (or precompiled i386 Linux binary) to run it.

Code Snippets

The following are some code samples, tutorials, or just topics that I'd like to cover. I'm putting an on-going effort to make them both documented as well as enjoyable.

Random Stuff

Rants, casual writing, or just for fun.

© 2009 Paul Liu · Brought to you by Typogridphy CCS · Valid XHTML 1.0 Strict