-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathuso-avanzato-degli-iteratori.html
647 lines (538 loc) · 51.1 KB
/
uso-avanzato-degli-iteratori.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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
<!DOCTYPE html>
<meta charset=utf-8>
<title>Uso avanzato degli iteratori - Immersione in Python 3</title>
<!--[if IE]><script src=j/html5.js></script><![endif]-->
<link rel=stylesheet href=dip3.css>
<style>
body{counter-reset:h1 8}
mark{display:inline}
</style>
<link rel=stylesheet media='only screen and (max-device-width: 480px)' href=mobile.css>
<link rel=stylesheet media=print href=print.css>
<meta name=viewport content='initial-scale=1.0'>
<form action=http://www.google.com/cse><div><input type=hidden name=cx value=014021643941856155761:l5eihuescdw><input type=hidden name=ie value=UTF-8> <input type=search name=q size=25 placeholder="powered by Google™"> <input type=submit name=sa value=Search></div></form>
<p>Voi siete qui: <a href=index.html>Inizio</a> <span class=u>‣</span> <a href=indice.html#uso-avanzato-degli-iteratori>Immersione in Python 3</a> <span class=u>‣</span>
<p id=level>Livello di difficoltà: <span class=u title=avanzato>♦♦♦♦♢</span>
<h1>Uso avanzato degli iteratori</h1>
<blockquote class=q>
<p><span class=u>❝</span> Le grandi pulci portano piccole pulci che le mordono con appetito,<br>e le pulci piccole hanno pulci più piccole, e così via all’infinito. <span class=u>❞</span><br>— Augustus De Morgan
</blockquote>
<p id=toc>
<h2 id=divingin>Immersione!</h2>
<p class=f>Laddove le <a href=espressioni-regolari.html>espressioni regolari</a> accrescono enormemente le funzionalità delle <a href=stringhe.html>stringhe</a>, il modulo <code>itertools</code> agisce allo stesso modo nei confronti degli <a href=iteratori.html>iteratori</a>. Ma prima di esaminare le meraviglie di questo modulo, voglio mostrarvi un classico rompicapo.
<pre class=nd><code>HAWAII + IDAHO + IOWA + OHIO == STATES
510199 + 98153 + 9301 + 3593 == 621246
H = 5
A = 1
W = 0
I = 9
D = 8
O = 3
S = 6
T = 2
E = 4</code></pre>
<p>Rompicapi come questi sono chiamati <i>criptarismi</i> o più precisamente criptarismi <i>alfametici</i>. Le lettere formano parole vere, ma se sostituite ogni lettera con una cifra da 0 a <code>9</code> il rompicapo “forma” anche un’equazione aritmetica. Il trucco è scoprire quali lettere corrispondono a quali cifre. Tutte le occorrenze di ogni lettera devono corrispondere alla stessa cifra, nessuna cifra può essere ripetuta e nessuna “parola” può cominciare con la cifra 0.
<aside>Il rompicapo alfametico più conosciuto è <code>SEND + MORE = MONEY</code>.</aside>
<p>In questo capitolo, analizzeremo un incredibile programma Python originariamente scritto da Raymond Hettinger. Questo programma risolve rompicapi di alfametica <em>in sole 14 righe di codice</em>.
<p class=d>[<a href=esempi/alphametics.py>scarica <code>alphametics.py</code></a>]
<pre class=pp><code>import re
import itertools
def solve(puzzle):
words = re.findall('[A-Z]+', puzzle.upper())
unique_characters = set(''.join(words))
assert len(unique_characters) <= 10, 'Troppe lettere'
first_letters = {word[0] for word in words}
n = len(first_letters)
sorted_characters = ''.join(first_letters) + \
''.join(unique_characters - first_letters)
characters = tuple(ord(c) for c in sorted_characters)
digits = tuple(ord(c) for c in '0123456789')
zero = digits[0]
for guess in itertools.permutations(digits, len(characters)):
if zero not in guess[:n]:
equation = puzzle.translate(dict(zip(characters, guess)))
if eval(equation):
return equation
if __name__ == '__main__':
import sys
for puzzle in sys.argv[1:]:
print(puzzle)
solution = solve(puzzle)
if solution:
print(solution)</code></pre>
<p>Potete eseguire il programma dalla riga di comando. Su Linux, avrete qualcosa di simile a questo. (Le seguenti esecuzioni potrebbero impiegare un po’ di tempo a seconda della velocità del vostro computer, e non c’è nessun indicatore di progresso. Siate pazienti!)
<pre class='nd screen'>
<samp class=p>you@localhost:~/diveintopython3/esempi$ </samp><kbd>python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO = STATES"</kbd>
<samp>HAWAII + IDAHO + IOWA + OHIO = STATES
510199 + 98153 + 9301 + 3593 == 621246</samp>
<samp class=p>you@localhost:~/diveintopython3/esempi$ </samp><kbd>python3 alphametics.py "I + LOVE + YOU == DORA"</kbd>
<samp>I + LOVE + YOU == DORA
1 + 2784 + 975 == 3760</samp>
<samp class=p>you@localhost:~/diveintopython3/esempi$ </samp><kbd>python3 alphametics.py "SEND + MORE == MONEY"</kbd>
<samp>SEND + MORE == MONEY
9567 + 1085 == 10652</samp></pre>
<p class=a>⁂
<h2 id=re-findall>Trovare tutte le occorrenze di un pattern</h2>
<p>Come prima cosa, questo risolutore di alfametica trova tutte le lettere (A–Z) nel rompicapo.
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>import re</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>re.findall('[0-9]+', '16 pezzi 2x4 in righe di 8')</kbd> <span class=u>①</span></a>
<samp class=pp>['16', '2', '4', '8']</samp>
<a><samp class=p>>>> </samp><kbd class=pp>re.findall('[A-Z]+', 'SEND + MORE == MONEY')</kbd> <span class=u>②</span></a>
<samp class=pp>['SEND', 'MORE', 'MONEY']</samp></pre>
<ol>
<li>Il modulo <code>re</code> è l’implementazione Python delle <a href=espressioni-regolari.html>espressioni regolari</a>. Include un’elegante funzione chiamata <code>findall()</code> che accetta un pattern di espressione regolare e una stringa e trova tutte le occorrenze del pattern all’interno della stringa. In questo caso il pattern corrisponde a sequenze di numeri. La funzione <code>findall()</code> restituisce una lista di tutte le sottostringhe che corrispondono al pattern.
<li>Qui il pattern di espressione regolare corrisponde a sequenze di lettere. Ancora una volta, il valore di ritorno è una lista e ogni elemento nella lista è una stringa che corrisponde a quel pattern di espressione regolare.
</ol>
<p>Ecco un altro esempio per mettere alla prova la vostra mente.
<pre class='nd screen'>
<samp class=p>>>> </samp><kbd class=pp>re.findall(' c.*? c', 'Chi ama chiama chi ama, chiamami tu che chi ami chiami.')</kbd>
<samp class=pp>[' chiama c', ' chiamami tu c', ' chi ami c']</samp></pre>
<aside>Questo è uno degli <a href=http://it.wikipedia.org/wiki/Scioglilingua>scioglilingua più facili</a> che esistono in italiano.</aside>
<p>Sorpresi? L’espressione regolare cerca uno spazio, una <code>c</code> e poi la serie di caratteri più corta possibile contenente qualsiasi carattere (<code>.*?</code>), poi uno spazio, poi un’altra <code>c</code>. Bene, guardando la stringa in ingresso, vedo cinque corrispondenze:
<ol>
<li><code>Chi ama<mark> chiama c</mark>hi ama, chiamami tu che chi ami chiami.</code>
<li><code>Chi ama chiama<mark> chi ama, c</mark>hiamami tu che chi ami chiami.</code>
<li><code>Chi ama chiama chi ama,<mark> chiamami tu c</mark>he chi ami chiami.</code>
<li><code>Chi ama chiama chi ama, chiamami tu<mark> che c</mark>hi ami chiami.</code>
<li><code>Chi ama chiama chi ama, chiamami tu che<mark> chi ami c</mark>hiami.</code>
</ol>
<p>Ma la funzione <code>re.findall()</code> resituisce solo tre corrispondenze. Nello specifico, restituisce la prima, la terza e la quinta. Come mai? Perché <em>non restituisce corrispondenze sovrapposte</em>. La prima corrispondenza si sovrappone alla seconda, quindi la prima viene restituita e la seconda viene saltata. Poi la terza si sovrappone alla quarta, quindi la terza viene restituita e la quarta viene saltata. Infine, la quinta viene restituita. Tre corrispondenze, non cinque.
<p>Questo non ha nulla a che fare con il risolutore di alfametica; ho solo pensato che fosse interessante.
<p class=a>⁂
<h2 id=unique-items>Eliminare gli elementi ripetuti da una sequenza</h2>
<p>Gli <a href=tipi-di-dato-nativi.html#sets>insiemi</a> rendono banale eliminare gli elementi ripetuti da una sequenza.
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>a_list = ['Chi', 'ama', 'chiama', 'chi', 'ama', 'chiamami', 'tu', 'che', 'ami', 'chi', 'chiami']</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>set(a_list)</kbd> <span class=u>①</span></a>
<samp class=pp>{'ami', 'che', 'ama', 'Chi', 'tu', 'chi', 'chiamami', 'chiama', 'chiami'}</samp>
<samp class=p>>>> </samp><kbd class=pp>a_string = 'EAST IS EAST'</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>set(a_string)</kbd> <span class=u>②</span></a>
<samp class=pp>{'A', ' ', 'E', 'I', 'S', 'T'}</samp>
<samp class=p>>>> </samp><kbd class=pp>words = ['SEND', 'MORE', 'MONEY']</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>''.join(words)</kbd> <span class=u>③</span></a>
<samp class=pp>'SENDMOREMONEY'</samp>
<a><samp class=p>>>> </samp><kbd class=pp>set(''.join(words))</kbd> <span class=u>④</span></a>
<samp class=pp>{'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}</samp></pre>
<ol>
<li>Data una lista contenente diverse stringhe, la funzione <code>set()</code> restituirà un insieme di stringhe uniche a partire dalla lista. Questa operazione ha senso se la pensate come un ciclo <code>for</code>. Prendete il primo elemento della lista, mettetelo nell’insieme. Il secondo. Il terzo. Il quarto. Il quinto — aspettate, questo è già nell’insieme, quindi va elencato solo una volta, perché gli insiemi Python non accettano ripetizioni. Il sesto, il settimo, l’ottavo, il nono. Poi il decimo — anche questo elemento è ripetuto, quindi va elencato solo una volta. E l’undicesimo. Il risultato finale? Un insieme di elementi unici creato a partire dalla lista originale, senza alcuna ripetizione. La lista originale non va nemmeno ordinata prima.
<li>La stessa tecnica funziona con le stringhe, dato che una stringa è solamente una sequenza di caratteri.
<li>Data una lista di stringhe, <code>''.join(<var>lista</var>)</code> le concatena tutte in un’unica stringa.
<li>Quindi, data una lista di stringhe, questa riga di codice restituisce un insieme di caratteri unici senza alcuna ripetizione creato a partire da tutte le stringhe.
</ol>
<p>Il risolutore di alfametica usa questa tecnica per ottenere un insieme di tutti i caratteri unici nel rompicapo.
<pre class='nd pp'><code>unique_characters = set(''.join(words))</code></pre>
<p>Questo insieme viene successivamente usato per assegnare le cifre ai caratteri man mano che il risolutore itera attraverso le possibili soluzioni.
<p class=a>⁂
<h2 id=assert>Fare asserzioni</h2>
<p>Come molti linguaggi di programmazione, Python possiede un’istruzione <code>assert</code>. Ecco come funziona.
<pre class=screen>
<a><samp class=p>>>> </samp><kbd class=pp>assert 1 + 1 == 2</kbd> <span class=u>①</span></a>
<a><samp class=p>>>> </samp><kbd class=pp>assert 1 + 1 == 3</kbd> <span class=u>②</span></a>
<samp class=traceback>Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AssertionError</samp>
<a><samp class=p>>>> </samp><kbd class=pp>assert 2 + 2 == 5, "Solo per valori molto grandi di 2"</kbd> <span class=u>③</span></a>
<samp class=traceback>Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AssertionError: Solo per valori molto grandi di 2</samp></pre>
<ol>
<li>L’istruzione <code>assert</code> è seguita da una qualsiasi espressione Python valida. In questo caso l’espressione <code>1 + 1 == 2</code> viene valutata a <code>True</code>, quindi l’istruzione <code>assert</code> non fa nulla.
<li>Tuttavia, se l’espressione Python viene valutata a <code>False</code>, l’istruzione <code>assert</code> solleverà un’eccezione di tipo <code>AssertionError</code>.
<li>Potete anche includere un messaggio di spiegazione che viene stampato nel caso l’eccezione <code>AssertionError</code> venga sollevata.
</ol>
<p>Perciò, questa riga di codice:
<pre class='nd pp'><code>assert len(unique_characters) <= 10, 'Troppe lettere'</code></pre>
<p>…equivale a queste due righe:
<pre class='nd pp'><code>if len(unique_characters) > 10:
raise AssertionError('Troppe lettere')</code></pre>
<p>Il risolutore di alfametica usa proprio questa istruzione <code>assert</code> per interrompere la propria esecuzione nel caso il rompicapo contenga più di dieci lettere uniche. Dato che a ogni lettera viene assegnata una singola cifra e che ci sono solo dieci cifre, un rompicapo con più di dieci lettere uniche non può avere una soluzione.
<p class=a>⁂
<h2 id=generator-expressions>Espressioni generatore</h2>
<p>Un’espressione generatore è come una <a href=generatori.html>funzione generatore</a> senza la funzione.
<pre class=screen>
<samp>>>> </samp><kbd class=pp>unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}</kbd>
<a><samp>>>> </samp><kbd class=pp>gen = (ord(c) for c in unique_characters)</kbd> <span class=u>①</span></a>
<a><samp>>>> </samp><kbd class=pp>gen</kbd> <span class=u>②</span></a>
<samp><generator object <genexpr> at 0x00BADC10></samp>
<a><samp>>>> </samp><kbd class=pp>next(gen)</kbd> <span class=u>③</span></a>
<samp class=pp>69</samp>
<samp>>>> </samp><kbd class=pp>next(gen)</kbd>
<samp class=pp>68</samp>
<a><samp>>>> </samp><kbd class=pp>tuple(ord(c) for c in unique_characters)</kbd> <span class=u>④</span></a>
<samp class=pp>(69, 68, 77, 79, 78, 83, 82, 89)</samp></pre>
<ol>
<li>Un’espressione generatore è come una funzione anonima che produce valori. L’espressione stessa somiglia a una <a href=descrizioni.html#listcomprehension>descrizione di lista</a>, ma è circondata da parentesi tonde invece che parentesi quadre.
<li>Un’espressione generatore restitiusce… un iteratore.
<li>Invocare <code>next(<var>gen</var>)</code> restituisce il valore successivo dell’iteratore.
<li>Se volete, potete iterare attraverso tutti i possibili valori e restituire una tupla, una lista, o un insieme passando l’espressione generatore a <code>tuple()</code>, <code>list()</code>, o <code>set()</code>. In questi casi non avete bisogno di un insieme aggiuntivo di parentesi — vi basta passare l’espressione <code>ord(c) for c in unique_characters</code> “nuda e cruda” alla funzione <code>tuple()</code> e Python scoprirà che è un’espressione generatore.
</ol>
<blockquote class=note>
<p><span class=u>☞</span>Usare un’espressione generatore invece di una descrizione di lista può risparmiare sia <abbr>CPU</abbr> che <abbr>RAM</abbr>. Se state costruendo una lista solo per buttarla via (per esempio, passandola a <code>tuple()</code> o <code>set()</code>), è meglio usare un’espressione generatore!
</blockquote>
<p>Ecco un altro modo di realizzare la stessa cosa, utilizzando una <a href=generatori.html>funzione generatore</a>:
<pre class='nd pp'><code>def ord_map(a_string):
for c in a_string:
yield ord(c)
gen = ord_map(unique_characters)</code></pre>
<p>L’espressione generatore è più compatta, ma funzionalmente equivalente.
<p class=a>⁂
<h2 id=permutations>Calcolare le permutazioni… in maniera ritardata!</h2>
<p>Prima di tutto, cosa diavolo sono le permutazioni? Le permutazioni sono un concetto matematico. (Ci sono effettivamente diverse definizioni, a seconda di quale matematica state utilizzando. Qui sto parlando di combinatoria, ma se questo non vi dice niente, non preoccupatevi. Come sempre, <a href=http://it.wikipedia.org/wiki/Permutazioni>Wikipedia è vostra amica</a>.)
<p>L’idea alla base delle permutazioni è quella di prendere una lista di cose (potrebbero essere numeri, potrebbero essere lettere, potrebbero essere orsi danzanti) e trovare tutti i modi possibili per dividerla in liste più piccole. Tutte le liste più piccole hanno la stessa dimensione, che può essere tanto piccola quanto 1 e tanto grande quanto il numero totale degli elementi. Oh, e nessun oggetto può essere ripetuto. I matematici dicono cose come “troviamo le permutazioni di 3 elementi differenti presi 2 alla volta”, che significa trovare tutte le possibili coppie ordinate a partire da una sequenza di 3 elementi.
<pre class=screen>
<a><samp class=p>>>> </samp><kbd class=pp>import itertools</kbd> <span class=u>①</span></a>
<a><samp class=p>>>> </samp><kbd class=pp>perms = itertools.permutations([1, 2, 3], 2)</kbd> <span class=u>②</span></a>
<a><samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd> <span class=u>③</span></a>
<samp class=pp>(1, 2)</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>(1, 3)</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<a><samp class=pp>(2, 1)</samp> <span class=u>④</span></a>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>(2, 3)</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>(3, 1)</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>(3, 2)</samp>
<a><samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd> <span class=u>⑤</span></a>
<samp class=traceback>Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration</samp></pre>
<ol>
<li>Il modulo <code>itertools</code> contiene i più svariati tipi di roba divertente, compresa una funzione <code>permutations()</code> che si sobbarca tutto il duro lavoro della ricerca di permutazioni.
<li>La funzione <code>permutations()</code> prende una sequenza (qui una lista di tre interi) e un numero, che è il numero di elementi che volete includere in ogni gruppo più piccolo. La funzione restituisce un iteratore, che potete usare in un ciclo <code>for</code> o dovunque sia richiesto un oggetto iterabile. Qui attraverserò l’iteratore manualmente per mostrare tutti i valori.
<li>La prima permutazione degli elementi di <code>[1, 2, 3]</code> presi 2 alla volta è <code>(1, 2)</code>.
<li>Notate che le permutazioni sono ordinate: <code>(2, 1)</code> è diversa da <code>(1, 2)</code>.
<li>Ecco qua! Quelle che abbiamo visto sono tutte le permutazioni degli elementi di <code>[1, 2, 3]</code> presi 2 alla volta. Coppie come <code>(1, 1)</code> e <code>(2, 2)</code> non compaiono mai, perché contengono ripetizioni e quindi non sono permutazioni valide. Quando non ci sono più permutazioni, l’iteratore solleva un’eccezione di tipo <code>StopIteration</code>.
</ol>
<aside>Il modulo <code>itertools</code> contiene i più svariati tipi di roba divertente.</aside>
<p>La funzione <code>permutations()</code> non deve per forza prendere una lista. Può accettare qualsiasi sequenza — persino una stringa.
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>import itertools</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>perms = itertools.permutations('ABC', 3)</kbd> <span class=u>①</span></a>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<a><samp class=pp>('A', 'B', 'C')</samp> <span class=u>②</span></a>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>('A', 'C', 'B')</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>('B', 'A', 'C')</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>('B', 'C', 'A')</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>('C', 'A', 'B')</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=pp>('C', 'B', 'A')</samp>
<samp class=p>>>> </samp><kbd class=pp>next(perms)</kbd>
<samp class=traceback>Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration</samp>
<a><samp class=p>>>> </samp><kbd class=pp>list(itertools.permutations('ABC', 3))</kbd> <span class=u>③</span></a>
<samp class=pp>[('A', 'B', 'C'), ('A', 'C', 'B'),
('B', 'A', 'C'), ('B', 'C', 'A'),
('C', 'A', 'B'), ('C', 'B', 'A')]</samp></pre>
<ol>
<li>Una stringa è semplicemente una sequenza di caratteri. Allo scopo di trovare permutazioni, la stringa <code>'ABC'</code> è equivalente alla lista <code>['A', 'B', 'C']</code>.
<li>La prima permutazione dei 3 elementi in <code>['A', 'B', 'C']</code> presi 3 alla volta è <code>('A', 'B', 'C')</code>. Esistono altre cinque permutazioni — gli stessi tre caratteri in ogni ordine possibile.
<li>Dato che la funzione <code>permutations()</code> restituisce sempre un iteratore, si può facilmente effettuare il debug sulle permutazioni passando l’iteratore alla funzione built-in <code>list()</code> per vedere immediatamente tutte le permutazioni.
</ol>
<p class=a>⁂
<h2 id=more-itertools>Altra roba divertente nel modulo <code>itertools</code></h2>
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>import itertools</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>list(itertools.product('ABC', '123'))</kbd> <span class=u>①</span></a>
<samp class=pp>[('A', '1'), ('A', '2'), ('A', '3'),
('B', '1'), ('B', '2'), ('B', '3'),
('C', '1'), ('C', '2'), ('C', '3')]</samp>
<a><samp class=p>>>> </samp><kbd class=pp>list(itertools.combinations('ABC', 2))</kbd> <span class=u>②</span></a>
<samp class=pp>[('A', 'B'), ('A', 'C'), ('B', 'C')]</samp></pre>
<ol>
<li>La funzione <code>itertools.product()</code> restituisce un iteratore contenente il prodotto cartesiano di due sequenze.
<li>La funzione <code>itertools.combinations()</code> restituisce un iteratore contenente tutte le possibili combinazioni di lunghezza data a partire dalla sequenza data. Questa funzione si comporta come la funzione <code>itertools.permutations()</code>, a parte il fatto che le combinazioni non includono elementi che siano una copia di altri elementi in ordine differente. Quindi <code>itertools.permutations('ABC', 2)</code> restituirà sia <code>('A', 'B')</code> che <code>('B', 'A')</code> (tra le altre), ma <code>itertools.combinations('ABC', 2)</code> non restituirà <code>('B', 'A')</code> perché è una copia di <code>('A', 'B')</code> con un diverso ordine degli elementi.
</ol>
<p class=d>[<a href=esempi/favorite-people.txt>scarica <code>favorite-people.txt</code></a>]
<pre class=screen>
<a><samp class=p>>>> </samp><kbd class=pp>names = list(open('esempi/favorite-people.txt', encoding='utf-8'))</kbd> <span class=u>①</span></a>
<samp class=p>>>> </samp><kbd class=pp>names</kbd>
<samp class=pp>['Dora\n', 'Ethan\n', 'Wesley\n', 'John\n', 'Anne\n',
'Mike\n', 'Chris\n', 'Sarah\n', 'Alex\n', 'Lizzie\n']</samp>
<a><samp class=p>>>> </samp><kbd class=pp>names = [name.rstrip() for name in names]</kbd> <span class=u>②</span></a>
<samp class=p>>>> </samp><kbd class=pp>names</kbd>
<samp class=pp>['Dora', 'Ethan', 'Wesley', 'John', 'Anne',
'Mike', 'Chris', 'Sarah', 'Alex', 'Lizzie']</samp>
<a><samp class=p>>>> </samp><kbd class=pp>names = sorted(names)</kbd> <span class=u>③</span></a>
<samp class=p>>>> </samp><kbd class=pp>names</kbd>
<samp class=pp>['Alex', 'Anne', 'Chris', 'Dora', 'Ethan',
'John', 'Lizzie', 'Mike', 'Sarah', 'Wesley']</samp>
<a><samp class=p>>>> </samp><kbd class=pp>names = sorted(names, key=len)</kbd> <span class=u>④</span></a>
<samp class=p>>>> </samp><kbd class=pp>names</kbd>
<samp class=pp>['Alex', 'Anne', 'Dora', 'John', 'Mike',
'Chris', 'Ethan', 'Sarah', 'Lizzie', 'Wesley']</samp></pre>
<ol>
<li>Questo idioma restituisce una lista delle righe in un file di testo.
<li>Sfortunatamente (per questo esempio), l’idioma <code>list(open(<var>nomedelfile</var>))</code> include anche i ritorni a capo alla fine di ogni riga. Questa descrizione di lista usa il metodo <code>rstrip()</code> delle stringhe per togliere lo spazio bianco alla fine di ogni riga. (Le stringhe sono anche dotate di un metodo <code>lstrip()</code> per togliere lo spazio bianco all’inizio e di un metodo <code>strip()</code> che toglie lo spazio bianco sia all’inizio che alla fine.)
<li>La funzione <code>sorted()</code> prende una lista e la restituisce ordinata. L’ordine predefinito è quello alfabetico.
<li>Ma la funzione <code>sorted()</code> può anche prendere una funzione come parametro <var>key</var> e ordinare in base a essa. In questo caso la funzione di ordinamento è <code>len()</code>, quindi questa invocazione ordina sulla base della lunghezza di ogni elemento calcolando <code>len(<var>ogni_elemento</var>)</code>. I nomi più corti vengono prima, poi quelli più lunghi, poi quelli ancora più lunghi.
</ol>
<p>Che cos’ha a che fare tutto questo con il modulo <code>itertools</code>? Sono contento che lo abbiate chiesto.
<pre class=screen>
…continuando dalla shell interattiva precedente…
<samp class=p>>>> </samp><kbd class=pp>import itertools</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>groups = itertools.groupby(names, len)</kbd> <span class=u>①</span></a>
<samp class=p>>>> </samp><kbd class=pp>groups</kbd>
<samp><itertools.groupby object at 0x00BB20C0></samp>
<samp class=p>>>> </samp><kbd class=pp>list(groups)</kbd>
<samp class=pp>[(4, <itertools._grouper object at 0x00BA8BF0>),
(5, <itertools._grouper object at 0x00BB4050>),
(6, <itertools._grouper object at 0x00BB4030>)]</samp>
<a><samp class=p>>>> </samp><kbd class=pp>groups = itertools.groupby(names, len)</kbd> <span class=u>②</span></a>
<a><samp class=p>>>> </samp><kbd class=pp>for name_length, name_iter in groups:</kbd> <span class=u>③</span></a>
<samp class=p>... </samp><kbd class=pp> print('Nomi con {0:d} lettere:'.format(name_length))</kbd>
<samp class=p>... </samp><kbd class=pp> for name in name_iter:</kbd>
<samp class=p>... </samp><kbd class=pp> print(name)</kbd>
<samp class=p>... </samp>
<samp>Nomi con 4 lettere:
Alex
Anne
Dora
John
Mike
Nomi con 5 lettere:
Chris
Ethan
Sarah
Nomi con 6 lettere:
Lizzie
Wesley</samp></pre>
<ol>
<li>La funzione <code>itertools.groupby()</code> prende una sequenza e una funzione chiave e restituisce un iteratore che genera coppie. Ogni coppia è composta dal risultato dell’applicazione della funzione chiave a ogni elemento (<code>funzione_chiave(<var>ogni_elemento</var>)</code>) e da un altro iteratore che contiene tutti gli elementi che condividono quel risultato.
<li>L’invocazione della funzione <code>list()</code> ha “esaurito” l’iteratore, cioè avete già generato tutti gli elementi nell’iteratore per costruire la lista. Non c’è nessun pulsante di “reset” su un iteratore, perciò non potete semplicemente ricominciare da capo una volta che lo avete esaurito. Se volete attraversarlo di nuovo (diciamo, nel ciclo <code>for</code> successivo) dovete chiamare ancora <code>itertools.groupby()</code> per creare un nuovo iteratore.
<li>In questo esempio, data una lista di nomi <em>già ordinata per lunghezza</em>, <code>itertools.groupby(names, len)</code> metterà tutti i nomi di 4 lettere in un iteratore, tutti i nomi di 5 lettere in un altro iteratore, e così via. La funzione <code>groupby()</code> è completamente generica; potrebbe raggruppare stringhe sulla base della prima lettera, numeri sulla base del loro numero di fattori oppure utilizzando qualsiasi altra funzione chiave che vi possa venire in mente.
</ol>
<!-- YO DAWG, WE HEARD YOU LIKE LOOPING, SO WE PUT AN ITERATOR IN YOUR ITERATOR SO YOU CAN LOOP WHILE YOU LOOP. -->
<blockquote class=note>
<p><span class=u>☞</span>La funzione <code>itertools.groupby()</code> funziona solo se la sequenza in ingresso è già ordinata secondo il criterio seguito dalla funzione di raggruppamento. Nell’esempio precedente avete raggruppato una lista di nomi secondo la funzione <code>len()</code>. Questa operazione ha funzionato solo perché la lista in ingresso era già ordinata per lunghezza.
</blockquote>
<p>State guardando da vicino?
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>list(range(0, 3))</kbd>
<samp class=pp>[0, 1, 2]</samp>
<samp class=p>>>> </samp><kbd class=pp>list(range(10, 13))</kbd>
<samp class=pp>[10, 11, 12]</samp>
<a><samp class=p>>>> </samp><kbd class=pp>list(itertools.chain(range(0, 3), range(10, 13)))</kbd> <span class=u>①</span></a>
<samp class=pp>[0, 1, 2, 10, 11, 12]</samp>
<a><samp class=p>>>> </samp><kbd class=pp>list(zip(range(0, 3), range(10, 13)))</kbd> <span class=u>②</span></a>
<samp class=pp>[(0, 10), (1, 11), (2, 12)]</samp>
<a><samp class=p>>>> </samp><kbd class=pp>list(zip(range(0, 3), range(10, 14)))</kbd> <span class=u>③</span></a>
<samp class=pp>[(0, 10), (1, 11), (2, 12)]</samp>
<a><samp class=p>>>> </samp><kbd class=pp>list(itertools.zip_longest(range(0, 3), range(10, 14)))</kbd> <span class=u>④</span></a>
<samp class=pp>[(0, 10), (1, 11), (2, 12), (None, 13)]</samp></pre>
<ol>
<li>La funzione <code>itertools.chain()</code> prende due iteratori e restituisce un iteratore che contiene tutti gli elementi del primo iteratore seguiti da tutti gli elementi del secondo iteratore. (In realtà, può prendere un numero qualsiasi di iteratori e concatenarli tutti nell’ordine in cui sono stati passati alla funzione.)
<li>La funzione <code>zip()</code> fa qualcosa di prosaico che si rivela estremamente utile: prende un numero qualsiasi di sequenze e restituisce un iteratore che restituisce tuple contenenti il primo elemento di ogni sequenza, poi il secondo elemento di ognuna, poi il terzo, e così via.
<li>La funzione <code>zip()</code> si ferma alla fine della sequenza più corta. <code>range(10, 14)</code> contiene 4 elementi (10, 11, 12 e 13) ma <code>range(0, 3)</code> ne contiene solo 3, quindi la funzione <code>zip()</code> restituisce un iteratore di 3 elementi.
<li>D’altra parte, la funzione <code>itertools.zip_longest()</code> si ferma alla fine della sequenza <em>più lunga</em>, inserendo il valore <code>None</code> per elementi oltre la fine delle sequenze più corte.
</ol>
<p id=dict-zip>Bene, tutto questo è stato molto interessante, ma come si collega al risolutore di alfametica? Ecco come:
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>characters = ('S', 'M', 'E', 'D', 'O', 'N', 'R', 'Y')</kbd>
<samp class=p>>>> </samp><kbd class=pp>guess = ('1', '2', '0', '3', '4', '5', '6', '7')</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>tuple(zip(characters, guess))</kbd> <span class=u>①</span></a>
<samp class=pp>(('S', '1'), ('M', '2'), ('E', '0'), ('D', '3'),
('O', '4'), ('N', '5'), ('R', '6'), ('Y', '7'))</samp>
<a><samp class=p>>>> </samp><kbd class=pp>dict(zip(characters, guess))</kbd> <span class=u>②</span></a>
<samp class=pp>{'E': '0', 'D': '3', 'M': '2', 'O': '4',
'N': '5', 'S': '1', 'R': '6', 'Y': '7'}</samp></pre>
<ol>
<li>Data una lista di lettere e una lista di cifre (ognuna rappresentata qui come una stringa di 1 carattere), la funzione <code>zip()</code> creerà coppie di lettere e cifre, in ordine.
<li>Perché è così fantastico? Perché si dà il caso che la struttura dati sia esattamente la struttura giusta da passare alla funzione <code>dict()</code> per creare un dizionario che usi le lettere come chiavi e le cifre a esse associate come valori. (Questo non è l’unico modo per farlo, naturalmente. Potreste usare una <a href=descrizioni.html#dictionarycomprehension>descrizione di dizionario</a> per creare direttamente il dizionario.) Sebbene la rappresentazione stampata del dizionario elenchi le coppie in ordine differente (i dizionari non hanno alcun “ordine” di per sé), potete vedere che ogni lettera è associata con una cifra sulla base dell’ordinamento delle sequenze <var>characters</var> e <var>guess</var> originali.
</ol>
<p id=guess>Il risolutore di alfametica usa questa tecnica per creare un dizionario che mette in relazione le lettere nel rompicampo con le cifre nella soluzione, per ogni possibile soluzione.
<pre class='nd pp'><code>characters = tuple(ord(c) for c in sorted_characters)
digits = tuple(ord(c) for c in '0123456789')
...
for guess in itertools.permutations(digits, len(characters)):
...
<mark> equation = puzzle.translate(dict(zip(characters, guess)))</mark></code></pre>
<p>Ma cos’è questo metodo <code>translate()</code>? Ah, ora state arrivando alla parte <em>davvero</em> divertente.
<p class=a>⁂
<h2 id=string-translate>Un nuovo tipo di manipolazione di stringhe</h2>
<p>Le stringhe Python sono dotate di molti metodi. Avete imparato alcuni di quei metodi nel <a href=stringhe.html>capitolo sulle stringhe</a>: <code>lower()</code>, <code>count()</code> e <code>format()</code>. Ora voglio introdurvi a una tecnica di manipolazione di stringhe molto potente ma poco conosciuta: il metodo <code>translate()</code>.
<pre class=screen>
<a><samp class=p>>>> </samp><kbd class=pp>translation_table = {ord('A'): ord('O')}</kbd> <span class=u>①</span></a>
<a><samp class=p>>>> </samp><kbd class=pp>translation_table</kbd> <span class=u>②</span></a>
<samp class=pp>{65: 79}</samp>
<a><samp class=p>>>> </samp><kbd class=pp>'MARK'.translate(translation_table)</kbd> <span class=u>③</span></a>
<samp class=pp>'MORK'</samp></pre>
<ol>
<li>Le traduzioni di stringa cominciano con una tabella di traduzione, che è solo un dizionario che mette in relazione un carattere con un altro. In effetti, “carattere” non è il termine giusto — in realtà la tabella di traduzione mette in relazione un <em>byte</em> con un altro.
<li>Ricordate, i byte in Python 3 sono interi. La funzione <code>ord()</code> restituisce il valore <abbr>ASCII</abbr> di un carattere, che nel caso delle lettere A–Z è sempre un byte da 65 a 90.
<li>Il metodo <code>translate()</code> fa scorrere una stringa attraverso la tabella di traduzione passata come argomento, sostituendo tutte le occorrenze delle chiavi della tabella con i valori corrispondenti. In questo caso, “traducendo” <code>MARK</code> in <code>MORK</code>.
</ol>
<aside>Ora state arrivando alla parte <em>davvero</em> divertente.</aside>
<p>Che cos’ha a che fare questo con la soluzione dei rompicapi alfametici? A quanto pare, tutto.
<pre class=screen>
<a><samp class=p>>>> </samp><kbd class=pp>characters = tuple(ord(c) for c in 'SMEDONRY')</kbd> <span class=u>①</span></a>
<samp class=p>>>> </samp><kbd class=pp>characters</kbd>
<samp class=pp>(83, 77, 69, 68, 79, 78, 82, 89)</samp>
<a><samp class=p>>>> </samp><kbd class=pp>guess = tuple(ord(c) for c in '91570682')</kbd> <span class=u>②</span></a>
<samp class=p>>>> </samp><kbd class=pp>guess</kbd>
<samp class=pp>(57, 49, 53, 55, 48, 54, 56, 50)</samp>
<a><samp class=p>>>> </samp><kbd class=pp>translation_table = dict(zip(characters, guess))</kbd> <span class=u>③</span></a>
<samp class=p>>>> </samp><kbd class=pp>translation_table</kbd>
<samp class=pp>{68: 55, 69: 53, 77: 49, 78: 54, 79: 48, 82: 56, 83: 57, 89: 50}</samp>
<a><samp class=p>>>> </samp><kbd class=pp>'SEND + MORE == MONEY'.translate(translation_table)</kbd> <span class=u>④</span></a>
<samp class=pp>'9567 + 1085 == 10652'</samp></pre>
<ol>
<li>Usando una <a href=#generator-expressions>espressione generatore</a>, calcoliamo velocemente i valori in byte per ogni carattere in una stringa. <var>characters</var> è un esempio dei valori di <var>sorted_characters</var> nella funzione <code>alphametics.solve()</code>.
<li>Usando un’altra espressione generatore, calcoliamo velocemente i valori in byte per ogni cifra in quella stringa. Il risultato, <var>guess</var>, è nella forma <a href=#guess>restituita dalla funzione <code>itertools.permutations()</code></a> nella funzione <code>alphametics.solve()</code>.
<li>Questa tabella di traduzione è generata <a href=#dict-zip>invocando <code>zip()</code> su <var>characters</var> e <var>guess</var></a> e costruendo un dizionario a partire dalla sequenza di coppie risultante. Questo è esattamente quello che la funzione <code>alphametics.solve()</code> fa all’interno del ciclo <code>for</code>.
<li>Infine, passiamo la tabella di traduzione al metodo <code>translate()</code> della stringa del rompicapo originale. Questa operazione converte ogni lettera della stringa nella cifra corrispondente (sulla base delle lettere in <var>characters</var> e delle cifre in <var>guess</var>). Il risultato è un’espressione Python valida, sotto forma di stringa.
</ol>
<p>Piuttosto impressionante. Ma cosa potete fare con una stringa che casualmente rappresenta un’espressione Python valida?
<p class=a>⁂
<h2 id=eval>Valutare stringhe arbitrarie come espressioni Python</h2>
<p>Questo è l’ultimo pezzo del puzzle (o piuttosto, l’ultimo pezzo del risolutore di puzzle). Dopo tutta quella sofisticata manipolazione di stringhe, non ci rimane altro che una stringa come <code>'9567 + 1085 == 10652'</code>. Ma quella, appunto, è solo una stringa, e a cosa può servirci una stringa? Entra <code>eval()</code>, lo strumento universale di valutazione in Python.
<pre class='nd screen'>
<samp class=p>>>> </samp><kbd class=pp>eval('1 + 1 == 2')</kbd>
<samp class=pp>True</samp>
<samp class=p>>>> </samp><kbd class=pp>eval('1 + 1 == 3')</kbd>
<samp class=pp>False</samp>
<samp class=p>>>> </samp><kbd class=pp>eval('9567 + 1085 == 10652')</kbd>
<samp class=pp>True</samp></pre>
<p>Ma aspettate, c’è di più! La funzione <code>eval()</code> non si limita alle espressioni logiche. Può operare su <em>qualsiasi</em> espressione Python e restituire <em>qualsiasi</em> tipo di dato.
<pre class='nd screen'>
<samp class=p>>>> </samp><kbd class=pp>eval('"A" + "B"')</kbd>
<samp class=pp>'AB'</samp>
<samp class=p>>>> </samp><kbd class=pp>eval('"MARK".translate({65: 79})')</kbd>
<samp class=pp>'MORK'</samp>
<samp class=p>>>> </samp><kbd class=pp>eval('"AAAAA".count("A")')</kbd>
<samp class=pp>5</samp>
<samp class=p>>>> </samp><kbd class=pp>eval('["*"] * 5')</kbd>
<samp class=pp>['*', '*', '*', '*', '*']</samp></pre>
<p>Ma aspettate, non è tutto!
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>x = 5</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>eval("x * 5")</kbd> <span class=u>①</span></a>
<samp class=pp>25</samp>
<a><samp class=p>>>> </samp><kbd class=pp>eval("pow(x, 2)")</kbd> <span class=u>②</span></a>
<samp class=pp>25</samp>
<samp class=p>>>> </samp><kbd class=pp>import math</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>eval("math.sqrt(x)")</kbd> <span class=u>③</span></a>
<samp class=pp>2.2360679774997898</samp></pre>
<ol>
<li>L’espressione che <code>eval()</code> accetta può fare riferimento a variabili globali definite al di fuori di <code>eval()</code>. Se <code>eval()</code> viene chiamata all’interno di una funzione, l’espressione può anche fare riferimento a variabili locali.
<li>E a funzioni.
<li>E a moduli.
</ol>
<p>Ehi, aspettate un momento…
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>import subprocess</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>eval("subprocess.getoutput('ls ~')")</kbd> <span class=u>①</span></a>
<samp class=pp>'Desktop Library Pictures \
Documents Movies Public \
Music Sites'</samp>
<a><samp class=p>>>> </samp><kbd class=pp>eval("subprocess.getoutput('rm /un/file/a/caso')")</kbd> <span class=u>②</span></a></pre>
<ol>
<li>Il modulo <code>subprocess</code> vi permette di eseguire comandi di shell arbitrari e ottenerne il risultato sotto forma di stringa Python.
<li>Comandi di shell arbitrari possono avere conseguenze permanenti.
</ol>
<p>È anche peggio di così, perché esiste una funzione globale chiamata <code>__import__()</code> che prende il nome di un modulo sotto forma di stringa, importa il modulo e ne restituisce un riferimento. Combinandola con la potenza di <code>eval()</code>, potete costruire una singola espressione che cancellerà tutti i vostri file:
<pre class=screen>
<a><samp class=p>>>> </samp><kbd class=pp>eval("__import__('subprocess').getoutput('rm /un/file/a/caso')")</kbd> <span class=u>①</span></a></pre>
<ol>
<li>Ora immaginate l’uscita di <code>'rm -rf ~'</code>. In realtà non ci sarebbe nessuna uscita, ma d’altra parte non vi sarebbe rimasto più alcun file.
</ol>
<p class=xxxl>eval() è un PERICOLO
<p>Be’, la parte pericolosa è la valutazione di espressioni arbitrarie provenienti da sorgenti non affidabili. Dovreste usare <code>eval()</code> solo su ingressi affidabili. Naturalmente il trucco è scoprire cos’è “affidabile”. Ma ecco qualcosa che so di sicuro: <b>NON</b> dovreste prendere questo risolutore di alfametica e metterlo su Internet come un piccolo servizio web divertente. Non fate l’errore di pensare: “Gosh, la funzione effettua un sacco di manipolazioni di stringhe prima di ottenere una stringa da valutare; <em>non riesco a immaginare</em> come qualcuno potrebbe servirsene.” Qualcuno <b>SCOPRIRÀ</b> come infilare codice eseguibile pericoloso attraverso tutte quelle manipolazioni di stringhe (<a href=http://www.securityfocus.com/blogs/746>sono accadute cose anche più strane</a>), e poi potrete dare al vostro server il bacio d’addio.
<p>Ma sicuramente ci sarà <em>qualche</em> modo per valutare espressioni in sicurezza? Per mettere <code>eval()</code> in un ambiente controllato dove non possa accedere al mondo esterno o danneggiarlo? Be’, sì e no.
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>x = 5</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>eval("x * 5", {}, {})</kbd> <span class=u>①</span></a>
<samp class=traceback>Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name 'x' is not defined</samp>
<a><samp class=p>>>> </samp><kbd class=pp>eval("x * 5", {"x": x}, {})</kbd> <span class=u>②</span></a>
<samp class=p>>>> </samp><kbd class=pp>import math</kbd>
<a><samp class=p>>>> </samp><kbd class=pp>eval("math.sqrt(x)", {"x": x}, {})</kbd> <span class=u>③</span></a>
<samp class=traceback>Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name 'math' is not defined</samp></pre>
<ol>
<li>Il secondo e terzo parametro passati alla funzione <code>eval()</code> agiscono come spazi di nomi globali e locali in cui valutare l’espressione. In questo caso sono entrambi vuoti, così quando la stringa <code>"x * 5"</code> viene valutata non esiste alcun riferimento a <var>x</var> né nello spazio di nomi globale né in quello locale, quindi <code>eval()</code> solleva un’eccezione.
<li>Potete selettivamente includere specifici valori nello spazio di nomi globale elencandoli individualmente. Poi quelle variabili — e solo quelle — saranno disponibili durante la valutazione.
<li>Anche se avete appena importato il modulo <code>math</code>, non lo avete incluso nello spazio di nomi passato alla funzione <code>eval()</code>, così la valutazione è fallita.
</ol>
<p>Perbacco, è stato facile. Lasciatemi fare quel servizio web di alfametica ora!
<pre class=screen>
<a><samp class=p>>>> </samp><kbd class=pp>eval("pow(5, 2)", {}, {})</kbd> <span class=u>①</span></a>
<samp class=pp>25</samp>
<a><samp class=p>>>> </samp><kbd class=pp>eval("__import__('math').sqrt(5)", {}, {})</kbd> <span class=u>②</span></a>
<samp class=pp>2.2360679774997898</samp></pre>
<ol>
<li>Anche se avete passato dizionari vuoti per gli spazi di nomi globali e locali, tutte le funzioni built-in di Python sono ancora disponibili durante la valutazione. Quindi <code>pow(5, 2)</code> funziona, perché <code>5</code> e <code>2</code> sono letterali e <code>pow()</code> è una funzione built-in.
<li>Sfortunatamente (e se non vedete perché è una sfortuna, continuate a leggere), anche la funzione <code>__import__()</code> è una funzione built-in e quindi è disponibile.
</ol>
<p>Sì, questo significa che potete ancora fare cose pericolose, anche se avete esplicitamente impostato gli spazi di nomi globali e locali a dizionari vuoti quando avete invocato <code>eval()</code>:
<pre class='nd screen'><samp class=p>>>> </samp><kbd class=pp>eval("__import__('subprocess').getoutput('rm /un/file/a/caso')", {}, {})</kbd></pre>
<p>Oops. Sono contento di non aver fatto quel servizio web di alfametica. C’è un modo <em>qualsiasi</em> di utilizzare <code>eval()</code> in sicurezza? Be’, sì e no.
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>eval("__import__('math').sqrt(5)",</kbd>
<a><samp class=p>... </samp><kbd class=pp> {"__builtins__":None}, {})</kbd> <span class=u>①</span></a>
<samp class=traceback>Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name '__import__' is not defined</samp>
<samp class=p>>>> </samp><kbd class=pp>eval("__import__('subprocess').getoutput('rm -rf /')",</kbd>
<a><samp class=p>... </samp><kbd class=pp> {"__builtins__":None}, {})</kbd> <span class=u>②</span></a>
<samp class=traceback>Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name '__import__' is not defined</samp></pre>
<ol>
<li>Per valutare espressioni non affidabili in maniera sicura, avete bisogno di definire nello spazio di nomi globale un dizionario che faccia corrispondere <code>"__builtins__"</code> a <code>None</code>, il valore nullo di Python. Internamente, le funzioni “built-in” sono contenute in uno pseudomodulo chiamato <code>"__builtins__"</code>. Questo pseudomodulo (cioè l’insieme delle funzioni built-in) viene reso disponibile alle espressioni valutate a meno che non lo ridefiniate esplicitamente.
<li>Assicuratevi di aver ridefinito <code>__builtins__</code> e non <code>__builtin__</code> o <code>__built-ins__</code> o qualche altra variazione che funzionerà benissimo ma vi esporrà a rischi catastrofici.
</ol>
<p>Quindi <code>eval()</code> è sicura ora? Be’, sì e no.
<pre class=screen>
<samp class=p>>>> </samp><kbd class=pp>eval("2 ** 2147483647",</kbd>
<a><samp class=p>... </samp><kbd class=pp> {"__builtins__":None}, {})</kbd> <span class=u>①</span></a>
</pre>
<ol>
<li>Anche senza accedere a <code>__builtins__</code> potete ancora lanciare un attacco di negazione del servizio. Per esempio, elevare <code>2</code> alla potenza di <code>2147483647</code> utilizzerà il 100% della <abbr>CPU</abbr> del vostro server per un bel po’ di tempo. (Se state provando a farlo nella shell interattiva, premete alcune volte <kbd>Ctrl-C</kbd> per interrompere la computazione.) Tecnicamente questa espressione <em>restituirà</em> un valore alla fine, ma nel frattempo il vostro server non riuscirà a fare proprio nient’altro.
</ol>
<p>In conclusione, <em>è</em> possibile valutare in sicurezza espressioni Python non affidabili, per una qualche definizione di “sicurezza” che si scopre non essere terribilmente utile nella vita reale. Va benissimo se state semplicemente divertendovi un po’ e va benissimo se usate solo ingressi affidabili. Ma, in qualsiasi altra situazione, significa andare in cerca di guai.
<p class=a>⁂
<h2 id=alphametics-finale>Mettere tutto insieme</h2>
<p>Ricapitolando: questo programma risolve rompicapi alfametici utilizzando la forza bruta, cioè attraverso una ricerca completa di tutte le possibili soluzioni. Per fare questo, il programma…
<ol>
<li><a href=#re-findall>Trova tutte le lettere nel rompicapo</a> con la funzione <code>re.findall()</code>.
<li><a href=#unique-items>Trova tutte le lettere <em>uniche</em> nel rompicapo</a> eliminando le ripetizioni con gli insiemi e la funzione <code>set()</code>.
<li><a href=#assert>Controlla se ci sono più di 10 lettere uniche</a> (cioè se il rompicapo è assolutamente irrisolvibile) con un’istruzione <code>assert</code>.
<li><a href=#generator-objects>Converte le lettere nei loro equivalenti <abbr>ASCII</abbr></a> con un oggetto generatore.
<li><a href=#permutations>Calcola tutte le possibili soluzioni</a> con la funzione <code>itertools.permutations()</code>.
<li><a href=#string-translate>Converte ogni possibile soluzione in un’espressione Python</a> con il metodo <code>translate()</code> delle stringhe.
<li><a href=#eval>Verifica ogni possibile soluzione valutando l’espressione Python</a> con la funzione <code>eval()</code>.
<li>Restituisce la prima soluzione che viene valutata a <code>True</code>.
</ol>
<p>…in sole 14 righe di codice.
<p class=a>⁂
<h2 id=furtherreading>Letture di approfondimento</h2>
<ul>
<li><a href=http://docs.python.org/3.1/library/itertools.html>Il modulo <code>itertools</code></a>
<li><a href=http://www.doughellmann.com/PyMOTW/itertools/><code>itertools</code> — Funzioni di iterazione per effettuare cicli in maniera efficiente</a>
<li>Guardate Raymond Hettiger presentare <a href=http://blip.tv/file/1947373/>“IA facile con Python”</a> a PyCon 2009
<li><a href=http://code.activestate.com/recipes/576615/>Ricetta n°576615: risolutore di alfametica</a>, il risolutore di alfametica originale scritto da Raymond Hettinger per Python 2
<li><a href=http://code.activestate.com/recipes/users/178123/>Altre ricette di Raymond Hettinger</a> nell’archivio di codice di ActiveState
<li><a href=http://en.wikipedia.org/wiki/Verbal_arithmetic>Alfametica su Wikipedia</a>
<li><a href=http://www.tkcs-collins.com/truman/alphamet/index.shtml>Indice dell’alfametica</a>, compresi <a href=http://www.tkcs-collins.com/truman/alphamet/alphamet.shtml>moltissimi rompicapi</a> e <a href=http://www.tkcs-collins.com/truman/alphamet/alpha_gen.shtml>un generatore per farne dei vostri</a>
</ul>
<p>Molte grazie a Raymond Hettinger per aver accettato di ridistribuire il suo codice con una licenza diversa in modo che io potessi convertirlo verso Python 3 e usarlo come base per questo capitolo.
<p class=v><a href=iteratori.html rel=prev title='indietro a “Classi & iteratori”'><span class=u>☜</span></a> <a href=test-di-unità.html rel=next title='avanti a “Test di unità”'><span class=u>☞</span></a>
<p class=c>© 2001–10 <a href=informazioni-sul-libro.html>Mark Pilgrim</a><br>
© 2009–10 <a href=informazioni-sulla-traduzione.html>Giulio Piancastelli</a> per la traduzione italiana
<script src=j/jquery.js></script>
<script src=j/prettify.js></script>
<script src=j/dip3.js></script>