[boost] Review: Lambda library - more technical analysis

From: Asger Alstrup Nielsen (alstrup_at_[hidden])
Date: 2002-03-25 07:22:19

Over the weekend, I have tried to analyse in more
detail, what I do not like about the LL. I hope
this will help explain my vote.

What is the Lambda Library
--------------------------

Lambda Library is designed to allow anonymous functions in C++.
It is especially designed to ease the use of STL algorithms.

As such, Lambda Library is a 80% reimplementation of C++ inside C++.
Many language constructs are reimplemented so they can be
used in lambda expressions.
There are restrictions and limitations in C++, and therefore
the reimplementation is suboptimal in many places. Special helpers
are added to work around the problems. The reimplementation also
includes wrappers for a bunch of STL algorithms.

The result is that you can write full-blown anonymous C++ functions
as a substitute for ordinary C++ functions. They are specifically
usable in cooperation with the STL algorithms.

So, given the tools at hand, the authors certainly have solved
the problem they wanted to solve very well. C++ lacks a bunch of
features, and therefore it is hard to solve the problem better
than they have.

In addition, the library meets all the Boost requirements:
It uses the proper coding style, it has good documentation.
there is a test-system, the code is probably as nice as it
can get, and so on.

So why do I think it should not be accepted at the present time
in Boost?

I have three major issues that I elaborate on in the following:

1) LL is trying to solve the wrong problem
2) LL is a new programming language, which lacks important features,
   and has many superfluous features
3) LL position in the field as such is being challenged

I consider these issues to be serious enough that I do not vote
to accept the library before they are resolved. In particular, I
consider my objections to be concrete and technical, and not
just FUD.

1) LL is trying to solve the wrong problem
------------------------------------------

First of all, I think LL is trying to solve the wrong problem.
It's the wrong problem in three ways:

1) I personally think that a lambda library should focus much
   more on the functional style of programming, in addition to
   the imperative view, LL has. I return to this point later,
   and hope to illustrate that it is a technical issue.

2) The problem can not be solved satisfactory. C++ does not
   have the features needed to do this properly, and the result
   is not complete, nor "clean".

3) In solving the problem, LL de-facto introduces a new
   programming language inside C++, which tries to mirror
   C++ itself as much as possible. This is questionable for
   several reasons:
    a) Study Common Lisp to see where this trend takes you.
       If you have the energy to read the hundreds of pages
       with one small programming language after the other
       all inside the same language, I think you will discover
       that you should think twice before introducing a new
       language.
    b) If you have to introduce a new programming language
       in order to solve the problem, it might be worth it
       to go for a different language which can be embedded
       more nicely.

Well, people can choose to solve any problem they like,
and it is not fair to reject a library just because they
do not solve the problem you would like them to.

While I agree with this in general, I think this case is different.
In order to explain myself, let's first have a closer look at
the concrete solution to the stated problem.

2) LL is a new programming language
-----------------------------------

LL tries to reimplement C++ inside C++ in order to provide the
feature of anonymous functions.

It is in fact a new programming language, because it is not
possible to use the same keywords or syntax, and it is not possible
to implement things exactly like you like, because of limitations
in C++.
There are many things to learn: When should you use "var",
"constant", "ref", "cref", "bind<Type>", "ret<type>", ...
Besides the basic core stuff with variables, operators, and
constants, the library also provides for-, while- and switch-
statements, exceptions, new/delete and constructors and probably
more.
Many of these use clumsy syntax, some have subtle issues to be
aware of, and the error messages from the compiler are hard to read.
While the documentation is great, you will not get a lot
of help from the compiler in order to learn this new programming
language.

In other words, both the syntax and the semantics of the
lambda language is different from C++. So there is a lot to learn,
and it will probably take a while to become fluent in this new,
kind-of-strange programming language.

But the good thing is that all of this allows you to write
some pretty complex code at the point in the code where you
need it.

Or does it?

Well, complex expressions take a long time to compile, the compiler
might not be able to compile them due to template depth, and the poor
error messages make it hard to write complex code. These problems
lead the authors themselves to advise against writing complex
lambda expressions.

In addition, there is a very important restriction:

You can not define named, local variables inside a lambda expression!

Certainly, you need local variables in complex code, and yet,
this feature is not present. All you have is the current scope,
three parameter, and the "unlambda" function to instantiate
a lambda functor.
The parameters are not scoped by themselves, so you have to
use the unlambda function to simulate a kind of local variables.
There is no way to locally introduce names for nested parameters,
and this makes it tricky to write nested lambda expressions.
To me, it puts a limit to how nice the imperative programming
in lambda expressions will be.

The end result, to me, seems to be this: While LL technically provides
a way for you to write complex lambda expressions, the reality is
that it is only practical for one-line expressions.

Given this, it seems ironic to me that the authors provide all
these features. I fail to see the need for most of the constructs,
and it hardly seems worth the effort to learn this new programming
language just to write one-line expressions that only need a fraction
of the features.

To this, the authors have countered that you only pay for what you use.
Well, I have to pay for what my colleagues use, and I don't want them
to write complex lambda expressions with LL, because then I have to
learn this new programming langauge. The best way to prevent this is
to take the unneeded bits out of LL.

So I state that all of this machinery is only useful for one-liners.
This is surprising when you consider what lambda expressions
in the general functional programming style can do for you: Lambda
expressions with proper scoping are Turing complete in themselves.
On the other hand, lambda expressions with only global scope are
not. Those local variables are important!

Well, one thing is theoretical considerations. Lambda expressions
are practically useful, because they taste like having first-order
functions at your disposal. At least, that was what I thought and
had hoped for.
It turns out that it is possible to save lambda expressions as objects
themselves. However, a technical limitation prevents this from being
practical: The type of a lambda expression is too complex to write
yourself, and not even Boost::function can understand it.

So I'm left with a feeling that we are so close to getting the real
thing, but it's not there. Instead, there is a lot of unneeded
stuff that will make life harder for me, because I will have to learn
it if my peers use LL. And when they do, the result will not be
beautifyul, but a strange kind of code where much of it is bookkeeping
code that is needed to make things work.

I would rather trade all of the control-flow stuff, the new/delete
stuff, and the constructors, that I think are counter-productive,
for two concrete features:

- Proper interaction with boost::function to allow a kind of
  first-order functions. This is important to gain the full
  benefit of lambda functions.
- Local variables, or scoping, in the lambda expressions to
  allow nested expressions, and give more power

It is entirely possible that this can be provided in a new layer,
but I think such a layer is a prerequisite for adoption.

3) LL position in the field as such is being challenged
-------------------------------------------------------

I do not want to elaborate much on this, because this has been
elaborated on already.

Phoenix is coming, and from what Joel said, it is coming fast.
I think Phoenix is a better lambda library, because it does not
have the bloat, it meets the functional needs better, and from
the initial look, it seems easier to extend.

In addition to this, there are a number of smaller issues with
the concrete implementation in Lambda Library now:

- The strong arity checking
- The syntax of control statements
- VC6 compatibility
- The documentation does not include an analysis of the
  relation to traditional lambda expressions as know from
  functional programming

All in all, I maintain my vote not to include the current lambda
library in Boost.

Greets,

Asger Alstrup Nielsen

--
A collection of some minor errors in the documentation:
Introduction:
"...which implements [a] form of..."
boost\libs\lambda\doc\ar01s04.html:
Missing space in footnote: "..functionality ofstd::for_each..."
5.6
"and ouptuts"
5.9.1
Last line in example lacks a parenthesis
8
"must be written explicilty"
                        ^^