the sort function in lisp (destructive)
Xah Lee
I started to learn elisp in 2005 casually. (am a daily emacs user
since 1997) To my surprise, for tasks of text processing (and sys
admin), elisp's power, ease, and convenience is almost a order above
Perl. This is particular painful to realize for me because even being
a Perl hater from the very beginning, fully aware of its rampant lies,
i was nevertheless strongly deceived by the wide-spread understanding
that Perl IS the most suitable language for text processing tasks.
(and conversely, due to emacs lisper's lack of emacs lisp advocacy,
partly due to the supression by Scheme lisp and Common Lisp factions,
emacs's power as a text-processing computer language system is
basically unknown to the programers at large (often, emacs lisp is
understood to programers who actually heard of lisp, as “just a
extension niche language” usually with demeaning connotations))
Besides industrial programing, my personal use of perl is primarily
text processing. So, i was quite pissed by the extent of damage perl's
lies caused to me on this regard. I'm currently, casually doing all my
text processing needs in emacs instead of Perl or Python. (e.g.
typically a function that process tens to tens of thousand files.)
Anyway, the main point for this post is something i realized in emacs
lisp that's rather bizarre. That is: its “sort” function destroys the
variable of list it is sorting!!!
Here's a example:
(setq mylist '("c" "d" "a"))
(sort mylist 'string< )
mylist ; ⇒ ("c" "d")
O my god???
This actually caused me few hours to debug. (among other reasons. e.g.
i'm still learning elisp system)
In high level languages, sort will either sort the variable in-place,
or return the sorted list. I have not come across any language that
actually destroy the variable in the process. I asked a bit, and it
seems Common Lisp's sort has the same behavior.
So, my question is: What could possibly be the use of this? When does
a programer EVER need to do simply just (sort mylist 'f) ?
Of course, lisp is old, with many quaint qualities (e.g. the cons
business; elisp's char being integers; elisp's dynamic scope; Common
Lisp's big baggage ...etc.), but what could have possibly made the
design of “sort” function the way it is?
Rainer Joswig
<25880ded-3e53-4baf...@21g2000hsj.googlegroups.com>,
Xah Lee <x...@xahlee.org> wrote:
> I'm a perl expert, programing it in industry daily from 1998 to 2002.
> I started to learn elisp in 2005 casually. (am a daily emacs user
> since 1997) To my surprise, for tasks of text processing (and sys
> admin), elisp's power, ease, and convenience is almost a order above
> Perl. This is particular painful to realize for me because even being
> a Perl hater from the very beginning, fully aware of its rampant lies,
> i was nevertheless strongly deceived by the wide-spread understanding
> that Perl IS the most suitable language for text processing tasks.
> (and conversely, due to emacs lisper's lack of emacs lisp advocacy,
> partly due to the supression by Scheme lisp and Common Lisp factions,
> emacs's power as a text-processing computer language system is
> basically unknown to the programers at large (often, emacs lisp is
> understood to programers who actually heard of lisp, as “just a
> extension niche language” usually with demeaning connotations))
>
> Besides industrial programing, my personal use of perl is primarily
> text processing. So, i was quite pissed by the extent of damage perl's
> lies caused to me on this regard. I'm currently, casually doing all my
> text processing needs in emacs instead of Perl or Python. (e.g.
> typically a function that process tens to tens of thousand files.)
>
> Anyway, the main point for this post is something i realized in emacs
> lisp that's rather bizarre. That is: its “sort” function destroys the
> variable of list it is sorting!!!
This must be a FAQ.
There is a misconception. Sort does not operate on variables
or touches variables. It creates a sorted list of another list.
If you see (sort mylist pred) , SORT can't change the variable mylist,
it never sees it. The evaluation evals mylist and pred and calls
SORT with the results.
>
> Here's a example:
>
> (setq mylist '("c" "d" "a"))
> (sort mylist 'string< )
> mylist ; ⇒ ("c" "d")
>
> O my god???
(in Common Lisp it is not allowed to destructively modify literal code.
SORT is a destructive function. So you need to cons a fresh list.)
If you want to sort a list, you have to use the result of SORT:
Wrong:
(let ((mylist (list "c" "d" "a")))
(sort mylist #'string<)
mylist)
Correct:
(let ((mylist (list "c" "d" "a")))
(setq mylist (sort mylist #'string<))
mylist)
Remember, Lisp has a Functional core. In this case sort returns
the sorted list. You have to use the result.
If you don't want the original list to be destructively modified,
you need to write:
(sort (copy-list mylist) #'string<)
> This actually caused me few hours to debug. (among other reasons. e.g.
> i'm still learning elisp system)
>
> In high level languages, sort will either sort the variable in-place,
> or return the sorted list. I have not come across any language that
> actually destroy the variable in the process. I asked a bit, and it
> seems Common Lisp's sort has the same behavior.
Lisp destructively modifies the list (if necessary), this has nothing
to do with the original variable. It just still points to the original
CONS. Make sure you understand evaluation and how arguments
are passed. (sort mylist pred) does not mean that the variable
mylist will be sorted. It means the the result of evaluating mylist
will be sorted and a sorted list will be returned as a result.
The returned list may share cons cells with the original unsorted list.
SORT does not and cannot change the variable MYLIST.
>
> So, my question is: What could possibly be the use of this? When does
> a programer EVER need to do simply just (sort mylist 'f) ?
>
> Of course, lisp is old, with many quaint qualities (e.g. the cons
> business; elisp's char being integers; elisp's dynamic scope; Common
> Lisp's big baggage ...etc.), but what could have possibly made the
> design of “sort” function the way it is?
>
> Xah
> x...@xahlee.org
John Thingstad
> So, my question is: What could possibly be the use of this? When does
> a programer EVER need to do simply just (sort mylist 'f) ?
>
> Of course, lisp is old, with many quaint qualities (e.g. the cons
> business; elisp's char being integers; elisp's dynamic scope; Common
> Lisp's big baggage ...etc.), but what could have possibly made the
> design of “sort” function the way it is?
>
> Xah
> x...@xahlee.org
> ∑ http://xahlee.org/
>
From the documentation:
This function sorts LIST stably, though destructively, and returns
the sorted list. It compares elements using PREDICATE. A stable
sort is one in which elements with equal sort keys maintain their
relative order before and after the sort. Stability is important
when successive sorts are used to order elements according to
different criteria. This function sorts LIST stably, though
destructively, and returns
the sorted list. It compares elements using PREDICATE. A stable
sort is one in which elements with equal sort keys maintain their
relative order before and after the sort. Stability is important
when successive sorts are used to order elements according to
different criteria.
The destructive aspect of `sort' is that it rearranges the cons
cells forming LIST by changing CDRs. A nondestructive sort
function would create new cons cells to store the elements in their
sorted order. If you wish to make a sorted copy without
destroying the original, copy it first with `copy-sequence' and
then sort.
The reason is that it is more efficient to sort a list by rearranging the
pointers than to build a whole new list. But it would be inefficient to
update variable to point to the start of the list each time. In practise
this is rarely a problem.
(This is written in Common Lisp not elisp)
(defun scramble (sequence)
"Return the sequence with elements in random order.
example:
(scramble '(0 1 2 3 4 5 6 7 8 9))
=>(3 2 0 5 6 4 9 1 7 8)"
(let ((length (length sequence)))
(dotimes (i (1- length) sequence)
(rotatef
(elt sequence i)
(elt sequence (random (+ i (- length i))))))))
(defparameter *list" (scramble (loop for i from 1 below 100 collect i)))
> *list*
(38 59 78 ... 2) ; 100 elements
> (setf *list* (sort *list* #'<))
(0 1 2 ... 99)
> *list*
(0 1 2 ... 99)
--------------
John Thingstad
Nicolas Neuss
> Anyway, the main point for this post is something i realized in emacs
> lisp that's rather bizarre. That is: its “sort” function destroys the
> variable of list it is sorting!!!
I admit that I also would prefer if SORT wouldn't work destructively (at
least by default, it could take some keyword argument :destructive-p to
switch it to the destructive behaviour if performance would require it).
Probably the most practical remedy is to define some function SAFE-SORT in
your utility package and use that instead of SORT most of the time.
Nicolas
David Kastrup
> Xah Lee <x...@xahlee.org> writes:
>
>> Anyway, the main point for this post is something i realized in emacs
>> lisp that's rather bizarre. That is: its “sort” function destroys the
>> variable of list it is sorting!!!
>
> I admit that I also would prefer if SORT wouldn't work destructively (at
> least by default, it could take some keyword argument :destructive-p to
> switch it to the destructive behaviour if performance would require
> it).
Where is the point? Sorting necessarily requires changing the involved
cons-cells. If you don't want them changed, you need to make a copy of
the list structure, obviously.
--
David Kastrup, Kriemhildstr. 15, 44793 Bochum
Alex Mizrahi
XL> variable of list it is sorting!!!
if you do not understand the difference between variable and data it refers
to, you probably understand nothing about Lisp.
variable is just a reference or a pointer to data.
no function in CL can affect _variable_ that is passed as parameter to the
function. but it can affect data.
XL> This actually caused me few hours to debug.
it seems you know the word "destructive", don't you?
if you use function that is documented to be destructive, but you do care
about your data, you should copy your data.
that seems to be easy and intuitive rule.
XL> Lisp's big baggage ...etc.), but what could have possibly made the
XL> design of “sort” function the way it is?
i guess it's destructive by default because often you do sort a freshly
created list, and rarely you do need both sorted and non-sorted list.
in case somebody needs it, it's fairly easy to do so calling copy-list
function or something like this.
there's no sortf macro (only macro can interact with parameters passed to
it) because it's not widely used pattern -- i think typically people just
return what sort returns.
it's fairly easy to make sortf macro yourself, something like:
(defmacro sortf (seq-place predicate) `(setf ,seq-place (sort ,seq-place
,predicate)))
and you'll have what you call "in-place sort".
i agree that it would be more newbie-friendly to have either non-destructive
sort by default or sortf,
but Common Lisp is not a newbie-oriented language, and more experienced Lisp
programmers use SORT without problems (or they can easily define function or
macro that fits them better).
if newbies will spend some hours debugging weird SORT behaviour it would be
better for them -- that way they'll understand understand faster what does
word "destructive" mean and how variables do work.
Joost Kremers
> I admit that I also would prefer if SORT wouldn't work destructively (at
> least by default, it could take some keyword argument :destructive-p to
> switch it to the destructive behaviour if performance would require it).
> Probably the most practical remedy is to define some function SAFE-SORT in
> your utility package and use that instead of SORT most of the time.
i'm curious: in what kind of situations do you wish sort were
non-destructive? usually when i use sort, i don't need the unsorted list
afterwards, so i don't care if it's modified. if you do need the unsorted
list after sorting, you can always use copy-list before you call sort.
--
Joost Kremers joostk...@yahoo.com
Selbst in die Unterwelt dringt durch Spalten Licht
EN:SiS(9)
Rainer Joswig
"Alex Mizrahi" <udod...@users.sourceforge.net> wrote:
> i agree that it would be more newbie-friendly to have either non-destructive
> sort by default or sortf,
> but Common Lisp is not a newbie-oriented language, and more experienced Lisp
> programmers use SORT without problems (or they can easily define function or
> macro that fits them better).
Another alternative would be a SORT that does not reorder the CONS cells,
but the CARs of the CONS cells. SORT the list into another
data structure and then set the list's CARs from there.
Though even that would not be that useful.
(defun my-sort (list predicate)
(map-into list
#'identity
(sort (copy-list list) predicate)))
(let ((l1 (list 'd 'e 'a 'f 'x 'h)))
(let ((l2 (sort l1 #'string<)))
(values l1 l2)))
->
(D E F H X)
(A D E F H X)
(let ((l1 (list 'd 'e 'a 'f 'x 'h)))
(let ((l2 (my-sort l1 #'string<)))
(values l1 l2)))
->
(A D E F H X)
(A D E F H X)
>
> if newbies will spend some hours debugging weird SORT behaviour it would be
> better for them -- that way they'll understand understand faster what does
> word "destructive" mean and how variables do work.
John Thingstad
>
> Another alternative would be a SORT that does not reorder the CONS cells,
> but the CARs of the CONS cells. SORT the list into another
> data structure and then set the list's CARs from there.
> Though even that would not be that useful.
>
>
In fact looking at the source for Corman Lisp I discovered that it reads
the CAR into a vector, sorts that, and then puts the values back in the
CAR's in sorted order.
--------------
John Thingstad
Alex Mizrahi
RJ> cells, but the CARs of the CONS cells. SORT the list into another
RJ> data structure and then set the list's CARs from there.
and if implementation uses bubble-sort algorithm it doesn't even need any
additional storage!
but i think we can confuse Xah without introducing any significant
runtime/space overhead:
(defun pseudo-nice-sort (list pred)
(when list
(let ((beheaded-list (cons (first list) (rest list))))
(setf beheaded-list (sort beheaded-list pred))
(setf (car list) (car beheaded-list)
(cdr list) (cdr beheaded-list))
list)))
it will not "destroy variable" because it preserves the first CONS:
CL-USER> (let ((l1 (list 'd 'e 'a 'f 'x 'h)))
(let ((l2 (pseudo-nice-sort l1 #'string<)))
(values l1 l2)))
(A D E F H X)
(A D E F H X)
however it's still destructive, so in some cases it can bring more than a
few hours of happy debugging
Kent M Pitman
David Kastrup <d...@gnu.org> writes:
> Nicolas Neuss <last...@math.uni-karlsruhe.de> writes:
> [...]
> > I admit that I also would prefer if SORT wouldn't work destructively
> [...]
> Where is the point? Sorting necessarily requires changing the involved
> cons-cells.
Indeed. Just as addition should be destructive because it requires
changing the bits involved. :)
I don't think the workaround suggested by Nicolas Neuss is an
unreasonable one. Certainly it has a point since the function he
describes is both semantically distinct from the one CL provides, and
is something users frequently ask for.
I don't think the notion of an sort/nsort distinction would have been
so unreasonable in a design-from-scratch scenario, it just didn't
match the history of things at the time of the CL design, and that's
almost surely why it wasn't done... legacy code, which was a priority,
was already depending on the side-effect in the manner it was already
done. Tracking down the bugs that would have resulted from making
this change would have been tricky since type errors would have been
rare and bugs would have been somewhat elusive.
Kent M Pitman
> På Sun, 06 Jan 2008 17:38:04 +0100, skrev Rainer Joswig <jos...@lisp.de>:
>
> >
> > Another alternative would be a SORT that does not reorder
> > the CONS cells, ...
>
> In fact looking at the source for Corman Lisp I discovered that it
> reads the CAR into a vector, sorts that, and then puts the values
> back in the CAR's in sorted order.
This might have been done for other reasons than avoiding side-effect.
For example, to avoid having two different sort algorithms, or even
because it didn't occur to him how to write the algorithm without
doing indexed access.
Not that it relates directly to the issue of side-effect, but I always
liked this algorithm, probably because of its cute choice of variable
names, but also because it's so concise...
tim Josling
> Nicolas Neuss wrote:
>> I admit that I also would prefer if SORT wouldn't work destructively (at
>> least by default, it could take some keyword argument :destructive-p to
>> switch it to the destructive behaviour if performance would require it).
>> Probably the most practical remedy is to define some function SAFE-SORT in
>> your utility package and use that instead of SORT most of the time.
>
> i'm curious: in what kind of situations do you wish sort were
> non-destructive? usually when i use sort, i don't need the unsorted list
> afterwards, so i don't care if it's modified. if you do need the unsorted
> list after sorting, you can always use copy-list before you call sort.
>
For the same reasons I use non-destructive versions of other list
processing utilities. Specifically, to avoid nuking preexisting data
structures. For example, I have a list and sort several times according to
various criteria. This requires a non-destructive sort.
There is nothing wrong with having a destructive sort, it's just that
normally destructiveness is flagged in some way, by having "n" at the
start of the name or something. With SORT, there is no hint.
One day I'm going to build myself a set of macros that make these
irregularities in CL go away. For example, I will have SRT and SRT! for
non-destructive and destructive versions of SORT.
Or perhaps you could wrapper your code in a single macro "SAFE" that
checks all the functions you have used are nondestructive, unless they are
wrappered by some sort of declaration such as unsafe. Probably a bit
clumsy to use in practice.
e.g.
(SAFE (or (mapcar .... ... (unsafe (sort ...)))))
Tim Josling.
David Kastrup
> On Sun, 06 Jan 2008 15:36:30 +0000, Joost Kremers wrote:
>
>> Nicolas Neuss wrote:
>>> I admit that I also would prefer if SORT wouldn't work destructively (at
>>> least by default, it could take some keyword argument :destructive-p to
>>> switch it to the destructive behaviour if performance would require it).
>>> Probably the most practical remedy is to define some function SAFE-SORT in
>>> your utility package and use that instead of SORT most of the time.
>>
>> i'm curious: in what kind of situations do you wish sort were
>> non-destructive? usually when i use sort, i don't need the unsorted list
>> afterwards, so i don't care if it's modified. if you do need the unsorted
>> list after sorting, you can always use copy-list before you call sort.
>>
>
> For the same reasons I use non-destructive versions of other list
> processing utilities. Specifically, to avoid nuking preexisting data
> structures.
Uh, that's what copying is for. The whole point of sorting is to change
the conses, establishing a different order.
> For example, I have a list and sort several times according to various
> criteria. This requires a non-destructive sort.
Sorting _is_ a destructive operation (on all of the list conses) by
definition.
> There is nothing wrong with having a destructive sort, it's just that
> normally destructiveness is flagged in some way, by having "n" at the
> start of the name or something.
Like with delete, delq, setcdr?
tim Josling
> tim Josling <tejgcc...@westnet.com.au> writes:
>
>> For example, I have a list and sort several times according to various
>> criteria. This requires a non-destructive sort.
>
> Sorting _is_ a destructive operation (on all of the list conses) by
> definition.
>
I see sorting as a function that takes an unsorted list and returns a
sorted list.
The destructiveness in Lisp's sort is incidental.
>> There is nothing wrong with having a destructive sort, it's just that
>> normally destructiveness is flagged in some way, by having "n" at the
>> start of the name or something.
>
> Like with delete, delq, setcdr?
>
As I said, sort is not the only irregularity in Lisp by any means. The
last two are from emacs lisp, which is a dialect of its own, not from CL.
Tim Josling
Gene
> "John Thingstad" <jpth...@online.no> writes:
> > På Sun, 06 Jan 2008 17:38:04 +0100, skrev Rainer Joswig <jos...@lisp.de>:
>
> > > Another alternative would be a SORT that does not reorder
> > > the CONS cells, ...
>
> > In fact looking at the source for Corman Lisp I discovered that it
> > reads the CAR into a vector, sorts that, and then puts the values
> > back in the CAR's in sorted order.
>
> This might have been done for other reasons than avoiding side-effect.
> For example, to avoid having two different sort algorithms, or even
> because it didn't occur to him how to write the algorithm without
> doing indexed access.
>
paging behavior. If you sort a long, randomly ordered list by
changing cdr's, merely traversing the resulting list cells makes for a
terrible memory access pattern.
David Kastrup
> On Sun, 06 Jan 2008 21:34:01 +0100, David Kastrup wrote:
>
>> tim Josling <tejgcc...@westnet.com.au> writes:
>>
>>> For example, I have a list and sort several times according to various
>>> criteria. This requires a non-destructive sort.
>>
>> Sorting _is_ a destructive operation (on all of the list conses) by
>> definition.
>>
>
> I see sorting as a function that takes an unsorted list and returns a
> sorted list.
That's not how sorting items works in real life. The original order
gets lost.
> The destructiveness in Lisp's sort is incidental.
Huh? The list conses define the order of the list members. Sorting the
members changes their order.
In normal everyday language, sorting is a process that abolishes the
original order. The function would have to be called something like
"sorted" to imply that it returns a sorted list _without_ sorting the
original list.
Kent M Pitman
David Kastrup <d...@gnu.org> writes:
> tim Josling <tejgcc...@westnet.com.au> writes:
>
> > I see sorting as a function that takes an unsorted list and returns a
> > sorted list.
>
> That's not how sorting items works in real life. The original order
> gets lost.
Appending doesn't work that way either. If I tell you to append something
to the list on the refrigerator, very few people would make a new list and
replace the previously existing list with it, just to avoid modifying the
list they were throwing into the trash.
I certainly think it's worth noting that there are such issues as you're
doing. It's good design practice to be aware of people's real world
sensibilities. But I think it's also worth not taking this to an extreme.
There is a reason that we don't use webster.com in favor of the CL spec.
And even if we did, webster.com is filled with words that have many
senses. I think what people like Tim are saying in cases like this is
not that your sensibility is wrong, but that there are multiple
sensibilities possible.
Incidentally, if I tell you to find the list of things to buy at the
grocery store that I have pinned to the refrigerator and to sort it by
the aisle in the store that the items will appear, and then carry it
with you to the store buying things from it, and as you wander the
aisles to sort the list by cost, I'm not asking you to randomize the
order in which you visit the aisles. It's a bit of an odd request in
the first place, but I believe a human being would observe the
conflict and would make a copy. So human intuitions are not always
what you might infer from a simple example. I think, in fact, if we
surveyed the space of human use, you'd probably have to admit that
humans are quite savvy/clever about side-effect in a way that is not
as rote/dogmatic as you suggest.
Madhu
Wrote on Sun, 6 Jan 2008 13:20:31 -0800 (PST):
|> > In fact looking at the source for Corman Lisp I discovered that it
|> > reads the CAR into a vector, sorts that, and then puts the values
|> > back in the CAR's in sorted order.
|>
|> This might have been done for other reasons than avoiding side-effect.
|> For example, to avoid having two different sort algorithms, or even
|> because it didn't occur to him how to write the algorithm without
|> doing indexed access.
|>
| Another possible reason is to avoid a certain kind of degenerate cache/
| paging behavior. If you sort a long, randomly ordered list by
| changing cdr's, merely traversing the resulting list cells makes for a
| terrible memory access pattern.
I think there are two many `if's in reasoning about memory access
patterns. You will traverse the list to get it into the array in the
first place, and there may be repeated traversals immediately , on the
resulting list.
But I notice you have made this point in the past, when citing
your paper which exhibited a SHUFFLE algorithm which worked on cons
cells. I could not look it up, perhaps you could post a brief
description of how it worked here?
[As for SORT Robert Maas posted a small hack that would preserve the head
cons after calling the implementation's SORT in SORT-KEEPING-HEAD-CELL
in his post[1] <News:rem-2007...@yahoo.com>
Dated "11 Oct 2007 02:44:41 -0700"]
--
Madhu
[1] (rem-2007oct11-003 @ yahoo.com)
Raffael Cavallaro
> That's not how sorting items works in real life. The original order
> gets lost.
clearly you haven't drunk the functional kool-ade ;^)
Kent M Pitman
Perhaps it's a marketing error on the functional community's part;
I'm somehow imagining a mind-altering beverage that nevertheless
has no side-effects.
To paraphrase Oliver Wendell Holmes (with all due apology):
"A mind that once stretched by a new idea never regains its
original dimensions is obviously not functional."
David Kastrup
writes:
> On 2008-01-06 16:29:50 -0500, David Kastrup <d...@gnu.org> said:
Tell that to the cons cells.
John Thingstad
<pit...@nhplace.com>:
Well there is a quick-sort and a merge-sort and none of them are heavily
optimized. For quick-sort I would probably use a median of three to get
the start element and a insert sort for less than 10 element for stability
and efficiency reasons. This hasn't been done. This leads me to think that
it is done because it was the first thing he could think of. Remember
Rodger Corman has essentially written the entire compiler and library
alone so assumably he has a tight time budget.
--------------
John Thingstad
Raffael Cavallaro
> Perhaps it's a marketing error on the functional community's part;
Maybe it needs to be made explicit that using a functional style will
cause programs to not resemble the real world, in that the real world
is often all about the side effects.
> I'm somehow imagining a mind-altering beverage that nevertheless
> has no side-effects.
Drinking the Merry Pranksters' functional kool-aid returns a copy of
you on acid. Drinking Jim Jones' functional kool-aid returns a copy of
you that is dead.
In the real world, it just kills you. ;^)
tim Josling
> Raffael Cavallaro <raffaelcavallaro@pas-d'espam-s'il-vous-plait-mac.com>
> writes:
>
>> On 2008-01-06 16:29:50 -0500, David Kastrup <d...@gnu.org> said:
>>
>>> That's not how sorting items works in real life. The original order
>>> gets lost.
>>
>> clearly you haven't drunk the functional kool-ade ;^)
>
> Tell that to the cons cells.
>
Lisp does support imperative, functional and OO styles of programming. So
you can't assume everything has to be functional. Unlike Haskell, Lisp is
not a pure functional language and has variable/place assignments. It
would be nice if Lisp was more consistent in its naming, so the programmer
could more easily tell which functions have side-effects and which don't.
In scheme, the naming conventions make it very easy - but scheme was
designed from scratch by a small group, and Lisp evolved over a period of
time.
[I sometimes suspect that some of these difficulties with Lisp are not
accidental. The significant cognitive hurdles involved in using Lisp have
the effect of keeping stupid people from using the language. Not everyone
wants the VB crew using Lisp. The relatively civilized tone of
comp.lang.lisp seems to reflect the kind of people who use Lisp. Still
as they say, it's probably not a conspiracy, more likely it's just a
stuff-up.]
Functional programming has limitations. Some data structures just have to
be mutable for performance and when dealing with external entities you have
to remember the state. Even Haskell has had to add Monads, and ML has
mutable arrays.
But I have found that if I program in a functional style, debugging and
testing are a lot more efficient. With no side-effects and no hidden
internal state, all that you need to test is the outputs versus the
inputs. Once you have tested that, you are done. The incidence of weird,
time-consuming bugs goes down significantly.
Pure functional style also makes reuse a lot easier in my experience. The
interfaces are a lot simpler to use because of the lack of preconditions
and side-effects.
In contrast, imperative programming with mutable variables is a lot harder
for humans and computers to reason about. As an example. look at how
easily an effective multi-threading facility was added to Haskell, but
languages with variable assignment either impose a large burden on the
programmer (C*, Java) or it just doesn't perform (Python).
The functional people have the view that variable assignment is like
"GOTO" for variables. To some extent they have a point I think.
Generally I find that it's only the performance.sensitive "inner loop"
that needs to be written in imperative style. I then try to hide the
imperative nature of this inner loop from the rest of the program.
Tim Josling
Pascal Bourguignon
> [ comp.lang.lisp only; http://www.nhplace.com/kent/PFAQ/cross-posting.html ]
>
> Raffael Cavallaro <raffaelcavallaro@pas-d'espam-s'il-vous-plait-mac.com> writes:
>
>> On 2008-01-06 16:29:50 -0500, David Kastrup <d...@gnu.org> said:
>>
>> > That's not how sorting items works in real life. The original order
>> > gets lost.
>>
>> clearly you haven't drunk the functional kool-ade ;^)
>
> Perhaps it's a marketing error on the functional community's part;
> I'm somehow imagining a mind-altering beverage that nevertheless
> has no side-effects.
Oh, then you don't want kool-aid, you want mon-aid.
> To paraphrase Oliver Wendell Holmes (with all due apology):
> "A mind that once stretched by a new idea never regains its
> original dimensions is obviously not functional."
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Our users will know fear and cower before our software! Ship it!
Ship it and let them flee like the dogs they are!"
Pertti Kellomäki
> Maybe it needs to be made explicit that using a functional style will
> cause programs to not resemble the real world, in that the real world is
> often all about the side effects.
Maybe it also needs to be made explicit that -- regardless of what the
OO crowd will tell you -- a 1:1 mapping between programs and the real
world is not always necessary or even desireable. If it were so, it
would be dead easy to design programs.
--
Pertti
Holger Schauer
> David Kastrup <d...@gnu.org> writes:
>> tim Josling <tejgcc...@westnet.com.au> writes:
>> > I see sorting as a function that takes an unsorted list and returns a
>> > sorted list.
>> That's not how sorting items works in real life. The original order
>> gets lost.
> I certainly think it's worth noting that there are such issues as you're
> doing. It's good design practice to be aware of people's real world
> sensibilities. But I think it's also worth not taking this to an extreme.
I'm not certain what David was refering to, but real life here may
also have a computer-related connotation -- most algorithm books I've
seen show sorting as a destructive operation.
Holger
--
--- http://hillview.bugwriter.net/ ---
Fachbegriffe der Informatik - Einfach erklärt
283: whoami
Whoami ist nur was für Leute mit Alzheimer! (Begründung von
Microsoft Deutschland für das Entfernen des Befehls aus Windows
NT)
Kent M Pitman
> On 5240 September 1993, Kent M. Pitman wrote:
> > David Kastrup <d...@gnu.org> writes:
> >> That's not how sorting items works in real life. The original order
> >> gets lost.
> [...]
> > I certainly think it's worth noting that there are such issues as you're
> > doing. It's good design practice to be aware of people's real world
> > sensibilities. But I think it's also worth not taking this to an extreme.
> I'm not certain what David was refering to, but real life here may
> also have a computer-related connotation -- most algorithm books I've
> seen show sorting as a destructive operation.
An algorithms book is kind of the extreme case of computational minimalism.
I would not expect copying to occur in there at all unless it was criterial
to the algorithm.
It's probably more an illustration of why you can't easily jump to a
retroactive justification of a design choice--it's not obvious where
to draw the data from unless you've made a proper description of your
target audience in advance.
Raffael Cavallaro
> Maybe it also needs to be made explicit that -- regardless of what the
> OO crowd will tell you -- a 1:1 mapping between programs and the real
> world is not always necessary or even desireable. If it were so, it
> would be dead easy to design programs.
Absolutely, which is why many are glad that common lisp is a
multiparadigm language where one can do things functionally, or do
things in some OO way, imperatively, recursively[1], iteratively, etc.
It's simply that (as someone else in this thread wrote - Rainer?), lisp
has a functional core, so one needs to be aware that many functions do
not work as one might naively expect them to based on their real world
counterparts.
[1]with suitable settings in a number of implementations
tim Josling
>
> I'm not certain what David was refering to, but real life here may
> also have a computer-related connotation -- most algorithm books I've
> seen show sorting as a destructive operation.
>
> Holger
>
Most of the sorting ever done was probably in a commercial environment. On
commercial mainframes you typically have a different input and output
file. Similarly COBOL's sort has separate input and output files and/or
procedures.
Google's map/reduce incorporates a sort step which is not destructive. In
fact the whole process is modeled on a functional (non-destructive)
paradigm for performance reasons. Using a functional approach allows
massive parallelism, and allows all sorts of other techniques to speed
things up. For example if a process fails, just run it again. No concerns
about half-completed updated. If a process is running slow, start a second
copy and use the output of the one that finishes first.
Taking this into account I think it is hard to argue that sorting is
inherently or obviously destructive.
---
I have nothing against destructive operations when appropriate. And when
properly flagged, which is not the case in Lisp.
It's just that they tend to create elusive bugs and they are harder to test
than purely functional operations. Especially if the caller was not aware
it was destructive.
Tim Josling
Vassil Nikolov
> ...
> Most of the sorting ever done was probably in a commercial environment. On
> commercial mainframes you typically have a different input and output
> file. Similarly COBOL's sort has separate input and output files and/or
> procedures.
And then in the past, people used to sort tape files _a lot_. Think
about optimizing sort runs with regards to the number of work tapes
used. (Who wrote that the good old times are those which we have
forgotten a lot about?)
Or, (with apologies to Paul Simon)
Mama, don't take my destructive sort routine away...
---Vassil.
--
Bound variables, free programmers.
Robert Maas, see http://tinyurl.com/uh3t
> As for SORT Robert Maas posted a small hack that would preserve the head
> cons after calling the implementation's SORT in SORT-KEEPING-HEAD-CELL
> Dated "11 Oct 2007 02:44:41 -0700"]
Note I haven't fully tested that code, so corrections would be welcome.
But it's nice that I'm fondly remembered for my occasional hackery.
<http://groups.google.com/group/comp.lang.lisp/msg/c99a0c00771261bc?dmode=source>
However I think I have a cleaner idea: Keep aside a single CONS cell
(or re-allocate it each time for better thread safety but increased CONSing),
temporarily splice it in place of the user's head cell before sorting,
then splice the user's head cell back in after sorting.
No special cases are needed except for empty (or single-element) list.
(defvar *temphead* (cons nil nil))
(defun sort-keeping-head-cell (userhead sortfn)
(when (cdr userhead)
(shiftf (car *temphead*) (car userhead) nil)
(shiftf (cdr *temphead*) (cdr userhead) nil)
(setq *temphead* (sort *temphead* sortfn))
(shiftf (car userhead) (car *temphead*) nil)
(shiftf (cdr userhead) (cdr *temphead*) nil)
)
userhead)
(setq l1 (list 1 3 5 2 4 6))
--> (1 3 5 2 4 6)
(sort-keeping-head-cell l1 #'>)
--> (6 5 4 3 2 1)
l1
--> (6 5 4 3 2 1)
Of course, with either original (ugly) or new (clean) version, you
really want to mess with &rest argument to have full flexibility of
the built-in SORT function's keyword arguments.
Aside lecture to newbies: In Lisp, we often pass a pointer to a
single CONS cell, but imply passing an entire list or alist or tree
etc. This implication of what we really intend to pass is *not*
built into the language, but is implied by what function we are
calling. For example, when calling the SORT or SORT-KEEPING-HEAD-CELL
function we're really passing only the pointer to the head cell,
but we imply passing the entire list. Kent Pittman's essay on
intention of data type <http://www.nhplace.com/kent/PS/EQUAL.html>
may be useful reading to grok this idea nearly in fullness.
If anyone ever encourages me I might write a companion essay that
extends the idea into ambiguous atomic data types such as integers
(used as if characters in emacs-lisp and c and most other languages
except Common Lisp), and integers again (used as if bit vectors
even in Common Lisp), and numbers in general (used as-is when
really a physical unit is implied, such as kilometers or seconds or
volts or ohms etc.). Hans Moravec had a nice MacSyma utility that
used data values that carried the physical unit around with them,
and thereby allowed trivial conversion from any unit to any other
unit, his favorite being furlongs per fortnight as a unit for speed
or velocity. (I personally prefer nano-c for walking/bicycling
speeds, micro-c for aircraft speeds, etc.)
Gene
> * Gene <3d734438-8f14-48ab-95f6-46aec08e7...@d4g2000prg.googlegroups.com> :
> Wrote on Sun, 6 Jan 2008 13:20:31 -0800 (PST):
> |> > In fact looking at the source for Corman Lisp I discovered that it
> |> > reads the CAR into a vector, sorts that, and then puts the values
> |> > back in the CAR's in sorted order.
> |>
> |> This might have been done for other reasons than avoiding side-effect.
> |> For example, to avoid having two different sort algorithms, or even
> |> because it didn't occur to him how to write the algorithm without
> |> doing indexed access.
> |>
> | Another possible reason is to avoid a certain kind of degenerate cache/
> | paging behavior. If you sort a long, randomly ordered list by
> | changing cdr's, merely traversing the resulting list cells makes for a
> | terrible memory access pattern.
>
> I think there are two many `if's in reasoning about memory access
> patterns. You will traverse the list to get it into the array in the
> first place, and there may be repeated traversals immediately , on the
> resulting list.
>
> But I notice you have made this point in the past, when citing
> your paper which exhibited a SHUFFLE algorithm which worked on cons
> cells. I could not look it up, perhaps you could post a brief
> description of how it worked here?
>
I agree. There may not be many cases when it would benefit.
On the random permuter, I'm really very sorry, but I have no access to
the original lisp. Only C. At least this is a fairly literal
translation of the lisp. Here, rand31() is a random number in [0 ..
2^31 - 1]. I apologize for
// this is a provably random permuter Call initially with tail=NULL.
NODE *permutation(NODE *p, int len, NODE *tail)
{
NODE *e, *l1, *l2, *next;
unsigned int l1_len, l2_len;
unsigned long r;
if (!p) return tail;
for (r = rand31() % len, e = p; r; --r) e = e->left;
for (r = 1, l1 = l2 = NULL, l1_len = l2_len = 0; p != NULL; p = next)
{
next = p->left;
if (r == 1) r = rand31() | (1 << 31); // random bit generator
if (p != e) {
if (r & 1) { p->left = l1; l1 = p; ++l1_len; }
else { p->left = l2; l2 = p; ++l2_len; }
r >>= 1; // set up for next random bit
}
}
e->left = permutation(l1, l1_len, permutation(l2, l2_len, tail));
return(e);
}