Category Archives: Workshop

Constructing datatype-generic fully polynomial-time approximation schemes using generalised thinning

Shin-Cheng Mu, Yu-Han Lyu, and Akimasa Morihata. In the 6th ACM SIGPLAN workshop on Generic programming (WGP 2010), pages 97-108, Sep. 2010. [PDF]

The fully polynomial-time approximation scheme (FPTAS) is a class of approximation algorithms that is able to deliver an approximate solution within any chosen ratio in polynomial time. By generalising Bird and de Moor’s Thinning Theorem to a property between three orderings, we come up with a datatype-generic strategy for constructing fold-based FPTASs. Greedy, thinning, and approximation algorithms can thus be seen as a series of generalisations. Components needed in constructing an FPTAS are often natural extensions of those in the thinning algorithm. Design of complex FPTASs is thus made easier, and some of the resulting algorithms turn out to be simpler than those in previous works.

XML stream processing using a lazy concurrent language

S-C. Mu, T-C. Tsai, and K. Nakano. In Programming Language Techniques for XML (PLAN-X 2008). January 2008. [PDF]

Motivated by previous work on XML stream processing, we noticed that programmers need concurrency to save space, especially in a lazy language. User-controllable concurrency provides the possibility of reducing space usage in many programs. With lower garbage-collection overhead resulting from concurrent execution, the elapsed time of programs, stream processing ones in particular, is tremendously decreased.

The challenge is how to encapsulate concurrency without compromising expressiveness and flexibility of languages. We propose the idea of pushing datatypes — when a pushing closure is demanded, all expressions referring to it are evaluated concurrently to weak head normal forms. The closure is no more alive and may thus be garbage collected. Semantically, it is a non-intruding extension because it does not change the denotational semantics of an expression. It is also easy to be implemented on top of a language providing concurrent threads and inter-thread synchronisation. We have developed a prototype using Haskell and showed pushing datatypes can be used to effectively reduce space usage and thus result in shorter elapsed time in many programs.

Quantum functional programming

S-C. Mu and R. S. Bird. In 2nd Asian Workshop on Programming Languages and Systems , KAIST, Dajeaon, Korea, December 17-18, 2001.
[GZipped Postscript]

It has been shown that non-determinism, both angelic and demonic, can be encoded in a functional language in different representation of sets. In this paper we see quantum programming as a special kind of non-deterministic programming where negative probabilities are allowed. The point is demonstrated by coding two simple quantum algorithms in Haskell. A monadic style of quantum programming is also proposed. Programs are written in an imperative style but the programmer is encouraged to think in terms of values rather than quantum registers.

On building trees with minimum height, relationally

S-C. Mu and R. S. Bird. In First Asian Workshop on Programming Languages and Systems, Singapore, December 2000.
[GZipped Postscript]

The algebraic style of reasoning about programs has been proposed and studied by computing scientists. We rephrase the old problem of building trees of minimum height as an optimisation problem and apply the greedy theorem to derive a linear time algorithm. To put the problem in the right form, we find it necessary to generalise from functions to relations and make use of the converse of a function theorem to write the inverse of a function as a fold.

Optimisation problems in logic programming: an algebraic approach

S. Seres and S-C. Mu. In Proceedings of LPSE’00, July 2000.
[GZipped Postscript]

Declarative programming, with its mathematical underpinning, was aimed to simplify rigorous reasoning about programs. For functional programs, an algebraic calculus of relations has previously been applied to optimisation problems to derive efficient greedy or dynamic programs from the corresponding inefficient but obviously correct specifications. Here we argue that this approach is natural also in the logic programming setting.

Out-of-core functional programming with type-based primitives

T-R. Chuang and S-C. Mu,. In 2nd International Workshop on Practical Aspects of Declarative Languages, January 2000.
[GZipped Postscript]

We formulate and experiment with type-based primitives (such as fold and unfold operations) for out-of-core processing of functional data structures. We follow the view that recursive data types are fixed points of polynomial type constructors. This view leads to a clear separation of the semantics and the implementations of recursive data types. We provide monadic implementations of the type-based primitives so that the intermediate data structures used for the executions of the primitives can be placed in out-of-core storage. The parametric module facility of Objective Caml is further used to package the out-of-core implementations. The resulting out-of-core user code retains the same program structure of the in-core user code and can be as elegant.