forked from filonenko-mikhail/cltl2-doc
-
Notifications
You must be signed in to change notification settings - Fork 0
/
clmse146.html
140 lines (131 loc) · 8.16 KB
/
clmse146.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//RU"
"http://www.w3.org/TR/html4/loose.dtd">
<html >
<head><title>Introduction</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="generator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)">
<meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)">
<!-- 3,index=2,next,fn-in,charset=utf-8,sections+,minitoc<,html -->
<meta name="src" content="clm.tex">
<meta name="date" content="2012-04-12 20:56:00">
<link rel="stylesheet" type="text/css" href="clm.css">
<link rel="stylesheet" type="text/css" href="cltl2ed.css"></head><body
>
<!--l. 42--><p class="noindent" > <div id="main_container"> <div id="content"> <div id="toplinks"><tt><</tt><a
href="clmse147.html" >Далее</a><tt>></tt><tt><</tt><a
href="clmap1.html" >Назад</a><tt>></tt><tt><</tt><a
href="clmap1.html#tailclmap1.html" >Назад-и-вниз</a><tt>></tt><tt><</tt><a
href="#tailclmse146.html">В-конец</a><tt>></tt><tt><</tt><a
href="clmap1.html#clmse146.html" >Наверх</a><tt>></tt></div><h3 class="sectionHead"><span class="titlemark">A.1 </span> <a
href="clm.html#QQ2-180-485" id="x180-461000A.1">Introduction</a></h3>
<!--l. 44--><p class="noindent" >Series combine aspects of sequences, streams, and loops. Like sequences, series
represent totally ordered multi-sets. In addition, the series functions have the
same flavor as the sequence functions—namely, they operate on whole series,
rather than extracting elements to be processed by other functions. For instance,
the series expression below computes the sum of the positive elements in a list.
<div class=lisp><div class=tabbing>
<table
cellpadding="0" border="0" cellspacing="0"
class="tabbing"><tr
style="vertical-align:baseline;" class="tabbing"><td
class="tabbing">(collect-sum (choose-if #’plusp (scan ’(1 -2 3 -4)))) <span class="math"> ⇒</span> 4
</td></tr></table>
<!--l. 52--><p class="indent" >
</div>
</div>
<!--l. 54--><p class="indent" > Like streams, series can represent unbounded sets of elements and are
supported by lazy evaluation: each element of a series is not computed until it is
needed. For instance, the series expression below returns a list of the first five even
natural numbers and their sum. The call on <tt><a
href="clmse147.html#x181-463002r975">scan-range</a></tt> returns a series of all
the even natural numbers. However, since no elements beyond the first
five are ever used, no elements beyond the first five are ever computed.
<div class=lisp><div class=tabbing>
<table
cellpadding="0" border="0" cellspacing="0"
class="tabbing"><tr
style="vertical-align:baseline;" class="tabbing"><td
class="tabbing">(let ((x (subseries (scan-range :from 0 :by 2) 0 5)))
</td></tr></table>
<!--l. 62--><p class="indent" > <table
cellpadding="0" border="0" cellspacing="0"
class="tabbing"><tr
style="vertical-align:baseline;" class="tabbing"><td
class="tabbing"> (values (collect x) (collect-sum x)))</td></tr></table>
<!--l. 63--><p class="indent" > <table
cellpadding="0" border="0" cellspacing="0"
class="tabbing"><tr
style="vertical-align:baseline;" class="tabbing"><td
class="tabbing"> <span class="math"> ⇒</span> (0 2 4 6 8) and 20</td></tr></table>
<!--l. 65--><p class="indent" >
</div>
</div>
<!--l. 67--><p class="indent" > Like sequences and unlike streams, a series is not altered when its
elements are accessed. For instance, both users of <tt>x</tt> above receive the same
elements.
<!--l. 71--><p class="indent" > A totally ordered multi-set of elements can be represented in a loop by the
successive values of a variable. This is extremely efficient, because it avoids the
need to store the elements as a group in any kind of data structure. In most
situations, series expressions achieve this same high level of efficiency, because
they are automatically transformed into loops before being evaluated or compiled.
For instance, the first expression above is transformed into a loop like the
following. <div class=lisp><div class=tabbing>
<table
cellpadding="0" border="0" cellspacing="0"
class="tabbing"><tr
style="vertical-align:baseline;" class="tabbing"><td
class="tabbing">(let ((sum 0))
</td></tr></table>
<!--l. 79--><p class="indent" > <table
cellpadding="0" border="0" cellspacing="0"
class="tabbing"><tr
style="vertical-align:baseline;" class="tabbing"><td
class="tabbing"> (dolist (i ’(1 -2 3 -4) sum)</td></tr></table>
<!--l. 80--><p class="indent" > <table
cellpadding="0" border="0" cellspacing="0"
class="tabbing"><tr
style="vertical-align:baseline;" class="tabbing"><td
class="tabbing"> (when (plusp i) (setq sum (+ sum i))))) <span class="math"> ⇒</span> 4</td></tr></table>
<!--l. 82--><p class="indent" >
</div>
</div>
<!--l. 84--><p class="indent" > A wide variety of algorithms can be expressed clearly and succinctly with
series expressions. In particular, at least 90 percent of the loops programmers
typically write can be replaced by series expressions that are much easier to
understand and modify, and just as efficient. From this perspective, the key
feature of series is that they are supported by a rich set of functions. These
functions more or less correspond to the union of the operations provided by
the sequence functions, the <tt><a
href="clmse41.html#x53-117002r90">loop</a></tt> clauses, and the vector operations of
APL.
<!--l. 93--><p class="indent" > Some series expressions cannot be transformed into loops. This is unfortunate,
because while transformable series expressions are much more efficient than
equivalent expressions involving sequences or streams, non-transformable series
expressions are much less efficient. Whenever a problem comes up that blocks the
transformation of a series expression, a warning message is issued. On the basis of
information in the message, it is usually easy to provide an efficient fix for the
problem (see section <a
href="clmse148.html#x182-471000A.3">A.3<!--tex4ht:ref: SERIES-E-SECTION --></a>).
<!--l. 102--><p class="indent" > Fortunately, most series expressions can be transformed into loops. In
particular, pure expressions (ones that do not store series in variables) can always
be transformed. As a result, the best approach for programmers to take is
simply to write series expressions without worrying about transformability.
When problems come up, they can be ignored (since they cannot lead
to the computation of incorrect results) or dealt with on an individual
basis.
<div class=implementation>
<!--l. 111--><p class="noindent" ><b>Заметка для реализации:</b> The series functions and the theory underlying them are
described in greater detail in <span class="cite">[<a
href="clmli5.html#XWATERS-SERIES-DESIGN">52</a>, <a
href="clmli5.html#XWATERS-SERIES-IMPLEMENTATION">53</a>]</span>. These reports also discuss the algorithms required
to transform series expressions into loops and explain how to obtain a portable
implementation.
</div>
<!--l. 120--><p class="indent" > <div id="bottomlinks"><tt><</tt><a
href="clmse147.html" >Далее</a><tt>></tt><tt><</tt><a
href="clmap1.html" >Назад</a><tt>></tt><tt><</tt><a
href="clmap1.html#tailclmap1.html" >Назад-и-вниз</a><tt>></tt><tt><</tt><a
href="clmse146.html" >В-начало</a><tt>></tt><tt><</tt><a
href="clmap1.html#clmse146.html" >Наверх</a><tt>></tt></div><a
id="tailclmse146.html"></a> </div> </div>
</body></html>