Показаны сообщения с ярлыком programming. Показать все сообщения
Показаны сообщения с ярлыком programming. Показать все сообщения

пятница, 9 декабря 2011 г.

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)

вторник, 31 мая 2011 г.

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 ;)

среда, 27 апреля 2011 г.

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.