" /> Ezra's Research: September 2005 Archives

Main | October 2005 »

September 30, 2005

Gripes with SLinks Implementation

Things to change when we re-do it:

  • OCaml is annoying:
    • Syntax too verbose.
    • Syntax errors are unhelpful (Syntax error)
  • Build objects into a build directory.
  • Get rid of sl_ prefix on everything.
  • Eliminate 'conn which infects all the expression types.
  • Need comment syntax in Links
  • Only one expression is allowed per batch file. Want more to support easy testing.


  • Why are results and expressions different types? Answer: because it separates eval'd and uneval'd objects.
  • Why is the environment split into two values, globals and locals? At least, make it (globals, locals)? Answer: semantics are different; also we want to avoid marhsaling "static" data.
  • How best to do a testing framework in Links?

September 28, 2005

Do CPS transformation on interpreter

I eventually grokked lambda-lifting and worked on some code for it but ultimately I wasn't getting what I wanted out of it.

The larger goal was to have a function from terms to terms: to convert them such that old term was now wrapped in a lambda, expecting a continuation. Phil convinced me this was bunk, since evaluating the new terms still happens according to the same process as the old ones.

The proper goal should have been to modify the *interpreter*. The interpreter, then, should evaluate terms *using* a continuation-passing style. Trying to modify the terms in-place was a bad idea, since it makes them harder to read, messes up the types, and may screw up some other stuff down the road. CPS should simplify things for us, not complicate them! So, I wrote up a lambda-calculus interpreter that uses the continuation-passing style. SML code for this is below.

datatype Term = Const of string | Var of string
              | Thing of string * Term
              | Lam of string * Term | App of Term * Term;

type Envir = (string * Term) list;

(* Kinds of continuations: *)
datatype Cont = FL of Term * Envir
              | Ylppa of Term * Envir;

fun subst(name, term) (Const x) = Const x
 | subst(name, term) (Var x) = if name = x then term else (Var x)
  | subst(name, term) (Lam(param, body)) =
        if name = param then
            Lam(param, body)
            Lam(param, subst(name, term) body)
  | subst(name, term) (App(f, a)) = App(subst(name, term) f,
                                        subst(name, term) a);

exception NoSuchVar of string;
exception NoSuchPrimitive of string;

fun lookup x [] = raise NoSuchVar x
  | lookup x ((vr, vl)::others) = if x = vr then vl else lookup x others;

load "Int";

fun const_apply "inc" (Const a) env = Const(Int.toString (1 +
                                           getOpt(Int.fromString a, 0)))
  | const_apply const (Lam l) env = Thing(const, Lam l)
  | const_apply const arg env = raise NoSuchPrimitive const;

fun appl_cont [] vl = vl
  | appl_cont (FL(t, env) :: rest) vl = eval t env (Ylppa(vl,env) :: rest)
  | appl_cont (Ylppa(t, env) :: rest) (Lam(p,b)) =
        eval b ((p, t)::env) rest
  | appl_cont (Ylppa(t, env) :: rest) (Const c) =
        appl_cont rest (const_apply c t env)

and eval (Const x) env cont = appl_cont cont (Const x)
  | eval (Var x) env cont = appl_cont cont (lookup x env)
    (* FLAW: this doesn't preserve the environment the Lam was evaluated in *)
  | eval (Lam(a, b)) env cont = appl_cont cont (Lam(a, b))  
  | eval (App(f, a)) env cont = eval a env (FL(f, env) :: cont);

fun tleval t = eval t [] []
   handle NoSuchPrimitive prim
        => (print("no such primitive " ^ prim);
            Const "dead");

September 26, 2005

Simplifying, Serializing and Lifting

Today I made a little progress on my CPS transformer for lambda-terms. I can now "simplify" terms (because the CPS'd terms have lots of unneccessary lambda-abstractions) and serialize them. In principle I should be able to serialize the continuations, even though they're not yet defunctionalized, and thereby gain a little clarity on this.

The non-strict evaluation order is still dogging me. I have these terms where the important part is buried in the middle, and won't be forced by anything in my system. This is why I say "in principle." I am getting a term that has "print c" in the middle where c is a continuation, but I'm having trouble forcing evaluation of that.

I read up on lambda-lifting today; the only general resource was the FOLDOC description.

Straw Man Against Static Typing

The paper, "Dyanimic vs. Static Typing—A Pattern-Based Analysis," by Pascal Costanza [linked from Lambda the Ultimate] describes three situations where static typing supposedly provokes the programmer to do more error-prone things than would dynamic typing. All three points are based on straw man arguments, although they elicit good lessons for language designers.

I'll take the three issues in turn. These are all in the context of Java.

Partial implementation of interfaces

This is, of course a common problem: while developing, you need to implement an interface and you want to start testing the methods you've written, without having to implement all the others.

Arguably, in this example, the interface to be implemented is overweening: it requires you to implement subSequence even though it could have a standard implementation that makes use of charAt. Mix-ins are an attractive solution to this kind of problem: a default implementation of subSequence can be given, that calls the subclass's charAt. A more efficient implementation can given when the programmer is ready.

But let's assume that we're given an interface with lots of methods, which are not at all expressible in terms of one another. That's the crux.

Dynamic checking allows you to avoid implementing something if you don't use it.

Static checking finds cases where you've not implemented something, since you don't know whether it will be used by some client code.

This is quite clearly a tradeoff. The paper asserts that dynamic languages "do the right thing" by default, but arguably dynamic languages are just as weak, since they don't give you a choice.

How about compiler settings for dynamicity? "Development mode" allows you to ignore partially-implemented interfaces, while "deployment mode" or "debugging mode" helps you catch them?

How about adding to static languages a shorthand for doing what the author suggests, namely declaring a particular method to to throw an exception?

public notYetImplemented subSequence(int, int);

This would, in effect, tell the compiler to shut up on this particular method, but forces the programmer to think about whether that's the right thing.

For even more brevity, the class declaration could say: "public class FileCharSequence partiallyImplements CharSequence" In this case, a compiler warning should probably warn the programmer that something is wrong.

Exceptions which should be ignored by a mid-level component

The scenario is: A uses B uses C. C will throw an exception. A cares about this exception; B does not. But to pass it on to A, B must be declared with these exceptions which are not "appropriate to its level of abstraction" in the words of the paper's author.

From the outset, there is a failure here in object-oriented design. If B makes direct use of C, it should be designed with C's characteristics in mind. An interesting case is one where B does not make direct use of C, but rather admits a pluggable component which it will call to do the low-level work. In this case, some work needs to be done to adapt the low-level package to fit into B's required interface. For example, an Adaptor class may be written which catches C's exceptions and converts them into exceptions which are declared within the needed interface. When composing reusable software components, this is often the case anyway: method names and signatures must be "rewired" with an Adaptor pattern.

However, an interesting language feature is suggested here. What if it were possible to use a brief "closure" to bind exception handlers around an external component? I have a third-party component called FooReader and my StatsPackage wants to read data from an interface like FooReader's; but FooReader may throw some ugly exceptions which StatsPackage is not prepared to handle. Rather than going out and writing a new Adaptor class, I would like to locally write a short wrapper which says "here's the object you need, but by the way, if this object throws exception X or Y, use this code to handle it." Imagine a construct bindExceptions, which modifies an object to add additional exception handlers--handlers that would be matched for any exception emanating from ANY methods of the object:

new StatsPackage(bindExceptions(fooReader)
               catch (UglyException e)
               { throw new PrettyException(e.description) }
               catch (Ugly2Exception e)
               { throw new PrettyException(e.name)});

Checking feature availability

This last argument is not a flaw of static typing, but rather an interesting quirk of Java which might beg a clever solution. The point here is that there is no atomic way in Java to check whether an object implements a certain method and dispatch to it. Obviously "synchronized" blocks are a decent answer to this need, but perhaps they impose undesirable concurrency properties.

It is true that in most statically-checked languages, we don't allow the kind of thing the author suggests--that is, to just invoke obj.method() and catch an exception if obj doesn't implement that method. But one could easily imagine a method-invocation operator in a statically-checked language which has the alternate signature: that is, instead of checking that the method exists, it could simply allow the invocation, but check that the block catches the MethodNotFound exception.

By contrast, the absolute principle of dynamic checking would argue that the compiler should not check that the exception is handled.

Sometimes static checks are too stringent; sometimes dynamic checks are too loose. The problem is not that one or the other principle is Correct; instead we are sometimes checking the wrong things at the wrong times. As language designers, our goal should be to improve the quality, expressivity, and timing of the checks that occur.

September 24, 2005

The Cat Keeps Coming Back

Today, got a CPS transformation kind of working on a toy lambda-calculus. Something's snagging me up, and it's the collision of CPS with laziness.

As a test term, I'm using variations of this:

call_cc (lambda e. 1 + (if P then 5 else (e 5)))

What should happen? if P is true, we should take the first branch and return 5 from the if, which is then incremented and returned to the top level--the result is "6". If P is false, then we take the (e 5) branch. e is the continuation sent by call_cc, which is effectively the toplevel, so applying e to 5 should simply return 5 to the toplevel and drop everything else.

But in my pure lazy lambda calculus, I don't have a way to tell the interpreter to "drop" everything which is irrelevant. Invoking the continuation should never return, but in this pure setting, there's no natural way to prevent it from returning. I faked it by creating a primitize Print, which prints a value and returns Bot; Bot is like die: evaluating any application that involves Bot just returns Bot, which gives me a way to fake the non-returning quality of the toplevel.

Using Print in the toplevel continuation, I was able to get the desired behavior: by varying P I can get either 6 or 5 as the result of the expression. That feels good! Continuations are working!

Still, this can't be the standard way to do it. How does a continuation "never return" in pure lambda-calculus?

RIFE: Continuations in a Java Web Framework?

Continuations in RIFE, a Java web development framework, look like they might be done right. I'm trying to dig how it's possible to create first-class continuations in a language that doesn't already have them. Check out the description of continuations in RIFE.

September 23, 2005

Closures Considered Neat

Don Box on Scheme:

What I love about this approach [using closures] versus defining a class is that I didn't need to go through the standard 20 questions one typically asks themselves when writing a new class. No class versus struct, interface versus abstract base, or other analysis was necessary. Instead I wrote a program that did what I wanted it to do. Period.

A lot of OO programmers are under the impression that everything should be a class, but there's a lot of baggage that comes with that. Sometimes, indeed, you just need a quickie function: a closure.

September 22, 2005


Questions on my mind:

  • What's a good way to deal with the different layers of code in a web program: DB bindings, data-structure logic, business logic, interface logic?
  • How "functional" are web programs?
  • What about a language for describing web interfaces? A way to say, "Deleting things of type $x$ should require a confirmation, in the following contexts..." A way to avoid writing procedural code for walking the user through an interaction.
  • Use HTML purely as (visual) design space. Describe interactions in a different way, describe algorithms (data manipulation) in a third way.
  • How do we measure prorgammer productivity? Get some papers on this.
  • Learn more about the details of FP and its efficiency.

September 21, 2005

Running Links

In trying to get Links running, here are some things I had to do:

  • edit the OCAML_DIR variable in the Makefile to point at ~/lib/
  • Download the OCaml-PostgreSQL interface from http://www.ocaml.info/home/ocaml_sources.html
    • make it, but not make install--instead I copied its lib directory into my ~/lib/postgresql directory.
  • Download and compile (the same way), these packages: netstring: http://lists.debian.org/debian-devel/2001/04/msg00212.html curl:

  • Had some trouble with the PCRE package, needed by Netcgi_fcgi. The trick in the end was to replace:

export INCDIRS
export LIBDIRS

in OCamlMakefile with

export INCDIRS=/home/s0567141/Downloads/pcre-6.4
export LIBDIRS=/home/s0567141/Downloads/pcre-6.4

  • Lots of trouble building OCamlNet. Jeremy gave me a hacked version of it which worked great. Need to get this checked in alongside the Links source.

September 20, 2005

Web Continuations Review

I think what I want to do first is to build up a review of all the web programming systems that use some notion of "continuations" and compare them. This could be a 2 or 3 page writeup.

Some first notes:

  • PLT scheme seems to have it. Reading "Automatically Restructuring Programs for the Web" by Graunke, Findler, Krishnamurthi and Felleisen
  • Ruby has continuations, but apparently no way to freeze them onto a web page.
  • That "Continuations" rubbish in Jetty.
  • Borges has caches server-side objects from multiple points in a user's session, in order to support the back button.

Playing with toys

What I'm doing today:

  • Screwing around with Haskell (I don't know it very well)
  • Installing Erlang, DrScheme
  • Playing with Eclipse

September 19, 2005

Jetty 'Continuations'

Here's a weird hack called "Continuations" to get a Java Servlet request handler to suspend until there's something to do. It's worth pointing out that invoking the 'continuation' doesn't actually 'continue,' it just re-tries.

This seems workable for the specific case of suspending an event-polling request. Note that it's only working around the threading limitations of Java, anyway. Also note the issue about side effects discussed in the comments.