MagicHaskeller: A Search-based Inductive Functional Programming System

Susumu Katayama, University of Miyazaki
ܸ(Japanese)

MagicHaskeller on the Web

\f ->

Overview

See publications at my top page:) Also, here is my presentation used at the 25th ToPS seminar (held at IPL, University of Tokyo). (NB: this presentation is rather old, and lacks in survey on recent progress in the extended Summers-like approach.)
The name is abbreviation of "automagic Haskell programmer", but it may not be adequate because currently it supports just a subset of Haskell, notably without type classes.
Since May 2006 It has two forms: stand alone program including a cheap interpreter, and new library package which is supposed to be used with some recent versions of Glasgow Haskell Compiler interactive (GHCi) (because it uses Template Haskell).

What's new

Jan. 9, 2013 Version 0.9.1 is released as a library (in addition to the web service). The same version is used as the backend server of the current web service, so please check it out if you are interested in its source files and/or if you want to make a new service.
May 23, 2012 As you have already seen, the first alpha version of the web interface is out! Please let me know (instead of exploiting it) if you ever found a security hole....
Mar. 2, 2012 Version 0.8.6.3 fixes a bug in MagicHaskeller.ProgGenSF, which is used by MagicHaskeller.LibTH.exploit. (Well..., actually..., the bug caused segmentation fault!)
Dec. 18, 2011 Version 0.8.6.2 fixes some bugs in the analytical modules. Also, MagicHaskeller.LibTH.exploit is more useful and interesting now. Try something like
Prelude MagicHaskeller.LibTH> exploit $ \f -> f "abc" == "abcba"
Dec. 13, 2011 NOTICE: module MagicHaskeller.RunAnalytical is supposed to be run under GHCi, and it does not work in the a.out form. Also, it is only tested on Linux, and does not work with Windows.
Apr. 27, 2011 Version 0.8.6.1 fixes a bug related to dealing with background knowledge when doing analytical generate-and-test. Also added some additional functions.
Apr. 8, 2011 Version 0.8.6 includes some new modules for analytical synthesis. See MagicHaskeller-RunAnalytical.html.
Nov. 28, 2009 Version 0.8.5-1 fixes some minor problems, and user-defined datatypes have become usable again even with recent compiler versions.
July 14, 2009 Version 0.8.5.
June 10, 2008 Version 0.8.4 enables some options to fine tune program generation. Also I mined some old optimizations used until 0.7.5 --- see the library documentation.
Apr. 11, 2008 Version 0.8.3-1 (hopefully) fixes a bug in package dependency.
Apr. 7, 2008 Version 0.8.3 is out.
Sep. 3, 2007 Version 0.8.2 is out. The full changelog (generated by darcs changes) since May 2006 is here.

Download

The newest package is registered to the Hackage DB, so if you have the cabal command,
cabal install MagicHaskeller
should work, though you may want to specify --flags=GHCAPI for the full installation. However, if it fails, try unpacking and then installing the package, namely,
cabal unpack MagicHaskeller-0.8.6.3
cd MagicHaskeller-0.8.6.3
cabal install

Source distribution

Since Version 0.8.5 I have decided to make its source available (in the BSD3 style license).
source tarball for Version 0.9.1
Recently I noticed that my office will never be finished cleaning up. Neither will my source. So the source is released almost as is, with some unnecessary comments, maybe in Japanese.

Binary distributions

NB: because I think this tool is still experimental, the older library distributions that are released in the binary form will be installed onto the current directory by default. Therefore, while you are out of the directory your copy of the library will not work.

Linux i686

Linux EM64T (known to work on RHEL4)

I do not know who wants this release, but I have such a box at hand.

Windows (known to work on XP)

Also download the sample component library for the stand alone program, or that for the library package.

How to Play

Source tarball

The standard method for installation should work, i.e.,
tar xvfz MagicHaskeller-0.8.6.1.tar.gz
cd MagicHaskeller-0.8.6.1
runhaskell Setup.hs configure --user
runhaskell Setup.hs haddock
runhaskell Setup.hs build
runhaskell Setup.hs install
(Instead of typing the four lines starting with runhaskell, you can just say
cabal install
if you have the cabal command.)
And now you have package MagicHaskeller-0.8.6.1 available. Leave the directory and type
ghci -fth -package MagicHaskeller
to launch ghci and try the following (or whatever you think of):

:m +MagicHaskeller.LibTH
initialize
printAll $ \f -> f "abc" == "aabbcc"
exploit $ \f -> f "abc" == "aabbcc" -- This uses a richer library, and thus the resulting programs are more readable.
-- The following will find the recursive form definition of the fibonacci function from its closed-form solution.
init075 -- The problem is tough, so you should be prepared to resort whatever measure you can take!
printAll $ \f -> all (\n -> (f :: Int->Int) n == let phi = (1 + sqrt 5)/2 in round ((phi^n - (1-phi)^n) / sqrt 5) ) [0..9]
-- You may also try analytically-generate-and-test synthesis, if you are using GHC 6.10.* or 6.12.*.
:m MagicHaskeller.RunAnalytical
quickStart [d| f [] = []; f [a] = [a,a] |] noBKQ $ \f -> f "abc" == "aabbcc"

Also, you may want to see the haddock-generated documentation (but the export list is subject to change).
With the library distributions user-defined types can be used. TryTreeExample.hs as an example. Also, this paper may be interesting, although it describes a little older version.
(Actually, if the type of everything, etc. uses type constructors which never appear in the primitive component set, that can cause an error. This is a fixable bug, but please wait until I fix it.)

Library package

Make sure you have either GHC 6.8.2 or GHC 6.6.1 installed. Try the following:

mkdir foo
cd foo
wget http://nautilus.cs.miyazaki-u.ac.jp/~skata/magichaskeller(version)-ghc(ghc version).tgz # pick up a filename from above links
wget http://nautilus.cs.miyazaki-u.ac.jp/~skata/LibTH.hs
tar xvzf magichaskeller(blah).tgz
./register.sh
ghc --make -O -fth -package MagicHaskeller -fglasgow-exts LibTH.hs
ghci -fth -package MagicHaskeller -fglasgow-exts LibTH.hs


(Or alternatively, download, edit, and execute either Quickstart.sh (for Linux) or Quickstart.bat (for Windows) for the same effect. You may still want to execute the ghc and ghci lines by hand on Windows.)
Then, in GHCi try the following (or whatever you think of):

initialize
printAny (\f -> f "abc" == "aabbcc")
-- The following will find the recursive form definition of the fibonacci function from its closed-form solution.
init075 -- The problem is tough, so you should be prepared to resort whatever measure you can take!
printAny (\f -> all (\n -> (f :: Int->Int) n == let phi = (1 + sqrt 5)/2 in round ((phi^n - (1-phi)^n) / sqrt 5) ) [0..9])

Also, you may want to see the haddock-generated documentation (but the export list is subject to change).
With the library distributions user-defined types can be used. TryTreeExample.hs as an example. Also, this paper may be interesting, although it describes a little older version.
(Actually, if the type of everything, etc. uses type constructors which never appear in the primitive component set, that can cause an error. This is a fixable bug, but please wait until I fix it.)
After having fun for a while, you can unregister it by
./unregister.sh
before leaving the directory.

Stand alone program

Download the executable and the sample component library. Invoke the executable and type in a predicate (a function returning Bool), e.g.
\f -> f "abc" == "abccba"
The system infers its type and searches for an expression that satisfies the predicate. In the above case it should print
(\ a -> list_para a (\ b -> b) (\ b c d e -> cons b (d (cons b e))) nil)
This is a valid Haskell expression, and so you can use it within a Haskell interpreter after loading the component library. For example, if the Hugs interpreter is installed in your computer, by typing
hugs LibDeb.hs
(\ a -> list_para a (\ b -> b) (\ b c d e -> cons b (d (cons b e))) nil) "abcd"

in your shell, you get
"abcddcba"
(Actually there is no need to run an external interpreter since 0.7.1.) In the above case the request type is inferred, and thus is a monomorphic type. If you like to limit the search to a more polymorphic type, you can provide the type, like
\f -> f "abc" == "abccba" ;; [a] -> [a]
(Note the semicolons. You know the actual type of the predicate we want is ([a]->[a])->Bool)

Tips

Commands in the stand alone program

Limitations

Limitations in the interpreter of the stand alone program

There are a lot of limitations in the interpreter, some of which can be guessed from the sample component library.