ndanger000
commented
8 years ago This still needs more work:
- Section 1: basically good.
- Reverse the order of the "two problems" paragraphs. The "concrete" problem is that f may not have constant cost. The "abstract" problem raised by the concrete problem is that our heuristics may miss important information about actual operational cost.
- Give a more concrete example about why use cost is important (i.e., an example of some non-trivial composition). Use the terms potential/use cost here.
- Drop the last paragraph, because it is getting into previous work.
- Section 2: Needs more detail!
- Start with a 2-sentence "as we've just seen..." summary of Section 1.
- Explain how these papers work toward resolving the issues you raised in Section 1:
- ATS: interpretation into (type-2) polynomials; even fold interpreted as a polynomial. Can be seen as a restricted notion of extracting recurrences for cost and potential.
- DPR: fold interpreted by a fold. But restricted source language, and extraction is really a denotational semantics.
- DLR: Purely syntactic translation, so now we really have (a language for) recurrences. Also programmer-defined sizes of datatypes.
- Section 3: Earlier issues not yet fixed.
- Refer to chapters by number, not ordinal. Chapter 2, Chapter 3, etc. Your first chapter is an introduction (the reader is reading it right now), not a catalogue.
- You don't do the comparisons you describe, so don't mention the possibility.
- Explain why each example is worth doing.
- Explain how the source language changes for parallelism.
- One chapter alone doesn't demonstrate that potential does not depend on cost. Be more explanatory here.
You need a much more thorough introduction. Remember, this is the part that convinces your reader to read the rest of the thesis. S/he needs to know what to expect.
Section 1 can be fairly short, describing some of the issues with traditional complexity analysis that you've identified (more on that in another issue). You should also raise the issue of a formal connection between the recurrence and the source code. Together these motivate the work you address in Section 2.
Section 2 will be on prior work that leads to our recurrence extraction function. By the time you discuss the ICFP'15 paper, you should have identified the concepts of source language, complexity language, extraction (translation), and bounding theorem.
Section 3 is the contribution of this thesis. It is a wordy table of contents. You should describe (referring to appropriate chapters/sections) the examples that you will work out. Make sure to explain why they are interesting, which boils down to "things that ICFP'15 says we can analyze, but we haven't ever worked out" (higher-order folds; functions with non-trivial costs; different notion of cost). An observation that we can make after this catalog is that the recurrence that describes the potential never depends upon that for the cost, even though formally the two recurrences should be mutually recursive (you will need to have been clear before now about this idea of having a pair of recurrences). So in Chapter XXX we will make this intuition formal by defining another extraction function that is a lot like the one used in the examples, but drops any reference to cost, and then you will go on to establish a logical relation between the two extractions, which will formalize the intuition. And (hopefully) we'll have some examples to show that the modified extraction function yields precisely the potential recurrences from our usual extraction function.