Purity, laziness, and stupid compiler tricks

So now we have a pointer sized (on x86-32 Linux anyway), type-safe concurrenc ry primitive in our MVar<T>. I'm going to add an additional operation, and we're going to talk about the ramifications.

First, we need to add it to ptrmvar32:

  template<typename F>
  void* pure_modify(F f)
  {
    uintptr_t curr;
    while(1) {
      curr = m_val;
      if( curr == 0 )
      {
        if( __sync_bool_compare_and_swap(&m_val, 0, 1) )
          futex_wait(&m_val, 1);
      } else if( curr == 1 ) {
        futex_wait(&m_val, 1);
      } else {
        void *new_val = f(reinterpret_cast<void*>(curr & ~1));
        if( __sync_bool_compare_and_swap(&m_val, curr, new_val) )
           break;
      }
    }
  }

We're going to add this to the type-safe version as well before we get into it, so don't worry if this looks confusing.

private:
  template<typename F, typename V>
  struct AdapterF
  {
    F f;
    std::auto_ptr<V>* mem;
    void* operator()(void *in)
    {
      V r = f(*static_cast<V*>(in));
      mem->reset(new V(r));
      return static_cast<void*>(mem->get());
    }
  };

public:
  template<typename F>
  T pure_modify(F f)
  {
    std::auto_ptr<T> mem;
    AdapterF<F,T> adapter;
    adapter.f = f;
    adapter.mem = &mem;
    m_impl.pure_modify(adapter);
    return *mem.release();
  }

Because this is C++, there is some noise with regards to memory management, but it should be pretty clear what this new operation does. It takes the current value of the MVar, applies a function to the value, and returns a new value tha t is put into the MVar. Now, the analogous operation for Haskell is modifyMVar/m odifyMVar_. Interestingly the type of the function that the Haskell modifyMVar t akes is

  a -> IO a

This is because Haskell's modifyMVar has semantics more like the following:

  template<typename F>
  T haskell_modify(F f)
  {
     T val = take();
     struct ValRestorer {
        T val;
        bool restore;
        MVar<T> *self;
        ~ValRestorer() { if(restore) self->put(val); }
        ValRestorer(T val_, MVar<T> *self_) : val(val_), self(self_),
        restore(true) {}

        void Dismiss() { restore = false; }
     } restorer(val, this);
     T new_val = f(val);
     put(new_val);
     restorer.Dismiss();
  }

In other words, Haskell's modify is to make the update transactional in the face of exceptions in the modifying code. To properly use modify, you have to ma ke sure all the threads take from the mvar before they put to it.

I called attention to the type of modifyMVar earlier, and also by naming my m ethod pure_modify. As should be obvious from the code, the user supplied functio n may be called many times (although we hope it isn't in the common case). In Ha skell, the user supplied function would have to have the type

a -> a

This is wonderful! Wonderful because we can actually express it. Among other things, we know the user supplied function won't take any other locks for instan ce, so modification is deadlock free. The other great thing, is that we can feel comfortable calling it as many times as we need, because beign a pure function the observable effect is that it atomically modified the value in the MVar.

Often when we think about purity and how it enables laziness (or is it the ot her way around?), we think in terms of functions being called less often (someti mes we even think laziness implies automatic memoization, this is not the case, and if you think about the memory usage you'll quickly realize why). But here, w e can leverage the same properties of pure code to spend less time blocked or wa iting, and hopefully, in the common case waste less CPU time.

Finally, see if you can see what classic "lock-free programming" bug I've int roduced into this code (or bugs? There's at least one) by adding this pure_modif y operation.

Implementing Haskell-style MVars in C++ using futexes

Last time we talked about what Linux futexes were. Now, I want to use them to implement a concept from Haskell called an MVar. An MVar can be thought of as concurrent queue with a size of 1, that is it is a box which you can put things in, and take things out safely from multiple threads. The basic operations are two:

• put(T value)


• T take()

When the MVar is empty, take'ing blocks, when it is full, put'ing blocks. Real Haskell MVars have guarantees with regards to fairness, we're not going to address those here. In fact, we're going to do a "cute" implementation, and it has several flaws. First, it's only going to work on x86-32, this will not be a portable implemnetation. But this lets us be "cute", our MVar is going to be only the size of an int. Below is `ptrmvar32`, it is a 32bit void* MVar implementation that we we'll use to build our MVar<T>. NULL will represent empty, and we'll use the LSB to note whether we need to wake anyone up (using only one bit for this is one of the flaws).

#ifndef PTRMVAR32_H
#define PTRMVAR32_H
#include <stdint.h>
#include <assert.h>
class ptrmvar32
{
  uintptr_t m_val;
  static char s_pointers_are_32_bits[sizeof(void*) == 4 ? 1 : -1];
  static void futex_wait(void *, uintptr_t);
  static void futex_wake(void *);
  public:
  ptrmvar32(void *initial_value) : m_val(reinterpret_cast<uintptr_t>(initial_value))
  {
    assert(m_val);
  }

  ptrmvar32() : m_val(0)
  {}

  void* take()
  {
    uintptr_t curr;
    while(1) {
      curr = m_val;
      if( curr == 0 )
      {
        if( __sync_bool_compare_and_swap(&m_val, 0, 1) )
          futex_wait(&m_val, 1);
      } else if( curr == 1 ) {
        futex_wait(&m_val, 1);
      } else {
        if( __sync_bool_compare_and_swap(&m_val, curr, 0) )
        {
          if( curr & 1 )
          {
            futex_wake(&m_val);
          }
          curr &= ~1;
          return reinterpret_cast(curr);
        }
      }
    }
  }

  void put(void *val)
  {
    const uintptr_t new_val = reinterpret_cast<uintptr_t>(val);
    uintptr_t curr;
    while(1) {
      curr = m_val;
      if( curr == 0 )
      {
        if( __sync_bool_compare_and_swap(&m_val, 0, new_val) )
          return;
      } else if( curr == 1 ) {
        if( __sync_bool_compare_and_swap(&m_val, 1, new_val) ) {
          futex_wake(&m_val);
          return;
        }
      } else {
        if( __sync_bool_compare_and_swap(&m_val, curr, curr | 1) ) {
          futex_wait(&m_val, curr | 1);
        }
      }
    }
  }

  void* unsafe_value()
  {
    return reinterpret_cast<void*>( m_val & ~1);
  }
};
#endif

ptrmvar32.cpp contains the implementation of futex_wake and futex_wait which are wrappers around the futex syscall

#include "ptrmvar32.h"
#include &t;linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <limits>

void ptrmvar32::futex_wait(void *on, uintptr_t when)
{
  syscall(__NR_futex, on, FUTEX_WAIT, when, NULL, 0, 0);
}

void ptrmvar32::futex_wake(void *on)
{
   syscall(__NR_futex, on, FUTEX_WAKE, std::numeric_limits<int32_t>::max(), NULL, 0, 0);
}

As you can see futex_wake wakes up everyone, not just one waiter. This is because someone could be waiting to take and someone could be waiting to put and if we wake the wrong one of the two we'll never wake up. If this situation does actually occur we end up in thudering herd territory.

Next we build our typesafe, templated version on top of this:

#include "ptrmvar32.h"

template<typename T>
class MVar
{
  ptrmvar32 m_impl;

  public:
  MVar() : m_impl()
  {}

  MVar(const T& val) : m_impl(static_cast(new T(val)))
  {}

  void put(const T& val)
  {
    T* p = new T(val);
    m_impl.put(static_cast(p));
  }

  T take()
  {
    T *p = static_cast(m_impl.take());
    T r(*p);
    delete p;
    return r;
  }

  ~MVar()
  {
    delete static_cast(m_impl.unsafe_value());
  }
};

Now put and take use new and delete, really we should be using a thread local allocator here, but I got too lazy to implement that part. Maybe next time. Ignoring that, you can see that this is a very light weight primitive, only taking 4 bytes. The pthread based implementation would take at least a mutex and condition variable, probably two condition variables to avoid the problem of waking up the wrong threads that this implementation is suspectible to. However, this is implemented the way it is to set up for next time, where we are going to talk about the implications of laziness and purity, and the operation that Haskell doesn't provide but could.

Here's a sample program making use of the MVars:

#include "mvar_template.h"
#include <string>
#include <iostream>
#include <pthread.h>

using namespace std;

namespace
{
  MVar<string> in;
  MVar<string> out;

  void *worker(void *)
  {
    cout << "waiting for value" << endl;
    string v = in.take();
    cout << "got value: " << v << endl;
    v += " gotten";
    out.put(v);
    return NULL;
  }

}

int main()
{
  cout << sizeof(in) << endl;
  string s = "in";
  pthread_t t;
  pthread_create(&t, NULL, &worker, NULL);
  pthread_detach(t);
  in.put(s);
  string r = out.take();
  cout << "got " << r << endl;
}

Linux threading primitives: the futex

Linux and glibc support POSIX threads. Unsurprisingly, POSIX concepts like mutexs, condition variables, etc. are not baked into the kernel. How then does glibc's implementation of pthreads for Linux work? Well, for mutual exclusion and signaling (that is mutexes, condition variables, semphores, etc.) pthreads on Linux generally uses the "futex", which is an abbreviation for "fast user-space mutex". This is a somewhat deceptive name. The actual futex system call's capabilities bring more to mind a "fast user-space semaphore" but I guess "fuphore" isn't quite as catchy. We'll assume the name is descriptive of usage rather than the mechanism.

The futex syscall itself has 6 parameters.

int futex(int *uaddr, int op, int val, const struct timespec *timeout,

int *uaddr2, int val3);

The first is always the address of the futex. A futex is just an int (this brings to mind, at least to me, NT's keyed events), generally representing the count of the semaphore. The identity of that int (that is to say, not the _value_ of its address, because that can vary across processes) is how the kernel distinguishes futexes. This is a neat trick, avoiding the requirement of a global namespace (such as with named events, mutexes etc. in Windows), while allowing for it by leveraging existing mechanisms (mmap, SysV shared memory, etc.). Of course, by typing this to the virtual address space of the process, this can't serve as cluster wide mechanism (mmaping a file shared over NFS is not going to be sufficient for example).

The fourth parameter to the call is an optional timeout, which applies when using some operations. The third, fifth and sixth parameters meaning vary based on the operation.

The operation is of course the second parameter. I'm only going to talk about two of the most basic operations, FUTEX_WAIT and FUTEX_WAKE.

For FUTEX_WAIT, the val parameter is the current value of *uaddr. When you call futex with the wait operation, it checks atomically that *uaddr == val. If not, you return from futex right away. Otherwise, you FUTEX_WAIT until someone FUTEX_WAKEs you up.

FUTEX_WAKE wakes val processes (for the purposes of this discussion thread and process are synonymous) waiting on the futex uaddr.

These two operations, in conjunction with atomic operations on int values give us everything we need to implement a semaphore. We can then use that semaphore to implement various other synchronization primitives (a mutex can be modelled as a binary semaphore for example).

The "fast" and the "user-space" parts both refer to the idea that you don't actually call the system call save in the case of contention. Rather you platform specific code to increment and decrement *uaddr. If there is no contention, we need never go to the kernel to arbitrate.

To demonstrate this, I'm going to show a small library for working with futexes. Note that I'm not using them entirely correctly, which you will discover if you check out the "further reading" section.

First, we'll create an API for dealing with semaphores implemented with futexes. it is written in C, and I have named the header simple_futex.h

#ifdef __cplusplus

extern "C" {

#endif

struct simplefu_semaphore {

int avail;

int waiters;

};

typedef struct simplefu_semaphore *simplefu;

void simplefu_down(simplefu who);

void simplefu_up(simplefu who);

#ifdef __cplusplus

}

#endif

Our sempahore consists of two operations, simplefu_down and simplefu_up, which perform as one expects a semaphore to. The avail member of the struct represents the count of the semaphore, the waiters member is used for tracking if we need to issue a wake operation.

Here, in simple_futex.c is the implementation:

#include "simple_futex.h"
#include <linux/futex.h>
#include <sys/syscall.h>

void simplefu_down(simplefu who)
{
int val;
do {
val = who->avail;
if( val > 0 && __sync_bool_compare_and_swap(&who->avail, val, val - 1) )
return;
__sync_fetch_and_add(&who->waiters, 1);
syscall(__NR_futex, &who->avail, FUTEX_WAIT, val, NULL, 0, 0);
__sync_fetch_and_sub(&who->waiters, 1);
} while(1);
}

void simplefu_up(simplefu who)
{
int nval = __sync_add_and_fetch(&who->avail, 1);
if( who->waiters > 0 )
{
syscall(__NR_futex, &who->avail, FUTEX_WAKE, nval, NULL, 0, 0);
}
}

A few things. This code is gcc specific, I'm using its atomic built-ins. I am using an atomic compare and swap to decrement the count only if doing so would not reduce the count to below zero. I am using an additional count to track if the semaphore ahs been contended. The futex documentation says you should use atomic increments/decrements and treat -1 as being contended. Since this was for my own edification I decided to use a mechanism that I felt was more clear. I would not attempt to use this semaphore in the real world.

The basics of the down operation are "Try to atomically decrement the avail member, if that is not possible, note that we are going to wait by incrementing waiters and then wait on the futex. Then decrement waiters and try again." The basics of the up operation are "increment the available count. Additionally if there are waiters, wake as many of them that could proceed given the current count.".

Now that we have a semaphore implementation we can endeavorer to come up with a use for it.

In this program, we start a child process and wait for it to perform some initialization before using it further. In this example, the initialization is represented by a sleep. main.c:

#include <stdio.h>

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>
#include <stdlib.h>
#include <assert.h>

#include "simple_futex.h"

int main()
{
int lockfile = open("ipc_lock", O_RDWR);
assert(lockfile != -1);
simplefu sema = mmap(NULL, sizeof(*sema), PROT_READ|PROT_WRITE,
MAP_SHARED, lockfile, 0);
assert(sema != MAP_FAILED);

int pid = fork();
assert(pid != -1);
if( pid == 0 ) { // child
printf("Initializing...\n");
sleep(10);
printf("Done initializing\n");
simplefu_up(sema);
exit(0);
}
printf("Waiting for child...\n");
simplefu_down(sema);
printf("Child done initializing\n");

return 0;
}

ipc_lock is simply an 8 byte file (the platform specific size of *sema), filled with zeros. You can make your own with dd if=/dev/zero of=ipc_lock bs=8 count=1.

If we run this guy we get:

% ./a.out

Waiting for child...

Initializing...

Done initializing

Child done initializing

Now, coming back to the "fast" and "user-space" part of this, if there's no contention, there's no need to make a syscall. We can demonstrate this by using a slightly different program, main2.c The only difference between main2.c and min.c is as follows:

% diff -du main.c main2.c
--- main.c      2010-11-21 16:57:50.000000000 +0000
+++ main2.c     2010-11-21 20:12:24.000000000 +0000
@@ -25,6 +25,7 @@
 simplefu_up(sema);
 exit(0);
}
+  sleep(15);
printf("Waiting for child...\n");
simplefu_down(sema);
printf("Child done initializing\n");

That is, the additional of a sleep(15) call before we start waiting for the child. This represents some other, real work that the other process may be doing at this time instead of waiting for its child to be ready. First, let's confirm that futex is called in the first program:

% strace -o traces ./a.out && grep futex traces
Initializing...
Waiting for child...
Done initializing
Child done initializing
futex(0xb7861000, FUTEX_WAIT, 0, NULL)  = 0

Now, let's compare to the second program, where we're off busy doing something instead of immediately waiting for the child:

% strace -o traces ./a.out && grep futex traces
Initializing...
Done initializing
Waiting for child...
Child done initializing

As you can see, we did not have occasion to actually go to kernel land for this version.

If you are interested in futexes you find out more in the man pages, http://www.kernel.org/doc/man-pages/online/pages/man2/futex.2.html and http://www.kernel.org/doc/man-pages/online/pages/man7/futex.7.html as well as the original paper http://www.kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf

Last Call - Tim Powers

This is a book about poker with Tarot cards. If you've ever read a Stephen King book and enjoyed it, especially Dark Tower before it got all meta-fictiony on us, you'll probably like this. Towards the end it does get a little too "and this is how this actually works" which I did not appreciate, but over all a good one.

Stupid C++ tricks

Ever wanted to downcast something, but not too far down? Me either really, but just in case I came up with this:

template<typename Target, typename Excluding, typename Source>
struct exclusive_cast {
static Target* cast(Source *s) {
  if( ! dynamic_cast<Excluding *>(s) ) {
    return dynamic_cast<Target *>(s);
  }
  return NULL;
}
};

template<typename Ex1, typename Ex2>
struct ExcludingBoth {};

template<typename Target, typename Ex1, typename Ex2, typename Source>
struct exclusive_cast<Target, ExcludingBoth<Ex1, Ex2>, Source> {
static Target* cast(Source *s) {
  if( ! dynamic_cast<Ex1 *>( s ) ) {
    return exclusive_cast<Target, Ex2, Source>::cast(s);
  }
  return NULL;
}
};

That was the header, exclusive_cast.hpp. Now here's a little test program that makes sure it does what I think it does:

#include <iostream>
#include "exclusive_cast.hpp"

class A {
  virtual void rtti_rules() {}
};
class B : public A {};
class C : public B {};
class D : public B {};
class E : public B {};
int main() {
  B b;
  C c;
  D d;
  E e;
  A *ab = &b;
  A *ac = &c;
  A *ad = &d;
  A *ae = &e;

  if( exclusive_cast<B, C, A>::cast(ab) ) {
    std::cout << "correct" << std::endl;
  } else {
    std::cout << "incorrect" << std::endl;
  }

  if( exclusive_cast<B, C, A>::cast(ac) ) {
    std::cout << "incorrect" << std::endl;
  } else {
    std::cout << "correct" << std::endl;
  }

  if( exclusive_cast<B, ExcludingBoth<C, D>, A>::cast(ad) ) {
    std::cout << "incorrect" << std::endl;
  } else {
    std::cout << "correct" << std::endl;
  }
  typedef exclusive_cast<B, ExcludingBoth<C, ExcludingBoth<D, E> >, A> complicated;

  if( complicated::cast(ae) ) {
    std::cout << "incorrect" << std::endl;
  } else {
    std::cout << "correct" << std::endl;
  }
  if( complicated::cast(ad) ) {
    std::cout << "incorrect" << std::endl;
  } else {
    std::cout << "correct" << std::endl;
  }
  if( complicated::cast(ac) ) {
    std::cout << "incorrect" << std::endl;
  } else {
    std::cout << "correct" << std::endl;
  }
  if( complicated::cast(ab) ) {
    std::cout << "correct" << std::endl;
  } else {
    std::cout << "incorrect" << std::endl;
  }
  return 0;
}

A possible improvement might be to nest the template parameter Source inside the struct for the cast function so wouldn't need to name Source necessarily.

Something I wish terminated but doesn't

Sure,
data Weekday = Sun | Mon | Tue | Wed | Thu | Fri | Sat deriving Enum is fine.

But wouldn't it be fun if this actually worked?
let as@[sun, mon, tue, wed, thur, fri, sat] = [1..length as], unfortunately attempt to evaluate mon for instance, and it doesn't terminate (at least as far as I know, I didn't wait for all eternity for it to finish). Needs -XDWIM I suppose.

A simple infix calculator in Haskell

I saw this on reddit and knew that my infix calculator was hanging around, so I decided to post it for some contrast.

There are a few problems, mainly that I had this desire to "not cheat" when I wrote it so I didn't use nearly as many Parsec functions as I could have. Also it's not very user-friendly, the only way to quit is Ctrl-C or EOF and EOF causes an error to be displayed. That said, here it is in all it's "glory". Compile with ghc --make Main.hs (or whatever you named the file, if you bothered).

module Main where
import Text.ParserCombinators.Parsec
import Control.Monad
import Control.Monad.Error
import System.IO

data Expr a = Number a
            | Add (Expr a) (Expr a)
            | Mul (Expr a) (Expr a)
            | Sub (Expr a) (Expr a)
            | Div (Expr a) (Expr a)
            | Negate (Expr a)
            deriving (Show, Eq)

data AddOp = Plus | Minus
data MulOp = Times | Over

evaluate :: (Fractional a, Monad m) => Expr a -> m a
evaluate (Negate x) = liftM negate (evaluate x)
evaluate (Div x y)  = do x' <- (evaluate x)
                         y' <- (evaluate y)
                         if y' == 0 then fail "Division by zero"
                                    else return $ x' / y'
evaluate (Sub x y)  = liftM2 (-) (evaluate x) (evaluate y)
evaluate (Mul x y)  = liftM2 (*) (evaluate x) (evaluate y)
evaluate (Add x y)  = liftM2 (+) (evaluate x) (evaluate y)
evaluate (Number x) = return x



pDigit = oneOf ['0'..'9']
pSign = option '+' $ oneOf "-+"
pDigits = many1 pDigit
pDecimalPoint = char '.'
pFracPart = option "0" (pDecimalPoint >> pDigits)

number = do sign <- pSign
            integerPart <- pDigits
            fracPart <- pFracPart
            expPart <- pExp
            let i = read integerPart
            let f = read fracPart
            let e = expPart
            let value = (i + (f / 10^(length fracPart))) * 10 ^^ e
            return $ Number $ case sign of
                 '+' -> value
                 '-' -> negate value
         where pExp = option 0 $ do
                             oneOf "eE"
                             sign <- pSign
                             num <- pDigits
                             let n = read num
                             return $ if sign == '-' then negate n else n

whitespace = many $ oneOf "\n\t\r\v "

term = do t <- term'
          whitespace
          return t
       where term' = (try number) <|> negTerm <|> parenExpr

negTerm = do
             char '-'
             whitespace
             e <- term
             return $ Negate e

expr = do
          first <- mulTerm
          ops <- addOps
          return $ foldl buildExpr first ops
       where buildExpr acc (Plus, x) = Add acc x
             buildExpr acc (Minus, x) = Sub acc x

addOp = do operator <- oneOf "+-"
           whitespace
           t        <- mulTerm
           return $ case operator of
                         '-' -> (Minus, t)
                         '+' -> (Plus, t)

addOps = many addOp


parenExpr = do char '('
               e <- expr
               char ')'
               return e

mulTerm = do first <- term
             ops <- mulOps
             return $ foldl buildExpr first ops
          where buildExpr acc (Times, x) = Mul acc x
                buildExpr acc (Over, x) = Div acc x

mulOp = do operator <- oneOf "*/"
           whitespace
           t        <- term
           return $ case operator of
                         '*' -> (Times, t)
                         '/' -> (Over, t)

mulOps = many mulOp
calculation = do whitespace
                 e <- expr
                 eof
                 return e

evalPrint s = case (parse calculation "" s) of
                   Right x -> case evaluate x of
                                   Right v -> print v
                                   Left err -> putStrLn $ "Error: " ++ err
                   Left err -> putStr "parse error at " >> print err

main =  getLine >>= evalPrint >> main

The Church Code

You may have heard of the lambda calculus, in which everything is a function. And you may have asked yourself, as I have, ok that's great, but I how do I do anything with just functions? How do I create all those datastructures I've become acustommed to? Do I need to build the datastructures I've become accustomed to? If so, how do I do it?

One answer to this question, is the Church encoding, named after Alonzo Church who first came up with the idea. So how do you use Church encoding?

Well, before I get into that I'm going to describe the environment I'm going to use. I'm going to use the ruby programming language, because it's familar to me, and Haskell's type system makes it difficult to use Church encoding. Secondly I'm gonna define a convience method in ruby called curry:

def curry(&l)
  lambda { |a| lambda { |b| l[a,b] } }
end

curry takes a block of two arguments and transforms it into a Proc w/ a single argument that returns another Proc of a single argument. This is just to save me typing later.

Now that that's out of the way we can start talking about how to turn our functions into values. Consider one of the simplest values in most programming languages, true and false.

# we are going to use the names ctrue and cfalse because
# ruby takes exception to our using true and false
# as variables
ctrue = curry { |a,b| a }
cfalse = curry { |a,b| b }

Now if you didn't stop reading a while ago because you already know all about this stuff, you may be wondering, how are those functions true and false? Actually, let's just make sure that curry method makes sense first.

curry { |a,b| a } -->
lambda { |a| lambda { |b| a } }
# So to call ctrue we'd do the following:
ctrue[1][0] #=> 1

The reason for currying all these functions should become clear fairly soon. Now that that's out of the way, how does this give us true and false? Well, think about an if statement. Now imagine if was defined as a function, like the following:

cif = lambda { |condition| curry { |true_branch, false_branch|
  condition[true_branch][false_branch] } }

Now we can for instance write not:

cnot = lambda { |cond| cif[cond][cfalse][ctrue] }

Now if you've picked up on what's going on with cif you've realized that it's not really necessary. ctrue and cfalse are true and false, and they are also if.

So we can write cnot as

cnot = lambda { |cond| cond[cfalse][ctrue] }

And if we cheat for a moment, we can discover which value a given church encoded boolean is by using the following function

cbool_to_rbool = lambda { |cond| cond[true][false] }

Now we can make sure our cnot method works

>> cbool_to_rbool[ctrue]
=> true
>> not_ctrue = cnot[ctrue]
=> #<Proc:0x02b9876c@(irb):1>
>> cbool_to_rbool[not_ctrue]
=> false

So now what? We've managed to come up with bools out of functions. Doesn't seem very useful yet, although maybe kind of entertaining.

Well we can now also define and and or. A and B is true if A is true and B is true. Put another way, A and B is true if neither A nor B are false.

cand = curry { |a,b| a[b][a] }

So let's walk through this function
if a is true, it will take a the left value and give us b. If b is true, we have true and true -> true, which is what we wanted. if b is false, we have true and false -> false which is again, what we wanted. If a is false, we get a so we had false and anything -> false, which is what we want as well.

Next we can define or.

cor = curry { |a,b| a[a][b] }

If is a true, we get a, if a is false we get b. Therefore we will only get a false result if both a and b are false. Now that we have and, or and not, we can build boolean operation (xor, etc.), and we've done it using only functions. No datastructures in sight.

The next thing we are going to try, is to create some datastructures out of pure functions. The first thing we will create is a pair, that is a list of two values.

cpair = curry { |a,b| lambda { |f| f[a][b] } }
cfst = lambda { |apair| apair[ctrue] }
csnd = lambda { |apair| apair[cfalse] }

cpair is a 3 argument function, it takes the first value for the pair, the second value for the pair, and a function that takes two arguments to use the pair.cfst will let us extract the first value from a pair, and csnd will allow us to extract the second value from a pair. Let's try it out:

>> pair_of_values = cpair["Ok"][5]
=> #<Proc:0x02b7ec40@(irb):12>
>> csnd[pair_of_values]
=> 5
>> cfst[pair_of_values]
=> "Ok"

Now you can see the purpose of using curried functions. It makes it easier for us to partially apply our functions so we can perform multiple operations with an argument of true, selecting the first value. You can also see that we can if we want create tuples of any arity. Since we already have true and false, one way to encode numbers could be to have an N-tuple of bits (true and false) and define the arithmetic operators in terms of logical operations on bits, like the way the ALU of a processor works. An interesting idea, but this is not how Church actually defined numbers with functions.

Instead, he represented natural numbers as the nth composition of a function with itself:

zero = curry { |f, x| x }
one = curry { |f,x| f[x] }
two = curry { |f,x| f[f[x]] }

Writing this definitions can be a bit tedius, so we can define a successor function:

succ = lambda { |n| curry { |f,x| f[n[f][x]] } }
three = succ[two]
four = succ[three]
.
.
.

We also define a function to convert our church numerals to ruby integers so we can see what's going on:

cnum_to_rnum = lambda { |n| n[lambda { |x| x + 1 }][0] }

>> cnum_to_rnum[two]
=> 2

What's happening is that n is composing the function lambda { |x| x + 1 } n times, so in the case of two, it is twice. We then feed it an initial value of zero, so 0 + 1 + 1 = 2.

We can also add our church numerals

plus = curry { |m,n| curry { |f,x| m[f][n[f][x]] } }

>> cnum_to_rnum[plus[two][four]]
=> 6

We can also define multiplication, a predecessor function etc. But I'm getting bored of church numerals so lets move on into how you create algebraic data types. This is going to allow us to create linked lists, trees, pretty much any data structure you can have in a pure functional language.

In Haskell, there is a type Maybe a, (ML has the same type, only they spell it 'a option). The definition in Haskell looks like:

data Maybe a = Just a | Nothing

That is, any value of Maybe Int for instance will either be Nothing or Just some integer value.

We can define this same data structure using just functions. Each constructor, Just and Nothing will be a function. Each value of Maybe a will be a function that takes a function (a -> b) and a value ( b ).

just = lambda { |value| curry { |f,x| f[value] } }
nothing = curry { |f,x| x } # if you recall this is also the definition of cfalse

Haskell also has a type Either a b whose definition looks like:

data Either a b = Left a | Right b

You may have noticed that Maybe a is just a special case of Either a b where we don't care about the second value. Again, we can define this type using only functions. We will have two functions left and right. Both will take a value, and return a function that takes two arguments, two functions, one from a to c and the other from b to c.

left = lambda { |value| curry { |f,g| f[value] } }
right = lambda { |value| curry { |f,g| g[value] } }

Given that an N-tuple can be represented in pairs, and that nested Eithers give us all the sum-types we need we can represent almost any datatype you can define in Haskell (barring things like strictness annotations, FFI, etc.) using pure functions.

For instance, we can define a linked list. In Haskell the definition might look like:

data List a = Cons a (List a) | Empty

Like maybe or either we will have two constructor functions cons, and empty
cons will take two inputs, a head and a tail and return a function taking two functions. The first one will take as parameters the head and the tail, the second will be a value to use if the list is empty. Empty will simple be a function that takes two functions, with the same parameters as the function returned by cons.

cons = curry { |h,t| curry { |cf, ev| cf[h][t] } }
empty = curry { |cf, ev| ev }

Now we can write first and rest to get the first item of the list
and the rest of the list:

first = lambda { |alist| alist[ctrue][nil] }
rest = lambda { |alist| alist[cfalse][nil] }

>> list = cons[1][cons[2][empty]]
=> #
>> h = first[list]
=> 1
>> t = rest[list]
=> #
>> first[t]
=> 2

We can also write the function map for instance:

map = curry { |f,l| l[curry { |h,t| cons[f[h]][map[f][t]] }][empty] }

>> l2 = cons[1][cons[2][cons[3][empty]]]
=> #<Proc:0x00002b1909def588@(irb):10>
>> l3 = map[lambda { |x| x.to_s }][l2]
=> #<Proc:0x00002b1909def588@(irb):10>
>> first[l3]
=> "1"
>> first[rest[l3]]
=> "2"
>> first[rest[rest[l3]]]
=> "3"

Given that we've defined church numerals earlier we can of course use them instead of
ruby numbers. Strings can be represented as lists of characters, and characters as integers, which again can be represented using church numerals. Basically, all you need are functions. I hope you've learned something, or were at least mildly entertained.

Let's eval some strings

List comprehensions are neat, but ruby doesn't have em. That's ok, we've got string eval!

module Enumerable
  def concat_map(&f)
    inject([]) { |a, b| a.concat(f.call(b)) }
  end
end


def guard( b )
  if b
    [nil]
  else
    []
  end
end

def r( v )
  [v]
end

def comp( s, b = binding )
  before_bar, after_bar = s.split("|")
  before_bar.gsub!(/\A\s*\[/, '')
  after_bar.gsub!(/\]\s*\z/, '')
  components = after_bar.split(/;/)
  gen_exprs, guard_exprs = components.partition { |e| e =~ /<-/ }
  final = "r(#{before_bar})"
  final = guard_exprs.reverse.inject(final) { |s, e| "guard(#{e}).concat_map { #{s} }" }
  final = gen_exprs.reverse.inject(final) { |s, e|
    var, expr = e.split("<-").map { |c| c.strip }
    "(#{expr}).concat_map { |#{var}| #{s} }"
  }
  eval(final,b)
  #final
end

See, easy?

Now we can do things like:

def factors( n )
   comp "[ [x,y] | x <- (1..n) ; y <- (1..n) ; x * y == n ]", binding
end

If we do factors 25 we get [[1, 25], [5, 5], [25, 1]].

We can also write "quicksort" (being that not so great list comprehension quicksort that I'm sure you've seen before:"

def qsort( a )
  if a.length < 2
    a
  else
    pivot = a.first
    tail = a[1..-1]
    b = binding
    qsort(comp("[ x | x <- tail ; x < pivot ]", b)) + [pivot] + qsort(comp("[ y | y <- tail ; y >= pivot ]", b))
  end
end

And of course we write a cartesian product function:

def cart_prod(a, b)
  comp "[ [x,y] | x <- a ; y <- b ]", binding
end

By the way the code that this expands to is:

(a).concat_map { |x| (b).concat_map { |y| r( [x,y] ) } }

Of course we could've written all these functions before, w/o list comprehensions but this was more fun.

Abuse: Is it ruby? Is it Haskell? It's both!

=begin

> puts = return ()
> main = do let (.) = flip ($)

=end
eval <<HERE.gsub(/^>/, '')

>           print([1,2,3].length)
>           puts

HERE

Save to somefile.lhs

Run with ruby something.lhs
runhaskell something.lhs

How Arrays Work In Ruby

WKC CCC wrote:

> unknown wrote:
> > WKC CCC wrote:
> >
> >>
> >> count = count + 1
> >> end
> >>
> >> puts one.inspect
> >
> > Array.new(array) copies the *array* but it does not copy its *elements*.
> > So tempArr[0] is another name for the very same object as one[0], and so
> > forth. m.
>
> If they are referring to the same object, why is it when
>
> tempArr = Array.new(one)
> one.clear
>
> results in tempArr still having the values originally assigned to array
> one?

Reread what I said. I didn't say that tempArr and one refer to the same
object; I said that tempArr[0] and one[0] (and so on) refer to the same
object.

Think of it this way. Items in an array are dogs. Arrays are people
holding leashes. Anyone can attach a leash to a dog. So I (tempArr) can
have a leash on Fido, and so can you (one). If you let go of your leash
(one.clear), Fido is still Fido; you just don't have a leash on him. But
if you cut off one Fido's legs (modify one[0]), that leg on my Fido
(tempArr[0]) is also cut off, because they are the same Fido.

m.

--
matt neuburg, phd = matt@tidbits.com, http://www.tidbits.com/matt/
Tiger - http://www.takecontrolbooks.com/tiger-customizing.html
AppleScript - http://www.amazon.com/gp/product/0596102119
Read TidBITS! It's free and smart. http://www.tidbits.com

Monads in Ruby Part 2: Maybe (then again Maybe not)

So here's when things start to get interesting. Today I'm going to discuss the maybe monad. In Haskell, the maybe type is used for computations that might fail. An example of this in ruby would be the #index method on arrays. In ruby index returns either the index of the passed in item in the array, or nil if the item is not in the array. Haskell is statically typed so variables can only hold one type of data. This means we can't return a 3 or a nil. Instead we have the maybe type which looks like data Maybe a = Just a | Nothing . So index would return a Maybe Integer. e.g:

index  "hello" ["world", "planet", "hello", "hi"] --> Just 2
index  25 [3,4,5] --> Nothing

What does this have to do with monads you may be wondering? Well, just like identity, the maybe type is a monad. In fact maybe is a monad with some extra features, an instance of MonadPlus. We'll come back to that. But first a detour in ruby land. You may have seen something like this:

class NilClass
   def method_missing(*args, &block)
      nil
   end
end

This is sometimes called the null pattern, and it makes Ruby's nil act like Objective-C's. That is, nil will just swallow messages it doesn't understand. The general opinion among the ruby community is that this is a Bad Idea (tm). I would tend to agree with that idea. It's also not as useful as it might initially appear, consider 1 + nil.

This pattern however is superficially similar to how Maybe works in Haskell as a monad. I mentioned earlier that maybe was an instance of MonadPlus. This means it supports two additional operations, mzero and mplus. mzero, acts as you might guess from it's name as a zero. mzero mplus anything will always be the anything. Likewise if you think of the bind operation (discussed last time) as a sort of multiplication, mzero bind f will always be mzero. For the maybe monad, Nothing is mzero.

So if I define

class Array
   def maybe_index( obj )
      i = index( obj )
      if i
         Maybe.Just( i )
      else
         Maybe.Nothing
      end
   end
end

I can now change the first 3 in an array for instance into a 4, with no need for error checking:

a = [1,3,5]
b = Maybe.m_bind( a.maybe_index( 3 ) ) { |i| a1 = a.dup; a1[ i ] += 1; Maybe.m_return( a1 ) }

So b will either be Just [1,4,5] or Nothing. Either way, we had no opportunity to index an array by nil, and no need to litter our code with if statements. (What we did litter our code with was quite a bit more verbose, but you win some you lose some.)

Now, you must be wondering, what about this mplus business? Well let's same you need to address someone. If you know their nickname, you'd like to use that, if you don't know their nickname, you'd like to use their first name, and if you don't know their first name, you'd like to use their last name (which you know you'll always have). So how do we do this? We get all three and mplus the results together:

class Hash
   def maybe_fetch( key )
      if has_key? key
         Maybe.Just(self[key])
      else
         Maybe.Nothing
      end
   end
end

person1 = { :nick => 'Big Joe', :first => 'Joseph', :last => 'Smith' }
person2 = { :last => 'Baggins' }

greeting1 = Maybe.mplus( Maybe.m_bind( person1.maybe_fetch( :nick ) ) { |nick| Maybe.m_return("Hey, #{nick}") },
                                         Maybe.mplus( Maybe.m_bind( person1.maybe_fetch( :first ) ) { |first| Maybe.m_return("Hi, #{first}") },
                                                               Maybe.m_bind( person1.maybe_fetch( :last ) ) { |last| Maybe.m_return("Hello, Mr. #{last}") }))

puts greeting1.from_just

greeting2 = Maybe.mplus( Maybe.m_bind( person2.maybe_fetch( :nick ) ) { |nick| Maybe.m_return("Hey, #{nick}") },
                                         Maybe.mplus( Maybe.m_bind( person2.maybe_fetch( :first ) ) { |first| Maybe.m_return("Hi, #{first}") },
                                                               Maybe.m_bind( person2.maybe_fetch( :last ) ) { |last| Maybe.m_return("Hello, Mr. #{last}") }))

puts greeting2.from_just

This is similar to something likep1[:nick] || p1[:first] || p1[:last] in your standard ruby idiom, but note how I also transformed each value differently. And this code won't misevaluate due to things like nil being false or "" being true. The effect is localized entirely to the semantics you give it. This also means that you won't easily run into the major problem of the null pattern in that it runs away with you. It's very easy to contain this to a small section of code.

Before I post the code, I'm going to make one small note. I've decided not to bother with writing "type-safe" versions of this monads anymore. a) They aren't really type-safe anyway and b) classes aren't types, especially not in Ruby. It's a losing battle, so I think that to use monads in ruby you'll unfortunately have to rely more on self-discipline and less on type-checking.

class Maybe
  def initialize(*args)
    if args.length > 1
      raise ArgumentError, "Expected 0 or 1 arguments, got #{args.length}"
    end

    @nothing = args.empty?
    @val = args.first
  end

  def nothing?
    @nothing
  end

  def from_just
    raise "Maybe pattern match failure" if nothing?
    @val
  end

  def self.Just( v )
    new(v)
  end

  def self.Nothing
    new
  end
end

# Monad stuff
class Maybe
  def self.m_bind(maybe_a)
    if maybe_a.nothing?
      Maybe.Nothing
    else
      yield(maybe_a.from_just)
    end
  end

  def self.m_return(v)
    Maybe.Just v
  end

  def self.mplus(a, b)
    if a.nothing?
      b
    else
      a
    end
  end
end

Monads In Ruby Part 1.5: Identity

So after chatting in #haskell on freenode it became apparent that my Identity monad was kind of a cheat. It wasn't a function from types to types. So I present here for comment, a modified version, that pretends that ruby has parametric types:

% cat identity.rb
$implementation_detail = {}
def Identity(klass)
  $implementation_detail[klass] ||= Class.new do
    define_method :initialize do |obj|
        @obj = obj
    end

    define_method :m_bind do |f|
      r = f.call( @obj )
      raise TypeError, "Bind did not type check" unless r.kind_of? Identity(klass)
      r
    end

    (class << self; self; end).class_eval {
    define_method :m_return do |obj|
      raise TypeError, "#{obj} not instance of #{klass}" unless obj.kind_of? klass
     self.new( obj ) 
    end

    define_method :name do
      "Identity(#{klass})"
    end

    alias_method( :to_s, :name )
    alias_method( :inspect, :name )
    }
  end
end

p Identity(Array).m_return( [1, 2, 3] ).m_bind( lambda do |a|
  Identity(Array).m_return( [3] + a[1..-1] )
end)




% ruby identity.rb
#<#:0x1eaff0 @obj=[3, 2, 3]>

Monads in Ruby Part 1: Identity

Just to get this out of the way, yes it's been done before: http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/00introduction.html

In order to better understand the various monads available in Haskell, I've been re-implementing them in Ruby. Thus far I've done Identity, List (well Array), Maybe and State. Today I'm going to show you the Identity monad. A monad is a framework of sorts for applying rules to a series of computations. A monad has at least two operations, bind and return. return takes a non monadic value and converts it to a monadic one, it has type:
(Monad m) => a -> m a
(I'm using Haskell type notation here because ruby doesn't have type notation ;) )

Bind takes a monadic value and de-monadifies it to feed it into a function that returns a monadic value. It has the type:
(Monad m) => m a -> (a -> m b) -> m b

Bind is where the magic happens. Haskell uses it's type system to ensure that every sequence of computations in a given monad goes through bind. Bind therefore lets the writer of the monad decide the rules for the little monadic world within a given program. (This is how Haskell deals with side-effects (IO) ).

So now without further ado, I present the Identity monad:

class Identity
  def initialize( val )
    @val = val
  end

  def self.m_return( a )
    Identity.new( a )
  end

  def self.m_bind(id_a, &f)
    f.call( id_a.val )
  end

  def val
    @val
  end
end

Short and sweet. All you can really do with an Identity monad is force evaluation order. Ruby is imperative so that doesn't really matter.

Here's some code using Identity:

Identity.m_bind( Identity.m_return( 1 ) ) do |x| # x is 1, we've sucked it out of the Monad.
  Identity.m_return( x + 1 )
end

This is quite verbose. In Haskell it would be return 1 >>= (\x -> return x + 1), where >>= is bind and (\x -> ... ) is analogous to lambda { |x| ... }. Haskell also has some syntactic sugar for monadic expressions like this. Using the the syntactic sugar it would look like:

let i = return 1 in
       do x <- i
            return x + 1

The real difference of course is the type checking. If I wrote return 1 >>= (\x -> x + 1) in Haskell it would not compile where ruby cares not a whit if we want to escape our monads. That combined with the fact that unlike Haskell we have no syntactic sugar for monads means it's going to be difficult to debug our ruby implementations. Hopefully I've whet your appetite, next time we'll tackle the Maybe monad, that allows us to handle computations that might fail.

Seen in #ruby-lang

[4:21pm] <tpope> blink, less +F
[4:21pm] <teferi> tpope: I just SUGGESTED that
[4:21pm] <blink> technomancy: ssh+screen+tail, and doing an escape to copy mode everytime i want tos croll back is a hassle.
[4:21pm] bingeldac joined the chat room.
[4:21pm] <tpope> well good for you
[4:22pm] <blink> teferi: oh, i thought you were referring to tail -F
[4:22pm] <technomancy> if you say so
[4:22pm] langenberg_ left the chat room. (Connection timed out)
[4:23pm] <LoganCapaldo> he
[4:23pm] <LoganCapaldo> it's funny how you can man less and search for tail and get relevant info
[4:23pm] <blink> teferi: heeeeee, it works in conjuction with the F command within less. thank you.
[4:23pm] <blink> LoganCapaldo: i didn't se anything, so i decided to ask some geeks :P
[4:24pm] <simplicoder> a manless search for tail?
[4:24pm] <blink> simplicoder: i do that all the time.

NextFest

So yesterday (9/30) I hit up nextfest with my compatriot Jimmy. Won a USB hub from the GeekSquad both. Saw a creepy creepy robot, that had Einstein's head attached to Asimo's body. (Well it wasn't really Asimo, It was Hubo, but it sure looked a lot like Asimo.) There was this planetary rover that's wheels were each independent robots (I use "independent" loosely because the whole time they were being controlled by guys with RC remotes). IBM can apparently move individual atoms now thru the magic of cut and paste.

After NextFest, we wanted to see The Prestige, so instead we saw The Illusionist. (The Prestige having not yet been released). It was ok. My friend remarked it was very The Usual Suspects there at the end.

Vi for Mac OS X eveverywhere!

So cruising freshmeat today, I came across the world's niftiest Input Manager, http://www.corsofamily.net/jcorso/vi/. It lets you use vi command mode commands anywhere that uses Mac OS X's text input doohicky, which is pretty much everywhere. TextEdit, Safari, etc. all now have Vi key-bindings. It's not perfect, every time I've tried to edit something in this window for instance, I haven't been able to see the cursor, but it does work admirably in TextEdit and Colloquy, which is good enough for me. Hopefully it will get better.

Picture of Me

For anyone whose ever wondered what I look like:

Two Friends at a Cafe

The following takes place at an outdoor table of the Jester's
Cafe in Kingstown, Mittelland. Sitting at this table is Mr. Arthur
Shortbush, a Kingstown business-man. He is taking his morning coffee
(where the morning is eleven A.M.), and reading the Kingstown
Informer, a paper chiefly for the entertainment of business-men.

We observe Mr. Shortbush for a while, he is like his namesake
short, barely four foot eleven inches. He does however have the
advantage of the most wonderful thick, and perfectly neat brown hair.
Many would say it was his most attractive feature. Mr. Shortbush is
not lazy to be up so late, but the Markets are closed today, and he
relaxes for the moment, sure that his investments are secure.

By-and-by we see Mr. Shortbush's good friend come up the
street and join Shortbush at the table.

"You still read that rag?" Mr. Shortbush's friend is of course
referring to the already mentioned Kingstown Informer. Mr. Shortbush
folds up the paper in response.

"I must keep up with my business affairs."

"Don't lie, I know you read that thing for fun." Lord
Southwell is of course completely correct. Lord Southwell being Mr.
Shortbush's friend. Lord Southwell is actually a relatively minor
personage, which no land worth speaking of. He is unfortunately tall,
undesirably lanky and not very handsome. His only saving grace as far
as the general populace was concerned was that that he had the
friendship and esteem of (the very rich) Mr. Shortbush.

"I would never lie to you Leon." We wonder whether Mr.
Shortbush is being genuine. "However, there was a rather interesting
article in today's 'rag'. It seems Southland man has received
permission and financing from the Westland monarchy to try a mad
expedition to the other side of the world."

"Ah yes. DeMerro is his name right? I wonder what he plans to
do when he gets to the other side of the world."

"Well considering the Southlander nature, I imagine he intends
to throw a ball." Lord Southwell laughs uproariously at Mr.
Shortbush's witticism. The other diners and people in the vicinity do
not think it nearly as clever.

Mr. Shortbush continues, "Yes, it says here he will have a
fleet of five ships. Is five really a fleet I wonder? My own merchant
fleet exceeds fifteen, although my ships don't appear to be nearly as
large as this madman's. Five ships will depart from southernmost port
in Westland, and travel west, all around the earth until they arrive
in the Distant East. It goes on and on about the minutiae of sailing,
not very interesting I should think.

"Fancy a card game?"

"I suppose I could do with a hand or two." replies Lord
Southwell.

Animal Crossing: WW

Well I just discovered this saturday is another Flea Market. I'm quite excited, the Flea Market is where you get to trip off the cool stuff from all the animals in your town, and sell some your crap. AC is very much like the non-combat addicting parts of an MMORPG, but without other people. This game is so great. I'll update on saturday with all the cool stuff I manage to yoink. (Is that how you spell "yoink!" ?)