This is the shelter we stayed in. The high pitched roof helps keep the heat in, and the rain out. And the snow, although that mostly melted.



This was the point of the whole trip. A garbage can cooked turkey to share with friends and family. The can acts as an oven, with the charcoal providing way more than enough heat to cook the bird, which is impaled on a stake, holding it vertically in the middle of the can. The 15 pound bird cooked in just a few hours.



My boy Jonathan (on the left), me on the right, and our friend Joel in between. Yes, that's coffee in the mug. And, yes, it's a stainless steel vacuum mug. With a spill proof top. But not the one I leave at the office.


My other boy, Michael, against the far wall, near the fire. They're warming up after we sent them outside to do some of the cooking. Which was mostly making sure there were enough coals around the trash can.
We also made mashed potatoes, sweet potatoes, gravy, peas, corn bread, stuffing, and cherry and apple pies, cooked in dutch ovens. The dutch ovens were in the fireplace opposite the one in this picture, in the far corner of the shelter. Between the two fireplaces, the inside temperature got up into the 80s at one point. We had to open the doors to let out the heat.
And the smoke.

Everyone had a good time, and we came back with the same number of boys we left with.

"my office looks like a bookstore exploded in it, and then an electronics store was dropped on it to smother the flames." - J.Scalzi
http://scalzi.com/whatever/?p=152

The books are all triple stacked, and there are several more shelves surrounding the room....

So I bought it. And there was at least one more face out copy, besides the one you see here.

And this is where I bought it:

Penn Books on the LIRR Level of Penn Station. Small store, but many shelves of SF, particularly if you know to look under the display table across from the main set of shelves. The staff are outstanding. I got the first recommendation for Vinge's Rainbows (sic) End there. They also have an excellent classics and literature section. As in, when I mentioned that 'March Up Country' was (sort of) based on 'The Anabasis', they knew where it should be shelved, wondered why it wasn't there, and offered to order it. Which might just be good salesmanship, except, after picking up my copy, I was looking in the same section for a copy of the Eddas, which they had, and spotted another copy of the Anabasis.

Buy books there, if you can.

Using the Standard C++ Library in a Functional style.

The standard C++ library offers a number of algorithms that have nearly exact analogues in functional languages, and are used in almost the same way. In particular std::accumulate and std::transform are powerful, and very general, algorithms. In functional programming literature, accumulate is usually referred to as fold, or foldl, and transform is known as map, or zipWith, depending on whether transform is the unary or binary function form.

To quickly review, accumulate takes an iterator range, and either sums the range, or applies a functor to each value together with the result of the last application of the functor. This can be thought of as putting the operation between each pair of elements in the range. When the operation is plus or times, the result is the sum or product of all of the elements in the list. This is useful, but not really exciting to most programmers. However, when you consider carefully what can be used as the functor argument, you realize that fold is a an extremely powerful algorithm.

A quick example:

std::list& cons(std::list& xs,int x)

{

xs.push_back(x);

return xs;

}

int init[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

vector v(init, init + 10);

std::list empty;

std::list v2 = std::accumulate(v.begin(), v.end(), empty, cons);

> foldr (:) [] [1..10]

(Note, the lines of code starting with > are Haskell equivalents to the C++ code, and SHOULD work at a ghci Prelude> prompt. Since that's where I'm cutting and pasting from. Although it's sort of like literate haskell, the whole article probably won't compile since early definitions may conflict with later ones.)

Cons is a list constructor function. It pushes its argument onto the end of the linked list, and then returns a reference to the list that the element was appended to. The fact that this function takes and returns a reference to a list is a compromise I've made between the C++ library and functional purity. Really, I should be taking and returning lists by value. Except that the overhead is unconscionable, turning an O(n) operation into an O(n^2) operation. Since there is no way of accessing the intermediate state, in this case, I'm safe, but you need to be careful in this analysis. Using cons() in your own code will modify the value, and you lose the referential transparency we're trying to maintain.

So the application of cons() using accumulate against an empty list copies the list into a new list. If we had supplied a non-empty list, we would have appended the lists together. Interesting, for an algorithm that's usually considered a purely numerical one.

Functional languages usually work with singly linked lists. A singly linked list has an append at the head only, and therefore the tail remains unchanged, and any references to the tail can not tell that there is a new list that uses it. In fact, a list might be the tail of several other lists, and there is no way of telling the difference. It would be possible to create a version of list that is singly linked, where cons returned by value, and in that case, two lists could share a tail, but have distinct heads. So long as the list held only immutable values (and properly, all values are immutable), you would be completely safe.

Transform, or map, as it's know in FP circles, is another fundamental algorithm. Transform takes an iterator range and applies a functor to each element in the range and copies the result into a destination output iterator, or, in its second form, takes two ranges and a binary operator, and outputs the result of pair -wise evaluation of the elements in each range, through the output iterator.

int func(int x)

{

return x*x + x + 1;

}

// ...

std::transform(v.begin(), v.end(), v2.begin(), func);

> let func x = x*x + x + 1

> map func [1 .. 10]

Functions and function objects as first-class entities

As you can see, the core STL algorithms are fairly weak by themselves. That is, they don't really do anything by themselves. What they do is capture conventional patterns of function applications to collections. The real power is in the functions themselves. However, C++ functions are fairly limited. Let's say you wanted to write a function that added a constant K to its argument. One way is to write int adder(int x, int K); Unfortunately, it's rather difficult to apply this function with the same constant to every element in a collection.

{Actually, in a few moments we'll see how we can do exactly that almost trivially, but let's hold on to that thought.}

Function objects, aka functors in the OO community (the name means something _entirely_ different in functional programming) , give us a way of extending what functions can do by letting us associate some additional information with the function call. We do this by creating an object with an operator()() method. That lets the object be used where a function is called for, and also to supply the additional information as part of the object the operator is part of.

class adder

{

int K;

public:

adder(int k) : K(k)

{}

int operator()(int i) const

{return K+i;}

};

Then we can do something like:

std::transform(v.begin(), v.end(), v3.begin(), adder(5));

> let adder x = (x +)

> let adder5 = adder 5

> map adder5 [1 .. 10]

But, as you can see, that's a lot of work for a small function that we're probably only going to use in one place.

Still, it's nice to see that we now have an entity that can be used just like a function, but is also a first class entity in the C++ language.

Lambda abstraction and Partial Application

So, how can the adder example be made more convenient. Something that you might actually use?
How about

std::transform(v.begin(), v.end(), v4.begin(), _1 + 5);

> map (x -> x + 5) [1 .. 10]

> -- or, even cooler

> map ( + 5) [1 .. 10]

This is using the Boost Lambda library to constructed a function object in place. One that takes a single parameter, and returns that plus 5. That _1 is what as known as a placeholder. Its type is boost::lambda::placeholder1_type. (And, yes, the leading underscore followed by a number is a perfectly legal variable name.) The functor acts in this context as though it has an operator() with a signature like int operator()(int arg1), and when transform applies it, the output is the same as our earlier example using adder. Except we didn't have create a class just for this single use.

The reason I say that it acts as though it has that signature in this context, is that the actual signature is much more complicated, involving quite a bit of template metaprogramming in order to deduce the correct signature given the actual types of the arguments. If, v, for example, was a vector of doubles, the lambda expression would need to calculate that the return type is also a double, since the type of (double + int) is double. And for non-builtin types, it can be much more complicated, particularly if the lambda expression has more than one free variable.

For example:

k = (_1 * _2)(i,j);

> let k = x y -> x * y

That lambda expression can be applied to any pair of arguments that has an operator*() defined for it, and then as long as k has an assignment operator that can accept the result of that operator*(), everything will just work. However, that flexibility comes with a cost. The actual type of (_1 *_2) is insanely complicated. With the version of boost that I have, with gcc 4.0.2, the type is:

const boost::lambda::lambda_functor, boost::tuples::tuple >, boost::lambda::lambda_functor >, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type> > >

Not a variable or member you would like to declare. Fortunately, it works together with boost::function. You can assign that functor to a boost::function for later use. e.g.

boost::function a = (_1 * _2);

boost::function b = (_1 * _2);

This is also one of the powerful aspects of ML and Haskell, and most modern functional languages. They are strictly typed, but the types can be inferred by the compiler. So the programmer is, for the most part, freed from having to annotate the types of everything. But the compiler will still give you an error if you say something that is really impossible. You get most of the benefits of duck-typing, without having to worry that there is some case that you haven't covered in tests that will result in 'Does Not Understand'.

The boost::lambda library even supports currying, although with a syntax that is a little hard to work with:

boost::function c = bind(protect(_1 * _2), i, _1);

The protect call protects the evaluation of the lambda expression from the bind operation. The bind operation attaches an argument to an expression to be used when the expression is evaluated later. In this case, one of the arguments is a lambda placeholder, so that the result is equivalent to the lambda expression (i * _1).

The documentation for boost::lambda is quite good, and is worth extensive study. So I won't repeat it. Instead, let's focus on ways of using it that you might not have thought of otherwise.

Pipes and Filters Architecture

Pipes and Filters is one of the fundamental architectural patterns identified by Mary Shaw. On a Unix command line, this is expressed with | (pipe), < (redirect stdin), > (redirect stdout), and tools like tee and xargs. In a functional programing system, piping the output of one function to the input of another is via function composition, that is with functions f and g, you compute f(g(x)). This is also sometimes written as f . g. read as f compose g.

Doing this can also be very useful in complex template programs, where the intermediate type is not known, or difficult to express, but when passed directly to another templated function, the compiler computes the type for us.

The goal here is to take a sequence of functions, compose the entire sequence, and then apply that composed function to a sequence of values. Where we end up is

std::transform(

v.begin(),

v.end(),

std::ostream_iterator(

std::cout,

"t"),

foldl1(

fns.begin(),

fns.end(),

composer())

The interesting part is the final stanza. What are foldl1 and composer? Lets work our way outward. The composer is a functor that takes two boost::functions and returns a boost::function that composes them. It assumes that each of the functions has the same signature, which in this case is reasonable, since they've come out of a single sequence. It binds together the two functions and a lambda placeholder, then converts that to a new boost::function.

class composer

{

public:

template

boost::function

operator()(boost::function f,

boost::function g)

{

using boost::lambda::_1;

return bind(f, bind(g, _1));

}

};

Constructing a version of composer that takes functions with different signatures and generates the correct return type is a little more complicated. Take a look at the example code. The trick is to use a nested struct that does the type computation based on the template arguments of the member function. A conventional template metaprogramming approach, but quite strange the first time you come across it.

The next part is the function foldl1. The unusual name is borrowed from Haskell. Once you've learned C++, Java, and Ruby, Haskell is the next language you should learn. Foldl1 is an abbreviation for fold left with one argument. It's very similar to std::accumulate, with one key difference. Instead of starting with a base value, the first value in the sequence is used. This means that it can not be applied to an empty list, but it does avoid having to come up with an identity value, such as 0 for addition, or 1 for multiplication. We could use the function identity(x){return x;}, but that's an extra function call we don't need, and an extra argument to constructing the composed function. And, not all sets have an identity.

template

typename BinOp>

typename Iter::value_type

foldl1(Iter first,

Iter last,

BinOp oper)

{

typename Iter::value_type n

= *first++;

return std::accumulate(first,

last,

n,

oper);

}

So, assuming that fns is, say, a std::vector >, then it's just a matter of pushing the elements of the sequence v through the composed function, and streaming them out through the ostream_iterator.

Since it really is an aha! moment, the best I can do is tell you what led me to it, and hope that helps.

There is a difference between partial application and currying that most experts ignore, because they already understand, but they lie in wait ready to tell you that you have it all wrong.

And you won't understand because the concepts are >thatI'll start with Haskell syntax for the type of a function that takes two integers and returns one.

Integer -> Integer -> Integer

in C that would be

int (*T)(int , int )

Now. what about a function that takes an int and returns a function
that takes an int and returns an int?

(using cdecl syntax)
declare T as function (int) returning pointer to function (int) returning int

int (*T(int ))(int )

or, in Haskell
Integer -> Integer -> Integer

Wait.

Shouldn't those have different types in Haskell? They look really much more different in C !

I can't tell the difference in Haskell between a function that takes two ints and returns an int, and a function that takes one int and returns a function that takes one int and returns an int.

Yes.

Exactly.

AHA!

a -> b -> c

a function that takes an a and returns a function that maps b to c, or a function that takes an a and a b and returns a c. They are entirely equivalent.

Introduction

C++ is known to be a multi-paradigmed language. This is often construed
to mean you can program in both a procedural and and object oriented
style. This is too limiting a view. C++, particularly with modern
library support, is more than capable of supporting programming in
the functional style. Even without modern libraries like boost, or
std::tr1, the Standard Template Library embodies many functional
concepts.

It also turns out that the template system in C++ defines a
metaprogramming language that is a pure, non-strict, lazy, functional
language. Of course, since this was not by design, it is not a
particularly elegant language, as anyone who has had to do template
metaprogramming can attest. For right now, though, I'm going to stay
away from metaprogramming, and look just at what can be done in the
language with the facilities provided.

What is functional programming

At the base, it is performing computations by the pure application of
functions, with no side-effects. Of course C has allowed this since
its inception, and it is never considered a functional language.
There is a lot of debate, and at least a little acrimony, in
determining if a language is functional. There are certainly many
claims of 'my language is more functional that yours.'

Languages that are widely regarded as pure functional languages are Haskell and
ML. Haskell is also getting a lot of alpha geek buzz, for a number of
reasons, and has finally hit the stage where people are learning it
in order to work on something other than a Haskell compiler.

The flavor of ML most commonly encountered is O'caml. The optimizing
compilers for the language are quite powerful, and programs often
compete, and beat, equivalent C programs in efficiency and
performance.

The LISP family has deep functional roots, with Scheme being the version
that focuses the most on functional purity, as well as simplicity and
ease of teaching. Common Lisp has a much broader range of libraries
and facilties defined for it and standardised for it.

JavaScript, Ruby and Python also all have a strong functional component to them.

Examining these languages leads to the observation that the real keys seem to
be

1. Functions as first class objects
   
2. Referential transparency of expressions
3. Partial application, a.k.a currying.
4. Unnamed functions, a.k.a lambda expressions

All of these features have been implemented in C++, in the language
itself, in the Standard Library, in TR1, in Boost, or in custom
libraries such as FC++. This article will examine these in more
depth, and show how they can be profitably incorporated into your
existing practice.

First let's examine what the four cornerstones of functional programming
really mean.

Functions as first class objects means that functions can be used in the same
way as all other entities in the language. In particular, that they
can be passed as values to functions, returned as values from
functions, and new ones can be created at runtime. In C, function
pointers can be passed and returned as values, but creating new
functions is not (portably) possible. In C++, however, we can create
objects that overload operator(), that satisfy all of the desired
properties. Function pointers can also be treated much more generally
with std::tr1::function objects.

Referential transparency of expressions means that an expression, or any of its
sub-expressions can be replaced by the value of that expression or
sub-expression without changing the behavior of the program as a
whole. A computation will always return the same result, and will
only depend on the value of its arguments. This implies that there
are no side-effects to evaluating an expression. No globals that can
be changed, producing non-local changes elsewhere. This property
gives the programmer, and the compiler and runtime, strong
capabilities to reason about the program, optimize it, and
demonstrate its correctness.

Partial application is one of the most unusual, and most powerful, features
of functional programming. This is also known as currying, after
Haskell Curry, a mathematician in the mid 20^th Century who
did some of the fundamental work in combinatory logic and the lambda
calculus. Currying takes a function of N parameters and turns it into
a function of N-1 parameters by fixing the value of one of the
formers arguments. Or, another way of looking at it, is to say that a
function that takes N arguments is equivalent to a chain of N
functions, each taking 1 argument and returning a function that
consumes the next argument. Haskell Curry invented it as a way of
talking about multi-variate functions in a theory of functions of one
variable. Well, Shoenfinkel invented it first, but shoenfinkling
never really caught on.

Unnamed functions don't sound very useful. However, combined with
higher-order functions, that is functions that take and return
functions as parameters, they become very powerful, and quite useful.
If you've ever wanted to supply a simple function inline in a one of
the STL algorithms, but were frustrated with the syntax:

compose2(

plus(),
compose2(multiplies(),

bind2nd(plus(),0.0),

bind2nd(plus(),0.0)),
bind2nd(plus(),1))

you've wanted a better way of writing lambda expressions. Lambda calculus is one of the fundamental theories of computation, and while I'm temptedto start a lengthy exposition, I think a few of quick examples willgive you the flavor.

(Haskell)

\x -> x*x + x + 1

(Lisp)

(lambda (k) (+(+(* k k) k) 1) )

(Boost.Lambda (c++))

_1 * _1 + _1 + 1

The key is that you can provide a definition of a function and then bind
it to a variable, rather than a fixed name. Ideally with nearly the
same syntax as you would use if you did name the function. Functional
languages are often defined in terms of lambda expressions and the
lambda calculus, with syntactic sugar sprinkled on top to make it
more palatable. I'm using syntactic sugar in the techincal sense of a
well defined transformation from one syntactic form to a more
primitive syntactic form. The thing to keep in mind is that too much
syntactic sugar causes truth decay.

Objects vs Values

“Just like an int” has been a mainstay of C++ programming since the very
beginning. The phrase indicates that you can create a new type with
all of the capabilities of a built-in type. What many programmers
don't realize is that the behavior of ints is a polar opposite of the
behavior expected of objects. That is because ints are quintessential
value types. And whereas an object is an entity with state and
identity, values have neither. This 7 here is indistinguishable from
that 7 over there. And 7 never changes (unless you;re using an old
version of FORTRAN) into 8. You evaluate an expression such as 7+1,
and produce an 8, but the original 7 is unaffected. Objects are
different. This object is always distinct from that object, even if
they have the same state. You can change Bob, and everyone who has a
reference to Bob sees the change also. Unfortunately, the mechanism
by which you produce new value types in C++ is exactly the same as
how you produce new object types. You declare a new class.

What you permit and accept by default with that class determines whether
instances of the class behave like values or like objects. The key
pieces of machinery in the language are familiar to all C++
programmers: default construction, copy construction, copy assignment
and destruction. The compiler will provide ones that by default act
(mostly) like a value. Mostly, because of the shallow vs deep issue,
and the fact that pointers are values, even if what they point to
isn't. So what all the compiler instantiated methods do is treat each
member of the class as a value, and then create, copy, assign or
destroy it, in the order they are declared. Unfortunately, for the
programmer concerned with efficiency, and almost all C++ programmers
are, these copies are, or can be very expensive.

Objects, on the other hand, typically either do not accept the default
implementations, or they avoid invoking them. Usually when you say
object2 = object1, you want them to continue to refer to the same
entity. In fact, assignment is fraught with danger, with potential
slicing when assigning a derived to a base. Programmers will either
use a Handle/Body or pimpl_ pattern to separate the implementation
side of the class from the reference side of it, or use a smart
pointer such as std::tr1::shared_ptr. In the evil past, some
programmers would attempt to use raw pointers, and manage the
allocated resources by hand. In practice, it turns out that no one is
smart enough to do so successfully in any program of interesting
size. Or at the very least, if the original programmer is that smart,
the next person to attempt to enhance the system, or fix a bug, is
not that smart.

Lazy functional programming languages, such as Haskell, avoid the price of
copying values by only evaluating an expression when it is needed.
This is guaranteed to be correct because of referential transparency.
Although it can lead to puzzling runtime behavior. I've coded some
benchmarks which seem to take practically no time, because it turns
out that the calculation is never fully evaluated. This takes not
paying for what you don't use to the n-th degree. This call-by-need
behavior is why they are characterized as lazy.

Getting this behavior in C++ is tricky, but far from unheard of. One
technique, used in numerical libraries such as Blitz++, and pioneered
by Todd Veldhuizen, is known as expression templates.

The problem expression templates were introduced to solve is the creation
of unneeded temporaries. Take for example the code

Array A,B,C,D;

//
... stuff

D = A * B + C

Where each of A, B, C and D are two-d arrays, with the usual definitions
for multiplication and addition. The straightforward implementation
of operators *() and +() lead to the creation and destruction of
temporaries, with associated memory allocation and destruction. e.g.

Array operator *(const Array& lhs, const Array& rhs);

has to create and return a new array, which might be quite large, only to
have it used temporarily in Array operator +(const Array&, const
Array&) and then discarded. And even once the expression on the
right hand side of the assignment statement is evaluated, it has to
be passed into the copy assignment operator and very likely discarded
afterwards. (note that this is not an initialization, so that
permitted optimization does not apply).

Template expressions change the operators to return something else, an
expression that encapsulates the arguments, and evaluates them only
when necessary.

ArrayExpression operator +(const Array&, const Array&amp;);

Where ArrayExpression looks something like

class
ArrayExpression {

const Array& lhs;

const Array& rhs;

//....
more stuff

double operator(int,int); //compute the value at the point

}

Now, for lazy languages, like Haskell, this can be built into the language
itself, and in this case the concept is called a 'thunk'. Because by
the time you need to think about it, the thought has already been
thunk. Yes, it's a really awful joke. You have to remember, we work
in an industry where an extremely popular language is named after an
obscure, although influential, comedy troupe. Other industries do not
consider understanding why Norwegian Blue Parrots are funny a job
qualification. Nor do most of our managers, unless they came up
through the ranks themselves.

Referential transparency makes thunks extremely powerful because not only can
they be passed around instead of fully evaluated values, once they
are fully evaluated, the system can remember that value and use it
from then on. This is very much like common sub-expression
elimination, only it is a runtime feature, as well as a compile time
optimization.

OK, with that title, I'm sure to please almost no one. If you want to know how to do REST-ful programming in Haskell, or tie REST to C++, move along, there's nothing to see here. The connection isn't at the implementation level. Which is the whole point.
So what do REST, Monads and (successful) Template Metaprogramming have in common?
Strict maintenance of levels of abstraction, and extremely narrow interfaces between those levels.
What does that get you?
Extremely (and possibly maximally) reusable abstractions (code).
What triggered the realization for me was a paper on Arrows by Hughes, which asked the question 'Why are Monads so reusable when the have such a small interface', although not in those exact words. It dawned on me that they are so reusable exactly because they have such a narrow, but still very well defined, interface. They can do that because Monads are all about abstracting out features. A particular Monad will delagate all the real work down to the type it is being run over. Its real job is constraining the ways the values of the types it is a Monad over can be combined.
The analogue I have in mind for C++ MP is the swap() method. In a C++ template, we can assume that we can call swap on two values, that we otherwise know nothing about, and that the two values will be exchanged in a way that does not throw any exceptions, and is the best way of exchanging two values of that type. The abstract notion of swapping two values is delegated to the concrete implementation of the type being templated over.
A REST-ful web application exposes PUT, GET, POST, and DELETE on resources named by a URI. Nominally not much to have a really rich experience. OTOH, Google Map mashups contradict that.
It's not the richness of the interface of the metalevel, it's the richness allowed at level below. The narrow, but well defined, interface, where that interface delegates to a lower level abstraction, is exactly what enables composeability.
Monads, being firmly grounded in Functors in Category Theory, take this to an extreme level of rigor. There are laws that must be satisfied for a thing to be called a Monad, and those laws ensure that other Monads can interoperate, and achieve the Principle of Least Surprise.
I'm not intending this to be Yet Another Monad Tutorial. So I won't go too deep here. But monad transformers show a degree of generic reusability that is awfully hard to achieve with C++ templates, even though C++ templates have similar expressive power (with a horribly clumsy syntax).
Monads are functions (functors) that take types to types, and so correspond to mpl metafunctions. But they preserve the underlying structure on the types they operate over. In particular, composition is preserved. So if I have an function of type a -> M b, and a function b -> c, I get a working a -> M c for free, just by using fmap. In C++ it would be like
template foo(A)
and
C bar(B)
getting you to
template foo(A) by saying template fmap(a,b), or even better just fmap(a,b) and letting the compiler figure out types.
(where foo is something like
template foo(A a);)
That looks so impossible in C++, that most C++ programmers have no intuition about it.
But every time you wish that you didn't have to write some type that the compiler already knows, like the iterator or value_type or return_value, particularly when they get really messy, you're looking for what Monads, or at least what Hindley-Milner type inference, provide.

oh
yes
of course
i had forgotten
my god, it's full of stars