I’ve got two parser combinators today for you to play with, both whipped up this evening from pieces of earlier experiments.
Author Archives: aaron
Schrodinger’s Yacc
There was a small controversy last year about parser combinators, a convenient way of rapidly developing parsers in a functional style. Yacc is presumably chosen as the archetypal non-combinator parser generator, requiring separate external parser compiler, known for being a pain to use.
Like Schrodinger’s cat, Yacc seems to be indeterminately alive or dead (though the last article conclusively opened the box for me).
Concepts: Typeclasses for C++?
I’ve had a hypothesis for a while that C++ templates (paired at times with ADL) are an ad-hoc, unsound version of typeclasses. I’ve seen this hold for parser combinators, range base algorithms, and more. I’m also not the first to draw this comparison[1].
Concepts are supposed to bring soundness in through constrained templates. Concepts look awfully a lot like type classes; they export functions and types, and are parameterized, and act as constraints on generic functions and other concepts. I checked the draft specification [2], and it even seems to permit parameterizing concepts on type constructors, just like Haskell! (er, C++ calls them class templates, not type constructors. to-may-to, to-mah-to)
But I worried I may be mistaken about concepts, as I’ve searched through google and literature and have yet to find a single example in literature demonstrating the use of template template concepts.
In case you’re curious what this might look like, here’s an educated guess:
concept Monad<template <> class m> { template<typename T, typename U> m<U> mbind(m<T>, function<m<U>(T)>); template<class T> m<T> mreturn(T); }; template <template <typename> class m, class T, class U, class Iter> requires M<m> requires InputIterator<Iter, U> m<T> foldM(Iter begin, Iter end, T i, function<m<T>(T, U)> f) { if(begin == end) return mreturn(i); else return mbind(f(i, *begin), [=](T result){ Iter next = begin; ++next; return foldM(next, end, result, f); }); }
Have template template concepts been covered thoroughly somewhere, and I’ve just missed it?
- [1] “C++ templates/traits versus Haskell typeclasses” (2005), by Sunil Kothari, Martin Sulzmann.
- [2] “Proposed Wording for Concepts (Revision 5)” (2008).
- [3] “Trip Report: Exit Concepts, Final ISO C++ Draft in ~18 Months” (2009), Herb Sutter.
- [4] “ConceptClang: An Implementation of C++ Concepts in Clang” [pdf]
Repls, repls, everywhere
Have a new-years resolution to try out a new programming language, but in too much of a hurry to pick only one, or install anything?
Today there’s 61 different languages on that list. That many, there’s gotta be at least one that strikes your fancy.
Best batch execution site: ideone.com with 50 unique languages.
Best interactive REPL site: repl.it with 16 unique languages.
Bondage and Discipline Python
Python has an identity crisis sometimes. It starts with the premise, from Guido’s prior work on ABC, to make a simple but easy to understand language.
But then turns around and cries out “one way to do it“, leaving the programmer perplexed as to how Guido van Rossum thought we should do things. For example, Guido hates tail calls, so recursion isn’t the one way to do it that he picked (note that his blog post and followups contain a large number of factual errors; read it as an opinion piece only).
During these fits, Python suffers itself to be a bondage and discipline language.
Apparently there is hope. One bit that causes me particular pain is that nested functions cannot rebind variables in the outer scope; only read from them. A case in point:
def f():
x = 1
def doubleIt():
x *= 2 # local variable 'x' referenced before assignment
doubleIt(); doubleIt();
return x;
However, I was reading a piece on Factor, and it mentions that this restriction is lifted in Python 3.0. I’m still on 2.6 (the only differences I had been aware of were the somewhat arbitrary swapping of the ‘/’ and ” operators, and the insulting removal of map, filter, and reduce from Python 3.0). However, fixing this scoping rule, even if an extra keyword is needed, sure would be convenient for me.
Actually, there are a lot of improvements:
- Various APIs returns views instead of mutable list (copies).
- sorted is now built in. (I’ve had to write that myself so many times…)
- Apparently map and filter are still here (though he still went and put reduce all the way off in functools. I guess you can’t have it all -_-)
- Set literals, yay!
Now, if Guido would be so kind to add proper statement support to lambdas, I’ll switch ^_^. Oh, but Guido hates lambdas. Oh well, next time maybe.
– signed an ambivalent Python user
The case of the different shifts
Larry Osterman has commented on an interesting edge case in the C/C++ standards, involving the underflow of the right shift operator.
They reported that if they compiled code which calculated: 1130149156 >> -05701653 it generated different results on 32bit and 64bit operating systems. On 32bit machines it reported 0 but on 64bit machines, it reported 0x21a.
This is one of various areas of “undefined behavior” for which you can ask 2 engineers what it should do and get 3 answers, at least one being that “but I know there must be one!” I think I know where at least 2 of the answers are coming from … Continue reading
Typography for Lawyers
… And for everyone else. Typography for Lawyers; an easy read, very accurate, and despite the title, the typography advice is really for everybody.
Well, maybe not for typographers. I get the impression this is all entry level stuff.
Cache effects
Quick call out to an illustrative blog entry on various cache effects.
http://igoro.com/archive/gallery-of-processor-cache-effects/
When someone bugs me about “X is too slow, because it has to make a virtual call”, and I get annoyed, it’s because a hot virtual call is an overhead of some dozen cycles or so. Missing the cache? In the thousands. Don’t get me wrong, virtual calls can matter for many reasons, but that all flies out the window the moment you’re working on any non-trivial sized data set. If your objects are 100′s of bytes large, you don’t worry about the virtual calls, you worry about shuffling their member slots around to squeeze more out of your caches.
“It better not allocate”
My other favorite perf quote from this month: “It better not allocate — this call needs to take 100 microseconds or less”. On my dev box, on the default Win7 heap, an uncontended small allocation (and the pairing free) is 120 ns — or 0.12 microseconds. My personal favorite small object allocator can hit down to 0.020 microseconds sustained.
We could allocate thousands of objects per call and still come in under budget.
[ot] 500 mile email bug
Just a humorous software bug story, the case of the 500 mile email:
"We're having a problem sending email out of the department." "What's the problem?" I asked. "We can't send mail more than 500 miles," the chairman explained. I choked on my latte. "Come again?"
A must read for CS/IT folks.
My programming languages story
It’s bad style, but I must start with an aside: on reddit/scheme, there was a link to a blog series on developing a Scheme interpreter over January 2010. It might not implement any particular Scheme standard or particularly many libraries, but it’s got all the functional elements. Bootstrapping a programming language is fun and easy.
Anyway, he also posted a his personal history of programming language study, and it got me thinking about my own personal programming languages history.
It all started with Logo…