Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 243 lines (188 sloc) 8.018 kB
a27785d @tlikonen Add files to the repository
authored
1 * General accumulator
2
3 General accumulator is a general-purpose, extensible value accumulator
4 library for Common Lisp language. Its main interface is
5 =with-accumulator= macro which sets an environment for easy
6 accumulation. The library provides several built-in accumulators which
7 should cover the common use-cases but any kind of accumulators can be
8 added because the accumulator back-end is implemented through generic
9 functions.
10
11 ** The interface
12
13 #+BEGIN_SRC lisp
14 (with-accumulator (NAME OBJECT &key KEYWORD-ARGUMENTS ...)
15 BODY ...)
16 #+END_SRC
17
18 The =with-accumulator= macro creates an accumulation environment in
19 which a local function /name/ handles the accumulation. Accumulator's
20 type is defined by the /object/ argument. Then all /body/ forms are
21 executed normally and the return value of the last form is returned.
22
23 The local function /name/ can optionally take one argument which is an
24 object to be accumulated. If the function is called without arguments it
25 returns the currently accumulated value.
26
27 The accumulation process is handled by generic functions =initialize=,
28 =accumulate= and =value=.
29
30 ** Built-in accumulators
31
32 There are several built-in accumulator types. Possible values for the
33 /object/ argument of =with-accumulator= macro:
34
d76ac6f @tlikonen Change built-in accumulator names from boldface to a ***-level heading
authored
35 *** :LIST
a27785d @tlikonen Add files to the repository
authored
36
37 Creates a list collector. Each accumulated object is collected to a
38 list. Example:
39
40 #+BEGIN_SRC lisp
41 GENACC> (with-accumulator (collect :list)
42 (collect 1) (collect 2) (collect 3)
43 (collect))
44 (1 2 3)
45 #+END_SRC
46
47 The collecting is done destructively. The applicable /accumulate/ method
48 maintains a pointer to the last cons cell of the list and each time
49 modifies its /cdr/ value to point to a new cons cell.
50
d76ac6f @tlikonen Change built-in accumulator names from boldface to a ***-level heading
authored
51 *** [A list]
a27785d @tlikonen Add files to the repository
authored
52
53 If the /object/ argument is of type /list/ then new elements are
54 collected at the end. Example:
55
56 #+BEGIN_SRC lisp
57 GENACC> (with-accumulator (collect (list 1 2 3))
58 (collect 4) (collect 5)
59 (collect))
60 (1 2 3 4 5)
61 #+END_SRC
62
63 This is a destructive operation. The /cdr/ value of the last cons cell
64 of the original list is modified and linked to a new cons cell.
65
d76ac6f @tlikonen Change built-in accumulator names from boldface to a ***-level heading
authored
66 *** :VECTOR
a27785d @tlikonen Add files to the repository
authored
67
68 Creates a general vector collector. It creates an adjustable vector with
69 a fill pointer 0 and element type /t/. New elements are pushed to that
70 vector with =cl:vector-push-extend= function. Example:
71
72 #+BEGIN_SRC lisp
73 GENACC> (with-accumulator (collect :vector)
74 (collect "first") (collect "second")
75 (collect))
76 #("first" "second")
77 #+END_SRC
78
d76ac6f @tlikonen Change built-in accumulator names from boldface to a ***-level heading
authored
79 *** :STRING
a27785d @tlikonen Add files to the repository
authored
80
81 This is similar to =:VECTOR= but the element type is /character/. The
82 underlying /accumulate/ methods can take a single /character/ or a
83 sequence of characters as the argument. Example:
84
85 #+BEGIN_SRC lisp
86 GENACC> (with-accumulator (collect :string)
87 (collect #\a)
88 (collect "bcd")
89 (collect #(#\e #\f))
90 (collect '(#\g #\h #\i))
91 (collect))
92 "abcdefghi"
93 #+END_SRC
94
d76ac6f @tlikonen Change built-in accumulator names from boldface to a ***-level heading
authored
95 *** :BIT-VECTOR
a27785d @tlikonen Add files to the repository
authored
96
97 This is similar to =:STRING= but the element type is /bit/. The argument
98 for the accumulator function can a /bit/ or a sequence of bits.
99
d76ac6f @tlikonen Change built-in accumulator names from boldface to a ***-level heading
authored
100 *** [A vector]
a27785d @tlikonen Add files to the repository
authored
101
102 If /object/ is of type /vector/ which satisfies the test
103 =array-has-fill-pointer-p= then that vector is appended, starting from
104 its current fill pointer.
105
106 #+BEGIN_SRC lisp
db188f4 @tlikonen Don't start example lines with ":" character.
authored
107 GENACC> (defvar *arr*
108 (make-array 2 :fill-pointer 2 :adjustable t :initial-contents
109 (vector 1 2)))
110 *arr*
111 GENACC> (with-accumulator (collect *arr*)
a27785d @tlikonen Add files to the repository
authored
112 (collect 3)
113 (collect 4)
114 (collect))
115 #(1 2 3 4)
116 #+END_SRC
117
118 Note that if the vector is not adjustable then the accumulator may reach
119 vector's limits and =cl:vector-push-extend= signals an error.
120
d76ac6f @tlikonen Change built-in accumulator names from boldface to a ***-level heading
authored
121 *** [A function]
a27785d @tlikonen Add files to the repository
authored
122
123 If /object/ is of type /function/ then the accumulator behaves like the
124 =cl:reduce= function: all accumulated objects are combined into one by
125 calling the given reducer function. Examples:
126
127 #+BEGIN_SRC lisp
128 GENACC> (with-accumulator (summing #'+)
129 (summing 5) (summing 7) (summing 11)
130 (summing))
131 23
132
133 GENACC> (with-accumulator (nc #'nconc)
134 (nc (list 1 2 3))
135 (nc (list 4 5 6))
136 (nc (list 7 8 9))
137 (nc))
138 (1 2 3 4 5 6 7 8 9)
139
140 GENACC> (with-accumulator (early-char (lambda (a b)
141 (if (char< a b) a b)))
142 (early-char #\o)
143 (early-char #\b)
144 (early-char #\s)
145 (early-char))
146 #\b
147 #+END_SRC
148
149 Note that a single reduce operation for a sequence is probably faster
150 with just =cl:reduce= function than with =with-accumulator= macro.
151 Therefore, the macro could be used only for collecting values into a
152 sequence and =cl:reduce= would be used for the actual reduce operation.
153 On the other hand, an advantage of doing all the reducing work with
154 =with-accumulator= is that the macro does it one step at the time.
155 Intermediate results of the reducing are always available.
156
157 ** Adding a custom accumulator
158
159 The whole accumulation process is handled by three generic functions:
160 =initialize=, =accumulate= and =value=. Writing new methods for those
161 functions allow adding any kind of accumulators. The following example
162 adds an accumulator which calculates the arithmetic mean of accumulated
163 numbers.
164
165 First we define a class whose instances will keep the state of the
166 accumulator. In this case we need to store the sum and the count of
167 accumulated numbers so we create slots for them.
168
169 #+BEGIN_SRC lisp
170 (defclass mean-accumulator ()
171 ((sum :initform 0)
172 (count :initform 0)))
173 #+END_SRC
174
175 Then we add a method for initializing an instance of the class. The
176 generic function =initialize= is used for that. It is called with the
177 /object/ argument of =with-accumulator= macro and with optional
178 /keyword-arguments/. In this example we use an /EQL/ specializer for
179 symbol =:MEAN=. We don't use any keyword arguments so there's just empty
180 /&key/ at the end of the lambda list.
181
182 #+BEGIN_SRC lisp
183 (defmethod genacc:initialize ((type (eql :mean)) &key)
184 (make-instance 'mean-accumulator))
185 #+END_SRC
186
187 Now we create a method for generic function =accumulate=. The function
188 is called with two arguments:
189
190 1. the accumulator object created by =initialize=
191 2. the object that is meant to be accumulated.
192
193 This method specializes on our =mean-accumulator= class as well as on
194 /number/ class. The number is added to the previous value and the count
195 is increased by one.
196
197 #+BEGIN_SRC lisp
198 (defmethod genacc:accumulate ((object mean-accumulator)
199 (number number))
200 (with-slots (sum count) object
201 (incf sum number)
202 (incf count 1)))
203 #+END_SRC
204
205 For returning the accumulated mean value we create a method for the
206 generic function =value=. This method, too, must specialize on the
207 =mean-accumulator= class. We get the current accumulated mean value by
208 dividing the value of /sum/ slot with the value of /count/ slot.
209
210 #+BEGIN_SRC lisp
211 (defmethod genacc:value ((object mean-accumulator))
212 (with-slots (sum count) object
213 (/ sum count)))
214 #+END_SRC
215
216 Now the custom accumulator is ready and it can be used with the
217 =with-accumulator= macro. Example:
218
219 #+BEGIN_SRC lisp
220 GENACC> (with-accumulator (mean :mean)
221 (loop repeat 10 do (mean (random 1000)))
222 (format t "The mean so far: ~A~%" (mean))
223 (loop repeat 10 do (mean (random 1000)))
224 (format t "The final mean: ~A~%" (mean)))
225 The mean so far: 2512/5
226 The final mean: 2704/5
227 NIL
228 #+END_SRC
f584102 @tlikonen Add author and license info
authored
229
a24ec10 @tlikonen Add an URL to the source code repository
authored
230 ** The source code repository
231
232 GitHub repository: <[[https://github.com/tlikonen/cl-general-accumulator]]>
233
f584102 @tlikonen Add author and license info
authored
234 ** Author and license
235
3b7bed0 @tlikonen Remove hyperlink markup from email address
authored
236 Author: Teemu Likonen <tlikonen@iki.fi>
f584102 @tlikonen Add author and license info
authored
237
238 License: Public domain
239
240 This program is distributed in the hope that it will be useful, but
241 WITHOUT ANY WARRANTY; without even the implied warranty of
242 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Something went wrong with that request. Please try again.