tag:blogger.com,1999:blog-107708552024-03-18T15:28:48.342-04:00The Little CalculistDave Herman's research blog.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.comBlogger324125tag:blogger.com,1999:blog-10770855.post-56875754598273514172011-12-06T00:28:00.000-05:002011-12-06T00:29:21.972-05:00I've moved!This blog has a new home:<br /><br /><span style="font-weight:bold;"><a href="http://calculist.org">http://calculist.org</a></span><br /><br />Hope to see you there!Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com29tag:blogger.com,1999:blog-10770855.post-83886357864442999442010-06-12T11:07:00.003-04:002010-06-12T11:15:07.928-04:00RAII vs finallySince I'm pretty new to C++, I wasn't too deeply familiar with <a href="http://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization">RAII</a>; like most Schemers I just thought of it as "C++'s version of <span style="font-family: courier new;">dynamic-wind</span>."<br /><br />This week I learned an important distinction between C++ destructors and Java's <span style="font-family: courier new;">finally</span>. The latter, of course, unilaterally executes when the body terminates, regardless of how or when it terminates. The thing that gives destructors more expressiveness for dealing with cleanup is that they only execute for the objects that have been initialized. This means that if control exits a block after only half of the stack-local objects have been constructed, only those half of the objects have their destructors invoked. With <span style="font-family: courier new;">finally</span>, all that bookkeeping is the responsibility of the programmer.<br /><br />(That said, I still see RAII used all over the place to construct awkward, special-purpose classes whose sole purpose is to run some cleanup code. In these cases, having to create a named object <span style="font-style: italic;">and</span> a named class to go along with it is pretty perverse.)Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com81tag:blogger.com,1999:blog-10770855.post-10348488795717280962010-05-03T16:40:00.002-04:002010-05-03T16:43:07.739-04:00A Theory of Typed Hygienic Macros<a href="http://www.ccs.neu.edu/home/dherman/research/papers/dissertation.pdf">A Theory of Typed Hygienic Macros</a><br />PhD Dissertation, 2010<br /><br /><blockquote>We present the λ<span style="font-size:78%;"><sub>m</sub></span>-calculus, a semantics for a language of hygienic macros with a non-trivial theory. Unlike Scheme, where programs must be macro-expanded to be analyzed, our semantics admits reasoning about programs <span style="font-style: italic;">as they appear to programmers</span>. Our contributions include a semantics of hygienic macro expansion, a formal definition of α-equivalence that is independent of expansion, and a proof that expansion preserves α-equivalence. The key technical component of our language is a type system similar to Culpepper and Felleisen’s “shape types,” but with the novel contribution of <span style="font-style: italic;">binding signature types</span>, which specify the bindings and scope of a macro’s arguments.</blockquote>Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com60tag:blogger.com,1999:blog-10770855.post-4847678234412042772010-04-23T13:11:00.004-04:002010-04-23T13:18:15.230-04:00Effective MLYaron Minsky has giving great advice on <a href="http://ocaml.janestcapital.com/?q=node/75">effective ML</a> lately. For my money, the single most important lesson is #3: <span style="font-style: italic;">make illegal states unrepresentable</span>. There are so many benefits-- and I've seen the awful drawbacks of not following it.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com25tag:blogger.com,1999:blog-10770855.post-74542372997139590992010-04-22T17:59:00.002-04:002010-04-22T18:03:18.674-04:00Cyclic reference graphs FTWI've just created <a href="http://blog.mozilla.com/dherman">my new Mozilla-hosted blog</a>! I don't have intention of stopping this one here, but I'm moving my Mozilla-related (and consequently ECMAScript-related) thoughts to that space.<br /><br />Also, um, I should hopefully have some pretty good news in a couple weeks.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com21tag:blogger.com,1999:blog-10770855.post-20997038797515194232010-04-14T11:27:00.004-04:002010-04-14T12:02:00.528-04:00Single-frame continuations for Harmony, ctdContinuing last week's <a href="http://calculist.blogspot.com/2010/04/delimited-continuations-in-ecmascript.html">series</a> of <a href="http://calculist.blogspot.com/2010/04/design-space-of-continuations.html">posts</a> on <a href="http://calculist.blogspot.com/2010/04/thinking-about-continuations.html">single-frame</a> <a href="http://calculist.blogspot.com/2010/04/harmony-first-class-activations.html">continuations</a> for ECMAScript Harmony:<br /><br />The inimitable <a href="https://mail.mozilla.org/pipermail/es-discuss/2010-April/010900.html">Waldemar Horwat points out the flaw</a> in my strawman proposal (strawman strawman?):<br /><blockquote>Since in the final expression you have A(... A(x)), you'll just end up executing the same finally block twice under certain circumstances.<br /></blockquote>This program demonstrates the bug:<br /><blockquote><pre>function captured() {<br /> try {<br /> handler->();<br /> throw "throw";<br /> }<br /> finally {<br /> alert("finally!");<br /> }<br />}<br /><br />function handler(k) {<br /> k();<br />}</pre></blockquote>The <span style="font-family:courier new;">captured</span> function calls <span style="font-family:courier new;">handler</span>, with the <span style="font-family:courier new;">finally</span> clause on the stack. Then <span style="font-family:courier new;">handler</span> invokes the captured continuation, which places the <span style="font-family:courier new;">finally</span> clause on the stack <span style="font-style: italic;">again</span>. So after throwing an exception, unwinding the stack passes through two copies of the <span style="font-family:courier new;">finally</span> clause.<br /><br />The takeaway for me is that a capturing mechanism that involves a call to a user function has a pigeonhole problem: the suspended continuation ought to capture the <span style="font-family:courier new;">catch</span> and <span style="font-family:courier new;">finally</span> clauses of the function activation, but the call to the handler <span style="font-style: italic;">also</span> ought to be protected by those same <span style="font-family:courier new;">catch</span> and <span style="font-family:courier new;">finally</span> clauses. And yet the <span style="font-family:courier new;">finally</span> block should only executed once per activation. Note that generators do not suffer from this problem, since <span style="font-family:courier new;">yield</span> immediately suspends and aborts the activation, without calling user code in the middle.<br /><br />For what it's worth, I tried the above program with <a href="http://www.neilmix.com/narrativejs/doc/">NarrativeJS</a> and it died with an internal error. But I didn't investigate further, so that may have been a mistake on my part. (It's difficult to tell what NJS should do since the docs don't really specify its semantics.) Nonetheless, I'm starting to think that <span style="font-family:courier new;">finally</span> (and in particular, the intended invariant that finally happens at most once per activation) renders unworkable any attempt to combine continuation-capture with a function call.<br /><br />Actually, there are two more takeaways: 1) the notation of evaluation contexts is a nice way to describe and demonstrate the bug--notice Waldemar's wording!--and 2) thank goodness for Waldemar.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com13tag:blogger.com,1999:blog-10770855.post-6816087848538586082010-04-07T14:50:00.004-04:002010-04-07T15:10:42.963-04:00Harmony first-class activationsThis morning I've been blogging about <a href="http://calculist.blogspot.com/2010/04/delimited-continuations-in-ecmascript.html">single-function activations for Harmony</a>, the <a href="http://calculist.blogspot.com/2010/04/design-space-of-continuations.html">history and design space of continuations</a>, and <a href="http://calculist.blogspot.com/2010/04/thinking-about-continuations.html">informal models and design sketches</a> for control operators. A few more thoughts here.<br /><br /><span style="font-weight: bold;">One-shot continuations</span><br /><br /><div class="" id="magicdomid131"><span class="author-g-hz122z3qsttw90ct9shy">(I won't try to model this in the framework I sketched earlier, because it introduces mutation, and then we have to add a heap to the model, and it gets mucky enough not to be worth it here.)</span></div><div class="" id="magicdomid132"><br /></div><div class="" id="magicdomid133"><span class="author-g-hz122z3qsttw90ct9shy">You can limit the expressivity of continuations to only allow control to enter them at most once. This is totally compatible with most any design we pick along the other dimensions. For example, in the <a href="http://calculist.blogspot.com/2010/04/thinking-about-continuations.html">semantics I sketched earlier</a>, if the callee throws an exception, we throw back into the activation, and it becomes marked as un-reusable. So if the callee saved the captured continuation, invoking it later would be an error. But if the callee calls the captured continuation before returning and then returns normally, the caller skips past the continuation and returns normally.<br /></span></div><div class="" id="magicdomid134"><br /></div><div class="" id="magicdomid135"><span class="author-g-hz122z3qsttw90ct9shy">There's one very subtle aspect of multi-shot continuations that is probably their single biggest liability: <span style="font-family:courier new;">finally</span>. In ES, when you execute a <span style="font-family:courier new;">try</span> block with a <span style="font-family:courier new;">finally</span> block, the <span style="font-family:courier new;">finally</span> block is guaranteed to be executed exactly once (assuming the body of the <span style="font-family:courier new;">try</span> block completes without an infinite loop and the program isn't abruptly terminated). Now, even with one-shot continuations, it's possible that you'll suspend the continuation before the <span style="font-family:courier new;">try</span> block completes and never resume it. But if you do resume it and the <span style="font-family:courier new;">try</span> block completes, it'll still execute the <span style="font-family:courier new;">finally</span> block exactly once.</span></div><div class="" id="magicdomid136"><br /></div><div class="" id="magicdomid137"><span class="author-g-hz122z3qsttw90ct9shy">With multi-shot continuations, you can resume that code as many times as you like, and that <span style="font-family:courier new;">finally</span> block will get executed again and again. (This is analogous to Common Lisp's <a href="http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/speope_unwind-protect.html"><span style="font-family:courier new;">unwind-protect</span></a> and Scheme's <a href="http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_idx_764"><span style="font-family:courier new;">dynamic-wind</span></a>.) This is pretty subtle, and makes it harder to write correct "clean-up" code.</span></div><br /><span style="font-weight: bold;">Implementing JS1.7 generators</span><br /><br /><div class="" id="magicdomid145"><span class="author-g-hz122z3qsttw90ct9shy">One-shot, single frame continuations should be expressive enough to implement <a href="https://developer.mozilla.org/en/New_in_JavaScript_1.7">JS1.7 generators</a> pretty easily. I sent a draft implementation of <a href="https://mail.mozilla.org/pipermail/es-discuss/2010-April/010872.html">generators via one-frame continuations</a> to the es-discuss list. As soon as there's a prototype implementation of single-frame continuations somewhere, it should be possible to test that code (mutatis mutandis).<br /></span></div><br /><span style="font-weight: bold;">My current preference</span><br /><br /><span class="author-g-hz122z3qsttw90ct9shy">So far I sort of prefer the <a href="http://calculist.blogspot.com/2010/04/thinking-about-continuations.html">semantics I described earlier today</a>, with one-shot continuations. But I need to implement and experiment before I trust my opinion. There are certainly questions of API and syntax design that aren't addressed by my design sketches. For that I'd really prefer to look at real callback-heavy DOM code and see what would fit the most smoothly.</span>Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com26tag:blogger.com,1999:blog-10770855.post-19889353183742380992010-04-07T13:57:00.005-04:002010-04-07T15:15:35.380-04:00Thinking about continuationsFollowing up on my <a href="http://calculist.blogspot.com/2010/04/delimited-continuations-in-ecmascript.html">previous</a> <a href="http://calculist.blogspot.com/2010/04/design-space-of-continuations.html">posts</a> about continuations and Harmony, I want to show how I use the modeling tools of evaluation contexts and operational semantics to sketch out informal designs. I'll use a plausible syntax for a new Harmony operator (based on Neil Mix's <a href="http://www.neilmix.com/narrativejs/doc/">NarrativeJS</a>) and start with a reasonably simple semantics based on the well-known shift/reset operators, and sort of work out from there.<br /><br />I'll keep this as light and informal as possible. To stay on point, I'll ignore most of the ES features-- no mutation (so we don't have to model the heap / object graph), and not even scope chains. For a faithful and precise model, we'd need all of these things. But for design sketches, I can afford to be sloppier.<br /><br /><span style="font-weight: bold;">Stacks and activations</span><br /><br />I'll model the stack as a non-empty sequence of function activations:<br /><blockquote>S ::= A | S(A)</blockquote><span class="author-g-hz122z3qsttw90ct9shy">An activation is a function body, but we want to highlight the current statement being executed or expression being evaluated (aka the code pointer). So I'll model the activation as two things: the next bit of code to execute (a statement or expression), and the function body <span style="font-style: italic;">without</span> that bit of code. If the code pointer is at an expression, the activation is a function body with a placeholder that I'll spell <span style="font-family:courier new;">()</span> (an "expression hole"); if it's a statement, the activation is a function body with <span style="font-family:courier new;">{()}</span> (a "statement hole") in place of the current statement.</span><br /><br />For the curious, what I just did was -- informally -- define <span style="font-style: italic;">evaluation contexts</span> for ES.<br /><br />If that was a little too opaque, here's an example. Let's say we have a function<br /><blockquote><pre>function foo(x) { f(x); g(x, 2 * x, null); return x + 4; }</pre></blockquote>If we call <span style="font-family:courier new;">foo(42)</span>, then at first, our current code is <span style="font-family:courier new;">f(42)</span>; and our activation is<br /><blockquote><pre>{ {()} g(42, 2 * 42, null); return 42 + 4; }</pre></blockquote>When we're about to evaluate the second argument to g, then the current code is <span style="font-family:courier new;">2 * 42</span> and the current activation is<br /><blockquote><pre>{ g(42, (), null); return 42 + 4; }</pre></blockquote>When we get to the return statement, current code is return <span style="font-family:courier new;">42 + 4;</span> and the current activation is<br /><blockquote><pre>{ {()} }</pre></blockquote>Notice how after we execute some code, it's gone from the activation; the activation just needs to keep track of the code we have left to run.<br /><br />For talking about the activation and the current code together, I'll write A<span style="font-family:courier new;">(</span><span style="font-style: italic;">expr</span><span style="font-family:courier new;">)</span> or A<span style="font-family:courier new;">{</span><span style="font-style: italic;">stmt</span><span style="font-family:courier new;">}</span>. This is what people call "plugging" code into the hole of a context. Essentially, it's just a modeling trick that makes it convenient to call out where the current code pointer is, but it also turns out to be really natural for talking about first-class control operators-- because it explicitly models the very things we want to manipulate.<br /><br /><span style="font-weight: bold;">Operational semantics</span><br /><br />The above is more or less enough to start writing simple transition rules that describe how programs run, e.g.:<br /><blockquote>S<span style="font-family:courier new;">(</span>A<span style="font-family:courier new;">{return</span> <span style="font-style: italic;">val</span><span style="font-family:courier new;">;})</span> → S(<span style="font-style: italic;">val</span>)<br /></blockquote>In English, this rule says: "in a stack starting with S and with activation A on top, when the next code to execute is the statement <span style="font-family:courier new;">return</span> <span style="font-style: italic;">val</span><span style="font-family:courier new;">;</span> (for some value <span style="font-style: italic;">val</span>), then remove the current activation and place <span style="font-style: italic;">val</span> in the expression hole of the stack."<br /><br />One thing to make clear: this transition arrow describes a runtime state transition of the program, not a compile-time transformation.<br /><br /><span style="font-weight: bold;">Starting with shift and reset</span><br /><br />Here's how a design based on shift and reset might work, specified in one line:<br /><blockquote>S<span style="font-family:courier new;">(</span>A<span style="font-family:courier new;">(</span><span style="font-style: italic;">val</span><span style="font-family:courier new;">->(</span><span style="font-style: italic;">val1</span><span style="font-family:courier new;">,</span> ...<span style="font-family:courier new;">,</span> <span style="font-style: italic;">valn</span><span style="font-family:courier new;">)))</span> → S<span style="font-family:courier new;">(</span><span style="font-style: italic;">val</span><span style="font-family:courier new;">(</span><span style="font-style: italic;">val1</span><span style="font-family:courier new;">,</span> ...<span style="font-family:courier new;">,</span> <span style="font-style: italic;">valn</span><span style="font-family:courier new;">,</span> <span style="font-family:courier new;">function(</span><span style="font-style: italic;">x</span><span style="font-family:courier new;">)</span> A<span style="font-family:courier new;">(</span><span style="font-style: italic;">x</span><span style="font-family:courier new;">)))</span><br /></blockquote>The special syntax of a capturing function call comes is from NarrativeJS. The transition rule describes several things:<br /><ol><li>After evaluating the callee and its arguments, the operator immediately aborts the current activation and saves it in a function.</li><li>Next, it calls the callee with its arguments along with the captured continuation value as an additional argument.</li><li>If the captured continuation is called, it executes the captured function activation, with its new argument plugged into the hole of that activation.</li></ol>There's a serious problem with this semantics for ECMAScript: exception handlers. Aborting A will discard any try or finally blocks in A before we call the function. So you'd get surprising behavior like:<br /><blockquote><pre>function mightFail(k) {<br /> // ...<br /> throw "boo!";<br />}<br />function main() {<br /> try {<br /> mightFail->()<br /> }<br /> catch (x) {<br /> return 42<br /> }<br />}<br />main() // uncaught exception: "boo!"</pre></blockquote>A pretty clear violation of principle of least astonishment.<br /><br /><span style="font-weight: bold;">When to abort</span><br /><br />Having the semantics in such a concise format makes it easy to tweak and experiment with. Let me modify the above semantics in the following way: instead of aborting <span style="font-style: italic;">before</span> we call the callee, let's abort the activation <span style="font-style: italic;">after</span> we return from the call. That way, if it throws exceptions, they'll be caught by any handlers in A.<br /><br />We'll have to invent an expression form that aborts the current function activation after evaluating an expression. This is pretty much just like <span style="font-family:courier new;">return</span>, exception it's an expression form.<br /><blockquote>S<span style="font-family:courier new;">(</span>A<span style="font-family:courier new;">(</span><span style="font-style: italic;">val</span><span style="font-family:courier new;">->(</span><span style="font-style: italic;">val1</span><span style="font-family:courier new;">,</span> ...<span style="font-family:courier new;">,</span> <span style="font-style: italic;">valn</span><span style="font-family:courier new;">)))</span><br /> → S<span style="font-family:courier new;">(</span>A<span style="font-family:courier new;">(</span><span style="font-style: italic;"><span style="font-weight: bold;">RETURN</span> val</span><span style="font-family:courier new;">(</span><span style="font-style: italic;">val1</span><span style="font-family:courier new;">,</span> ...<span style="font-family:courier new;">,</span> <span style="font-style: italic;">valn</span><span style="font-family:courier new;">,</span> <span style="font-family:courier new;">function(</span><span style="font-style: italic;">x</span><span style="font-family:courier new;">)</span> A<span style="font-family:courier new;">(</span><span style="font-style: italic;">x</span><span style="font-family:courier new;">))))</span></blockquote>Actually, we could do this without positing a magic <span style="font-style: italic;"><span style="font-weight: bold;">RETURN</span></span> operator if we have something like the newly-proposed <a href="http://wiki.ecmascript.org/doku.php?id=strawman:let_expressions">let expressions</a>, which allow you to execute statements inside an expression. Then we'd have:<br /><blockquote>S<span style="font-family:courier new;">(</span>A<span style="font-family:courier new;">(</span><span style="font-style: italic;">val</span><span style="font-family:courier new;">->(</span><span style="font-style: italic;">val1</span><span style="font-family:courier new;">,</span> ...<span style="font-family:courier new;">,</span> <span style="font-style: italic;">valn</span><span style="font-family:courier new;">)))<br /></span> → S<span style="font-family:courier new;">(</span>A<span style="font-family:courier new;">(let (x = </span><span style="font-style: italic;">val</span><span style="font-family:courier new;">(</span><span style="font-style: italic;">val1</span><span style="font-family:courier new;">,</span>...<span style="font-family:courier new;">,</span> <span style="font-style: italic;">valn</span><span style="font-family:courier new;">,</span> <span style="font-family:courier new;">function(</span><span style="font-style: italic;">x</span><span style="font-family:courier new;">)</span> A<span style="font-family:courier new;">(</span><span style="font-style: italic;">x</span><span style="font-family:courier new;">))) {return x;}))</span></blockquote>So that's a brief demo of using evaluation contexts and operational transition rules to sketch the semantics of continuation operators.<br /><br /><span style="font-weight: bold;">Edit:</span> I forgot to mention, it's easy enough to specify the behavior of <span style="font-style: italic;"><span style="font-weight: bold;">RETURN</span></span>:<br /><blockquote>S<span style="font-family: courier new;">(</span>A<span style="font-family: courier new;">(</span><span style="font-weight: bold; font-style: italic;">RETURN</span> <span style="font-style: italic;">val</span><span style="font-family: courier new;">))</span> → S<span style="font-family: courier new;">(</span><span style="font-style: italic;">val</span><span style="font-family: courier new;">)</span></blockquote>As I say, just like <span style="font-family: courier new;">return</span> statements, but as an expression form. To be clear, this is just a specification mechanism, not something I'd suggest as a language feature.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com18tag:blogger.com,1999:blog-10770855.post-87460490869665047512010-04-07T13:10:00.007-04:002010-04-07T13:55:42.450-04:00The design space of continuations<a href="http://calculist.blogspot.com/2010/04/delimited-continuations-in-ecmascript.html">I mentioned earlier</a> that the design space for first-class continuations has a lot of historical research behind it. This <a href="http://library.readscheme.org/page6.html">list of papers on continuations</a> up to around 2005 is a start, but by no means complete. (The history of continuations is actually pretty astoundingly far-reaching. Apparently my <a href="http://www.ccs.neu.edu/home/wand">PhD advisor</a>'s <a href="http://cs-www.cs.yale.edu/homes/fischer/">PhD advisor</a> was one of a number of people who <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.237">independently discovered continuations</a> in different research programs and under different guises.)<br /><br />The research literature has been helpful to me in understanding the design space of control operators better, particularly because it gives me good models for reasoning, formally or informally, about control effects.<br /><br />Here are some of the design questions raised by the research literature and good modeling frameworks. This isn't a complete list, and it isn't the place to cite adequately. All I'm interested in is highlighting some of the takeaways<span style="font-style: italic;">.</span><br /><span style="font-style: italic;"><br /></span><span style="font-weight: bold;">How much of the continuation can be captured?</span><br /><br />Scheme's <span style="font-family:courier new;">call/cc</span> allows you to capture the "whole" continuation, up to wherever the language implementor decides is the limit. But delimited continuations make this boundary more explicit, which has a couple benefits. First, by installing a delimiter, you can prevent code that you call from capturing parts of your continuation that you want to keep private. Second, when you capture a continuation, you have a clearer picture of what you're capturing.<br /><br /><span style="font-weight: bold;">What elements of the continuation are captured?</span><br /><br />The answer at first seems obvious: you capture the control context and the environment (aka scope chain). But it gets trickier when you have things like exception handlers and other information associated with the dynamic state of the control context.<br /><br /><span style="font-weight: bold;">What kinds of delimiters do you give to users?</span><br /><br />In our case, we're only interested in an implicit delimiter at function boundaries. But there are a number of different designs of control delimiters.<br /><br /><span style="font-weight: bold;">What kinds of control-abort operators do you give to users?</span><br /><br />Turns out there's at least one in every C-like language: <span style="font-family:courier new;">return</span>. That's probably enough for our purposes. But there are several possibilities there, too, and they can get surprisingly subtle.<br /><br /><span style="font-weight: bold;">Does executing a captured continuation install a new delimiter?</span><br /><br />This is the key difference between <a href="http://portal.acm.org/citation.cfm?id=73560.73576">Felleisen's <span style="font-style: italic;">F</span>/# operators</a> [*] and <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.8753">Danvy and Filinski's <span style="font-family:courier new;">shift</span>/<span style="font-family:courier new;">reset</span> operators</a>. With the former, you capture a continuation up to the nearest delimiter, but when you invoke the captured continuation, there's no new delimiter. With the latter, a captured continuation reinstalls a new delimiter every time you invoke it.<br /><br /><span style="font-weight: bold;">How many times can you enter a continuation?</span><br /><br />The most general design allows a captured continuation to be used any number of times. With "one-shot" continuations, you can only enter a continuation once. Notice that "entering a continuation" could mean a number of things: returning normally, unwinding it by throwing exceptions, or calling into it later via a captured continuation.<br /><br /><span style="font-weight: bold;">When do we abort the current continuation?</span><br /><br />This one is really, really variable. There are many plausible points in the semantics where an exit can occur, and many of them lead to plausible but distinct designs.<br /><br />[*] That's pronounced "eff" and "prompt" -- no relation to <a href="http://msdn.microsoft.com/en-us/fsharp/default.aspx">F#</a>. I just noticed that!Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com108tag:blogger.com,1999:blog-10770855.post-51342011227414692882010-04-07T12:22:00.004-04:002010-04-07T12:37:40.783-04:00Delimited continuations? In ECMAScript?Well, no.<br /><br />Besides breaking a lot of language invariants, first-class continuations would be a nightmare for portability, since different implementations implement different API's natively. Either you mandate capturing continuations across native frames, which is a hardship for implementers and a performance-killer, or you don't, which causes observably different behavior across browsers when they place native delimiters at different points in the continuations-- leading to lots of painful bug reports and nasty market dynamics where everyone has to tailor their implementations to track the most popular.<br /><br />So that won't happen. But!<br /><br /><a href="https://developer.mozilla.org/en/New_in_JavaScript_1.7">JS 1.7</a> introduced <a href="http://www.python.org/dev/peps/pep-0255/">Pythonic generators</a>, which allow you to suspend a single function activation. This alleviates some of the painful CPS patterns people have to use on the web to interact with the event-loop-concurrent, single-thread-of-control semantics of JavaScript on the web. But it's also a little ad hoc. And <a href="https://mail.mozilla.org/pipermail/es-discuss/2010-March/010865.html">Kris Zyp</a> recently made the helpful suggestion that we could explore a design for a simpler, more general single-frame continuation-capture operation for <a href="http://calculist.blogspot.com/2008/08/ecmascript-harmony.html">Harmony</a>.<br /><br />What we're talking about here is a restricted version of delimited continuations: the delimiters are implicit--they're at function boundaries. But otherwise it's very much in that space. And there's a loooot of prior work on this topic. I'll post later with a little background and some notes about the design space of delimited continuations for ES.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com45tag:blogger.com,1999:blog-10770855.post-1680273577758883322010-02-27T21:10:00.003-05:002010-02-27T21:19:47.484-05:00Generalizing JavadotThe idea of <a href="http://jscheme.sourceforge.net/jscheme/doc/javadot.html">Javadot</a> is to allow the rich lexical syntax of Lisp and Scheme with the elegance of the dot-notation from the C tradition by simply allowing scope to trump lexical splitting: if <span style="font-family: courier new;">foo.bar</span> is in scope as an identifier, then it parses as a variable reference; otherwise it parses as <span style="font-family: courier new;">"foo"</span> <span style="font-family: courier new;">"."</span> <span style="font-family: courier new;">"bar"</span>. It's a simple compromise, it's easy to understand, it plays well with lexical scope, and (in an infix language) you can always circumvent it with whitespace. (I don't <span style="font-style: italic;">think</span> it needs to complicate parsing too much, either, since you can do a post-hoc splitting of the lexeme, rather than forcing the lexer to understand scope the way you're forced to with the <a href="http://calculist.blogspot.com/2009/02/c-typedef-parsing-problem.html">C <span style="font-family: courier new;">typedef</span> ambiguity</a>).<br /><br />My question is: couldn't you use this idea in an infix language, and generalize it to work for all infix operators? This would allow the use of other common operators such as -, +, *, /, <, and >, all of which I've loved being able to use in identifier names in Scheme, and all of which I also really like being able to use as infix operators.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com21tag:blogger.com,1999:blog-10770855.post-91029431442319599612010-02-12T13:19:00.002-05:002010-02-12T13:27:05.943-05:00Eich's LawFound this gem in a C++ comment while <a href="http://mxr.mozilla.org/mozilla-central/source/js/src/jsscan.cpp#1464">digging in the SpiderMonkey codebase</a>:<br /><blockquote>After much testing, it's clear that Postel's advice to protocol designers ("be liberal in what you accept, and conservative in what you send") invites a natural-law repercussion for JS as "protocol":<br /><br />"If you are liberal in what you accept, others will utterly fail to be conservative in what they send."</blockquote>The comment is unsigned, but it sounds like Brendan.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com7tag:blogger.com,1999:blog-10770855.post-72962635273856949862010-01-25T22:29:00.002-05:002010-01-25T22:40:10.355-05:00Wading into the CNo time for deep thoughts these days; too much hacking, dissertating, designing, and committeefying going on. Just a couple notes based on recent experiences hacking in C/C++:<br /><br />1. Not being able to rely on recursion makes me sad.<br /><br />2. "Downwards macro-args" in C:<br /><blockquote><pre>#define MY_ENUM_LIST(m) \<br /> m(RED, 0), \<br /> m(GREEN, 1), \<br /> m(BLUE, 2)<br /><br />#define DEF_ENUM_ENTRY(c, v) c = v<br />#define QUOTE_ENUM_ENTRY(c, v) #c<br /><br />typedef enum rgb {<br /> MY_ENUM_LIST(DEF_ENUM_ENTRY)<br />} rgb;<br /><br />const char *rgb_names[] = {<br /> MY_ENUM_LIST(QUOTE_ENUM_ENTRY)<br />};</pre></blockquote>3. I am fast becoming acquainted with <span style="font-family:courier new;">gdb</span>.<br /><br />4. And a few choice command-line shortcuts really save extraordinary amounts of time. My new fav: the <a href="http://www.gnu.org/software/bash/manual/bashref.html#Event-Designators"><span style="font-family:courier new;">!?</span> bash-history shortcut</a>.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com9tag:blogger.com,1999:blog-10770855.post-46016682362536171092009-12-11T14:26:00.003-05:002009-12-11T14:30:31.132-05:00Computer Science Education WeekIn honor of <a href="http://www.acm.org/press-room/news-releases/cs-education-week">Computer Science Education Week</a>, I'll just cite <a href="http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-2.html">a passage I find inspirational</a> about the role of computer science education:<br /><p> </p><blockquote><p>Yet programming is more than just a vocational skill. Indeed, <em>good programming</em> is a fun activity, a creative outlet, and a way to express abstract ideas in a tangible form. And designing programs teaches a variety of skills that are important in all kinds of professions: critical reading, analytical thinking, creative synthesis, and attention to detail.</p> <p> We therefore believe that the study of program design deserves the same central role in general education as mathematics and English. Or, put more succinctly, </p> <div align="center"><table><tbody><tr><td> <strong>everyone should learn how to design programs.</strong> </td></tr></tbody></table></div> On one hand, program design teaches the same analytical skills as mathematics. But, unlike mathematics, working with programs is an active approach to learning. Interacting with software provides immediate feedback and thus leads to exploration, experimentation, and self-evaluation. Furthermore, designing programs produces useful and fun things, which vastly increases the sense of accomplishment when compared to drill exercises in mathematics. On the other hand, program design teaches the same analytical reading and writing skills as English. Even the smallest programming tasks are formulated as word problems. Without critical reading skills, a student cannot design programs that match the specification. Conversely, good program design methods force a student to articulate thoughts about programs in proper English.</blockquote>From "<a href="http://www.htdp.org">How to Design Programs</a>," by Felleisen, Findler, Flatt and Krishnamurthi.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com7tag:blogger.com,1999:blog-10770855.post-88420111330210183232009-11-04T16:30:00.003-05:002009-11-04T16:35:13.722-05:00Ezra: Function calls are not stack framesI don't have much to add to this but <a href="http://ezrakilty.net/research/">Ezra</a>'s saying <a href="http://ezrakilty.net/research/2009/11/function_calls_are_not_stack_frames.html">things that are true</a>:<br /><p></p><blockquote><p>Tim Bray is spreading more misinformation about tail recursion. He describes it this way:</p> <blockquote> <p>It looks like a subroutine call, but in the case where it occurs as the last thing in the routine, it magically, silently, and automatically gets turned into, now how did I put it? “A highly controlled and structured GOTO.”</p> </blockquote> A tail-call <em>is</em> a subroutine call. The efficient implementation does not magically transformed into something else; if it doesn't create a stack frame on such a call, it's because one simply isn't relevant.</blockquote>It's worth reading <a href="http://ezrakilty.net/research/2009/11/function_calls_are_not_stack_frames.html">Ezra's whole post</a>. I especially appreciate his point about confusing semantics with cost model.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com0tag:blogger.com,1999:blog-10770855.post-86392371857092793962009-09-08T10:49:00.004-04:002009-09-08T14:39:48.589-04:00Proposed json.plt changeI'm not sure how many users I have of my <a href="http://planet.plt-scheme.org/display.ss?package=json.plt&owner=dherman">json.plt PLaneT package</a>, nor how many of them read my blog. But I thought I'd see if I could take a straw poll here. I'm thinking about changing the data definition in a backwards-incompatible way. What if I said:<br /><blockquote>A <span style="font-style: italic;">jsexpr </span>is one of:<br /><ul><li style="font-family: courier new;">'null</li><li>boolean</li><li>string</li><li>integer</li><li>inexact-real</li><li>(vectorof <span style="font-style: italic;">jsexpr</span>)</li><li>(listof (cons symbol <span style="font-style: italic;">jsexpr</span>))</li></ul></blockquote>The nice thing about this representation is that it's easier to quote and quasiquote. The down-sides are that array manipulation is a little less convenient, and table lookup is slower.<br /><br />Another alternative is:<br /><blockquote>A <span style="font-style: italic;">jsexpr </span>is one of:<br /><ul><li style="font-family: courier new;">#:null</li><li> boolean</li><li> string</li><li> integer</li><li> inexact-real</li><li> (listof <span style="font-style: italic;">jsexpr</span>)</li><li> (listof (cons symbol <span style="font-style: italic;">jsexpr</span>))</li></ul></blockquote>The nice thing about this is that both arrays and tables are conveniently represented as lists. But it's a little uglier for representing <span style="font-family:courier new;">null</span>, which is necessary to avoid ambiguity between the JSON strings <span style="font-family:courier new;">{ "null" : [] }</span> and <span style="font-family:courier new;">[[null]]</span>. Note that it's also a little more subtle to distinguish between arrays and tables.<br /><br />Other possible unambiguous representations of <span style="font-family:courier new;">null</span> include <span style="font-family:courier new;">#\null</span>, <span style="font-family:courier new;">#"null"</span>, or <span style="font-family:courier new;">#&0</span>. Yech.<br /><br />If you have any opinions, feel free to comment here or email me privately.<br /><br /><span style="font-weight: bold;">Update:</span> Whoops, can't have them both be lists, because of the ambiguity between the empty object and empty array.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com4tag:blogger.com,1999:blog-10770855.post-45574032696169467432009-09-03T17:07:00.002-04:002009-09-03T17:08:54.998-04:00Mitchfest blogWe've created a <a href="http://mitchfest.wordpress.com">Mitchfest blog</a> where we'll be posting updates on new material as it becomes available, including presentation slides, videos, and publication of issues of the Festschrift.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com0tag:blogger.com,1999:blog-10770855.post-2234567516836806212009-08-17T12:52:00.003-04:002009-08-17T12:55:27.512-04:00Quote of the day<blockquote>"What's surprising to me is that this language ever managed to achieve widespread use - but I guess it's just another example of how you can break a whole bunch of precious rules and the sky doesn't necessarily fall in. Software is full of people declaiming their 'thou shalt not' lists, and right across the street there's another bunch of people breaking those very rules quite profitably."<br /> -- <a href="http://lambda-the-ultimate.org/node/3564#comment-50626">Daniel Earwicker</a></blockquote>Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com3tag:blogger.com,1999:blog-10770855.post-33280163333474891102009-08-11T16:28:00.001-04:002009-08-11T16:28:58.529-04:00Mitchfest programWe've posted the <a href="http://www.ccs.neu.edu/events/wand-symposium">Mitchfest</a> <a href="http://www.ccs.neu.edu/events/wand-symposium/program.html">schedule and program</a>!Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com0tag:blogger.com,1999:blog-10770855.post-14039781494527626682009-08-10T07:26:00.004-04:002009-08-10T07:37:12.217-04:00Call for Participation: Scheme Workshop 2009<div style="text-align: center;"><div style="text-align: left;">[<span style="font-weight: bold;">Note: </span>only one day left to register! --Dave]<br /><span style="font-weight: bold;"><br /></span></div><span style="font-weight: bold;">2009 Workshop on Scheme and Functional Programming</span><br /> Co-Located with the <a href="http://www.ccs.neu.edu/events/wand-symposium">Symposium in Honor of Mitchell Wand</a><br /><br /> August 22, 2009<br /> Boston, Massachusetts, USA<br /> <a href="http://www.schemeworkshop.org/2009">http://www.schemeworkshop.org/2009</a><br /></div><br /> <span style="font-weight: bold;">CALL FOR PARTICIPATION</span><br /><br />To the delight of all and sundry, the 2009 Scheme and Functional Programming Workshop will be held on August 22nd at Northeastern University, and it is a signal honor for me to be able to invite YOU to the WORLD'S FOREMOST WORKSHOP on the marvelous Scheme language, and to present a program PACKED with contributions from familiar faces and new ones, certain to amaze, delight, and edify. Lend us your ears, and we will widen the space between them.<br /><br />- John Clements<br /><br /><span style="font-weight: bold;">IMPORTANT DATES</span><br /><br />August 11, 2009 - Registration deadline<br />August 22, 2009 - <a href="http://www.schemeworkshop.org/2009">Workshop on Scheme and Functional Programming</a><br />August 23-24, 2009 - <a href="http://www.ccs.neu.edu/events/wand-symposium">Symposium in Honor of Mitchell Wand</a><br /><br /><span style="font-weight: bold;">VENUE</span><br /><br />Northeastern University<br />Boston Massachusetts<br /><a href="http://www.northeastern.edu/campusmap/map/qad5.html">Curry Student Center</a> Ballroom (Building 50)<br /><a href="http://maps.google.com/maps?q=346+Huntington+Ave,+Boston,+MA+02115">346 Huntington Ave</a><br />Boston, MA 02115<br /><br /><span style="font-weight: bold;">ACCOMMODATION</span><br /><br />A limited block of hotel rooms has been reserved for participants of the Scheme Workshop and/or the Mitchell Wand Symposium at hotels in Cambridge and Boston. See the <a href="http://www.schemeworkshop.org/2009">workshop web site</a> for more information, and please note that some of these special rates have already expired.<br /><br /><span style="font-weight: bold;">REGISTRATION</span><br /><br />The registration fee will be $40 to help cover the operating costs and lunch accommodations. Please register by <span style="font-weight: bold;">August 11, 2009</span> so that we will have an accurate head count. To register, please send an email to <a href="mailto:aoeuswreg@brinckerhoff.org">aoeuswreg@brinckerhoff.org</a> with your name and any dietary restrictions for lunch.<br /><br /><span style="font-weight: bold;">PROGRAM COMMITTEE</span><br /><ul><li>John Clements (Cal Poly State University (organizer & chair))</li><li>Dominique Boucher (Nu Echo)</li><li>Abdulaziz Ghuloum (Indiana University)</li><li>David Herman (Northeastern University)</li><li>Shriram Krishnamurthi (Brown University)</li><li>Matthew Might (University of Utah)</li><li>David Van Horn (Northeastern University)</li></ul><br /><span style="font-weight: bold;">PRELIMINARY PROGRAM</span><br /><br /><span style="font-style: italic;">Invited: If programming is like math, why don't math teachers teach programming?</span><br />Emmanuel Schanzer<br /><br /><span style="font-style: italic;">Invited Talk on Future Directions for the Scheme Language</span><br />The Newly Elected Scheme Language Steering Committee<br /><br /><span style="font-style: italic;">The Scribble Reader: An Alternative to S-expressions for Textual Content</span><br />Eli Barzilay<br /><br /><span style="font-style: italic;">World With Web: A compiler from world applications to JavaScript</span><br />Remzi Emre Başar, Caner Derici, Çağdaş Şenol<br /><br /><span style="font-style: italic;">Scalable Garbage Collection with Guaranteed MMU</span><br />William D Clinger, Felix S. Klock II<br /><br /><span style="font-style: italic;">Distributed Software Transactional Memory</span><br />Anthony Cowley<br /><br /><span style="font-style: italic;">Sequence Traces for Object-Oriented Executions</span><br />Carl Eastlund, Matthias Felleisen<br /><br /><span style="font-style: italic;">Keyword and Optional Arguments in PLT Scheme</span><br />Matthew Flatt, Eli Barzilay<br /><br /><span style="font-style: italic;">Fixing Letrec (reloaded)</span><br />Abdulaziz Ghuloum, R. Kent Dybvig<br /><br /><span style="font-style: italic;">Descot: Distributed Code Repository Framework</span><br />Aaron W. Hsu<br /><br /><span style="font-style: italic;">A pattern-matcher for miniKanren -or- How to get into trouble with CPS macros</span><br />Andrew W. Keep, Michael D. Adams, Lindsey Kuper, William E. Byrd, Daniel P. Friedman<br /><br /><span style="font-style: italic;">Randomized Testing in PLT Redex</span><br />Casey Klein, Robert Bruce Findler<br /><br /><span style="font-style: italic;">Screen-Replay: A Session Recording and Analysis Tool for DrScheme</span><br />Mehmet Fatih Köksal, Remzi Emre Başar, Suzan Üsküdarlı<br /><br /><span style="font-style: italic;">Interprocedural Dependence Analysis of Higher-Order Programs via Stack Reachability</span><br />Matthew Might, Tarun Prabhu<br /><br /><span style="font-style: italic;">Get stuffed: Tightly packed abstract protocols in Scheme</span><br />John Moore<br /><br /><span style="font-style: italic;">Higher-Order Aspects in Order</span><br />Eric Tanter<br /><br /><span style="font-style: italic;">Peter J Landin (1930-2009)</span><br />Olivier DanvyDave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com2tag:blogger.com,1999:blog-10770855.post-75462923391803254492009-08-06T23:41:00.006-04:002009-08-07T18:21:52.586-04:00Selectively disabling tail recursion<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMGGN-8_dGYCMevWToF_IHvt3wFqWiUvs8cVmq3iyEcN_PLLjvgf34flZFtIGmVzzDGScjk-upg6Qoc3fu10tQiH9Latqmn6AH62TLLiqu9qlPZVSdTUkZkX_q8gUvGUHopPEjLA/s1600-h/partial-trace.png"><img style="margin: 0pt 0pt 10px 10px; float: right; cursor: pointer; width: 200px; height: 78px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgMGGN-8_dGYCMevWToF_IHvt3wFqWiUvs8cVmq3iyEcN_PLLjvgf34flZFtIGmVzzDGScjk-upg6Qoc3fu10tQiH9Latqmn6AH62TLLiqu9qlPZVSdTUkZkX_q8gUvGUHopPEjLA/s200/partial-trace.png" alt="" id="BLOGGER_PHOTO_ID_5367067052753799970" border="0" /></a>The anti-tail-recursion crowd often complains about loss of information in stack traces. In DrScheme, if you raise an exception after a sequence of tail calls:<br /><blockquote><pre>(define (fact-iter n acc)<br /> (if (zero? n)<br /> (error 'fact "stop!")<br /> (fact-iter (sub1 n) (* n acc))))<br />(fact-iter 3 1)</pre></blockquote>the stack trace you get back has very little information in it.<br /><br />One argument you'll sometimes hear from people like me is that in a properly tail calling language, you can always turn a tail position into a non-tail-position, whereas the reverse is impossible. But in practice, when you want broadly better diagnostics, manually converting lots of individual function calls throughout a program is too hard to be practical, and you then have to go and undo it afterward.<br /><br />So in the spirit of <a href="http://calculist.blogspot.com/2009/07/linguistic-tools-for-diagnostics.html">linguistic tools for diagnostics</a>, I've discovered a dirt-simple trick for improving the information in stack traces while debugging.<br /><br />PLT Scheme lets you hijack the normal meaning of function application by rebinding the <a style="font-family: courier new; font-weight: bold;" href="http://docs.plt-scheme.org/reference/application.html">#%app</a> macro. So I defined a utility called <a style="font-family: courier new; font-weight: bold;" href="http://planet.plt-scheme.org/package-source/dherman/tail.plt/5/0/planet-docs/tail/index.html">trace-app</a> that wraps its function application in (roughly) the identity function, forcing the given function call out of tail position. Then all you have to do is add to the top of a module:<br /><blockquote><pre>(require (planet dherman/tail:4))<br />(define-syntax #%app trace-app)</pre></blockquote>and suddenly, all function applications that occur syntactically within the current module body are non-tail calls, and <span style="font-style: italic;">voilà</span>:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEja4JUVho5YuFu1GRB5JTp51DghxZqheypjjmTLdXkGTw_BmcqZ8U2Jc7uCE9Oj5GdolMkS3bh8RlKY9scdBKQtwnQ0iVEVKVr5Ej43dS9OwqN00qKLyBsjWSvwcXGjnnmnFJ9XUw/s1600-h/full-trace.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 200px; height: 146px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEja4JUVho5YuFu1GRB5JTp51DghxZqheypjjmTLdXkGTw_BmcqZ8U2Jc7uCE9Oj5GdolMkS3bh8RlKY9scdBKQtwnQ0iVEVKVr5Ej43dS9OwqN00qKLyBsjWSvwcXGjnnmnFJ9XUw/s200/full-trace.png" alt="" id="BLOGGER_PHOTO_ID_5367067230902862322" border="0" /></a><br /><span style="font-weight: bold;">Update:</span> I've posted a <a href="http://planet.plt-scheme.org/display.ss?package=tail.plt&owner=dherman">new version of the package</a>, which exports <a style="font-weight: bold; font-family: courier new;" href="http://planet.plt-scheme.org/package-source/dherman/tail.plt/5/0/planet-docs/tail/index.html">trace-app</a> in a slightly different way. The initial version had a hazard that client modules which used<blockquote><pre>(provide (all-defined-out))</pre></blockquote>would inadvertently re-provide <span style="font-family: courier new;">#%app</span>, which would then disable tail recursion for its client modules.<br /><br />The new way to use it is<blockquote><pre>(require (rename-in (planet dherman/tail:5) [trace-app #%app]))</pre></blockquote>or<blockquote><pre>(require (only-in (planet dherman/tail:5) [trace-app #%app]))</pre></blockquote>Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com0tag:blogger.com,1999:blog-10770855.post-23978968087165754352009-07-22T23:09:00.006-04:002009-07-23T07:21:58.406-04:00Linguistic tools for diagnosticsI've written before about how <a href="http://calculist.blogspot.com/2006/03/call-stack-is-not-history.html">the stack gets misunderstood as a history</a> thanks to non-tail-recursive languages. Of course, stack traces are indispensable: they're essential for debugging, and they're also useful for reporting crash information from live applications.<br /><br />But this conflates two very different language requirements in one feature: the need for nested (unbounded, if your language isn't broken) function application, and the need for diagnostics of dynamic errors.<br /><br />The first is what continuations and stacks are all about, of course: <del>functions can't call each other</del> function calls can't be nested in compound expressions without the language runtime keeping track of the work it has left to do. But the second is an independent need: there's all sorts of diagnostic information that's potentially useful, and the stack just happens to be one source of information that's already there.<br /><br />Now, as it turns out, it's a pretty useful source of information. And if you happen <span style="font-style: italic;">not</span> to have proper tail recursion, it's even more useful, since it provides a path through the function call graph. But I've been finding stack traces in Scheme less informative, because with proper tail calls, there's less function-call history in the continuation.<br /><br />I recognize that sometimes the "complexity budget" in language design necessitates using one feature to satisfy multiple requirements. But I'd like to see more investigation of <span style="font-style: italic;">linguistic diagnostics</span> designed independently of existing language features. For example, it might be useful to provide configurable tracing facilities that record program history during runtime, where the tuning of how much gets recorded is completely independent of the space semantics of the evaluator. So you have a properly tail recursive semantics with a flexible tracing facility grafted on top.<br /><br />What classifies a language feature as "purely diagnostic" might be that it is designed not to <span style="font-style: italic;">change</span> the observable behavior of the program, but merely to <span style="font-style: italic;">report</span> some additional information. <a href="http://www.ece.northwestern.edu/%7Erobby/pubs/papers/fb-tr2006-01.pdf">Contracts-as-projections</a> is an example.<br /><br /><span style="font-weight: bold;">Update:</span> rephrased my rookie characterization of continuations.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com4tag:blogger.com,1999:blog-10770855.post-30863553918324217292009-07-13T23:03:00.004-04:002009-07-13T23:07:04.712-04:00Contractiveness not required for regularity<a href="http://calculist.blogspot.com/2009/07/regular-subtree-set-finiteness.html">Yesterday</a> I wrote about ensuring termination of subtyping for equirecursive types that I thought contractiveness ensures that the (potentially) infinite tree corresponding to a recursive type is regular. That was wrong. Contractiveness just ensures that you can't represent types that don't have a corresponding tree, such as μ<span style="font-style: italic;">A</span>.<span style="font-style: italic;">A</span>. The fact that the tree is regular comes from the fact that the syntactic representation is finite and substitution doesn't add anything new.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com0tag:blogger.com,1999:blog-10770855.post-76235644992614861122009-07-12T17:13:00.004-04:002009-07-12T17:26:36.435-04:00Regular => Subtree set finiteness => Termination of memoized algorithmThe termination argument behind the <a href="http://www.cis.upenn.edu/%7Ebcpierce/tapl/">TAPL</a> algorithm for subtyping of equirecursive types is not as scary as it sounds (or as it sounded to me, anyway). It's as simple as this: even though the subtyping rules generate bigger types when they substitute a recursive type into its own body, the fact that the types are <span style="font-style: italic;">regular</span> means that there are only a finite number of distinct subterms in the infinite type tree--that's the definition of regular trees. So as long as you keep a cache of types you've looked at before and never have to look at the same pair of types twice, you can't do an infinite number of checks.<br /><br /><div style="text-align: center;"><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.boston.com/ae/theater_arts/exhibitionist/Great%20Depression%20Unemployment%20Line.JPG"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 358px; height: 263px;" src="http://www.boston.com/ae/theater_arts/exhibitionist/Great%20Depression%20Unemployment%20Line.JPG" alt="" border="0" /></a><span style="font-style: italic;font-size:85%;" >(Eventually, you run out of work.)</span><br /></div><br />If I'm not mistaken, the syntactic restriction that types are <span style="font-style: italic;">contractive</span>, i.e., recursive type variables have to appear under constructors, is sufficient to guarantee that the corresponding type trees are regular.Dave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com0tag:blogger.com,1999:blog-10770855.post-58338314252026752452009-07-09T00:04:00.005-04:002009-07-09T02:15:07.149-04:00Call for Participation: Symposium in Honor of Mitchell Wand<div style="text-align: center;"><span style="font-weight: bold;">Symposium in Honor of Mitchell Wand</span><br />In Cooperation with ACM SIGPLAN<br />Coordinated with <a href="http://www.schemeworkshop.org/2009">Scheme Workshop 2009</a><br /><br />August 23-24, 2009<br />Boston, Massachusetts, USA<br /><a href="http://www.ccs.neu.edu/events/wand-symposium">http://www.ccs.neu.edu/events/wand-symposium</a><br /></div><br /><div style="text-align: center;"><span style="font-weight: bold;">CALL FOR PARTICIPATION</span><br /></div><br /><br /><span style="font-weight: bold;">IMPORTANT DATES</span><br /><br />August 1, 2009 - Registration deadline<br />August 22, 2009 - <a href="http://www.schemeworkshop.org/2009">Scheme Workshop</a><br />August 23-24, 2009 - <a href="http://www.ccs.neu.edu/events/wand-symposium">Symposium in Honor of Mitchell Wand</a><br /><br /><span style="font-weight: bold;">VENUE</span><br /><br />Northeastern University<br />346 Huntington Ave<br />Boston, MA 02115 USA<br /><br /><span style="font-weight: bold;">ACCOMMODATION</span><br /><br />A limited block of hotel rooms will be reserved for participants of the Symposium and/or the Scheme Workshop at hotels in Boston and Cambridge. More information will be available soon; please check back on the event web site.<br /><br /><span style="font-weight: bold;">REGISTRATION</span><br /><br />Registration is free. Please register by <span style="font-weight: bold;">August 1, 2009</span> so that we will have an accurate head count. To register, please send an email to <a href="mailto:mitchfest-registration@ccs.neu.edu">mitchfest-registration@ccs.neu.edu</a> with your name and any dietary restrictions for lunch.<br /><br /><span style="font-weight: bold;">SCOPE</span><br /><br />Northeastern University is hosting a special Symposium in celebration of Dr. Mitchell Wand's 60th birthday and honoring his pioneering work in the field of programming languages. For over 30 years Mitch has made important contributions to many areas of programming languages, including semantics, continuations, type theory, hygienic macros, compiler correctness, static analysis and formal verification.<br /><br />Please join us at Northeastern on August 23rd and 24th as we celebrate this personal milestone and pay tribute to a great computer scientist, researcher, teacher and colleague, Dr. Mitchell (Mitch) Wand.<br /><br /><span style="font-weight: bold;">STEERING COMMITTEE</span><br /><br />* Olivier Danvy (University of Aarhus)<br />* David Herman (Northeastern University)<br />* Dino Oliva (Bloomberg L.P.)<br />* Olin Shivers (Northeastern University)<br /><br /><span style="font-weight: bold;">PRELIMINARY PROGRAM</span><br /><br /><span style="font-style: italic;">Functional un|unparsing</span><br /> Kenichi Asai and Oleg Kiselyov and Chung-chieh Shan<br /><br /><span style="font-style: italic;">A mechanized bisimulation for the nu-calculus</span><br /> Nick Benton and Vasileios Koutavas<br /><br /><span style="font-style: italic;">A shallow Scheme embedding of bottom-avoiding streams</span><br /> William E. Byrd and Daniel P. Friedman and Ramana Kumar and Joseph P. Near<br /><br /><span style="font-style: italic;">A model of functional traversal-based generic programming</span><br /> Bryan Chadwick and Karl Lieberherr<br /><br /><span style="font-style: italic;">The MacScheme compiler: using denotational semantics to prove correctness </span><br /> William D. Clinger<br /><br /><span style="font-style: italic;">Eliminating the middle man: Learning garbage collection without interpreters</span><br /> Gregory H. Cooper and Arjun Guha and Shriram Krishnamurthi<br /><br /><span style="font-style: italic;">Specializing continuations</span><br /> Christopher Dutchyn<br /><br /><span style="font-style: italic;">A Scheme for native threads</span><br /> R. Kent Dybvig<br /><br /><span style="font-style: italic;">Trampolining architectures</span><br /> Steven E. Ganz and Daniel P. Friedman<br /><br /><span style="font-style: italic;">Finding everything that can happen: Solving authentication tests by computer</span><br /> Joshua D. Guttman and John D. Ramsdell<br /><br /><span style="font-style: italic;">A theory of typed hygienic macros</span><br /> David Herman<br /><br /><span style="font-style: italic;">The MzScheme machine and bytecode verifier</span><br /> Casey L. Klein and Matthew Flatt and Robert Bruce Findler<br /><br /><span style="font-style: italic;">Featherweight X10: A core calculus for async-finish parallelism</span><br /> Jonathan K. Lee and Jens Palsberg<br /><br /><span style="font-style: italic;">Subcubic control-flow analysis algorithms</span><br /> Jan Midtgaard and David Van Horn<br /><br /><span style="font-style: italic;">A simplified multi-tier semantics for Hop</span><br /> Manuel Serrano and Christian Queinnec<br /><br /><span style="font-style: italic;">DDP for CFA</span><br /> Olin Shivers and Dimitrios Vardoulakis and Alexander Spoon<br /><br /><span style="font-style: italic;">The design and implementation of Typed Scheme</span><br /> Sam Tobin-Hochstadt and Matthias FelleisenDave Hermanhttp://www.blogger.com/profile/00405190527081772997noreply@blogger.com0