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>
|
---|
107 | def has_cool_property(f):
|
---|
108 | """Returns True if f has this cool property,
|
---|
109 | False otherwise."""
|
---|
110 | # XXX: Put magic here!
|
---|
111 |
|
---|
112 | def tiny_cool_function(*args, **kw):
|
---|
113 | """Tiny function we wrote to show the cool property
|
---|
114 | is sometimes met."""
|
---|
115 | # XXX: Write this.
|
---|
116 |
|
---|
117 | def 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 | “Compiling a program and staring at a screenfull of nagging messages is
|
---|
216 | a dull and exasperating activity.”
|
---|
217 | </blockquote>
|
---|
218 | </section>
|
---|
219 | <section>
|
---|
220 | <blockquote cite="http://mcsp.wartburg.edu/zelle/python/python-first.html">
|
---|
221 | “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.”
|
---|
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>
|
---|