Sunday, February 10, 2013

Porting Haskell's Finite Domain Solver to Frege

On learning Haskell/Frege, I thought I would try to write a Sudoku Solver as an exercise in Frege. I was interested in Knuth's Dancing Links approach which I did in Java but found out that it is not that easy or Haskell's way of doing. Instead I found this excellent blogpost Constraint Programming in Haskell.

I learnt a lot from reading that code. So I thought, instead of trying a solver from scratch, why not port(read it as copy-paste :)) this to Frege? I have ported some Java classes to Frege but never attempted a Haskell library to Frege. This is my first attempt at that and it works great!

First, the Sudoku Solver module which is an application of the finite domain solver, explained here in another post A Haskell Sudoku Solver using Finite Domain Constraints:

This is almost the same as Haskell. There are two changes though from the Haskell version:
  1. Line 7 in Haskell: sudoku puzzle = runFD $ do but in Frege, it results in compilation error (not sure, why Frege parses it different).
  2. Line 10: the lambda parameters in Haskell: \x n -> ... whereas in Frege, each parameter must be preceded by '\' hence it will be \x \n.
Apart from this, main has the type [String] -> IO ()

Next, the main module FD in Frege:

The main problem porting this module from Haskell to Frege is the missing IntSet, StateT, MonadState, MonadTrans in the standard library. So the lines from 150-208 are copy-pastes from Haskell library with few changes (apart from the syntax changes mentioned for the Sudoku module above):
  1. MonadState in Haskell introduces Functional Dependency which Frege doesn't support yet. So I just specialized all the functions involving MonadState to (FD s) (lines 169, 207,208)
  2. In instance declarations, the constraints come after the class name (line 154, for example)
  3. newtype in Haskell is just regular type in Frege where the constructor has only one field (StateT declaration at line 152, for example)
  4. Haskell derives instances automatically for 'newtype's but Frege derives instances only for Eq, Ord, Enum, Bounded and Show. So we have to manually derive Monad, MonadPlus for the (FD s) in the above module. But in this module, even for Eq, Ord, I had to manually derive because the constraints were generated even for the phantom type variable in FD while deriving automatically.
  5. Unlike in Haskell, the field names for records are not global-scoped in Frege. So while referencing, the field names must be prefixed with either type name or with the record instance itself. Example:
    line 35 for prefixing with record type: FDState.varSupply s
    line 36 for prefixing with record variable itself: v.unFDVar

  6. In this module, I have added all missing types/classes/instances (StateT,MonadTrans) except IntSet which is really huge. So I created that module in a seperate source file from Haskell source. In that module, I had to remove all preprocessor directives and I replaced .&. and .|. (bitwise 'and/or') with 'band' and 'bor' in Frege and 'shiftRL', 'shiftLL' with 'bshr', 'bshl'.
It seems it is not that difficult to port Haskell to Frege, atleast for this library. In fact, It is a lot easier to port from Haskell to Frege than creating native interface from Java to Frege.

For complete source code:

Sunday, July 15, 2012

A Frege Servlet

I was playing around with Frege to create a small Servlet. There is no web framework for Frege available yet so it is going to be mostly interfacing with native Java classes. Here is the code snippet in Frege.

First, we need to create native declarations in Frege for the Java classes and methods that we are interested in. For this example, we will be defining data types for HttpServletRequest, HttpServletResponse, HttpServlet classes and an implementation for Servlet's doGet method.

In HttpServletRequest class, we will be encoding getParameter method. The type signature for that method,

Since this method could return null in case of missing parameters from the request, the return type is Maybe String. Frege automatically handles null if the return type is "Maybe".

Now let us declare a getWriter function to it's native counterpart in HttpServletResponse class.

Since HttpServletResponse.getWriter method can throw IOException and since it is not a pure method, the return type is IO (Exception PrintWriter).

The definitions for ServletContext and HttpServlet are not of much interest since we are not going to use any of the methods from those classes for this example.

The definition of doGet function is where we are actually writing to response. From the signature of the function, it takes a servlet, a request and a response instance and returns IO () since it is a side-effect function which doesn't return any value. Another important point is that the parameter names are prefixed by bang character which makes the parameters strict which would otherwise be all lazy since Frege is by default lazy.

The last missing piece is how do we specify a servlet class in web.xml? I don't really know yet in Frege how to create a named class that extends a Java class. So I created the servlet in Scala which will forward the request to our doGet function defined in Frege.

Here FregeServlet.doGet(this, request, response) calls the doGet function defined in FregeServlet module and returns an IO lambda. Then we call that IO action by passing an arbitrary integer representing the real world. Here the Scala's support for 'apply' method is helpful.
FregeServlet.doGet(this, request, response)(realWorld)
is actually
FregeServlet.doGet(this, request, response).apply(realWorld)
where the doGet function defined in Frege module returns frege.rt.Lambda which has an apply method. The final method call _e is to evaluate the lazy value which is where the IO action is actually executed and our response is sent to the client. We can add this class as servlet in web.xml and point to the servlet URL to see the Frege/Scala servlet in action.

Saturday, March 3, 2012

Brush your code!

Lately I have been playing around with SyntaxHighlighter to highlight code syntax on my blog for the new programming language, Frege. Here are some simple steps on that process which would be useful for anyone wanting to create new/enable SyntaxHighlighter.

1) Copy and paste the following just before '</head>'in the blog template

You don't need to include all the 'shBrushxxx.js' scripts. Just include the brushes you need for your blogs. The scripts in the format are inbuilt brushes. The last "<script>" is the one I created for the language 'Frege'. Yon can refer this guide on creating new brushes:

2) After step 1 (You have included all the css and scripts for brushes), you can use it in your blogs like this ('Edit html' for your blog), or You can use "script" method: The difference is that when you use "script", your contents will be automatically html-escaped whereas in "pre" method, you need to escape those special characters.

3) If you want to customize some styles, you can add it before "]]></skin>" like this, The last style "syntaxhighlighter" is to disable scrollbars in chrome which adds scrollbars even when there is nothing to scroll. IE and firefox correctly render without scrollbars.
Thats all you need to enable SyntaxHighlighter for your blog.

Wednesday, February 29, 2012

Hello World Frege!

Ever since I started learning Scala, the whole functional programming thing is absolutely fascinating to me. As "Scala is a gateway drug to Haskell",  then I was attracted by Haskell's gravity. Haskell changed the way I think about programs and made me enjoy programming more than ever. While learning Haskell, as a Java programmer, I used to think how good would it be to code Haskell in the ubiquitous JVM and then I found this language, Frege more interesting for JVM and Haskell-like.

As I am practicing Frege along with Haskell and Frege is still relatively new, I thought it would be a good idea to share my experience with Frege.

Getting started:

FregIDE Eclipse plugin is still at basic level but is really usable and a good way to start with Frege. The plugin installation details can be found here: Frege requires JRE 7 so even after following the instructions on the page, if you still do not see Frege Builder/Preferences enabled in Eclipse, try starting your Eclipse with "-vm" argument pointing to your JRE 7. Now, the "Hello World"
module Main where
main _ = println "Hello World"

Yes, I know that is not much interesting. How about implementing a function from Haskell?
In Haskell, there is a function "getLine" which reads a line from standard input. Now lets implement that function in Frege using Java's IO classes.

Haskell's 'getLine' using Java's methods:
import frege.IO

--Reads a line from standard input device
getLine :: IO String
getLine = do
  isin  <- stdin
  isrin <- isin
  brin  <- IO.BufferedReader.fromISR isrin
  line <- brin.readLine
  return $ fromExceptionMaybe line

fromExceptionMaybe :: Exception (Maybe a) -> a
fromExceptionMaybe (Right (Just r)) = r
fromExceptionMaybe (Right _) = error "get on Nothing"
fromExceptionMaybe (Left l) = error l.getMessage

--Native reference to Java's parseInt
pure native parseInt java.lang.Integer.parseInt :: String -> Int

main _ = do
  line <- getLine
  println $ parseInt line

Here as you can see, we have defined 'getLine' using Java's Classes, InputStreamReader, BufferedReader, Exception along with Haskell goodies Maybe and Either (through Exception). The parseInt function is declared with native reference to Java's 'parseInt' method from 'Integer' class and since it is a pure method, the types are straight-forward otherwise we would be using ST monad for those native declarations.

Happy Haskelling on JVM!