forked from B-Rich/vfa
-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
82 lines (70 loc) · 3.75 KB
/
index.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
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"/>
<link href="coqdoc.css" rel="stylesheet" type="text/css"/>
<title>Verified Functional Algorithms</title>
</head>
<body>
<div id="page">
<div class="doc" id="index">
<h1>Verified Functional Algorithms</h1>
<h2>Andrew W. Appel</h2>
<i>(Version of June 2014)</i>
<p>
<strong>Please do not distribute solutions to these problems.</strong>
This is copyrighted material and I do not license derivative works.
<p>
<strong>OPLSS students: Which exercises did you complete?</strong>
<br><a href=https://docs.google.com/forms/d/17nP5P89PWbzlbrURhOqKOnXRl6op5yVdIWlwLo47noA/viewform>Answer here</a>.
<br><a href=https://docs.google.com/spreadsheet/ccc?key=0AtdEso0pwmdgdEx3TFc5YWdpaFhNVzF4anZ4Z2hrZ1E&usp=sharing>View results here</a>.
<p>
The general theme of my four lectures will be <i>writing functional
programs and proving them correct in Coq.</i>
<p>
<strong>Suggested Reading:</strong> If you have time, please read or skim the suggested reading before the lectures.
<p>
The Coq files are compatible with Coq 8.4pl3.
The problems are listed in approximate order of increasing difficulty. Coq novices should start at the beginning; those with more experience can skip to whichever problem interests them the most.
<p>
Some of these Coq files import <a href="SfLib.v">SfLib.v</a> or
<a href="Imp.v">Imp.v</a> from <a href="http://www.cis.upenn.edu/~bcpierce/sf/">Software Foundations</a>.
<h2>The exercises</h2>
<a href="vfa.tgz">(Download all as a tar file)</a>
<dl>
<dt><a href="Sort.v">Insertion sort</a><dd>
Background reading: any elementary textbook on algorithms.
<dt><a href="Selection.v">Selection sort</a><dd>
Background reading: any elementary textbook on algorithms.
<dt><a href="Unroll.v">Unrolling lists</a><dd>
Background reading:
<A HREF="http://www.cs.princeton.edu/~appel/papers/unrolling-lists.pdf">Unrolling Lists</A>, by Zhong Shao, John H. Reppy, and Andrew W. Appel.
<I>Proc. 1994 ACM Conf. on Lisp and Functional Programming,</I> June 1994.</A>
<dt><a href="SearchTree.v">Binary Search Trees</a><dd>
Background reading: any elementary textbook on algorithms.
<dt><a href="Binom.v">Binomial queues</a><dd>
Background reading: <a href=http://www.cs.princeton.edu/~appel/BQ.pdf>Binomial Queues</a>, Section 9.7 of
<i>Algorithms 3rd Edition in Java, Parts 1-4:
Fundamentals, Data Structures, Sorting, and Searching,</i>
by Robert Sedgewick. Addison-Wesley, 2002.
<dt><a href="Redblack.v">Red-black trees</a><dd>
Background reading: <a href=http://www.eecs.usma.edu/webs/people/okasaki/jfp99redblack.pdf>Red-Black Trees in a Functional Setting</a>, by Chris Okasaki.
<i>Journal of Functional Programming,</i> 9(4):471-477, July 1999. <br>
Optional reading: <a href=http://www.cs.princeton.edu/~appel/papers/redblack.pdf>Efficient Verified Red-Black Trees</a>, by Andrew W. Appel, September 2011.<br>
Test driver: <a href="test_rb.ml">test_rb.ml</a>
<dt><a href="Compiler.v">Compiling straight-line code</a><dd>
Background reading: <a href="http://www.cis.upenn.edu/~bcpierce/sf/">Software Foundations</a> by Benjamin Pierce <i>et al.</i>, up to chapter "Imp: Simple Imperative Programs".
<dt><a href="Color.v">Graph coloring</a><dd>
Background reading: <a href="http://www.cs.princeton.edu/~appel/papers/regalloc.pdf">Formal Verification of Coalescing Graph-Coloring Register Allocation</a>,
by Sandrine Blazy, Benoit Robillard, and Andrew W. Appel.
<i>ESOP 2010: 19th European Symposium on Programming,</i> pp. 145-164, March 2010.
</dl>
</div>
<div id="footer">
Copyright © 2014, Andrew W. Appel <br>
</div>
</div>
</div>
</body>
</html>