Thursday, October 10, 2013

Fun with Functional

I recently uploaded my first NuGet package. It contains my first shot at playing with functional programming with my favorite computer language. This has been inspired by the things I’ve learned in the book Functional JavaScript.

Thinking from a functional programming standpoint is quite different than traditional OOP thinking. Sometimes I call it ‘inside-out thinking’. It can lead to some seriously efficient code. You’ll see that with a powerful tested functional library, you end up writing less code; and the less code you write, the less code you have to test, and the less code that can go wrong. Remember that you can probably write a 5 line program that has no bugs. I recall seeing my college Lisp instructor code faster and more powerfully than any C coder I’ve ever met. To be sure, there are a lot of good functional languages to learn these techniques, among them Clojure, F Sharp, and Nemerle. As a C Sharp guy, I’ll start with a library, and apply functional programming to my C sharp code. You can see much of the influence of functional programming when exploring LINQ. I’ll be using some of the LINQ extensions in my library.

Sometimes I write code like this:

for(int i= 0; i< 5; i++) fn(i);

or this:

IList<int> result = new List<int>();
for(int i=0;i < 5; i++) result.Add(fn(i));

Let’s do this from a functional standpoint. We’ll build with bricks. One of the first things I've discovered is the conflict between operators and functions. I can pass around functions, but I can't pass around operators. Thus, we'll make the operators in to functions. Here are some bricks:

public static class Functional<T> {
    public static Func<int, int, bool> gt = (l, r) => (l > r);
    public static Func<int, int, bool> lt = (l, r) => (l < r);
    public static Func<int, int, bool> equ = (l, r) => (l == r);
    public static Func<int, int, bool> neq = (l, r) => (l != r);
    // many more are not displayed here

One of the takeaways from functional programming is the increasingly blurry line between code and data. You may see the term “code = data”. Note that these are almost the same thing:

IEnumerable<int> x1 = new List<int>() { 0, 1, 2, 3, 4 };
IEnumerable<int> x2() { for(int i = 0; i < 5; i++) yield return i; }

These are not completely interchangeable, as we can declare the list implementation in a function, but not the function implementation. Had we been able to have a yield return in a lambda, we could have. We’ll make another brick.

    public static IEnumerable<int> range(int start,int end) {
        int step = ((end - start) > 0) ? 1 : -1;
        for (int i = start; neq(i, end); i += step) yield return i;

The full-featured version would be:

    public static IEnumerable<int> range(int start, int end, int step = 1) {
       int Step = ((end - start) > 0) ? Math.Abs(step) : -Math.Abs(step);
       Func<int, int, bool> condition = ((end - start) > 0) ? lt : gt;
       for (int i = start; condition(i, end); i += Step) yield return i;

Code = data, replacing a list of integers with a range. Now these are the same:

IEnumerable<int> x1 = new List<int>() { 0, 1, 2, 3, 4 };
IEnumerable<int> x2 = Functional<int>.range(0,5,1);

Functional programming promotes recursion over iteration. Often one will build a function that takes a list, and does something with the first element, and the then calls itself with the rest of the list, recursively. Therefore a couple useful functions are to get the first element of a list, and a function to return the rest of the list. I use some LINQ functions for this.

    public static Func<IEnumerable<T>,T> first = (lst) => lst.First();
    public static Func<IEnumerable<T>,IEnumerable<T>> rest = (lst) => lst.Skip(1);

Back to my original code, these bricks:

    public static Action<IEnumerable<T>, Action<T>> each = (lst, fn) => { foreach (T t in lst) fn(t); };
    public static IEnumerable<U> map<U>(IEnumerable<T> lst, Func<T, U> fn) { return lst.Select(fn); }

make this:

for(int i= 0; i< 5; i++) fn(i);



And this:

Func<int,int> fn = (x) => x * x;
IList<int> result = new List<int>();
for(int i=0;i < 5; i++) result.Add(fn(i));


IEnumerable<int> result = Functional<int>.map<int>(Functional<int>.range(0,5,1),(x) => x * x);

Another couple of bricks are:

    public static Func<string,IEnumerable<char>> Chars = (s) => s.AsEnumerable();
    public static T reduce(IEnumerable<T> lst, Func<T, T, T> acc, T initialItem) {
        return lst.Aggregate(initialItem, acc);

Now suppose we had a string “abcdefg”, and we want to transform that to “a.b.c.d.e.f.g”. In the old days, I might do this:

string Interleave(char c,string source) {
    string result = source[0].ToString();
    for(int i=1; i<source.Length;i++) {
        result = result + c.ToString() + source[i].ToString();
    return result;

Now I depend on a functional style:

Func<char, string, string> Interleave = (c, s) => {
     IEnumerable<char> seq = Functional<string>.Chars(s);
     string result = Functional<char>.reduce<string>(
        (st, ch) => st + c + ch,
    return result;

It’s often useful to know if two sequences are the same. I have a function that does this, and is very useful in my tests.

    public static Func<IEnumerable<T>, IEnumerable<T>, Func<T, T, bool>, bool> same = (lst1, lst2, fn) => {
        IEnumerator<T> i1 = lst1.GetEnumerator();
        IEnumerator<T> i2 = lst2.GetEnumerator();
        bool result = true;
        bool b1 = i1.MoveNext();
        bool b2 = i2.MoveNext();
        while (result && (b1 && b2)) {
            result = fn(i1.Current, i2.Current);
            b1 = i1.MoveNext();
            b2 = i2.MoveNext();
        return (result && (b1 == b2));

With this I can verify that:

IEnumerable<int> result = Functional<int>.map<int>(Functional<int>.range(0, 7), x => x + 5);
bool success = Functional<int>.same(result, Functional<int>.range(0 + 5, 7 + 5),Functional<int>.equ);

There is a strange function called always. Sometimes it's useful to have a function that always return a specific value.

    public static Func<T> always(T t) { return () => t; }

Interestingly, making two functions with the same value, does not return the same function.

Func<int> x = Functional<int>.always(3);
Func<int> y = Functional<int>.always(3);
// x != y

Just to tighten the potential proliferation of functions a bit, I provide the alwaysTrue and alwaysFalse functions:

    public static Func<bool> always(bool b) { return (b) ? alwaysTrue() : alwaysFalse(); }
    public static Func<Func<bool>> alwaysTrue = () => () => true;
    public static Func<Func<bool>> alwaysFalse = () => () => false;

There are times where it's useful to combine two or more sequences in some way, and return the new sequence.

    public static IEnumerable<U> map<U>(IEnumerable<T> lst1, IEnumerable<T> lst2, Func<T, T, U> fn) {
        IEnumerator<T> one = lst1.GetEnumerator();
        IEnumerator<T> two = lst2.GetEnumerator();
        while ((one.MoveNext()) && (two.MoveNext())) {
            yield return fn(one.Current, two.Current);

So testing the three sequence of this would be painful without the sequence compare function called same. We'll start with this brick:

    public static Func<bool, bool, bool> and = (l, r) => l && r;

Now to test the three-sequence combiner.

bool success = true;
// t f f t
IEnumerable<Func<bool>> test = new List<Func<bool>>() {
IEnumerable<char> first = Functional<string>.Chars("xoxo");
IEnumerable<char> second = Functional<string>.Chars("xxoo");
IEnumerable<char> third = Functional<string>.Chars("xooo");
IEnumerable<Func<bool>> result = Functional<char>.map<Func<bool>>(first, second, third,
    (x, y, z) => Functional<bool>.always(Functional<bool>.and((x == y), (y == z))));
success = Functional<Func<bool>>.same(result, test,(x,y)=>x()==y());

The key is passing a function that knows how to compare elements of the sequences. The == operator fails this, so the functional style of passing functions to functions saves us.

Finally, I have some curry functions. This is a technique to creating a function on the fly, and also configuring it. Suppose that I have a function that can add two integers (as I do)

    public static Func<int, int, int> add = (x, y) => x + y;

Now suppose that we need a function that takes an integer, and returns the sum of that integer, and 6. In the recent past, I would be tempted to write:

int addSix(int x) { return x + 6; }

No more. I have a class called Curry2 (big brother to Curry1) that takes a function, and when asked, will return a configured function.

    public class Curry2<T, U> {
        private Func<T, U, U> fn; // U fn(T t, U u)
        public Curry2(Func<T, U, U> fun) { this.fn = fun; }
        public Func<U, U> Create(T t) { return (x) => this.fn(t, x); }

Creating the addSix function looks like this:

Curry2<int, int> add = new Curry2<int, int>(Functional<int>.add); //here
Func<int, int> addSix = add.Create(6);
int r = addSix(21); // 27

I’ve published version 0.0.9 here. Install it and try it out.

Friday, August 2, 2013

Web API testing with Node

As I’m building an application that requires a backend web-service, I am building that service using Node. I intend that service to be RESTful. I need a tool to test this service, and have created a tool that runs under Node.  I use the assert library for verification.

var endpoint = 'localhost';
var http = require('http');
var assert = require('assert');
var opts = {
host: endpoint,
port: 8000,
path: '/submit',
method: 'POST',
headers: { "Accept": "application/json", "Content-Type": "application/x-www-form-urlencoded" }
var req = http.request(opts, function(res) {
var data = "";
res.on('data', function(d) {
data += d;
res.on('end', function() {
//var result = eval(''+data);
//assert.strictEqual(data,'{"status":"ok","message":"this is fun"}');

Wednesday, July 24, 2013

Morse code with an Arduino

In the hobby of amateur radio is a hobby called Radiosport. It is a competitive activity that combines RDF (radio direction finding) and orienteering, or land navigation. At the heart of this activity are a set of hidden transmitters that periodically transmits a coded message in Morse code. The goal is to locate all the transmitters in the minimum time. I have created some software for the Arduino, that with a gated oscillator and a hand-held radio, will make a good hidden transmitter for RDF activities like Radiosport or fox hunts.

The code for Arduino is called “Processing”. You can think of it as ‘C’, as the back end is a CPP compiler. The Arduino requires two functions to be implemented, and calls them when the device is powered on. The first function, ‘setup’ is called once soon after the device comes up, and then another function, ‘loop’ is called again and again forever, until the device is powered down.


I start with a few global variables. You’ll see this pattern many times in Arduino code.

/* Version 0.1 Support a-z and 0-9 and space */
/* Version 0.2 Support .,?!{}&:;=+-_"$@'/ */
int ledPin = 13;
int PTT = 12;

PTT means push-to-talk, a line to tell the transmitter to…transmit. The ledPin would connected to gate the output of an audio frequency oscillator. The output of that gated oscillator would go to the mic line of the transmitter.

int lengthDot = 200;
int lengthDash = 3 * lengthDot;
int CycleTime = 15000; // every 15 seconds

The length of a dot is 200 milliseconds, while the length of a dash is three times that. This transmitter transmits every 15 seconds.

I use a structure that contains a key, the number of symbols (sum of dots and dashes) and the code itself encoded from right to left. Dots are 0, while dashes are 1.

typedef struct {
char info;
byte length;
byte code;
} tagMorseLetter;

I create a table with 54 entries

int entries = 54;
tagMorseLetter morseCode[] = {
//code is shifted from the left
{'a',2,0b00000010}, // .-
{'b',4,0b00000001}, // -...
{'c',4,0b00000101}, // -.-.
{'d',3,0b00000001}, // -..
{'e',1,0b00000000}, // .
{'f',4,0b00000100}, // ..-.
{'g',3,0b00000011}, // --.
{'h',4,0b00000000}, // ....
{'i',2,0b00000000}, // ..
{'j',4,0b00001110}, // .---
{'k',3,0b00000101}, // -.-
{'l',4,0b00000010}, // .-..
{'m',2,0b00000011}, // --
{'n',2,0b00000001}, // -.
{'o',3,0b00000111}, // ---
{'p',4,0b00000110}, // .--.
{'q',4,0b00001011}, // --.-
{'r',3,0b00000010}, // .-.
{'s',3,0b00000000}, // ...
{'t',1,0b00000001}, // -
{'u',3,0b00000100}, // ..-
{'v',4,0b00001000}, // ...-
{'w',3,0b00000110}, // .--
{'x',4,0b00001001}, // -..-
{'y',4,0b00001101}, // -.--
{'z',4,0b00000011}, // --..
{'1',5,0b00011110}, // .----
{'2',5,0b00011100}, // ..---
{'3',5,0b00011000}, // ...--
{'4',5,0b00010000}, // ....-
{'5',5,0b00000000}, // .....
{'6',5,0b00000001}, // -....
{'7',5,0b00000011}, // --...
{'8',5,0b00000111}, // ---..
{'9',5,0b00001111}, // ----.
{'0',5,0b00011111}, // ----- Stay away from the codes below here
{'.',6,0b00101010}, // .-.-.- _No_ hams know them
{',',6,0b00110011}, // --..--
{'?',6,0b00001100}, // ..--..
{'!',6,0b00110101}, // -.-.--
{'{',5,0b00001101}, // -.--.
{'}',6,0b00101101}, // -.--.-
{'&',5,0b00000010}, // .-...
{':',6,0b00000111}, // ---...
{';',6,0b00010101}, // -.-.-.
{'=',5,0b00010001}, // -...-
{'+',5,0b00001010}, // .-.-.
{'-',6,0b00100001}, // -....-
{'_',6,0b00101100}, // ..--.-
{'"',6,0b00010010}, // .-..-.
{'$',7,0b01001000}, // ...-..-
{'@',6,0b00010110}, // .--.-.
{'\'',6,0b00011110}, // .----.
{'/',5,0b00001001} // -..-.

The meat of the code. The variable ‘current’ is the index of current item in the message as it's being transmitted.

int current = 0;

void setup() {
pinMode(ledPin, OUTPUT);
pinMode(PTT, OUTPUT);
void loop() {
int timeSpent = DoTask(ledPin,"your callsign here");
int restOfTime = CycleTime - timeSpent;
if (restOfTime > 0) delay(restOfTime);

Because I want to transmit synchronously, I need to know how much time each function in my code takes (give or take). I can sum all the times, and know when to start my next transmission. When I send a message, that function tells me how long it took. Of course that requires that each call to send a character or a space returns the time that took, which of course requires that the call to send a dot or a dash also returns how long it took. It's turtles all the way down. And finally, I wrap it in a DoTask function.

int DoTask(int pin, char* sentence) {
return sendSentence(pin, sentence);

int sendSentence(int pin, char sentence[])
int result = 0;
boolean between = false;
digitalWrite(PTT, HIGH);
char* p = sentence;
while (0 != *p) {
if (between) result += InterLetter(pin);
if (*p == ' ') result += Space(pin);
else {
int entry = FindCode(*p); // unknown time
if (-1 != entry) {
result += sendLetter(pin,morseCode[entry].length,morseCode[entry].code);
between = true;
digitalWrite(PTT, LOW);
return result;

I use a mask to get the LSB of the current code. I shift it out, bit-by-bit, and depending if the result is a 0 or 1, I transmit a dot or a dash. Note that the symbols are coded right to left, so I must shift them out left to right. Of course I accumulate the time spent transmitting the symbols. Between each symbol is a gap, so I account for that also.

int sendLetter(int pin, byte length, byte code)
int result = 0;
boolean between = false;
for(byte i = 0; i<length; i++) {
byte lsb = code & 0b00000001;
if (between) result += Gap(pin);
if (lsb == 0b00000001) result += Dash(pin);
if (lsb == 0b00000000) result += Dot(pin);
code = code>>1;
between = true;
digitalWrite(pin, LOW);
return result;
int Dash(int pin) {
digitalWrite(pin, HIGH);
return lengthDash;
int Dot(int pin)
digitalWrite(pin, HIGH);
return lengthDot;
int Gap(int pin)
digitalWrite(pin, LOW);
return lengthDot;
/* The space between letters is the time of 3 dots */
int InterLetter(int pin)
digitalWrite(pin, LOW);
int totalDelay = lengthDot + lengthDot + lengthDot;
return totalDelay;
/* A space character is the time of 7 dots */
int Space(int pin)
digitalWrite(pin, LOW);
int totalDelay = lengthDot + lengthDot +
lengthDot + lengthDot +
lengthDot + lengthDot + lengthDot;
return totalDelay;

Now normally I'd run a binary search here, but this was just easier, and it works. In a future version, I’ll improve this.

int FindCode(char c) {
int found = -1;
for(int i = 0; i< entries; i++) {
if (morseCode[i].info == c) {
found = i;
return found;

Monday, July 8, 2013

Day of the Week library

Some applications may need a Day Of The Week object. The application may be a business tool that may need to track something based on the day of the week, such as business hours. The application I am designing is using a bus schedule, which varies depending on if it's a weekday or on a weekend. A useful feature of such a class is: given today, what is tomorrow? It works the other way as well. If today is Tuesday, was yesterday a weekday? Is four days from today on a weekend?


namespace Library.Contracts {
public enum DaysOfTheWeek {
Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday
public enum DayClassification { WeekDay, WeekEnd }
public interface IDay {
DaysOfTheWeek DayOfTheWeek { get; }
DayClassification Classification { get; }
IDay Next { get; set; }
IDay Previous { get; set; }
public interface IWeek {
DayClassification Classification(DaysOfTheWeek day);
DaysOfTheWeek Tomorrow(DaysOfTheWeek today);
DaysOfTheWeek Yesterday(DaysOfTheWeek today);


using Library.Contracts;
namespace Library.Impl {
public sealed class Day : IDay {
public DaysOfTheWeek DayOfTheWeek { get; private set; }
public DayClassification Classification { get; private set; }
public Day(DaysOfTheWeek dayOfTheWeek, DayClassification classification) {
this.DayOfTheWeek = dayOfTheWeek;
this.Classification = classification;
public IDay Next { get; set; }
public IDay Previous { get; set; }

public sealed class Week : IWeek {
private IList<IDay> Days;
public Week() {
this.Days = new List<IDay>();
IDay sunday = new Day(DaysOfTheWeek.Sunday, DayClassification.WeekEnd);
IDay monday = new Day(DaysOfTheWeek.Monday, DayClassification.WeekDay);
IDay tuesday = new Day(DaysOfTheWeek.Tuesday, DayClassification.WeekDay);
IDay wednesday = new Day(DaysOfTheWeek.Wednesday, DayClassification.WeekDay);
IDay thursday = new Day(DaysOfTheWeek.Thursday, DayClassification.WeekDay);
IDay friday = new Day(DaysOfTheWeek.Friday, DayClassification.WeekDay);
IDay saturday = new Day(DaysOfTheWeek.Saturday, DayClassification.WeekEnd);
sunday.Previous = saturday;
sunday.Next = monday;
monday.Previous = sunday;
monday.Next = tuesday;
tuesday.Previous = monday;
tuesday.Next = wednesday;
wednesday.Previous = tuesday;
wednesday.Next = thursday;
thursday.Previous = wednesday;
thursday.Next = friday;
friday.Previous = thursday;
friday.Next = saturday;
saturday.Next = sunday;
saturday.Previous = friday;

public DayClassification Classification(DaysOfTheWeek today) {
return this.Days[(int)(today)].Classification;
private int indexOfToday(DaysOfTheWeek today) {
return (int)(today);
public DaysOfTheWeek Tomorrow(DaysOfTheWeek today) {
return this.Days[(int)(today)].Next.DayOfTheWeek;
public DaysOfTheWeek Yesterday(DaysOfTheWeek today) {
return this.Days[(int)(today)].Previous.DayOfTheWeek;

Your code would look like this:

IWeek week = new Week();
DaysOfTheWeek today = DaysOfTheWeek.Wednesday; // munge this from DateTime
int count = 0;
while (week.Classification(today) != DayClassification.WeekEnd) {
today = week.Tomorrow(today);
// count contains the number of days until the weekend.