A simple calculator

After a long struggle with some wildly inefficient algorithms, I've given up on Parsnip's more exotic parse strategies. Unfortunately, this means my long held goal of allowing left-recursion is out. To keep Parsnip user code readable (by avoiding left-factoring) I just wrote the OpTableParser class, which implements operator precedence parsing. The syntax of operator parsing is a bit funky, but not so mysterious if you keep in mind that infix_left returns an OpTableParser pointer. For an example, here's a parser/evaluator for simple mathematical expressions.

//First we need some functions to evaluate our mathematical expressions 


double multiply(double x, double y) { return x*y; }
double add(double x, double y) { return x+y; }
double subtract(double x, double y) { return x-y; }
double divide(double x, double y) { return x/y; }


// Our parser will accept a string and return a double

typedef Parser<string, double>::type NumParser;


// Here is the new operator precedence parser
// The infix_left method accepts an operator string, its precedence and 
// an associate reducer function


NumParser ops = op_table(real)
                 ->infix_left("+", 10, add)
                 ->infix_left("-", 10, subtract)
                 ->infix_left("*", 20, multiply)
                 ->infix_left("/", 20, divide);


Our parser will return a double if it succeeds. The returned value, along
with any error info, will be stored in a ParseResult object

ParseResult<double> result;
 
result = parse("3+4*2", ops);

if (result.parse_finished())
{
  std::cout << parse.data(); 
}

Building maps with parsnip

To further demonstrate the brevity and power of Parsnip, here is the code for a simple grammar which accepts strings of the format "key1 = value1; key2 = value2;". The return value of the parser is an std::map of the key-value pairs.

Parser<string, Tuple2<string, string>>::type single_pair = letters >> skip(token_ch('=')) >>  letters >> skip_ch(';');

Parser<string, std::map<string, string>>::type pair_parser = many< BuildMap<string, string> >(token(single_pair));

That's it!

Parsing s-expressions with Parsnip

Moving to New York has been quite hectic, but I have found a few spare moments to keep working on Parsnip. The library is still patchy and probably full of undiscovered bugs, but nonetheless quite powerful.

As a demonstration of Parsnip's capabilities, I used the library to build a small s-expression parser.

First, we need some data structures to represent s-expressions in C++:

//All s-expression objects (nil, cons, number, etc...) derive from LispObject

struct LispObject
{
   virtual bool isCons() { return false; }
   virtual bool isNumber() { return false; }
   virtual bool isSymbol() { return false; }
   virtual bool isNil() { return false; }

   virtual std::string toString()=0;
};

typedef ptr<LispObject> ObjPtr;


/*
Cons cells are the fundamental element of s-expression lists. 
Each cell contains a head (which is a data item, in the case of a flat list)
and a tail (which is the next cons cell in the list). 
The last cell has a tail which points to nil (like a null-terminated string). 
*/


struct Cons : public LispObject
{
   Cons(ObjPtr _head, ObjPtr _tail) : head(_head), tail(_tail) {}
   virtual bool isCons() { return true; }
   virtual std::string toString()
   {
      return "(" + head->toString() + " . " + tail->toString() + ")";
   }

   ObjPtr head;
   ObjPtr tail;
};
typedef ptr<Cons> ConsPtr;

ObjPtr makeCons(ObjPtr head, ObjPtr tail)
{
   return new Cons(head, tail);
}

Cons* toCons(ObjPtr obj)
{
   return static_cast<Cons*>(obj.GetRawPointer());
}


// Symbols are any variable/identifier


struct Symbol : public LispObject
{
   Symbol(const std::string& _name) : name(_name) {}
   virtual bool isSymbol() { return true; }
   std::string toString() { return name; }

   std::string name;
};
typedef ptr<Symbol> SymPtr;

ObjPtr makeSymbol(const std::string& str)
{
   return new Symbol(str);
}


// Number objects are boxed (or wrapped) floats

struct Number : public LispObject
{
   Number(float _val) : value(_val) {}
   virtual bool isNumber() { return true; }
   std::string toString() { return to_string(value); }
   
   float value;
};

typedef ptr<Number> NumPtr;

ObjPtr makeNumber(float val)
{
   return new Number(val);
}


// Nil is the terminating element at the end of each list


struct NilObject : public LispObject
{
   bool isNil() { return true; }

   static ObjPtr getNil()
   {
      if (nil) { return nil; }
      else
      {
         nil = new NilObject;
         return nil;
      }
   }
   std::string toString() { return "()"; }

private:
   static ObjPtr nil;
};
ObjPtr NilObject::nil;

ObjPtr getNil()
{
   return NilObject::getNil();
}


/*
The BuildCons accumulator class is a template parameter
to the many/many1 parser combinators. 
Each ObjPtr accepted by the many/many1 parser is passed
to an instance of BuildCons. 
A resulting cons-list can be extracted using the result() method.
*/


struct BuildCons : public Accumulator
{
   BuildCons()
   {
      first_cell = getNil();
      last_cell = first_cell;
   }

   virtual void accum(const ObjPtr& o)
   {
     static ObjPtr nil = getNil();
     if(first_cell->isCons())
     {
        ObjPtr new_cell = makeCons(o, nil);
        toCons(last_cell)->tail = new_cell;
        last_cell = new_cell;
     }
     else
     {
        first_cell = makeCons(o, nil);
        last_cell = first_cell;
     }
   }
   virtual ObjPtr result() { return first_cell; }

private:
    ObjPtr first_cell;
    ObjPtr last_cell;
};

Next, we construct the parser itself:

// An ObjParser is any parser which accepts an input std::string and returns an ObjPtr. 


typedef Parser<string, ObjPtr>::type ObjParser;
ObjParser lisp_symbol =  call1(makeSymbol, many1(letters | oneOf("+-/*=@!?&^~:<>%")));


/*
The 'real' parser accepts strings such as "3.42" and "200".
The utility function makeNumber accepts a string and converts
it to a float. 
The function 'call1' creates a parser which takes the result of
its second argument applies to that its first argument. In short,
it calls makeNumber. 
*/

ObjParser lisp_number = call1(makeNumber, real);

typedef Parser<string, void>::type VoidParser;

VoidParser LP = skip(token_ch('('));
VoidParser RP =  skip(token_ch(')'));

ObjParser lisp_nil = call0(getNil, LP >> RP);
ObjParser lisp_atom = lisp_symbol | lisp_number | lisp_nil;


/*
The lisp_cons parser can't refer to itself directly, 
so we have to use a proxy LazyParser called cons_self. 
*/


ObjParser cons_self = lazy<string, ObjPtr>();
ObjParser lisp_cons =  LP >> many<BuildCons>(token(lisp_atom | cons_self)) >>  RP;
ObjParser lisp_expr = lisp_atom | lisp_cons;

setLazy(cons_self, lisp_cons);

Lastly, we add an input loop to test how the expressions get parsed:

std::string input;

while (true)
{
   std::cout << "> ";
   std::getline(std::cin, input);
   Result<ObjPtr> result = parse(input, lisp_expr);
   if (input == "exit") break;
   if (parse_finished(result))
   {
      cout <  result.data()->toString() << endl;
   }
   else if (input_consumed(result)) 
   {
     cout << "Unexpected end of input string " << endl;
   }
   else
   {
      int pos = parse_position(result);
      cout << "Unexpected character '" << input[pos] << "' at position " << pos  << endl;
    }
}

And that's it! We're now half way to writing an s-expression based language (ie, a mini-lisp or a configuration DSL).

Hyrax and The Parsnip

I've been working on and off on a programming language for over a year now. In the beginning it was a nameless C++ implementation of Paul Graham's illusory Arc. Under the name Hyrax my language kept the s-expression syntax and Lisp-like core but donned and shed many poorly implemented language features (type inference, prototype-based Objects, etc..). Finally I found some purpose for the beast as a functional matrix language. With the semantics of Scheme, the mathematical capabilities of GSL and GiNac and the syntax of Matlab I could give SciPy a run for its money.

The only obstacle in my way is parsing the new syntax. I have thus far been using a kludgy hand-written s-expression parser that is highly immune to improvement. I tried out ANTLR and Spirit but found them both cumbersome. In the true spirit of Not Invented Here I have been writing my own parser library in C++: Parsnip.

Parsnip is a backtracking recursive descent parser combinator library inspired by Parsec. Here's an example of Parsnip in action:

/*
  PARSER types are declared Output, Input
  so this parser accepts strings and return ints. 
  The reversal of the usual order seems a little clumsy 
  but it makes some code shorter and is easy to get used to.
*/

typedef PARSER(int, string) Parser;


/* 
  plus parses 0 or more spaces followed
  by the '+' character followed by 0 or more 
  spaces
*/

Parser plus = spaces >> ch('+') >> spaces;


/* 
   The sepBy1 parse creates a sequence
   of integer parsers from an input
   of integer strings separated by 
   plus parsers. 
 
   The reduce parser works like
   usual reduce function, it collects
   pairs of values from a sequence and 
   applies a function to them. The second
   argument passed to reduce is the default
   in case of an empty sequence. 
*/


Parser sum = reduce(add, 0, sepBy1(integer, plus)); 


//The Maybe struct is modeled after Haskell's Maybe a = Nothing | Just a
//but in this case the Just value can be accessed by Maybe::data

Maybe<int> result = parse("1 + 2 + 3", sum);
 
// prints "6"
  
if (result) cout << result.data;

To allow more natural expression of grammars I make heavy use of backtracking in parsnip parsers. All this backtracking comes at the cost of horrible algorithmic bounds, which I partially offset by memoizing the parse results. This makes Parsnip's parsers full-blown packrat parsers.

With this immensely powerful and easy to use parser I plan on turning Hyrax into an unstoppable juggernaut of scientific computing. Now all I need is a new name.

Blogorevolution: How I Faked The Moon Landing Using Web 3.0

I'm commandeering Spikebucket for unbearable programming language nerdiness. I'll say it here so you don't have to hear it at a party. Since neither Weissman nor Sergey are likely to ever check this page again, I don't think this change of course will be a problem.

Redundancy is for chumps

The Deepest Cut: a New Yorker piece about medical hemispherectomies.
The bulk of the article documents the lives of doctors and patients. Ignore the fluff and you'll find some good neuroscience. The primary lesson here has been said before but it's worth reiterating: neural plasticity is solely responsible for the anatomical structures of the brain

Leah Krubitzer...removed large pieces of the brains of newborn marsupials. Once the marsupials became adult, she examined the brains again and found that they had organized themselves in such a way that the visual, auditory, and other somatosensory areas were all in the same relative positions that they would occupy in a normal brain, but they were smaller, commensurate with the total space available.

The article contains several anecdotes of people recovering lateralized brain functions after the relevant hemisphere had been removed. Apparently, even the lateralization of language can rewired: if the left hemisphere is removed the right hemisphere will adapt to generate and understand language. In the only cited example a 13-year old had her left hemisphere removed and regained her speaking ability. Presumably this is after the critical period. Could language switch hemispheres even in adults?

The Quest for Consciousness

What consciousness is Koch questing after? He purposefully and hastily redefines consciousness into something irreconcilable with the word's popular definition. To carve out a tractable research area Koch drained consciousness of its most interesting content. Into the bin of "extended consciousness" Koch places self-awareness, verbal thought and emotion; a category he then immediately discards and forgets. Isn't "sensory perception" a better more accurate term for the group of phenomena Koch calls "core consciousness"? Also, I have a problem with the claim "all the different aspects of consciousness...employ one or perhaps a few common mechanisms" (p.15). It seems to me that core consciousness is shallower (in terms of depth of computation) than extended consciousness. Isn't there a unidirectional flow of influence between conscious sensory perception and conscious verbal thought?

I think the strength of Koch's theories and frameworks is the lucidity with which he summarizes and rearranges the field of neuroscience. Lifted by his capable pen generalizations and trends are arising from the dataswamp of neurobiology.

Handheld Audio Spectrum Analyzer

I'd like to build a small, back-lit, audio spectrum analyzer. Things I might need:

1) Micro-controller that does signal processing stuff along with associated software and development kit. Could be expensive. Nobody should have to code the FFT in this day and age. TI?
2) LCD (black and white is probably fine) that has a very simple input/output. All it needs to do is show the frequency axis and very thing Winamp-like bars for the magnitude. I guess we can skip the phase entirely and just have two buttons: On/Off and a button to freeze what's currently on the screen so you can examine the current spectrum at your leisure. Is touchscreen expensive?
3) Tiny microphone. Directional seems most reasonable, but it would have to work at large ranges, so maybe the tiny mics ones I used for my mini-disc secret headphone recorder would be better.
4) Casing, power supply. I can probably steal a bunch of stuff from work and might just be able to actually develop this during work. Hmm.

Thoughts from the ghosts that read this blog?