I thought about implementing a kind of the Clojure-style SEQ protocol
for iterating over arbitrary collections. Below is my first take.
I wanted to ask to review the code: maybe there are some things, that
I missed (like terrible inefficiencies)?
The design overview is given below. Overall, I didn't find it hard to
do it, so even less now I understand the premise of Clojure, that it's
so hard to extend CL in this direction.
Sidenote
--------
Not to introduce irrelevant complexity here I use unique function
names for the operations: FST for FIRST, RST for REST, NXT for POP,
ELM fot ELT and INTO for COERCE. It is quite possible to shadow the
bult-ins, but I don't see this step as necessary here. It's more the
question of taste...
Implemetation
-------------
The implementation of the protocol can be found at: http://paste.lisp.org/display/77174#1
(For reference I show the implementation of methods on concrete
sequences as well).
The SEQ class is defined as a thin wrapper around collection classes,
which has a reference to the concrete collection, to the position in
it and an iterator in collection. Basically, it's all just syntactic
sugar over iterators.
To use the concrete collection as a seq, just call SEQ with it.
Afterwards 4 operations are possible:
* FST, NXT and ELM return 2 values: the value of an item in the
collection and the corresponding key (for sequence type the key is
just an item's number). To test for the end of collection check the
nullity of key (no errors will be signaled for out-of-bounds
conditions)
* RST returns the rest of the sequence (lazily)
No CONS (in Clojure meaning)
----------------------------
The main purpose of SEQ is to give the ability to iterate over various
collections uniformly. But there's no problem of accumulation.
Accumulation is solved: just use lists (it's the most simple and
efficient way). It's possible to define the analog of Clojure's CONS
operation, but we'll need to pay the price of generic dispatch
(moreover, twice) on each operation. It's much more efficient to pay
it not more, than once, for the whole accumulation loop. So if you
want to get the concrete sequence of the same type, as the argument,
just convert the result to it (with INTO). This pattern can be
codified with the following macros:
(defmacro doseq
((var-form coll &optional result) &body body)
"The analog of DOLIST for any collection COLL,
which can be put in a seq.
VAR-FORM can be either ATOM, in which case this name
is bound to the value (1st), returned by NXT, or LIST:
the 1st symbol will be bound to the 1st value (value),
returned by NXT, and the 2nd -- to the 2nd (key).
If RESULT form is provided, it's value will be returned"
(with-gensyms (gseq key val)
`(let ((,gseq (seq ,coll)))
(loop
(multiple-value-bind (,val ,key) (nxt ,gseq)
(multiple-value-bind ,(mklist var-form)
(values ,val ,key)
(if ,key (progn ,@body)
(return ,result))))))))
(defmacro with-acc
((var-form acc-name coll &optional result-type)
&body body)
"Iterate over COLL with accumulation to list and
conversion into either RESULT-TYPE or type-of COLL.
VAR-FORM can be either ATOM, in which case this name
is bound to the value (1st), returned by NXT, or LIST:
the 1st symbol will be bound to the 1st value (value),
returned by NXT, and the 2nd -- to the 2nd (key)."
(with-gensyms (gseq)
`(let ((,gseq (seq ,coll)))
(into (or ,result-type (seq-ref ,gseq))
(with-output-to-list (,acc-name)
(doseq (,var-form ,gseq)
,@body))))))
(Where with-gensyms, mklist and with-output-to-list are the common
utility macros).
You can as well define extensions for ITERATE:
(iter:defmacro-clause (ITER:FOR var ITER:NXT coll)
"Iterate over COLL as a SEQ"
(with-gensyms (gseq k v)
`(progn (iter:with ,gseq := (seq ,coll))
(iter:for ,var
:next (multiple-value-bind (,v ,k)
(nxt ,gseq)
(if ,k ,v
(iter:terminate)))))))
Examples
--------
Using range:
(defclass range ()
((start :initarg :start :reader range-start :initform 0)
(end :initarg :end :reader range-end)
(step :initarg :step :reader range-step :initform 1)))
(defun range (start &key end step)
(make-instance 'range :start start :end end :step step))
(defmethod seq ((coll range) &optional (start-pos 0))
(make-instance 'seq :ref coll :pos start-pos
:itr #`(with-slots (step end) coll
(let ((rez (+ start-pos (* _ step))))
(and (or (not end) (<= rez end))
(values rez
_))))))
CL-USER> (with-acc (v rez (range 0 :step 2 :end 10) 'vector)
(push v rez))
#(0 2 4 6 8 10)
Implementing generic FILTER.
Here I faced the problem with iteration over two different kinds of
collections: with meaningful keys, that should be preserved (hash-
tables), and with, let's say, implicit keys (ordinary sequences, for
which we can say, that key is a number). There are 2 ways to treat
them: either to indicate explicitly, what type of sequence it is, in
the SEQ class, or to track the list of keys separately and use it in
situations, wheh it's needed: like creating a hash-table from list,
which is performed in INTO. After some though I decided, that the
explicit indication is a much simpler and better way, because keys are
needed only in small fraction of situations. The usage of the
indicator can be seen in FILTER implementation (I believe, it's quite
natural):
(defun filter (fn coll)
"Sequentially apply FN to all elements of COLL and
return the collection, consisting of only non-nil results"
(let ((seq (seq coll)))
(with-slots (ref kv?) seq
(with-acc ((v k) acc seq)
(when-it (funcall fn v)
(when kv?
(push k acc))
(push it acc))))))
Althought, the right choice for filter is to define it generic as
well. The difference in performance between a concrete list FILTER:
(defun filter (fn lst)
"Sequentially apply FN to all elements of LST and
return the list, consisting of only non-nil results"
(let ((acc nil))
(dolist (x lst)
(let ((val (funcall fn x)))
(if val (push val acc))))
(nreverse acc)))
and the generic one can be upto 10-100 times (for small computations,
like (filter #'oddp '(1 2 3))).
P.S.
----
Afterwards I looked in Clojure core.clj source to see, how filter is
implemented there. Interestingly enough, it doesn't work on maps:
user=> (filter odd? {:a 1 :b 2})
java.lang.ClassCastException: clojure.lang.MapEntry cannot be cast to
java.lang.Number (NO_SOURCE_FILE:0)
user=> (filter odd? (seq {:a 1 :b 2}))
java.lang.ClassCastException: clojure.lang.MapEntry cannot be cast to
java.lang.Number (NO_SOURCE_FILE:0)
and for a Vector argument the result type is List...
In general there is a shameless plug: http://common-lisp.net/projects/cl-enumeration
Cheers
--
Marco
Vsevolod wrote:
> I thought about implementing a kind of the Clojure-style SEQ protocol
> for iterating over arbitrary collections. Below is my first take.
>
> I wanted to ask to review the code: maybe there are some things, that
> I missed (like terrible inefficiencies)?
> The design overview is given below. Overall, I didn't find it hard to
> do it, so even less now I understand the premise of Clojure, that it's
> so hard to extend CL in this direction.
>
>
> Sidenote
> --------
> Not to introduce irrelevant complexity here I use unique function
> names for the operations: FST for FIRST, RST for REST, NXT for POP,
> ELM fot ELT and INTO for COERCE. It is quite possible to shadow the
> bult-ins, but I don't see this step as necessary here. It's more the
> question of taste...
>
>
> Implemetation
> -------------
> The implementation of the protocol can be found at: http://paste.lisp.org/display/77174#1
> (For reference I show the implementation of methods on concrete
> sequences as well).
>
> The SEQ class is defined as a thin wrapper around collection classes,
> which has a reference to the concrete collection, to the position in
> it and an iterator in collection. Basically, it's all just syntactic
> sugar over iterators.
>
> To use the concrete collection as a seq, just call SEQ with it.
> Afterwards 4 operations are possible:
> * FST, NXT and ELM return 2 values: the value of an item in the
> collection and the corresponding key (for sequence type the key is
> just an item's number). To test for the end of collection check the
> nullity of key (no errors will be signaled for out-of-bounds
> conditions)
> * RST returns the rest of the sequence (lazily)
>
> No CONS (in Clojure meaning)
> ----------------------------
> The main purpose of SEQ is to give the ability to iterate over various
> collections uniformly. But there's no problem of accumulation.
> Accumulation is solved: just use lists (it's the most simple and
> efficient way). It's possible to define the analog of Clojure's CONS
> operation, but we'll need to pay the price of generic dispatch
> (moreover, twice) on each operation. It's much more efficient to pay
> it not more, than once, for the whole accumulation loop. So if you
> want to get the concrete sequence of the same type, as the argument,
> just convert the result to it (with INTO). This pattern can be
> codified with the following macros:
>
> (defmacro doseq
> ((var-form coll &optional result) &body body)
> "The analog of DOLIST for any collection COLL,
> which can be put in a seq.
>
> VAR-FORM can be either ATOM, in which case this name
> is bound to the value (1st), returned by NXT, or LIST:
> the 1st symbol will be bound to the 1st value (value),
> returned by NXT, and the 2nd -- to the 2nd (key).
> If RESULT form is provided, it's value will be returned"
> (with-gensyms (gseq key val)
> `(let ((,gseq (seq ,coll)))
> (loop
> (multiple-value-bind (,val ,key) (nxt ,gseq)
> (multiple-value-bind ,(mklist var-form)
> (values ,val ,key)
> (if ,key (progn ,@body)
> (return ,result))))))))
>
> (defmacro with-acc
> ((var-form acc-name coll &optional result-type)
> &body body)
> "Iterate over COLL with accumulation to list and
> conversion into either RESULT-TYPE or type-of COLL.
>
> VAR-FORM can be either ATOM, in which case this name
> is bound to the value (1st), returned by NXT, or LIST:
> the 1st symbol will be bound to the 1st value (value),
> returned by NXT, and the 2nd -- to the 2nd (key)."
> (with-gensyms (gseq)
> `(let ((,gseq (seq ,coll)))
> (into (or ,result-type (seq-ref ,gseq))
> (with-output-to-list (,acc-name)
> (doseq (,var-form ,gseq)
> ,@body))))))
>
> (Where with-gensyms, mklist and with-output-to-list are the common
> utility macros).
>
> You can as well define extensions for ITERATE:
>
> (iter:defmacro-clause (ITER:FOR var ITER:NXT coll)
> "Iterate over COLL as a SEQ"
> (with-gensyms (gseq k v)
> `(progn (iter:with ,gseq := (seq ,coll))
> (iter:for ,var
> :next (multiple-value-bind (,v ,k)
> (nxt ,gseq)
> (if ,k ,v
> (iter:terminate)))))))
>
>
> Examples
> --------
> Using range:
>
> (defclass range ()
> ((start :initarg :start :reader range-start :initform 0)
> (end :initarg :end :reader range-end)
> (step :initarg :step :reader range-step :initform 1)))
>
> (defun range (start &key end step)
> (make-instance 'range :start start :end end :step step))
>
> (defmethod seq ((coll range) &optional (start-pos 0))
> (make-instance 'seq :ref coll :pos start-pos
> :itr #`(with-slots (step end) coll
> (let ((rez (+ start-pos (* _ step))))
> (and (or (not end) (<= rez end))
> (values rez
> _))))))
>
> CL-USER> (with-acc (v rez (range 0 :step 2 :end 10) 'vector)
> (push v rez))
> #(0 2 4 6 8 10)
>
> Implementing generic FILTER.
> Here I faced the problem with iteration over two different kinds of
> collections: with meaningful keys, that should be preserved (hash-
> tables), and with, let's say, implicit keys (ordinary sequences, for
> which we can say, that key is a number). There are 2 ways to treat
> them: either to indicate explicitly, what type of sequence it is, in
> the SEQ class, or to track the list of keys separately and use it in
> situations, wheh it's needed: like creating a hash-table from list,
> which is performed in INTO. After some though I decided, that the
> explicit indication is a much simpler and better way, because keys are
> needed only in small fraction of situations. The usage of the
> indicator can be seen in FILTER implementation (I believe, it's quite
> natural):
>
> (defun filter (fn coll)
> "Sequentially apply FN to all elements of COLL and
> return the collection, consisting of only non-nil results"
> (let ((seq (seq coll)))
> (with-slots (ref kv?) seq
> (with-acc ((v k) acc seq)
> (when-it (funcall fn v)
> (when kv?
> (push k acc))
> (push it acc))))))
>
> Althought, the right choice for filter is to define it generic as
> well. The difference in performance between a concrete list FILTER:
>
> (defun filter (fn lst)
> "Sequentially apply FN to all elements of LST and
> return the list, consisting of only non-nil results"
> (let ((acc nil))
> (dolist (x lst)
> (let ((val (funcall fn x)))
> (if val (push val acc))))
> (nreverse acc)))
>
> and the generic one can be upto 10-100 times (for small computations,
> like (filter #'oddp '(1 2 3))).
>
>
> P.S.
> ----
> Afterwards I looked in Clojure core.clj source to see, how filter is
> implemented there. Interestingly enough, it doesn't work on maps:
> user=> (filter odd? {:a 1 :b 2})
> java.lang.ClassCastException: clojure.lang.MapEntry cannot be cast to
> java.lang.Number (NO_SOURCE_FILE:0)
> user=> (filter odd? (seq {:a 1 :b 2}))
> java.lang.ClassCastException: clojure.lang.MapEntry cannot be cast to
> java.lang.Number (NO_SOURCE_FILE:0)
>
> and for a Vector argument the result type is List...
On Mar 17, 6:52 am, Vsevolod <········@gmail.com> wrote:
> I thought about implementing a kind of the Clojure-style SEQ protocol
> for iterating over arbitrary collections.
Personally, i prefer Common Lisp-style extensible sequences like those
implemented in SBCL. See this paper for details:
www.doc.gold.ac.uk/~mas01cr/papers/ilc2007/sequences-20070301.pdf ..
or check out the SB-SEQUENCE package in SBCL.
A more specific criticism would be your choice of identifiers.. though
i understand it's supposed to be 'clojure style', there's no need to
get all 'arc' on us :).
Cheers,
drewc
Below is my first take.
>
> I wanted to ask to review the code: maybe there are some things, that
> I missed (like terrible inefficiencies)?
> The design overview is given below. Overall, I didn't find it hard to
> do it, so even less now I understand the premise of Clojure, that it's
> so hard to extend CL in this direction.
>
> Sidenote
> --------
> Not to introduce irrelevant complexity here I use unique function
> names for the operations: FST for FIRST, RST for REST, NXT for POP,
> ELM fot ELT and INTO for COERCE. It is quite possible to shadow the
> bult-ins, but I don't see this step as necessary here. It's more the
> question of taste...
>
> Implemetation
> -------------
> The implementation of the protocol can be found at:http://paste.lisp.org/display/77174#1
> (For reference I show the implementation of methods on concrete
> sequences as well).
>
> The SEQ class is defined as a thin wrapper around collection classes,
> which has a reference to the concrete collection, to the position in
> it and an iterator in collection. Basically, it's all just syntactic
> sugar over iterators.
>
> To use the concrete collection as a seq, just call SEQ with it.
> Afterwards 4 operations are possible:
> * FST, NXT and ELM return 2 values: the value of an item in the
> collection and the corresponding key (for sequence type the key is
> just an item's number). To test for the end of collection check the
> nullity of key (no errors will be signaled for out-of-bounds
> conditions)
> * RST returns the rest of the sequence (lazily)
>
> No CONS (in Clojure meaning)
> ----------------------------
> The main purpose of SEQ is to give the ability to iterate over various
> collections uniformly. But there's no problem of accumulation.
> Accumulation is solved: just use lists (it's the most simple and
> efficient way). It's possible to define the analog of Clojure's CONS
> operation, but we'll need to pay the price of generic dispatch
> (moreover, twice) on each operation. It's much more efficient to pay
> it not more, than once, for the whole accumulation loop. So if you
> want to get the concrete sequence of the same type, as the argument,
> just convert the result to it (with INTO). This pattern can be
> codified with the following macros:
>
> (defmacro doseq
> ((var-form coll &optional result) &body body)
> "The analog of DOLIST for any collection COLL,
> which can be put in a seq.
>
> VAR-FORM can be either ATOM, in which case this name
> is bound to the value (1st), returned by NXT, or LIST:
> the 1st symbol will be bound to the 1st value (value),
> returned by NXT, and the 2nd -- to the 2nd (key).
> If RESULT form is provided, it's value will be returned"
> (with-gensyms (gseq key val)
> `(let ((,gseq (seq ,coll)))
> (loop
> (multiple-value-bind (,val ,key) (nxt ,gseq)
> (multiple-value-bind ,(mklist var-form)
> (values ,val ,key)
> (if ,key (progn ,@body)
> (return ,result))))))))
>
> (defmacro with-acc
> ((var-form acc-name coll &optional result-type)
> &body body)
> "Iterate over COLL with accumulation to list and
> conversion into either RESULT-TYPE or type-of COLL.
>
> VAR-FORM can be either ATOM, in which case this name
> is bound to the value (1st), returned by NXT, or LIST:
> the 1st symbol will be bound to the 1st value (value),
> returned by NXT, and the 2nd -- to the 2nd (key)."
> (with-gensyms (gseq)
> `(let ((,gseq (seq ,coll)))
> (into (or ,result-type (seq-ref ,gseq))
> (with-output-to-list (,acc-name)
> (doseq (,var-form ,gseq)
> ,@body))))))
>
> (Where with-gensyms, mklist and with-output-to-list are the common
> utility macros).
>
> You can as well define extensions for ITERATE:
>
> (iter:defmacro-clause (ITER:FOR var ITER:NXT coll)
> "Iterate over COLL as a SEQ"
> (with-gensyms (gseq k v)
> `(progn (iter:with ,gseq := (seq ,coll))
> (iter:for ,var
> :next (multiple-value-bind (,v ,k)
> (nxt ,gseq)
> (if ,k ,v
> (iter:terminate)))))))
>
> Examples
> --------
> Using range:
>
> (defclass range ()
> ((start :initarg :start :reader range-start :initform 0)
> (end :initarg :end :reader range-end)
> (step :initarg :step :reader range-step :initform 1)))
>
> (defun range (start &key end step)
> (make-instance 'range :start start :end end :step step))
>
> (defmethod seq ((coll range) &optional (start-pos 0))
> (make-instance 'seq :ref coll :pos start-pos
> :itr #`(with-slots (step end) coll
> (let ((rez (+ start-pos (* _ step))))
> (and (or (not end) (<= rez end))
> (values rez
> _))))))
>
> CL-USER> (with-acc (v rez (range 0 :step 2 :end 10) 'vector)
> (push v rez))
> #(0 2 4 6 8 10)
>
> Implementing generic FILTER.
> Here I faced the problem with iteration over two different kinds of
> collections: with meaningful keys, that should be preserved (hash-
> tables), and with, let's say, implicit keys (ordinary sequences, for
> which we can say, that key is a number). There are 2 ways to treat
> them: either to indicate explicitly, what type of sequence it is, in
> the SEQ class, or to track the list of keys separately and use it in
> situations, wheh it's needed: like creating a hash-table from list,
> which is performed in INTO. After some though I decided, that the
> explicit indication is a much simpler and better way, because keys are
> needed only in small fraction of situations. The usage of the
> indicator can be seen in FILTER implementation (I believe, it's quite
> natural):
>
> (defun filter (fn coll)
> "Sequentially apply FN to all elements of COLL and
> return the collection, consisting of only non-nil results"
> (let ((seq (seq coll)))
> (with-slots (ref kv?) seq
> (with-acc ((v k) acc seq)
> (when-it (funcall fn v)
> (when kv?
> (push k acc))
> (push it acc))))))
>
> Althought, the right choice for filter is to define it generic as
> well. The difference in performance between a concrete list FILTER:
>
> (defun filter (fn lst)
> "Sequentially apply FN to all elements of LST and
> return the list, consisting of only non-nil results"
> (let ((acc nil))
> (dolist (x lst)
> (let ((val (funcall fn x)))
> (if val (push val acc))))
> (nreverse acc)))
>
> and the generic one can be upto 10-100 times (for small computations,
> like (filter #'oddp '(1 2 3))).
>
> P.S.
> ----
> Afterwards I looked in Clojure core.clj source to see, how filter is
> implemented there. Interestingly enough, it doesn't work on maps:
> user=> (filter odd? {:a 1 :b 2})
> java.lang.ClassCastException: clojure.lang.MapEntry cannot be cast to
> java.lang.Number (NO_SOURCE_FILE:0)
> user=> (filter odd? (seq {:a 1 :b 2}))
> java.lang.ClassCastException: clojure.lang.MapEntry cannot be cast to
> java.lang.Number (NO_SOURCE_FILE:0)
>
> and for a Vector argument the result type is List...
On Mar 18, 12:55 am, Drew Crampsie <·············@gmail.com> wrote:
> On Mar 17, 6:52 am, Vsevolod <········@gmail.com> wrote:
>
> > I thought about implementing a kind of the Clojure-style SEQ protocol
> > for iterating over arbitrary collections.
>
> Personally, i prefer Common Lisp-style extensible sequences like those
> implemented in SBCL. See this paper for details:www.doc.gold.ac.uk/~mas01cr/papers/ilc2007/sequences-20070301.pdf..
> or check out the SB-SEQUENCE package in SBCL.
Thanks for the hint. Never heard of them, so I'll check them out.
> A more specific criticism would be your choice of identifiers.. though
> i understand it's supposed to be 'clojure style', there's no need to
> get all 'arc' on us :).
You can view it as a pun on Arc... :)
Surely, the names are quite arbitrary. Used just for the purpose of
this example.
Cheers,
Vsevolod
Vsevolod wrote:
> I thought about implementing a kind of the Clojure-style SEQ protocol
> for iterating over arbitrary collections. Below is my first take.
I've thought off and on about doing something similar.
For Clojure, its a no-brainer to implement iterator-based containers;
that's a major selling point for native Java interop. CL doesn't get
this environmental benefit from iterators.
The key benefit to iterator-based algorithms is "plug-and-play"
generic functions. Write a container to the API, get useful
algorithms for free. Write an algorithm, use it with all your containers.
That works fairly well for functions like MAP* which simply traverse
the container once from beginning to end. When adding in functions
like FIND, things break down fast.
find x in a list: iterators are great
find x in an array: again no problem (unless the array was sorted...)
find x in a hashtable: traversal is bad
...
Then you start hitting issues like forward, backward, bidirectional,
and random-access iterators... IMHO, all the complexity and special
cases reveal a fundamental oversimplification in the iterator idea.
Don't get me wrong, iterator-based algorithms are good for any
language; they provide a generic API that is great for implementing
new containers and algorithms; but I don't think they should be the
primary algorithmic implementation.
Instead, things should probably look more like
(defgeneric find (item container))
(defmethod find (item container)
"default/reference iterator implementation"
(find-iterators item container))
(defmethod find (item (container array))
(find-array item container))
(defmethod find (item (container hash-table))
(find-hash-table item container))
etc.
Yeah, a generic dispatch burns a little time; but its an O(1) hit that
is easily regained by selecting the optimal algorithm for the
container; and the specialized functions are readily available.
Later,
Daniel
On Mar 18, 2:56 am, D Herring <········@at.tentpost.dot.com> wrote:
> Vsevolod wrote:
> > I thought about implementing a kind of the Clojure-style SEQ protocol
> > for iterating over arbitrary collections. Below is my first take.
>
> I've thought off and on about doing something similar.
>
> For Clojure, its a no-brainer to implement iterator-based containers;
> that's a major selling point for native Java interop. CL doesn't get
> this environmental benefit from iterators.
>
> The key benefit to iterator-based algorithms is "plug-and-play"
> generic functions. Write a container to the API, get useful
> algorithms for free. Write an algorithm, use it with all your containers.
>
> That works fairly well for functions like MAP* which simply traverse
> the container once from beginning to end. When adding in functions
> like FIND, things break down fast.
>
> find x in a list: iterators are great
> find x in an array: again no problem (unless the array was sorted...)
> find x in a hashtable: traversal is bad
> ...
>
> Then you start hitting issues like forward, backward, bidirectional,
> and random-access iterators... IMHO, all the complexity and special
> cases reveal a fundamental oversimplification in the iterator idea.
>
> Don't get me wrong, iterator-based algorithms are good for any
> language; they provide a generic API that is great for implementing
> new containers and algorithms; but I don't think they should be the
> primary algorithmic implementation.
>
> Instead, things should probably look more like
>
> (defgeneric find (item container))
> (defmethod find (item container)
> "default/reference iterator implementation"
> (find-iterators item container))
> (defmethod find (item (container array))
> (find-array item container))
> (defmethod find (item (container hash-table))
> (find-hash-table item container))
I agree (and I used the same approach here to some extent).
And I think, it's possible to provide both: SEQ for quick-&-dirty
hacks, so to say, and a possibility to tailor specialized methods for
each container is always there (just don't forget to define the
functions generic...)
Vsevolod
From: Javier
Subject: Re: Reinventing the iterator
Date:
Message-ID: <gpp8j8$uhl$1@aioe.org>
Vsevolod escribi�:
> I thought about implementing a kind of the Clojure-style SEQ protocol
> for iterating over arbitrary collections. Below is my first take.
Everybody is trying to reinvent Clojure things for CL. I think to
myself: wouldn't it just better to use Clojure?
On Mar 18, 12:37 am, Javier <·······@gmail.com> wrote:
> Everybody is trying to reinvent Clojure things for CL. I think to
> myself: wouldn't it just better to use Clojure?
There are at least two reasons to do it in CL:
1. Clojure proponents state, that it has such and such benefits over
CL (which include generic sequences) and that CL wouldn't allow for
such kinds of things.
But when you try to implement some of those features yourself, you
see, that they are actually quite possible in CL. And having some as a
utility package might be beneficial to the language users (maybe
nobody used them, just because didn't thought in that direction -- not
beacuse the language doesn't support them).
In general, language progress not always happens by switching between
languages, but also by incorporating good ideas from other languages.
Clojure has some great ideas. And CL is one of those adaptable
languages, that do not need to wait for the desire of a BDFL (be it
one person or a company) or other external factors to implement
something: you can do it yourself and it will be usable on par with
other language features.
2. Implementing such general-purpose utilities teaches you a lot about
the language.
And as a sidenote: can you go the opposite way from Clojure? Is it
possible to implement in it something, for which it was not designed
initially. Like :around methods?..
Cheers,
Vsevolod
From: Javier
Subject: Re: Reinventing the iterator - Clojure
Date:
Message-ID: <gpqgq0$vb3$1@aioe.org>
Vsevolod escribi�:
> On Mar 18, 12:37 am, Javier <·······@gmail.com> wrote:
>> Everybody is trying to reinvent Clojure things for CL. I think to
>> myself: wouldn't it just better to use Clojure?
>
> There are at least two reasons to do it in CL:
> 1. Clojure proponents state, that it has such and such benefits over
> CL (which include generic sequences) and that CL wouldn't allow for
> such kinds of things.
> But when you try to implement some of those features yourself, you
> see, that they are actually quite possible in CL. And having some as a
> utility package might be beneficial to the language users (maybe
> nobody used them, just because didn't thought in that direction -- not
> beacuse the language doesn't support them).
> In general, language progress not always happens by switching between
> languages, but also by incorporating good ideas from other languages.
> Clojure has some great ideas. And CL is one of those adaptable
> languages, that do not need to wait for the desire of a BDFL (be it
> one person or a company) or other external factors to implement
> something: you can do it yourself and it will be usable on par with
> other language features.
> 2. Implementing such general-purpose utilities teaches you a lot about
> the language.
>
> And as a sidenote: can you go the opposite way from Clojure? Is it
> possible to implement in it something, for which it was not designed
> initially. Like :around methods?..
>
> Cheers,
> Vsevolod
The problem about you theory is that, in some way, adding the Clojure's
features to CL, is fighting against CL itself.
The main problem about CL is that the standard is fixed. Everything
around the standard is just eclipsed by the standard itself.
For example, you can't easily make vector types to be first class
citiciens in CL, as it is in Clojure, as you may need to rewrite a
significant part of CL for doing so.
Have a look:
http://blip.tv/file/get/Richhickey-ClojureForLispProgrammersPart1997.mov
http://blip.tv/file/get/Richhickey-ClojureForLispProgrammersPart2299.mov
On Mar 18, 12:04 pm, Javier <·······@gmail.com> wrote:
> The problem about you theory is that, in some way, adding the Clojure's
> features to CL, is fighting against CL itself.
Not at all. I use a lot of CL's facilities in my implementation. The
only issue I may appear to be fighting with is the choice of names.
But I don't think it's a problem at all. Pick any you like (even the
standard CL ones. But why would you do that, if you can call you
functions NEXT, HEAD, TAIL etc?) You can even define aliases (which
will be indistinguishable in usage): e.g. short and long versions for
people with different preferences.
> The main problem about CL is that the standard is fixed. Everything
> around the standard is just eclipsed by the standard itself.
It is one of it's main benefits. Because you know, what you are
dealing with and can build on top of it. Look, ITERATE was initially
created in 1989, SERIES even earlier. And they work now 20! years
later.
> For example, you can't easily make vector types to be first class
> citiciens in CL, as it is in Clojure, as you may need to rewrite a
> significant part of CL for doing so.
What do you mean by first-class? What's second class about vectors in
CL? You can use them anywhere you can use lists, except for source
code (however, I think it's possible to make such an extension), they
have a read syntax and you can add other cases, they have a powerful
API (both as concrete vectors and as sequences). What more do you
need?
And some words about Clojure. Clojure doesn't have any standard or
even a spec. It's just that file core.clj. What is the chance, that in
2-5 years 30% of it will change significantly (like recently with lazy-
cons)? I think it's quite high. So who in the right mind will base an
effort to develop any large-scale system (with say a development time
frame of 1-2 years) on top of Clojure? Would you? Yes, it's good for
hacking and scripts, but it can't be compare to CL in the aspect of
standard. And you say, that you can freely change the Clojure core?
Maybe you could provide at least one example, when such user input was
accepted? Or you mean create MyClojure fork? Well, you can do it with
SBCL as well... ;)
Finally, CL is just the 25 special operators. This is what's fixed.
Everything else can actually be redefined (just, there's no point in
doing it in many cases). Can you draw such a distinction in Clojure?
I'd say, that at least the whole core.clj is a list of fixed (in the
sense of arbitrary, but not constant) decisions...
Best regards,
Vsevolod
>
> Have a look:
>
> http://blip.tv/file/get/Richhickey-ClojureForLispProgrammersPart1997.movhttp://blip.tv/file/get/Richhickey-ClojureForLispProgrammersPart2299.mov
From: Javier
Subject: Re: Reinventing the iterator - Clojure
Date:
Message-ID: <gprapv$n8a$1@aioe.org>
Vsevolod escribi�:
> On Mar 18, 12:04 pm, Javier <·······@gmail.com> wrote:
>> The problem about you theory is that, in some way, adding the Clojure's
>> features to CL, is fighting against CL itself.
>
> Not at all. I use a lot of CL's facilities in my implementation. The
> only issue I may appear to be fighting with is the choice of names.
> But I don't think it's a problem at all. Pick any you like (even the
> standard CL ones. But why would you do that, if you can call you
> functions NEXT, HEAD, TAIL etc?) You can even define aliases (which
> will be indistinguishable in usage): e.g. short and long versions for
> people with different preferences.
>
>> The main problem about CL is that the standard is fixed. Everything
>> around the standard is just eclipsed by the standard itself.
>
> It is one of it's main benefits. Because you know, what you are
> dealing with and can build on top of it. Look, ITERATE was initially
> created in 1989, SERIES even earlier. And they work now 20! years
> later.
>
>> For example, you can't easily make vector types to be first class
>> citiciens in CL, as it is in Clojure, as you may need to rewrite a
>> significant part of CL for doing so.
>
> What do you mean by first-class? What's second class about vectors in
> CL?
Rich is explaining much better than me. Look at the Clojure screencasts.
Anyway, there is a good proof: take a function that takes and processes
lists/conses arguments, and now pass a vector to it. While in Clojure
the function is most likely to work (with exceptions), in CL it will
fail, unless you do the adaption or convert its arguments to lists.
> You can use them anywhere you can use lists, except for source
> code (however, I think it's possible to make such an extension),
Yeah, but you are again fighting against CL...
> they
> have a read syntax and you can add other cases, they have a powerful
> API (both as concrete vectors and as sequences). What more do you
> need?
>
> And some words about Clojure. Clojure doesn't have any standard or
> even a spec. It's just that file core.clj. What is the chance, that in
> 2-5 years 30% of it will change significantly (like recently with lazy-
> cons)? I think it's quite high. So who in the right mind will base an
> effort to develop any large-scale system (with say a development time
> frame of 1-2 years) on top of Clojure? Would you? Yes, it's good for
> hacking and scripts, but it can't be compare to CL in the aspect of
> standard. And you say, that you can freely change the Clojure core?
> Maybe you could provide at least one example, when such user input was
> accepted? Or you mean create MyClojure fork? Well, you can do it with
> SBCL as well... ;)
If your CL program is dependent on network, threads, external code, you
have the same problem, as you must use the tools of your specific
implementation.
Anyway, technology changes everyday. The Java standard itself is
changing every 2 years. Python is changing. Ruby, Haskell, Scheme, too.
Not to talk about Perl... Even C changes at times. And people are
constructing large-scale systems on those languages... so I don't see
the reason to not to do the same in Clojure. Even, the source code of
Clojure is at your disposal, so if you need something really specific,
you can always modify it.
If fact, it seems that the CL standard is the only one that doesn't
change from its arising... ;)
> Finally, CL is just the 25 special operators. This is what's fixed.
> Everything else can actually be redefined (just, there's no point in
> doing it in many cases). Can you draw such a distinction in Clojure?
> I'd say, that at least the whole core.clj is a list of fixed (in the
> sense of arbitrary, but not constant) decisions...
This is funny... I have that impression too (arbitrarily), but not about
Clojure, but the CL standard...
At least, every feature of Clojure is well known why it has been added.
>
> Best regards,
> Vsevolod
>
>
>> Have a look:
>>
>> http://blip.tv/file/get/Richhickey-ClojureForLispProgrammersPart1997.movhttp://blip.tv/file/get/Richhickey-ClojureForLispProgrammersPart2299.mov
>
On Mar 18, 7:27 pm, Javier <·······@gmail.com> wrote:
> Rich is explaining much better than me. Look at the Clojure screencasts.
I did. See: http://lisp-univ-etc.blogspot.com/2008/10/clojure-for-lisp-programmers-talk.html
> Anyway, there is a good proof: take a function that takes and processes
> lists/conses arguments, and now pass a vector to it. While in Clojure
> the function is most likely to work (with exceptions), in CL it will
> fail, unless you do the adaption or convert its arguments to lists.
If a Clojure function expects lists it won't take vectors. If it
expects seqs, it will. The same with CL functions. It's CS 101 (types)
> If your CL program is dependent on network, threads, external code, you
> have the same problem, as you must use the tools of your specific
> implementation.
That's not a problem, because the change, if it's happening, is
localized. While if you change something at the language core almost
everything else should also be updated.
Btw, you didn't give me an example of user-contributed code to
core.clj.
> Anyway, technology changes everyday.
Technology is in libraries, while in languages there should be
abstractions. How often do you change Euclid's geometry?
> The Java standard itself is
> changing every 2 years. Python is changing. Ruby, Haskell, Scheme, too.
> Not to talk about Perl... Even C changes at times. And people are
> constructing large-scale systems on those languages... so I don't see
> the reason to not to do the same in Clojure. Even, the source code of
> Clojure is at your disposal, so if you need something really specific,
> you can always modify it.
Most of those languages have at least a spec. And when they change,
it's quite predictable and backward compatibility is usually
preserved.
> If fact, it seems that the CL standard is the only one that doesn't
> change from its arising... ;)
Yeah and it's one of the benefits
>
> This is funny... I have that impression too (arbitrarily), but not about
> Clojure, but the CL standard...
If you've programmed anything serious in CL, you would have been
amazed how well thought out the language is...
Vsevolod
Vsevolod schrieb:
> On Mar 18, 12:04 pm, Javier <·······@gmail.com> wrote:
>> For example, you can't easily make vector types to be first class
>> citiciens in CL, as it is in Clojure, as you may need to rewrite a
>> significant part of CL for doing so.
>
> What do you mean by first-class? What's second class about vectors in
> CL? You can use them anywhere you can use lists, except for source
> code (however, I think it's possible to make such an extension), they
> have a read syntax and you can add other cases, they have a powerful
> API (both as concrete vectors and as sequences). What more do you
> need?
They are indeed nice. But when you first lay out your algorithm with
a prototype that uses lists and then want to use vectors instead, you
find yourself having to rewrite several parts of your program.
first/rest don't work so well and consing elements to a vector can be
problematic too.
The reader syntax is indeed nice, but I don't understand why it is so
rarely used.
> And some words about Clojure. Clojure doesn't have any standard or
> even a spec.
This means it comes with all advantages and disadvantages of not having
one.
> It's just that file core.clj.
Well, this is not true.
But even if it would be the case, in principle everything could be just
one file.
> What is the chance, that in
> 2-5 years 30% of it will change significantly (like recently with lazy-
> cons)?
Like the real world, it will most likely change.
But it seems also likely that todays functionality will stay pretty stable.
> So who in the right mind will base an
> effort to develop any large-scale system (with say a development time
> frame of 1-2 years) on top of Clojure? Would you?
Yes, indeed.
Exactly this happens now for me, as well as for some other companies.
Nearly all changes are improvements and additions of features. Possible
that still some breaking changes will occur, but this will cost us 10
days of fixing in the coming 1,5 years. It's okay, because it pays back
much more value. And again, mostly it's the addition of new stuff that
happens.
> Yes, it's good for
> hacking and scripts, but it can't be compare to CL in the aspect of
> standard.
Have you done some months of Clojure development to reach this conclusion?
> And you say, that you can freely change the Clojure core?
> Maybe you could provide at least one example, when such user input was
> accepted?
For example condp.
And several patches of users.
Clojure can happily coexist with CL and I heared there are people who
like both.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
On Mar 23, 2:13 am, André Thieme <address.good.until.
···········@justmail.de> wrote:
> Vsevolod schrieb:
>
> They are indeed nice. But when you first lay out your algorithm with
> a prototype that uses lists and then want to use vectors instead, you
> find yourself having to rewrite several parts of your program.
> first/rest don't work so well and consing elements to a vector can be
> problematic too.
I think, it's good, that consing to a vector is a different operation,
because it indeed has quite different characteristics, that you should
mind, when you use it (for such low-level stuff it's important, I
think).
> This means it comes with all advantages and disadvantages of not having
> one.
Agreed.
> > It's just that file core.clj.
>
> Well, this is not true.
> But even if it would be the case, in principle everything could be just
> one file.
Yes. It's good, that it's one file. What's bad is that there's no
spec, defining that file. And this has it's implications (see, for
example: http://ola-bini.blogspot.com/2007/06/there-can-be-only-one-tale-about-ruby.html
For example, what is a compliant Ruby implementation? Since there
exists no spec, and no comprehensive test suite, the only way to
measure compliance is to check how close the behavior matches MRI. But
this have some problems too. How do you check behavior? Well, you need
to run applications. But how do you get so far as you can run
applications?)
I don't mean, that it's bad for Clojure not to have one. At this stage
it can be acceptable. I just don't understand the comparison with CL
here. Eventually Clojure will be either like CL (have a spec/standard)
or like Perl. And if you consider implementing some substantial system
in some language exclusively, than CL's maturity is definitely a win.
And don't tell me, that you can use the Java platform's maturity,
because you can use it anyway. I see it as a question, whether you are
developing the system in Lisp with possible use of some external
libraries (like Java ones) or in Java with Lisp as a scripting glue.
> Like the real world, it will most likely change.
Why doesn't the Euclidian geometry change then? ;)
>
> > Yes, it's good for
> > hacking and scripts, but it can't be compare to CL in the aspect of
> > standard.
>
> Have you done some months of Clojure development to reach this conclusion?
Of course not. But you don't need to make all the mistakes yourself,
no?
> For example condp.
> And several patches of users.
OK. Thanks for the info. Just I don't think, that Javier could've
provided it :)
> Clojure can happily coexist with CL and I heared there are people who
> like both.
Surely, I like both
Cheers,
Vsevolod
Vsevolod schrieb:
> On Mar 23, 2:13 am, Andr� Thieme <address.good.until.
> ···········@justmail.de> wrote:
>> Vsevolod schrieb:
>>
>> They are indeed nice. But when you first lay out your algorithm with
>> a prototype that uses lists and then want to use vectors instead, you
>> find yourself having to rewrite several parts of your program.
>> first/rest don't work so well and consing elements to a vector can be
>> problematic too.
> I think, it's good, that consing to a vector is a different operation,
> because it indeed has quite different characteristics, that you should
> mind, when you use it (for such low-level stuff it's important, I
> think).
It's of course the right descision to not allowing cons to add elements
to CLs vectors, as they are implemented, as arrays.
I don't know if the Hyperspec asks for this, or if a CL is free to
implement them for example in the Clojure style, where it's very
performant to "add" an element to a vector.
While it makes very much sense to not offer such an expensive operation
straight ahead (adding to a CL vector in the general case could mean
that one needs to make a full copy), it still makes it more difficult to
adopt algorithms (prototyped with lists) now for vectors.
>>> It's just that file core.clj.
>> Well, this is not true.
>> But even if it would be the case, in principle everything could be just
>> one file.
>
> Yes. It's good, that it's one file. What's bad is that there's no
> spec, defining that file.
As I said, this means advantages and disadvantages. I can clearly
understand the position that having a spec can be advantageous, if it is
well done like CLs.
> I don't mean, that it's bad for Clojure not to have one. At this stage
> it can be acceptable.
Right now it seems impossible to have one.
I guess Clojure will never have one. Most languages don't have a defined
one, but get regular updates instead, which would outdate a spec.
>> Like the real world, it will most likely change.
>
> Why doesn't the Euclidian geometry change then? ;)
That part doesn't change right, but it also is not an interesting
problem anymore in todays world.
Intelligent applications begin to raise, new jobs are waiting to be done
and new advancements are needed to improve life quality.
Problems of Euclidian geometry are solved with satisfying deepness.
Now new challenges need to be solved, and constantly evolving software
is a key element to get there, in my opinion.
>> For example condp.
>> And several patches of users.
>
> OK. Thanks for the info. Just I don't think, that Javier could've
> provided it :)
I don't know, until now I have not seen him posting code, or I can't
remember it. Anyway, I suppose he is interested in languages of the Lisp
family.
I am glad that William James now started to actually code Lisp.
He proved that he can jump over his own shadow and do it.
Of course, he will continue to try to provoke people, but at least it is
more on-topic now.
>> Clojure can happily coexist with CL and I heared there are people who
>> like both.
>
> Surely, I like both
Same here. I code both professionally nearly every day.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
On Mar 23, 10:47 pm, André Thieme <address.good.until.
···········@justmail.de> wrote:
> Vsevolod schrieb:
>
> > On Mar 23, 2:13 am, André Thieme <address.good.until.
> > ···········@justmail.de> wrote:
> >> Vsevolod schrieb:
>
> >> They are indeed nice. But when you first lay out your algorithm with
> >> a prototype that uses lists and then want to use vectors instead, you
> >> find yourself having to rewrite several parts of your program.
> >> first/rest don't work so well and consing elements to a vector can be
> >> problematic too.
> > I think, it's good, that consing to a vector is a different operation,
> > because it indeed has quite different characteristics, that you should
> > mind, when you use it (for such low-level stuff it's important, I
> > think).
>
> It's of course the right descision to not allowing cons to add elements
> to CLs vectors, as they are implemented, as arrays.
> I don't know if the Hyperspec asks for this, or if a CL is free to
> implement them for example in the Clojure style, where it's very
> performant to "add" an element to a vector.
VECTOR-PUSH-EXTEND is very perfomant too.
> While it makes very much sense to not offer such an expensive operation
> straight ahead (adding to a CL vector in the general case could mean
> that one needs to make a full copy),
Come on. Using 'add' on a vector potentially implies a compy of O(N)
elements. It is the nature of the beast. Clojure is no better or no
worse than Java or CL or whatever.
> it still makes it more difficult to
> adopt algorithms (prototyped with lists) now for vectors.
But not functions prototyped for SEQUENCE.
>
> >>> It's just that file core.clj.
> >> Well, this is not true.
> >> But even if it would be the case, in principle everything could be just
> >> one file.
>
> > Yes. It's good, that it's one file. What's bad is that there's no
> > spec, defining that file.
>
> As I said, this means advantages and disadvantages. I can clearly
> understand the position that having a spec can be advantageous, if it is
> well done like CLs.
>
> > I don't mean, that it's bad for Clojure not to have one. At this stage
> > it can be acceptable.
>
> Right now it seems impossible to have one.
> I guess Clojure will never have one. Most languages don't have a defined
> one, but get regular updates instead, which would outdate a spec.
>
> >> Like the real world, it will most likely change.
>
> > Why doesn't the Euclidian geometry change then? ;)
>
> That part doesn't change right, but it also is not an interesting
> problem anymore in todays world.
> Intelligent applications begin to raise, new jobs are waiting to be done
> and new advancements are needed to improve life quality.
> Problems of Euclidian geometry are solved with satisfying deepness.
> Now new challenges need to be solved, and constantly evolving software
> is a key element to get there, in my opinion.
>
> >> For example condp.
> >> And several patches of users.
>
> > OK. Thanks for the info. Just I don't think, that Javier could've
> > provided it :)
>
> I don't know, until now I have not seen him posting code, or I can't
> remember it. Anyway, I suppose he is interested in languages of the Lisp
> family.
> I am glad that William James now started to actually code Lisp.
> He proved that he can jump over his own shadow and do it.
Nope. He has not posted a single line fo Common Lisp and he has not
done his homework yet. :)
> Of course, he will continue to try to provoke people, but at least it is
> more on-topic now.
>
> >> Clojure can happily coexist with CL and I heared there are people who
> >> like both.
>
> > Surely, I like both
>
> Same here. I code both professionally nearly every day.
Exactly. But don't get woprked up if some of us are sticking with CL.
Cheers
--
Marco
Marco Antoniotti schrieb:
> On Mar 23, 10:47 pm, Andr� Thieme <address.good.until.
> ···········@justmail.de> wrote:
>> Vsevolod schrieb:
>>
>>> On Mar 23, 2:13 am, Andr� Thieme <address.good.until.
>>> ···········@justmail.de> wrote:
>>>> Vsevolod schrieb:
>>>> They are indeed nice. But when you first lay out your algorithm with
>>>> a prototype that uses lists and then want to use vectors instead, you
>>>> find yourself having to rewrite several parts of your program.
>>>> first/rest don't work so well and consing elements to a vector can be
>>>> problematic too.
>>> I think, it's good, that consing to a vector is a different operation,
>>> because it indeed has quite different characteristics, that you should
>>> mind, when you use it (for such low-level stuff it's important, I
>>> think).
>> It's of course the right descision to not allowing cons to add elements
>> to CLs vectors, as they are implemented, as arrays.
>> I don't know if the Hyperspec asks for this, or if a CL is free to
>> implement them for example in the Clojure style, where it's very
>> performant to "add" an element to a vector.
>
> VECTOR-PUSH-EXTEND is very perfomant too.
Yes. However, it will call adjust-array eventually.
>> While it makes very much sense to not offer such an expensive operation
>> straight ahead (adding to a CL vector in the general case could mean
>> that one needs to make a full copy),
>
> Come on. Using 'add' on a vector potentially implies a compy of O(N)
> elements. It is the nature of the beast. Clojure is no better or no
> worse than Java or CL or whatever.
This has nothing to do with Clojure being "better". That is just an
opinion.
But the thing is, that Clojure vectors are not implemented as arrays
under the hood. So, "adding" elements to a Clojure vector, done
via (conj my-vector new-element), will indeed not imply a copy of the
existing vector.
Of course, this would be true for any language which implements vectors
that way under the hood. For CL (via ABCL) and Java this is already
accessible - they can simply use the Clojure vectors if anyone would
be interested.
These vectors are not the right datastructure for any task. But there
are a lot of jobs for which they come in handy.
> Nope. He has not posted a single line fo Common Lisp and he has not
> done his homework yet. :)
Maybe it was a very very long line of code.
> Exactly. But don't get woprked up if some of us are sticking with CL.
Of course not. It's a perfectly fine choice, and I myself code CL nearly
every day.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
On Mar 26, 2:30 am, André Thieme <address.good.until.
···········@justmail.de> wrote:
> Marco Antoniotti schrieb:
>
>
>
> > On Mar 23, 10:47 pm, André Thieme <address.good.until.
> > ···········@justmail.de> wrote:
> >> Vsevolod schrieb:
>
> >>> On Mar 23, 2:13 am, André Thieme <address.good.until.
> >>> ···········@justmail.de> wrote:
> >>>> Vsevolod schrieb:
> >>>> They are indeed nice. But when you first lay out your algorithm with
> >>>> a prototype that uses lists and then want to use vectors instead, you
> >>>> find yourself having to rewrite several parts of your program.
> >>>> first/rest don't work so well and consing elements to a vector can be
> >>>> problematic too.
> >>> I think, it's good, that consing to a vector is a different operation,
> >>> because it indeed has quite different characteristics, that you should
> >>> mind, when you use it (for such low-level stuff it's important, I
> >>> think).
> >> It's of course the right descision to not allowing cons to add elements
> >> to CLs vectors, as they are implemented, as arrays.
> >> I don't know if the Hyperspec asks for this, or if a CL is free to
> >> implement them for example in the Clojure style, where it's very
> >> performant to "add" an element to a vector.
>
> > VECTOR-PUSH-EXTEND is very perfomant too.
>
> Yes. However, it will call adjust-array eventually.
Depends. You have control over it with the fill-pointer; but this is
nitpicking.
> >> While it makes very much sense to not offer such an expensive operation
> >> straight ahead (adding to a CL vector in the general case could mean
> >> that one needs to make a full copy),
>
> > Come on. Using 'add' on a vector potentially implies a compy of O(N)
> > elements. It is the nature of the beast. Clojure is no better or no
> > worse than Java or CL or whatever.
>
> This has nothing to do with Clojure being "better". That is just an
> opinion.
That's what I understood from you post.
> But the thing is, that Clojure vectors are not implemented as arrays
> under the hood. So, "adding" elements to a Clojure vector, done
> via (conj my-vector new-element), will indeed not imply a copy of the
> existing vector.
Then (as we understood from elsewhere) Clojure vectors are not
vectors, in the sense that they do not support constant time random
access.
The issue, which was masterly addressed by the C++ STL (and not by the
CL ANSI, cfr. the O(N^2) INTERSECTION implementations distributed with
some implementations), is what are the operation characteristics of
the data structure.
By and large, vectors are usually interpreted as data structures
having O(1) random access time and sequential ordering of the indexed
elements. It looks like Clojure implements vectors using some form of
persistent tree structure, which is fine, but then it potentially had
'add' as a logarithmic operation as well as their random access
operation.
> Of course, this would be true for any language which implements vectors
> that way under the hood. For CL (via ABCL) and Java this is already
> accessible - they can simply use the Clojure vectors if anyone would
> be interested.
From what you say, using a persistent (functional) tree structure
masked (as in superhero) as a 'vector' would do it. It isn't that
difficult. Just read Okasaki's. book.
Cheers
--
Marco
From: Javier
Subject: Re: Reinventing the iterator - Clojure
Date:
Message-ID: <gqahe6$ti0$1@aioe.org>
Andr� Thieme escribi�:
>>> For example condp.
>>> And several patches of users.
>>
>> OK. Thanks for the info. Just I don't think, that Javier could've
>> provided it :)
>
> I don't know, until now I have not seen him posting code, or I can't
> remember it. Anyway, I suppose he is interested in languages of the Lisp
> family.
I have posted some CL code over some years. I recently asked for some
Java-like CLOS.
Yes, I'm interested in Lisp like languages, but feel a bit disappointed
about CL, like a lot of people here.
Javier wrote:
> Andr� Thieme escribi�:
>
>>>> For example condp.
>>>> And several patches of users.
>>> OK. Thanks for the info. Just I don't think, that Javier could've
>>> provided it :)
>> I don't know, until now I have not seen him posting code, or I can't
>> remember it. Anyway, I suppose he is interested in languages of the Lisp
>> family.
>
>
> I have posted some CL code over some years. I recently asked for some
> Java-like CLOS.
> Yes, I'm interested in Lisp like languages, but feel a bit disappointed
> about CL, like a lot of people here.
There are enough alternatives out there, you don't have to use Common
Lisp. But it is the case that a lot of people are actually happy with
Common Lisp as it is. So just let them be.
Diversity is good, there is room for many Lisp dialects.
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/
Javier <·······@gmail.com> wrote in ·················@aioe.org:
> I have posted some CL code over some years.
Which was the best?
From: Pascal J. Bourguignon
Subject: Re: Reinventing the iterator - Clojure
Date:
Message-ID: <87ocvqgbap.fsf@galatea.local>
Javier <·······@gmail.com> writes:
> Andr� Thieme escribi�:
>
>>>> For example condp.
>>>> And several patches of users.
>>>
>>> OK. Thanks for the info. Just I don't think, that Javier could've
>>> provided it :)
>>
>> I don't know, until now I have not seen him posting code, or I can't
>> remember it. Anyway, I suppose he is interested in languages of the Lisp
>> family.
>
>
> I have posted some CL code over some years. I recently asked for some
> Java-like CLOS.
> Yes, I'm interested in Lisp like languages, but feel a bit disappointed
> about CL, like a lot of people here.
Well, if you feel disappointed about CL, don't worry, you still have a
lot of choices:
- Scheme (r5rs, r6rs, various implementations of each),
- emacs lisp
- Qi
- Arc
- Lush
- xlisp
- vlisp
- LeLisp
- newLisp
- clojure
- ISLisp (ISO Lisp)
etc...
--
__Pascal Bourguignon__
Javier <·······@gmail.com> writes:
> The problem about you theory is that, in some way, adding the Clojure's
> features to CL, is fighting against CL itself.
>
> The main problem about CL is that the standard is fixed. Everything
> around the standard is just eclipsed by the standard itself.
> For example, you can't easily make vector types to be first class
> citiciens in CL, as it is in Clojure, as you may need to rewrite a
> significant part of CL for doing so.
You are plain wrong.
That's the power of Lisp, having such a trivial syntax, that there is
no syntactic difference between a special operator, a macro and a
function, and absolutely no difference between an operator from the
COMMON-LISP package and an operator from another user defined package.
That's something that you won't find in any other programming
language, and that's the reason why it is possible, and it is
routinely done, to incorporate in CL systems the features of any other
programming language.
We can see you tremble on your feet, indeed, you may fear the power of CL!
There's no reason why the functions defined in CL have to process the
user defined data types. They are defined to work on the CL defined
types and that's well enough. If you defined your own data types, you
will define your own functions.
If you need some generic functions able to work with predefined types
in addititon to your own, nothing prevents you do to so. You may
define a MY-SEQ:FIND function that takes your own MY-SEQ:SEQUENCE data
type in addition to CL:VECTOR an CL:LIST. But it would come to nobody
sane mind to complain that MY-SEQ:SEQUENCE doesn't handle
PJB:CONTAINER objects.
--
__Pascal Bourguignon__
Pascal J. Bourguignon schrieb:
> If you need some generic functions able to work with predefined types
> in addititon to your own, nothing prevents you do to so. You may
> define a MY-SEQ:FIND function that takes your own MY-SEQ:SEQUENCE data
> type in addition to CL:VECTOR an CL:LIST. But it would come to nobody
> sane mind to complain that MY-SEQ:SEQUENCE doesn't handle
> PJB:CONTAINER objects.
Well, I would.
But maybe I am just not sane :)
The same what you wrote in your previous post is true for any serious
Lisp, not just for CL.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
On Mar 18, 12:04 pm, Javier <·······@gmail.com> wrote:
> The problem about you theory is that, in some way, adding the Clojure's
> features to CL, is fighting against CL itself.
On the contrary, I embrace it. (And if you don't see it, you either
didn't bother to look at the code or just are a fool, sorry).
All of the available sequence functions are not discarded, but put to
work. Multiple-values (which are not available in Clojure) are used to
gracefully handle sequence keys. CLOS and generic functions (with
multiple dispatch) make the facility fully extensible. And so on.
Overall, I just add another abstraction layer on top of CL:
first there're lists, then sequences, then seqs:
car - first - fst
cdr - subseq - rst
nth - elt - elm
Vsevolod
Javier wrote:
> Vsevolod escribi�:
>> On Mar 18, 12:37 am, Javier <·······@gmail.com> wrote:
>>> Everybody is trying to reinvent Clojure things for CL. I think to
>>> myself: wouldn't it just better to use Clojure?
>> There are at least two reasons to do it in CL:
>> 1. Clojure proponents state, that it has such and such benefits over
>> CL (which include generic sequences) and that CL wouldn't allow for
>> such kinds of things.
>> But when you try to implement some of those features yourself, you
>> see, that they are actually quite possible in CL. And having some as a
>> utility package might be beneficial to the language users (maybe
>> nobody used them, just because didn't thought in that direction -- not
>> beacuse the language doesn't support them).
>> In general, language progress not always happens by switching between
>> languages, but also by incorporating good ideas from other languages.
>> Clojure has some great ideas. And CL is one of those adaptable
>> languages, that do not need to wait for the desire of a BDFL (be it
>> one person or a company) or other external factors to implement
>> something: you can do it yourself and it will be usable on par with
>> other language features.
>> 2. Implementing such general-purpose utilities teaches you a lot about
>> the language.
>>
>> And as a sidenote: can you go the opposite way from Clojure? Is it
>> possible to implement in it something, for which it was not designed
>> initially. Like :around methods?..
>>
>> Cheers,
>> Vsevolod
>
> The problem about you theory is that, in some way, adding the Clojure's
> features to CL, is fighting against CL itself.
>
> The main problem about CL is that the standard is fixed. Everything
> around the standard is just eclipsed by the standard itself.
> For example, you can't easily make vector types to be first class
> citiciens in CL, as it is in Clojure, as you may need to rewrite a
> significant part of CL for doing so.
As far as I can tell, Rich Hickey also had to rewrite a significant part
of a Lisp dialect to get his extensions to work. Actually more than you
would have to in an existing Lisp dialect.
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/
From: Javier
Subject: Re: Reinventing the iterator - Clojure
Date:
Message-ID: <gpr7eh$jsm$1@aioe.org>
Pascal Costanza escribi�:
>> The main problem about CL is that the standard is fixed. Everything
>> around the standard is just eclipsed by the standard itself.
>> For example, you can't easily make vector types to be first class
>> citiciens in CL, as it is in Clojure, as you may need to rewrite a
>> significant part of CL for doing so.
>
> As far as I can tell, Rich Hickey also had to rewrite a significant part
> of a Lisp dialect to get his extensions to work. Actually more than you
> would have to in an existing Lisp dialect.
Really?
Anyway you can clearly distinguish Clojure from whatever dialect you are
talking about. So much that it is a complete new language.
The good point is that Clojure is already packaged, tested, optimized.
You don't have to do any effort on modifying CL.
On Mar 18, 12:30 pm, Javier <·······@gmail.com> wrote:
> The good point is that Clojure is already packaged, tested, optimized.
clojure is optimized for correctness in concurrency, *not* for
performance.
for example, here is the same array based prime sieve algorithm in
both common lisp and clojure. the common lisp version is completely
unoptimized - no declarations at all, even though the :element-type
and various other variables could be declared fixnum. the common lisp
version runs about 10x faster than the clojure version on the same
machine.
(defun array-primes (limit)
(let ((prime-vector (make-array limit))
(factor-limit (isqrt limit)))
(loop for vector-index from 0 to (1- limit)
do (setf (aref prime-vector vector-index) (1+ vector-index)))
(setf (aref prime-vector 0) 0) ;; 1 is not prime
(loop for outer-index from 2 to factor-limit
do (when (plusp (aref prime-vector (1- outer-index)))
(loop for inner-index from outer-index until (> (* outer-
index inner-index) limit)
do (setf (aref prime-vector (1- (* outer-index inner-
index))) 0))))
(coerce (delete 0 prime-vector) 'list)))
(defn array-primes [limit]
(let [primes-array (make-array (. Integer TYPE) limit)
factor-limit (int (Math/sqrt limit))]
(loop [aidx 0]
(if (= aidx limit) nil
(do (aset-int primes-array aidx (inc aidx))
(recur (inc aidx)))))
(aset primes-array 0 0) ;; 1 is not prime
(loop [outer-index 2]
(if (> outer-index factor-limit)
(filter pos? primes-array)
(do
(when (pos? (aget primes-array (dec outer-index)))
(loop [inner-index outer-index]
(if (> (* outer-index inner-index) limit)
nil
(do
(aset-int primes-array (dec (* outer-index inner-index)) 0)
(recur (inc inner-index))))))
(recur (inc outer-index)))))))
Raffael Cavallaro schrieb:
> On Mar 18, 12:30 pm, Javier <·······@gmail.com> wrote:
>
>> The good point is that Clojure is already packaged, tested, optimized.
>
> clojure is optimized for correctness in concurrency, *not* for
> performance.
Hmm, I think making Clojure concurrency ready had a higher priority than
making it fast. But Rich put a lot of effort into the core data
structures, and they are fast in a concurrent environment, and not
really bad for serial tasks.
> for example, here is the same array based prime sieve algorithm in
> both common lisp and clojure. the common lisp version is completely
> unoptimized - no declarations at all, even though the :element-type
> and various other variables could be declared fixnum. the common lisp
> version runs about 10x faster than the clojure version on the same
> machine.
Do you see that this has to do with Clojure having not been optimized?
I did not study your code deeply, but I think we hit the "tagged numbers
issue" for the JVM.
> (defun array-primes (limit)
> (let ((prime-vector (make-array limit))
> (factor-limit (isqrt limit)))
> (loop for vector-index from 0 to (1- limit)
> do (setf (aref prime-vector vector-index) (1+ vector-index)))
> (setf (aref prime-vector 0) 0) ;; 1 is not prime
> (loop for outer-index from 2 to factor-limit
> do (when (plusp (aref prime-vector (1- outer-index)))
> (loop for inner-index from outer-index until (> (* outer-
> index inner-index) limit)
> do (setf (aref prime-vector (1- (* outer-index inner-
> index))) 0))))
> (coerce (delete 0 prime-vector) 'list)))
>
>
>
> (defn array-primes [limit]
> (let [primes-array (make-array (. Integer TYPE) limit)
> factor-limit (int (Math/sqrt limit))]
> (loop [aidx 0]
> (if (= aidx limit) nil
> (do (aset-int primes-array aidx (inc aidx))
> (recur (inc aidx)))))
> (aset primes-array 0 0) ;; 1 is not prime
> (loop [outer-index 2]
> (if (> outer-index factor-limit)
> (filter pos? primes-array)
> (do
> (when (pos? (aget primes-array (dec outer-index)))
> (loop [inner-index outer-index]
> (if (> (* outer-index inner-index) limit)
> nil
> (do
> (aset-int primes-array (dec (* outer-index inner-index)) 0)
> (recur (inc inner-index))))))
> (recur (inc outer-index)))))))
I didn't look into making it run faster, but with some cleanups it is
more readable:
(defn array-primes [limit]
(let [primes-array (int-array (conj (range 2 (inc limit)) 0))
factor-limit (inc (int (Math/sqrt limit)))]
(doseq [outer-index (range 2 factor-limit)]
(when (pos? (aget primes-array (dec outer-index)))
(doseq [i (range outer-index (inc (/ limit outer-index)))]
(aset-int primes-array (dec (* i outer-index)) 0))))
(filter pos? primes-array)))
This eliminates some noise, such as
(loop [aidx 0]
(if (= aidx limit) nil
(do (aset-int primes-array aidx (inc aidx))
(recur (inc aidx)))))
which is not better than
(dotimes [i limit] (aset-int primes-array i (inc i)))
But as you see, I removed that part completely and just put the right
values directly into the primes-array.
A rule of thumb: in most cases a Clojure program should be shorter than
its CL equivalent.
On my system your CL code needs 43% more runtime in clisp than in
Clojure. At a first glimpse I suppose this inner loop is one part where
Clojure gets slowed down. The inner loop runs more often than limit
times as it seems. And I suspect that there are still boxed numbers in
use. Java still does not support the nice trick of tagging numbers,
which sbcl (I think) can do.
Have a look at this thread:
http://groups.google.com/group/comp.lang.functional/browse_frm/thread/99b8230c078d9b44
It shows how a Clojure program can run with +/- the efficiency of its
F# equivalent. With some few changes one can parallelize the Clojure
code, and it will run extremly well on a Quadcore or Dual-Quadcore.
At first Clojure started out with about 250 seconds of runtime, while
F# only took around 2,5 seconds. In a later version Clojure caught up
to a bit more than those 2,5 seconds runtime. The thread I linked shows
some results.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
On Mar 18, 7:34 pm, André Thieme <address.good.until.
···········@justmail.de> wrote:
> A rule of thumb: in most cases a Clojure program should be shorter than
> its CL equivalent.
Which reveals what we already know from your past Clojure-CL
comparisons: that you think of either language as a
non-extensible thing that you script towards an end. Which
is to say: for you, Lisp is dead. Please update your sig.
On Mar 18, 8:34 pm, André Thieme <address.good.until.
···········@justmail.de> wrote:
> On my system your CL code needs 43% more runtime in clisp than in
> Clojure.
clisp? really? you're joking right?
compare it to openmcl, or sbcl, or lispworks. IOW, compare it to a
common lisp implementation that doesn't generate the slowest compiled
code.
in sbcl this:
(time (progn (array-primes 6000000) nil))
takes .6 seconds
in clojure the equivalent:
(time (do (array-primes 6000000) nil))
takes 6 seconds. So 10x as long.
WRT to your prettification of my code, I'm aware of the idiomatic
clojure forms. I replaced them with loop/recur because doing so
decreased the run time and I didn't want to use idiomatic, but slow
clojure.
On Mar 18, 11:50 pm, Raffael Cavallaro <················@gmail.com>
wrote:
> in sbcl this:
>
> (time (progn (array-primes 6000000) nil))
>
> takes .6 seconds
>
> in clojure the equivalent:
>
> (time (do (array-primes 6000000) nil))
>
> takes 6 seconds. So 10x as long.
just to be 100% clear, I'm not cherry picking here; it takes .7
seconds under 32-bit intel lispworks, and .6 seconds under 64-bit
openmcl, and .8 seconds under 32-bit openmcl.
and heaven forfend you should want a particular value; walking the
list to the 100000th item takes less than a second under openmcl,
sbcl, or lispworks, but more than two full minutes under clojure:
openmcl:
? (time (nth 100000 (primes 6000000)))
(NTH 100000 (PRIMES 6000000)) took 728,280 microseconds (0.728280
seconds) to run
with 2 available CPU cores.
During that period, 692,335 microseconds (0.692335 seconds) were spent
in user mode
34,080 microseconds (0.034080 seconds) were spent
in system mode
147,555 microseconds (0.147555 seconds) was spent in GC.
58,658,659 bytes of memory allocated.
0 minor page faults, 6,300 major page faults, 0 swaps.
1299721
?
clojure:
user=> (time (nth (primes 6000000) 100000))
"Elapsed time: 130640.211 msecs"
1299721
user=>
Raffael Cavallaro schrieb:
> and heaven forfend you should want a particular value; walking the
> list to the 100000th item takes less than a second under openmcl,
> sbcl, or lispworks, but more than two full minutes under clojure:
Mama mia, that is really way too long.
That means traversing around 800 array cells per second. Not
acceptable for anything faster than an Amiga 500.
> openmcl:
>
> ? (time (nth 100000 (primes 6000000)))
> (NTH 100000 (PRIMES 6000000)) took 728,280 microseconds (0.728280
> seconds) to run
> with 2 available CPU cores.
> During that period, 692,335 microseconds (0.692335 seconds) were spent
> in user mode
> 34,080 microseconds (0.034080 seconds) were spent
> in system mode
> 147,555 microseconds (0.147555 seconds) was spent in GC.
> 58,658,659 bytes of memory allocated.
> 0 minor page faults, 6,300 major page faults, 0 swaps.
> 1299721
> ?
If you do this timing a few times in a row, will the timing be stable,
around 730 msecs?
> clojure:
>
>
> user=> (time (nth (primes 6000000) 100000))
> "Elapsed time: 130640.211 msecs"
> 1299721
> user=>
I suppose that primes is the earlier defined array-primes?
On my system I get very different timings.
I tried this function:
(defn array-primes [limit]
(let [primes-array (int-array (conj (range 2 (inc limit)) 0))
factor-limit (inc (int (Math/sqrt limit)))]
(doseq [outer-index (range 2 factor-limit)]
(when (pos? (aget primes-array (dec outer-index)))
(doseq [i (range outer-index (inc (/ limit outer-index)))]
(aset-int primes-array (dec (* i outer-index)) 0))))
(filter pos? primes-array)))
user> (time (def x (array-primes 6000000)))
"Elapsed time: 2685.973637 msecs"
#'user/x
user> (time (nth x 100000))
"Elapsed time: 21.058752 msecs"
1299721
user> (time (nth (array-primes 6000000) 100000))
"Elapsed time: 2774.845686 msecs"
1299721
When I use your version with the loops and optimize it a little,
and if I write it in a more idiomatic way (for example: an IF does
not return nil, and the DOs were not needed), then I get this:
(defn array-primes [limit]
(let [primes-array (int-array (conj (range 2 (inc limit)) 0))
factor-limit (int (Math/sqrt limit))
l (int limit)] ; I mark l as an int, for the unchecked *
(loop [outer-index (int 2)]
(when (<= outer-index factor-limit)
(when (pos? (aget primes-array (dec outer-index)))
(loop [inner-index (int outer-index)]
(when (<= (unchecked-multiply outer-index inner-index) l)
(aset-int primes-array (dec (unchecked-multiply
outer-index inner-index)) 0)
(recur (inc inner-index)))))
(recur (inc outer-index))))
(filter pos? primes-array)))
user> (time (nth (array-primes 6000000) 100000))
"Elapsed time: 1720.038944 msecs"
1299721
It is still not as fast as OpenMCL, but we could reduce the factor
100x down to about 2.3x
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
On Mar 21, 3:51 pm, André Thieme
> It is still not as fast as OpenMCL, but we could reduce the factor
> 100x down to about 2.3x
clearly clojure has been patched since I did the original timing
because when I update to 1336 nth no longer takes an absurdly long
time on my machine either.
On Mar 21, 4:52 pm, Raffael Cavallaro <················@gmail.com>
wrote:
> On Mar 21, 3:51 pm, André Thieme
>
> > It is still not as fast as OpenMCL, but we could reduce the factor
> > 100x down to about 2.3x
>
> clearly clojure has been patched since I did the original timing
> because when I update to 1336 nth no longer takes an absurdly long
> time on my machine either.
and when I compare your version using unchecked-multiply with a common
lisp version that is optimized (declaration of types, (optimize (speed
3) (safety 0)... etc.) then I still get a 5x difference. iow, openmcl
is still 5x as fast doing:
(time (nth 100000 (array-primes 6000000)))
as clojure is doing:
(time (nth (array-primes 6000000) 100000))
Raffael Cavallaro schrieb:
> On Mar 21, 4:52 pm, Raffael Cavallaro <················@gmail.com>
> wrote:
>> On Mar 21, 3:51 pm, Andr� Thieme
>>
>>> It is still not as fast as OpenMCL, but we could reduce the factor
>>> 100x down to about 2.3x
>> clearly clojure has been patched since I did the original timing
>> because when I update to 1336 nth no longer takes an absurdly long
>> time on my machine either.
>
> and when I compare your version using unchecked-multiply with a common
> lisp version that is optimized (declaration of types, (optimize (speed
> 3) (safety 0)... etc.) then I still get a 5x difference. iow, openmcl
> is still 5x as fast doing:
>
> (time (nth 100000 (array-primes 6000000)))
>
> as clojure is doing:
>
> (time (nth (array-primes 6000000) 100000))
One possibility that I currently still see is the (by me assumed)
difference in the JVM. I use Java 6 Update 12 on Win XP.
Anyway, thanks for your reports about openmcl.
If I decide to buy a Mac and if sbcl does not perform as good under
OSX as it does under Linux, then it seems that openmcl would be a
very good plattform for my Genetic Programming engine.
Raffael Cavallaro schrieb:
> On Mar 18, 8:34 pm, Andr� Thieme <address.good.until.
> ···········@justmail.de> wrote:
>
>> On my system your CL code needs 43% more runtime in clisp than in
>> Clojure.
>
> clisp? really? you're joking right?
Raffael, clisp is the CL which I had at hand. I was aware that it is
not known for its amazing performance.
But still, for many people clisp generates fast enough code. And at
least for this example Clojure produced even faster output.
> compare it to openmcl, or sbcl, or lispworks. IOW, compare it to a
> common lisp implementation that doesn't generate the slowest compiled
> code.
I compiled it now in sbcl and Lispworks.
> in sbcl this:
>
> (time (progn (array-primes 6000000) nil))
>
> takes .6 seconds
I can confirm your numbers. Your machine is a bit faster, as on my compi
sbcl does it in around 690 msecs.
Lispworks' timing was around 760 msecs.
> in clojure the equivalent:
>
> (time (do (array-primes 6000000) nil))
>
> takes 6 seconds. So 10x as long.
Hmm, did you run it in a -server JVM?
I did, and for me it took "only" 3500 msecs. This is still much slower
than what sbcl did, but also noticeable faster.
> WRT to your prettification of my code, I'm aware of the idiomatic
> clojure forms. I replaced them with loop/recur because doing so
> decreased the run time and I didn't want to use idiomatic, but slow
> clojure.
Okay, maybe in the -client JVM it decreased the run time, I didn't test
that. In the server VM it made no difference. In fact, my version was
even a bit faster, but that came because of
(let [primes-array (int-array (conj (range 2 (inc limit)) 0)) ...)
vs
(loop [aidx 0]
(if (= aidx limit) nil
(do (aset-int primes-array aidx (inc aidx))
(recur (inc aidx)))))
(aset primes-array 0 0) ;; 1 is not prime
...
But with one thing you are right: because the JVM can not do tagged
numbers right now and because I can't type-hint ranges in Clojure,
there is probably no way to speed my version up further.
But I was able to speed up your version. For example by using
unchecked-multiply instead of * in (* outer-index inner-index).
That way I came down to ca. 2,5x runtime of sbcl, which was around
1820 msecs.
This is not very bad anymore, I find. But I still don't see why it
is still much slower than the Java version, which needs about half
the runtime of sbcl.
In the end I would say: if speed is required, one should write that
code directly in Java. It has practically the same size as the sbcl
version. One could simply use that code inside ones Clojure
application. That would not reduce productivity in a noticable way
and produces code that runs faster than the best performing CL.
For hard number crunching this could be the better alternative at
the moment.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
On Mar 21, 6:08 am, André Thieme <address.good.until.
···········@justmail.de> wrote:
> Hmm, did you run it in a -server JVM?
yes
> In the end I would say: if speed is required, one should write that
> code directly in Java.
If I'm using a non-lisp language for all the parts that require speed,
I can just as easily use common lisp as the main language and then
I'll need to recode fewer bits (or none) in java/c/c++/fortran
whatever for speed. This argument works against clojure, not for it.
BTW, you still haven't addressed the 100x difference in nth between
common lisp and clojure.
Raffael Cavallaro schrieb:
> On Mar 21, 6:08 am, Andr� Thieme <address.good.until.
> ···········@justmail.de> wrote:
>
>> Hmm, did you run it in a -server JVM?
>
> yes
I am using Java 6 Update 12, Server VM on a
Intel Core2 Duo E7300 @ 2,66 GHz, 2GB Ram under XP with Servicepack 3.
Maybe you have a different version?
In general it seems your compi is a few percent faster than the one
that I used. Your sbcl takes only 600 msecs while mine is closer to 700.
>> In the end I would say: if speed is required, one should write that
>> code directly in Java.
>
> If I'm using a non-lisp language for all the parts that require speed,
> I can just as easily use common lisp as the main language and then
> I'll need to recode fewer bits (or none) in java/c/c++/fortran
> whatever for speed. This argument works against clojure, not for it.
Well, I can agree on that. I think it would be best if as much code as
possible is written in your favourite lisp dialect, or the one that is
most useful for the problem at hand.
But still most Lisp compilers can't always beat Java or even C. And you
posted this "competition" for a problem that is in my eyes not
representative for the overall run time speed of Clojure. I made some
tests in the past months in more areas, and pretty much always Clojure
outperformed sbcl, or was in the 20% range. And with the ease of writing
concurrent code one can gain even more performance.
This makes of course more sense in real world examples. I think that
Clojures mechanisms will not make a substantial difference for most
problems posted in newsgroups.
So, even if a number crunching problem would be important, then one
could go to Java and write these few lines there. I suggest to ask a
profiler which 1% of the code is too slow and try to rewrite that in
Java. In CL I would face the same situation, and would probably write
the hardcore number crunching parts in C, if nothing else helps.
> BTW, you still haven't addressed the 100x difference in nth between
> common lisp and clojure.
Uh, that sounds odd. Let me try it out. If Clojure should be really
that slow, then I would say you spotted a bug.
Andr�
--
Lisp is not dead. It�s just the URL that has changed:
http://clojure.org/
From: Javier
Subject: Re: Reinventing the iterator - Clojure
Date:
Message-ID: <gq2g54$ut0$1@aioe.org>
Andr� Thieme escribi�:
> In the end I would say: if speed is required, one should write that
> code directly in Java. It has practically the same size as the sbcl
> version. One could simply use that code inside ones Clojure
> application. That would not reduce productivity in a noticable way
> and produces code that runs faster than the best performing CL.
> For hard number crunching this could be the better alternative at
> the moment.
You are telling a CL fan to write Java code?
You don't know what you are saying.... ;)
(And not because writing Java code is bad, but because they are so
mindly closed that they are not going to understand it for sure.)
On Mar 21, 11:42 am, Javier <·······@gmail.com> wrote:
> André Thieme escribió:
>
> > In the end I would say: if speed is required, one should write that
> > code directly in Java. It has practically the same size as the sbcl
> > version. One could simply use that code inside ones Clojure
> > application. That would not reduce productivity in a noticable way
> > and produces code that runs faster than the best performing CL.
> > For hard number crunching this could be the better alternative at
> > the moment.
>
> You are telling a CL fan to write Java code?
> You don't know what you are saying.... ;)
>
> (And not because writing Java code is bad, but because they are so
> mindly closed that they are not going to understand it for sure.)
What part of Java are we not supposed to understand? Some of us have
dug deep into the JNI and friends to be able to understand very well
what Java has to offer.
Moreover, we do understand Java lessons and try to use them properly.
CL-ENUMERATION is a CL rendition of Java Enumeration API. This came
before the new Iterable interface and the Iterator stuff.
Nevertheless it is a IMHABO a good rendition of the same concepts in
CL.
Cheers
--
Marco
From: Javier
Subject: Re: Reinventing the iterator - Clojure
Date:
Message-ID: <gq2puh$76d$1@aioe.org>
Marco Antoniotti escribi�:
> On Mar 21, 11:42 am, Javier <·······@gmail.com> wrote:
>> Andr� Thieme escribi�:
>>
>>> In the end I would say: if speed is required, one should write that
>>> code directly in Java. It has practically the same size as the sbcl
>>> version. One could simply use that code inside ones Clojure
>>> application. That would not reduce productivity in a noticable way
>>> and produces code that runs faster than the best performing CL.
>>> For hard number crunching this could be the better alternative at
>>> the moment.
>> You are telling a CL fan to write Java code?
>> You don't know what you are saying.... ;)
>>
>> (And not because writing Java code is bad, but because they are so
>> mindly closed that they are not going to understand it for sure.)
>
> What part of Java are we not supposed to understand? Some of us have
> dug deep into the JNI and friends to be able to understand very well
> what Java has to offer.
Java can offer, for example, a minimum of 2x more speed (and 4x on
average if you declare everything in CL, and probably 16x if you don't
declare anything) than the best Lisp implementation.
It also offers cross-platform compability. It is also free (and not only
gratis). It is also an industry standard. It is also the language that
everybody knows. It also has an impressive amount of libraries at your
disposal. It scales well low and high. And so on.
You probably can't recognize those advantages, but we all know that
people here are very hard to recognize good things in anything which is
not CL...
>
> Moreover, we do understand Java lessons and try to use them properly.
> CL-ENUMERATION is a CL rendition of Java Enumeration API. This came
> before the new Iterable interface and the Iterator stuff.
> Nevertheless it is a IMHABO a good rendition of the same concepts in
> CL.
>
> Cheers
> --
> Marco
>
>
>
>
On Mar 21, 9:29 am, Javier <·······@gmail.com> wrote:
> Java can offer, for example, a minimum of 2x more speed (and 4x on
> average if you declare everything in CL, and probably 16x if you don't [more java cheerleading snipped]
Then why are you still here if java is so wonderful?
Oh, right, you're a troll.
Javier <·······@gmail.com> writes:
> Java can offer, for example, a minimum of 2x more speed (and 4x on
> average if you declare everything in CL, and probably 16x if you don't
> declare anything) than the best Lisp implementation.
> It also offers cross-platform compability. It is also free (and not only
> gratis). It is also an industry standard. It is also the language that
> everybody knows. It also has an impressive amount of libraries at your
> disposal. It scales well low and high. And so on.
> You probably can't recognize those advantages, but we all know that
> people here are very hard to recognize good things in anything which is
> not CL...
When I need these things, I just use abcl. If a piece exists in Java
and it meets my needs, I use it directly. If I really need speed in
one patch of lisp code, I'll rewrite it in Java. Otherwise it's nice
to write in a mature, full featured, dynamic language.
Other times I'll use sbcl. Other times I'll clisp. Are you getting
the hint?
You don't even know CL, yet you drone on ignorantly about it's flaws.
Why don't you really learn the language first, then complain?
-russ
On Mar 17, 5:37 pm, Javier <·······@gmail.com> wrote:
> Everybody is trying to reinvent Clojure things for CL. I think to
> myself: wouldn't it just better to use Clojure?
As this has an obvious answer -- "No." -- you should investigate
the answer instead of trying to elicit it. Why would people
decide not to use Clojure for these features? Here are some
answers:
1. The reimplemented features aren't regarded as very important.
2. Although everything in Clojure can be ported piecemeal to CL,
the reverse is not the case.
3. Even if you discount #2, porting CL to Clojure is an
overwhelmingly larger task than the reverse.
If you hang in #Clojure, you may have the idea that CL has
nothing at all to recommend it over Clojure. If this the case,
you can begin your investigation by searching for
countexamples.
From: Javier
Subject: Re: Reinventing the iterator
Date:
Message-ID: <gpqhlh$dv$1@aioe.org>
·······@gmail.com escribi�:
> On Mar 17, 5:37 pm, Javier <·······@gmail.com> wrote:
>> Everybody is trying to reinvent Clojure things for CL. I think to
>> myself: wouldn't it just better to use Clojure?
>
> As this has an obvious answer -- "No." -- you should investigate
> the answer instead of trying to elicit it. Why would people
> decide not to use Clojure for these features? Here are some
> answers:
>
> 1. The reimplemented features aren't regarded as very important.
I don't think so.
>
> 2. Although everything in Clojure can be ported piecemeal to CL,
> the reverse is not the case.
False. Clojure is very open, and its (only) implementation is at your
disposal to make changes.
>
> 3. Even if you discount #2, porting CL to Clojure is an
> overwhelmingly larger task than the reverse.
If you avoid porting all the non-needed/boiler-plate features of CL, and
implement modern and well-known new theories of computation appeared
since the emerge of the CL standard, I think you're going to end up with
something very similar to Clojure.
> If you hang in #Clojure, you may have the idea that CL has
> nothing at all to recommend it over Clojure. If this the case,
> you can begin your investigation by searching for
> countexamples.
Javier <·······@gmail.com> writes:
> If you avoid porting all the non-needed/boiler-plate features of CL,
You mistyped `If you throw away the bits of CL I don't like, or that
inconvenience my argument'.
> and implement modern and well-known new theories of computation
> appeared since the emerge of the CL standard, I think you're going to
> end up with something very similar to Clojure.
Well, similar to the way Clojure would be with:
* proper cons cells,
* honest characters,
* nonlocal exits,
* goto,
* efficient and restartable exceptions,
* multiple return values,
* multiple inheritance,
* multiple dispatch methods,
* fancy method combinations.
Good luck.
-- [mdw]
From: Javier
Subject: Re: Reinventing the iterator
Date:
Message-ID: <gpub4m$ldh$1@aioe.org>
Mark Wooding escribi�:
> Javier <·······@gmail.com> writes:
>
>> If you avoid porting all the non-needed/boiler-plate features of CL,
>
> You mistyped `If you throw away the bits of CL I don't like, or that
> inconvenience my argument'.
>
>> and implement modern and well-known new theories of computation
>> appeared since the emerge of the CL standard, I think you're going to
>> end up with something very similar to Clojure.
>
> Well, similar to the way Clojure would be with:
>
> * proper cons cells,
You have conj. It is not the same, it is better! and general.
> * honest characters,
??
Characters can be honest?
> * nonlocal exits,
> * goto,
and line numbers a la basic?
> * efficient and restartable exceptions,
Exceptions in Java are good, can be better.
> * multiple return values,
Use vectors.
> * multiple inheritance,
Clojure has no classes, but has inmmutable "objects" named structs,
which are maps in fact. You can assoc new objects to old ones, and form
very complex structures. And the funny thing is that they are immutable.
> * multiple dispatch methods,
> * fancy method combinations.
Look more closely to this. Clojure has methods, and they are very
powerful, as they can dispatch on VALUE, not only type, something wich
(up to what I know), CLOS is not able to.
Bye.
On Mar 19, 10:52 pm, Javier <·······@gmail.com> wrote:
> You have conj. It is not the same, it is better! and general.
cons cell is not a cons operation (or conj operation)
> > * goto,
>
> and line numbers a la basic?
strange, that you don't object to Clojure's vars. They are global!
>
> Use vectors.
In the lines of those people, who say "exceptions are useless, just
encode the errors in function return values".
> Look more closely to this. Clojure has methods, and they are very
> powerful, as they can dispatch on VALUE, not only type, something wich
> (up to what I know), CLOS is not able to.
Look for EQL method specializers.
Overall, I'll repeat to you the advice of one of the local Clojure
evangelists (André): go program a little bit in Common Lisp, otherwise
you are risking receiving homework assignments from Marco.
Cheers,
Vsevolod
On Mar 19, 4:52 pm, Javier <·······@gmail.com> wrote:
Clojure has methods, and they are very
> powerful, as they can dispatch on VALUE, not only type, something wich
> (up to what I know), CLOS is not able to.
clos can dispatch on value:
? (defmethod foo ((num number))
(format t "~a is a number.~%" num))
#<STANDARD-METHOD FOO (NUMBER)>
? (defmethod foo ((num (eql 42)))
(format t "we're dispatching on the value ~a here, not just class~
%" num))
#<STANDARD-METHOD FOO ((EQL 42))>
? (foo 12)
12 is a number.
NIL
? (foo 42)
we're dispatching on the value 42 here, not just class
NIL
?
clojure has more general multimethod dispatch because the programmer
can define any dispatch function, not just those built into the object
system.
On Mar 20, 12:25 am, Raffael Cavallaro <················@gmail.com>
wrote:
> On Mar 19, 4:52 pm, Javier <·······@gmail.com> wrote:
> Clojure has methods, and they are very
>
> > powerful, as they can dispatch on VALUE, not only type, something wich
> > (up to what I know), CLOS is not able to.
>
> clos can dispatch on value:
>
> ? (defmethod foo ((num number))
> (format t "~a is a number.~%" num))
> #<STANDARD-METHOD FOO (NUMBER)>
> ? (defmethod foo ((num (eql 42)))
> (format t "we're dispatching on the value ~a here, not just class~
> %" num))
> #<STANDARD-METHOD FOO ((EQL 42))>
> ? (foo 12)
> 12 is a number.
> NIL
> ? (foo 42)
> we're dispatching on the value 42 here, not just class
> NIL
> ?
>
> clojure has more general multimethod dispatch because the programmer
> can define any dispatch function, not just those built into the object
> system.
Clojure has more general multimethod dispatch, than CLOS, but CL
method-combinations facilities are even more general. In the previous
discussion I showed how to implement Clojure multimethods with them
(and I didn't even need to use the MOP for that):
http://groups.google.com/group/comp.lang.lisp/msg/53752d14920a9c47
Cheers,
Vsevolod
On Mar 19, 6:36 pm, Vsevolod <········@gmail.com> wrote:
> In the previous
> discussion I showed how to implement Clojure multimethods with them
> (and I didn't even need to use the MOP for that):http://groups.google.com/group/comp.lang.lisp/msg/53752d14920a9c47
yes, nicely done - the benefits of a truly programmable programming
language. but to be fair clojure works this way out of the box, no
define-method-combination hacking required.
On Mar 20, 12:51 am, Raffael Cavallaro <················@gmail.com>
wrote:
> On Mar 19, 6:36 pm, Vsevolod <········@gmail.com> wrote:
>
> > In the previous
> > discussion I showed how to implement Clojure multimethods with them
> > (and I didn't even need to use the MOP for that):http://groups.google.com/group/comp.lang.lisp/msg/53752d14920a9c47
>
> yes, nicely done - the benefits of a truly programmable programming
> language. but to be fair clojure works this way out of the box, no
> define-method-combination hacking required.
Surely. And presence of defmulti in it is a very good choice,
considering the context.
But then it doesn't have, for example, :before/:around/:after method
combination. And I don't see a way to add it without going down to the
Java level (and even that way it seems to be problematic)...
On Mar 19, 7:01 pm, Vsevolod <········@gmail.com> wrote:
> On Mar 20, 12:51 am, Raffael Cavallaro <················@gmail.com>
> wrote:
>
> > On Mar 19, 6:36 pm, Vsevolod <········@gmail.com> wrote:
>
> > > In the previous
> > > discussion I showed how to implement Clojure multimethods with them
> > > (and I didn't even need to use the MOP for that):http://groups.google.com/group/comp.lang.lisp/msg/53752d14920a9c47
>
> > yes, nicely done - the benefits of a truly programmable programming
> > language. but to be fair clojure works this way out of the box, no
> > define-method-combination hacking required.
>
> Surely. And presence of defmulti in it is a very good choice,
> considering the context.
>
> But then it doesn't have, for example, :before/:around/:after method
> combination. And I don't see a way to add it without going down to the
> Java level (and even that way it seems to be problematic)...
my take on things is that clojure has a lot of things neatly packaged
and ready to go for many common use cases. If you want similar things
in common lisp you can have them, but you'll have to roll your own. If
you're looking for a language to be a building material then common
lisp is arguably a better substrate to start with. If you're looking
to use the language as is, clojure might be a better choice,
especially if your goals include java library interop and an easy path
to correct concurrency. The fact that there are no user reader macros
says a lot; Rich Hickey doesn't want lots of incompatible dialects as
it were; everyone should be using the same idioms; whereas common lisp
hands you the keys and says "go to town!"
Javier <·······@gmail.com> writes:
> Mark Wooding escribió:
> > Javier <·······@gmail.com> writes:
> >
> >> If you avoid porting all the non-needed/boiler-plate features of CL,
> >
> > You mistyped `If you throw away the bits of CL I don't like, or that
> > inconvenience my argument'.
> >
> >> and implement modern and well-known new theories of computation
> >> appeared since the emerge of the CL standard, I think you're going to
> >> end up with something very similar to Clojure.
> >
> > Well, similar to the way Clojure would be with:
> >
> > * proper cons cells,
>
> You have conj. It is not the same, it is better! and general.
Clojure:
user=> (conj 1 2)
java.lang.ClassCastException: java.lang.Integer cannot be cast to
clojure.lang.IPersistentCollection (NO_SOURCE_FILE:0)
Common Lisp (actually SBCL):
* (cons 1 2)
(1 . 2)
CL looks more general to me.
> > * honest characters,
>
> Characters can be honest?
Yes. Java `char's, which Clojure uses as its characters, are dishonest,
because they can't properly represent Unicode characters outside of the
Basic Multilingual Plane -- for that, one needs a `surrogate pair' of
`char' objects. This is obviously insane: I shouldn't need two
`character' objects to represent one character.
> > * nonlocal exits,
> > * goto,
>
> and line numbers a la basic?
No. Block names, catch tags and tagbody labels will do fine. Given
one, I can manufacture the others with macros. Given none, I'm screwed.
(Common Lisp provides a large collection of useful control constructs --
more than any other language I know of, certainly. As an aside, I
implemented something quite like TAGBODY in Tcl once...)
> > * efficient and restartable exceptions,
>
> Exceptions in Java are good, can be better.
They're distressingly poor! Reifying the stack backtrace prematurely
was a major blunder. Of course, without nonlocal exits (above), it's
hard to build a sensible restartable exception system.
> > * multiple return values,
>
> Use vectors.
Ugh! Then I have to painstakingly ignore the values I wasn't interested
in. In CL, I just get the primary value if I didn't do anything
special.
In this way, GETHASH can return the thing I was looking for or NIL --
which is great for most cases -- with an additional `really found it'
flag for those cases when it's important to distinguish NIL from an
absent entry. CL's well-thought-out FLOOR, CEILING and TRUNCATE
operations are useful for their primary (quotient) values, but also
provide a remainder as a second value.
Keyword arguments are a good way to extend a function's input without
breaking compatibility; CL's multiple return values are a good way of
extending its output.
> > * multiple inheritance,
>
> Clojure has no classes, but has inmmutable "objects" named structs,
> which are maps in fact. You can assoc new objects to old ones, and
> form very complex structures. And the funny thing is that they are
> immutable.
So, a lose, then.
> > * multiple dispatch methods,
> > * fancy method combinations.
>
> Look more closely to this. Clojure has methods, and they are very
> powerful, as they can dispatch on VALUE, not only type, something wich
> (up to what I know), CLOS is not able to.
EQL specializers.
Oh, I didn't mention the package system, which is another CL win.
-- [mdw]
On Mar 19, 8:04 pm, Mark Wooding <····@distorted.org.uk> wrote:
> Javier <·······@gmail.com> writes:
[...]
> > and line numbers a la basic?
> No. Block names, catch tags and tagbody labels will do fine. Given
> one, I can manufacture the others with macros.
You can do TAGBODY/GO with LABELS, though, provided you have a
compiler which will merge tail calls for you.
Cheers,
Pillsy
Pillsy <·········@gmail.com> writes:
> You can do TAGBODY/GO with LABELS, though, provided you have a
> compiler which will merge tail calls for you.
No. This would only work for GO calls in tail-position. Remember: GO
can do nonlocal transfers, e.g., from nested LAMBDA expressions, like
RETURN does.
-- [mdw]
On Mar 20, 6:21 am, Mark Wooding <····@distorted.org.uk> wrote:
> Remember: GO can do nonlocal transfers, e.g., from nested LAMBDA
> expressions, like RETURN does.
I had forgotten all about that, actually.
Oops,
Pillsy
On Mar 17, 11:37 pm, Javier <·······@gmail.com> wrote:
> Vsevolod escribió:
>
> > I thought about implementing a kind of the Clojure-style SEQ protocol
> > for iterating over arbitrary collections. Below is my first take.
>
> Everybody is trying to reinvent Clojure things for CL. I think to
> myself: wouldn't it just better to use Clojure?
Doesn't look to me that anybody is trying to reinvet anything. Have
you looked at the initial checkin date of CL-ENUMERATION?
Cheers
--
Marco