Imagine I'm using a language like Lisp but where conses are immutable.
I want to design a data structure which supports two operations:
- adding other objects to it
- mapping some operation over those other objects, in the order they
were added.
It should be possible to interleave these two operations (so add, add,
map (many times), add, add, map (many times) say).
I started doing this (before I realised conses were immutable) using
the standard maintain-a-tail-pointer trick to building lists
forwards. That obviously does not work.
I'm now thinking that the best approach is probably build the list
backwards, and internally maintain a cached right-way-round list,
which would be blown away on any add. Then the map operation would
notice this and call reverse, stash it in the cache, and then map over
that.
But that's just painful.
Is there any pattern I should use which is less horrible than this but
does not involve giving up and using some other structure (extendable
arrays of some kind) such as one would use inJava or something.
I guess the subtext is: how crippled is a Lisp where conses are
immutable?
On Mar 25, 8:29 am, Tim Bradshaw <··········@tfeb.org> wrote:
[...]
> I'm now thinking that the best approach is probably build the list
> backwards, and internally maintain a cached right-way-round list,
> which would be blown away on any add. Then the map operation would
> notice this and call reverse, stash it in the cache, and then map over
> that.
> But that's just painful.
How painful is it to always have the map operation reverse the list,
map your routine over the reversed list, and then reverse the list
again? Then you just have to remember that the newer elements are at
the front of the list rather than at the back.
That doesn't strike me as particularly painful, just slower and more
consy, but then again, I don't know what your other requirements are.
Cheers,
Pillsy
On Mar 25, 6:26 pm, Pillsy <·········@gmail.com> wrote:
> How painful is it to always have the map operation reverse the list,
> map your routine over the reversed list, and then reverse the list
> again? Then you just have to remember that the newer elements are at
> the front of the list rather than at the back.
>
> That doesn't strike me as particularly painful, just slower and more
> consy, but then again, I don't know what your other requirements are.
That's quite painful enough to make me not want to do it.
On Mar 25, 9:29 am, Tim Bradshaw <··········@tfeb.org> wrote:
> I guess the subtext is: how crippled is a Lisp where conses are
> immutable?
Crippled?! I call that a benefic anti-imperative feature. ;)
It could also possibly lead to use of more well suited data-structures
rather than lists for everything.
On Mar 25, 6:36 pm, namekuseijin <············@gmail.com> wrote:
> Crippled?! I call that a benefic anti-imperative feature. ;)
>
> It could also possibly lead to use of more well suited data-structures
> rather than lists for everything.
So, come on now, how would you actually do this? Note I'm not using
lists for everything, I'm using a list as part of the implementation
of a class.
Here's some kind of spec which should map to any Lispy language
Class name is compound-thing
Making an instance of compound-thing (in whatever way is idiomatic)
should allow arguments (either an unbounded number, or a list, up to
you) of initial objects. In the case of a list the new object must
not use the list internally (must copy it, though need not bother if
lists are immutable, obviously).
Two operations on the object:
add-thing adds a new thing to the end of the list
map-things (misnamed) maps a function, for side-effect, over the
thing.
So in CL something like this:
(make-instance 'compound-thing :objects '(1 2 3)) ; must copy that
(add-thing my-thing '1)
(map-thing #'print my-thing)
Details of the syntax do not matter. Identity does - add-thing must
modify its argument.
P� Wed, 25 Mar 2009 21:33:39 +0100, skrev Tim Bradshaw
<··········@tfeb.org>:
> On Mar 25, 6:36�pm, namekuseijin <············@gmail.com> wrote:
>
>> Crippled?! �I call that a benefic anti-imperative feature. ;)
>>
>> It could also possibly lead to use of more well suited data-structures
>> rather than lists for everything.
>
> So, come on now, how would you actually do this? Note I'm not using
> lists for everything, I'm using a list as part of the implementation
> of a class.
>
> Here's some kind of spec which should map to any Lispy language
>
> Class name is compound-thing
>
> Making an instance of compound-thing (in whatever way is idiomatic)
> should allow arguments (either an unbounded number, or a list, up to
> you) of initial objects. In the case of a list the new object must
> not use the list internally (must copy it, though need not bother if
> lists are immutable, obviously).
>
> Two operations on the object:
> add-thing adds a new thing to the end of the list
> map-things (misnamed) maps a function, for side-effect, over the
> thing.
>
> So in CL something like this:
>
> (make-instance 'compound-thing :objects '(1 2 3)) ; must copy that
> (add-thing my-thing '1)
> (map-thing #'print my-thing)
>
> Details of the syntax do not matter. Identity does - add-thing must
> modify its argument.
>
>
Why must it modify it's argument? add-thing could just return the new
object. Of cource your data structures must also be applicative, but if
they are this does not represent a problem. The old element is removed,
then the new element is added. In one operation of cource. (for
efficiency) Critical to make this reasonably efficient is to share data.
Say you have a tree. You replace your parent nodes and your subtree nodes.
but the other ones can just be set to point to the existing nodes.
--------------
John Thingstad
On Mar 25, 9:16 pm, "John Thingstad" <·······@online.no> wrote:
> Why must it modify it's argument?
Because I care about identity. Or, to put it another way: because I'm
asking in a Lisp newsgroup, not one for pure functional languages.
I think I've answered my own question though: Lisp without mutable
conses is sufficiently different that I'd not want to use it, since
I'm profoundly uninterested in functional languages (and if I was
interested I'd not be interested in ones which have assignment but
make half the data structures immutable).
(The reason for the original question, which may seem perverse now, is
that I'm constrained to use such a language, or Java, which has
clearly won the battle.)
In article
<····································@j39g2000yqn.googlegroups.com>,
Tim Bradshaw <··········@tfeb.org> wrote:
> On Mar 25, 9:16�pm, "John Thingstad" <·······@online.no> wrote:
>
> > Why must it modify it's argument?
>
> Because I care about identity. Or, to put it another way: because I'm
> asking in a Lisp newsgroup, not one for pure functional languages.
>
> I think I've answered my own question though: Lisp without mutable
> conses is sufficiently different that I'd not want to use it, since
> I'm profoundly uninterested in functional languages (and if I was
> interested I'd not be interested in ones which have assignment but
> make half the data structures immutable).
Does it have *any* mutable datastructures, or is it totally functional?
If it has mutable structures or arrays, you can emulate conses with them.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
On Mar 26, 2:02 am, Barry Margolin <······@alum.mit.edu> wrote:
> make half the data structures immutable).
>
> Does it have *any* mutable datastructures, or is it totally functional?
> If it has mutable structures or arrays, you can emulate conses with them.
Yes it does, and yes, you can obviously do that.
I think my point (which I have not put very well) is that if you want
to make a "better Lisp" then tinkering of this kind is probably not
really the right approach, because the end result is that you have a
language which looks like Lisp, but actually is not at all like it
because a huge number of techniques familiar to Lisp programmers just
do not work any more. Rather, you're better to start again and make a
different language. which does not try and somehow be "almost" Lisp.
P� Wed, 25 Mar 2009 13:29:20 +0100, skrev Tim Bradshaw
<··········@tfeb.org>:
> Imagine I'm using a language like Lisp but where conses are immutable.
>
> I want to design a data structure which supports two operations:
> - adding other objects to it
> - mapping some operation over those other objects, in the order they
> were added.
> It should be possible to interleave these two operations (so add, add,
> map (many times), add, add, map (many times) say).
>
> I started doing this (before I realised conses were immutable) using
> the standard maintain-a-tail-pointer trick to building lists
> forwards. That obviously does not work.
>
> I'm now thinking that the best approach is probably build the list
> backwards, and internally maintain a cached right-way-round list,
> which would be blown away on any add. Then the map operation would
> notice this and call reverse, stash it in the cache, and then map over
> that.
>
How do make a cache without a hash-table? You could use a Trie I guess,
that could be made applicable.
The straightforward approach is to build it backwards and call reverse.
(If you could use nreverse instead it would be as efficient or more than
maintaining a tail pointer. But that's not applicable, so you end up
needlessly copying the list.)
> But that's just painful.
>
> Is there any pattern I should use which is less horrible than this but
> does not involve giving up and using some other structure (extendable
> arrays of some kind) such as one would use inJava or something.
>
> I guess the subtext is: how crippled is a Lisp where conses are
> immutable?
As you seem to have noticed, quite crippled. So the question then is 'why
do you want to do this?' Seriously I think you are solving the wrong
problem. A cons is a very low level abstraction. I would be like trying to
build Haskell without allowing the code to be internally rewritten to
applicable code. You could do it but it would be very slow and awkward.
Perhaps you can take a look at the series library for a alternative way of
thinking about it that is more efficient and usable.
http://series.sourceforge.net/
http://common-lisp.net/project/fset/
http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504/ref=sip_rech_dp_8
--------------
John Thingstad
On Mar 25, 1:23 pm, "John Thingstad" <·······@online.no> wrote:
> As you seem to have noticed, quite crippled. So the question then is 'why
> do you want to do this?' Seriously I think you are solving the wrong
> problem. A cons is a very low level abstraction. I would be like trying to
> build Haskell without allowing the code to be internally rewritten to
> applicable code. You could do it but it would be very slow and awkward.
I'm perfectly willing to consider other ways of doing it: I just need
something which supports the semantics I've described, and which is
not enormously more painful to implement. Everything else I've seen
(including some of the ones you posted links to) definitely counts as
"enormously more painful".
I guess the answer I probably am looking for is that, in fact, these
purer Lisps are sufficiently painful to use that it's just easier to
use Java.
Tim Bradshaw wrote:
> Imagine I'm using a language like Lisp but where conses are immutable.
>
> I guess the subtext is: how crippled is a Lisp where conses are
> immutable?
For a non-imaginary example you can take a look at AutoLISP.
--
On Mar 25, 6:03 pm, Martti Halminen <···············@nospam.invalid>
wrote:
> For a non-imaginary example you can take a look at AutoLISP.
My example is also non-imaginary, I just didn't want to start a fight
about specific implementations.
Tim Bradshaw schrieb:
> Imagine I'm using a language like Lisp but where conses are immutable.
>
> I want to design a data structure which supports two operations:
> - adding other objects to it
> - mapping some operation over those other objects, in the order they
> were added.
> It should be possible to interleave these two operations (so add, add,
> map (many times), add, add, map (many times) say).
>
> I started doing this (before I realised conses were immutable) using
> the standard maintain-a-tail-pointer trick to building lists
> forwards. That obviously does not work.
>
> I'm now thinking that the best approach is probably build the list
> backwards, and internally maintain a cached right-way-round list,
> which would be blown away on any add. Then the map operation would
> notice this and call reverse, stash it in the cache, and then map over
> that.
>
> But that's just painful.
>
> Is there any pattern I should use which is less horrible than this but
> does not involve giving up and using some other structure (extendable
> arrays of some kind) such as one would use inJava or something.
>
> I guess the subtext is: how crippled is a Lisp where conses are
> immutable?
Do you have an example of code?
From what you said I don't fully understand what you want to achieve and
what part of it does not work out?
Here one example in Clojure:
user> (conj [] 7)
[7]
user> (conj *1 17)
[7 17]
user> (conj *1 27)
[7 17 27]
user> (vec (map #(+ % 3) *1))
[10 20 30]
user> (conj *1 40)
[10 20 30 40]
Where *1 is the result of the previous form. In your code those would be
just forwarded into other functions.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
Andr� Thieme <······························@justmail.de> writes:
> Tim Bradshaw schrieb:
>> Imagine I'm using a language like Lisp but where conses are immutable.
>> I want to design a data structure which supports two operations:
>> - adding other objects to it
>> - mapping some operation over those other objects, in the order they
>> were added.
>> It should be possible to interleave these two operations (so add, add,
>> map (many times), add, add, map (many times) say).
>> I started doing this (before I realised conses were immutable) using
>> the standard maintain-a-tail-pointer trick to building lists
>> forwards. That obviously does not work.
>> I'm now thinking that the best approach is probably build the list
>> backwards, and internally maintain a cached right-way-round list,
>> which would be blown away on any add. Then the map operation would
>> notice this and call reverse, stash it in the cache, and then map over
>> that.
>> But that's just painful.
>> Is there any pattern I should use which is less horrible than this
>> but
>> does not involve giving up and using some other structure (extendable
>> arrays of some kind) such as one would use inJava or something.
>> I guess the subtext is: how crippled is a Lisp where conses are
>> immutable?
>
> Do you have an example of code?
;; So you wanted immutable conses?
(defclass icons ()
((car :initarg :car :reader icar)
(cdr :initarg :cdr :reader icdr)))
(defun icons (car cdr) (make-instance 'icons :car car :cdr cdr))
(defun iconsp (object) (typep object 'icons))
(defmethod icar ((self null)) self)
(defmethod icdr ((self null)) self)
(defmethod icar ((self cons)) (car self))
(defmethod icdr ((self cons)) (cdr self))
(defgeneric iprint (object &optional stream)
(:method ((self t) &optional (stream *standard-output*))
(prin1 self stream))
(:method ((self icons) &optional (stream *standard-output*))
(loop
:for sep = "" :then " "
:for cell = self :then (icdr cell)
:initially (princ "#i(" stream)
:while (iconsp cell)
:do (princ sep stream)
(iprint (icar cell) stream)
:finally (when cell
(princ " . " stream)
(iprint cell stream))
(princ ")" stream))))
(defmethod print-object ((self icons) stream)
(iprint self stream)
self)
(deftype ilist () '(or null icons))
(defun ilistp (object) (or (null object) (iconsp object)))
(defun ilist (&rest args)
(loop
:with result = nil
:for item :in (reverse args)
:do (setf result (icons item result))
:finally (return result)))
(defgeneric ilength (object)
(:method ((self null)) 0)
(:method ((self cons)) (length self))
(:method ((self icons))
(loop
:for len :from 0
:for cell = self :then (icdr cell)
:while (iconsp cell)
:finally (return len))))
(defmacro ipush (&environment env element place)
(multiple-value-bind (vars vals store-vars writer-form reader-form)
(get-setf-expansion place env)
(when (cdr store-vars) (error "Can't expand this."))
(let ((velement (gensym))
(vstore (car store-vars)))
`(let* ((,velement ,element)
,@(mapcar (function list) vars vals)
(,vstore ,reader-form))
(setq ,vstore (icons ,velement ,vstore))
,writer-form))))
(defmacro ipop (&environment env place)
(multiple-value-bind (vars vals store-vars writer-form reader-form)
(get-setf-expansion place env)
(when (cdr store-vars) (error "Can't expand this."))
(let ((vstore (car store-vars)))
`(let* (,@(mapcar (function list) vars vals)
(,vstore ,reader-form))
(prog1
(cond ((iconsp ,vstore) (icar ,vstore))
((consp ,vstore) (car ,vstore))
((null ,vstore) nil)
(t
(error "~S is not a list" ,vstore)))
(setq ,vstore (icdr ,vstore))
,writer-form)))))
(defun irevappend (ilist itail)
(loop
:with result = itail
:for cell = ilist :then (icdr cell)
:while (iconsp cell)
:do (ipush (icar cell) result)
:finally (return result)))
(defun ireverse (ilist)
(irevappend ilist nil))
(defun imapcar (fun ilist)
(loop
:with result = nil
:for cell = ilist :then (icdr cell)
:while (iconsp cell)
:do (setf result (icons (funcall fun (icar cell)) result))
:finally (return result)))
;; So we can implement faithfully Tim's data structure:
(defclass pain ()
((recently-added :initform nil :type ilist :accessor %pain-recently-added)
(oldies :initform nil :type ilist :accessor %pain-oldies)))
(defmethod pain-length ((self pain))
(+ (ilength (%pain-recently-added self))
(ilength (%pain-oldies self))))
(defmethod pain-add ((self pain) item)
"Add ITEM to the PAIN in O(1)"
(ipush item (%pain-recently-added self)))
(defmethod pain-map ((self pain) fun)
"Map FUN on the items in PAIN."
(when (%pain-recently-added self)
(setf (%pain-oldies self) (irevappend (ireverse (%pain-oldies self))
(ireverse (%pain-recently-added self)))
(%pain-recently-added self) nil))
(imapcar fun (%pain-oldies self)))
(let ((p (make-instance 'pain)))
(pain-add p 1) ; O(1)
(pain-add p 2) ; O(1)
(pain-add p 3) ; O(1)
(pain-map p 'prin1) (terpri) ; O(3n)
(pain-map p 'prin1) (terpri) ; O(n)
(pain-add p 4) ; O(1)
(pain-add p 5) ; O(1)
(pain-add p 6) ; O(1)
(pain-map p 'prin1) (terpri) ; O(3n)
(pain-map p 'prin1) (terpri)) ; O(n)
;; Since we get O(1) for add and O(n) for map, I think everybody can be happy.
> From what you said I don't fully understand what you want to achieve and
> what part of it does not work out?
>
> Here one example in Clojure:
> user> (conj [] 7)
> [7]
> user> (conj *1 17)
> [7 17]
> user> (conj *1 27)
> [7 17 27]
> user> (vec (map #(+ % 3) *1))
> [10 20 30]
> user> (conj *1 40)
> [10 20 30 40]
>
> Where *1 is the result of the previous form. In your code those would be
> just forwarded into other functions.
You cannot use clojure (this way) to understand the problem, because
clojure hides it from the programmer. (In the same way, you cannot use
Lisp to demonstrate how garbage collection work (unless you "simulate"
the "real" memory)).
In the case of your operations, you don't see that there are some
operations that are not O(1). I've been told that operations on
vectors in clojure are O(log32(n))...
--
__Pascal Bourguignon__
Pascal J. Bourguignon schrieb:
> Andr� Thieme <······························@justmail.de> writes:
>
>> Tim Bradshaw schrieb:
>>> Imagine I'm using a language like Lisp but where conses are immutable.
>>> I want to design a data structure which supports two operations:
>>> - adding other objects to it
>>> - mapping some operation over those other objects, in the order they
>>> were added.
>>> It should be possible to interleave these two operations (so add, add,
>>> map (many times), add, add, map (many times) say).
>>> I started doing this (before I realised conses were immutable) using
>>> the standard maintain-a-tail-pointer trick to building lists
>>> forwards. That obviously does not work.
>>> I'm now thinking that the best approach is probably build the list
>>> backwards, and internally maintain a cached right-way-round list,
>>> which would be blown away on any add. Then the map operation would
>>> notice this and call reverse, stash it in the cache, and then map over
>>> that.
>>> But that's just painful.
>>> Is there any pattern I should use which is less horrible than this
>>> but
>>> does not involve giving up and using some other structure (extendable
>>> arrays of some kind) such as one would use inJava or something.
>>> I guess the subtext is: how crippled is a Lisp where conses are
>>> immutable?
>> Do you have an example of code?
>
>
> ;; So you wanted immutable conses?
Thanks for your detailed example!
>> From what you said I don't fully understand what you want to achieve and
>> what part of it does not work out?
>>
>> Here one example in Clojure:
>> user> (conj [] 7)
>> [7]
>> user> (conj *1 17)
>> [7 17]
>> user> (conj *1 27)
>> [7 17 27]
>> user> (vec (map #(+ % 3) *1))
>> [10 20 30]
>> user> (conj *1 40)
>> [10 20 30 40]
>>
>> Where *1 is the result of the previous form. In your code those would be
>> just forwarded into other functions.
>
> You cannot use clojure (this way) to understand the problem, because
> clojure hides it from the programmer. (In the same way, you cannot use
> Lisp to demonstrate how garbage collection work (unless you "simulate"
> the "real" memory)).
Yes, makes sense.
> In the case of your operations, you don't see that there are some
> operations that are not O(1). I've been told that operations on
> vectors in clojure are O(log32(n))...
Yes, it's what Rich Hickey also mentioned.
While not being exactly O(1) it's also not too slow, if used in the
right scenario (concurrency that is).
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
* Andr� Thieme
>> vectors in clojure are O(log32(n))...
> While not being exactly O(1) it's also not too slow, if used in the
> right scenario (concurrency that is).
Looking at how Clojure vectors are implemented, I'd guesstimate that
they'll perform at least 10x worse for random access and about 100x
worse for random updates, compared to (in-place) operations on "real"
arrays and assuming an average length of a few hundred elements.
Marcus Breiing schrieb:
> * Andr� Thieme
>
>>> vectors in clojure are O(log32(n))...
>
>> While not being exactly O(1) it's also not too slow, if used in the
>> right scenario (concurrency that is).
>
> Looking at how Clojure vectors are implemented, I'd guesstimate that
> they'll perform at least 10x worse for random access and about 100x
> worse for random updates, compared to (in-place) operations on "real"
> arrays and assuming an average length of a few hundred elements.
Yes, those times sound realistic.
Clojure offers both: "real arrays" and its vectors.
Of course, the programmer needs to decide which data structure she needs.
Your estimates about the timing are independent from the plattform
these vectors are implemented in. So, these timings would also be about
the same for C, D, C++, Prolog and Scheme, as soon they implement
concurrency ready vectors in that same style as Rich Hickey did.
The 100x for random updates tell us that those vectors are not made
for random updates. And they are immutable anyway - random updates
make no sense in that scenario. And adding an element E to the end means
to return a new vector that contains everything the previous did plus E.
Changing random elements in Clojure vectors is as useful as adding
elements at the end of an array. For arrays of length of 3000 elements
this would take up to 3000x longer. Of course, this is again independent
from the plattform, including Clojure.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
Andr� Thieme wrote:
> Marcus Breiing schrieb:
>> * Andr� Thieme
>>
>>>> vectors in clojure are O(log32(n))...
>>
>>> While not being exactly O(1) it's also not too slow, if used in the
>>> right scenario (concurrency that is).
>>
>> Looking at how Clojure vectors are implemented, I'd guesstimate that
>> they'll perform at least 10x worse for random access and about 100x
>> worse for random updates, compared to (in-place) operations on "real"
>> arrays and assuming an average length of a few hundred elements.
>
> Yes, those times sound realistic.
> Clojure offers both: "real arrays" and its vectors.
> Of course, the programmer needs to decide which data structure she needs.
> Your estimates about the timing are independent from the plattform
> these vectors are implemented in. So, these timings would also be about
> the same for C, D, C++, Prolog and Scheme, as soon they implement
> concurrency ready vectors in that same style as Rich Hickey did.
Just a sidenote: You should try to tone down your buzzwordy language a
little bit. What Rich Hickey does with Clojure is indeed very cool. But
calling the data structure "concurrency-ready" - as if regular arrays
were not concurrency-ready - is a bit over the top. Really.
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza schrieb:
> Andr� Thieme wrote:
>> Marcus Breiing schrieb:
>>> * Andr� Thieme
>>>
>>>>> vectors in clojure are O(log32(n))...
>>>
>>>> While not being exactly O(1) it's also not too slow, if used in the
>>>> right scenario (concurrency that is).
>>>
>>> Looking at how Clojure vectors are implemented, I'd guesstimate that
>>> they'll perform at least 10x worse for random access and about 100x
>>> worse for random updates, compared to (in-place) operations on "real"
>>> arrays and assuming an average length of a few hundred elements.
>>
>> Yes, those times sound realistic.
>> Clojure offers both: "real arrays" and its vectors.
>> Of course, the programmer needs to decide which data structure she needs.
>> Your estimates about the timing are independent from the plattform
>> these vectors are implemented in. So, these timings would also be about
>> the same for C, D, C++, Prolog and Scheme, as soon they implement
>> concurrency ready vectors in that same style as Rich Hickey did.
>
> Just a sidenote: You should try to tone down your buzzwordy language a
> little bit. What Rich Hickey does with Clojure is indeed very cool. But
> calling the data structure "concurrency-ready" - as if regular arrays
> were not concurrency-ready - is a bit over the top. Really.
They are, if you don't mutate them. How can you know that not one of
your 4 workmates modifies an array?
Sooner or later you will want to represent state. And if you decide that
an array is the right data structure to do so, you will need a strategy
for that.
I really don't understand why you see "concurreny-ready" as a buzzword.
Whoever is is impressed by that will be in shock when you mention
object oriented programming.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
Andr� Thieme wrote:
> Pascal Costanza schrieb:
>> Andr� Thieme wrote:
>>> Marcus Breiing schrieb:
>>>> * Andr� Thieme
>>>>
>>>>>> vectors in clojure are O(log32(n))...
>>>>
>>>>> While not being exactly O(1) it's also not too slow, if used in the
>>>>> right scenario (concurrency that is).
>>>>
>>>> Looking at how Clojure vectors are implemented, I'd guesstimate that
>>>> they'll perform at least 10x worse for random access and about 100x
>>>> worse for random updates, compared to (in-place) operations on "real"
>>>> arrays and assuming an average length of a few hundred elements.
>>>
>>> Yes, those times sound realistic.
>>> Clojure offers both: "real arrays" and its vectors.
>>> Of course, the programmer needs to decide which data structure she
>>> needs.
>>> Your estimates about the timing are independent from the plattform
>>> these vectors are implemented in. So, these timings would also be about
>>> the same for C, D, C++, Prolog and Scheme, as soon they implement
>>> concurrency ready vectors in that same style as Rich Hickey did.
>>
>> Just a sidenote: You should try to tone down your buzzwordy language a
>> little bit. What Rich Hickey does with Clojure is indeed very cool.
>> But calling the data structure "concurrency-ready" - as if regular
>> arrays were not concurrency-ready - is a bit over the top. Really.
>
> They are, if you don't mutate them. How can you know that not one of
> your 4 workmates modifies an array?
I assume they are smart enough not to do so.
On top of that, there are situations when you exactly want to do that,
that different threads assign to the same shared array. As long as they
assign to separate regions of the same array, there is no problem.
Just read some good book on parallel programming, and you will see
enough good examples.
> I really don't understand why you see "concurreny-ready" as a buzzword.
...because it _is_ a buzzword.
Parallel programming has lots of different flavors, and what Clojure
provides is support for "only" a particular kind. "Concurrency-ready"
suggests too much that whatever Clojure supports is all you need, and
that is not the case.
> Whoever is is impressed by that will be in shock when you mention
> object oriented programming.
Whatever.
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On Fri, 27 Mar 2009 14:02:30 +0100, Pascal Costanza wrote:
> André Thieme wrote:
>> They are, if you don't mutate them. How can you know that not one of
>> your 4 workmates modifies an array?
>
> Just read some good book on parallel programming, and you will see
> enough good examples.
Hi Pascal and others,
Could you recommend a good book on parellel programming? I am an
economist with no formal CS background, and I would like to parallelize
some of my numerical programs. I would be writing programs in CL, but
I assume that books are more general -- nevertheless a CL-specific
parallel programming book would be nice too.
Thanks,
Tamas
Tamas K Papp wrote:
> On Fri, 27 Mar 2009 14:02:30 +0100, Pascal Costanza wrote:
>
>> André Thieme wrote:
>>> They are, if you don't mutate them. How can you know that not one of
>>> your 4 workmates modifies an array?
>> Just read some good book on parallel programming, and you will see
>> enough good examples.
>
> Hi Pascal and others,
>
> Could you recommend a good book on parellel programming? I am an
> economist with no formal CS background, and I would like to parallelize
> some of my numerical programs. I would be writing programs in CL, but
> I assume that books are more general -- nevertheless a CL-specific
> parallel programming book would be nice too.
I can recommend this:
http://www.pearsonhighered.com/educator/academic/product/0,3110,0321487907,00.html
For a more lispy perspective, try to get a copy of "The Paralation
Model" by Gary Sabot, that's a very nice book.
Finally, reading about NESL is also not a bad idea:
http://www.cs.cmu.edu/~scandal/nesl.html
See also more recent work on Fortress...
I hope this helps,
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Tamas K Papp schrieb:
> On Fri, 27 Mar 2009 14:02:30 +0100, Pascal Costanza wrote:
>
>> André Thieme wrote:
>>> They are, if you don't mutate them. How can you know that not one of
>>> your 4 workmates modifies an array?
>> Just read some good book on parallel programming, and you will see
>> enough good examples.
>
> Hi Pascal and others,
>
> Could you recommend a good book on parellel programming? I am an
> economist with no formal CS background, and I would like to parallelize
> some of my numerical programs. I would be writing programs in CL, but
> I assume that books are more general -- nevertheless a CL-specific
> parallel programming book would be nice too.
Nice, that's impressive. I always thought that you are the typical
computer scientist.
Anyway, by lots of experts regarded as one of the most important books
on that area is: "Java Concurrency in Practice" by Brian Göetz.
Yes, it uses Java for example code, but that really doesn't matter in
my opinion. Try a search for that book and see what others say, if you
want more opinions.
André
--
Lisp is not dead. It’s just the URL that has changed:
http://clojure.org/
Pascal Costanza wrote:
> On top of that, there are situations when you exactly want to do that,
> that different threads assign to the same shared array. As long as they
> assign to separate regions of the same array, there is no problem.
This is not true, unfortunately.
Consider the following (pseudo) code:
(let ((shared (make-array 16 :element-type '(unsigned-byte 8))))
(make-thread (lambda ()
(loop ... (setf (aref shared 0) ...))))
(make-thread (lambda ()
(loop ... (setf (aref shared 15) ...)))))
Despite not sharing actual array slots, the two threads can influence each
other performancewise, depending on a couple of factors (array alignment,
cache line size, ...). Look for "False Sharing". This is a problem.
Another issue is that when writing into a shared data structure concurrent
threads probably are also reading from it. Then the order of load and stores
is probably important. However, processors have certain freedom to reorder
loads and stores. Without any language guarantees wrt. a memory model you are
pretty much hosed.
The "Intel64 Architecture Memory Ordering White Paper"
<http://www.multicoreinfo.com/research/papers/2008/damp08-intel64.pdf>
contains some interesting cases.
Other processors (Itanium, IIRC) allow even more relaxed orderings.
Michael Weber wrote:
> Pascal Costanza wrote:
>
>> On top of that, there are situations when you exactly want to do that,
>> that different threads assign to the same shared array. As long as they
>> assign to separate regions of the same array, there is no problem.
>
> This is not true, unfortunately.
>
> Consider the following (pseudo) code:
>
> (let ((shared (make-array 16 :element-type '(unsigned-byte 8))))
> (make-thread (lambda ()
> (loop ... (setf (aref shared 0) ...))))
> (make-thread (lambda ()
> (loop ... (setf (aref shared 15) ...)))))
>
> Despite not sharing actual array slots, the two threads can influence each
> other performancewise, depending on a couple of factors (array alignment,
> cache line size, ...). Look for "False Sharing". This is a problem.
>
> Another issue is that when writing into a shared data structure concurrent
> threads probably are also reading from it. Then the order of load and stores
> is probably important. However, processors have certain freedom to reorder
> loads and stores. Without any language guarantees wrt. a memory model you are
> pretty much hosed.
>
> The "Intel64 Architecture Memory Ordering White Paper"
> <http://www.multicoreinfo.com/research/papers/2008/damp08-intel64.pdf>
> contains some interesting cases.
>
> Other processors (Itanium, IIRC) allow even more relaxed orderings.
Sure, these are important issues. But that doesn't necessarily mean that
shared accesses should be completely avoided.
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal Costanza schrieb:
> Andr� Thieme wrote:
>> Pascal Costanza schrieb:
>>> Andr� Thieme wrote:
>>>> Marcus Breiing schrieb:
>>>>> * Andr� Thieme
>>>>>
>>>>>>> vectors in clojure are O(log32(n))...
>>>>>
>>>>>> While not being exactly O(1) it's also not too slow, if used in the
>>>>>> right scenario (concurrency that is).
>>>>>
>>>>> Looking at how Clojure vectors are implemented, I'd guesstimate that
>>>>> they'll perform at least 10x worse for random access and about 100x
>>>>> worse for random updates, compared to (in-place) operations on "real"
>>>>> arrays and assuming an average length of a few hundred elements.
>>>>
>>>> Yes, those times sound realistic.
>>>> Clojure offers both: "real arrays" and its vectors.
>>>> Of course, the programmer needs to decide which data structure she
>>>> needs.
>>>> Your estimates about the timing are independent from the plattform
>>>> these vectors are implemented in. So, these timings would also be about
>>>> the same for C, D, C++, Prolog and Scheme, as soon they implement
>>>> concurrency ready vectors in that same style as Rich Hickey did.
>>>
>>> Just a sidenote: You should try to tone down your buzzwordy language
>>> a little bit. What Rich Hickey does with Clojure is indeed very cool.
>>> But calling the data structure "concurrency-ready" - as if regular
>>> arrays were not concurrency-ready - is a bit over the top. Really.
>>
>> They are, if you don't mutate them. How can you know that not one of
>> your 4 workmates modifies an array?
>
> I assume they are smart enough not to do so.
This would be good, and I would trust you to keep track of all the rules
of what we allow to mutate and what not, in our hypothetical project.
But the reality shows that this unfortunately happens. There need to be
meetings held for all the ressources, and people must agree on how to
treat their data structures.
And then, several months after everybody agreed on what definitly will
not be a shared ressource suddenly becomes one, because the manager
decides so. Then all 73 places in the code that access this ressource
need to be locked, removing potentially a good bit of concurrency.
> On top of that, there are situations when you exactly want to do that,
> that different threads assign to the same shared array. As long as they
> assign to separate regions of the same array, there is no problem.
>
> Just read some good book on parallel programming, and you will see
> enough good examples.
Thanks for the suggestion, but I must play the ball back to you and
suggest you the same. You will see that traditional arrays are not so
concurreny ready as you may think.
>> I really don't understand why you see "concurreny-ready" as a buzzword.
>
> ...because it _is_ a buzzword.
Okay, I can agree on that, but at the same moment it means that many
other terms also then become buzzwords, such as functional programming,
object oriented programming, aspect oriented programming, multiple
dispatch, design patterns, etc.
I have seen you in the past using lots of buzzwords, so I conclude that
you are not in principle against using them.
One difference that I see is that "concurrency ready" is a new term.
A google search reveals that there are only around 100 mentions of this
word in the right context, several times coming from me.
There were people using this term before me, but I might well be the
person who coins this term ;)
Just kidding.
Anyway, from that thought I come to think: you are against the usage of
buzzwords, as long they are not around for a few years.
I personally think that it is okay to use them, especially in the right
context. When experts like us are discussing, then everyone knows that
there is no silver bullet, and for every coolness there are already
several exceptions.
> Parallel programming has lots of different flavors, and what Clojure
> provides is support for "only" a particular kind. "Concurrency-ready"
> suggests too much that whatever Clojure supports is all you need, and
> that is not the case.
There are also potentially hundreds of models for object oriented
programming (though some of them vary only slightly), and I think it is
not important that a language must support 14 of those to be called an
OOP language.
That you put "only" into quotes shows that you are aware that the route
that Clojure goes is a pretty general and reusable one.
For every Lisp expert who actually works with Clojure it will become
very soon clear that this model supports the programmer really well.
There are cases for which other models may be better. But in my opinion
it is absolutely fair to say that Clojure is ready for writing concurrent
applications, without the need to make lots of preparations, compared
to nearly every other existing language. The two other noteworthy
exceptions are Erlang and Haskell.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
Andr� Thieme wrote:
> Pascal Costanza schrieb:
>> Andr� Thieme wrote:
>>> Pascal Costanza schrieb:
>>>> Andr� Thieme wrote:
>>>>> Marcus Breiing schrieb:
>>>>>> * Andr� Thieme
>>>>>>
>>>>>>>> vectors in clojure are O(log32(n))...
>>>>>>
>>>>>>> While not being exactly O(1) it's also not too slow, if used in the
>>>>>>> right scenario (concurrency that is).
>>>>>>
>>>>>> Looking at how Clojure vectors are implemented, I'd guesstimate that
>>>>>> they'll perform at least 10x worse for random access and about 100x
>>>>>> worse for random updates, compared to (in-place) operations on "real"
>>>>>> arrays and assuming an average length of a few hundred elements.
>>>>>
>>>>> Yes, those times sound realistic.
>>>>> Clojure offers both: "real arrays" and its vectors.
>>>>> Of course, the programmer needs to decide which data structure she
>>>>> needs.
>>>>> Your estimates about the timing are independent from the plattform
>>>>> these vectors are implemented in. So, these timings would also be
>>>>> about
>>>>> the same for C, D, C++, Prolog and Scheme, as soon they implement
>>>>> concurrency ready vectors in that same style as Rich Hickey did.
>>>>
>>>> Just a sidenote: You should try to tone down your buzzwordy language
>>>> a little bit. What Rich Hickey does with Clojure is indeed very
>>>> cool. But calling the data structure "concurrency-ready" - as if
>>>> regular arrays were not concurrency-ready - is a bit over the top.
>>>> Really.
>>>
>>> They are, if you don't mutate them. How can you know that not one of
>>> your 4 workmates modifies an array?
>>
>> I assume they are smart enough not to do so.
>
> This would be good, and I would trust you to keep track of all the rules
> of what we allow to mutate and what not, in our hypothetical project.
> But the reality shows that this unfortunately happens. There need to be
> meetings held for all the ressources, and people must agree on how to
> treat their data structures.
> And then, several months after everybody agreed on what definitly will
> not be a shared ressource suddenly becomes one, because the manager
> decides so. Then all 73 places in the code that access this ressource
> need to be locked, removing potentially a good bit of concurrency.
Yes, there are bad programmers out there. That's not a good reason to
cripple programming languages, though.
>>> I really don't understand why you see "concurreny-ready" as a buzzword.
>>
>> ...because it _is_ a buzzword.
>
> Okay, I can agree on that, but at the same moment it means that many
> other terms also then become buzzwords, such as functional programming,
> object oriented programming, aspect oriented programming, multiple
> dispatch, design patterns, etc.
Those buzzwords are not condescending. "Concurrency-ready" implies that
other data structures are not "concurrency-ready." That's nonsense.
Pascal
--
ELS'09: http://www.european-lisp-symposium.org/
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
On 2009-03-25, Tim Bradshaw <··········@tfeb.org> wrote:
> I guess the subtext is: how crippled is a Lisp where conses are
> immutable?
For one thing, cyclic structures are impossible---unless there are special
construction primitives that allow back-references, and which can close the
cycles before returning the entire structure (now immutable) to the program.
A Lisp with immutable conses needs to have some interface for manipulating
mutable conses which then become immutable under the programmer's control.
Like say with some kind ``write protect'' bit which can be only set once.
So for instance if you wanted to use the usual tail pointer based accumulation,
you would write protect each cons after updating it to point to the new cons.
...
(when tail ;; initially NIL
(setf (cdr tail) new-cons)
(write-protect tail))
(setf tail new-cons)
Kaz Kylheku <········@gmail.com> writes:
> On 2009-03-25, Tim Bradshaw <··········@tfeb.org> wrote:
>> I guess the subtext is: how crippled is a Lisp where conses are
>> immutable?
>
> For one thing, cyclic structures are impossible---unless there are special
> construction primitives that allow back-references, and which can close the
> cycles before returning the entire structure (now immutable) to the program.
False.
(defun make-icircular-list (ilist)
(icons ilist ilist))
(defun icircular-current (cilist)
(icar (icdr cilist)))
(defun icircular-advance (cilist)
(if (iconsp (icdr (icdr cilist)))
(icons (icar cilist) (icdr (icdr cilist)))
(icons (icar cilist) (icar cilist))))
(labels ((loop (n c)
(when (plusp n)
(print (icircular-current c))
(loop (1- n) (icircular-advance c)))))
(loop 7 (make-icircular-list (ilist 1 2 3))))
prints:
1
2
3
1
2
3
1
--> NIL
I know that there are no circular pointers inside, but here we have an
immutable circular list data structure displaying all the
characteristics of such. So we didn't remove anything from the user
point of view. What could we say of the speed of the garbage
collector now that it doesn't have to deal with circles?
> A Lisp with immutable conses needs to have some interface for manipulating
> mutable conses which then become immutable under the programmer's control.
> Like say with some kind ``write protect'' bit which can be only set once.
IF you want to be able to implement some kinds of optimizations.
But if that prevents you to implement other kinds of optimizations,
you have a dilema, and you may choose to remove mutable structures
because programs written on some machines may be faster with these
other kinds of optimizations.
> So for instance if you wanted to use the usual tail pointer based accumulation,
> you would write protect each cons after updating it to point to the new cons.
>
> ...
> (when tail ;; initially NIL
> (setf (cdr tail) new-cons)
> (write-protect tail))
> (setf tail new-cons)
It is known for a long time that this technique is not faster (nor
slower) than head-consing and reversing when done.
--
__Pascal Bourguignon__
On Mar 25, 7:27 pm, ····@informatimago.com (Pascal J. Bourguignon)
wrote:
> Kaz Kylheku <········@gmail.com> writes:
[...]
> > ...
> > (when tail ;; initially NIL
> > (setf (cdr tail) new-cons)
> > (write-protect tail))
> > (setf tail new-cons)
> It is known for a long time that this technique is not faster (nor
> slower) than head-consing and reversing when done.
I understand why it would be the same speed (or virtually the same
speed) as head-consing and then NREVERSEing, but I'd think that
consing and then just-plain-REVERSEing needn't be the same speed
(since you'd cons more but wouldn't be use RPLACD at all).
Cheers,
Pillsy
Pillsy <·········@gmail.com> writes:
> On Mar 25, 7:27�pm, ····@informatimago.com (Pascal J. Bourguignon)
> wrote:
>> Kaz Kylheku <········@gmail.com> writes:
> [...]
>> > � ...
>> > � (when tail ;; initially NIL
>> > � � (setf (cdr tail) new-cons)
>> > � � (write-protect tail))
>> > � (setf tail new-cons)
>
>> It is known for a long time that this technique is not faster (nor
>> slower) than head-consing and reversing when done. �
>
> I understand why it would be the same speed (or virtually the same
> speed) as head-consing and then NREVERSEing, but I'd think that
> consing and then just-plain-REVERSEing needn't be the same speed
> (since you'd cons more but wouldn't be use RPLACD at all).
With a generational garbage collector it may well not make any
difference.
It could be slower if the list is between half and full cache size.
But since you had to create it (take time to compute the elements) I
doubt that the time difference in copying the cells inside the cache
or outside of it would be significant.
--
__Pascal Bourguignon__
On 2009-03-25, Pascal J. Bourguignon <···@informatimago.com> wrote:
> Kaz Kylheku <········@gmail.com> writes:
>
>> On 2009-03-25, Tim Bradshaw <··········@tfeb.org> wrote:
>>> I guess the subtext is: how crippled is a Lisp where conses are
>>> immutable?
>>
>> For one thing, cyclic structures are impossible---unless there are special
>> construction primitives that allow back-references, and which can close the
>> cycles before returning the entire structure (now immutable) to the program.
>
> False.
>
>
> (defun make-icircular-list (ilist)
> (icons ilist ilist))
>
> (defun icircular-current (cilist)
> (icar (icdr cilist)))
>
> (defun icircular-advance (cilist)
> (if (iconsp (icdr (icdr cilist)))
> (icons (icar cilist) (icdr (icdr cilist)))
> (icons (icar cilist) (icar cilist))))
>
>
> (labels ((loop (n c)
> (when (plusp n)
> (print (icircular-current c))
> (loop (1- n) (icircular-advance c)))))
> (loop 7 (make-icircular-list (ilist 1 2 3))))
>
> I know that there are no circular pointers inside
Then why post that as some kind of counter-argument?
April 1st is still some days away, you know.
Sure you can model special cases circularity using clumsy some conventions
inside a dag.
> What could we say of the speed of the garbage
> collector now that it doesn't have to deal with circles?
We can say that a dumber garbage collector is possible which is faster to
develop, but runs slower.
>> A Lisp with immutable conses needs to have some interface for manipulating
>> mutable conses which then become immutable under the programmer's control.
>> Like say with some kind ``write protect'' bit which can be only set once.
>
> IF you want to be able to implement some kinds of optimizations.
Optimizations? I was writing about simply making it possible to construct an
arbitrarily complex cyclic object (which is then immutable).
> But if that prevents you to implement other kinds of optimizations,
> you have a dilema, and you may choose to remove mutable structures
> because programs written on some machines may be faster with these
> other kinds of optimizations.
I doubt it. All mainstream machines are based on mutable memory. Moreover
algorithms that mutate values have a better locality of reference; better use
of registers and caches.
>> (when tail ;; initially NIL
>> (setf (cdr tail) new-cons)
>> (write-protect tail))
>> (setf tail new-cons)
>
> It is known for a long time that this technique is not faster (nor
> slower) than head-consing and reversing when done.
Sure, on small lists that fit into your L1 cache.
From: Tobias C. Rittweiler
Subject: Re: Immutable conses and pain
Date:
Message-ID: <87tz5gtzqp.fsf@freebits.de>
···@informatimago.com (Pascal J. Bourguignon) writes:
> > So for instance if you wanted to use the usual tail pointer based accumulation,
> > you would write protect each cons after updating it to point to the new cons.
> >
> > ...
> > (when tail ;; initially NIL
> > (setf (cdr tail) new-cons)
> > (write-protect tail))
> > (setf tail new-cons)
>
> It is known for a long time that this technique is not faster (nor
> slower) than head-consing and reversing when done.
A long time ago I wrote PUSHEND (see post scriptum) so you can write a
collecting loop like the following
(let ((list) (tail))
(dotimes (i 1000 list)
(pushend i list tail)))
From recollecting the memories of the ad-hoc microbenchmarking I did
back then, I remember that the above is actually _25-30% faster_ than
the PUSH+NREVERSE idiom, both on long lists and small lists on
implementations that compile to native code.
On Clisp it was 30% slower as NREVERSE is written in C and hence very
performant comparing to ordinary Lisp code.
I wouldn't vouch for this as the absolute truth as the benchmarking was
very ad-hoc. But see the code below if you want to give it a shot
yourself.
-T.
PS
(define-modify-macro nconcf (&rest lists) nconc)
(defmacro pushend (new-item list &optional list-end)
(if list-end
`(%pushend ,new-item ,list ,list-end)
;; This actually was `(CALLF #'NCONC ,LIST (LIST ,LIST-END))
`(nconcf ,list (list ,new-item))))
(defmacro %pushend (new-item list list-end &environment env)
(multiple-value-bind (list.gvars list.vals list.gstorevars list.setter list.getter)
(get-setf-expansion list env)
(multiple-value-bind (tail.gvars tail.vals tail.gstorevars tail.setter tail.getter)
(get-setf-expansion list-end env)
(when (or (second list.gstorevars) (second tail.gstorevars))
(error "%PUSHEND -- VALUES place not supported"))
(let ((gitem (gensym "NEWITEM+"))
(list.gstorevar (first list.gstorevars))
(tail.gstorevar (first tail.gstorevars)))
`(let (,@(mapcar #'list list.gvars list.vals)
,@(mapcar #'list tail.gvars tail.vals))
(let ((,gitem (list ,new-item)))
;;; XXX: I really would like a declaration that tells a
;;; compiler that one branch of an IF is unlikely to be
;;; taken.
(if ,list.getter
(let ((,tail.gstorevar ,gitem))
(setf (cdr ,tail.getter) ,gitem) ; update LIST
,tail.setter) ; set LIST-END to new tail.
(let ((,list.gstorevar ,gitem)
(,tail.gstorevar ,gitem))
,list.setter ,tail.setter ; set LIST and LIST-END to
)))))))) ; a list with the new item.