Mathematical Informatics
Graduate School of Information Science and Technology
Tokyo University
7-3-1, Hongo, Bunkyo, Tokyo 113-8656, JAPAN

scm@ipl.t.u-tokyo.ac.jp

As of June 2003 I have started working as a postdoc in the Programmable Structured Document group in Information Processing Lab, University of Tokyo.

Before that I was a graduate student in the Algebra of Programming group in Oxford University, working with Prof. Richard Bird.

My main interest concerns algebraic and relational approach to program derivation. More specific research topics include:

• The converse-of-a-function theorem. Many problems can be specified as the inverse of some well-known function. The converse-of-a-function theorem, originally proposed by Oege, describes how to construct the inverse of a function as a fold. We need more experience to deal with the calculations involved and are keen to see more of its applications.
• Program inversion in general. We are seeking possibility to exploit program inversion techniques for XML editing and processing.
• The greedy and the thinning theorems. Many optimisation problems can be solved using a thinning strategy and they often yield beautiful algorithms. I worked on a generalisation of the greedy and the thinning theorems to folds with mutually defined algebras.
• The inverse Burrows-Wheeler transform . Richard and I found a calculational proof of the inverse Burrows-Wheeler transform. Surprisingly, higher-order naturality plays an essential role.
• Anything about program derivation. Show me an algorithm and I will give you a calculational proof! :)

Programs I wrote, alll of them toy programs accompanying my papers.

• Countdown: programs and profiling results accompanying the paper Countdown: a case study in origami programming.
  [Gzipped Tarball]
• Inv: The injective language Inv, together with the language X, the XEditor, and the HaXml embedding.
  [Gzipped Tarball]

Some tips for my own use:

• A simple script checking the maximum and current capacity of the battery on an iBook.
• A Haskell quine. That is, a program whose output is itself. To deal with string quoting, it is difficult to write a quine not assuming a particular encoding (e.g. ASCII). In Haskell, however, it is side-stepped by using the built-in show function for strings. See also the quine page.

  Functional programmers would notice that such programs resembles the lambda expression (\x -> x x) (\x -> x x), which reduces to itself. As a simple extension, this self-expanding program inserts to itself one line of empty comment each time it is run. It resembles the Y combinator.

  Yokoyama later came up with a more elegant quine

• Do you know that the S combinator is injective? I have a simple algebraic proof and Nakano actually constructed its inverse.

Titles and abstracts of my papers:

• Z. Hu, S-C. Mu and M. Takeichi, A programmable editor for developing structured documents based on bidirectional transformations. Submitted to Higher-Order and Symbolic Computation.
  [Abstract][PDF]
• S-C. Mu, Z. Hu and M. Takeichi, Bidirecionalising HaXML. Submitted to International Conference on Functional Programming '05.
  [Abstract][PDF]
• R. S. Bird and S-C. Mu, Countdown: a case study in origami programming. Submitted to Journal of Functional Programming.
  [Abstract][GZipped Postscript]
• S-C. Mu, Z. Hu and M. Takeichi, A language for bidirectional updating based on injective mapping. Unpublished.
  [Abstract][PDF]
• R. S. Bird and S-C. Mu, Inverting the Burrows-Wheeler transform. Journal of Functional Programming Vol. 14(6) Special Issue on Functional Pearls, pp. 603-612, Novermber 2004.
  [Abstract][GZipped Postscript]
• S-C. Mu, Z. Hu and M. Takeichi, An algebraic approach to bidirectional updating. In The Second Asian Symposium on Programming Language and Systems, pp. 2-18. November 2004.
  [Abstract][PDF]
• Z. Hu, S-C. Mu and M. Takeichi, A programmable editor for developing structured documents based on bidirectional transformations. In Partial Evaluation and Semantics-Based Program Manipulation, pp. 178-189. August 2004.
  [Abstract][PDF]
• S-C. Mu, Z. Hu and M. Takeichi, An injective language for reversible computation. In Mathematics of Program Construction 2004, LNCS 3125, pp. 289-313, July 2004.
  [Abstract][PDF]
• S-C. Mu and R. S. Bird, Theory and applications of inverting functions as folds. In Science of Computer Programming Vol. 51 Special Issue for Mathematics of Program Construction 2002, pp. 87-116, 2003.
  [Abstract][GZipped Postscript]
• S-C. Mu and R. S. Bird, Rebuilding a tree from its traversals: a case study of program inversion. In The First Asian Symposium on Programming Languages and Systems, LNCS 2895, pp. 265-282, Bejing, 2003.
  [Abstract][GZipped Postscript]
• S-C. Mu, A Calculational Approach to Program Inversion. D.Phil Thesis. Oxford University Computing Laboratory. March 2003
  [Abstract][GZipped Postscript][PDF]
• S-C. Mu and R. S. Bird, Inverting functions as folds. In Sixth International Conference on Mathematics of Program Construction, Dagstuhl, Germany, July 2002
  [Abstract][GZipped Postscript]
• R. S. Bird, J. Gibbons and S-C. Mu, Algebraic methods for optimisation problems. In Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, LNCS 2297, pp. 281-307, January 2002.
  [PDF]
• S-C. Mu and R. S. Bird, Quantum functional programming. In 2nd Asian Workshop on Programming Languages and Systems , KAIST, Dajeaon, Korea, December 17-18, 2001.
  [Abstract][GZipped Postscript]
• R. S. Bird and S-C. Mu, Inverting the Burrows-Wheeler Transform. In ACM SIGPLAN 2001 Haskell Workshop, Firenze, Italy, September 2001.
  Superseded by the extended version for Journal of Functional Programming.
  
• S-C. Mu and R. S. Bird, On building trees with minimum height, relationally. In First Asian Workshop on Programming Languages and Systems, Singapore, December 2000.
  [GZipped Postscript]
• S-C. Mu, Algebraic Methods for Optimisation Problems. Transfering dissertation.
  
• S. Seres and S-C. Mu, Optimisation problems in logic programming: an algebraic approach. In Proceedings of LPSE'00, July 2000.
  [GZipped Postscript]
• T-R. Chuang and S-C. Mu, Out-of-core functional programming with type-based primitives. In 2nd International Workshop on Practical Aspects of Declarative Languages, January 2000.
  [GZipped Postscript]

Part of this site was generated using CDuce.
Last update: 05/09/05