- alexandria-devel - mailman3.common-lisp.net

[alexandria-devel] Simple optimizations for BINOMIAL-COEFFICIENT and COUNT-PERMUTATIONS
by Gustavo 23 Sep '10

23 Sep '10

Hello, Just some simple optimizations. By the way, nice work on FACTORIAL, it is very fast. Gustavo

2 1

[alexandria-devel] IO for vectors.
by Heka Treep 16 Sep '10

16 Sep '10

Hi, I was define some functions like `read-file-into-string' and `write-string-into-file' but for various vectors. That's all functions: read-file-into-vector read-file-into-byte-vector read-file-into-{u|s}{8|16|32|64}-vector write-vector-into-file write-byte-vector-into-file write-{u|s}{8|16|32|64}-vector-into-file Like in Scheme's SRFI.

1 0

[alexandria-devel] Fwd: Fold operators on lists and trees in Alexandria?
by Gustavo 19 Aug '10

19 Aug '10

Sorry, I forgot to CC. ---------- Forwarded message ---------- From: Gustavo <gugamilare(a)gmail.com> Date: 2010/8/8 Subject: Re: [alexandria-devel] Fold operators on lists and trees in Alexandria? To: Heka Treep <zena.treep(a)gmail.com> Hello, Heka, Just to clarify, I'm not a Alexandria developer, but I'll make some criticism. I'm sorry but flatten/fold-right is not faster than flatten. It has a bug that prevents it from working correctly: fold-right version is destructive (it uses nreverse in the incoming list, it should be used in the result).Then, if you make a loop that flattens the same tree a lot of times, the original tree is modified so the running time is altered. cl-user> (defvar tree '((1 2 3) (4 5 6))) tree cl-user> (flatten/fold-right tree) (1 2 3 4 5 6) cl-user> tree ((1)) It doesn't make sense flatten/fold-right to be faster than flatten because it calls append which needs to traverse the first argument, so it gets slower when the list to be flattened has large sublists. Also, it treats NIL as an atom while flatten treats it as the empty list. The following version of flatten is the only one that I have noted to be faster than flatten (25% to 45% faster) because it doesn't have to call nreverse at the end: (defun flatten/tail (tree) (let (list tail) (labels ((traverse (subtree) (when subtree (cond ((consp subtree) (progn (traverse (car subtree)) (traverse (cdr subtree)))) (tail (setf (cdr tail) (cons subtree nil) tail (cdr tail))) (t (setf list (list subtree) tail list)))))) (traverse tree)) list)) Don't worry, everyone commits mistakes. It took me some time to figure out the problem too. Gustavo. 2010/8/7 Heka Treep <zena.treep(a)gmail.com> > Sorry, I made a small typo: > > > (defun flatten/fold-rigth (list) > (fold-rigth #'(lambda (e rest) > (typecase e > (atom (cons e rest)) > - (list (append (flatten e) rest)) > + (list (append (flatten/fold-rigth e) rest)))) > list nil)) > > But this, of course, does not affect the benchmark. > > 2010/8/8 Heka Treep <zena.treep(a)gmail.com> > > Hi. >> >> I was found that there is no effective fold operators on lists or trees in >> CL. I know that `reduce' can do this (as an article in Wikipedia sayz) but >> `reduce' is not very effective. As stated in the Graham Hutton's article >> ``fold is a standard operator that encapsulates a simple pattern of >> recursion for processing lists'', also catamorphism at some ADT plays the >> same role. So I thought that if we introduce an effective fold operators, it >> becomes possible to express many functions through its shortly and >> effectively (in fact, almost any function on that ADT). >> >> Take for example the `flatten' function that is defined in Alexandria as >> follows: >> >> >> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; >> ;; ok, TCO recursion: >> ;; >> (defun flatten (tree) >> (let (list) >> (labels ((traverse (subtree) >> (when subtree >> (if (consp subtree) >> (progn >> (traverse (car subtree)) >> (traverse (cdr subtree))) >> (push subtree list))))) >> (traverse tree)) >> (nreverse list))) >> >> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; >> >> We need an ADT for the trees, but in the first approximation we can use >> nested lists. >> >> When expressed in terms of reduce: >> >> >> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; >> (defun flatten/reduce (list) >> (reduce #'(lambda (e rest) >> (typecase e >> (atom (cons e rest)) >> (list (append (flatten/reduce e) rest)))) >> list >> :initial-value nil >> :from-end t)) >> >> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; >> >> Now if we translate pure functional operator (here is `reduce') to the >> instructions for tagbody/go "state machine": >> >> >> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; >> ;;; fold-left f '(a b c) i >> ;;; >> ;;; f >> ;;; /\ >> ;;; f c >> ;;; /\ >> ;;; f b >> ;;; /\ >> ;;; i a >> ;;; >> ;;; foldl f z [] = z >> ;;; foldl f z (x:xs) = foldl f (f z x) xs >> >> (defun fold-left (function list &optional initial-value) >> (let ((result initial-value)) >> (tagbody >> :start >> (unless (endp list) >> (setq result (funcall function result (car list))) >> (setq list (cdr list)) >> (go :start))) >> result)) >> >> ;;; fold-rigth f '(a b c) i >> ;;; >> ;;; f >> ;;; /\ >> ;;; a f >> ;;; /\ >> ;;; b f >> ;;; /\ >> ;;; c i >> ;;; >> ;;; foldr f z [] = z >> ;;; foldr f z (x:xs) = f x (foldr f z xs) >> >> (defun fold-rigth (function list &optional initial-value) >> (let ((result initial-value) >> (list (nreverse list))) >> (tagbody >> :start >> (unless (endp list) >> (setq result (funcall function (car list) result)) >> (setq list (cdr list)) >> (go :start))) >> result)) >> >> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; >> >> Then `flatten' can be written as: >> >> >> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; >> (defun flatten/fold-rigth (list) >> (fold-rigth #'(lambda (e rest) >> (typecase e >> (atom (cons e rest)) >> (list (append (flatten e) rest)))) >> list nil)) >> >> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; >> >> I try to benchmarc (this three functions) and has the following results: >> >> flatten/fold-rigth >> >> X time >> Y memory >> >> alexandria:flatten >> >> 10 * X time >> 23 * Y memory >> >> flatten/reduce >> >> 42 * X time >> 83 * Y memory >> >> So, its look resonable to use folders there. >> >> >> >> ((sorry for my english - I just using google.translate :)) >> > > > _______________________________________________ > alexandria-devel mailing list > alexandria-devel(a)common-lisp.net > http://common-lisp.net/cgi-bin/mailman/listinfo/alexandria-devel > >

2 1

[alexandria-devel] Fold operators on lists and trees in Alexandria?
by Heka Treep 07 Aug '10

07 Aug '10

Hi. I was found that there is no effective fold operators on lists or trees in CL. I know that `reduce' can do this (as an article in Wikipedia sayz) but `reduce' is not very effective. As stated in the Graham Hutton's article ``fold is a standard operator that encapsulates a simple pattern of recursion for processing lists'', also catamorphism at some ADT plays the same role. So I thought that if we introduce an effective fold operators, it becomes possible to express many functions through its shortly and effectively (in fact, almost any function on that ADT). Take for example the `flatten' function that is defined in Alexandria as follows: ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;; ok, TCO recursion: ;; (defun flatten (tree) (let (list) (labels ((traverse (subtree) (when subtree (if (consp subtree) (progn (traverse (car subtree)) (traverse (cdr subtree))) (push subtree list))))) (traverse tree)) (nreverse list))) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; We need an ADT for the trees, but in the first approximation we can use nested lists. When expressed in terms of reduce: ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun flatten/reduce (list) (reduce #'(lambda (e rest) (typecase e (atom (cons e rest)) (list (append (flatten/reduce e) rest)))) list :initial-value nil :from-end t)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Now if we translate pure functional operator (here is `reduce') to the instructions for tagbody/go "state machine": ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;; fold-left f '(a b c) i ;;; ;;; f ;;; /\ ;;; f c ;;; /\ ;;; f b ;;; /\ ;;; i a ;;; ;;; foldl f z [] = z ;;; foldl f z (x:xs) = foldl f (f z x) xs (defun fold-left (function list &optional initial-value) (let ((result initial-value)) (tagbody :start (unless (endp list) (setq result (funcall function result (car list))) (setq list (cdr list)) (go :start))) result)) ;;; fold-rigth f '(a b c) i ;;; ;;; f ;;; /\ ;;; a f ;;; /\ ;;; b f ;;; /\ ;;; c i ;;; ;;; foldr f z [] = z ;;; foldr f z (x:xs) = f x (foldr f z xs) (defun fold-rigth (function list &optional initial-value) (let ((result initial-value) (list (nreverse list))) (tagbody :start (unless (endp list) (setq result (funcall function (car list) result)) (setq list (cdr list)) (go :start))) result)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Then `flatten' can be written as: ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun flatten/fold-rigth (list) (fold-rigth #'(lambda (e rest) (typecase e (atom (cons e rest)) (list (append (flatten e) rest)))) list nil)) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; I try to benchmarc (this three functions) and has the following results: flatten/fold-rigth X time Y memory alexandria:flatten 10 * X time 23 * Y memory flatten/reduce 42 * X time 83 * Y memory So, its look resonable to use folders there. ((sorry for my english - I just using google.translate :))

1 1

[alexandria-devel] Missing export of sans
by Liam Healy 16 Jul '10

16 Jul '10

'sans is not exported, despite it being described in the manual as alexandria:sans. Liam

2 1

[alexandria-devel] Fix for CDR5 type generation / Symbol case
by Hans Hübner 14 Jun '10

14 Jun '10

Hi, find a patch to Alexandria attached that makes CDR5 type generation work with Allegro CL in "modern" mode. Thanks for pushing, Hans

1 0

[alexandria-devel] Compilation failure
by Sebastian Tennant 04 Jun '10

04 Jun '10

Hi all, Just checked out the latest git version and keep getting the following compilation error with SBCL 1.0.34: --- REPL --- [...] WARNING: COMPILE-FILE warned while performing #<COMPILE-OP NIL {BC32C51}> on #<CL-SOURCE-FILE "conditions" {AFEDBD1}>. ; compilation unit aborted ; caught 1 fatal ERROR condition ; caught 1 WARNING condition --- buffer: *SLIME Compilation* --- cd /root/ 1 compiler notes: Unknown location: warning: COMPILE-FILE warned while performing #<COMPILE-OP NIL {C440179}> on #<CL-SOURCE-FILE "conditions" {AFEDBD1}>. Unknown location: error: erred while invoking #<COMPILE-OP NIL {C440179}> on #<CL-SOURCE-FILE "conditions" {AFEDBD1}> clbuild/source/alexandria/conditions.lisp:9:1: warning: change in superclasses of class SIMPLE-STYLE-WARNING: current superclasses: (T CONDITION SIMPLE-CONDITION SIMPLE-WARNING WARNING STYLE-WARNING) new superclasses: (T CONDITION STYLE-WARNING WARNING SIMPLE-CONDITION SIMPLE-WARNING) --> PROGN ==> (EVAL-WHEN (:COMPILE-TOPLEVEL) (SB-KERNEL::%COMPILER-DEFINE-CONDITION 'ALEXANDRIA.0.DEV:SIMPLE-STYLE-WARNING '(SIMPLE-WARNING STYLE-WARNING) '#<SB-KERNEL:LAYOUT for ALEXANDRIA.0.DEV:SIMPLE-STYLE-WARNING, INVALID=:UNINITIALIZED {C12D0A1}> 'NIL 'NIL)) Compilation failed. Hope this helps. Sebastian -- Emacs' AlsaPlayer - Music Without Jolts Lightweight, full-featured and mindful of your idyllic happiness. http://home.gna.org/eap

2 2

[alexandria-devel] COUNT-PERMUTATIONS and SUBFACTORIAL patch
by Mason Smith 18 May '10

18 May '10

The attached patch addresses two issues: 1. COUNT-PERMUTATIONS now has type-checking and uses %MULTIPLY-RANGE, as was suggested in the comments. 2. SUBFACTORIAL now produces correct values. Previously, the values returned were incorrect starting with N = 12 or so. This was because the approximate value of e, produced by (exp 1), had insufficient precision be used in the [ n! / e ] formula for the subfactorial !n. Changing (exp 1) to (exp1.0d0) adds precision to e, but the problem still remained for N >= 14 or so. I reimplemented SUBFACTORIAL using the !n = n! * \sum_{k=0}^k{ \frac{ (-1)^k }{ k! } } formula to give exact results. I also added tests for both of these functions. In the near future, I'd like to open up a review of these functions (as well as the other combinatorics functions). Nikodemus suggested a couple of months ago that this should be done, but I wasn't sure if this was limited to Alexandria's main developers or open to everyone. Mason

1 0

[alexandria-devel] `with-rebinding' macro
by Heka Treep 18 Apr '10

18 Apr '10

Hi, How about to take this macro in Alexandria? I was found it in Hunchentoot and rewrote using a simple `dolist' (instead `loop'). The patch can be found here: http://github.com/treep/alexandria/commit/13479ea033d68fc521f9eaa80d0689d61…

2 2

[alexandria-devel] Review cycle 2: SWITCH, ESCWITCH, and CSWITCH
by Nikodemus Siivola 08 Apr '10

08 Apr '10

macro switch ((object &key test key) &body clauses) "Evaluates first matching clause, returning its values, or evaluates and returns the values of DEFAULT if no keys match." macro eswitch ((object &key test key) &body clauses) "Like SWITCH, but signals an error if no key matches." cswitch ((object &key test key) &body clauses) "Like SWITCH, but signals a continuable error if no key matches."

8 23