Re: functional programming is great, but why lists?

[Daniel Mahler <mahler@cyc.com>]

Hi guys,

I find the direction of this discussion surprising.
I consider the primary reason  that higher order languages
had concrete data structures primarily to be efficiency,
though printing, debugging and equality tests are also a consideration.
Cons cells take op two words (plus intrinsic GC bookkeeping overhead)
and the basic operations on them are trivial.
The functional datastructures contain their code
and basic operations are significantly more complex too.

The reason that the pure lambda calculus is not adequate for
defining libraries is that it does not have a global definition mechanism in the language;
in formal lambda calculus proofs the definitions are in the metalanguage.
Provided one can make global defininitions (ie define)
then functional data structures
are "adequate" for building libraries provide you have the time and
memory to use them.

I doubt that the reason for concrete dat structures is catching type
errors; that can be done better by a type system.
Of course the type system then has to be expressive enough
to implement the data types.
The result though is not pretty (see Girard's Proofs and Types).

Daniel Mahler



Shriram Krishnamurthi writes:
 > Michael Vanier wrote:
 > 
 > > Thus, I don't understand Olin's comment about lambda not being sufficient,
 > > unless lambda + lists are also not sufficient.  I'm not being facetious; I
 > > know this is hopelessly inefficient, but we're talking about what's
 > > necessary in principle.
 > 
 > ... and Olin's not.  That's your difference.  (I should have provided
 > some context.  Olin was referring to the creation of libraries for
 > practical Scheme programming.)
 > 
 > If that answer isn't good enough, I'll give you one more:
 > 
 >   Are there type errors in the lambda calculus?
 > 
 >   Should there be type errors in a useful, realistic programming
 >     language?
 > 
 > There you go.
 > 
 > Shriram