Inversion

I want to talk briefly about a powerful language implementation technique, but I don't have any sample code for this one, because any sample code I provided would have all sorts of little fiddly bits which would distract from my main point. The technique is inversion, and it is increadibly powerful.

I could tell you that inversion is the process of turning a program into a tool, or that inversion is the act of re-writing a program to externalize it's game logic, or even that inversion is the process by which an API is wedded directly to a runtime environment, and the program is left for later. Maybe these descriptions are helpful, maybe they aren't, but they do set the stage.

Let's say that I've got a program which does something with, say, image files. That program is supported by a large API, and the API is supported by a complex environment which must be setup and torn down. So the program, roughly speaking, runs like this: first, it parses its arguments, and exits early if there is a problem (or help was asked for), then it sets up its environment, then it runs it core logic, a rather small program "written" in the language of the API, which actually does the work, then it tears everything down, and exits. If you want to add a new feature, you need to add a new bit to the API, or to the core logic, and sometimes to both. But as the API grows more powerful, more and more features are just additions to the core logic. And the core logic needs to be very general, because it can't be changed by the end user.

To invert such a program, we would stick a language interpreter in where the core logic currently resides (a big deal for compiled languages, but trivial for scripting languages). Then, interesting new applications of the API can be had by putting together a new little core program which runs in a language defined in terms of abstractions on the API, and that program can be very simple, because it need only handle its immediate application.

YubNub and Articulated Keywords

http://yubnub.org/

Previously, I posted on articulated keywords, which might better be described as location bar commands. Well, YubNub is location bar commands writ large. The service provides a means of matching (and acting on) hundreds (thousands?) of commands, of defining new commands, and of commenting on the commands. All from adding a single keyword bookmark.

XML Macros

http://littlelanguages.com/web/languages/xmlmacros/

There are many complex things which can be done with XSLT, and because of this, many people overlook the very simple things which XSLT can also provide. Previously, I discussed XSLT page compilers, but there is a technique buried in that idea which I thought should get some more light, so I'm presenting it here as it's own thing.

Due to the way that XSLT processing descends, it is possible to use the XSLT identity transform in adition to some simple templates to write XSLT transformations which behave very similarly to hygenic macros (possibly identically, but my Scheme is still weak, so I'm avoiding that statement). You can extend existing XML languages with new elements, and use simple XSLT documents to resolve those elements down to the base language which you are extending.

This often proves to be a powerful technique, especially when designing new languages, as a macro resolving transformation can be performed on your new language before the transformation which provides its semantics, dramatically reducing the implementation complexity. The basic approach resolves arround that old workhorse of XSLT hackers, the identity transform:

<xsl:transform version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

<!--
 ! This transform provides a guide towards defining
 ! XML macros using XSLT. We expand only our XML
 ! extensions, and preserve everything else in a
 ! document.
 +-->

<xsl:template match="node()">
  <!--
   ! This is an identity template in XSLT. However,
   ! due to the very low specificity (a technical
   ! aspect of XSLT) of the match, other templates
   ! will override this one when they match.
   +-->
  <xsl:copy>
    <xsl:for-each select="attribute::*">
      <xsl:copy/>
      </xsl:for-each>
    <xsl:apply-templates/>
    </xsl:copy>
  </xsl:template>

<xsl:template match="bi">
  <!--
   ! This defines the element 'bi',
   ! which is both bold and italic.
   +-->
  <b><i>
    <xsl:apply-templates/>
    </i></b>
  </xsl:template>

<xsl:template match="def">
  <!--
   ! This defines the element 'def',
   ! which provides a link to search the web
   ! for the definition of a term.
   +-->
  <a href="http://google.com/search?q=define%3A{.}">
    <xsl:value-of select='.'/>
    </a>
  </xsl:template>

</xsl:transform>

Which permits us to transform this input document, which isn't quite HTML:

<html>
<head>
  <title>Sample</title>
  </head>
<body>
Here is <bi>my</bi> page,
 and I like <def>monkeys</def>.
  </body>
  </html>

Into this output document, which is pure HTML:

<html>
<head>
<meta http-equiv="Content-Type"
 content="text/html; charset=UTF-8">
  <title>Sample</title>
  </head>
<body>
Here is <b><i>my</i></b> page,
 and I like
 <a href="http://google.com/search?q=define%3Amonkeys">monkeys</a>.
  </body>
  </html>

List Resolution Techniques for Grammar Development

http://press.samedi-studios.com/drafts/dunnavant2004list_resolution/dunnavant2004list_resolution.pdf

This is a paper I wrote a while back, cribbed together from a utility fragment of my thesis. It doesn't present anything new, but I think it does a good job of communicating some techniques which are quite useful in practical grammar developmen, a subject which I have always thought was to little discussed. It is only three pages, and I think it is pretty easy to read. I would post it here, but I'm too lazy to try and translate LaTeX into blogger.

Update: I've messed about with latex2html, and I've uploaded an html version to:
http://littlelanguages.com/web/crutcher/lrtgd/index.html

Abstract: Most popular parser generation tools work in terms of grammar rules which are not directly capable of providing list semantics. While the basic techniques for realizing list semantics are frequently re-invented, the literature has suffered from a lack of a solid collection of these techniques. This paper presents a collection of techniques for realizing various forms of lists as grammatically re-written forms using AST re-writes compatible with most parser generation environments. Also provided is a set of additional EBNF extension operators for specifying AST re-write actions.

A Pattern Language for Language Implementation

http://press.samedi-studios.com/publications/2004/jones2004pl4li.plopD5/jones2004pl4li.pdf

This is a paper from a while back that we workshoped at PLoP 2004. We are still shopping about for a place to publish it, but it hase some valuable things to say about language implementation.

Abstract. Programming languages are typically considered to be difficult to implement. However, a programming language tailored to an application domain can be an extremely powerful productivity enhancer. We present a pattern language for implementing languages that gathers together many ideas that are known in the language implementation community that should be more widely known. By applying this pattern language, productivity can be increased by the blossoming of more programming languages tailored to a specific purpose. We begin by discussing some of the dichotomies that shape the language design process. The pattern language itself consists of patterns describing various language flavors, and patterns for doing syntactic recognition, evaluation, and source production.

CommandLoop module in python

http://littlelanguages.com/web/software/python/modules/cmdloop.py

Here's a python module which provides a base class for writing simple interactive command loop environments. It makes use of python 2.4 decorators to describe the command functions.

CommandLoop provides a base class for writing simple interactive user environments. It is designed around sub-classing, has a simple command parser, and is trivial to initialize.

Here is a trivial little environment written using CommandLoop:

import cmdloop

class Hello(cmdloop.CommandLoop):
  PS1='hello>'

  @cmdloop.aliases('hello', 'hi', 'hola')
  @cmdloop.shorthelp('say hello')
  @cmdloop.usage('hello TARGET')
  def helloCmd(self, flags, args):
    '''
    Say hello to TARGET, which defaults to 'world'
    '''
    if flags or len(args) != 1:
      raise cmdloop.InvalidArguments
    print >> self.OUT, 'Hello %s!' % args[0]

  @cmdloop.aliases('quit')
  def quitCmd(self, flags, args):
    '''
    Quit the environment.
    '''
    raise cmdloop.HaltLoop

Hello().runLoop()

Here's a more complex example:

import cmdloop

class HelloGoodbye(cmdloop.CommandLoop):
  PS1='hello>'

  def __init__(self, default_target = 'world'):
    self.default_target = default_target
    self.target_list = []

  @cmdloop.aliases('hello', 'hi', 'hola')
  @cmdloop.shorthelp('say hello')
  @cmdloop.usage('hello [TARGET]')
  def helloCmd(self, flags, args):
    '''
    Say hello to TARGET, which defaults to 'world'
    '''
    if flags or len(args) > 1:
      raise cmdloop.InvalidArguments
    if args:
      target = args[0]
    else:
      target = self.default_target
    if target not in self.target_list:
      self.target_list.append(target)
    print >> self.OUT, 'Hello %s!' % target

  @cmdloop.aliases('goodbye')
  @cmdloop.shorthelp('say goodbye')
  @cmdloop.usage('goodbye TARGET')
  def goodbyeCmd(self, flags, args):
    '''
    Say goodbye to TARGET.
    '''
    if flags or len(args) != 1:
      raise cmdloop.InvalidArguments
    target = args[0]
    if target in self.target_list:
      print 'Goodbye %s!' % target
      self.target_list.remove(target)
    else:
      print >> self.OUT, \ 
        "I haven't said hello to %s." % target

  @cmdloop.aliases('quit')
  def quitCmd(self, flags, args):
    '''
    Quit the environment.
    '''
    raise cmdloop.HaltLoop

  def _onLoopExit(self):
    if len(self.target_list):
      self.pushCommands(('quit',))
      for target in self.target_list:
        self.pushCommands(('goodbye', target))
    else:
      raise cmdloop.HaltLoop

HelloGoodbye().runLoop()

Articulated Keywords

http://littlelanguages.com/web/languages/articulated-keywords/keywords.html

Firefox's Bookmark Keywords

In Firefox, you can set a keyword for a bookmarked page. This keyword can be typed in as a shortcut to the location bar. If the bookmark link has a "%s" in it, then the text after the keyword will be substituted in.

For example, if the user had a bookmark (with the keyword 'k') of:

http://foo.bar.org/search?q=%s

And the user typed in:

k foo bar baz

Then the browser would construct:

http://foo.bar.org/search?q=foo bar baz

Creating articulated keywords

Given Firefox's bookmark keywords, and javascript's abaility to access the query string of the url, it is possible to write bookmarks which jump to pages which parse the query as a command sequence. Such command dispatch systems usually treat the first variable token as a command, and dispatch to functions registered on those names.

Note: it is also possible to bookmark 'javascript: ...' links, called bookmarklets. These can be quite useful, but require updating, while the articulated keywords method described here need users to set it once, and can be updated in a suite, and all users will see the updates.

A sample implementation is provided in keywords