Meeting20130601: index.html

File index.html, 10.8 KB (added by hodgestar, 11 years ago)

Source HTML for slides on Rice's Theorem (requires reveal.js)

Line 
1<!doctype html>
2<html lang="en">
3
4 <head>
5 <meta charset="utf-8">
6
7 <title>Practical Implications of Rice's Theorem</title>
8
9 <meta name="description" content="An introduction to Rice's Theorem and a look at what it implies for day-to-day development">
10 <meta name="author" content="Simon Cross">
11
12 <meta name="apple-mobile-web-app-capable" content="yes" />
13 <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />
14
15 <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
16
17 <link rel="stylesheet" href="css/reveal.min.css">
18 <link rel="stylesheet" href="css/theme/moon.css" id="theme">
19
20 <!-- For syntax highlighting -->
21 <link rel="stylesheet" href="lib/css/zenburn.css">
22
23 <!-- If the query includes 'print-pdf', use the PDF print sheet -->
24 <script>
25 document.write( '<link rel="stylesheet" href="css/print/' + ( window.location.search.match( /print-pdf/gi ) ? 'pdf' : 'paper' ) + '.css" type="text/css" media="print">' );
26 </script>
27
28 <!--[if lt IE 9]>
29 <script src="lib/js/html5shiv.js"></script>
30 <![endif]-->
31 </head>
32
33 <body>
34
35 <div class="reveal">
36 <div class="slides">
37
38 <!-- Title slide -->
39 <section>
40 <h1>Rice's Theorem</h1>
41 <h3>and what it means for you! :)</h3>
42 <p>
43 <small>Created by <a href="http://hodgestar.za.net">Simon Cross</a> / <a href="http://twitter.com/hodgestar">@hodgestar</a></small>
44 </p>
45 </section>
46
47 <!-- What is Rice's Thoerem -->
48
49 <section data-state="alert">
50 <section>
51 <h2>What the heck is Rice's Theorem?</h2>
52 </section>
53 <section>
54 <h2>Some things are just unpossible!</h2>
55 <p class="fragment">
56 Which things? Glad you asked! :)
57 </p>
58 </section>
59 <section>
60 <h2>Properties of computable partial functions</h2>
61 </section>
62 <section>
63 <h2>Formal(ish) statement</h2>
64 <p>
65 <span class="fragment">Given a <b>non-trivial</b> <b>property</b> of computable partial <b>functions</b></span>
66 <span class="fragment">the problem of whether a particular program computes such a function is undecidable</span>
67 </p>
68 </section>
69 <section>
70 <h2>Non-trivial</h2>
71 <ul>
72 <li class="fragment">A least one function that <b>has</b> the property</li>
73 <li class="fragment">A least one function that <b>doesn't have</b> the property</li>
74 </ul>
75 </section>
76 <section>
77 See <a href="http://en.wikipedia.org/wiki/Rice's_theorem">Wikipedia</a> for the gory details. :)
78 </section>
79 </section>
80
81 <section>
82 <section>
83 <h2>Kinds of properties</h2>
84 </section>
85 <section>
86 <h2>Works for:</h2>
87 <p class="fragment">Properties that refer to behaviour</p>
88 <p class="fragment">Properties that refer to input and output only</p>
89 </section>
90 <section>
91 <h2>Doesn't work for:</h2>
92 <p class="fragment">Properties that refer to the implementation</p>
93 <ul>
94 <li class="fragment">Number of lines of code</li>
95 <li class="fragment">Number of for-loops</li>
96 <li class="fragment">Whether the code is syntactically correct</li>
97 </section>
98 </section>
99
100 <section data-state="soothe">
101 <section>
102 <h2>Sketch of a proof ...</h2>
103 </section>
104 <section>
105 <h2>... in Python!</h2>
106 <pre><code data-trim contenteditable>
107def has_cool_property(f):
108 """Returns True if f has this cool property,
109 False otherwise."""
110 # XXX: Put magic here!
111
112def tiny_cool_function(*args, **kw):
113 """Tiny function we wrote to show the cool property
114 is sometimes met."""
115 # XXX: Write this.
116
117def halts(a, i):
118 """Returns True if a halts given input i."""
119 def t(*args, **kw):
120 a(i) # this is just here to mess with has_cool_property
121 return tiny_cool_function(*args, **kw)
122 return has_cool_property(t)
123 </code></pre>
124 </section>
125 </section>
126
127 <!-- Implications -->
128
129 <section>
130 <section>
131 <h2>So these implications you promised?</h2>
132 </section>
133 <section>
134 <h2>QA and testing</h2>
135 </section>
136 <section>
137 <h2>Security and sandboxes</h2>
138 </section>
139 <section>
140 <h2>Compiling and static analysis</h2>
141 </section>
142 </section>
143
144 <!-- Non-implications -->
145
146 <section data-state="alert">
147 <section>
148 <h2>Non-implications</h2>
149 <p class="fragment">a.k.a. things that might work</p>
150 </section>
151 <section>
152 <h2>Upfront design</h2>
153 <aside class="notes">
154 Rice's Theorem doesn't say much about whether an algorithm can be tailored to have
155 a particular feature -- it just says that if you don't you're a bit screwed trying
156 to add the property afterwards.
157 </aside>
158 <p class="fragment">If you want a property, design it in up front ...</p>
159 <p class="fragment">because you won't be able to check later. :/</p>
160 </section>
161 </section>
162
163 <!-- After thoughts -->
164
165 <section data-state="soothe">
166 <h1>HALT?</h1>
167 <h3>BY Simon Cross / hodgestar.za.net</h3>
168 </section>
169
170 <section>
171 <section>
172 <h2>What made you look into all this?!</h2>
173 </section>
174 <section>
175 <h2>Blame PERL!</h2>
176 <p class="fragment"><a href="http://www.perlmonks.org/?node_id=663393">It's unparsable. :/</a></p>
177 </section>
178 <section>
179 <h2>Its grammar is ambiguous in crazy ways:</h2>
180 <code class="fragment" data-trim contenteditable>
181 whatever / 25 ; # / ; die "this dies!";
182 </code>
183 </section>
184 <section>
185 <h2>If you ever need to feel great about using Python:</h2>
186 <ul>
187 <li>
188 <a href="http://www.perlmonks.org/index.pl?node_id=44722">On Parsing Perl</a>
189 by <i>Randal Schwartz</i> (2000)
190 </li>
191 <li>
192 <a href="http://search.cpan.org/~adamk/PPI-1.215/lib/PPI.pm">PPI man page</a>
193 by <i>Adam Kennedy</i>
194 </li>
195 <li>
196 <a href="http://www.perlmonks.org/?node_id=663393">Perl Cannot be Parsed: A Formal Proof</a>
197 by <i>Jeffrey Kegler</i> (2008)
198 </li>
199 </ul>
200 </section>
201 </section>
202
203 <section data-state="blackout">
204 <section>
205 <h2>An unrelated cool thing:</h2>
206 <ul>
207 <li>
208 <a href="http://mcsp.wartburg.edu/zelle/python/python-first.html">Python as a First Language</a>
209 by <i>John M. Zelle</i>
210 </li>
211 </ul>
212 </section>
213 <section>
214 <blockquote cite="http://mcsp.wartburg.edu/zelle/python/python-first.html">
215 &ldquo;Compiling a program and staring at a screenfull of nagging messages is
216 a dull and exasperating activity.&rdquo;
217 </blockquote>
218 </section>
219 <section>
220 <blockquote cite="http://mcsp.wartburg.edu/zelle/python/python-first.html">
221 &ldquo;In fact, I would venture to say that after a couple days playing with Python,
222 many faculty who are now teaching C++ would know Python better.&rdquo;
223 </blockquote>
224 </section>
225 </section>
226
227 <section>
228 <h2>Ideas generated by questions and comments after the talk</h2>
229 <ul>
230 <li>Scalability is another property one can't tack on to programs afterwards.</li>
231 <li>JIT compilation also benefits from Rice's Theorem since it imposes strong
232 bounds on what static compilation can prove about the algorithm implemented.</li>
233 </ul>
234 </section>
235
236 </div>
237 </div>
238
239 <script src="lib/js/head.min.js"></script>
240 <script src="js/reveal.min.js"></script>
241
242 <script>
243
244 // Full list of configuration options available here:
245 // https://github.com/hakimel/reveal.js#configuration
246 Reveal.initialize({
247 controls: false,
248 progress: true,
249 history: true,
250 center: true,
251
252 theme: Reveal.getQueryHash().theme, // available themes are in /css/theme
253 transition: Reveal.getQueryHash().transition || 'default', // default/cube/page/concave/zoom/linear/fade/none
254
255 // Optional libraries used to extend on reveal.js
256 dependencies: [
257 { src: 'lib/js/classList.js', condition: function() { return !document.body.classList; } },
258 // { src: 'plugin/markdown/marked.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
259 // { src: 'plugin/markdown/markdown.js', condition: function() { return !!document.querySelector( '[data-markdown]' ); } },
260 { src: 'plugin/highlight/highlight.js', async: true, callback: function() { hljs.initHighlightingOnLoad(); } },
261 { src: 'plugin/zoom-js/zoom.js', async: true, condition: function() { return !!document.body.classList; } },
262 { src: 'plugin/notes/notes.js', async: true, condition: function() { return !!document.body.classList; } }
263 // { src: 'plugin/search/search.js', async: true, condition: function() { return !!document.body.classList; } }
264 // { src: 'plugin/remotes/remotes.js', async: true, condition: function() { return !!document.body.classList; } }
265 ]
266 });
267
268 </script>
269
270 </body>
271</html>