Let's Talk About Lambda Functions!

James J. Besemer jb at cascade-sys.com
Fri Aug 2 08:38:47 CEST 2002

Bryan Olson wrote:

> James J. Besemer wrote:
>  > Lambda and the Lambda Calculus have nothing to
>  > do with "control structures," per se.

> That strikes me as failure to abstract.  Lambda can emulate any of the
> control structures, and the control structures can all be described as
> functions from states to states.

We're talking the difference between Imperative and
Declarative languages which are radically different.

Characteristics of imperative languages:

  1. Model of computation based on a step by
      step sequences of commands.
  2. Program states exactly how the result is to
      be obtained.
  3. Destructive assignment of variables.
  4. Data structures changed by successive
      destructive assignments.
  5. Order of execution is crucial, commands
      can only be understood in context of previous
      computation due to side effects.
  6. Expressions/definitions cannot be used as values.
  7. Control is the responsibility of the programmer.

Characteristics of declarative languages:

  1. Model of computation based on a system where
      relationships are specified directly in terms of the
      constituents of the input data.
  2. Made up of sets of definitions or equations
      describing relations which specify what is to be
      computed, not how it is to be computed.
  3. Non-destructive assignment of variables
      (or no assignment at all).
  4. Explicit representations for data structures used.
  5. Order of execution does not matter (no side effects).
  6. Expressions/definitions can be used as values.
  7. Programmer no longer responsible for control.


As alternative choices of notation (syntax and semantics)
they're different in almost every conceivable way!
The last point specifically contrasts 'control' structures,
essentially present in one and absent from the other.

The fact that they're equivalent in an abstract mathematical
sense and that each system is able at some level to emulate
the other does not change the fact that how they work and
consequently how each is used in practice, is radically

Closer to the real world, it's like you're saying there's nothing
in Python that can't be done in C++ or Perl or even assembler.
While technically true, there nevertheless are many practical
reasons for preferring Python.  Python's "if" (not to mention
lambda) is simply "more powerful" than the assembly equivalent.
That is to say Python is more economical for people to use
and hence more powerful.

> > Smalltalk's "blocks" are more powerful than Python's
> > Lambda and even Church's Lambda notation.
> The lambda calculus is equal in power to the Turing machine.  In the
> important sense, no implementable language is more powerful.

I agree your statement is true, though I dispute that this is
"the important sense" for evaluating the "power" of languages.
The conclusion actually is of very little practical importance,
as it doesn't give us any means of discriminating one language
from another.  It says they're all equal when we know quite
the opposite is true.  The practical value of the mathematical
theory may only be perhaps to help distinguish the possible
from the impossible -- what's computable from what's not --
but those boundaries are far from our present domain of

In the real world, "power" means the rate at which work
is done.  So when discussing the power of a language
(outside the narrow context of automata theory), it
makes more sense to evaluate languages from an
economic standpoint -- that is how easy or difficult
it is for humans to express themselves using a
particular language or language feature.

Thus, from a practical, economic standpoint, and in the
overall context of this thread, my statement above still
holds.  It's easier to express a wider range of useful
actions in Smalltalk's blocks than in the other alternatives.

Actually, from a purely theoretical standpoint, all
programming languages are substantially less powerful
than Turing machines and other mathematical abstractions.
The mathematical models all assume infinite time and space
(zero time and infinite space?), whereas all real world
languages in comparison are necessarily severely limited
in those dimensions.

So real world languages from a theoretical standpoint
are infinitely less powerful than the theoretical ones and
yet at the same time from a practical standpoint they're
infinitely more useful.

Go figure.



James J. Besemer  503-280-0838 voice
http://cascade-sys.com  503-280-0375 fax
mailto:jb at cascade-sys.com

More information about the Python-list mailing list