Of what use is 'lambda'???

[Kragen Sitaker]

In article <wk8zso744u.fsf at turangalila.harmonixmusic.com>,
Dan Schmidt  <dfan at harmonixmusic.com> wrote:
>ge at nowhere.none (Grant Edwards) writes:
>| In Scheme, lambda is the only way to create a function. There is
>| some syntactic sugar that lets you leave out the actual string
>| "lambda" if you want, but I always leave it in.
>| 
>| Does elisp have a non-lambda predicate to create functions?
>
>Yep:
>
> - Special Form: defun NAME ARGUMENT-LIST BODY-FORMS
>     `defun' is the usual way to define new Lisp functions.  It defines
>     the symbol NAME as a function that looks like this:
>
>          (lambda ARGUMENT-LIST . BODY-FORMS)
>
>     `defun' stores this lambda expression in the function cell of
>     NAME.

To me, that looks a lot like "syntactic sugar that lets you leave out the
actual string "lambda" if you want", rather than "a non-lambda
predicate to create functions".

I mean, it says right there in the doc string that defun's only purpose
in life is to create a lambda expression and store it in the function
cell of NAME.


In answer to the question, "What is lambda good for?", I can think of
two answers:
- it is useful to bind arguments, e.g. lambda x, y=zz: do_something(x,
  y) --- which can be passed as a function in place of do_something.
- why would you want to make an indirect function call in the first place?

The answer to the second is deep.  

Of course, you don't ever *need* to make an indirect function call; in
procedural programming, you can write code like this:

	if fcode == 1:
		do_thing_one(x, y)
	elif fcode == 2:
		do_thing_two(x, y)
	else:
		complain(fcode)

And when you add a new fcode value, you just have to go to every
if-elif-elif-else switch and add a new branch.  This is kind of bad, in
that it scatters information about what fcode==2 means all over the
place, and it's likely that it would be handier to have it all in one
place.  (There's a balance, of course.  Sometimes what fcode==2 means
has more to do with the code the if-elif thing is in the middle of than
with the other branches that also happen when fcode==2.)

With object-oriented programming, you can do something like this instead:

	fcodething.do_something(x, y)

and rely on dynamic method dispatch to do the right thing.  This has
the advantage that you can put all the do_something and
do_something_else methods together.

With functional programming, instead, you say:

	fcode(x, y)

and just use indirect function invocation to do the right thing.
Closures (like lambda x, y, z=foo: do_something(x, y, z)) make it
possible to store state in an invocable function, which means that
functions (closures, lambdas) become equivalent to objects.

There are times when functional code --- passing around lambdas --- is
clearer, and there are arguably times when object-oriented code is
clearer.  Functional code seems to me more likely to be more flexible,
but that's kind of a fuzzy statement and could be nonsense.

Closures are sort of equivalent to objects with a single method.  If
you want to do multiple methods, you have to use some parameter to
decide which one to invoke.  This makes it hard to go from a
"single-method" function to a "multiple-method" function --- you have
to change every call to it.  You can do prototype-based "inheritance"
by delegation --- call some "prototype" function if you don't
understand the requested method.  Here's an example, albeit a specious
one, since Python has stacks built in:

def stack(op, arg, data, prototype):
	if op == 'push':
		data.append(arg)
	elif op == 'tos':
		return data[len(data) - 1]
	elif op == 'pop':
		data.pop()
	else:
		return prototype(op, arg)

def make_stack(prototype=lambda op, arg: None):
	return (lambda op, arg=None, data=[], prototype=prototype: 
			stack(op, arg, data, prototype))

>>> x = make_stack()
>>> x('push', 3)
>>> x('tos')
3
>>> x('push', 4)
>>> x('tos')
4
>>> x('pop')
>>> x('tos')
3
>>> x('pop')
>>> x('tos')
Traceback (innermost last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 2, in <lambda>
  File "<stdin>", line 5, in stack
IndexError: list index out of range
>>> x('unknown')
>>> def hello():
...     print "hello, world"
... 
>>> x = make_stack(lambda op, arg: hello())
>>> x('push', 37)
>>> x('tos')
37
>>> x('unknown arg')
hello, world


Just as you can create a lambda that acts like an object, you can
create an object that emulates a lambda, simply by creating an object
with only one method.  Both are kind of awkward.  (It gets a lot worse
when you start trying to do multiple inheritance with lambdas, closures
with objects, etc.)

(Also, even without closures, function pointers allow you to simulate
objects in languages that really have only structs: C, JavaScript, and
Lua come to mind, and of these, JavaScript and Lua have syntactic sugar
to make it easier.  In C, you have to say things like 
obj->method(obj, arg).)

So both approaches are equally powerful; but both of them are more
convenient for expressing certain kinds of algorithms.  

Lambdas seem to be especially convenient for expressing non-mutative
stateless algorithms: map, filter, zip.  Objects seem to be especially
convenient for writing things with lots of state that can be peacefully
extended later on.

Lambdas make it possible to have really private attributes, even in
libertine[0] languages like Perl, JavaScript, and Python.  Well, maybe
not in Python --- I don't know it well enough yet, but I wouldn't be
surprised if there were a way to get at default argument values ;)

In Perl (and, I think, JavaScript), you can use closures to have really
private methods, too.  This has the unfortunate disadvantage that if
the methods are potentially recursive, the closures will have circular
references and screw up the reference-counting garbage collection, so
you have to deallocate things by hand or leak memory.

Sometimes it's clearer to write a function in-line in a lambda, even
when you're not binding any data into a closure.  

"sort" is the usual example; you could define an interface (or
protocol) "comparator" consisting of a method "compare" which compared
two objects in some user-defined way, and then specify your sort
routine to require an object implementing "comparator" which compares
objects.  This has the disadvantage that the order you want the data in
is specified in a different class from the one that wants it sorted,
which often means that it's actually in a different file --- by
convention or by language requirement.

Defining a comparator function is often much easier --- you can usually
put it in the same file.  But, in many languages, you still have to put
it outside of the routine that wants the sorting done --- which means
that it's ten, twenty, forty lines away from the sort call.

Being able to write the function in-line in a lambda keeps related
things together and unrelated things apart, which makes your code
easier to read, easier to write, easier to find bugs in, and easier to
improve.

academically y'rs  - kragen

[0] Libertine?  Do I really mean libertine?  Eiffel programmers surely
    think so --- but then, the late-binding crowd is fond of accusing
    Eiffel hackers of being into bondage and discipline, so maybe I
    should stay away from the whole subject --- say no more, say no more! [1]
[1] See, I'm not *totally* Monty-illiterate.
-- 
<kragen at pobox.com>       Kragen Sitaker     <http://www.pobox.com/~kragen/>
Perilous to all of us are the devices of an art deeper than we ourselves
possess.
                -- Gandalf the Grey [J.R.R. Tolkien, "Lord of the Rings"]