1 <!DOCTYPE html PUBLIC
"-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
4 <meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8">
5 <meta http-equiv=
"Content-Style-Type" content=
"text/css">
7 <meta name=
"Generator" content=
"Cocoa HTML Writer">
8 <meta name=
"CocoaVersion" content=
"824.42">
9 <style type=
"text/css">
10 p
.p1
{margin: 0.0px 0.0px 0.0px 0.0px; font: 18.0px Helvetica
}
11 p
.p2
{margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica
; min-height: 14.0px}
12 p
.p3
{margin: 0.0px 0.0px 0.0px 0.0px; font: 12.0px Helvetica
}
13 p
.p4
{margin: 0.0px 0.0px 0.0px 0.0px; font: 10.0px Monaco
; min-height: 14.0px}
14 p
.p5
{margin: 0.0px 0.0px 0.0px 0.0px; font: 10.0px Monaco
; color: #a71e12}
15 p
.p6
{margin: 0.0px 0.0px 0.0px 0.0px; font: 10.0px Monaco
}
16 p
.p7
{margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Helvetica
}
17 p
.p8
{margin: 0.0px 0.0px 0.0px 0.0px; font: 13.0px Courier
}
18 p
.p9
{margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Monaco
}
19 p
.p10
{margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Helvetica
; min-height: 17.0px}
20 span
.s1
{color: #0019b7}
21 span
.s2
{color: #326f17}
22 span
.s3
{color: #a71e12}
23 span
.s4
{font: 10.0px Monaco
}
24 span
.s5
{color: #000000}
25 span
.Apple-tab-span
{white-space:pre
}
29 <p class=
"p1"><b>List Comprehensions
</b></p>
30 <p class=
"p2"><br></p>
31 <p class=
"p3">List comprehensions are a syntactic feature of functional programming languages like Miranda, Haskell, and Erlang which were later copied into Python.
</p>
32 <p class=
"p3">You can search the web for
"list comprehensions" or
"generator expressions" to learn more.
<span class=
"Apple-converted-space"> </span></p>
33 <p class=
"p3">Basically list comprehensions are for getting a series of solutions to a problem.
</p>
34 <p class=
"p2"><br></p>
35 <p class=
"p3">in SC these are just a syntax macro for a longer expression.
</p>
36 <p class=
"p4"><br></p>
37 <p class=
"p5">// read this as
"all [x,y] for x in 1..5, y in 1..x, such that x+y is prime.</p>
38 <p class="p6
">all {:[x,y], x <- (1..5), y <- (1..x), (x+y).isPrime }</p>
39 <p class="p4
"><br></p>
40 <p class="p6
">[ [ 1, 1 ], [ 2, 1 ], [ 3, 2 ], [ 4, 1 ], [ 4, 3 ], [ 5, 2 ] ]</p>
41 <p class="p4
"><br></p>
42 <p class="p3
">the list comprehension above is equivalent to the following code:</p>
43 <p class="p4
"><br></p>
44 <p class="p6
">all(<span class="s1
">Routine</span>.new({ (1..5).do {<span class="s1
">|x|</span> (1..x).do {<span class="s1
">|y|</span> if ((x+y).isPrime) {[x,y].yield} }}}));</p>
45 <p class="p4
"><br></p>
46 <p class="p3
">..but much more concise and much easier to keep in your head than writing it out.</p>
47 <p class="p2
"><br></p>
48 <p class="p3
">In the list comprehension compiler, simple series like (1..5) and (1..x) are treated as special cases and implemented as loops rather than making a collection.</p>
49 <p class="p2
"><br></p>
50 <p class="p3
">A list comprehension in SC is really a Routine. You can use the 'all' message to collect all of the Routine's results into a list.</p>
51 <p class="p2
"><br></p>
52 <p class="p7
"><b>A few examples</b></p>
53 <p class="p4
"><br></p>
54 <p class="p6
">all {: x/(x+1), x <- (1..5) }</p>
55 <p class="p4
"><br></p>
56 <p class="p6
">[ 0.5, 0.66666666666667, 0.75, 0.8, 0.83333333333333 ]</p>
57 <p class="p4
"><br></p>
58 <p class="p6
">all {:[x,y], x <- (1..3), y <- [<span class="s2
">\a</span>,<span class="s2
">\b</span>,<span class="s2
">\c</span>] }</p>
59 <p class="p4
"><br></p>
60 <p class="p6
">[ [ 1, a ], [ 1, b ], [ 1, c ], [ 2, a ], [ 2, b ], [ 2, c ], [ 3, a ], [ 3, b ], [ 3, c ] ]</p>
61 <p class="p4
"><br></p>
62 <p class="p6
">all {:[x,y], x <- (0..3), y <- (x..0) }</p>
63 <p class="p4
"><br></p>
64 <p class="p6
">[ [ 0, 0 ], [ 1, 1 ], [ 1, 0 ], [ 2, 2 ], [ 2, 1 ], [ 2, 0 ], [ 3, 3 ], [ 3, 2 ], [ 3, 1 ], [ 3, 0 ] ]</p>
65 <p class="p4
"><br></p>
66 <p class="p6
">all {:y, x <- (1..4), y <- (x..1) }</p>
67 <p class="p4
"><br></p>
68 <p class="p6
">[ 1, 2, 1, 3, 2, 1, 4, 3, 2, 1 ]</p>
69 <p class="p4
"><br></p>
70 <p class="p4
"><br></p>
72 <p class="p6
"><span class="s1
">var</span> intervals;</p>
73 <p class="p5
">// a function to generate intervals between all pairs of notes in a chord voicing</p>
74 <p class="p6
">intervals = {<span class="s1
">|chord|</span></p>
75 <p class="p6
"><span class="Apple-tab-span
"> </span>all {: chord[i+gap] - chord[i],<span class="Apple-converted-space
"> </span></p>
76 <p class="p6
"><span class="Apple-tab-span
"> </span><span class="Apple-tab-span
"> </span>gap <- (1 .. chord.lastIndex),<span class="Apple-converted-space
"> </span></p>
77 <p class="p6
"><span class="Apple-tab-span
"> </span><span class="Apple-tab-span
"> </span>i <- (0 .. chord.lastIndex - gap)<span class="Apple-converted-space
"> </span></p>
78 <p class="p6
"><span class="Apple-tab-span
"> </span>}</p>
80 <p class="p4
"><br></p>
81 <p class="p6
">intervals.([0,4,7,10]).postln;</p>
82 <p class="p6
">intervals.([0,1,3,7]).postln;</p>
84 <p class="p2
"><br></p>
85 <p class="p6
">[ 4, 3, 3, 7, 6, 10 ]</p>
86 <p class="p6
">[ 1, 2, 4, 3, 6, 7 ]</p>
87 <p class="p4
"><br></p>
88 <p class="p6
">all {:[y, z], x<-(0..30), <span class="s1
">var</span> y = x.nthPrime, <span class="s1
">var</span> z = 2 ** y - 1, z.asInteger.isPrime.not<span class="Apple-converted-space
"> </span>}</p>
89 <p class="p6
">[ [ 11, 2047 ], [ 23, 8388607 ], [ 29, 536870911 ] ] <span class="s3
">// mersenne numbers which are no primes</span></p>
90 <p class="p2
"><br></p>
91 <p class="p7
"><b>Qualifier Clauses</b></p>
92 <p class="p2
"><br></p>
93 <p class="p3
">A list comprehension begins with <span class="s4
">{: </span>and contains a body followed by several qualifier clauses separated by commas.</p>
94 <p class="p2
"><br></p>
95 <p class="p8
">{: <i>body</i> , <i>qualifiers</i> }</p>
96 <p class="p2
"><br></p>
97 <p class="p3
">There are several types of qualifier clauses that can appear after the body.</p>
98 <p class="p2
"><br></p>
99 <p class="p3
"><b>generator clause</b></p>
100 <p class="p2
"><br></p>
101 <p class="p3
">The basic clause is the generator clause. Its syntax is<span class="Apple-converted-space
"> </span></p>
102 <p class="p2
"><br></p>
103 <p class="p8
"><i>name</i> <- <i>expr</i></p>
104 <p class="p2
"><br></p>
105 <p class="p3
">The expression should be something that can respond meaningfully to 'do' such as a collection or a stream.</p>
106 <p class="p3
">The name takes on each value of the expression.</p>
107 <p class="p3
">The name is a local variable whose scope extends to all clauses to the right. The name is also in scope in the body.</p>
108 <p class="p2
"><br></p>
109 <p class="p6
">all {: x, x <- (1..3) }</p>
110 <p class="p4
"><br></p>
111 <p class="p6
">[ 1, 2, 3 ]</p>
112 <p class="p4
"><br></p>
113 <p class="p6
">all {: x, x <- [\a, \b, \c] }</p>
114 <p class="p4
"><br></p>
115 <p class="p6
">[ a, b, c ]</p>
116 <p class="p4
"><br></p>
117 <p class="p6
">all {: x, x <- (1!3)++(2!2)++3 }</p>
118 <p class="p4
"><br></p>
119 <p class="p6
">[ 1, 1, 1, 2, 2, 3 ]</p>
120 <p class="p4
"><br></p>
121 <p class="p3
">multiple generators act like nested loops.</p>
122 <p class="p4
"><br></p>
123 <p class="p6
">all {: [x,y], x <- (1..2), y <- (10,20..30) }</p>
124 <p class="p4
"><br></p>
125 <p class="p9
">[ [ 1, 10 ], [ 1, 20 ], [ 1, 30 ], [ 2, 10 ], [ 2, 20 ], [ 2, 30 ] ]</p>
126 <p class="p4
"><br></p>
127 <p class="p3
">generators can depend on previous values.</p>
128 <p class="p4
"><br></p>
129 <p class="p6
">all {: x, x <- (1..3), y <- (1..x) }</p>
130 <p class="p4
"><br></p>
131 <p class="p6
">[ 1, 2, 2, 3, 3, 3 ]</p>
132 <p class="p4
"><br></p>
133 <p class="p6
">all {: x, x <- (1..3), y <- (1..4-x) }</p>
134 <p class="p4
"><br></p>
135 <p class="p6
">[ 1, 1, 1, 2, 2, 3 ]</p>
136 <p class="p4
"><br></p>
137 <p class="p4
"><br></p>
138 <p class="p3
"><b>guard clause</b></p>
139 <p class="p2
"><br></p>
140 <p class="p3
">A guard clause is simply an expression. It should return a boolean value.<span class="Apple-converted-space
"> </span></p>
141 <p class="p2
"><br></p>
142 <p class="p8
"><i>expr</i></p>
143 <p class="p4
"><br></p>
144 <p class="p3
">The guard acts as a filter on the results and constrains the search.</p>
145 <p class="p4
"><br></p>
146 <p class="p6
">all {: x, x <- (0..10), x.odd }</p>
147 <p class="p2
"><br></p>
148 <p class="p6
">[ 1, 3, 5, 7, 9 ]</p>
149 <p class="p2
"><br></p>
150 <p class="p3
">x.odd is the guard and causes all even numbers to be skipped.</p>
151 <p class="p2
"><br></p>
152 <p class="p6
">all {: x, x <- (0..30), (x % 5 == 0) || x.isPowerOfTwo }</p>
153 <p class="p4
"><br></p>
154 <p class="p6
">[ 0, 1, 2, 4, 5, 8, 10, 15, 16, 20, 25, 30 ]</p>
155 <p class="p2
"><br></p>
156 <p class="p3
">you can have multiple guards.</p>
157 <p class="p2
"><br></p>
158 <p class="p6
">all {: [x,y], x <- (0..10), (x % 5 == 0) || x.isPowerOfTwo, y <- (1..2), (x+y).even }</p>
159 <p class="p4
"><br></p>
160 <p class="p6
">[ [ 0, 2 ], [ 1, 1 ], [ 2, 2 ], [ 4, 2 ], [ 5, 1 ], [ 8, 2 ], [ 10, 2 ] ]</p>
161 <p class="p2
"><br></p>
162 <p class="p2
"><br></p>
163 <p class="p3
"><b>var clause</b></p>
164 <p class="p2
"><br></p>
165 <p class="p3
">A var clause lets you create a new variable binding that you can use in your expressions.</p>
166 <p class="p3
">The scope of the name extends to all clauses to the right and in the body.</p>
167 <p class="p2
"><br></p>
168 <p class="p8
">var <i>name</i> = <i>expr</i></p>
169 <p class="p2
"><br></p>
170 <p class="p3
">Unlike the generator clause, the name is bound to a single value, it doesn't iterate.</p>
171 <p class="p2
"><br></p>
172 <p class="p6
">all {: z, x <- (1..20), <span class="s1
">var</span> z = (x*x-x) div: 2, z.odd }</p>
173 <p class="p2
"><br></p>
174 <p class="p6
">[ 1, 3, 15, 21, 45, 55, 91, 105, 153, 171 ]</p>
175 <p class="p2
"><br></p>
176 <p class="p2
"><br></p>
177 <p class="p3
"><b>side effect clause</b></p>
178 <p class="p2
"><br></p>
179 <p class="p3
">This clause lets you insert code to do some side effect like printing.</p>
180 <p class="p2
"><br></p>
181 <p class="p8
">:: <i>expr</i></p>
182 <p class="p2
"><br></p>
183 <p class="p6
">all {: z, x <- (1..20), <span class="s1
">var</span> z = (x*x-x) div: 2, :: [x,z].postln, z.even }</p>
184 <p class="p4
"><br></p>
185 <p class="p2
"><br></p>
186 <p class="p3
"><b>termination clause</b></p>
187 <p class="p2
"><br></p>
188 <p class="p3
">The termination clause is for stopping further searching for results. Once the expression becomes false,</p>
189 <p class="p3
">the routine halts.</p>
190 <p class="p2
"><br></p>
191 <p class="p8
">:while <i>expr</i></p>
192 <p class="p2
"><br></p>
193 <p class="p5
">// using a guard</p>
194 <p class="p6
">all {: z, x <- (1..20), <span class="s1
">var</span> z = (x*x-x) div: 2,<span class="Apple-converted-space
"> </span>:: [x,z].postln, z < 50 }</p>
195 <p class="p4
"><br></p>
196 <p class="p5
">// using a termination clause</p>
197 <p class="p5
">// this one stops searching, so does less work than the above.</p>
198 <p class="p6
">all {: z, x <- (1..20), <span class="s1
">var</span> z = (x*x-x) div: 2,<span class="Apple-converted-space
"> </span>:: [x,z].postln, :while z < 50 }</p>
199 <p class="p2
"><br></p>
200 <p class="p7
"><b>Constrained Search</b></p>
201 <p class="p2
"><br></p>
202 <p class="p3
">list comprehensions can solve constrained combinatorial problems like this one:</p>
203 <p class="p2
"><br></p>
204 <p class="p3
">Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors.</p>
205 <p class="p3
">Baker does not live on the top floor. Cooper does not live on the bottom floor.</p>
206 <p class="p3
">Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper.</p>
207 <p class="p3
">Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's.</p>
208 <p class="p3
">Where does everyone live?</p>
209 <p class="p2
"><br></p>
211 <p class="p6
">z = {: [baker, cooper, fletcher, miller, smith] ,</p>
212 <p class="p6
"><span class="Apple-tab-span
"> </span><span class="s1
">var</span> floors = (1..5),</p>
213 <p class="p5
"><span class="s5
"><span class="Apple-tab-span
"> </span>baker <- floors,<span class="Apple-converted-space
"> </span>baker != 5,<span class="Apple-converted-space
"> </span></span>// Baker does not live on the top floor.</p>
214 <p class="p5
"><span class="s5
"><span class="Apple-tab-span
"> </span></span>// remove baker's floor from the list. var creates a new scope, so the 'floors' on the left is a new binding.</p>
215 <p class="p6
"><span class="Apple-tab-span
"> </span><span class="s1
">var</span> floors = floors.removing(baker),<span class="Apple-converted-space
"> </span></p>
216 <p class="p5
"><span class="s5
"><span class="Apple-tab-span
"> </span>cooper <- floors, cooper != 1, </span>// Cooper does not live on the bottom floor.</p>
217 <p class="p5
"><span class="s5
"><span class="Apple-tab-span
"> </span></span><span class="s1
">var</span><span class="s5
"> floors = floors.removing(cooper), </span>// remove cooper's floor from the list.</p>
218 <p class="p5
"><span class="s5
"><span class="Apple-tab-span
"> </span>fletcher <- floors, (fletcher != 5) && (fletcher != 1) </span>// Fletcher does not live on either the top or the bottom floor.</p>
219 <p class="p5
"><span class="s5
"><span class="Apple-tab-span
"> </span><span class="Apple-tab-span
"> </span><span class="Apple-tab-span
"> </span><span class="Apple-tab-span
"> </span><span class="Apple-tab-span
"> </span>&& (absdif(fletcher, cooper) > 1), </span>// Fletcher does not live on a floor adjacent to Cooper's.</p>
220 <p class="p6
"><span class="Apple-tab-span
"> </span><span class="s1
">var</span> floors = floors.removing(fletcher), <span class="s3
">// remove fletcher's floor</span></p>
221 <p class="p5
"><span class="s5
"><span class="Apple-tab-span
"> </span>miller <- floors, miller > cooper, </span>// Miller lives on a higher floor than does Cooper.</p>
222 <p class="p6
"><span class="Apple-tab-span
"> </span><span class="s1
">var</span> floors = floors.removing(miller), <span class="s3
">// remove miller's floor</span></p>
223 <p class="p5
"><span class="s5
"><span class="Apple-tab-span
"> </span>smith <- floors, absdif(fletcher, smith) > 1<span class="Apple-converted-space
"> </span></span>// Smith does not live on a floor adjacent to Fletcher's.</p>
226 <p class="p4
"><br></p>
227 <p class="p5
"><span class="s5
">z.next; </span>// [3, 2, 4, 5, 1 ]</p>
228 <p class="p5
"><span class="s5
">z.next; </span>// nil.<span class="Apple-converted-space
"> </span>only one solution</p>
229 <p class="p4
"><br></p>
230 <p class="p3
">combinatorial problems can take a lot of time to run.</p>
231 <p class="p3
">you can reorder the above tests to make it run faster. generally you want to search the most constrained variables first.</p>
232 <p class="p3
">the most constrained person above is fletcher, so he should be searched first, then cooper, etc.</p>
233 <p class="p4
"><br></p>
234 <p class="p4
"><br></p>
235 <p class="p4
"><br></p>
236 <p class="p7
"><b>Grammar:</b></p>
237 <p class="p10
"><br></p>
238 <p class="p3
">Here is the BNF grammar for list comprehensions in SC.</p>
239 <p class="p4
"><br></p>
240 <p class="p6
">[ ] - optional</p>
241 <p class="p6
">{ } - zero or more</p>
242 <p class="p4
"><br></p>
243 <p class="p6
"><list_compre> ::= "{:
" <body> ',' <qualifiers> "}
"</p>
244 <p class="p4
"><br></p>
245 <p class="p6
"><body> ::= <exprseq></p>
246 <p class="p4
"><br></p>
247 <p class="p6
"><exprseq> ::= <expr> { ";
" <expr> }</p>
248 <p class="p4
"><br></p>
249 <p class="p6
"><qualifiers> ::= <qualifier> { ',' <qualifiers> }</p>
250 <p class="p4
"><br></p>
251 <p class="p6
"><qualifier> ::= <generator> | <guard> | <binding> | <side_effect> | <termination></p>
252 <p class="p4
"><br></p>
253 <p class="p6
"><generator> ::= <name> "<-
" <exprseq></p>
254 <p class="p4
"><br></p>
255 <p class="p6
"><guard> ::= <exprseq></p>
256 <p class="p4
"><br></p>
257 <p class="p6
"><binding> ::= "var
" <name> "=
" <exprseq></p>
258 <p class="p4
"><br></p>
259 <p class="p6
"><side_effect> ::= "::
" <exprseq></p>
260 <p class="p4
"><br></p>
261 <p class="p6
"><termination> ::= ":while
" <exprseq></p>
262 <p class="p4
"><br></p>
263 <p class="p4
"><br></p>
264 <p class="p7
"><b>Code Generation:</b></p>
265 <p class="p4
"><br></p>
266 <p class="p3
">For each of the above clauses, here is how the code is generated. The body acts as the innermost qualifier.</p>
267 <p class="p3
">By understanding these translations, you can better understand how scoping and control flow work in list comprehensions.</p>
268 <p class="p4
"><br></p>
269 <p class="p3
"><b>generator:</b></p>
270 <p class="p4
"><br></p>
271 <p class="p6
">expr.do {|name| ..next qualifier.. }</p>
272 <p class="p4
"><br></p>
273 <p class="p4
"><br></p>
274 <p class="p3
"><b>guard:</b></p>
275 <p class="p4
"><br></p>
276 <p class="p6
">if (expr) { ..next qualifier.. }</p>
277 <p class="p4
"><br></p>
278 <p class="p4
"><br></p>
279 <p class="p3
"><b>binding:</b></p>
280 <p class="p4
"><br></p>
281 <p class="p6
">{|name| ..next qualifier.. }.value(expr)</p>
282 <p class="p4
"><br></p>
283 <p class="p4
"><br></p>
284 <p class="p3
"><b>side effect:</b></p>
285 <p class="p4
"><br></p>
286 <p class="p6
">expr ; ..next qualifier..</p>
287 <p class="p4
"><br></p>
288 <p class="p4
"><br></p>
289 <p class="p3
"><b>termination:</b></p>
290 <p class="p4
"><br></p>
291 <p class="p6
">if (expr) { ..next qualifier.. }{ nil.alwaysYield }</p>
292 <p class="p4
"><br></p>
