Saturday, October 25, 2014

Do it bottom up in the REPL!

Today I stumbled over a question on StackOverflow, where a poster faced difficulties with some homework. The task was to compute pi with the approximation

pi = 3.0 + 4 / (2*3*4) - 4 / (4*5*6) + 4 / (6*7*8) - ...
and he was getting nonsesical results. It followed 35 lines of Java code (not counting empty lines) and the request for help "because it must be submitted on tuesday".

Doing it the conventional way

It occured to me that Java lures beginners into writing some monolithical main method, and when it doesn't work, debugging begins.

Debugging is in some sense the dual to programming: in imperative programming, we assemble expressions and statements to a whole, the glue is, of course, mutable state. And the debugger is a tool to help you to do the reverse: you split that whole to be able to look at individual statements and expressions.

Doing it the functional way

But how if we could spare us this assembling and disassembling, and instead do it right from the start? This is, of course, not a new idea, and is well known by the name "bottom up". I am, for my part, strongly convinced that this is how to think when working in functional languages.

In praise of the REPL

For this, we need another tool, namely an interpreter, also called REPL (for read-eval-print-loop). As if to underline my theory, there is no REPL in Java (or, at least, it is very uncommon to use one), Frege has no debugger at all, whereas in Haskell, ironically, setting breakpoints is a feature of the interpreter ghci.

Ask a person whose favorite language you don't know to choose two out of compiler, interpreter and debugger. If the answer is "compiler and debugger" you can safely bet on C++, Java or C. If, however, the debugger is the least important tool, you found a functional or declarative programmer.

In the following, I'll work through the example using the Frege REPL, in the hope to show some reader with an imperative mindset how to "go about it" in a functional way. 

Going to the bottom

But before we can go "bottom up", we need to go "top down" mentally. At first, one needs to see that we have to compute a sum whose terms have a nice pattern (except the leading 3.0, of course). The key point is the smallest number in the products that serve to divide 4. Hence, we obviously need the positive even numbers, since the whole thing is based on them.

Going bottom up

We couldn't go deeper anymore for the moment, because we can write this directly in Frege:

frege> [2,4..]
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56

Thanks to foresight of the REPL author, Marimuthu Madasamy, the REPL will print only an initial part of an infinite list, so we won't get kicked out at this point!
Now that we have that list of integers, it is time to remember that we will need floating point numbers instead, because Frege won't let us mix integers and reals in numerical computations. Nothing easier than that! Get back that previous line and change it accordingly:

frege> map Int.double [2,4..]
[2.0,4.0,6.0,8.0,10.0,12.0,14.0,16.0,18.0,20.0,22.0,24.0,26.0,28.0,30.0,32.0,34.

In principle, we could proceed in this way and modify the last expression further and further, until we arrive at the solution. It is, however, recommended to name important sub-solutions. I usually do this when the expression gets too complex, makes sense on its own or if it is a list I do not want to get recomputed always.

frege> evens = map Int.double [2,4..]
value evens :: [Double]

The friendly type checker ensures us that we have a list of Doubles, as was our intention.
Time to write the code for the terms of the sum:

frege> [ 4 / n*(n+1)*(n+2) | n <- evens ]
[24.0,30.0,37.33333333333333,45.0,52.800000000000004,60.666666666666664,68.57142

Surprise! This result is surely not what we want, as the terms should get smaller and smaller instead of bigger and bigger!
It turns out that the whole product should be in the divisor, not just the first term, so we just forgot a pair of parentheses.

But note how such an error would escape us in a compile-only setting until runtime. The bottom up method already pays off!

frege> [ 4 / (n*(n+1)*(n+2)) | n <- evens ]
[0.16666666666666666,0.03333333333333333,0.011904761904761904,0.0055555555555555

Doesn't this look much better?
Now, we know that every second terms needs to be negative. If we only could apply negate to every other term! But wait, we can, of course:

frege> deltas = zipWith ($) (cycle [id,negate]) [4 / (n*(n+1)*(n+2)) | n <- evens]
value deltas :: [Double]

And this is it, essentially! We can now directly write a function that gives us pi, approximated with so many terms:


frege> p n = 3.0 + sum (take n deltas)
function p :: Int -> Double
frege> map p [0..10]
[3.0,3.1666666666666665,3.1333333333333333,3.145238095238095,3.1396825396825396,
frege> map p [20..40]
[3.1415657346585473,3.1416160719181865,3.1415721544829647,3.1416106990404735,3.1
frege> map p [1000]
[3.1415926533405423]
frege> map p [10000]
[3.1415926535895418]
frege> import Prelude.Floating
frege> Double.pi
3.141592653589793
frege> Double.pi - p 10000
2.5135449277513544E-13

Why wait until tuesday? We can submit monday.

Wednesday, August 14, 2013

Talk at Karlsruhe Functional Programmers Meetup

I gave an introduction to Frege on a meeting of functional programmers in Karlsruhe.

Very knowledgeable people, I am afraid it was a bit boring for some of them when I explained basic concepts of type inference and so on.

However, when I did some examples in the IDE, they seemed a bit impressed and there were some good discussions and questions.

The slides for the talk can be downloaded here (PDF).

Thursday, March 7, 2013

Adding Concurrency to Frege (part III)

In the second part of this series, we implemented MVars and noted some differences in the concurrency support of Haskell and Frege.

In this third and last part, we turn to another example taken from chapter 5 of Simon Marlows upcoming book on parallelism and concurrency in Haskell and conclude with a discussion of the lessons learned.

Overlapping IO without error handling

The following program loads two websites concurrently and prints their sizes:

main _ =  do
    m1 <- MVar.newEmpty
    m2 <- MVar.newEmpty
    
    forkIO do
        r <- getURL "http://www.wikipedia.org/wiki/Shovel"
        m1.put r
    
    forkIO do
        r <- getURL "http://www.wikipedia.org/wiki/Spade"
        m2.put r
    
    r1 <- m1.take
    r2 <- m2.take
    println (sum (map length r1), sum (map length r2))

The output will be:

(80278, 66924)

This is, however, sure to produce deadlock whenever, for some reason, one of the threads cannot complete to the point where it writes the result to its MVar - or, in other words, if the getURL action throws exceptions. We need not go into the details of the implementation of getURL, suffice it to say that it is a composition of several native methods that each can throw exceptions for a variety of reasons: bad URL syntax, IO error, network failure, and so on. For example, if we change the protocol in the second URL to htto (simulating a typo, where someone typed 'o' instead of 'p'), the output will look like:

Exception in thread "Thread-1" frege.runtime.WrappedCheckedException:
        at frege.runtime.WrappedCheckedException.wrapIfNeeded(WrappedCh
        ...
Caused by: java.net.MalformedURLException: unknown protocol: htto

In this case, the main thread will forever block in the attempt to get the result of the second thread.

Overlapping IO with error handling


To correct this issue, we can follow the approaches Simon Marlow explains in his book. Remember though, that exceptions in Frege are based on Java exceptions. Introducing new exceptions is not yet possible in Frege. Instead, one simply introduces appropriate Java classes that are subclasses of java.lang.Throwable. However, exceptions thrown from native methods are usually already implemented, and so is the "catch all" type Throwable. Hence all we need to make the examples work is the following:

type SomeException = Throwable

try :: IO a -> IO (SomeException|a)
try action = action >>= return . Right
        `catch` any
    where
        any :: SomeException -> IO (SomeException|a)
        any = return . Left 

To show this in action without using the more elaborate and better abstracted approaches of Simon Marlow, here is a non-deadlocking version of the program above:

main _ =  do
    m1 <- MVar.newEmpty
    m2 <- MVar.newEmpty
    
    forkIO do
        r <- (try . getURL) "http://www.wikipedia.org/wiki/Shovel"
        m1.put r
    
    forkIO do
        r <- (try . getURL) "htto://www.wikipedia.org/wiki/Spade"
        m2.put r
    
    r1 <- m1.take
    r2 <- m2.take
    println (result r1, result r2)
  where
    result :: (SomeException|[String]) -> String
    result (Left x)  = x.getClass.getName
    result (Right y) = (show . sum . map length)  y


When we run this, it produces the following output:

("80278", "java.net.MalformedURLException")


Not very nice, but it does now terminate despite of errors.

Lessons learned

It turns out that it was easy to add concurrency to Frege, thanks to the concurrency support that comes with Java and the JVM and the ability of Frege to make use of those feature in a seamless way.

It was even easy to do this in such a way that Haskell programmers would feel comfortable, by approximating the abstractions they are used to: forkIO, MVars, exceptions, etc. to such an extend that porting Haskell code via copy/paste was possible.

But we also observed important differences in the respective run time concurrency support:
  • Termination of the main thread does not terminate any other thread in the JVM.
  • MVars as implemented here are strict.
  • The JVM does not detect deadlocks.
But there is more, and it could not be easily ignored:
  • The forkIO we implemented in Frege is really what Haskell knows as forkOS, as genuine OS threads are forked, as opposed to Haskell's lightweight "green" threads. The Java concurrency API has nothing comparable to the latter, as far as I know. One could probably use thread pools, executor services and asynchronous tasks to achieve something like it, but there remains a basic difference: if an asynchronous task performs a blocking action like reading from a MVar, it will block the OS thread it is running on. Hence, in the Frege/Java/JVM concurrency model, a fixed number of OS threads cannot - on principle - support an arbitrary number of asynchronous tasks that may potentially block.
  • In the JVM, there is no way to throw an asynchronous exception in another thread. The only possibility is to interrupt another thread, which the other thread may or may not honor. But, if one interrupts a thread that is in a blocking operation, that operation will throw an InterruptedException.
  • In the JVM world, there is - to my knowledge - no support for software transactional memory (STM) out of the box, one would need to implement this manually and it would probably not be easy.
  • ...
The conclusion is, unfortunately, that one could not get very far in Frege if one only knows the Haskell concurrency model. To do serious concurrent work  in an JVM environment is different and it will thus require different knowledge. One way to obtain this knowledge would be to read books like "Java Concurrency in Practice".

Sunday, March 3, 2013

Adding Concurrency to Frege (part II)

In the first part we demonstrated how to implement the important forkIO operation. You can now implement the remaining simple examples Simon Marlow gives us in chapter 4 of his upcoming book. They  deal with threads that need not communicate with each other or with the main program.

Whenever we need some additional primitive operation, we look up the Java API if similar functionality is available, and add appropriate native definitions and perhaps some glue code to adapt the interface. For example, in the "reminders" example, Simon introduces an operation "that waits for some time to elapse"

--| do nothing for some microseconds
threadDelay    :: Int -> IO ()

What we have in Java is a similar function we can make usable in Frege through:

--- let the current thread sleep for some milliseconds
native sleep   java.lang.Thread.sleep
               :: Long   -> IO () throws InterruptedException

and then use it to implement the Haskell interface, that differs in the type of the argument and, very important, in that it interprets its argument as microseconds, whereas the Java API doesn't allow us such fine grained naps, and thinks it is better for our health to sleep in amounts of milliseconds.

--- convert microseconds to milliseconds, and Int to Long
threadDelay   :: Int -> IO ()
threadDelay n =  sleep ((n.long + 500L) `div` 1000L)  -- give or take some 

However, despite the many similarities and easy adoption of Haskell stuff,
it is important to keep in mind that there are differences that are not that
easy to bridge. For example, as Simon demonstrates us, the Haskell run time system terminates all threads as soon as the main program ends. This is not so in Java (whose run time system we are using in Frege), where all (non deamon) threads are born equal, and the JVM won't exit until all of them are finished. It is possible to simulate the Haskell runtime behaviour by running

System.exit 0

instead of

return ()

in the main function. This will exit the JVM and all still running threads.

Implementing MVars

A MVar is a data structure that serves as basic communication mechanism between threads in Concurrent Haskell. It is like a box that can be empty or full. Trying to take something from an empty box as well as trying to put something into a full box will cause the corresponding thread to block, until some other thread puts or takes something there.

In Java, we don't have anything like that, but we have blocking queues in the java.util.concurrent package, and we can make blocking queues with limited capacity. One way of implementing MVars would thus be to regard them as degenerated blocking queues with a maximum capacity of 1. We first "import" the interface java.util.concurrent.BlockingQueue with the operations we are interested in to Frege:

data BlockingQueue e = mutable native java.util.concurrent.BlockingQueue where
    --- add element to blocking queue, return false if not possible
    native offer    :: BlockingQueue e -> e -> IO Bool
    --- add element to blocking queue, block until possible
    native put      :: BlockingQueue e -> e -> IO () throws InterruptedException
    
    --- get and remove element from blocking queue, return null if it is empty
    native poll     :: BlockingQueue e -> IO (Maybe e)
    --- get and remove element from blocking queue, block until something is available
    native take     :: BlockingQueue e -> IO e throws InterruptedException

Because this is an interface and not a class, we do not have a constructor that allows us to actually create a blocking queue. For this we need to import a class that actually implements the interface, like:

data ArrayBlockingQueue e = mutable native java.util.concurrent.ArrayBlockingQueue where
    --- make a blocking queue with the given maximum capacity
    native new      :: Int -> IO (ArrayBlockingQueue e)

As a side note: while the Frege compiler does not explore the available Java classes and interfaces on its own, it automatically knows the relations between Java classes and Java interfaces we introduced through native data declarations and it applies this knowledge during type checking. It will thus be possible to pass a value of type ArrayBlockingQueue e when BlockingQueue e is expected (but not the other way around). This greatly simplifies and reduces the native boilerplate code we have to write.

The implementation of MVar is now straightforward:

abstract data MVar a = MV (BlockingQueue a) where
    newEmpty        = ArrayBlockingQueue.new 1 >>= return . MV
    new a           = do m <- newEmpty; m.put a; return m
    put   (MV q) a  = q.put a         
    take  (MV q)    = q.take
    offer (MV q) a  = q.offer a
    poll  (MV q)    = q.poll  

The abstract keyword basically makes the MV value constructor inaccessible, except for the code that lives in the MVar namespace. For this reason, we give the basic MVar operations in the where clause of the data definition. Note that a data definition with a single constructor that has a single field is equivalent to a Haskell newtype definition - there will be no runtime overhead.

The only ways to create MVars are MVar.newEmpty and MVar.new, which uses the former. In newEmpty, the capacity of the underlying blocking queue is limited to 1 element, thus giving us the desired functionality.

It is worth mentioning a big difference to Haskell's MVars: the values put into them will be evaluated to weak head normal form in the process of doing so. This is because the MVar operations are written in terms of native functions and arguments to native functions must all be strict.

We can give the following definitions, if only to make it easier to copy/paste Simons examples:

-- Haskell compatibility
newEmptyMVar    = MVar.newEmpty
newMVar         = MVar.new 
tryTakeMVar     = MVar.poll
tryPutMVar      = MVar.offer
takeMVar        = MVar.take
putMVar         = MVar.put 

Let's check if it works, and at the same time show the dangers that come with MVars:

main _ = do
    m <- newEmptyMVar
    m.take  -- or, if you like: takeMVar m

Here we find another difference between the Haskell and the Java runtime regarding concurrency: The Haskell runtime detects the deadlock, i.e., it notices that there is no other thread that could possibly put something into m and terminates the program. The JVM, on the other hand, does not care. It just sits there and waits. One will need to get a thread dump (using some tools like jvisualvm or the like) to diagnose deadlock.

Now that we have MVars, it should be easy to also implement the other examples that demonstrate usage of MVars as simple channels and shared state, by merely copying the Haskell code. Of course, we won't really use MVars as building blocks for unbounded channels in Frege, as we already have native unbounded blocking queues.

In the next part, we will turn to chapter 5, where Simon Marlow shows us overlapping input/output.

Wednesday, February 27, 2013

Adding Concurrency to Frege (part I)

Inspired by a reddit post this week, I wondered what it would take to add concurrency to Frege, so that one could program a few simple examples from the concurrency chapters of Simon Marlows upcoming book in Frege.

For this we would need Threads, MVars and the operation forkIO that is supposed to execute some IO actions in a new thread concurrently with the main thread. The Haskell type signature of forkIO is:

forkIO :: IO () -> IO ThreadID

Let us first deal with Threads. We can import the functionality we need from Java:

data Thread = mutable native java.lang.Thread where
    --- Create a 'Thread' that runs a 'Runnable'
    native new   :: MutableIO Runnable -> IO Thread
    --- Actually start execution of a 'Thread'
    native start :: Thread -> IO ()

A few explanations for those who are not familiar with Frege: The code above first tells the compiler, that there is a Java type java.lang.Thread that we want to use as abstract data type under the name Thread.
It then puts two native function definitions (in Haskell terminology this would be foreign imports) in the name space that is associated with each type constructor. By convention, the name new designates the Java constructor of some class, while start is just an ordinary instance method. (Note that new could never mean an actual Java method, as new is a keyword in Java.)

Observe that native definitions never create anything new at the native (i.e. Java) level, they are merely telling the Frege compiler what already exists in Java and how we want to use it. From the definition for start, for example, the compiler deduces that there must be an instance method start in the class java.lang.Thread with a declared return type of void. It will then generate some wrapper code that allows us to use the Frege function Thread.start like any other, non native function.

By the way, we don't have to put those native definitions in the Thread namespace. We could give the definitions on the top level like so:

native newThread   new   :: MutableIO Runnable -> IO Thread
native startThread start :: Thread -> IO ()

Obviuosly, though, in a program that deals with several Java classes (say A, B and C), we would then have to come up with different names like newA, newB and newC for their constructors and for other methods with the same name. We also could not use type directed name resolution, which allows us to write t.start and resolves it as (T.start t) if t is of type T.

The class java.lang.Thread has many different constructors,
but we want to use the one that takes a Runnable as argument.
The type Runnable is defined in frege.java.Lang,
this module is imported by default, so Runnable is normally in scope.

Interface Runnable is Javas way to pass around effectful computations.
The Frege runtime provides a function Runnable.new that
takes an IO action and constructs a Runnable instance that will execute
that action as soon as the Runnable.run method is called from within the depths
of Java. This is just what we need for our purposes.

We are now ready to write the Frege version of forkIO:

forkIO :: IO () -> IO Thread
forkIO action = do
    r <- Runnable.new action
    t <- Thread.new r
    t.start
    return t

This simply wraps the IO action passed as argument in an instance of Runnable
and creates a new thread with it. It then starts the thread
(which, in turn, causes invokation of Thread.run, which, in turn, invokes
Runnable.run and this, as said before, starts our IO action) and returns the Thread, unlike in Haskell, where it is a ThreadID.

But because a native type in Frege is just an abstract data type that can
ultimately only get manipulated through native functions,
the Thread reference we get from Java serves us very well as "handle" or "id",
so we need not distinguish between a thread and a handle to manipulate a thread.

What we have so far allows us to implement Simon Marlows first example, a simple program to demonstrate the interleaving of effects:

main args = do
    forkIO (replicateM_ 100000 (putChar 'a'))
    replicateM_ 100000 (putChar 'b')

And indeed, when we run this, we get something like:

ababababababababababababababababababababababababababa
ababababababababababababababababababababababababababa
ababababababababababababababababababababababababababa
ababababababababababababababababababababababababababa
ababababababababababababababababababababababababababa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
babababababababababababababababababababababababababab

Most of the time, the scheduling of the threads seems to be fair;
however, there are also long strokes of only 'a's or 'b's inbetween.
(Example was run on Ubuntu 12 on a PC with i3 processor with 2 cores with "hyperthreading".)



In the next part we will implement MVars and turn to more involved examples, so stay tuned.

Wednesday, February 20, 2013

Frege on Devoxx France


PRÉSENTATION DE FREGE, UN LANGAGE FONCTIONNEL DANS L'ESPRIT D'HASKELL TOURNANT SUR LA JVM

Yorrick Laupa will educate the French regarding Frege. Can't wait to watch the video!

Saturday, October 13, 2012

New Features in Frege

Now, that the holiday season is over, I'll hopefully have to announce interesting news regarding Frege more often.

As the short note from last week indicates, the project has now moved to Github. The fregIDE has been separated and is now a project on its own. There is ongoing work on a continuous integration facility. The result will be that there will be no "offiicial" releases any more. Rather, certain versions will be merely marked as stable, while all friends of frege will be able to download the more recent builds also.

Even if it may have seemed so, we were not completely idle since the Easter Release. Besides numerous bug fixes, the following new features are now available:

  1. Record fields can now be polymorphic
  2. The restrictions regarding instances of function types have been dropped.
  3. As a further step to more Haskell compatibility, a single dot can now be used as function composition operator.
For more explanations and examples please consult the new wiki page that is devoted to new or changed features.