Tuesday, January 21, 2014

Felix Circuits

A Felix "Circuit" Sieve of Eratostheses

Felix supports Active Programming by providing fibres ("f-threads") and synchronous channels ("s-channels"). This paradigm allows for millions of lightweight cooperative threads to exist concurrently!

I decided to learn more about this by writing a program to find prime numbers less than or equal to k using the "Sieve of Erastosthenes" algorithm (see this earlier blog entry for a simple version of that) only this time, phrased as a Felix "circuit" (of f-threads and s-channels).

It was a heck of a lot of fun!

The program I wrote and its tutorial can be browsed here. To learn more or get started with Felix yourself, start here!

Monday, January 20, 2014

Computing a US holiday calendar

Computing a US holiday calendar

Assume the existence of a type date and a function nth_kday_of_month with semantics described by Boost.Datetime documentation. We also assume sums type day_of_week=|Sunday|Monday|... and type ord=|First|second|....

These are utility functions I find myself writing time and time again.

let range l u =
    let rec range_aux acc x y =
      if x = y then acc
      else range_aux (acc@[x]) (x+1) y
    range_aux [] l u

let string_of_list f l = "[" ^ String.concat ";" (List.map f l) ^ "]"

The approach taken is to use date generators to convert abstract specification into a concrete set of dates.

let test () =
  let us_holiday_calendar (s, e) = 
    let generators = [
      nth_kday_of_month First Monday 09;  (*US labor day*)
      nth_kday_of_month Third Monday 01;  (*Martin Luther King day*)
      nth_kday_of_month Second Tuesday 02;  (*President's day*)
      nth_kday_of_month Fourth Thursday 11;  (*Thanksgiving*) 
    ] in
    let years = range s e in
    let apply_gen acc g = (acc@List.map g years) in
    let holidays = List.fold_left apply_gen [] generators in  
    List.sort compare holidays in
  assert_equal "[2014-01-20;2014-02-11;2014-09-01;2014-11-27;2015-01-19;2015-02-10;2015-09-07;2015-11-26;2016-01-18;2016-02-09;2016-09-05;2016-11-24;2017-01-16;2017-02-14;2017-09-04;2017-11-23;2018-01-15;2018-02-13;2018-09-03;2018-11-22;2019-01-21;2019-02-12;2019-09-02;2019-11-28;2020-01-20;2020-02-11;2020-09-07;2020-11-26;2021-01-18;2021-02-09;2021-09-06;2021-11-25;2022-01-17;2022-02-08;2022-09-05;2022-11-24;2023-01-16;2023-02-14;2023-09-04;2023-11-23]"
  @@ (us_holiday_calendar (2014, 2024) |> string_of_list string_of_date)

This code calculates a 10y calendar of US holidays between 2014 and 2024. If the operators @@ and |> are unfamiliar you can read about them here.