Quicksort in shen

I've been playing with shen language last time. It leaves very positive impressions. Being a lisp it introduces pattern matching and powerful type system to the language.

Just a simple quickstort algorithm for starters:

(define filter
  {(A --> boolean) --> (list A)--> (list A)}
  _    []      -> []
  T?  [A | B]  -> (append [A] (filter T? B)) where (T? A)
  T?  [_|B]    -> (filter T? B))

(define q-sort
  {(list number) --> (list number)}
  [] -> []
  [A | B] -> (append (q-sort (filter (> A) [A|B]))
                     [A]
                     (q-sort (filter (< A) [A|B]))))

Yeah you're right. That's just a naive quick-sort. Generate left and right partitions of list by the first element and then recursively apply algorithm to the left partition and to the right one.

The standard library is not yet ready and that's the reason for filter function which doesn't belong to the core language.

Let's see what shen features are present in this program.

Pattern matching   

T?  [A | B]  -> (append [A] (filter T? B)) where (T? A)

This rule says: return element A glued with the resulte filter function applied to the tail of list called B, if (T? A) is satisfied.

Function signatures 
   

{(A --> boolean) --> (list A)--> (list A)}

This function signature says that function takes two arguments:

1. The function from the type A to boolean (the predicate in other words).
2. A list with elements of type A.

And returns a list with elements of type A. In this particular example A is the number type.

The filter function is used like this:

 (filter (> 5) [5 3 5 91 42 1 2])
 [3 1 2] : (list number)

It generates a list of all elements less than 5. 

Notice the (> 5). That's the notation for writing partial application functions.
It is equavalent to the following lambda function in lisp:
(lambda(x) (> 5 x))

After you load the program to the evaluator (I use emacs and shen-mode for that) you can run it like this:

(16+) (q-sort [5 3 5 91 42 1 2])
[1 2 3 5 42 91] : (list number)

Finally...i've got the card

I've finally got that network card with the help of my friend's sister who kindly agreed to take it with her from Florida to Saint-Petersburg.

I used my bike to get to the airport. It was rather easy minus nasty freight trucks.

Time to play with the card

Export restrictions

It is a sad rainy day...

The ethernet card which i need for tests that NetBSD foundation sent to me was returned back with the following statement:

THE SHIPMENT CONTENTS ARE SUBJECT TO EXPORT RESTRICTIONS

I'm curious does that mean it's not possible to ship out that card out of US nor to pass it with someone?

SO_TIMESTAPMNS option in NetBSD

I've made a small patch that implements SO_TIMESTAMPNS option in NetBSD kernel. Userlevel program that can test it is here.
One nasty thing i faced is that i used older header files for userspace program, and struct timespec was changed since.

struct timespec
{
    time_t tv_sec; //Now 64 bits long (was 32)
    long tv_nsec;
};

I have been getting zero tv_nsec all the time because of that. 

For real the receieved structre is:
+---------------------------+
| tv_sec  | [lower 4 bytes] |
| tv_sec  | [upper 4 bytes] |
| tv_nsec | [4 bytes]       |
+---------------------------+

Userspace thinks:
+---------------------------+
| tv_sec  | [lower 4 bytes] |
| tv_nsec | [4 bytes]       |
+---------------------------+

Had a hard time debugging that ;)

Base64 and Pipes

Today I needed to copy an rpm file to Xen virtual machine having xm console as the only access to VM (xm console opens console to virtualized OS).

The first idea that comes is to open editor in the VM and copy-paste the contents of rpm there. 

Unfortunatelly it's not going to work because virtual console will interpret non-ASCII symbols of binary file stream as escape codes which makes copying in this way impossible.

The UNIX utility which can help us is base64. It converts binary file to text representation which can be copied safely.

The whole process can be simplified to following:

from host side:
base64 file.rpm | xm console vm

from VM side:
base64 -d < /dev/tty > file.rpm

Where
"< /dev/tty" - standart input (from console),
"> file.rpm" - standart output (to file)

GSoC is on the way

My GSoC 2011 proposal has been approved!

I'm going to need the network card w/frame time-stamping capability for tests.

This one seems suitable.

I've set up project page here where I will post current project status.

The wind in my ears

Cycling is just great.

I've bought my bike yesterday, and managed to get to work in 50 mins just like through the subway.

Gonna like that!