Ted Leung on the air
Ted Leung on the air: Open Source, Java, Python, and ...
Ted Leung on the air: Open Source, Java, Python, and ...
Wed, 30 Jul 2003
CPS in Parrot
I was very happy to read that
Dan Sugalski decided to go with continuation passing style (CPS) as the internal representation for the Parrot VM. But things that are internal could be made visible, which would make Parrot a good candidate for hosting Scheme or Stackless Python. Very interesting.
Reading Dan's post rang a bell in my head regarding CPS and Static Single Assignment (SSA) form. When I left graduate school. SSA was becoming the IR of choice for compiler optimizations. Richard Kelsey wrote a paper regarding
A Correspondence between Continuation-Passing Style and Static Single Assignment, which showed how to convert programs in CPS form to SSA form and the reverse. There are few CPS programs that cannot be converted to SSA, but they are not generated by the usual Lisp/Functional language to CPS conversion algorithm.
[02:09] |
[computers/programming/lisp] |
# |
TB |
F |
G |
4 Comments |
If Ted is interested in continuations work being done now, he ought to have a look at Seaside. If you have questions about it, just pop over to the Smalltalk IRC list and ask questions.
Posted by Trackback from Cincom Smalltalk Blog - Smalltalk with Rants at Wed Jul 30 06:53:51 2003
Posted by Trackback from Cincom Smalltalk Blog - Smalltalk with Rants at Wed Jul 30 06:53:51 2003
Hosting scheme was always possible (ignoring the dodge of not supporting continuations, as I've been told you don't actually have to have them to be Scheme, not that I can imagine doing that) since we support continuations, but it does make interoperability easier. Stackless Python, unless there's something I'm missing, wasn't ever an issue--as far as I can tell its functionality's been in Parrot since the beginning. (And in perl 5 from the beginning as well, though stackless might've progressed some since I last looked at it)
I'll have to go look at the SSA paper to see if we're going to end up violating any of its assumptions, which I fear we might. OTOH, because of the dynamic features of the languages we want, most optimizations aren't doable anyway as they change semantics in programs with active data in ways they don't in programs without active data.
Posted by Dan at Wed Jul 30 07:10:09 2003
I'll have to go look at the SSA paper to see if we're going to end up violating any of its assumptions, which I fear we might. OTOH, because of the dynamic features of the languages we want, most optimizations aren't doable anyway as they change semantics in programs with active data in ways they don't in programs without active data.
Posted by Dan at Wed Jul 30 07:10:09 2003
Dan,
What are some of the blockers for traditional optimizations in dynamic languages?
Posted by Ted Leung at Wed Jul 30 23:38:47 2003
What are some of the blockers for traditional optimizations in dynamic languages?
Posted by Ted Leung at Wed Jul 30 23:38:47 2003
Off the top of my head:
You can't tell at compile time whether a variable is active or not. (An active variable being one that may take some action when read from or assigned to) That means you can't hoist common subexpressions out of loops, for example, because that can change the overall semantics of a program.
You can't know at compile time whether a referenced subroutine or method will exist at runtime, nor whether the runtime version will match the version you see when compiling. Methods/subs/functions can be added, changed, and deleted as a program runs, so you can't do compile time binding--everything needs to be looked up at runtime, and potentially every time you make the call.
Given the lack of knowledge about subs at compile time, you can't make any assumptions about what a call may do--the potential for unknowable side-effects is quite large.
As most of the dynamic languages have significnat introspective capabilities, you can't even tell by inspection what code will do at compile time. Something as simple as addition might be overloaded and its execution can alter fundamental things in the calling context, including the types of the variables being added and anything that's global. (Subs, methods, classes, variables...)
All this makes optimization.... interesting.
Posted by Dan at Thu Jul 31 08:28:37 2003
You can't tell at compile time whether a variable is active or not. (An active variable being one that may take some action when read from or assigned to) That means you can't hoist common subexpressions out of loops, for example, because that can change the overall semantics of a program.
You can't know at compile time whether a referenced subroutine or method will exist at runtime, nor whether the runtime version will match the version you see when compiling. Methods/subs/functions can be added, changed, and deleted as a program runs, so you can't do compile time binding--everything needs to be looked up at runtime, and potentially every time you make the call.
Given the lack of knowledge about subs at compile time, you can't make any assumptions about what a call may do--the potential for unknowable side-effects is quite large.
As most of the dynamic languages have significnat introspective capabilities, you can't even tell by inspection what code will do at compile time. Something as simple as addition might be overloaded and its execution can alter fundamental things in the calling context, including the types of the variables being added and anything that's global. (Subs, methods, classes, variables...)
All this makes optimization.... interesting.
Posted by Dan at Thu Jul 31 08:28:37 2003
You can subscribe to an RSS feed of the comments for this blog:
Add a comment here:
You can use some HTML tags in the comment text:
To insert a URI, just type it -- no need to write an anchor tag.
Allowable html tags are:
You can also use some Wiki style:
URI => [uri title]
<em> => _emphasized text_
<b> => *bold text*
Ordered list => consecutive lines starting spaces and an asterisk
Add a comment here:
You can use some HTML tags in the comment text:To insert a URI, just type it -- no need to write an anchor tag.
Allowable html tags are:
<a href>, <em>, <i>, <b>, <blockquote>, <br/>, <p>, <code>, <pre>, <cite>, <sub> and <sup>.You can also use some Wiki style:
URI => [uri title]
<em> => _emphasized text_
<b> => *bold text*
Ordered list => consecutive lines starting spaces and an asterisk
![[Valid RSS]](http://www.sauria.com/blog/images/valid-rss.png "Validate my RSS feed"){kind=small}
