From: Robert P. Krajewski
Subject: Spreadsheets and Lisp {was: Letter From Ted Nelson}
Date:
Message-ID: <rpk-1006950123280001@192.0.2.1>
[Most groups removed, comp.apps.spreadsheets added.]
········@crl.com (Andrea Chen) wrote:
>······@netcom.com (Henry Baker) writes:
>
>>In article <··········@crl4.crl.com>, ········@crl.com (Andrea Chen) wrote:
>
>>> A historical example is the spreadsheet
>>> (a product which helped launch the PC revolution). Two features
>>> which distinguished it were its matrix frontend and "automatic
>>> recalculation" in the backend. This second feature is natural to
>>> Lisp dialects which could have served as an engine. They would
>>> also have provided call by name (not just cell number) and
>>> "multidimensional" structures. It took spreadsheet engines over
>>> ten years to evolve these features on their own.
As somebody who has done both Lisp language implementation (Lisp Machine
Lisp, Golden Common Lisp) and spreadsheet implementation (Lotus Improv),
I do not quite follow the implication here, which seems to be that Lisp
has an evaluation model which eases the implementation of a spreadsheet.
Spreadsheet recalculation can be looked as a propagation of changes across
a graph (possibly cyclic), something for a truth maintenance system to
handle in a general way, or an interesting constraint propagation problem,
and those are the kinds of computing applications and strategies that have
been explored quite fruitfully in Lisp (for good reason). But Lisp itself
doesn't really work like spreadsheet. Setting a Lisp variable doesn't make
things happen the way that editing a spreadsheet cell makes things happen.
>>The first spreadsheet _was_ prototyped in Multics Lisp by Bob Frankston,
>>which became 'VisiCalc', I believe.
Most likely, Frankston used Lisp to start prototyping things because he
thought it was a great language for prototyping. Make a mistake, and
you don't kill your environment. In fact, the Lisp in GNU Emacs was used
to analyze some aspects of Improv cell storage. No special reason -- it
was just the most reasonable interpreter we had lying around at the time.
The developer could have used C++ or awk or perl but he had better things
to do with his time.
>Then the author missed some of the funamental powers of Lisp. One of
>the problems with classical spreadsheet "recalculation" was that
>if a number was changed, the whole thing had to be recalculated.
>As spreadsheets grew more and more powerful computers were requied
>to process in real time.
First, see first paragraph. Second, there are ways to be clever
about the work that has to be done -- it's called "minimal recalc."
Modern spreadsheet data structures usually incorporate some form
of dependency information (which is cheaply pre-arranged) to help
this implementation of this cleverness. In fact, there are situations
where it's faster to just do the evaluation than to figure out if
it should be done in the first place. (Spreadsheets have this luxury
because most operators in the spreadsheet "language" tend to be free
of side effects.)
>
>
>In a Lisp statement of the form
>
>(SET CELL1 '(ADD CELL2 CELL3 CELL4))
>
>a change in CELL3 would be automatically compensated for by the statement
>
>(EVAL CELL1)
Sorry, but that doesn't make things any more efficient. Think: who's
going to arrange for (EVAL CELL1), or really, something more like
(SET 'CELL1 (EVAL (GET 'CELL1) 'FORMULA))) to be evaluated in the
first place. Clearly, if you just do that pattern of evaluation for
every cell in the spreadsheet, you're right back to the most
sledgehammeroid spreadsheet implementation possible.
>
>Lisp would also have made it possible to support sparse matrixes thus
>multiplying the amount of data which could be stored.
Although Lisp is a great language for making interesting data structures,
Lisp has no monopoly on a reasonable implementation of sparse matrices.
As it turns out, a commercial spreadsheet usually does have simple
sparse matrix implementation -- for a two-dimensional spreadsheet, simple
is usually good enough for real-world cases. In fact, that GNU Emacs
Lisp-using developer I mentioned earlier did a very clever C++-based
implementation of a matrix of cells (Improv worksheets can have up to
twelve dimensions) that handled sparseness quite nicely, thank you.
>It would also
>be possible to make symbolic links to the grid form (which helps make
>the frontend (interface) easy to use.
>
>(SET FIRST_QUARTER CELL1)
>(SET JAN CELL2)
Cool, but why bother with cell names in the first place ? If you can
scare up a copy of Improv (development after version 2.1 for Windows
was cancelled approximately a year ago), you'll see what I mean. But
you're right in noticing the connection of this feature with Lisp.
Improv's name-to-internal-location mapping implementation is much like
what Lisp hackers used to call an "obarray", on which strings are "interned,"
yielding "symbols." (It is run on exactly the same principles: hashing
text, and maintaining one unique object for each text string encountered.)
>And also to build non numeric logics into the system. �ics
>inherant in Lisp (or Snobol or a number of other languages) could
>have provided a far richer logical environment for spreadsheets.
>Only in the last five years have these evolved independantly into
>modern spreadsheets.
True, although I think strings have been there since the beginning.
A sad example: in the three spreadsheets I know best (Excel, 1-2-3,
Improv), a date is just a number *formatted* in a certain way. And,
I beleive that early versions of the Mac and Windows version of
Excel used slightly different conventions for the representation of
a date as a number (I think the difference was which date was "0.")
Ugh !
Improv did advance the model of a spreadsheet, but the real
leap that nobody's really made yet is to allow arbitrary datatypes
to participate in what a spreadsheet is good at -- taking a set
of rules and values, and keeping them consistent.
From: Andrea Chen
Subject: Re: Spreadsheets and Lisp {was: Letter From Ted Nelson}
Date:
Message-ID: <3rdvmd$fnj@crl6.crl.com>
The following is part of a discussion in which I claimed that good
ideas could be wasted unless they were implemented. An example
I gave was spreadsheets. I claimed that if the language was
built directly in the structures of a Lisp like logic that
capacities which have only become recently availible in the last
few years.
I have sliced out some statements from a counter claim.
In the following I use a destructive Lisp dialect known as TRAC
#( ) is roughly equivalent to EVAL, the logic within is carried
out. i
( ) is roughly equivalent to ' (Quote) the information within is
protected.
ds stands for define string and is roughly equivalent to SET
::Language example::
#(ds,subject, History Of Computing)
#(subject) would result in " History Of Computing"
···@world.std.com (Robert P. Krajewski) writes:
>As somebody who has done both Lisp language implementation (Lisp Machine
>Lisp, Golden Common Lisp) and spreadsheet implementation (Lotus Improv),
>I do not quite follow the implication here, which seems to be that Lisp
>has an evaluation model which eases the implementation of a spreadsheet.
>Spreadsheet recalculation can be looked as a propagation of changes across
>a graph (possibly cyclic), something for a truth maintenance system to
>handle in a general way, or an interesting constraint propagation problem,
>and those are the kinds of computing applications and strategies that have
>been explored quite fruitfully in Lisp (for good reason). But Lisp itself
>doesn't really work like spreadsheet. Setting a Lisp variable doesn't make
>things happen the way that editing a spreadsheet cell makes things happen.
This is correct. A classical spreadsheet variable is part of a 2
dimensional array. Finding the cell is a relatively straightforward
algorith which involves numeric operations on X and Y. If multiplies
are done with shifts this can be done in a few dozen cycles on a
fairly limited architecture.
A Lisp structure is a "call by name" variable.
Lisp trees can be made very efficient. Or a hashing algorithm can
be built with slightly more numerical calculation than in a
numeric matrix call.
A simple hashing algorithm can find a value in a hundred of so
machine cycles. A Lisp call is an order of magnitude less efficient
(or more) than a matrix lookup.
However this only works if you have a dense matrix. If you build
a sparse matrix (in which only cells which are used are mapped)
then the difference is not so great.
>Most likely, Frankston used Lisp to start prototyping things because he
>thought it was a great language for prototyping. Make a mistake, and
>you don't kill your environment. In fact, the Lisp in GNU Emacs was used
>to analyze some aspects of Improv cell storage. No special reason -- it
>was just the most reasonable interpreter we had lying around at the time.
>The developer could have used C++ or awk or perl but he had better things
>to do with his time.
C++ and Perl and even awk were unlikely to be avilible at the time.
>First, see first paragraph. Second, there are ways to be clever
>about the work that has to be done -- it's called "minimal recalc."
><<Modern>> <<*>> spreadsheet data structures usually incorporate some form
>of dependency information (which is cheaply pre-arranged) to help
>this implementation of this cleverness. In fact, there are situations
>where it's faster to just do the evaluation than to figure out if
>it should be done <<**>> in the first place. (Spreadsheets have this luxury
>because most operators in the spreadsheet "language" tend to be free
>of side effects.)
>
::Modern:: misses the point I tried to make. I am willing to admit
that some modern spreadsheets are high powered analytical systems and
can compete with such things as coherant Lisp for many problems.
However the main point I was trying to make was advanced ideas
(such as Lisp or Xanadu) don't necessarily catch. It took a decade
for spreadsheets to begin to match the logical capacities of
Lisp. I am talking 1982 spreadsheet not 1995.
::**:: If a cell is called for display or storage and it has been
defined as (eg.)
#(ds,first quarter,(#(+,#(jan),#(feb),#(mar)))
then the system looks up the first 3 months and adds them. With
3 lookups and various odds and ends this could end up costing a
copy thousand instructions. In modern computers which approach
one instruction per cycle and 100 million cycles per second this
means tens of thousands of such operations performed in
a blink of an eye.
>Sorry, but that doesn't make things any more efficient. Think: who's
>going to arrange for (EVAL CELL1), or really, something more like
>(SET 'CELL1 (EVAL (GET 'CELL1) 'FORMULA))) to be evaluated in the
>first place. Clearly, if you just do that pattern of evaluation for
>every cell in the spreadsheet, you're right back to the most
>sledgehammeroid spreadsheet implementation possible.
You don't evaluate every cell. You evaluate those you are looking
at. If you changed CELL4 in an early eighties spreadsheet you
might have to evaluate thousands of members to make the change.
A Lisp system can point to those cells which need changing.
It can also be updated.
If it is june then one can assume the first quarter is fixed for
the year.
#(ds,first quarter,#(first quarter))) will assign the value of
jan, feb and mar to the cell. The other cells can be removed.
>Although Lisp is a great language for making interesting data structures,
>Lisp has no monopoly on a reasonable implementation of <<sparse>> matrices.
>As it turns out, a commercial spreadsheet usually does have simple
>sparse matrix implementation -- for a ::two-dimensional:: spreadsheet, simple
>is usually good enough for real-world cases. In fact, that GNU Emacs
>Lisp-using developer I mentioned earlier did a very clever C++-based
>implementation of a matrix of cells (Improv worksheets can have up to
>twelve dimensions) that handled sparseness quite nicely, thank you.
Lisp certainly can represent sparse matrixes.
#(ds,5;8,(#(cell))
#(ds,cell address,5;8)
provides a perfectly adequete model. A standard matrix operation
will call addresses which exist. Those which are null (there
may be no definition for 6;8) can be treated as zero.
<<two-dimensional>> the table structure of the spreadseet is
one of its strengths. This is why it is important to map
into a numeric cell system. The table structure was also
liked by William James, the Venetians (double entry bookkeeping)
and Codd (relational algebra).
However a symbolic system allows modular construction. Some
eighties studies of spreadsheets found 70% contained logical
errors. Since it takes more time to text such a system for
correctness than to rewrite according to sound principles
these spreadsheets add up many millions of wasted white
collar (typically management) hours. Fortune and a number
of other sources have commented that "white collar productivity
remained flat in the eighties. This dispite nearly one
trillion in "knowlege equipment" such as FAX and PCs. We
know of many cases where such tools greatly increase productivity.
However there are other cases where they became time wasters.
A spreadsheet is a computer program. Early spreadsheet designs
made modular construction difficult (for example a set of cells
should have the capacity to be linked into several grids)
and provided users with a limited set of logics. In the early
years many of these individuals were fooled by hype which stated
the spreadsheet could easily solve basic accounting problems.
The fact the spreadsheets have evolved into more advanced system does
not change the fact that they could have acquired certain capacities
at the beginning. Many early spreadsheet programs were so rudimentary
that they didn't even allow easy writing of cells back and forth
between disk.
-ac-
In article <····················@192.0.2.1>, ···@world.std.com (Robert P.
Krajewski) wrote:
> [Most groups removed, comp.apps.spreadsheets added.]
>
> ········@crl.com (Andrea Chen) wrote:
> >······@netcom.com (Henry Baker) writes:
> >
> >>In article <··········@crl4.crl.com>, ········@crl.com (Andrea Chen) wrote:
> >
> >>> A historical example is the spreadsheet
> >>> (a product which helped launch the PC revolution). Two features
> >>> which distinguished it were its matrix frontend and "automatic
> >>> recalculation" in the backend. This second feature is natural to
> >>> Lisp dialects which could have served as an engine. They would
> >>> also have provided call by name (not just cell number) and
> >>> "multidimensional" structures. It took spreadsheet engines over
> >>> ten years to evolve these features on their own.
> Improv did advance the model of a spreadsheet, but the real
> leap that nobody's really made yet is to allow arbitrary datatypes
> to participate in what a spreadsheet is good at -- taking a set
> of rules and values, and keeping them consistent.
If you haven't seen the 'spreadsheet' that Xerox Info. Sys. did in
Smalltalk for the CIA in the early 1980's, you're missing something.
It had arbitrary datatypes in its cells, including pictures, etc., and
may have even had (recursive!) little spreadsheets in some of the cells.
I seem to recall it being called "The Analyst", or something nebbish like
that.
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
In article <····················@192.0.2.1>, ···@world.std.com (Robert P. Krajewski) writes:
|> [Most groups removed, comp.apps.spreadsheets added.]
|>
|> ········@crl.com (Andrea Chen) wrote:
|> >······@netcom.com (Henry Baker) writes:
|> >
|> >>In article <··········@crl4.crl.com>, ········@crl.com (Andrea Chen) wrote:
|> >
|> >>> A historical example is the spreadsheet
|> >>> (a product which helped launch the PC revolution). Two features
|> >>> which distinguished it were its matrix frontend and "automatic
|> >>> recalculation" in the backend. This second feature is natural to
|> >>> Lisp dialects which could have served as an engine. They would
|> >>> also have provided call by name (not just cell number) and
|> >>> "multidimensional" structures. It took spreadsheet engines over
|> >>> ten years to evolve these features on their own.
|>
|> As somebody who has done both Lisp language implementation (Lisp Machine
|> Lisp, Golden Common Lisp) and spreadsheet implementation (Lotus Improv),
|> I do not quite follow the implication here, which seems to be that Lisp
|> has an evaluation model which eases the implementation of a spreadsheet.
|> Spreadsheet recalculation can be looked as a propagation of changes across
|> a graph (possibly cyclic), something for a truth maintenance system to
|> handle in a general way, or an interesting constraint propagation problem,
|> and those are the kinds of computing applications and strategies that have
|> been explored quite fruitfully in Lisp (for good reason). But Lisp itself
|> doesn't really work like spreadsheet. Setting a Lisp variable doesn't make
|> things happen the way that editing a spreadsheet cell makes things happen.
Right, an application program still must be written.
While Common Lisp provides a lot of functionality,
it isn't necessarily what an application needs or is optimized in
exactly the right way for an application. You don't have to use the libraries
in Common Lisp to get it's other features.
In the spreadsheet case, I would think at least RATIOs
(CommonLisp represents 1/3 as "1" over "3", and thus represents "one third"
exactly rather than approximate it with floating point),
and perhaps even BIGNUMS would be useful (infinite precision integers)
to give business people more confidence that the answers they get
are correct. Garbage collection would seem to be important too.
> Improv did advance the model of a spreadsheet, but the real
> leap that nobody's really made yet is to allow arbitrary datatypes
> to participate in what a spreadsheet is good at -- taking a set
> of rules and values, and keeping them consistent.
I thought Texas Instruments used something like a "super spreadsheet" idea
for some application that worked like this, allowing complex objects
in the "cells". It was implemented in Common Lisp.
This kind of thing would definitely need run-time data typing wouldn't it?
-Kelly Murray ···@franz.com Franz Inc. http://www.franz.com
From: Robert P. Krajewski
Subject: Re: Spreadsheets and Lisp {was: Letter From Ted Nelson}
Date:
Message-ID: <rpk-1306952329310001@192.0.2.1>
In article <··········@no-names.nerdc.ufl.edu>, ···@prl.ufl.edu (Kelly
Murray) wrote:
>In the spreadsheet case, I would think at least RATIOs
>(CommonLisp represents 1/3 as "1" over "3", and thus represents "one third"
>exactly rather than approximate it with floating point),
>and perhaps even BIGNUMS would be useful (infinite precision integers)
>to give business people more confidence that the answers they get
>are correct. Garbage collection would seem to be important too.
True. Although for "normal" (commercial, mainstream, datatype-poor --
satisified ?) spreadsheets, GC isn't a big deal because it's hard to make
values refer to other values. Strings are pretty much the only example
where dynamic allocation comes into play, once the representation of the
matrix itself has been implemented.
With the recalc strategies I've seen, there are pointers between cells.
But the link slots are always part of the formula cell, not something that
goes away under certain conditions.
>I thought Texas Instruments used something like a "super spreadsheet" idea
>for some application that worked like this, allowing complex objects
>in the "cells". It was implemented in Common Lisp.
When I was working at LMI, I think I saw this. There were some guys from
TI working on something called "Hypercalc" (?), and they may have been
spun off from the company (which, of course, was selling Explorers at the
time).
>This kind of thing would definitely need run-time data typing wouldn't it?
Oh yes. For example, how about about a cell pointer representation where,
if the lower two bits were non-zero, it was really an immediate 30-bit
number ? Sound familiar ? One of the cool things about doing Improv was
getting to implement little pieces of a dynamic interpreter with run-time
type checking...
From: Patrick Logan
Subject: Re: Spreadsheets and Lisp {was: Letter From Ted Nelson}
Date:
Message-ID: <3rkk6i$q80@ornews.intel.com>
Robert P. Krajewski (···@world.std.com) wrote:
: Improv did advance the model of a spreadsheet, but the real
: leap that nobody's really made yet is to allow arbitrary datatypes
: to participate in what a spreadsheet is good at -- taking a set
: of rules and values, and keeping them consistent.
Xerox has (and I believe still sells) a spreadsheet written and extended
in Smalltalk.
Someone at Tektronix (I think) published in one of the first OOPSLAAs a
spreadsheet in Smalltalk showing the advantage of the recalc model with
more complex kinds of objects. One example I remember is a bitmap in
one cell. Other cells have formulas that are bitmap transformations,
each transforming and displaying the bitmap differently.
--
···············@ccm.jf.intel.com
Intel/Personal Conferencing
"Form follows function." -Le Corbusier