> > IMO the way to write a program is to design an abstract data type
> > then to use it. Only the person hand-coding the implementation of
> > that ADT need worry about low-level details such as cons cells.
> From: Xah Lee <x...@[EMAIL PROTECTED]
>
> Exactly. The problem with lisp's cons business, is that it
> surfaced to the language level in a way that a programer cannot
> ignore it.
So it's accessible to any random programmer, rather than being
accessible only to the wizards deep inside the vendor. Is that a
good or a bad thing? What are the alternatives to the Lisp way,
assuming you're going to have a linked-list data type, with methods
or functions that do ordinary things with them such as traversing
and mapping and reading and printing, in the first place.
First, why would you *want* a linked-list data type?
-1- So that you can use it as a stack, in o(1) time to push or pop an
item, without requiring allocation of a block of contiguous
memory with fixed size (or royal pain to re-size if the stack
gets too large).
-2- So that tails can be shared, to conserve memory and reduce CPU
time when copying a list with only a small change at the start,
while sharing side-effects (if any) on all the shared part.
(Special case: If the list is readonly after construction,
i.e. no side effects whatsoever on existing list elements.)
-3- So that you can read a large list into memory without knowing at
the outset how large it may be and without needing to pre-allocate
how large you guess it may be and re-copy the entire old allocation
into a new larger allocation if it turns out larger than guessed.
Now purposes -1-,-3- can be satisfied by an OO-style object with
limited actions allowed: make, push, pop, isEmpty, peekTop.
Reverse and nreverse can be included if you ever need them.
(READ is higher level, calling make once, then calling push many times,
then calling reverse or nreverse once.)
Now for READ of multi-level lists, you need to decide whether there
will be a single toplevel Object, with all ordinary lisp CONS-cell
structure under it, so that NTH will need to make a new Object
whenever the element is itself a linked list, or READ will create a
new Object immediately for every sub-list at every level, so then
NTH doesn't need to do anything special. Do you have a preference?
Head and tail pointers can be kept in the Object if you want,
whereupon you can allow pushEnd also (but not popEnd).
(Then READ can call pushEnd instead of push, and doesn't need reverse
or nreverse at very end. But then you are forced to build a whole
new Object at each level of list structure, because READ is a
high-level program that can't know about the internals of the
linked-list class, right?)
But then it's impossible to safely share tails between two
different linked-list Objects.
Furthermore, the Object can keep track of the length dynamically,
giving length in time o(1) instead of o(n). So if that's all you
want, then I suggest you have somebody implement a CLOS-style
object like that and then you never have to mess with car/cdr/cons
ever again. NTH, and SETF of NTH, can be provided in o(n) time
also. NTHCDR can be provided in o(n) time plus the overhead of
making a whole new object, and you have to decide whether the
implementation shares structure or copies all tails entirely. SETF
of NTHCDR can be provided too if you want, time o(n) but underlying
car/cdr/rplacd hidden from user, except then you lose the ability
to keep track of length dynamically and thereby deliver it in o(1)
time.
For all that plus having NTH and related methods available in
o(log(n)) time, but at the cost of push and pop o(log(n)) instead
of o(1) time, keep same API but switch to some kind of binary tree
internally. But that's not what you really want!!! The whole point
of using linked lists is that push and pop are o(1) time (and READ
doesn't have to know the length of input in advance). So back to
linked lists as the underlying implementation ...
But if you really need -2- done extensively, I see no really good
idea for implementation except to have linked-list cells directly
visible, i.e. car/cdr/cons. You *could* use the OO implementation
where it builds a whole new Object every time you do anything that
gives you a new "starting point" into the linked list, i.e.
whenever you do NTHCDR (probably renamed NTHTAIL), while still
sharing the underlying structure, but if you are doing a *lot* of
such operations, sharing tails among a very large number of
different linked-list Objects, that's a lot of overhead just to
hide the underlying CONS cells from the programmer. Is that what
you really want?
My thought here is that if the application programmer really wants
the linked-list type of data, then he/she needs to understand that
some sort of pairs (cells with down and right pointers) exists, and
would be frustrated at not being able to get at them directly.
Does any intelligent application programmer *really* want an API
that secretly uses linked-list representation without revealing
that fact, where the application programmer must read the timing
specs (i.e. o(1) for push/pop, o(n) for NTH, etc.) for the API and
wonder why it doesn't just come out and say it's a linked-list
representation, bringing us back to the frustration of the previous
paragraph?
> a lisp programer, can not practically code in lisp by using
> higher level list abstractions and functions without
> understanding the cons business.
Why would any application programmer, who has deliberately chosen
to use a linked-list ADT for purpose of constant-time push&pop and
the other advantages I described above, want to *not* understand
that a linked-list has cells with links pointing down to elements
and across to other linked-list cells??? What's the advantage of
not understanding the basic idea of the underlying representation
of the ADT that you have chosen to use??
> Because, in practice, the using cons is common.
If you're using linked lists to emulate stacks, then CONS is
actually non-destructive PUSH. Why wouldn't an application
programmer using lists to emulate stacks, and wi****ng to keep a
backup of the old value in case a rollback is needed, want to know
how to do a PUSH while *not* destroying the old value? It seems to me
that it'd be harder to understand that you can SETQ the old value
to a new value then PUSH one of the two variables and the *other*
variable won't be affected, because in OO programming if you assign
the same object to two variables and modify the object then *both*
variables are pointing at the modified object. It seems to me that
it makes more sense to directly offer CONS (which can be renamed
PUSH-NONDESTRUCTIVE if you want).
If you're building binary trees, then CONS is a way to build a new
tree out of two old trees, and CAR/CDR are ways to recover one or
the other of the original lists. Why wouldn't a person building
trees out of parts, and decomposing them back to parts, want to
know how to combine two trees into a larger tree and how to recover
the two sub-trees later??? (Of course you'd rename all three
functions, for example MAKE-TREE-FROM-PARTS LEFT-SUBTREE and
RIGHT-SUBTREE.)
For virtually every other application of linked lists, you do *not*
need car/cdr/cons directly at all. You use LIST to directly build
lists with a fixed set of parts. You use the mapping functions to
transform an old list to a new list elementwise. You use NTH to
select single elements by index, and SETF of NTH to change such an
element. You use SUBSEQ to extract ranges of elements from an old
list. You use APPEND to combine two lists into a list of all the
elements from both in the obvious way. You use READ and
PRINT/FORMAT to convert between internal lists and external print
representation, etc. None of those require the application
programmer to directly deal with cons/car/cdr operations. All you
need to understand is how some operations take longer than others
because they require copying of structure, but you need to know
that anyway even if you hide all the implementation details within
an ADT.
> You will encounter its use in just about every lisp program.
No. Most commonly you PUSH and POP without requiring a backup kept
around, or you don't do list-implementing-stack or
cons-implementing-tree at all in your application. You define
higher-level ADTs of lists-implementing-structures via NTH and SETF
of NTH, not by direct CAR/CDR.
> And, due to the cons business at the language level, there is the
> problem of =E2=80=9Cproper list=E2=80=9D and =E2=80=9Cimproper
> list=E2=80=9D. So, you can't pretend that cons doesn't exist and
> use only high-level list functions. They won't work.
You aren't *required* to use any improper lists in your
application, so you don't *need* to have this problem around in the
first place.
> > Look up the fu[n]ction NTH,
> > which indexes down a list by a given number.
> > Then imagine how trivial it is to write a function that uses a list
> > of successive indexes to specify the element number at successive
> > levels within a list, calling NTH at each level.
> The issue here is not whether it is easy to code it.
Then what *is* the issue? If you want a trivial extra layer of
software, and it's very very easy to implement it, and there's no
performance penalty compared to the wizards implementing it, then
why make such a fuss that somebody else didn't already write it for
you?
> First of all, as i gave the reason above, the cons business in the
> language stops any possibility of a uniform interface of list
> manipulating functions to the underlying cons.
That comment makes no sense to me. I gave above a sketch of a
uniform interface for using a linked-list as a stack, hiding the
implementation within a CLOS class if you want. The uniform
interface for mapping and reading/printing and
appending/subsequencing and for choosing/modifying element by index
already exist in CL, and you could embed that in a CLOS layer too
if you really wanted to hide the implementation. What more could
you want?
> Secondly, there is a big practical benefit of having functions
> built-in, even if trivial to code.
I agree. But IMO CL already has a very large set of useful
functions, both the kinds of stuff that wizards need to implement
because it's too hard or inefficient for the appliation programmer
to try to do it, and stuff that J. Random application programmer
could have done him/herself but having it built-in makes it more
convenient. But there has to be a limit of what's already built-in
the core language. Maybe there are five or ten additional functions
that would be really nice to also include, such as your proposed
(defun map-indexes-down-list-levels (listOfIndexes multiLevelList) ...)
and the HDDL mechanism for running ASSOC down multiple levels of
tagged lists that Tryg Ager implemented in PSL about twenty years
ago, etc. So maybe you can write a nice add-on package to include
these functions you feel just about everyone would want, and market
it? This is in addition to the special-purpose add-on packages
such as sup****t for regular expressions, XML, HTTP/HTML, etc.
But if you are the only person in the world who wants your proposed
function, then why should somebody else have implemented it and
fixed it into the core CL standard???
> Also, the availability large number of built-in functions has
> tremendous impact on the ease of coding with the language.
Only if it's easy to find the function you want when you have a
need for its functionality. See for example my attempt to
re-organize the commonly useful functions to process the
commonly-available data types across six common programming
languages (Common Lisp, Java, C, C++, Perl, and PHP) that are easy
to use with CGI.
<http://www.rawbw.com/~rem/HelloPlus/CookBook/Matrix.html>
> When you don't have the set A, it may be that it's trivial to
> create A by coding it yourself. But if you have A built in, it's
> trivial to build set B. But without A built in, B is now a bit
> difficult. The gist is that, you can't built a 2nd story without a
> 1st story.
That's why various add-on packages have become popular. But the key
is to have an information retrieval system that lets you find the
appropriate 1st-story package that you'll need for the de novo
2nd-story you intend to craft. Would be willing to survey all the
existing CL add-on packages that are available on the net, discard
the obscure very-specific or badly-designed ones, and nicely index
the non-obscure well-designed ones that ought to be available to
application programmers?
> Mathematica comes with a thousand (or few thousands) of built in
> functions (and high-quality ones, not just web collection of Joes
> like Perl's CPAN). Similarly, is Java. And to a lesser degree,
> Python, PHP. These large number of built-in functions contribute to
> their success.
It's my understanding that CL has a comparable number of functions,
of overall quality comparable to Java's standard release of J2SE.
Some Java stuff is missing in CL, and some CL stuff is missing in
Java, but I don't think CL is overall deficient compared to Java.
> ... for a language to be popular and practically useful, a huge
> number of built-in functionality is one of the main contribution[s].
Which both Common Lisp and Java have, so what's your complaint?
> Language's features typically talked about by computer scientist morons
Oh lookey, you're being all derogatory. (I snipped when you
complained that I said something you interpreted as derogatory, but
this *is* derogatory/insulting, no question about it.)
> such as all the details and variations of types,
All the essential types, except one, are in Common Lisp:
- integers of size limited only by available memory, present in
Java only if you switch to a special object type that doesn't
work well with the rest of the language, not present in any
other core language that I know of (for example PHP doesn't have
integers at all, it uses floats for everything)
- rationals with size of numerator and denominator limited only by
available memory, not present in any other general purpose
language that I know of, present in MacSyma (which is based on
MacLisp), probably present in other special-purpose math
packages I've never had access to
- floating-point approximations to real numbers (present everywhere)
- complex numbers
- interval arithmetic not present in *any* mainstream language, not
even Common LIsp
- general-purpose pairs, not present in Java at all unless you
emulate pairs by two-element arrays of element-type java.lang.Object
and always use class wrappers for numbers whenever they might be
included in pairs
- sup****t for linked lists using those general-purpose pairs, no
sup****t whatsoever for such in Java
- **symbols**, no sup****t whatsoever in any other language, the
closest you can get in Java is barebones hash tables, then you
have to re-invent the wheel if you want an object in the hash
table to have a print name and a value cell and a function cell
and a property list and a link back to the hash table it's
cataloged in
- streams, limited sup****t in Common Lisp for streams connected to
files in the system's filesystem, and to stdio, and to strings
acting as if files; this is where Java ****nes, where every
stream is a full Object, and anyone can build a stream connected
to anything and the wrap the usual BufferedReader etc. around it
for normal I/O. MacLisp had filearrays which allowed application
programmers to define new types of streams that worked just like
regular ones, but Common Lisp dropped that as not anything the
general community would want, which I still consider to have
been a serious mistake
- closures fully wonderful, merely hacked in Java
- user-defined classes in CLOS better in Common Lisp than in Java
because they are runtime-polymorphic on *every* parameter instead
of runtime-polymorphic on just one special pseudo-parameter and
only compiletime-polymorphic on all the regular parameters
It seems to me that all other data types are application specific.
If you do network stuff, you might want XML parser, or HTML parser,
or HTTP client and server, or RPC/RMI client and server, etc.,
depending on what specific kind of network stuff you wish to do.
If you write GUI applications, then of course you need the usual
assortment of windows/panes/panels and controls (close/resize/minimize,
textfield, textarea, checkbox, radiobutton, regular button, etc.).
If you want to process text in multiple non-USASCII languages, or
in any single language that has more than 256 characters, you
probably need sup****t for UniCode, including input/output of UTF-8.
(I'll have to say lack of built-in sup****t for UniCode is, for
non-American users, the number one deficiency in Common Lisp.
The major vendors have filled this gap, but not in a standard
****table way.)
> inferences
Please define what you mean there. It sounds like a special
application area to me, not anything the average application
programer will crave for if it's missing.
> higher-level/first-class function
This is what Common Lisp has, right? Or do you mean something more?
> curry
(defun foo (x y z) ...)
(defun curry-foo-x (x)
(function (lambda (y z) (foo x y z))))
(defun curry-foo-y (y)
(function (lambda (x z) (foo x y z))))
(defun curry-foo-z (z)
(function (lambda (x y) (foo x y z))))
;is that right?
You can pick whichever parameter you want to curry.
You aren't limited to currying only the first or last depending on
which was built into the language.
You can even write generic currying meta-functions, for example:
(defun curry-3-1 (f123 p1)
(function (lambda (p2 p3) (funcall f123 p1 p2 p3))))
You can even write a totally generic macro for generating currying
functions on the fly (just a sketch here):
(defmacro curry-k-of-n (f n k)
"f is a function object
0 <= k < n = number of parameters of f
curry the kth parameter of f, leaving all the rest as parameters of
result"
...)
;(curry-k-of-n #'foo 3 0) ==> the curry-foo-x from above
So what else do you want??
Should curry-k-of-n be built into the delivered system, including
correct handling of optional/keyword parameters off the end after
the first n parameters?
> closure, multi-inheritance
In CL already, as I said above.
> dispatch
What do you mean?
CASE/SELECT statements/expressions?
Runtime polymorphism of objects?
Handling interrupts/events (both device-generated and software-generated)?
Please specify which you want.
> lazy evaluation
This has not yet been reduced to standard practice, to where there
is any single specification that we can all agree upon. For
example, in recent years I have been advocating a system for
drawing a dataflow diagram for interval arithmetic where lazy
evaluation is used to compute approximate intervals narrower and
narrower as needed to produce a meaningful decision/output. The
general idea is to use a mathematical identity to yield a directed
computation which forms a stable feedback loop. For example, given
N known non-negative, you compute the square root of N via Newton's
method expressed as a feedback loop. Whenever you need to narrow
the interval, you track the dataflow backwards until you reach a
place where you can get more accuracy, then you compute forwards
again to see how narrow your output interval is now.
<http://www.rawbw.com/~rem/IntAri/>
That's doing the dataflow manually to illustrate how the interval
arithmetic itself works. Nobody expressed any interest in this
work, so there's no funding, so I haven't developed the idea
further except in my mind. Maybe you'd like to show some interest?
> pattern matching
This is a totally open-ended subject. Until you specify what kinds
of patterns you want to match (patterns of characters in a string,
patterns of trends in an economy, patterns of facial
characteristics, patterns of debris in high-energy atomic
collisions, patterns of sub-graphs in large mathematical graphs,
patterns in signals received from deep space which might possibly
be from ETI, patterns in whale "songs" which might represent a
meaningful grammar and/or meaningful discourse about ocean
conditions, patterns in brain activity which might be useful for
detecting honesty vs. deceit, etc. etc. etc.), you haven't a chance
of even getting started at the research project much less a
standard algorithm/heuristic.
> tail recursion
This is not as useful as it's hyped up to be. Sure if you write a
factorial recursively to emulate iteration, a compiler can convert
it back to the equivalent iterative algorithm to avoid stack
overflow. Whooptie-doo. True recursion isn't tail recursion in the
first place so you don't need this case handled specially. For
example, the right way to compute factorial recursively is:
(defun prod (m n)
(if (< (+ m 1) n)
(let ((mid (floor (+ m n) 2)))
(* (prod m mid) (prod mid n)))
m))
(defun fact (n) (prod 1 (+ 1 n)))
The whole point of recursion is divide-and-conquer, epecially if
you have multiple processors which can run in parallel on sub-tasks.
Always spawing one sub-task to do a trivial case and the other
sub-task to do all the work except that one trivial case, whereby
you actually compute the trivial case directly and tail-recurse on
the all-the-rest, is outright stupid.
> closure
Didn't we already cover this? Lisp has it.
> call-with-continuation
I'm not familiar with that jargon, but it sounds like something to
do with co-routines. I'll do a Google search ...
<http://jist.ece.cornell.edu/jist-user/node12.html>
... For example, an entity that models a file-transfer is
more readily encoded as a process than as a sequence of events.
Specifically, one would rather use a tight loop around a blocking send
routine than dispatch send events to some trans****t entity ...
Yeah, co-routines. Two processes each think they are calling the other,
and they take turns waiting for the co-routine linkage to return.
<http://www.pluralsight.com/blogs/dbox/archive/2005/04/27/7780.aspx>
continuation passing style (CPS) ... is based on the
notion that instead of returning a value from a function, the value is
passed to the code that will continue the computation.
Is that anything like what you have in mind?
<http://www.ibm.com/developerworks/java/library/os-lightweight9/index.html>
In Ruby, you use callcc, which means call with continuation.
Call with continuation gives you a code block, and the
continuation (or a saved call stack, with instance variables),
which you assign to a variable. Think of a continuation as all
of the program that hasn't executed yet.
<same question>
By the way, I've come to the line of thinking that the "business
logic" (actually the business calculations mostly) should be
written as an explicit state-of-computation object together with
functions/methods which perform individual transformation steps of
the business algorithm. Once that'd done, it's relatively trivial
to write a toplevel wrapper that has one process call the other, or
vice versa, or have the two processes act as co-routines. Any time
you need to parse an input stream, you design the parser explicitly
as a state machine (using a parser-compiler to convert from BNF or
equivalent expression of the grammar to the state machine). So if
we want to standardize this methodology, we need to agree upon a
standard representation of the state machine which can then be
automatically processed by the main application-builder. Do you
know of any good results in this area?
> and many other jargons, really have _little_ significance to
> daily practice.
Is that meant to be derogatory towards the daily programmers who
don't know beans about powerful concepts that could be of great use
to them but which unfortunately aren't provided by their favorite
programming languages or aren't tutorialized well enough, or
derogatory towards the people who envision these wonderful ideas
which turn out to be useless in practice?? I seriously believe
dataflow feedback loops with interval arithmetic is the *right* way
to go with complicated real-metric numeric calcuiations. I am
totally sure that lexical closures are useful. (I use them "all the
time" when I program applications!!)
> Every studious moron with a computer science degree, can create a
> language (like that of Larry Wall, Guido van Rossum, and now Paul
> Graham). But to create a high-quality set of huge number of
> libraries (as in Java, Mathematica), is extremely difficult.
I really can't believe that Mathematica has a huge set of
general-purpose libraries, the way that Java and Common Lisp do.
I thought that Mathematica was a special purpose system for doing
mostly the same sorts of things that MacSyma used to do, only
better and more commercially, i.e. closed-form mathematical
expression manipulation such as calculus and infinite-series
summation, and graphing the results. Am I mistaken??
|
