functional orbitz

What is Covariance and Contravariance Anyways?

2011-10-29T12:48:00.000-04:00

If you have been following the talk around Google's latest language, Dart, then you might have heard things like "covariant arrays are widely regarded as a mistake"(src). But what is covariance? Why are covariant arrays considered a mistake? Who has covariant arrays? Why?

What is Covariance and Contravariance All About?

class X:
    pass

class Y(X):
    def zoom(self):
        print 'Y.zoom'

class A:
    # Returns a value of type Y
    def foo(self):
        return Y()

class B(A):
    # Returns a value of type X
    def foo(self):
        return X()


# Takes a value of type A
def bar(a):
    y = a.foo()
    y.zoom()


# Call bar with a B
bar(B())

Is this code safe? Often, in an OO language, inheritance is used to create a type that looks just like another type, and pass values of this new type to functions that expect the other type and without breaking anything. So one might expect, looking at this code, that passing a B to bar would be safe. But it isn't. The problem is B.foo returns an X where A.foo returns a Y. bar then goes on to try to call a member function that only exists in Y, so the code will fail at runtime. B has violated the interface that A established. Python doesn't give us any tools to discover this error without executing the code, but statically typed languages like C++ and Java do. These languages can define the types that member functions of a subclass can take, and return, in order to be valid through covariant and contravariant properties. The concepts are larger than member functions but it's a good place to start.

Definitions

Before we can talk about covariance and contravariance we need to know what subtyping is. I'll restrict this to classes in an object-orientated language because that's what my knowledge is limited to, but these concepts go beyond that. An example of a subtype in an OO language would be a class that extends or inherits from another class, for example in C++ you would do class S : public T for S to extend T. The common way type theorists write this is S <: T. This can be read in a few ways: "any term of type S can safely be used in a context where a term of type T is expected" or "every value described by S is also described by T" (Pierce, 182). Thus, S is a more specific type than T, and conversely T is a more generic type than S. Given this, covariance and contravariance define when a more specific or more generic type is acceptable in a particular context.

The definition from the wiki article:

covariance and contravariance refers to the ordering of types from narrower to wider and their interchangeability or equivalence in certain situations

And their definitions:

Covariant - Given the types S and T specified above, covariance is when a more specific type, S, can be used when a more generic type, T, is specified. This applies to functions, a function that returns S can be used in the same context as a function that returns T.
Contravariant - When the more generic type, T, can be used where the more specific type, S, is specified. A function that takes a T can be used in the same context as a function that takes a S.
Invariant - The type specified is the only type that can be used.

My method for remembering the distinction is contravariant is larger than covariant, so it means narrower to wider.

Covariant Example

Consider this example from C++:

class X {};
class Y : public X {};
class Z : public Y {};

class A {
public:
  virtual Y *foo() { return new Y(); }
};

class B : public A {
public:
  virtual Z *foo() { return new Z(); }
};

Here we have three classes X, Y, and Z which we will return from a virtual function in classes A and B. This code is valid because B::foo is returning a narrower type than A::foo because Z is a subtype of Y. But what happens if we make B::foo return a wider type?

class X {};
class Y : public X {};
class Z : public Y {};

class A {
public:
  virtual Y *foo() { return new Y(); }
};

class B : public A {
public:
  virtual X *foo() { return new X(); }
};

$ g++ -W -Wall -ansi -pedantic -c foo.cc
foo.cc:12: error: invalid covariant return type for ‘virtual X* B::foo()'
foo.cc:7: error:   overriding ‘virtual Y* A::foo()’

Contravariant Example

As we saw above, one can be covariant on return types, but what about on parameters to a member function? One has to be the opposite actually: contravariant. Unfortunately, gcc (or the version I'm using at least) doesn't give us an error about contravariance, instead we have to add a little bit of code using B::foo to see the problem:

class X {};
class Y : public X {};
class Z : public Y {};

class A {
public:
  virtual void foo(Y &y) { }
};

class B : public A {
public:
  virtual void foo(X &x) { }
};


int main() {
  B b;
  Y y;
  Z z;
  
  b.foo(y);
  b.foo(z);
  return 0;
}

This behaves as we would expect. We can call B::foo with an X, Y, or Z, since B::foo takes the superclass to all of them (X). But what if we modify it to take Z:

class X {};
class Y : public X {};
class Z : public Y {};

class A {
public:
  virtual void foo(Y &y) { }
};

class B : public A {
public:
  virtual void foo(Z &z) { }
};


int main() {
  B b;
  Y y;
  Z z;
  
  b.foo(y);
  b.foo(z);
  return 0;
}

$ g++ -W -Wall -ansi -pedantic  foo.cc
foo.cc: In function ‘int main()’:
foo.cc:24: error: no matching function for call to ‘B::foo(Y&)’
foo.cc:14: note: candidates are: virtual void B::foo(Z&)

The error we get is about B::foo(Y&) not existing. Because Z is a narrower type than Y, we have broken the interface of A, so B is no longer a valid substitute for A.

But You Already Knew This

Intuitively, this is the way that makes the most sense. The use case for inheritance is generally when a function takes a certain type as input but you want to pass your own type. In order to ensure that the function, bar, can successfully use the type you pass it, all of the methods that bar calls on your type need to take types that bar can pass to it and return types that bar knows how to use. Take this code:

class X {};
class Y : public X { /* ... */ };
class Z : public Y { /* ... */ };

class A {
public:
  virtual Y *foo(Y &y) { /* ... */ }
};

void bar(A &a) {
  Y y;
  Y *y_ptr = a.foo(y);
}

If you were to pass your own type, B, which is a subtype of A (that is, B <: A) the only way we can implement B::foo such that our function bar still works is if B::foo takes an object as input that is a supertype to Y and returns a type that is a subtype of Y. Consider if it were valid for B::foo to want a Z. B::foo could try to call a member function that exists only in Z. But since bar is passing an object of type X, which we can't guarantee has member function that exists only in Z, our code would be unsafe. A similar argument can be made with the return type of Y and X.

What About Arrays?

Now that we get what these terms mean, how do they apply when it comes to arrays of objects? In C++, arrays are not covariant, however in Java they are:

public class Test {
    public static void foo() {
        Test[] tests = new Test[10];
        Object[] objects = tests;
    }
}

This code looks innocent enough, but there is a problem: what if I modify objects? For example:

public class Test {
    public static void foo() {
        Test[] tests = new Test[10];
        Object[] objects = tests;
        objects[0] = new Integer(1);
    }
}

This code compiles fine, but executing it gives the following error (changed foo to main in order to run it):

Exception in thread "main" java.lang.ArrayStoreException: java.lang.Integer
 at Test.main(Test.java:5)

This is what people mean when they refer to covariant arrays being a mistake. A compile-time check has been moved to runtime, which means you don't know if your code is safe without running it. Note, though, that what makes covariant arrays a problem in Java is modifying the array, not reading it. If we could somehow ensure that the objects array was immutable, covariant arrays in Java would be safe. Why does Java have covariant arrays then? Originally Java did not have parametric polymorphism (generics), without covariant arrays it would be impossible to write a generic function that copies one array to another. Instead one would have to write a copy function for every type of array they wish to copy (Pierce, 188). While the behavior is not ideal, at the least the JVM can provide some level of safety by performing type checks at runtime.

Unfortunately, I cannot shed any light on why Dart has covariant arrays. It has done everything from befuddle to enrage type theorists (null pointers, in 2011, why?!). Dart appears to support parametric polymorphism, the lack of which lead to Java having covariant arrays. It is a shame that Dart seems to be repeating, what some, would classify as mistakes for no obvious benefit. Dart is not the only one sinning though, C# also has covariant arrays and seems to have simply copied them from Java.

Conclusion

I'm no type theorist, this post went through several iterations with comments and corrections from friends smarter than I, so this post only scratches the surface of covariance and contravariance. Hopefully it is enough to understand what people are referring to when the terms come up in casual Reddit conversation. If you're interested in more, Benjamin Pierce's book, Types and Programming Languages, has an entire chapter dedicated to subtyping. While I haven't finished the book yet, what I have read is excellent. Even if you skip the math that looks complicated you will come out better.

Thanks

Special thanks to @dklee. Much of this post is based off of emails we have exchanged. Thanks to @j2labs, and @apgwoz, as well, for help in making this post.

Your Favorite Language is Probably Terrible at Concurrency too

2011-10-02T22:41:00.002-04:00

The internet has been ablaze with posts on NodeJS, to some people's joy and to others chagrin. Some have claimed that Node solves a long standing problem in concurrency, saying:

People are starting to build more on Node.js because it’s superior and it solves these problems that have always existed. I/O has been done wrong for the last 30 years

In my opinion, Node is bad at concurrency, and guess what? Your language probably isn't any better. But let's make sure we're on the same page first.

Language/Framework - Most languages do not have concurrency as a first class citizen. So when I say "your language is bad at concurrency", what I really mean is "the options available for doing concurrent things in your language are bad". The former just rolls off your tongue better.
Concurrency - What do I mean by concurrency? I mean a model by which you can define actions that can happen at the same time. That could mean running multiple pieces of code in parallel or interleaving them. Specifically in this post I am concerned with solving problems where the number of things you want to do concurrently is significantly larger than the number of cores you have.

There are a lot of options for concurrency out there. You may have heard of things like Pi calculus, Join calculus, Communicating Sequential Processes, Event-loops and Coroutines. Your language probably has an implementation of one of these, or a conceptual subset. NodeJS and Twisted implement an event-loop. Coroutines is the path Python's Gevent has taken, as well as libraries for Ruby, C, and C++. Go has chosen Communicating Sequential Processes. But all these distinctions aren't important unless I can say what I consider a good solution to concurrency.

Ideally, a good solution should have the following properties:

Scaling - If you are writing concurrent software you've already decided handling one thing at a time is not a scalable solution, so now you want to handle multiple things at a time. An ideal solution should scale to the limits of the machine. That means making use of multiple cores, if available.
Reasoning - It should be easy for a reader of your code to reason about what it does. Edge cases and gotcha's should be limited. Preferably one shouldn't even be aware of the concurrent aspects of the code unless they need to be.
Debugging - Debugging should not be painful. Standard tools like stacktraces should be meaningful. Tracing the path a piece of code takes shouldn't be harder than launching the space shuttle.

My claim is that very few concurrent solutions meet these criteria. But let me be clear, I'm not saying this is the only way you should judge selecting a solution. There is a Python library that does basically everything you think you need and it will be really hard to re-implement that functionality in another language? Well, maybe dealing with Python's concurrency shortcomings is less work than rewriting the library.

Scaling

Most languages were built for writing serial code. Memory is accessible by any piece of code in the process and it is assumed that nothing interesting happens between two function calls. But modern computers are not fast enough to do all the work programmers want them to do in serial and these languages have a lot of momentum behind them. For valid reasons, it is challenging to just move to another solution. Instead, we duct tape concurrency on top of these serial languages. One problem is that some of these languages can't even run code in parallel (that is, have two functions running at the same exact time) even if they wanted to. Python and Ocaml have a global lock that restricts this. In other languages it's just too much coordination to do safely. In C and C++ it can be too hard and time consuming to coordinate distributing concurrent work over multiple threads. For this reason, many mainstream solutions to concurrency are limited to running on a single core. It's insane, right? I can buy a laptop with, ostensibly, 8 cores now, yet a program written in most mainstream languages cannot make use of more than one.

For this reason, most solutions fail to be scalable. For example, NodeJS, Twisted, Ocaml/Lwt, and Gevent: from the point-of-view of a user of these frameworks, their code not only cannot run on multiple cores, but it depends on it. Consider some Twisted code that downloads N web pages and appends the result to a list:

def downloadUrls(urls):
    d = defer.Deferred()
    ret = []
    def _returnWhenDone(_):
        if len(ret) == len(urls):
            d.callback(ret)
    for url in urls:
        downloadDefer = downloadUrlAsString(url)
        downloadDefer.addCallback(lambda s : ret.append(s))
        downloadDefer.addCallback(_returnWhenDone)
    return d

Ignoring my failure to handle failures, this code is acceptable Twisted, and it could not work if Python suddenly got the ability to run code on multiple cores and Twisted used it. The reason being, there is no coordination around the ret.append(s) line. What if two threads were to try to append to ret at the same time? NodeJS and Gevent have the same idea in mind. Almost no data access is surrounded by a mechanism to coordinate multiple pieces of code accessing it at the same time. The result is, none of the code using these frameworks can be run on multiple cores. If CPython or V8 got multicore support it would take a rewrite of all of the code to make use of it.

But, you say, who cares? "I can just spin up N instances of my program, where N is the number of cores on my machine. I can easily scale that way". You can't even get concurrency right and now you want to move into distributed programming? Who are you fooling? But seriously, the problem is your code now needs to be "location aware". If you want to do something with object X, you have to be aware of where object X lives. This adds another layer of complexity to your system. Without a good way of communicating between instances you are limited to solving embarrassingly parallel problems or pushing the concurrency to another software layer. Either way, you aren't actually solving the problem with your framework. Luckily, a lot of what people want concurrency for is serving webpages, which requires almost no interprocess communication right now.

Reasoning

No matter how you slice it, writing concurrent code is hard. When it comes to serial code, looking at it and knowing what it does is as simple as understanding how each function operates given the current state of the program. But with concurrent code, the state of the program is changing while a function runs. Understanding a concurrent program involves understanding how the concurrent components are interacting with each other. Some solutions make this easier than others.

Take the following piece of example NodeJS code:

var db = require('somedatabaseprovider');
app.get('/price', function(req, res) {
  db.openConnection('host', 12345, function(err, conn) {
    conn.query('select * from products where id=?', [req.param('product')], function(err, results) {
      conn.close();
      res.send(results[0]);
    });
  });
});

The amount of syntax is enormous. There is a huge amount of line noise for what should look, at worst, like this:

var db = require('somedatabaseprovider');
app.get('/price', function(req, res) {
    var conn = db.openConnection('host', 12345)
    var result = conn.query('select * from products where id=?', [req.param('product')])
    conn.close();
    res.send(results[0]);
});

If you want to add proper error handling, the situation gets worse with callback code. Twisted has attempted to solve this by encapsulating code flow in an object called a Deferred, but the problem remains: a unit of work in callback-based code is not a function, like one is used to in serial code, it is work to do between events. Like the above example code showed, there isn't a function that connects to a db, does a query, and returns the result. There is a function to open a db connection, another function for when that is done and to do the db query, and another function to handle the result. You have defined three functions where you previously needed one. More importantly, you have to define functions not because it makes your code clearer but because the framework requires it.

Given how negatively this affects code, there are a lot of attempted solutions. Twisted, for example, allows one to use the defer.inlineCallbacks decorator so a function can use generators to express asynchronous code. Our previous NodeJS code might look like this:

@defer.inlineCallbacks
def handlePrice(req, res):
    conn = yield db.openConnection('host', 12345)
    result = yield conn.query('select * from products where id=?', [req.param('product')])
    yield conn.close()
    res.send(results[0])

app.get('/price', handlePrice)

In many ways this is an improvement but it does have its limitations.

The NodeJS community has been at work solving this problem for themselves too. One person added coroutines to V8, and gave it a C#-like syntax. OKCupid gave us TameJS. Both of these solutions have their problems which are deal breakers for many.

There are also, less complete, solutions like Step. But library solutions, like Step, only give you access to a subset of functionality you would get from the sequential code you really want to write. To do that you need a full CPS transformation (which is what TameJS gives you, at a cost of debugging). This is actually how the syntax extensions for Ocaml/Lwt work. The previous NodeJS code might look like this in Ocaml/Lwt (the relevant part is that lwt causes a CPS transformation to turn the code into the appropriate callback-based code):

let handle_price req res =
  lwt conn = DB.open_connection "host" 12345 in
  lwt result = DB.query conn (SQL.sprintf "select * from products where id=?" (req#param "product")) in
  DB.close conn;
  res#send results.[0]

App.get "/price" handle_price

This is one reason for Gevent/Eventlet's popularity in Python. Gevent uses coroutines to give you asynchronous code that looks sequential. The trick is, underneath the hood, some function calls actually result in all of the state for your current function call being saved, another one switched to, executed, rinse, repeat. Gevent has a cooperative scheduler that tries to intelligently decide which function to switch to.

Say you want to write the earlier NodeJS code in sequential Python, you might get:

def handlePrice(req, res):
    conn = db.openConnection('host', 12345)
    result = conn.query('select * from products where id=?', [req.param('product')])
    conn.close()
    res.send(results[0])

app.get('/price', handlePrice)

How would this look in Gevent? Exactly the same. The openConnection and query functions have an I/O call which actually jumps back to the Gevent scheduler so it can do something else while the I/O happens.

But Gevent is not without its cost when it comes to reasoning about code. Consider this:

def foo(data):
    print data.bar
    do_something()
    print data.bar

Looking at this code, will the same value be printed twice? The answer is: no idea. Even though do_something does not take data as input, it could do something that causes Gevent to context switch to another function, another function which also has access to data and modifies it. There is no way to tell, simply by looking at the code, if it will context switch or not.

Debugging

The previous Gevent code is printing out two different values for data.bar and you don't want this, how do you fix it? The first thing you might try, from your serial programming days, is a debugger. But that might not work very well. Why? You're in concurrent-land now, multiple things are happening at once! That means timing is important. If you set a break point somewhere, you've disrupted the time things happen and your program could take a completely different path, not the one you want to debug.

If you're smart and you control access to data.bar through function calls, you can do some printf debugging. Perhaps print out a stacktrace when one modifies it. But let's say, even those prints are causing the timing of your program to change, so now data.bar is coming out as the same value at each print. What do you do?!

The point is, debugging concurrent code can be very hard. Event-loop code adds another problem to debugging: your code doesn't have a linear path. If you could visualize sequential code, it would be a line. You start at point A, you do the things in order to get to point B, at any point if you have an error your callstack represents the path you took to get there. Event-loop code always needs to hit the event-loop for a blocking call though. The callstack you see is always limited to the path from the last event you got. A callstack in the code handling a database query may not contain the how you got there. If that query is part of a piece of fairly generic code you don't have many leads to go on to track it down.

Who got it right then?

Three languages come to mind: Erlang, Oz, Haskell. There are more out there but I'm not omnipotent. In my opinion, these languages are capable of the three properties I previously mentioned. Right now you are probably rolling your eyes and saying "I should have known, one of THOSE guys". But my argument is conservative: based on the properties that I believe are important for concurrent solution to be good, these languages excel (or are capable of it) at them. Real world problems contain more than just concurrency issues though, so this does not mean you're wrong to use a language that doesn't meet my criteria, but it does mean you are sacrificing something. Perhaps that sacrifice is acceptable. But don't fool yourself into thinking your language is not terrible at concurrency, because it probably is.

C Gotcha Of The Day: Pointers aren't integers

2011-07-31T14:35:00.003-04:00

The C standard is clear that pointers are not required to be convertible to or from an integer.

Section 6.3.2.3.5-6 in the C99 draft

An integer may be converted to any pointer type. The result is implementation-defined, might not be properly aligned, and might not point to an entity of the referenced type.)

Any pointer type may be converted to an integer type; the result is implementation-deﬁned. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type.

Basically, you can't depend on the following code doing anything useful:

int *p = (int*)0xff;

The C standard does not define a machine with a flat memory model. Old Intel systems are an example of a non flat memory model, they had a segmented memory model where a pointer needed a segment and offset.

Conversion to a string is also implementation defined in C, from 7.19.6.1 fprintf, the section on the %p format specifier:

The argument shall be a pointer to void. The value of the pointer is converted to a sequence of printable characters, in an implementation-defined manner.

And from fscanf:

Matches an implementation-defined set of sequences, which should be the same as the set of sequences that may be produced by the %p conversion of the fprintf function. The corresponding argument shall be a pointer to a pointer to void. The interpretation of the input item is implementation-defined. If the input item is a value converted earlier during the same program execution, the pointer that results shall compare equal to that value; otherwise the behavior of the %p conversion is undefined.

It does appear that even though the result of %p is implementation defined, it is guaranteed that you can fprintf and fscanf pointers and get back the same result inside the same program execution.

C Gotcha Of The Day: ptrdiff_t

2011-07-29T13:26:00.000-04:00

Excerpt from C99 Draft (AFAIK this has not changed):

The size of the result is implementation-deﬁned, and its type (a signed integer type) is ptrdiff_t deﬁned in the <stddef.h> header. If the result is not representable in an object of that type, the behavior is undefined. In other words, if the expressions P and Q point to, respectively, the i-th and j-th elements of an array object, the expression (P) - (Q) has the value i−j provided the value fits in an object of type ptrdiff_t.

That means, while the type size_t is capable of expressing the size of any object, you cannot guarantee that the subtraction of two pointers inside your object will result in defined behavior. That is because ptrdiff_t is signed (so it can give you the direction of the difference) and size_t is unsigned. You can use the macros PTRDIFF_MAX and SIZE_MAX to determine if your subtraction is safe though.

Sometimes I forget the full degree in which Python's "scoping" is broken.

2011-05-03T13:31:00.000-04:00

>>> [s for s in [1, 2,3]]
[1, 2, 3]
>>> s
3

[JC] Efficient Parallel Programming in Poly/ML and Isabelle/ML

2011-04-27T22:53:00.003-04:00

Authors: David C.J. Matthews and Makarius Wenzel
URL: http://www4.in.tum.de/~wenzelm/papers/parallel-ml.pdf
Year: 2010

I had not heard of Poly/ML or Isabelle/ML prior to reading this paper. I tried to do a bit of background research to get an idea for it, but I may have gotten some details wrong. If I made any mistakes below I will be happy to correct them.

The Paper

Poly/ML is a full implementation of Standard ML originally developed by David Matthews. Larry Paulson was an early adopter and implemented the Isabelle theorem prover. Isabelle/ML is the implementation of Isabelle on Poly/ML. Poly/ML was originally implemented with a single threaded run time system (RTS). With the ubiquity of multicore machines the RTS was modified to support threading, the garbage collector was modified and threading APIs were introduced. Finally, the modifications were tested in Isabelle. This paper is relevant to the frequent debates that occur on the Ocaml mailing list. Ocaml currently has no support for parallelism and this deficiency is frequently brought up as a negative.

The primary motivation for adding parallelism to Poly/ML is Isabelle/ML, where proofs can take hours to days to execute. Poly/ML and Isabelle/ML have been developed for many years which restricted the modifications to not break existing code and not grossly negatively effect single threaded applications. The authors decided to start with a fairly low level, pthreads-like, implementation and build layers on top of it, each more abstract than the previous. The majority of the changes took place in the RTS, Poly/ML base library, and Isabelle/ML library. In the end, no user's Isabelle code need be modified to take advantage of the performance benefits.

As stated before, Poly/ML is an implementation of Standard ML. The original definition of SML included an asynchronous exception called Interrupt. This was removed from the 1997 definition however Poly/ML has kept in for interrupting threads. This exception can be triggered by one thread in another thread to stop a computation. Interrupt is a useful mechanism to get a threads attention.

The RTS is written in C++, provides memory management, access to the underlying OS and required the most modifications. The RTS provides a one-to-one relationship between OS threads and ML threads. The OS is in charge of scheduling threads on cores. Synchronization primitives are not implement as a direct call to the underlying OS's, however. Each thread is given a single condition variable which the RTS can signal for the unlocking of a mutex, or signaling of a condition variable, in the ML code. A single threaded stop-the-world GC is used. While it is known that this is a likely bottleneck as the number of cores increase, it is shown that it not an issue up to 8 cores.

The base libraries were hardly altered, beyond adding the necessary threading APIs. The low-level APIs provided are:

Threads:

fork: (unit -> unit) * attribute list -> thread
interrupt: thread -> unit
setAttributes: attribute list -> unit
getAttributes: unit -> attribute list

Mutexes:

mutex: unit -> mutex
lock: mutex -> unit
unlock: mutex -> unit

Condition Variables:

condVar: unit -> condVar
wait: condVar * mutex -> unit
signal: condVar -> unit
boradcast: condVar -> unit

The only one that might need explaining is interrupt. This raises the asynchronous exception Interrupt in the provided thread. A few other locations of the standard library were modified, such as the I/O module which had locks added to each operation. The authors do point out:

... this overhead can be almost entirely avoided by using the functional IO layer of the ML library in which reading a character returns the character and a new stream since in this case a lock is only needed when the buffer is empty and needs to be refilled.

Abstractions over these were added to the Isabelle/ML library. The first is a synchronized variable with the following definition:

type 'a var
val var: 'a -> 'a var
val value: 'a var -> 'a
val guarded_access: 'a var -> ('a -> ('b * 'a) option) -> 'b

guarded_access takes a synchronized variable, and a function that takes the value of the synchronized variable as input and returns an option containing a tuple of the new value to put in the synchronized variable and the value to return. The combinator combines the idea of a mutex and condition variable. In the code guarded_access v f, f will be applied to the value stored in v. If f returns NONE then guarded_access waits for the next signal on that variable and applies f again. If f returns Some (a, b), then the value b will be put back into the synchronized variable and the value a will be returned.

This simple construct can be used to implement variables that can be safely shared, and updated, between threads. mvar's, variables where a thread waits for a value if none is there when getting and waits for the value to be removed when putting, can be easily implemented with this:

type 'a mvar = 'a option var
fun mvar () = var NONE
fun take v = guarded_access v 
               (fn NONE => NONE | Some x => Some (x, NONE))
fun put v x = guarded_access v 
               (fn SOME _ => NONE | NONE => (SOME ((), SOME x)))

The other abstraction presented is futures, which are a way to represent the result of a computation before it is completed. The futures interfaces looks a lot like a typical lazy evaluation interface, except the value will always be computed unless it is canceled. Futures are an attractive way to represent parallel computations. Consider this contrived example:

val x = future some_expensive_computation
val y = future some_other_expensive_computation
val z = join x + join y

We create two futures, x and y which evaluate to integers. Then we create z which will be the sum of x and y. Assuming you have enough cores, x and y will be computed in parallel. The join function waits for the future and evaluates to the value of the future. Here is the interface for futures in Isabelle/ML:

type 'a future
val future: (unit -> 'a) -> 'a future
val join: 'a future -> 'a
val cancel: 'a future -> unit

If a future is cancelled or produces an exception, that exception will be reraised when join is called. Isabelle/ML also contains a few future combinators, such as future groups which create a hierarchy of execution that kills all futures in the hierarchy if one fails.

The implied implementation of futures is a thread pool where the future function queues work for the thread pool. A scheduler will then decide which futures get work or are cancelled.

That is the end of additions to Poly/ML and Isabelle/ML. How well does it work? While subjective, performance improvements were more than acceptable with tests plateauing at around 8 cores. The tests were performed using large Isabelle/Isar proofs available in the standard distribution. Isabelle/Isar is non computational language and has a modular nature that makes it possible to exploit implicit parallelism. Four Isabelle applications were used for testing, all of which are considered reasonably large. The results showed a maximum of 3.2x speedup for 4 cores and 6.5x on 8 cores. Past 8 cores the performance increase plateaus. Two bottlenecks were investigated further. The first is garbage collection. As stated earlier Poly/ML has a single threaded stop-the-world GC. At 16 cores GC becomes about 15-30% of the run time. The second bottleneck is insufficient parallelization. Of the applications chosen, there was an insufficient amount of work to keep all of the cores busy.

While there are many implementations for functional languages out there, Poly/ML remains one of the few that supports true multicore threads in a stable state and used in realistic applications. The modifications to Poly/ML took about 1 person year of work. Future work includes parallelizing the garbage collector.

The Discussion

Every few months the question of if Ocaml will get multicore support comes up. The answer is generally "no" (although it's coming closer to "yes" thanks to OcamlPro) with the reason being it is too hard to provide a proper implementation, garbage collection being given as the primary reason. I think that the results of Poly/ML show that even a single threaded stop-the-world GC can provide a sufficient performance advantage while also providing more powerful abstractions for parallelism. A parallel garbage collector can be worked in later, if needed, without affecting existing code.

I liked that the authors chose to add low-level threading support and build layers on top. It gives developers options if the provided abstractions are not meeting their needs. Futures appear to be a very appealing abstraction but I worry somewhat that they are insufficient. In order to maximize parallelism, should every function consume and produce futures? That seems a bit overkill and the overhead would likely be enormous. But it is easy to think of situations where either decision hurts you, either because of the overhead or because you aren't utilizing all of the cores effectively. I do like futures as an option though and hope to see them if/when Ocaml gets multicore support.

This is my first exposure to Poly/ML and the authors have done excellent work. I hope it provides motivation for bringing Ocaml into the multicore world.

A little gotcha in overloading comparison methods in Python

2011-04-14T10:50:00.011-04:00

Python supports chaining relational operators so you can express 2 < 3 < 4 and get true. It looks like this is implemented as a little compiler trick that actually creates the expression "2 < 3 and 3 < 4". This can be confusing if you try to do something insane like implement Haskell's (>>=) in Python using (>=). Something like:

Just(10) >= (lambda x : Just(x + 1)) >= (lambda x : Just(x / 2))

Will actually become:

Just(10) >= (lambda x : Just(x + 1)) and \
    (lambda x : Just(x + 1)) >= (lambda x : Just(x / 2))

This only seems to only apply to the relational operators, choosing to implement (>>=) with (>>) in Python seems to work fine. Here is a Gist showing the problem from @apgwoz: https://gist.github.com/916132.

Unicorn is Unix, What?

2011-04-12T10:51:00.000-04:00

I'm late to this blog post but @apgwoz just sent it to me. I found it pretty silly. Apparently we should like Unicorn because it uses a lot of Unix system calls...

There’s another problem with Unix programming in Ruby that I’ll just touch on briefly: Java people and Windows people. They’re going to tell you that fork(2) is bad because they don’t have it on their platform, or it sucks on their platform, or whatever, but it’s cool, you know, because they have native threads, and threads are like, way better anyways.

Fuck that.

Don’t ever let anyone tell you that fork(2) is bad. Thirty years from now, there will still be a fork(2) and a pipe(2) and a exec(2) and smart people will still be using them to solve hard problems reliably and predictably, just like they were thirty years ago.

False dichotomies are the best form of logic.

Summary of CUFP 2010

2010-10-05T22:34:00.009-04:00

This year was my first attending CUFP and I had a great time. I was pleasantly surprised at how strong of a showing the OCaml community had. I knew Jane Street would be there but I ran into several other people working in OCaml. The star of the show was definitely F# in my opinion. The weakest part of the conference was the lack of outlets. My laptop battery ran out by the second session of the first day and it was really quite difficult to find an outlet to charge it.

Day 1

The first day was broken into two session, each in a tutorial style. For the first session I was in the Building Robust Servers Using Erlang presented by Martin Logan from Orbitz. This stumbled a bit at the beginning, I think Martin was hoping people would be more familiar with Erlang as a language so he could delve into how to build a robust server. It picked up in the end though and I think he successfully drove his message home. The people I talked to after the session expected it to be a basic description on how to write Erlang but were impressed by the power of OTP, especially the supervisor model. A few people remarked that Erlang seemed great for anything that needed to be long running, so I think Martin was successful.

I jumped between all of the presentations in the second session.

F# - This was interesting, I hadn't seen F# much before. The presenter was teaching it through an ant simulation and had a contest with prizes.

Camlp4 and Template Haskell - I was a bit let down by what I saw of this one. It didn't seem like the presenters really gave a good introduction to templating languages. They presented a problem and let everyone work on it and would go around answering any questions. I wish my laptop battery was working so I could have taken a shot at playing with Camlp4. To their credit they were very helpful when asked but the initial presentation seemed lacking to me. Perhaps it was just too far over my head at this time.

Scala and Lift - This was the presentation that I had the least interest in but I think was the most well done. David's presentation was interactive and had no slides. He simply wrote code with you and explained what it did and I think that worked well. Everyone I talked to after seemed impressed by what Lift was capable of accomplishing so easily.

Day 2

Day 2 was all talks done in serial. I enjoyed most of the talks quite a bit. Yaron Minksy from Jane Street started out by saying something I think was important and easy to forget if you are heavily in the FP community. Despite the clear progress FP seems to be making (F# in Visual Studio, Real World Haskell, FP's in several big companies), we really aren't growing like we'd like to think. For most people management either says no to a functional language or it has to be snuck in through the back door. That is why they chose the keynote to be about F#. Microsoft including it in Visual Studio is a big leap and probably the biggest news in terms of FP going mainstream. But is it enough? We'll find out in the coming years.

F# - This was the keynote presented by Luke Hoban from Microsoft and he painted a really great picture of F#. His talk spanned how they introduce F# to non-functional programmers, a demo of F#, and some experiences in productizing it. The integration with Visual Studio was topnotch. Luke showed off how easy it is to create a GUI, handle events, and run asynchronous code. It almost made me wish I was running Windows, it looked so nice. The power of F#, to me, was making GUIs. The language looked like it had to be weakened a bit in order to successfully exist in the .Net ecosystem but if I ever find myself working on Windows I will gladly use F#. How much will F# be adopted by mainstream programmers? Who knows, I'm hoping quite a bit though.

Scaling Scala at Twitter - I knew Twitter used Scala but I did not realize they were such a large Scala shop. Scala was another language that seemed to have good representation at CUFP. I am still not sold on it but people seem to be doing great things with it. This talk was mostly about experiences in building the geolocation in Twitter. It was impressive that geolocation was built very quickly by two engineers who had no Scala or Java experience. There were two takeaways from this talk. The first is that the data center is the new computer. When you are designing a distributed application you really need to think differently about it than you would a non distributed application. This should not be a surprise if you really think about it but the emphasis seemed to be that in many cases people don't realize there is a difference. The second was that we should be honest about GC and realize it is a leaky abstraction. It would be nice if the application could get information back from the GC. The application really knows best how to handle working under heavy load and it would be nice if it could query the GC to figure out what kind of load it is under. I am not quite sure how much I buy the second one, couldn't the application monitor itself based on some metric relevant to its operations and modify its behavior based on that?

Cryptol, a DSL for Cryptographic Algorithms - This was from the people at Galois. I don't know much about Galois other than dons works there and they do Haskell, but it looks like they get nice government contracts too. I had no idea how complex the world of cryptology is. I knew the algorithms were sophisticated but not the rest of it. Cryptol seems powerful but much of the talk was over my head.

Naïveté vs. Experience - or, How We Thought We Could Use Scala and Clojure, and How We Actually Did - This talk was by Michael Fogus and my favorite. MIchael was entertaining and insightful. Most of this talk was about Scala and it included why they moved to Scala from Java, what they expected to use in Scala, what they actually did use in Scala, and the problems with Scala. Michael talked a lot about how he convinced his team to move to Scala as well. The experiences were positive but it did take a lot of convincing. The slides to his talk can be found here.

Reactive Extensions (Rx): Curing Your Asynchronous Programming Blues - Sadly Erik Meijer was unable to present this. I forgot to write down the name of who did present it, Wes something, but he did a great job. Rx looks really cool. I don't know how it scales up in writing an application but Wes was able to throw together some interesting programs very quickly using Rx. Rx is a Reactive Programming library for .Net. In short, it treats events like a collection and you simply iterate over the collection to get events (you can even use LINQ). This makes writing even driven software easier to think about and easier to compose events together. All of his examples were in C# but, because Rx is on .Net, it can be used seamlessly with F# (is the impression that I got).

Eden: An F#/WPF framework for building GUI tools - Eden is built by the Credit Suisse guys so they were unable to actually show Eden, however a subset of its functionality was built for the talk. This showed off more of how pretty GUIs can be created with F#. WPF has really great graphics and looked easy to produce. The portion of Eden shown was using a graph-based layout to calculate output on demand. It is difficult to explain succinctly but this talk showed off GUIs in F# as well as how easy it is to create asynchronous code. F#'s two strongest points seem to be OCaml's two weakest points.

Functional Language Compiler Experiences at Intel - The speaker couldn't talk too much about what they were working on (apparently Intel is making a functional language designed to be used for their processors with many many cores) they they did have some interesting meta-things to say. The first was, even in the FP world, sometimes you just want impurity. The second was, if your FP language is going to allow you to write code imperatively, don't make the syntax terrible. In this case they were writing SML. Finally, it is harder to teach someone FP if they have programming experience than something completely fresh. In their case they were looking at 8 - 12 months before really getting a return from the people they were training.

Riak Core: Building Distributed Applications Without Shared State - This talk was great. Rusty from Basho gave a great look at the important functionality in Riak. Riak is broken into three components: Riak Core - a core library for building robust distributed applications in Erlang, Riak KV - A key-value store using Riak Core, and Riak Search - a full text search engine using Riak Core. The message here, again, was the data center is the computer. I thought Riak's usage of virtual nodes was interesting too, and it seemed obvious in hindsight. Rather than break your distributed application up by physical nodes, create a ton of virtual nodes (more than you'll ever have of physical nodes) and then map those to physical nodes. Take sharding, for example, if you map to physical nodes, once you add a new physical node you'll have to repartition your shards all over again. But if you have a few hundred virtual nodes, adding a physical node just means you have to remap some data to it and point the new virtual nodes at it, but your upstream code doesn't need to change at all. Riak Core helps take care of the virtual node mapping for you as well as how to push data around when you add or take away physical nodes.

Functional Programming at Freebase - I was excited for this talk but sadly let down. This involved rewriting Freebase's query language parser and executor from Python to OCaml. It looked more like mental masturbation to me though. Several times I found myself simply wonder why some choices were made. Many of the choices came off as wishing he were writing Haskell. In the end the speaker got a 10x speed up, which was pointed out to not be very good, and it looked like they had to go through a lot of headaches a long the way.

ACL2: Eating One's Own Dogfood - I was unable to attend this talk.

I enjoyed CUFP quite a bit. It was great to meet the people I read papers from or see on videos about my favorite languages. In terms of being mainstream, Scala seemed to be making the fastest gains, most likely because it is so close to Java, it is an easy switch. In many ways I felt like we are all slowly catching up to Haskell. Many of the technical ideas presented here have already existed in Haskell for quite awhile and I could almost see the frustration on faces of the Haskell people wondering why the rest of us haven't figured out that we should be writing it. I'm hoping that next year the number of companies adopting functional languages continues to grow so we can see more examples of FP in industry at the next CUFP.

Learn You Some Erlang renamed Learn You Some Scala

2010-03-31T15:19:00.004-04:00

I'm excited to announce that Frederic Trottier-Hebert has decided to change the name of Learn You Some Erlang to Learn You Some Scala! This should come as no surprise to most of us. As I demonstrated here Scala and Erlang are really the same language. With the growing popularity of Scala it only makes sense to target the Scala audience (whom we can thank for Erlang's actors). I got the chance to talk to Frederic about the change. When asked what finally prompted the change he said:

<MononcQc> Well yeah, I mean I was there when you first were talking with Virding about the migration of Erlang to the JVM. I'm quoted in that blog post

<MononcQc> that discovery was pretty much a shock to me too, and so it's why I've pondered this and discussed the whole issue over #erlang on the course of the last few weeks

<MononcQc> I picked up one of the many great books about Scala and realized that 'damn, they're the same stuff!'

<MononcQc> Scala being bigger with the JVM being stress tested in production environment (sometimes claiming 9 nines of uptime)

<MononcQc> I decided to do the switch.

<MononcQc> So LYSE becomes LYSS

<MononcQc> It's much more marketable anyway

Some of the changes he has told me are upcoming:

OTP In Scala - How to work with some of the Scala specific OTP libraries to get better soft real time guarantees and performance

Mnesia and Scala - Mnesia is written in Erlang/Scala so moving your databases should Just Work. There should be a pretty big performance increase due to the JIT too (performance improvements have been shown to be about 20%-25.4%) I'm pretty excited about this one.

JVM Performance tuning - When to use -client and when to use -server will play a big part in this chapter. Frederic plans on really covering the nitty details of JVM tuning. Frederic admits that he hasn't done much work with the JVM but given the similarity to beam doesn't forsee that being a problem

Java interop - No more need to use jinterface, Java interop is much easier when running on the JVM!

What does Frederic have to say about possible backlash from the Erlang community about the name change? "I see none. I'm moving for the best". There you have it folks. Frederic said the rebranding is still a work in progress but he hopes to have the entire book moved over to Scala terminology in a few weeks.

How Much Has Scala Influenced Erlang?

2010-03-10T13:12:00.007-05:00

This question was recently overheard at qcon. On the surface it seems like a rather silly question but after some digging I think the answer might surprise you.

Scala and Erlang have actually gone back and forth, sharing ideas, for quite awhile now. While many people don't realize it, Erlang was first implemented on the JVM. This is back in the 1.x days when Java was using green threads. Joe had seen that this was a great platform for distributed, low latency, high throughput, concurrent applications and wrote a quick language implementation that quickly grew into Erlang. Martin Odersky has stated several times that Erlang was his influence for implementing Scala on the JVM. It was at this point that Scala introduced actors. While not a new concept, Scala was one of the first major implementations of actors. Erlang originally used a dataflow concept similar to what Mozart/Oz would later implement.

Why, you may ask, did Erlang finally move off the JVM? Such a great platform, you would expect them to stay. The answer is tail calls. The JVM has always lacked tail call optimization and Erlang needed it. Trampolining just was not sufficient for how Joe wanted to structure programs. So they ditched the JVM and implemented their own VM (known as beam). At this point, since Erlang was off the JVM, Sun (now Oracle) decided to drop the green threads for a more traditional threading implementation. While this transition may seem weird, it actually gave birth to what many people consider the most powerful part of Erlang: fault tolerance. Because Joe wanted to move off the JVM as quickly as possible he had people use his unfinished VM, which was very buggy. A lot of the fault tolerance aspects of Erlang come from people trying to work around Joe's buggy VM, which thankfully is quite stable now.

Richard Virding was nice enough to give us a little rundown on what it was like in the early days of moving from the JVM to beam (from #erlang on freenode):

< MononcQc> Did the need for distribution have anything to do with your move from the JVM?

< rvirding> No not at all, Terracotta implemented everything we wanted, and better, it was really the tail calls that pushed it.

< rvirding> I can remember one night late with Joe we were trying to get our own distribution layer worker and we were having trouble with the security model.

< rvirding> Joe had just happened to be playing with Netscape that day and saw this idea they introduced called 'cookies' and he said "Richard, I've got it!"

All of this makes a lot of sense when you think about it though. Given the popularity of Scala and that it was a forerunner to Erlang's style of programming you can see why there are so few Erlang books. It also becomes clear why Erlang has such a hard time penetrating the market. You can pretty much pick up Erlang just from a Scala book and at that point, why not just use Scala?

EC2 Acting Up? Instances not showing up in describe after being launched

2010-01-28T11:05:00.003-05:00

There have been a bunch of posts lately about EC2 being over saturated. The latest issue I have run into is running an instance via ec2-run-instances, it returning successfully, but no new instances showing up in ec2-describe-instances. The instance eventually shows up in ec2-describe-instances about 10 minutes later, up and running. Unfortunately I cannot reproduce this easily and the actual code which handles this is buried deep in some layers so I don't know what ec2-run-instances is returning (it appears to be returning something valid though). I also don't feel like trying to bring up instances until one fails unless Amazon wants to reimburse me. Anyone else noticed this?

Friday Links - 2009/12/04

2009-12-04T08:49:00.002-05:00

Incanter Blog - A guy I work with wrote this. It is a statistical package in Clojure. It is currently used by a company that tries to make plane delay predictions.

Pasteboard HappStack Demo - Here is a little demo of how to write a web app in HappStack. It looks promising.

Earth's Relative Size - A neat set of videos that demonstrate Earths relative size among other celestial bodies.

Dirk's Accident - Demonstrates the dangers of magnets! The guy lost part of a finger.

Friday Links - 2009/11/20

2009-11-20T10:34:00.002-05:00

Paaaancaaaakes! - By far the best scene from Cabin Fever

Part of cat brain simulated - This is part of a cat brain simulated in a computer

Bowtie - Incredibly fast program for genome assembly against a reference genome

Not too many interesting links this week unfortunately.

My Weaksauce Event Loop In Python

2009-11-14T13:22:00.008-05:00

I have been writing a bunch of glorified shell scripts in Python. Like any tool, they start to get more complicated. Originally I was just wrapping up os.system into something with a bit more versatility, like throwing an exception if the program failed. Eventually I started to need to get the output of running programs so I switched to using the subprocess module. Then once again I realized I needed to run multiple programs at once to do some things in a reasonable amount of time. So I took the subprocess code and made it run a list of commands and use select to multiplex. Once again though I have found that I need more versatility. In this case I want to run multiple sequences of commands in parallel and I may not be able to predict what commands I need to run in total. For example, I may want to run a command to mount a drive, then if that succeeds do one thing and if it fails retry or error. So I decided to take my select code and change it a bit.

Rather than taking a list of commands to run, it takes a list of iterables. Each iterable returns a function that, when called, returns a list of streams to be processed and a function to call when all of the streams have been processed. The event loop then goes through handling the streams. When all of the streams for a specific iterable are finished, it calls the clean up function and calls the next iteration, if that is the last iteration for that iterable it removes it from the list.

Combining this with generations in Python makes writing this very easy. Here is some usage example code:


def test():
   import sys
   import random

   def f(id):
       print id
       yield ProgramRunner('date', sys.stdout.write, sys.stderr.write, log=True)
       print id
       yield ProgramRunner('sleep %d' % random.randrange(0, 10), sys.stdout.write, sys.stderr.write, log=True)
       print id
       yield ProgramRunner('date', sys.stdout.write, sys.stderr.write, log=True)
       print id


   runCommandGens([f(v) for v in range(100)])

This defines a generator called f that takes an id. f will run three programs in serial. One just prints out the date, the next sleeps for a random amount of time, and finally prints out the date again. The call to runCommandGens is the event loop. In this case it takes a list of 100 generators. I plan on changing the name of this function because obviously it doesn't need to be a generator, but something iterable.

The object being yielded, in this case a class ProgramRunner implements __call__. The cool thing is you can use whatever you want for this as long as it lives upto the interface required. Eventually having a Sleep instance would be helpful so you can pause reliably. You could also use sockets since the event loop is just selecting on streams. Here is another example:


def test1():
   import sys

   def f1():
       yield ProgramRunner('date', sys.stdout.write, sys.stderr.write, log=True)
       yield ProgramRunner('echo what is up', sys.stdout.write, sys.stderr.write, log=True)
       yield ProgramRunner('sleep 3', sys.stdout.write, sys.stderr.write, log=True)
       yield ProgramRunner('echo that is cool', sys.stdout.write, sys.stderr.write, log=True)

   def f2():
       yield ProgramRunner('sleep 2', sys.stdout.write, sys.stderr.write, log=True)
       yield ProgramRunner('echo this is another thing running concurrently', sys.stdout.write, sys.stderr.write, log=True)


   runCommandGens([f1(), f2()])

As you can see in this case it has iterables that it works through.

The use case for this is if you are mostly planning on doing work in serial and then want to do some work concurrently for a bit and when it is done go back to work in serial. This is mostly a toy at this point (although I do use it for simple things in production). I also want to add more specific versions of ProgramRunner. For example, one that constructs an ssh call or an scp call. I plan on using this for working with clusters of machines, for example on EC2. Often times I need to bring up N many machines and then run through a series of steps to properly set it up. I'll post some example code in the near future.

This code is also quite limited currently, in that it only allows output streams. In reality, this is the reverse of what I would like it to look like. What would be really cool is, rather than each iterator yielding something with a bunch of callbacks is if they could do:


def f():
    for event in ProgramRunner(...):
        process_event(event)

In this case, processing events would be no different than just iterating over a source of events. This is what Meijer appears to be going after in Meijer on .NET Reactive Framework. I really like the idea of what he was going for there.

Here is the code for runCommandGens. I'll probably be posting the complete code somewhere when I get a chance and if there is interest. Bear in mind this is just something I'm playing with, comments, criticisms and suggestions are welcome.


def runCommandGens(generators):
    """
    This takes a list of generators and runs through each of them
    in parallel running the commands.

    Each iteration of a generator must return something that is callable and returns a tuple that looks like:
    (oncomplete, [(stream1, function), (stream2, function), ... (streamn, function)])

    Where 'oncomplete' is a function that gets called when all streams have been exhausted
    and each stream has an associated function that gets called with the output
    """

    ##
    # contain objects being worked on from generator
    states = [(g, None) for g in ctorGenerators(generators)]

    ##
    # start initial commends:
    states = nextIteration(states)

    outputStreams = dict(activeOutputStreams(states))

    while outputStreams:
        input, _output, _error = select(outputStreams.keys(), [], [])

        iterateAndBuild = False
        for s in input:
            line = s.readline()

            if line:
                callStreamF(s, line, states[outputStreams[s]])
            else:
                iterateAndBuild = True
                            
                ##
                # removeStream returns True if this was the last stream to be removed
                # which means we need to try to start up the next iteration
                # and recreate outputStreams
                if not removeStream(s, states[outputStreams[s]]):
                    state = states[outputStreams[s]]
                    f = getOnComplete(state)
                    ##
                    # Finished with this one, call onComplete
                    f()
                    # Set the second portion to None, nextIteration uses that to know
                    # when to get the next iteration
                    states[outputStreams[s]] = (state[0], None)

        # If any of our streams are completely done, lets get new ones and rebuild
        if iterateAndBuild:
            states = nextIteration(states)
            outputStreams = dict(activeOutputStreams(states))

Friday links - 2009/11/13

2009-11-12T23:09:00.005-05:00

Smashing the Mega-d/Ozdok botnet in 24 hours - Pretty neat story of taking down a large botnet

3D Mandelbrot Set - purdy pictures

Google can render LaTeX math - Very nice feature to easily get proper mathematical equations in your webpages

Interview with John Hughes - John Hughes talking about Erlang and Haskell, I need to check out QuickCheck it sounds rad. I really like the end of this when he asks where the next order of magnitude in decreasing code size will come from.

Python Language Moratorium - A moratorium has been put on the Python language so that other implementations can catch up. This might mean we'll get an implementation that makes some aggressive optimizations

Cool Haskell Function - Shows off how simple and powerful Haskell can be

Philosophizing about Programming - MarkCC talks about his experiences with Haskell and why he thinks functional languages are great for building large systems

Google Go Language - Another MarkCC post. Go has made a lot of noise this week, it looks like it has promise

Friday Links - 2009/11/06

2009-11-06T00:23:00.005-05:00

I thought I'd add a weekly list of links that I found interesting over the course of the week. Here is the first installment. Some of these links may be old, they are presented in the week that I get to them, not necessarily the week they hit the 'tubes.

Blue Brain Project - A project to simulate a brain, pretty neat.

Where smoking kills most people - In developed countries, surpriiiiiiiise.

Shazam - Not Magic After All - How that Shazam program works, pretty neat.

F# and workflows - A short blurb + links about F# and workflows (which are monads). F# seems to have some pretty neat stuff.

Algae and Light Help Injured Mice Walk Again - Pretty amazing article on 'optigenetics".

Machine Learning - Stanford - Videos of Stanford course on Machine Learning (according to klafka the best part of stats).

One of those amazing Harvard Uni cell biology videos

2009-10-24T00:16:00.002-04:00

Suggestions On Debugging Distributed Apps?

2009-10-22T23:35:00.004-04:00

So far distributed apps seem to be the best use case for why it is important to be able to walk through code and do it by hand with a pencil and paper. I have been writing analytics code that runs on a cluster for close to a year and still have not been able to figure out a good way of debugging the code that runs on it.

Being able to bring it down to a testcase works well in some situations but I have found it ineffective in the long run. When you are dealing with a few terabytes of data it can be difficult to cut the problem down to a few megs of input data that you can reason about. While the framework I am using lets me run code on a single process so I can debug it, it is again not always possible to bring the input data down small enough that it is manageable on a single process. On top of that, the behavior you are trying to debug may not show up on such a simple case. It's pretty impossible to use a traditional debugger if the bug only shows up in a few megs of data when you are dealing with a terabyte, how can you step through a 6 hour run if it only shows up on a small portion of that data? How do you predict what machine that bad data will run on if you don't even know what the bad data is?

I have so far been using three methods to debug a distributed app.

If I have some idea what the bad data looks like, I'll look for some approximation of it in the input data and throw an exception with the debugging info I'm interested in. Exceptions make their way back to the main console of where the jobs are run from so I can see them easy enough.

Use standard IO. The annoying part is the framework I use only logs this out to local files on the machine it ran on, so I have to wrap the grep in an ssh call to each machine. It's also sometimes difficult to know what to even print out. Too much printing can also significantly reduce performance and even fill up the disk with logging data. Logging data as big as the input data is not any easy to comb through.

Just reading through the code by hand and working it out with pencil and paper. This has only really worked if I can get a good mental image of what the input is like. If I have a terabyte of input from untrusted sources it can be quite freeform and difficult to reason about as I walk through the code by hand.

Right now I am experiencing a bug that I have been unsuccessful in tracking down. The problem is it only shows up when I use it on huge amounts of data. I have two ways of doing the same thing. One of them takes way too long and the other takes a very short time, and the short way is not producing the same numbers as the long way. It is off by only about 500 million in 5 billion rows of input and it is being a very frustrating bug to track down. The main problem is that I cannot produce a smaller set of input files to cause the issue. Runs take over 6 hours with the input file I need, so a single test can take almost my entire work day. If anyone has any suggestions, please let me know.

Sneaking Complexity - Being Asynchronous

2009-10-18T20:58:00.006-04:00

I went out to lunch with some coworkers last week and we got to talking about the project they are working on. They had done a great job of implementing the app which pretty much makes up the backbone of our company. They rewrote it in Java and have gotten orders of magnitude better performance. The app needs access to various pieces of persistent data quickly and they have created several data-clusters that perform amazingly. And the code is very clean and easy to read. The problem they are running into though is the client code for the data-clusters.

One of the main reasons that Java was selected as a language to write in is the simplicity of reading and writing it. It is fairly easy to jump into a method and, with a good IDE, figure out what it is doing. It is simple. The problems they are running into, though, is when doing things Teh Java Way isn't working out for the volume and latency they are trying to reach. Specifically, they are hitting issues when they query the data-cluster. Generally when they decide they need to hit the data-cluster they do a query and if they don't get a response back in some timeout period they go on as if they have a new record. In this case, being correct about the data all the time is not very important. But they are getting over the number of timed out queries they feel comfortable with (there is also a concern that the timeouts on the library they are using are not working properly). What they would like to do is handle hitting the data-cluster asynchronously. When they think they are going to need data, they send their query in, go do some more processing, then check to see if the data is there and continue on as if a new record if the timeout is reached. The problem is, this really sucks so far in Java. Being asynchronous is hard if you haven't designed your application around it in the first place. You pretty much have to fire up a new thread for every one of these queries you want to do. When considering a single case, this doesn't sound too bad, but the JVM uses OS threads so if you are already pushing your app to the limit, in the worst case doubling or tripling the number of threads it needs is not going to help. You also have increased the complexity of your application. Most of the threading in this application doesn't really need to share any data, each request is off doing its own thing and rarely hitting shared objects. But in this case, sharing the result of the query will need to share some data. It may not be much but it is added complexity. On top of that, there might be a performance hit in terms of GC. I'm not an expert in the JVM GC but shared memory means you might have to walk the entire heap in order to clean up the objects created by the query thread.

This brings me to something that is so great about Erlang. Accomplishing this is trivial. Since messages in Erlang are asynchronous, you simply send your message to query the data-cluster at the beginning of your block, then do whatever work you'd like, and receive it when you are good and ready. A receive block can take a timeout so you don't have any issues there. Doing things asynchronously is how Erlang works pretty much from the get-go. Erlang processes also have their own heap so cleaning up after one is fairly light on the GC, just throw away that process's heap.

To be fair, I am certain that had they implemented this in Erlang they would have run into their own fair share of issues. No language is perfect and Erlang certainly is no exception. But the application in question is basically what Erlang was designed for and is good at. There are also other issues that we talked that they would benefit from had they used Erlang too that I did not talk about. But this is a pattern that seems common in my short career as a developer. People look at the project they are solving, then look at whatever tools solve all the easy problems fast but in the end leave them in a worse state when it comes to solving the harder problems. Those tools that get you 70% of the way there have forced you to design your app so that it even harder to solve that 30%. This happened at my previous employer. A framework was chosen that implemented all the simple things they wanted to solve but they had now inherited this framework whose design was not made to solve the more complex problems. In the end they had to rewrite a bunch of the framework to get what they wanted. I'm sure that my coworkers are going to be able to solve this problem in Java (they have no choice) and perhaps there is a Java-way that this should have been done and I am sure that had they implemented this in Erlang there would still be problems being discussed over lunch. But I feel confident that they would be frustration Erlang records, or syntax, or strings, not with the sneaking complexity of trying to get it to do things asynchronously (and don't even get me started on fault-tolerance).

Lorenz Attractor In R

2009-10-18T18:31:00.015-04:00

I spent much of this weekend trying to figure out how to graph Chua's Circuit for a homework assignment. I ended up using R since I don't have or know MATLAB and I don't really want to learn Octave. It took me longer than it should have mostly because I don't know much of anything about differential equations. The implementation required two extra R packages, deSolve and scatterplot3d. The fun thing about working on this project is the whole point is to graph it so you get to see some neat visual output.

After finishing the circuit I decided to do a little extra and graph the Lorenz Attractor, which comes up quite often in class. This is a pretty famous structure in the realm of chaos theory. The term 'butterfly effect' comes from look of the attractor.

My solution uses the deSolve package in R. The function ode is used to solve the three equations that make up the attractor. With some minor understanding of R it should be pretty easy to play with. The settings I have in there give this pretty image:


library(deSolve)
library(scatterplot3d)

##
# Parameters for the solver
pars <- c(alpha = 10,
          beta = 8/3,
          c = 25.58)

##
# In initial state
yini <- c(x = 0.01, y = 0.0, z = 0.0)


lorenz <- function(Time, State, Pars) {
  with(as.list(c(State, Pars)), {
    xdot <- alpha * (y - x)
    ydot <- x * (c - z) - y
    zdot <- x*y - beta*z
    return(list(c(xdot, ydot, zdot)))
  })
}

runIt <- function(times) {
  out <- as.data.frame(ode(func = lorenz, y = yini, parms = pars, times = times))

  scatterplot3d(x=out[,2],
                y=out[,3],
                z=out[,4],
                type="l",
                box=FALSE,
                highlight.3d=TRUE,
                xlab="x",
                ylab="y",
                zlab="z",
                main="3d Plot of Lorenz Oscillator")

}

##
# Run a default value
runAll <- function() {
  runIt(seq(0, 100, by=0.01))
}

Impressed with Haskell's concurrency

2009-09-06T20:08:00.000-04:00

I have been playing with both Ocaml and Haskell* lately. In Ocaml, I have been rewriting a lot of simple Python scripts I use at work to see how they compare. They tend to be faster and more trustworthy. Ocaml, though, has pretty bad concurrency support. They have some thread library that wraps the OS threads, no real good message passing interface. Even the guys at Jane St have listed that as a complaint**.

So I decided to check out Haskell again. With Haskell I have always thought it was a great language, but could never grok it. That sounds a little weird, but reading Haskell code is simply great. When you figure out what it does, it tends to be very expressive and flexible. After looking at what Haskell offers for concurrency, I think that in theory it could give Erlang a serious run for its money. Here's why:

- Haskell, in general and in my opinion, is a safer language to write code in than Erlang. One can do a lot of work with Dialyzer to verify their code, but they are still somewhat limited. Haskells type system is very expressive and powerful. Haskell also has ADT's, which as far as I know Erlang still does not. For an idea of why ADT's are so powerful when it comes to writing safe code, see the Caml Trading video. And in this case, by 'safe' I mean writing correct code.

- Haskell produces generally fast code. GHC does some impressive optimizations, and supercompilation*** is most likely getting going to be part of GHC in the near future. It should noted that while Haskell can produce fast results, its lazyness can also be unpredictable in the optimizations (both speed and memory) that it performs. This is believed, by many, to be a big drawback to Haskell. I haven't done enough work in Haskell to really say how bad this is but Real World Haskell does give a complete chapter to diagnosing performance problems and optimizing them.

- Haskell's threading implementation uses green threads with a many-to-one mapping to OS threads. This means you can take advantage of multiple cores without modifying your Haskell code. The Erlang VM does this too, with SMP support. The greenthread implementation also appears to be blazing fast. Haskell is number one in the threadring solution on the language shootout. Erlang is about 4x slower. Take from that what you will.

- You can implement Erlang-like best-case programming in Haskell, from what I can tell. Haskell supports Exceptions, and you can throw exceptions to other threads using asynchronous exceptions. This gives you a way to 'link' threads like you can link Erlang processes. It is still programmer driven, so you can make a mistake, point for Erlang.

- STM, while I haven't read up on this, it seems like a pretty great way to handle synchronization between threads.

- Monads. When reading up on concurrency in Haskell, monads seemed to often come up as valuable in ensuring correctness. For example, in an STM transaction, one wants to restrict the transaction from doing things that cannot be rolled back, such as IO. This is done by the 'atomically' function taking an STM monad as input and wrapping the output in an IO monad. What this all means is one can't do IO in the atomically block unless it's unsafe. The ability to restrict what the user can do, when one wants to, with the type system is quite powerful.

That being said, Haskell does have some clear losses next to Erlang. The biggest drawback is the lack of a distributed model. There is distributed Haskell, I have not researched it much but I'm under the impression it is not 'there' yet. Erlang is easy to learn, very easy. Haskell is not. I have found that, in order to write really good Haskell code, one has to keep a lot of stuff in their head at once. Perhaps this is just because I am new but I have found Haskell better to read than to write. Erlang is not like this, while the syntax has some peculiarities to it, it is not hard to pick up and start writing good Erlang. I think Ocaml shares more in common to Erlang in this regard. The hump one needs to get over in order to write solid Haskell code is a real and legitimate reason to not choose Haskell.

All that being said, I admittedly am fairly new to Haskell so these opinions will change over time, I'm planning on putting more effort into writing real projects in Haskell to see how it goes. Needless to say, I am impressed by what Haskell has to offer for concurrency. If I'm factually wrong on anything here, please correct me, this is all based on some reading research I've been doing on Haskell, not my actual experiences.

* When I say Haskell, I really mean GHC here

** Yaron Minsky's Caml Trading lecture, very good! Makes a great, practical argument, for Ocaml - http://ocaml.janestreet.com/?q=node/61

*** Supercompilation http://community.haskell.org/~ndm/downloads/slides-supercompilation_for_haskell-03_mar_2009.pdf

Scaling webapps

2008-04-02T10:46:00.000-04:00

DISCLAIMER: I am not an expert in web apps and simply have been doing some research on them. Given that, my claims and concerns may be completely unfounded and simply a result of my ignorance of web app design, if so, please let me know.

I have been doing a little bit of research on webapps and I'm not sure how I feel about the standard model. The standard model, as I understand it, works by every incoming http request results in some number of DB requests where the DB is the holder of all state information. The web app itself, whether it be in PHP, or Rails, etc is stateless. I certainly don't doubt that for a large majority of applications this works fine. Take something like the yellow pages which is a Rails application according to this. The standard model seems quite reasonable for this. You have a page that is fairly static, people are mostly doing requests for data which requires walking through some large database and the results are being displayed and not much is happening again until the user initiates another page request.

Web apps are changing though. Today, we expect our web apps to look and feel like native applications, which means snappy responses and updates of it even without the user explicitly reloading the page. We have things like AJAX and Comet-style serverpush. In the end, this means more requests are going to the http server even when the user is not doing anything. The Comet style is pretty neat but from what I can see, polling with AJAX is the most widely used way. My concern is how well the standard model is going to scale as web apps are required to act more and more like native applications. The reason for my concern is because this method is simply polling the DB for state changes on every request and in every other situation polling quite clearly has not scaled. This is the exact reason Comet exists.

For the sake of simplicity, let's imagine that the web app is AJAX with polling. Some portion of the page is going to be asking for updates every 5 seconds. The standard model would have us querying the DB every 5 seconds for that request to see if the state has changed. If you have a couple thousand people on this page that is a lot of work. If the component of the page is changing often for a majority of the people then it's not too big of a deal but if it's not changing often for a majority we are doing a lot of worthless DB calls. I'm sure we would design our database so that this call is hopefully very lightweight but how well does that really scale in the end?

Now, the reason we want our wep app (such as something in Rails) to be stateless is because for each request we can be pushed around to a separate VM. So if we hold onto session state information there is a good chance we might not even get a chance to use it on the next request. On top of that, if you are load balancing between several hosts, you may not even be in a good place to share state information between VMs.

I'm sure almost all of this is not news to anyone who has made it this far in the post. What can be done to make a webapp scale better? I'm not sure but here is my suggestion and hopefully someone with more experience than myself can come back and say if it's a horrible idea or not. Let's say I want to make a web app that will be handling something like instant messaging such as google talk or meebo (which are both using Comet).

For starters, I want this to be fairly real time, when I send a message to someone, I want it to get to them ASAP. Secondly, there will be a lot of interaction between users. Clearly, page-by-page viewing is not going to work here. People can't be refreshing their page every few seconds to see if there is an update. AJAX with polling or Comet are clearly your two choices currently. How should this look after the HTTP request comes in though?

Here is how I am suggesting it should:
Each request should have some sort of session ID. Each session ID will be associated with a process. By process here, it could be an Erlang process or some OS process written in some other language, whatever. The point here is, for a particular session ID, its request will get forwarded to the same process every time for the life time of its session. This way, the process can store all the state information. We don't have to do worry about sharing state information in something like memcache. The process would have some sort of timeout value so they die off eventually. At worst case, we are back to the standard model where if a user does multiple requests that happen to have a pause between them longer than the timeout we now have to initiate a new process and it has to do the DB calls to initiate itself. In the best case though, we are consistently getting sent to the same process which is holding onto our data. The upside to this method is the process can also do things specific for that user such as opening up other connections. For instance, in the instant messaging example, a user logs in, they get a session ID and a process created for them somewhere that will be mapped to this session ID. The process opens up a connection to an event server for that user so it can listen for IMs and push IM's out. We now have an application that is quite event based on all sides of it. We won't be hitting the DB too often. Given that we don't really care where this process lives, we can also scale it out to multiple machines and not have to worry about replicating the same data over many machines because we don't know where the users request will go to.

Downsides?
Certainly. Clearly if we have 2000 people using our IM application at once, we need to have 2000 processes a live. If we wrote this in Erlang where each process for a session ID maps to an Erlang process (sorry about the terminology here all)? That's childsplay. We could host this application on one machine! But not everyone wants to write things in Erlang, so what about them? If I were in this situation, I would probably have some machines each running some amount of applications that will be doing some I/O multiplexing to handle this. So you would have some amount of OS processes and each one can handle some amount of session ID's. Pretty standard for something that isn't Erlang but needs to handle a bunch of things at once. If you are into Python, Twisted comes to mind. I'm sure other languages have their own way of doing this.

Another edge case here, and I think this is probably not too hard to deal with, is what if an event comes in (such as an IM) and the process times out due to lack of activity? You could have each event have a timeout and if it is not ACK'd in that time it gets saved to a DB and the next process that is created for that user picks it up as part of its initiation.

To reiterate, I do not have much experience in webapps, I simply have been doing some research and this is the impression that I have gotten. Are my concerns valid? Is the system I described what people are already going to or is it broken? How would someone write Meebo or google talk? Let me know.

Back in the saddle

2008-03-19T11:18:00.000-04:00

So I have been working on Wall Street for the last year+ and last week decided to quit my job. And non-too-soon, as my job will most likely no longer exist in a few months if you have been following the news over the past few weeks.

I am going back to school, moving out of NYC and off to Maryland so over this summer I should have a lot of free time and I am working on possibly being involved in sort of a freelance project in order to make money (details are still pending). Anyways, the current design of the project has a typical web-app interface, then a manager layer that encapsulates the database. The manager layer handles caching data and moving it back to the database when needed, and event dispatching, blah blah blah.

Immediately I think this is the perfect use case for Erlang. We want it to be fault tolerant of course (the downside of a web-app is when things go wrong it affects everyone) and be able to handle a lot of data moving back and forth (although I'm unsure of the specifics since this is so early). Basically this sounds like a standard Erlang app with mnesia as the cache most likely, spanning a few nodes and moving data back to a DB in a write-behind method.

Some people have a bit of a concern about Erlang, how will we find developers and so on, which are perfectly valid. My response to that is:
Erlang is such a simple language it does not take much time to learn, and while OTP is not as simple, it does not take much time to learn either. In the end, one needs to be less of an expert in Erlang to get an equal or better application (in terms of Erlang's strengths) than they would have to be in another language such as Java.

One possible alternative language being considered is Java because of JBoss. I haven't looked into JBoss in-depth yet, but at a quick glance it looks like it has some really nice and really mature features. The JMS implementation sounds pretty solid and the clustering. Everyone knows Java, or at least puts it on their CV, but this sounds misleading. How good does one need to be in Java in order to not make a mess of an application written using JBoss compared to Erlang? My opinion is that the way one learns Erlang is fairly similar to how they would write production software with Erlang, but perhaps not the same for Java. The features we use in our 'Hello World' are the same that we use in a production environment, this is not true of Java in my experience.

We are still looking into things but I'm currently hoping for Erlang.

Erlang Job Advert

2008-01-25T23:03:00.000-05:00

Well, it's been over a year, sorry. Today I received an email with an Erlang job offer for a company based in Boston. I don't know anything about the company at all, perhaps it is junk, but the project seems like something Erlang is good at. It's a telecommuting job, so that might raise a red flag with some people. If you are interested I'll put you in touch with the recruiter or whatever he is, email me at orbitz AT ortdotlove.net (that is really ortdotlove.net, not fancy spelling for ort.love.net).

Here are the job details:

Job Description:

Our client, who is based in Boston, is seeking an adept Erlang developer to help build a next generation metrics and monitoring system on the GNU/Linux platform. This system will watch and report on hundreds and thousands of systems, ranging from network devices to servers to software applications.

Required Skills:

· Must have experience with the Erlang programming language

· Must have expert level network programming experience, preferably in Erlang, C++ and/or C

· Strong background in developing on GNU/Linux for mission-critical production deployments

· Strong understanding of MySQL 4.1-5.x, including database design patterns

· Strong experience programming network servers/clients, including knowledge of fundamental protocols such as TCP, UDP, IPV4/6, and SSL/TLS

Cryptogram solver

2006-11-20T21:14:00.000-05:00

Newspaper puzzles beware. I have been working on soving newspaper cryptograms for the past few days in my free time. It is a bit more interesting of a problem to solve than sudoku I think. The algorithm I've implementing is nothing alltogether impressive and it relies on a good dictionary file to get solutions.

The algorithm works like so:
First you need an index which is a map of abstract words to lists of words.
An abstract word is taking a word and turning it into a pattern, for instance, 'cat' has the pattern '123', as does 'hat', and 'fat'. 'mom' has the pattern '121'.

Then it takes the sentence you have given it, splits it on spaces.
Popping the first word off the list, finds the list in the index of possible words it could be, iterates over it generating a map of letters to letters and recurses on the rest of the sentence, once it has reached the end of the sentence it puts the map it has generated into a list of possible solutions. If a generated map for a word conflicts with teh current map it is not a valid solution and moves onto the next possible solution.
The solve function returns a list of solution maps that can eb applied to any sentence to get the result.

Little things that make it helpful include being able to give an intial map, if you are sure some letters map to other letters you can give that as a hint. It can also remove any words whos pattern does not appear in the map.

Todo:
Solve only those subsets of words that, if solved, will result in the entire alphabet being solved. It should do this for all possible combinations of words in teh sentence that will result in this. This is not an optimizations, it should probably make it take longer to solve actually, however it allows it to solve sentences with words that might not exist in the dictionary but could come about as a result of solving the other words. I have a few ideas of how to do this but havn't had time to implement it yet.

The current code can be downloaded here.

Sudoku

2006-11-14T22:00:00.000-05:00

I've got sudoku fever! Actually, no, I don't, I don't really like sudoku at all but I decided to write a solver in erlang. It was pretty trivial. The basic algorithm is as follows:
1) Create a list of every blank square and the possible values that can go into that square
2) Find the square with the least number of possible values
3) Iterate over the list of possible numbers that can be in that square, create a new board with that value in it and recurse on the new board
4) Continue until there are no more possible values (in which case it failed) or the puzzle is solved.

The code is not the prettiest stuff in the world but it appears to solve the problem (specifically the remove_* functions).

Usage looks like:


Eshell V5.5.1  (abort with ^G)
1> {solved, Res} = sudoku:solve([
1> [9, 5, b, b, b, 6, 4, 7, b],
1> [4, b, 8, 7, b, 2, b, b, b],
1> [6, 2, b, 4, b, b, b, 5, b],
1> [5, b, 2, b, 6, b, 3, b, b],
1> [b, b, b, 2, b, 7, b, b, b],
1> [b, b, 4, b, 1, b, 2, b, 8],
1> [b, 7, b, b, b, 9, b, 3, 4],
1> [b, b, b, 1, b, 3, 7, b, 5],
1> [b, 4, 3, 5, b, b, b, 2, 9]]).
...
2> sudoku:print(Res).
9 5 1 8 3 6 4 7 2 
4 3 8 7 5 2 9 6 1 
6 2 7 4 9 1 8 5 3 
5 8 2 9 6 4 3 1 7 
3 1 9 2 8 7 5 4 6 
7 6 4 3 1 5 2 9 8 
8 7 5 6 2 9 1 3 4 
2 9 6 1 4 3 7 8 5 
1 4 3 5 7 8 6 2 9 
ok

Code (can be downloaded here):


-module(sudoku).

-export([solve/1, print/1]).

solve(Puzzle) when is_list(Puzzle) ->
    solve_puzzle(dict_from_list(Puzzle)).

print(Puzzle) ->
    lists:foreach(fun(X) ->
                          lists:foreach(fun(Y) ->
                                                io:format("~w ", [dict:fetch({X, Y}, Puzzle)])
                                        end, lists:seq(0, 8)),
                          io:format("~n", [])
                  end, lists:seq(0, 8)).
                          
dict_from_list(List) ->
    element(2, lists:foldl(fun(Elm, {X, Dict}) ->
                                   {_, DDict} = lists:foldl(fun(Elem, {Y, NDict}) ->
                                                                    {Y + 1, dict:store({X, Y}, Elem, NDict)}
                                                            end, {0, Dict}, Elm),
                                   {X + 1, DDict}
                           end, {0, dict:new()}, List)).

solve_puzzle(Puzzle) ->
    case generate_open_spots(Puzzle) of
        [{{X, Y}, Set} | _] ->
            try_value({X, Y}, Set, Puzzle);
        [] ->
            {solved, Puzzle}
    end.

try_value(_, [], Puzzle) ->
    print(Puzzle),
    io:format("~n", []),
    failed;
try_value({X, Y}, [H | R], Puzzle) ->
    case solve_puzzle(dict:store({X, Y}, H, Puzzle)) of
        {solved, RPuzzle} ->
            {solved, RPuzzle};
        failed ->
            try_value({X, Y}, R, Puzzle)
    end.
                      
generate_open_spots(Puzzle) ->
    OpenSquareList = dict:fold(fun(Key, b, Acc) ->
                                       [Key | Acc];
                                  (_Key, _Value, Acc) ->
                                       Acc
                               end, [], Puzzle),
    lists:sort(fun({{_X1, _Y1}, E1}, {{_X2, _Y2}, E2}) when length(E1) < length(E2) ->
                       true;
                  (_E1, _E2) ->
                       false
               end, generate_open_values(OpenSquareList, Puzzle)).

generate_open_values(List, Puzzle) ->
    generate_open_values(List, [], Puzzle).

generate_open_values([], Acc, _Puzzle) ->
    Acc;
generate_open_values([{X, Y} | R], Acc, Puzzle) ->
    generate_open_values(R, [{{X, Y}, remove_region_vals({X, Y},
                                                         remove_x_vals(Y,
                                                                       remove_y_vals(X, lists:seq(1, 9),
                                                                                     Puzzle),
                                                                       Puzzle),
                                                         Puzzle)} | Acc],
                         Puzzle).

remove_x_vals(Y, List, Puzzle) ->
    lists:foldl(fun(Idx, Acc) ->
                        case dict:fetch({Idx, Y}, Puzzle) of
                            b ->
                                Acc;
                            E ->
                                lists:delete(E, Acc)
                        end
                        end,
                        List, lists:seq(0, 8)).

remove_y_vals(X, List, Puzzle) ->
    lists:foldl(fun(Idx, Acc) ->
                        case dict:fetch({X, Idx}, Puzzle) of
                            b ->
                                Acc;
                            E ->
                                lists:delete(E, Acc)
                        end
                        end,
                        List, lists:seq(0, 8)).

remove_region_vals({X, Y}, List, Puzzle) ->
    {RX, RY} = find_region(X, Y),
    lists:foldl(fun(IX, AccX) ->
                        lists:foldl(fun(IY, AccY) ->
                                            case dict:fetch({IX, IY}, Puzzle) of
                                                b ->
                                                    AccY;
                                                E ->
                                                    lists:delete(E, AccY)
                                            end
                                    end, AccX, lists:seq(RY, RY + 2))
                        end, List, lists:seq(RX, RX + 2)).

find_region(X, Y) ->
    {find_region(X), find_region(Y)}.

find_region(V) when V >= 0, V < 3 ->
    0;
find_region(V) when V >= 3, V < 6 ->
    3;
find_region(V) when V >= 6, V < 9 ->
    6.

Lack of activity

2006-07-19T14:28:00.000-04:00

I have been busy looking for a job so I have had not had much time to do anything Erlang related. This, unfortunately, means I have not had much time to blog. I am hoping this will change by Sept. If anyone has any job offers and wants a resume, I am currently looking in the New York Ciy area for Financial Programming work or Bioinformatics work. Send an email to orbitz AT ortdotlove.net (that is really ortdotlove.net, not fancy spelling for ort.love.net). I'll gladly mail you back my resume.

I'm looking forward to getting back to programming for fun soon.

Shell

2006-05-30T00:43:00.000-04:00

The other day, araujo suggested Erlang might make a good shell. Shell as in, bash. Hrm, I thought, maybe...
I don't think Erlang would be flexible enough to make a decent shell. Take something like this:


for i in *; do echo $i; done

What would the Erlang equivalent look like?


lists:map(fun(X) -> print([X]) end, ls())

I just don't see it? I should hope it doesn't look like that but I don't know. On the other hand, I seem to have it pretty set in my mind that Common Lisp would make an excellent shell language. A few people have told me that CL would probably be too verbose and not work out well but, I don't know, it just seems so succinct and powerful. You could make a lot of macros to make your life easier. I sent an email to the Lisp At Light Speed blog dude to get his opinion but I figured I'd post it here too to see if anyone has any thoughts.


What I have in mind is basically an interactive shell, using Common
Lisp as its programming language.  For instance something like:
 
for i in *; do echo $i; done
 
Might look like:
 
(loop for i in (ls) do (print i))
 
The second thing I would love to see is Monad/Powershell.  Rather
than using text to pass data around, uses lists/objects/etc.  (ls)
for instance gives a list of file objects to iterate over, and you
can extract things like the size and permissions and what not.
 
This raises a question though. In order to do this, just about every
standard program becomes obsolete. For instance, why use 'cut' when
you can simply split a string with a CL function.  However some
things would still be very useful, such as ls, or grep, but these
now need to communicate via objects rather than just text, so those
will have ot be rewritten.  In which cause it seems like they could
simply be packages and loaded into the shell, meaning you don't
have to deal with program startup times or what not.  Is this a lot
of work to rewrite all of these programs, and does it mean that we
cannot usefully use third party programs that people write?  You
can always drop down to using strings as communication I suppose.
 
That is the basic idea.  So far a few people have suggested that
sexprs really aren't any better for this sort of thing.  sexpr's
won't be any better than say...bash.  Someone suggested that Factor
might be a better language for this.  But it seems to me, with
Common Lisps powerful macro system, you can easily make most
operations incredibly simple?  The most useful aspect would be using
objects to communicate.  But even if this is a lot of work to
accomplish, it seems to me that simply using CL as a shell programming
language seems like it would be nice. Am I wrong here? Am I missing
something?

If CL would make a poor langauge, what would make a good language? Riastrach has suggested Factor. I don't know enough about factor to say that but I think I like CL better for this.

All I know is:

This is not the answer

Pastebin design - Mnesia tables

2006-05-06T23:27:00.000-04:00

I have started to design the tables for this. The main goal is simple: make it easily extendable. That is to say I want to make it so I can easily develope it incrementally and add things to it that I didn't think of before. But that should be obvious to any developer. Given the spec of my previous post, here is the beginning of the database.

Table:
paste - This is the table that will hold the actual pastes.
pid | text | annotation | language | date

pid - unique id to identify a paste
text - the actual text
annotation - any annotation the paster wants to include
language - Plaintext/C++/Erlang, etc
date - when they pasted it

highlight - cache of pastes that have been put through the source highlighter
pid | text | last_viewed

pid - the same as paste.pid
text - result of being put through the highlighter
last_viewed - to keep track of when the entry should be removed

threads - paste threads
tid | [pid]

tid - the unique id for a thread
[pid] - list of pid's

I decided to have the thread table just contain an id and list so you don't have to do a bunch of queries to get every paste in a thread. This way a paste can be part of multiple threads (Although I don't see when this will ever happen). The paste table contains, I think, the minimalist amount of data in order to be useful. Using a highlight table means we can store, if we want, every single paste with a highlighted copy of the text, or just a few and use it as a cache style system. Later on we can also add the ability to associate a paste with an irc channel or a user if we wish to track that sort of information.

I'm not sure how to generate unique id's in mnesia. In a SQL database I would use a serial data type but I am unsure if mnesia supports this functionality. If not I suppose I could use newref maybe? I need to be able to convert it to a string to make url's, and also be valid between restarts.

As I think about it, I guess serials are just implemented as a table and store the integer in there, I can implement that in mnesia I suppose. It just needs to have some sort of get_and_increment functionality so two proceses don't get the same idea. If anyone has any ideas on how to implement this let me know. Bear in mind I have not looked at the mnesia documentation yet and am just brainstorming, so it is quite possible the solution is incredibly simple.

Next step - determine what pages pages will be needed.

Erlang Pastebin

2006-05-04T01:08:00.000-04:00

I have always wanted to make a pastebin for some reason. When I first started looking at nevow, I wanted to make one in that however mg beat me to it (and made a kickass one at that). So now I have been looking at yaws and think it would be a good project. Perhaps it can be packaged along with the wiki and chat client. I think my pastebin is a bit ambitious, but I would like to design it in such a way that it can all be added incrementally so I can have a functional pastebin and add onto it.

For starters, I would like a nice clean layout. I am going to do my best to use CSS and valid HTML for all of this. I am hoping petekaz can possibly help out with this. I am going to write it with everything in a div tags with proper ids so it should be easy to give this thing a skin eventually.

Technical Features:
Syntax highlighting - As with any pastebin this will most likely be used for code 90% of the time. For all of those languages we need syntax highlighting so they are easy to read. I have found a program, I beleive it is just called 'highlight'. It handles 100+ languages, including all of the ones I have an interst in supporting so I can simply interface to that.

Documentation links - People seem to want this. I am not sure how easy it is to support, especially if you want to support a lot of languages. It's a thought but not on the top of my list.

Annotation - Instead of putting suplimentery information in comments of the paste, just having a section for such information would be nice.

Threads for pastes - lisppaste does this I beleive. A paste should be like a discussion. "Here this doesn't compile" "You have a mistake here, this fix will work" "Ok, but now I have a problem here" "Ok do this". Each post in a paste thread will have the paste + annotation. To reply, since you are generally going to simply be making small changes to the previous post, the paste section should be populated with that already.

Compile code for your language - I am not sure how to do this safely, if at all. It would be nice to provide a gcc interface and an erlc interface and a ghc, yadda yadda. But I am not going to put my system at risk just for this feature that shouldn't be needed all too much in the first place.

Interface to any erlang app - By providing a node + a process name, this should be able to send a message that paste is ready to any erlang node. The obvious first usage of this would be an IRC bot. The main problem I see with this is, depending on what application the data is sent to, that will affect the look of the pastebin. For example, if the events are sent to an IRC bot, you want to be able to select what channel the notification gets sent to for the IRC bot. Should I just hardcode this into the pastebin or provide some way for the IRC bot to register information with the pastebin and somehow have the pastebin display the information on the web app? This sounds a bit harder, but works better with any application (But what other applications would even want notification of a paste?). Perhaps I will hard code it at first and then move towards a more dynamic system as I figure out how.

Mnesia configuration - I like to use mnesia for my configuration. I have a config module which provides functions to be used in setting/getting values from the mnesia config data base. I also want to use mnesia to store all of the information for the actual pastes. I hear mnesia falls apart after store a lot of data, I can imagine some of these pastes will grow to be a fair size, so I am considering using a cache for the syntax highlighted pastes. Running the application to highlight the text on every hit sounds inefficient, and storing it for every paste sounds like a waste of space, so a cache is probably a good inbetween. Right now I would like to store as many pastes as I can but will consider deleting those that are too old.

Download paste - Being able to download the paste is always very helpful. Providing a nice filename that ends in the proper extension for the language would be nice.

Browsing recent pastes - You paste to my site you loste all privacy, go figure.

File upload - Somtimes it is easier to just upload a file rather than pasting.

This sounds like a lot but I don't think it will be too bad. It seems like I should be able to do most of it fairly modular.

Step one - Come up with mnesia tables, do some research on mnesia in terms of foreign keys and possibly how to do decent QLC queries. I think learning QLC will be important, especially when a lot of pastes get put into this thing.

Step two - Get the basic form for uploading going

Step three - Come up with step three when I get there.

UPDATE
Some obvious ideas were brought to my attention

Indent - Running various languages through astyle and friends would be very helpful, some people just can't indent properly.

Customize with cookies - Store various color information in cookies so people can keep colors they enjoy. This probably won't be implemented until much later.

Differences - Highlight differences between pastes so you can show what changes have been made. This sounds kind of difficult, especially if I am outsourcing the highlighting to a third party.

Line numbers - This should be obvious

Non GUI Browsers - Yes some people use these. The download as text option should be helpful for these people, but the probably also want line numbers so a specific Non GUI version of the code might be nice, this will include line numbers.

RSS - This certainly isn't a need but might be nice, especialy as the maintainer I might want to keept track of who's pasting what.

Intelligent Mouseovers - Showing balanced paren when the mouse is over

Yaws 1.58 true_nozip bug

2006-04-04T20:24:00.000-04:00

Yaws 1.58 has a bit of a bug. If you specify dir_listings = true_nozip, it poops out. This is because the if condition is written to only handle the situation where it is true or false.

Here is my little bug fix, the problem file is src/yaws_ls.erl


47c47,54
<            if DoAllZip == true -> allzip() end,
---
>            case DoAllZip of
>                  true ->
>                      allzip();
>                  true_nozip ->
>                      [];
>                  false ->
>                      []
>              end,

klacke says he also has a fix but, as usual, sourceforge is down so he has not been able to commit it.

Fun with processes (Updated)

2006-03-31T17:04:00.000-05:00

I really need to go through all of my Erlang documentation so people like petekaz can stop making me feel small.
I had an issue with some poor Erlang code I was running where it performed a file:open but not the appropriate file:close. Not wanting to restart my application I wanted to know how I could fix this problem without shutting it down. Erlang, of course, provides a solution.
One thing that made this workable in the first place was the fact that I had no other open files besides those that needed to be closed.

So imagine for a second you have opened a number of files and lost the reference to them. For example:


(ort_bot@blong)21> [file:open("/tmp/c2.log", read) || X <- lists:seq(1, 10)].
[{ok,<0.8974.7>},
 {ok,<0.8975.7>},
 {ok,<0.8976.7>},
 {ok,<0.8977.7>},
 {ok,<0.8978.7>},
 {ok,<0.8979.7>},
 {ok,<0.8980.7>},
 {ok,<0.8981.7>},
 {ok,<0.8982.7>},
 {ok,<0.8983.7>}]

file:open causes a process to be created (this is Erlang afterall).
In the shell you can simply type i(). and get output like:


(ort_bot@blong)22> i().
Pid                   Initial Call                          Heap     Reds Msgs
Registered            Current Function                     Stack              
<0.0.0>               otp_ring0:start/2                      377     6569    0
init                  init:loop/1                              2              
<0.2.0>               erlang:apply/2                        4181   179350    0
erl_prim_loader       erl_prim_loader:loop/3                   5              
<0.4.0>               gen_event:init_it/6                   1597     1114    0
error_logger          gen_event:loop/4                        10              
<0.5.0>               erlang:apply/2                        6765     8325    0
application_controlle gen_server:loop/6                        7              
<0.7.0>               application_master:init/4              377       45    0
                      application_master:main_loop/2           8              
<0.8.0>               application_master:start_it/4          233       90    0
                      application_master:loop_it/4             5              
<0.9.0>               supervisor:kernel/1                    610     1373    0
kernel_sup            gen_server:loop/6                       12              
<0.10.0>              rpc:init/1                             610 17456475    0
rex                   gen_server:loop/6                       12              
<0.11.0>              global:init/1                          233     1246    0
global_name_server    gen_server:loop/6                       12              
<0.12.0>              erlang:apply/2                         233      275    0
                      global:loop_the_locker/1                 4              
<0.13.0>              erlang:apply/2                         233        4    0
                      global:collect_deletions/2               6              
<0.14.0>              inet_db:init/1                         233      137    0
inet_db               gen_server:loop/6                       12              
<0.16.0>              supervisor:erl_distribution/1          377      307    0
net_sup               gen_server:loop/6                       12              
<0.17.0>              erl_epmd:init/1                        233      137    0
erl_epmd              gen_server:loop/6                       12              
<0.18.0>              auth:init/1                            233       77    0
auth                  gen_server:loop/6                       12              
<0.19.0>              net_kernel:init/1                      233     3272    0
net_kernel            gen_server:loop/6                       12              
<0.20.0>              inet_tcp_dist:accept_loop/2            233      178    0
                      prim_inet:accept0/2                     10

This list goes on for awhile longer, depending on what you have done. As you scan through this output you should see something like:


<0.8974.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8975.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8976.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8977.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8978.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8979.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8980.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8981.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8982.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3              
<0.8983.7>            erlang:apply/2                         233      135    0
                      file_io_server:server_loop/1             3

All of those file_io_server's are the open files. And the Pid associated with it is the file handle. So to close all these files all you have to do is call file:close on those pids. You can create a pid give 3 numbers in the shell by using the pid function:


(ort_bot@blong)23> file:close(pid(0, 8974, 7)).                              
ok
(ort_bot@blong)24> file:close(pid(0, 8975, 7)).
ok
(ort_bot@blong)25> file:close(pid(0, 8976, 7)).
ok
(ort_bot@blong)26> file:close(pid(0, 8977, 7)).
ok
(ort_bot@blong)27> file:close(pid(0, 8978, 7)).
ok
(ort_bot@blong)28> file:close(pid(0, 8979, 7)).
ok
(ort_bot@blong)29> file:close(pid(0, 8980, 7)).
ok
(ort_bot@blong)30> file:close(pid(0, 8981, 7)).
ok
(ort_bot@blong)31> file:close(pid(0, 8982, 7)).
ok
(ort_bot@blong)32> file:close(pid(0, 8983, 7)).
ok

Now, call i() again and you'll notice all of those pesky file's have been closed. You can also do all of this from a remote machine if you have run your erl properly. For example my remote application is run on a machine called 'blong' and the node name is 'ort_bot'. I am on 'ooter' on a machine called 'osx'. So from 'osx' I can do this:


osx:~/projects/Erlang orbitz$ erl -sname ooter -setcookie cookiemonster
Erlang (BEAM) emulator version 5.4.13 [source] [threads:0]

Eshell V5.4.13  (abort with ^G)
(ooter@osx)1> 
User switch command
 --> r ort_bot@blong
 --> j
   1  {shell,start,[init]}
   2* {ort_bot@blong,shell,start,[]}
 --> c 2
Eshell V5.4.12  (abort with ^G)
(ort_bot@blong)1> i().
Pid                   Initial Call                          Heap     Reds Msgs
Registered            Current Function                     Stack              
<0.0.0>               otp_ring0:start/2                      377     6579    0
init                  init:loop/1                              2              
<0.2.0>               erlang:apply/2                         610   161416    0
erl_prim_loader       erl_prim_loader:loop/3                   5              
<0.4.0>               gen_event:init_it/6                    610      557    0
error_logger          gen_event:loop/4                        10              
<0.5.0>               erlang:apply/2                        6765     8289    0
application_controlle gen_server:loop/6                        7

Connecting to a remote shell is easy and we now have a shell on that node and can do anything from here we want (infact I've done halt(). quite a few times by accident not thinking oi!).

Alternativly, you can also use pman, which provides an interface much like i() but does more interesting stuff too. For instance you can see linked processes and kill various processe through pman. In order to use pman, on your local node simply run: pman:start().
This provide you with a window that looks like:

This looks just like i(). And from the 'node' menu you can switch nodes to view the processes on. As you can see from this screenshot I am viewing the processes on ort_bot@blong, which is a remote node.

As you can see, Erlang provides a very powerful set of tools to keep your application stable and perform various operations. It is things like this that make me glad to run code in a shell rather than a stand alone appliction. For situations like this, the power of the erlang shell is unparalleled.

Update:
Well in his infinite wisdom, after a bit of playing around petekaz came up with two functions that makes solving this particular problem all of the easier. My goal was mainy to show how to interact with the shell to get useful information about processes, but petekaz has shown me how to actually close a specific file. It seems file:open drops some useful information into ets.


[ file:close(P) || P <- processes(), {ok, "/tmp/test.erl"} == file:pid2name(P) ].

Where "/tmp/test.erl" is the file you are trying to close.
This makes use of two useful functinos. processes for starters evaluates to a list of all current proceses runninging in the node, and file:pid2name takes a pid and tells you what file it is associated with. If the pid is not a file it returns undefined.
So it seems Erlang has a complete solution to this problem.

Thanks petekaz for figuring this one out completely.

Oort

2006-03-23T22:33:00.000-05:00

Well it was pretty painful but I ripped out most of my terrible code and replaced it with pretty gen_server's and the likes. The code is still in a state of flux and needs to be polished a bit more, but it's a good start. You can gawk at it here:

svn://ortdotlove.net/Erlang/trunk/p1

Ignore the manderlbot source tree in there.

MEUG

2006-03-06T12:43:00.000-05:00

MEUG is Massachusetts Erlang User Group.
For some reason, there seem to be a lot of Erlang users in MA. I would like to get us all together semi-regularly. We can enjoy some good food, some drinks, and talk about Erlang, or whatever else comes up. Concurrency in general is an interesting topic that that is much to talk about.
I will keep people updated. If there are any MA based Erlangers interested that I am not yet aware of feel free to email me at:
orbitz AT ortdotlove.net (That is really ortdotlove) or post a comment.

Re: Re: Re: Ruby Array class sucks

2006-01-23T12:04:00.000-05:00

I have been meaning to respond to this post on the factor blog for awhile. Factor has grown a lot, and this blog tracks the development of it. Factor is the result of Forth and Lisp having babies. But the post I'm interested in doesn't have so much to do with factor but with ruby. It is in response to another post (URL at the factor site) about a complaint with Ruby's Array class. The complaint centers mainly around the Array object having far more methods than it should and quite a few that don't belong there. Slava's (factor creator) response suggests that the methods do deserve to be there and from a functional standpoint most of them make plenty of sense.

For a number of the methods in Array, I do agree with slava that they should be present. For instance, the authors complaint about Array.new being able to preset an array to a specific value is silly to me, I often want some sort of initial value to work from so I would imagine many other people are in my boat.

Around Array.transpose, I start to disagree though. transpose takes an Array and treats it like a matrix. Slava's response is:

It might surprise the author to learn that mathematically, a matrix is a two-dimensional array. In Factor, you can perform mathematical operations on vectors, such as vector addition, dot product, and so on.

Ok, so basicaly the argument is, a matrix resembles an array in some way and factor allows these sort of manipulations, thus ruby should. Well ok, let's say, yes, a matrix is a two-dimensional array, that's nice. But what does that make an Array then? An Array is also a two-dimensional array? That sounds a bit circular. Why should a method in Array depend on Array being thought of as a specific type of object. If we want to do matrix work, I suggest abstracting a matrix type, even if it's as simple as Matrix = Array. But really, it sounds like transpose should be in some sort of Matrix object.

Array.rassoc also seems a bit out of place to me. Slava says:

Yes, and there's nothing wrong with that. Association lists, while they suffer from linear lookup time, are occasionally useful where you want to have a mapping together with a certain intrinsic order. For example, Factor's generic word code takes the hashtable of methods defined on a generic, converts this to an association list, then sorts the association list according to the partial ordering of classes. Finally, the sorted association list is used to generate code.

Again, the argument of "This is ok because factor does it" does not quite fly with me. Now, when I write code and I'm not quite sure what data type I really want, but I need some sort of key->value association, I will often just use a list or array type to start out with, abstracted into some interface so when I decide what I finally need I can simply change the backend. Now, is this a good reason to put a function that treats a list like a map inside a list object? In my opinion, No.

In my opinion, I would use some sort of generic sequence object that has various methods that act on arrays and lists and other sequence objects, allowing you to perform some of these manipulations. In most languages, I would probably go as far to even make something like rassoc just be a plain function, no need to make it part of an object. But I have a feeling a lot of Ruby programmers don't feel content unless they have methods in some class.

This Array object seems to be similar to various classes in Python. Back in the day, Python developers could add methods to classes without any sort of vote. This is why the Python standard lib has lots of random modules that one would not normally think should be in a standard library, and also why Python has been making such an effort to clean up a lot of the standard classes and provide a more consistent interface to them.

Sorry this post does not actually contain anything on erlang. My next one will, I promise. Feel free to flame me in response to my Ruby thoughts, just be civil.

Port Drivers

2005-11-21T23:11:00.000-05:00

Does anyone have any good tutorials on writing ports? Google doesn't seem to return much on initial tries.

Single exit point

2005-11-17T22:43:00.000-05:00

Many programmers insist on only having the flow of control in their function end at a single point. I got wondering for a few minutes if any languages enforce this style of programming. Then I realized. Erlang has no 'return' operator, so doesn't Erlang enforce this? That sounds about right as far as I can see. So an Erlang function can only have 1 exit point. That should make them feel good.

But as was just pointed out to me in the middle of writing this, Erlang has 'throw'. There can be many of thoughs. So perhaps Erlang doesn't have 1 exit point.

On a final note:
Does having 1 exit point even matter? Who cares? The beauty of Erlang (in my opinion) is it almost forces you to write short concise functions. Every single one of my erlang functions fits on 1 screen easily, so does having multiple exit locations from there matter? In my opinion, no. I don't need to go searching through pages of code for that function to find it, I can see it, so who cares?

The Twisted Matrix

2005-09-21T19:39:00.000-04:00

It has been a long road from where I started to using Erlang. I certainly don't plan on stopping with Erlang but so far I am quite the fan of it. On this road, which finally lead me here, I have used C, C++, Java, and Python, to name a few. I still have code for a multithreaded http I was writing in C hanging around.
I still use Python quite a bit, and one of the best tools in Python I have used is the Twisted Matrix framework. Prior to discovering Erlang (well more of introduced to it by noss, which i am deeply in debt for), I felt that Python was really *the* language for socket programming. Twisted is what made me think this.
Now, just to be clear, Erlang certainly does not make Python obsolete. Don't confuse enthusiasm for Erlang with feeling every other language is useless. I introduced Python and Twisted into our development cycle at work and I am fairly pleased with the results.
For those that don't know what Twisted is, it is a framework for developing software. What makes Twisted special is they have put a lot of work into making everything work in one thread. Making a server or client that handles multiple network connections is fairly trivial in Twisted.
So what makes Twisted work how it does? A uniform eventloop. In their case it's called a reactor. There are a bunch of different kinds of reactors in Twisted. One needs to be made for whichever kind of event loop you are using. There is a select reactor (default), gtkreactor, gtk2reactor, wxwidgets reactor, and some sort of win32 reactor (I think still under development). The good thing is, most of your code can generally be written without caring about what reactor is being used. That is, atleast, the portions that don't depend on gtk or win32 or wx.
Five years ago, when the Twisted project was first created, the authors feel that Python was the best language for the job. My question is, if Twisted was started today, would Python still be the best choice. I address part of the problem in a previous post. Part of the problem that I point out is, you have to do a lot of work to force everything into the event loop. That makes code reuse more difficult, and near impossible if you need to use a proprietary library that you can't make non-blocking.
An obvious example of this is the adbapi module. adbapi module can use any DB-API 2.0 compliant module. This is to make adbapi useful. There are quite a few DB-API 2.0 compliant modules for Python so the best thing is to make use of them. adbapi's API is not asynchronous or non-blocking though. Doing queries in the Twisted reactor thread means the entire application will stall until the query is finished. To solve this, Twisted does the queries in a thread. Twisted has to fall-back on the very thing it is trying to avoid in order to work. Python is particularly bad at threading too so Twisted tries to keep the number of threads to a reasonable amount. This means the number of queries you can have going concurrently is dependent on this.
A native implementation of the postgresql protocol has been implemented. It is called pgasync. I beleive the author has commented on how much quicker a large number of queries runs in his implementation, although I cannot find the quote. But has the same problem I pointed out before. Because Twisted is all in one thread, everything has to conform to its event loop making the implementation of the pgsql protocol useless. It had to be rewritten to work well in Twisted. This implementation is also fairly useless anywhere except Twisted. I cannot use this in an application that uses an event loop other than Twisted. Wouldn't it be nice if I could use code between projects that arn't dependent on Twisted? In a COL this is a non-issue. Simply run the database code in a process. Processes are part of the language so they are part of any program.
So, to get back to my question, would Python still be the choice of Twisted today, I don't know. I asked the people of Twisted if they still would. For the most part, it seems like they didn't quite know Erlang well enough to say if they would choose it. A few developers said one of the main reasons they chose Python was for its large standard library. In particular the 'os' module was pointed out as an important module that makes Python a good choice. However, after some research, most of the 'os' module is in Erlang's standard library as well. In my opinion, I think the quality of the Erlang standard library and OTP is quite a bit better than Pythons. Python's standard library seems to have suffered from a time period where anyone put anything they wanted into it. As a result, it is large, but a number of modules are fairly poor in quality.
Even if Python has a number of modules in its standard library that are nice for building Twisted, they still need to do a lot of work to force all of this code into the Twisted event loop. If you choose a COL, then you don't have to do any work in forcing code into a single event loop. Instead, you have to do work to build the standard library that Python has. Is that a lot of work? Yes.
One could also argue, "There are a lot more Python projects than Erlang ones so there is a lot of code being written for Python that Twisted can make use of". I think there is little contest in the point that there are more Python projects and programmers. But can Twisted really make use of this code? I think, in general, no, not without work. A lot of interesting things are probably going to involve some blocking somewhere which either needs to be pushed to a thread or rewritten not to block, such as the example I have already given.
The choice to use Python is a difficult one, I think. In my opinion, Python really does not offer much that Erlang doesn't. I think, considering the services Twisted is trying to offer, a COL would be an excellent choice for it. Twisted does a lot of work trying to make asynchronous programming less confusing but writing concurrent programs is more natural. It feels more natural atleast.
I have had a lot of success using Twisted. I don't think I'd write a socket program in Python without it. I also think I would generally not write a socket program in Python these days. Twisted and Erlang seem to be trying to accomplish much the same thing, although going about things in very different ways. In the end I think something like Erlang will win out. A COL seems to be saying, the world is concurrent so lets try to let people write in this natural way. Whereas, Twisted is forcing people to write in a rather artifical and unnatural way. Asynchronous programming works once you grasp it but even still the flow of the programs is rather awkward and hard to grasp I think.
I feel that, today, something like Twisted would be better off written in a COL. Let the work go into making powerful tools instead of massaging prewritten code into the event loop.

Java And Threads (Jetty)

2005-09-20T18:52:00.000-04:00

noss in #erlang on freenode recently brought to my attention: Jetty Continuations

This is an interesting blog entry. The basic idea is, instead of using 1 thread per connection, since connections can last awhile, they use 1 thread per request that a connection has. The hope being, a connection will idle most of the time and only send requests once in awhile. The problem that they ran into is, a piece of software is using a request timeout to poll for data. So requests are now sticking around for a long time, so they have all these active threads that they don't want. So to deal with this, they use a concept of continuations so the thread can die but the request still hang around, and then once it's ready to be processed a thread is created again and the request is handled. So having all these requests hanging around that arn't doing anything is no longer a problem.
Well, this begs the question, why are you using a dynamic number of threads in the first place if you are going to have to limit how many you can even make. If the problem, in the first place, is they have too many threads running, then their solution works only for idle threads doesn't it? Being forced to push some of the requests to a continuation means they have applied some artificial limit to the number of threads which can be run. What happens then, when the number of valid active requests exceeds this limit? What then? Push active requests to a continuation and get to then when you have time? Simply don't let the new requests get handled? If they want to to use threads to solve their problem then putting a limit on them seems to make the choice of threads not a good one. Too poorly paraphrase Joe Armstrong, are they also going to put a limit on the number of objects they can use? If threads are integral to solving your problem, then it seems as though you are limiting how well you can solve the problem.

This also got me thinking about other issues involving threading in non-concurrent orientated languages. Using a COL (Concurrent Orientated Language) all the time would be nice (and I hope that is what the future holds for us). But today, I don't think it is always practical. We can't use Erlang or Mozart or Concurrent ML for every problem due to various limiting factors. But on the same token, using threads in a non-COL sometimes makes the solution to a problem a bit easier to work with. At the very least, making use of multiple processors sounds like a decent argument. But writing code in, say, java, as if it was Erlang does not work out. I think the best one can hope to do is a static number of threads. Spawning and destroying threads dynamically in a non-COL can be fairly expensive in the long run and you have to avoid situations where you start up too many threads. I think having a static number of threads i a pool or with each doing a specific task is somewhat the "best of both worlds". You get your concurrency and you, hopefully, avoid situations like Jetty is running into. As far as communication between the threads is concerned, I think message passing is the best one can hope for. The main reason I think one should use message passing in these non-COL's is, it forces all of the synchornization to happen in one localized place. You can, hopefully, avoid deadlocks this way. And if there is an error in your synchornization, you can fix it in one spot and it is fixed everywhere. As opposed to having things synchornized all over the code, god knows where you may have made an error.

I think this post most likely opened up a can of worms. I lightly touched on a lot of issues and most likely did not explain things in full. Perhaps this will raise some interesting questions.

Initial impressions of yaws

2005-09-11T19:08:00.000-04:00

If any of this post is incorrect, please feel free to post a comment and correct me.

I have recently installed yaws and I am looking at it to create a small website. It will be fairly simple. My previous web experience has been using Nevow with Twisted. Nevow allows you to create xml files and then the template engine extracts information from the xml file which is translated to function calls on an object representing the page. I like this solution. It keeps the code seperate from presentation which many people seem to suggest is a good idea. I see it as a positive purely based on working with webdesigners. I dislike doing web frontends so allowing someone to make that and giving them the bare minimum needed to let them call functions in my code seems rather nice. From my experiences with yaws, it seems to use a style that reminds me more of PHP. The major difference being that you can use Erlang terms to be transformed to HTML. Nevow has something similar to this called stan. Even with this though, the .yaws file is still not purely Erlang code, but requires escaping html with a tag. This style of making web applications seems fairly error prone and difficult to work with in a team.
I do think Erlang would make a fairly good web development language. The applications could easily be distributed over several nodes, not requiring one to use some sort of load balancer. A web app could scale quite well. But what can be done about the interface for programming? Some sort of XML system might work but I'm not convinced of that. There must be some more intuitive means of mixing code and presentation. I wouldn't be sirprised if someone has attempted to tackle this already, maybe something exists on google about it.

Parallel Project

2005-09-07T20:40:00.000-04:00

I have a study in Parallel Programming this semester. However, the teacher is fairly lenient as far as projects are concerned. I am looking for some interesting project relating to Erlang. The leading idea right now is to create some sort of distributed computing framework. The idea would be using Erlang to communicate between nodes and then have each node communicate with a local process which does the actual computing (assuming Erlang could not handle the calculations). The major implementation would be a BLAST algorithm since that seems fairly easy to distribute and could possibly have some use at my college. Other ideas include some sort of fault tolerence framework or application which handles nodes going down well. That would seem fairly easy in Erlang so that probably would not provide a semester worth of interesting work. Another possibility is a peer-to-peer chat application where each user contributes to the number of possible people to host.
Hrmm, hopefully I'll get a better idea soon.

Bookmarks

2005-09-05T20:13:00.000-04:00

My archive of bookmarks is slowly growing. It contains a Erlang section, a long with a number of other languages as well as lots of other URL's.

http://ortdotlove.net/bookmarks.html

Where concurrency shines

2005-08-20T15:30:00.000-04:00

I think that it can almost be stated as a fact that concurrency in languages that weren't designed with concurrency in mind tends to be poor. The languages I have in mind here are Python, C, C++ and similar. I have come across a few people who disagree with this statement however after questioning I have found that they have A) Not done much of anything complex with threads B) Never used a concurrently oriented language. Needless to say, I don't take their opinion very seriously. Now, obviously, you can take the time to write an application that uses threads and works well. But, with enough time, you can do just about anything, and in the time it takes to make that application one can deffinatly develope an equivalent program faster in concurrent orientated (CO) language.
Because writting decent threaded applications in other languages is so difficult there are a number of frameworks available that try to make it easier to write applications in a single thread. One of the reasons I think these frameworks will fail in comparison to a language such as Erlang for most developers is the amount of work it takes to integrate other libraries into it. For anyone that has used a framework such as Twisted, they have probably run into a situation where they have a third party library they want to use however the problem is, it blocks. For an asynchornous framework this is murder. So one has two choices. Either to run the third party library in its own thread. Obviously this is generally not what we want to do since the whole point of using the framework is to avoid threads. The other solution is to rewrite the library to integrate it into the frameworks event loop. Depending on the situation, this might be acceptable but it sure is a pain to have to do extra work to use this library. Now, a language which supports concurrency does not have this problem so much. The first solution, of running the library in a thread, works perfectly fine. You probably have 300 or 400 threads going already so it is no big deal. This makes it easy to distribute libraries for the particular language.
For a simple example. Imagine you make a really great http client in python. You can't really make a general http client because you need to take into account the various networking frameworks they might be using. If they are using twisted then it needs to integrate into the twisted event loop to be really useful. If they are using asyncore it needs to integrate into the asyncore event loop, and so on and so forth. Now take the same situation in erlang. Just throw the client in a process and you are all set. You don't have to rewrite anything. The obvious benefit of this is increased development speed.

I think it seems pretty clear that our processors and applications are moving towards more concurrent environments. Languages that can take advantage of this environment are most likely going to be the ones that make it. However I'm no fortune teller, so there is a good chance I could be wrong.

I think I tried to put too much into this one post so it might not make sense. Hopefully I got my ideas across.

Developing on the go

2005-08-19T14:46:00.000-04:00

One benefit to using erlang compared to more traditional languages is the development cycle. Generally you write code, compile, debug, write, compile, debug, until you have something you want to use. In between compile and debug you run the program. In traditional languages you shut down the application then restart it to debug again. In erlang we can skip the 'restart' and simply load the new code in. This is assuming no bugs in the code didn't cause the entire application to crash horribly.
So basically, what is going on is, if you have a logic problem or what not in your application that you wish to fix. Outside of your running application, you edit the appropriate .erl files and recompile. For example, your application consists of a.erl and b.erl. In b.erl you have a function called mogwai.
So in our example. a.erl calls b:mogwai, and b:mogwai has some sort of error in it that does not cause the application to crash but you want to fix, regardless. You fix b:mogwai's error and you want to load the new codebase in your running application. Recompile b.erl then in the shell to your application you simple do:

nl(b).

This loads the new version of b into your application and now calls to b:mogwai will use the current version of the function. For certain applications this certinaly provides a more elegant development cycle. I think this style also alters the structure of ones code. For instance, if one writes an application knowing that errors in the code can be fixed on the fly, no longer do they necesarly have to exit nicely. Rather, the application can provide a means of restarting the portions that have crashed. The application can continue working without the crashed process/code or stall until the required portion can be brought back. I'm under the impression this is a feature supervision trees offer you. A supervisor simply restarts a process if it crashes, and reports it. By restarting, a new codebase can be loaded that fixes the error.

One final note on how code replacement works. Erlang only attempts to load a new module if the call is in the form of: module:function. For instance, if you have a process in a loop something like:

loop() ->
receive
Something ->
loop()
end.

If you reload the module that this loop is defined in, the call the 'loop()' will not load the new codebase. The common idiom is something a long the lines of:

loop() ->
receive
restart ->
?MODULE:loop();
Something ->
loop()
end.

This will load the new codebase. On a final note, any function called as module:function must be exported.
Erlang certinaly provides some interesting features. Certinaly somethign like code replacement is possible in other languages, such as python (which provides a reload function to reload a module) I think erlang provides a more elegant solution. For instance I don't think Python provides a means of a module to reload itself, especially in the middle of an event loop.
However this is not a contest between code replacement in various languages. I have modified my irc bot to allow code replacement more seemlessly, however I have not allowed a decent means of bringing an irc bot back if there is an error which causes a crash. I'll have the new code online later if anyone is interested.

Erlang and strings

2005-08-16T23:10:00.000-04:00

A lot of people complain about strings in erlang. I am one of them. Right now I am under the impression a string type needs to be added to erlang. Joe Armstrong thinks that instead of a string we simply need a character type. My complaint with that is there is no decent container for the character type. In erlangs we have tuples, binaries, and lists. Tuples are meant to store a fixed number of objects and do not have operations on them to perform operations such as iterate through them. The element/2 function allows you to access an index of a tuple but that isnt' very useful for iterating through. Binaries might be nice, but there are no functions to nicely deal with binaries as strings. Lists are what we currently have and I am not pleased. Using a linked list to store a string certinaly seems unreasonable in any other language. You have to store a character value and a link to the next node. This is a lot of memory for a string. The other problem with these containers is none of them allow O(1) access to indecies as far as I know. Am I wrong here? I suppose the question then is, is that a problem? I am under the impression that one generally wants O(1) access. For instance, if you have an index in the string and need to access it and surrounding indecies repeatedly.

http://schemecookbook.org/view/Erlang/StringBasics has a quote supposedly from the sendmail people:

But Erlang's treatment of strings as lists of bytes is as elegant as it is impractical. The factor-of-eight storage expansion of text, as well as the copying that occurs during message-passing, cripples Erlang for all but the most performance-insensitive text-processing applications.

This is in reference to their load balancing software. Is this true? I am inclined to think that it certinaly uses a lot of memory used up, but most text-processing is going to require touching every character in a string anyways won't it? What exactly is performance intensive text-processing? Does anyone have any ideas? If one is going to be iterating through the string they can use a binary to store the byte values. The problem with this is that none of the string functions work on binaries. I'm under the impression a string container type will solve some problems. Using integers as the character values seems like a fine idea to me, as people like to point out it makes dealing with unicode slightly easier.

What problems would having a character type solve? Maybe in the morning I'll be able to think of something.

Identd as done as I care

2005-08-16T20:55:00.000-04:00

The identd is as done as I'm interested in right now. It works atleast. Instead of worrying about how to figure out who belongs to an actual port I just return a random ident value for any input. However, the function it uses to make this is a variable you pass to the server so it is not very difficult to give it a different function. To run it, simply compile all the files then do
identd:start(SomePort, {random_identd, random}).

There is no clean shutdown, just kill your shell.

You can download it here.

Identd

2005-08-15T23:34:00.000-04:00

I think the basic design for my identd is going to be:

Start a process which takes a port and a function.
On a new connection, start a process to handle the connection with the function given.
Go back to waiting.
The new process will read in the port numbers, parse them out, then call the function given with the port information
The function does what it needs to and returns the information
The process responds on the socket with the correct information.

I think this would work good with gen_server behavior, unforunatly I don't quite understand superivsion tree's that well. I will write it the ad-hoc way first then once I figure out the correct method rewrite it that way.
This framework shouldn't be too hard, making a correct identd function which actually gets the user from the ports might be. Basic one will just return a random identd.

IRC Bot

2005-08-15T22:38:00.000-04:00

Here is the code for the latest revision of my IRC Bot. It isn't made to be use friendly right now so don't expect it to work right off the bat.

I think to get it started you'll need to do the following:

Compile everything, be sure to add the inc directory to your include path.
Start it with a node name and set a mnesia directory.
Call p1_db:start(). Then p1_db:create_tables().
Then call irc_bot:add_bot (Maybe it's addbot?). It takes a tuple, see code to figure it out.
p1_main:start()
When you are finished: bot_server ! stop. The beauty of erlang lets you do this from another node on another machine too, if you so desire.

The code can be found here.

The only other erlang irc bot I've found is manderlbot which can be found on freshmeat. I think it is a bit better designed than mine and has the intention of other people using it in mind where as mine is more of me just playing around. If there is an interest in it perhaps I will do more with it.

Initial Post

2005-08-15T22:09:00.000-04:00

I will be posting my various erlang accomplishments here. My intended goal is to write a smtpd in Erlang. I will have various posts on that in the future. So far I would not describe myself as a very good programmer but I am working on that. I have written portions of an erlang irc bot. It does not do very much, although it has the ability to relay chats between channels on multiple networks and supports some concept of factoids. My next mini project is a plugable identd. This will be fairly small and simply provide the ability to give it a function that creates a response.
Feel free to post responses to my post, I don't mind constructive criticism. The hope is to make my projects better.