Spikebucket

A simple calculator

2007-10-01T02:35:00.000-06:00

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

2007-09-15T01:50:00.001-06:00

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

2007-09-06T11:57:00.000-06:00

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

2007-05-14T17:06:00.000-06:00

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

2007-05-14T16:57:00.000-06:00

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

2007-04-26T00:59:00.000-06:00

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

2007-02-22T01:03:00.000-06:00

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

2007-01-13T15:40:00.000-06:00

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?

The State of Machine-Mediated Telepathy

2006-12-12T23:47:00.000-06:00

What is Machine-Mediated Telepathy?
A term I've made up to describe the use of a two-way neural interface to project mental states between two people.

Has any progress been made towards this freakish machine?
Much of the Brain-Computer Interface research also contributes towards direct Brain-to-Brain communication. A fine grained bi-directional BCI might be all that's necessary. The Johns-Hopkins BCI group seem to already have Brain-to-Brain interaction on their radar. However, even mainstrean BCI research is still embryonic. Still, some of the foundations have already been laid down, making the quest for telepahy not entirely quixotic.

Is this even possible?
Transmission of mental states (thoughts, memories, emotions, etc...) between brains hinges on advances in three research areas:

Brain "Reading": Neuroimaging and electrophysiology are both highly developed fields that offer researchers a dizzying variety of techniques for ascertaining brain state. Unfortunately, no single method has satisfactory temporal and spatial resolution. For a comparison of the resolution/invasiveness tradeoffs, see this chart. Not mentioned in the previous link are (1) electrode recording: highly invasive, spatially limited and temporally extremely precise (2) and EROS: non-invasive, sub-cm spatial resolution, ~100ms temporal resolution. MRS is the sole imaging technique which can discriminate neurotransmitter concentrations (I suspect this might be useful).
Brain "Writing": Not writing, in the sense of permanently altering, but rather the induction of neural activity based on inputs. Aside from direct electrode stimulation, the only technology I'm aware of in this field is Transcranial Magentic Stimulation. TMS has horrible spatial specificity (could this be improved on?).
Neural Correlates of Consciousness: Equally important as the mechanisms for brain access is the knowledge of what areas are relevant. I don't think it's necessary (nor possible) to fully map the interplay between brain and mind. Luckily, we could probably get by with a rudimentary knowledge. The activity of one brain will be interpreted by a second, so there's no need to make explicit what that activity means. Still, we *will* have to know which areas are relevant.

How long will it take?
Optimistically, decades. Of the three fields above, only "reading" (neuroimaging/electrophysiology) is advanced enough to be useful for a brain interface. Brain-effecting technologies will probably increase in the near future (as researchers delve deeper into bi-directional BCI), though their arrival is not certain. The correlation of conscious phenomena with neural activity has already begun in the Koch lab (as well as others). It's unclear how long it will take until such research crystallizes into a clear vision of how the brain implements conscious thoughts.

Emails to Christof Koch: The Highlight Reel

2006-12-10T23:15:00.000-06:00

Christof Koch is a very erudite visionary Neuroscientist whose emails inspire awe in all who see them. But most especially in Jon Weissman.