Re: Implementation of list concat and subclass conditio

[Peter M|ller Neergaard]

Sergey Mechveliani wrote:

> > I am doing a graduate student project with the aim of veryfying the result
> > of Bird, Jones and de Moor that lazy languages has the same time complexity
> > as impure Lisp on a problem proposed by Pippenger (The problem is solved in
> > a strictly higher complexity by a pure Lisp than in an impure Lisp program).
> > [...]
> 
> This is interesting. Could you provide a reference to these problem and 

Pippenger's originally description of the problem can be found in the record
from POPL'96, 

@InProceedings{pippenger:96:PureVsImpure,
  author =       "Nicholas Pippenger",
  title =        "Pure Versus Impure Lisp",
  pages =        "104--109",
  booktitle =   {Conference Record of POPL '96: The $23^{\mathrm{rd}}$ ACM
                  SIGPLAN-SIGACT Symposium on Principles of Programming
                  Languages},  
  month =       {21--24 } # jan,
  year =        1996,
  address=      {St.\ Petersburg Beach, Florida},
  organization= ACM,
  key =         {ACM},
  annote = {The aspect of purity versus impurity that we address involves
    the absence versus presence of mutation: the use of primitives
    ($\mathtt{RPLACA}$ and $\mathtt{RPLACD}$ in Lisp, $\mathtt{set-car!}$
    and $\mathtt{set-cdr!}$ in Scheme) that change the state of pairs
    without creating new pairs. It is well known that cyclic list structures
    can be created by impure programs, but not by pure ones. In this sense,
    the impure Lisp is ``more powerful'' than pure Lisp. If the inputs and
    outputs of programs are restrictred to be sequences of atomic symbols,
    however, this difference in computability disappears. We shall show that
    if the temporal sequence of input and output operations must be
    maintained (that is, if computations must by ``on-line''), then a
    difference in complexity remains: for a pure program to do what an
    impure program does in $n$ steps, $O(n \log n)$ steps are sufficient,
    and in some cases $O(n \log n)$ steps are necessary.}  
}

@Article{bird:MoreHaste,
  title =        "More haste, less speed: lazy versus eager evaluation",
  author =       "Richard Bird and Geraint Jones and Oege de Moor",
  pages =        "541--547",
  journal =      "Journal of Functional Programming",
  year =         1997, month = sep,
  volume =       7, number = 5,
  annote = {Nicholas Pippenger has recently given a problem that, under two
    simple restrictions, can be solved in linear time by an impure Lisp
    program, but requires $\Omega(n \log n)$ steps to be solved by any eager
    pure Lisp program.  By showing how to solve the problem in linear time
    with a lazy functional program, we demonstrate that---for some problems
    at least---lazy evaluators are strictly more powerful than eager ones.}
}



Furthermore Amir Ben-Amram, who was visiting the Department of Computer
Sciences, has made some notes on the problem

@Misc{ben-amram:1996:Pippenger,
  author =       {Ben-Amram, Amir M.},
  title =        {Notes on Pippenger's Comparison of Pure and Impure LISP},
  year=           1996, month = jun,
  keywords =     {LISP, pure LISP, mutation, destructive update, selective
                  update}, 
  annote = {This notes arose from a talk, in which I discussed Pippenger's
    recent result on Pure versus Impure LISP (paper in POPL '96).  They
    include an explanation of the nature and significance of Pippenger's
    results, a discussion of the limitations of the result and ensuing open
    problems, and finally of certain follow-ups.},
  semno =        {D-277},
  url =          {ftp://ftp.diku.dk/diku/semantics/papers/D-277.ps.gz}
}

There are probaply more references, but this is what I am using as the
stepping stones for the moment.

Best regards

Peter Mxller Neergaard


-- 
                                  __   _
Peter Mxller Neergaard           /  \-' )      ,,,  WWW: http://www.diku.dk/
Dept. of Computer Science       | |  ()|||||||[:::)            students/turtle/
University of Copenhagen         \__,-._)      '''  
E-mail: turtle @ diku.dk        
        ``Will all these memories be lost in time, like tears in rain?''