Syntax Tree Holes

I’ve had in my head a design for an experimental language called meme, whose ideas stem from my very rough concept of tagmemics. But the idea has evolved into a theory that I’m trying to develop called “Holey Syntax Trees”. Basically, you are allowed to leave out constituents and the language will infer what will be there. You could consider it to be a generalization of the concept of “topic” from Perl. For example, you could say:

    for each line in System.stdin.lines:
        print line

But you could also say:

    for each line:

And it would mean the exact same thing. The “in System.stdin.lines” would be inferred from the name of your variable, and the fact that System.stdin is in the “search path” for inference. The “line” would be inferred topically like in Perl (the thing you’re most likely to be talking about is the thing you’re iterating over, in this case).

I’ve started programming this project a couple times without it going anywhere. I’ve decided that the hole filler needs to have theoretical backing, because doing it heuristically is going to end up getting all the examples I thought of right and everything else wrong. In order to infer in a sensical way, the program will have to pull information from all kinds of places. So the first thing I’m going to try to do is to build a “partial AST”:

    for (each "line" HOLE) (line -> print HOLE)

And then use attribute grammars to transform the partial AST into a complete AST. Each function probably needs to have its own hole-filling rules (or break the functions into classes of similarly-inferring functions). So what do those rules look like?

Let’s just try to get this example. Let’s start with print.

    App "print" ? → App "print" @topic

Where @topic might represent an attribute in the AG, and ? represents a literal hole. On to each.

    App "each" [x, ?] → App "each" [x, {search for collections named plural(x) or x}]

(My hand is getting tired from waving around so much). Finally for:

    App "for" [?, body] → App "for" [@topic, body]
    App "for" [coll, body] :- body.@topic = coll.@name

The second of those rules says that, in “for”, the topic of the body is equal to the name of thing thing being iterated over. Hmm, I’d like to concretify these more, but I’m out of time.


1 thought on “Syntax Tree Holes

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s