{"id":65,"date":"2010-01-13T10:26:11","date_gmt":"2010-01-13T17:26:11","guid":{"rendered":"http:\/\/log.jonriehl.com\/?p=65"},"modified":"2013-06-10T09:52:57","modified_gmt":"2013-06-10T16:52:57","slug":"oopsla-2009-and-extensible-languages","status":"publish","type":"post","link":"https:\/\/log.jonriehl.com\/?p=65","title":{"rendered":"OOPSLA 2009 and Extensible Languages"},"content":{"rendered":"<p>I hate to have sat on this essay as long as I have, since it has been over two months since OOPSLA 2009 finished up.\u00c2\u00a0 I hope that later is better than never.\u00c2\u00a0 After rereading this post, I also see one piece of information missing: the part where I drop a little sizzle for myself.\u00c2\u00a0 I presented at <a href=\"http:\/\/www.hpi.uni-potsdam.de\/hirschfeld\/dls\/dls-09\/\">DLS 2009<\/a>, and it went well <a href=\"http:\/\/doi.acm.org\/10.1145\/1640134.1640141\">[Riehl09]<\/a>.\u00c2\u00a0 In that talk I argued for language extensibility and show how the extensibility mechanism in <a href=\"http:\/\/www.mython.org\/\">Mython<\/a> affords easier language embedding and optimization.\u00c2\u00a0 How funny I and other extensible language implementers should stumble into Liskov&#8217;s warning a few days later&#8230;<\/p>\n<p>I have always considered myself fortunate when I get to hear ACM Turing Award winners speak, and this year was no exception.\u00c2\u00a0 I was happy to see <a href=\"http:\/\/www.pmg.csail.mit.edu\/~liskov\/\">Barbara Liskov<\/a> <a href=\"http:\/\/www.infoq.com\/presentations\/liskov-power-of-abstraction\">reprise her 2009 ACM Turing Award lecture<\/a> at <a href=\"http:\/\/www.oopsla.org\/oopsla2009\/\">OOPSLA 2009<\/a>.\u00c2\u00a0 Her talk was interesting for several reasons.\u00c2\u00a0 I found it exciting to listen to her discussion of the history of abstract data types, which were fundamental when I was first learning to program.\u00c2\u00a0 I also liked Liskov&#8217;s review of CLU; It is always humbling to see how little modern systems languages have progressed in the last three or four decades.\u00c2\u00a0 I particularly liked her pointers into the literature, and her injunctions against reinvention of the wheel.<\/p>\n<p>As a researcher, I was particularly interested in her slide and comments about extensible languages: she didn&#8217;t think they were a good idea.\u00c2\u00a0 If I remember correctly, Liskov stated that extensible languages were researched in the 1960&#8217;s and 1970&#8217;s, abandoned as a bad idea, and recent efforts to revive them will encounter the same barriers.\u00c2\u00a0 Before I address this issue further, I&#8217;d like to discuss the two papers she cited for extensible languages:<\/p>\n<ul>\n<li>R. M. Balzer. &#8220;Dataless programming.&#8221;\u00c2\u00a0 FJCC 1967 <a href=\"http:\/\/doi.acm.org\/10.1145\/1465611.1465683\">[Balzer67]<\/a>.<\/li>\n<li>Stephen A. Schuman and Philippe Jorrand.\u00c2\u00a0 &#8220;Definition mechanisms in extensible programming languages.&#8221;\u00c2\u00a0 FJCC 1970 <a href=\"http:\/\/doi.acm.org\/10.1145\/1478462.1478465\">[SJ70]<\/a>.<\/li>\n<\/ul>\n<p>The paper by Balzer does not seem pertinent to my notions of language extensibility.\u00c2\u00a0 Balzer&#8217;s dataless programming language &#8220;feels&#8221; like a special form of aspect-oriented programming, where users define data layout in a special segment of the program specification.\u00c2\u00a0 Algorithms access data through a generic interface for decomposing and iterating through data structures.\u00c2\u00a0 I would note this citation makes more sense in the context of Liskov&#8217;s 1996 history of CLU <a href=\"http:\/\/doi.acm.org\/10.1145\/234286.1057826\">[Liskov96]<\/a>, where the dataless programming language&#8217;s mechanism may have been characteristic of an approach used in other extensible languages:<\/p>\n<blockquote><p>Extensible languages contained a weak notion of data abstraction.\u00c2\u00a0 This work arose from a notion of &#8220;uniform referents&#8221; [Balzer 1967; Earley 1971; Ross 1970].<\/p><\/blockquote>\n<p>The paper by Schuman and Jorrand is more recognizably about language extensibility.\u00c2\u00a0 They present an extensible language, describing facilities for modifying both the semantic and syntactic properties of their language.\u00c2\u00a0 They focus on semantic extensibility &#8220;in the domain of values&#8221;, providing basic mechanisms for user defined data structures.\u00c2\u00a0 Their extension types include support for type casts and name indexed unary operators.\u00c2\u00a0 They do not go into other forms of semantic extensibility, mentioning they are possible, but outside of the scope of this particular paper.<\/p>\n<p>Schuman and Jorrand&#8217;s paper presents a form of concrete syntax macros for syntactic extension.\u00c2\u00a0 They build on top of syntax macros as originally described by Leavenworth <a href=\"http:\/\/doi.acm.org\/10.1145\/365876.365879\">[Leavenworth66]<\/a>, but add additional functionality.\u00c2\u00a0 Schuman and Jorrand&#8217;s macro specifications consist of three things: a production, an optional predicate, and a replacement.\u00c2\u00a0 Their approach feels like a parser description language, where the production is in BNF style, extending the existing grammar of the extensible language, and the replacement is similar to a parsing action.\u00c2\u00a0 Using a production makes their approach able to use a single macro definition instead of having separate forms for expression and statement macros.\u00c2\u00a0 Predicates also allow their macros to do general purpose compile-time metaprogramming, binding values in the compile-time environment used by the replacement clause.<\/p>\n<p>I want to quickly give some credit to Barbara&#8217;s point about reinvention of the wheel.\u00c2\u00a0 I see similarities between Schuman and Jorrand&#8217;s macros and the &#8220;patterns&#8221; proposed in a new language, <a href=\"http:\/\/www.pi-programming.org\/\">\u00cf\u20ac (pi-programming.org)<\/a>, presented by Roman Kn\u00c3\u00b6ll in the Onward! track this year <a href=\"http:\/\/doi.acm.org\/10.1145\/1640089.1640128\">[KM09]<\/a>.\u00c2\u00a0 I think both of these mechanisms present issues of composibility and modularity.\u00c2\u00a0 Schuman and Jorrand do spend some time wringing their hands over this issue, especially since efficiency of compilation was a larger issue when they developed their system.\u00c2\u00a0 Neither of these papers gives me an idea of why these ideas weren&#8217;t developed further and put into the languages I learned as a teenager.\u00c2\u00a0 I can imagine an extensible Turbo Pascal where we were invited to learn more about object oriented programming by implementing our own object system.\u00c2\u00a0 I can&#8217;t trivially find a paper &#8220;Extensibility considered harmful&#8221; that exposes the fatal flaws in extensibility, and explains why I wasn&#8217;t taught to extend my language.\u00c2\u00a0 The impression I got from Liskov was that these systems led to a &#8220;Tower of Babel&#8221; problem, making user programs unreadable, and therefore too difficult to reuse and maintain.<\/p>\n<p>It isn&#8217;t surprising, therefore, that a member of the PLT, <a href=\"http:\/\/www.cs.brown.edu\/~sk\/\">Shriram Krishnamurthi<\/a>, raised this issue during the question period of Liskov&#8217;s presentation.\u00c2\u00a0 The Lisp and Scheme community have lived with syntax macros for a long time, and they seem to get by just fine with them.\u00c2\u00a0 If I understand correctly, these communities see &#8220;language towers&#8221; develop, and they fall in and out of use.\u00c2\u00a0 It&#8217;s unfortunate that I wasn&#8217;t introduced to the <a href=\"http:\/\/www.amazon.com\/Little-LISPer-Daniel-P-Friedman\/dp\/B001L1ELH0\/\">Little Lisper<\/a> until I was about to graduate from college, and even now have to admit I don&#8217;t have my head fully wrapped around the macro system in MzScheme.<\/p>\n<p>I think extensibility is a desirable property, and we can tame the issues it raises.\u00c2\u00a0 Users can use lexical scoping to delimit syntactic extensions, making it clear where they are using custom syntax (see &#8220;Mood-specific Languages&#8221; in <a href=\"http:\/\/doi.acm.org\/10.1145\/1297081.1297086\">[WP07]<\/a>).\u00c2\u00a0 We also have several new approaches to dealing with ambiguity in parsing concrete syntax macros.\u00c2\u00a0 In the limit, our machines are much bigger than they were in the 1970&#8217;s, and the cubic space and time of parsing an arbitrary context-free grammar simply isn&#8217;t the barrier it once was.\u00c2\u00a0 I don&#8217;t see how one can readily prove extensibility is a desirable or undesirable property (though I plan to show one technique I&#8217;m developing for Mython saves a great deal of coding and porting effort).\u00c2\u00a0 The fact that previous extensibility mechanisms were not widely adopted does not prove extensibility is undesirable.\u00c2\u00a0 At worst, this outcome only shows that we haven&#8217;t found the right mechanism or pedagogical tools.\u00c2\u00a0 Therefore, I remain interested in lowering the barriers to the evolution of languages, and seeing what happens.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I hate to have sat on this essay as long as I have, since it has been over two months since OOPSLA 2009 finished up.\u00c2\u00a0 I hope that later is better than never.\u00c2\u00a0 After rereading this post, I also see one piece of information missing: the part where I drop a little sizzle for myself.\u00c2\u00a0 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-65","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=\/wp\/v2\/posts\/65","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=65"}],"version-history":[{"count":22,"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=\/wp\/v2\/posts\/65\/revisions"}],"predecessor-version":[{"id":97,"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=\/wp\/v2\/posts\/65\/revisions\/97"}],"wp:attachment":[{"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=65"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=65"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/log.jonriehl.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=65"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}