Meeting20130601: index.html

File index.html, 10.8 KB (added by Simon Cross, 8 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>