Personal tools

Simonpj/Talk:Papers

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(some old related work)
 
(3 intermediate revisions by 2 users not shown)
Line 13: Line 13:
 
Here is [http://research.microsoft.com/~simonpj/papers/spec-constr the paper].
 
Here is [http://research.microsoft.com/~simonpj/papers/spec-constr the paper].
   
'''Brandon Moore''': In the second paragraph of section 4, I think "the
+
[[User:Brandonm|Brandonm]]: In the second paragraph of section 4, I think "the
 
only question is whether the rewrite rule created in Step *3* is correct".
 
only question is whether the rewrite rule created in Step *3* is correct".
 
I think the aside in section 4.3, middle of the right column on page 6 should
 
I think the aside in section 4.3, middle of the right column on page 6 should
Line 31: Line 31:
   
 
[[User:Agl|Agl]] 04:19, 26 April 2007 (UTC) In the Core translation of drop (page 2), shouldn't the it be <tt>case un of { 0 -> ys</tt> ... <tt>}</tt>, (rather than <tt>[]</tt> as it is currently)? <b>Later</b>: the translation is correct, it's the code for drop at the end of the first page which is odd. (Not wrong, because you can define it to be whatever, but it certainly doesn't match the Prelude drop :) )
 
[[User:Agl|Agl]] 04:19, 26 April 2007 (UTC) In the Core translation of drop (page 2), shouldn't the it be <tt>case un of { 0 -> ys</tt> ... <tt>}</tt>, (rather than <tt>[]</tt> as it is currently)? <b>Later</b>: the translation is correct, it's the code for drop at the end of the first page which is odd. (Not wrong, because you can define it to be whatever, but it certainly doesn't match the Prelude drop :) )
  +
  +
[[User:SamB|SamB]] 15:30, 28 May 2007 (UTC) I say that that <tt>drop</tt> ''is'' wrong, because the paper says "consider this standard function", which implies that it is the some one that is exported by Prelude.
   
 
[[User:PeterThiemann|PeterThiemann]] 19:57, 15 May 2007 (UTC) It's nice to see these ideas surfacing again, properly worked out, implemented and benchmarked. I'm sure you are not aware of this paper: http://www.informatik.uni-freiburg.de/~thiemann/papers/pepm94.ps.gz , which appeared in PEPM'94.
 
[[User:PeterThiemann|PeterThiemann]] 19:57, 15 May 2007 (UTC) It's nice to see these ideas surfacing again, properly worked out, implemented and benchmarked. I'm sure you are not aware of this paper: http://www.informatik.uni-freiburg.de/~thiemann/papers/pepm94.ps.gz , which appeared in PEPM'94.
Line 49: Line 51:
 
NUMBER = 724,
 
NUMBER = 724,
 
ISBN = {3-540-57264-3}
 
ISBN = {3-540-57264-3}
  +
</pre>
  +
  +
[[User:Fanf|Fanf]] 22:06, 4 July 2007 (UTC) I'm not convinced that the (unimplemented) fallthrough optimisation would be entirely helpful: the forward unconditional jump to map_cont can be predicted and pipelined by the processor, but the double indirection via map_ret to map_cont is much more troublesome.
  +
  +
[[User:Fanf|Fanf]] 22:06, 4 July 2007 (UTC) This analysis of the forward jump at the end of map_entry prompts a thought about a possible way to make CALL/RET tractable, with only a small change to the layout of info tables. If you put the CALL instruction right at the end of the info table, the return address will point to the entry code in the usual way; you then have to adjust info table indexes by the size of the call instruction.
  +
<pre>
  +
map_entry() {
  +
...
  +
if (R1 & TAG_MASK) jump map_ret;
  +
jump map_call;
  +
}
  +
  +
data { word32[] = { ... } }
  +
map_call() {
  +
R1[0](); // CALL
  +
// fall through on RET
  +
}
  +
map_ret() {
  +
...
  +
}
 
</pre>
 
</pre>

Latest revision as of 20:00, 30 October 2007

[edit] 1 Talk page for Simon Peyton Jones's papers

If you are kind enough to read one of my papers, you may like to jot down any thoughts it triggers off, and see what others have written. This talk-page lets you do just that. Here's a link back to my home page, from where you can get to all my papers.

There's a section for each paper. If you want to write notes about a paper where there's no section, just go ahead and create a new section.

You can identify your entries by preceding them with four tildes. Doing so adds your name, and the date. Thus:

Simonpj 08:42, 19 April 2007 (UTC) Note from Simon

[edit] 1.1 Constructor specialisation for Haskell programs

Here is the paper.

Brandonm: In the second paragraph of section 4, I think "the only question is whether the rewrite rule created in Step *3* is correct". I think the aside in section 4.3, middle of the right column on page 6 should say "(We have dropped some dead code here, although in practice that would not be done until the simplifier runs in Step 3)". Lower on the same page, it looks like the definition of f1 has an extra ')' in "(n - 1))".

I also had a few comments about the content :) About reboxing, it seems like you might be able to specialise, but also pass take the existing value as another argument, and arrange to use that argument instead of reboxing. Maybe it would be too hard to specialise the body that way, I doubt just simplifying a beta-redex would do it (but it does sound a bit like as-patterns). For related work, I wonder if flow-analysis is relevant.

Simonpj 08:54, 19 April 2007 (UTC) Yes, you could do that, but in the example in Section 6.1 showing that "this is too conservative", it'd be bad to pass the boxed version as well. It'd end up as an unused argument, and some subequent transformation would then have to get rid of it.

Agl 04:15, 26 April 2007 (UTC) (Typo) At the very top of the second page, the text reads "Here is roughly1 drop translates, after a bit of inlining:". Maybe needs a "how" after the "roughly"?

Agl 04:19, 26 April 2007 (UTC) In the Core translation of drop (page 2), shouldn't the it be case un of { 0 -> ys ... }, (rather than [] as it is currently)? Later: the translation is correct, it's the code for drop at the end of the first page which is odd. (Not wrong, because you can define it to be whatever, but it certainly doesn't match the Prelude drop :) )

SamB 15:30, 28 May 2007 (UTC) I say that that drop is wrong, because the paper says "consider this standard function", which implies that it is the some one that is exported by Prelude.

PeterThiemann 19:57, 15 May 2007 (UTC) It's nice to see these ideas surfacing again, properly worked out, implemented and benchmarked. I'm sure you are not aware of this paper: http://www.informatik.uni-freiburg.de/~thiemann/papers/pepm94.ps.gz , which appeared in PEPM'94. It actually has a precursor, which uses them same example of the last function. I don't have it online, but here is the citation:

        AUTHOR = {Peter Thiemann},
        TITLE = {Avoiding Repeated Tests in Pattern Matching},
        YEAR = 1993,
        PAGES = {141-152}
        TITLE = {3rd International Workshop on Static Analysis},
        YEAR = 1993,
        BOOKTITLE = {3rd International Workshop on Static Analysis},
        EDITOR = {Gilberto Fil{\'e}},
        PUBLISHER = SP,
        ADDRESS = {Padova, Italia},
        MONTH = sep,
        SERIES = LNCS,
        NUMBER = 724,
        ISBN = {3-540-57264-3}

Fanf 22:06, 4 July 2007 (UTC) I'm not convinced that the (unimplemented) fallthrough optimisation would be entirely helpful: the forward unconditional jump to map_cont can be predicted and pipelined by the processor, but the double indirection via map_ret to map_cont is much more troublesome.

Fanf 22:06, 4 July 2007 (UTC) This analysis of the forward jump at the end of map_entry prompts a thought about a possible way to make CALL/RET tractable, with only a small change to the layout of info tables. If you put the CALL instruction right at the end of the info table, the return address will point to the entry code in the usual way; you then have to adjust info table indexes by the size of the call instruction.

  map_entry() {
    ...
    if (R1 & TAG_MASK) jump map_ret;
    jump map_call;
  }

  data { word32[] = { ... } }
  map_call() {
    R1[0](); // CALL
    // fall through on RET
  }
  map_ret() {
    ...
  }