Home » forums » LtU Forum

Exploration of Program as Language

Onward 2009 essay* by Elisa Baniassad and Clayton Myers.

A well written essay that argues how programs form their own unique and self describing languages. Whereas programming languages have formal execution and are designed for the programmer to tell the computer what to do, program languages communicate what the program does to other programmers and (over time) to the programmer themselves. They claim that programming languages and program languages are inversely related in complexity: a higher-level programming language allows our program language to be simpler, which makes sense.

A couple of implications that I found interesting: First, perhaps we have to teach program languages as well as programming languages; e.g., knowing Java != knowing how to hack Eclipse code, we have to learn a lot about Eclipse through documentation and studying its source code first. Second, code migration (moving code from one program to another) is essentially language translation as the code must be translated from its from-program language to the to-program language, even if the programming language hasn't changed.

Ralph Johnson also has a good blog post on the essay.

* Unfortunately, the only link I could find was behind the ACM paywall. The paper hasn't made it to the author's homepage yet.

By Sean McDirmid at 2009-12-29 23:52 | LtU Forum | previous forum topic | next forum topic | other blogs | 5239 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

From Ralph's blog (emphasis mine)

Afterwards, Dave Ungar said "This is all obvious to anyone who has programmed a long time. What is new?"

What is new is that people have not studied programs as languages. It might be an obvious idea, but it has not really been explored. When researchers study programming, they think of it as theorem proving or theory building, but not as constructing a new language. They have not taken ideas from linguistics and applied them to programs. The talk didn't give much insight into how linguistics shines a light on programming, except by using the analogy that learning a large program is a lot like moving to Hong Kong and learning Chinese.

This is not true. While it's probable David Ungar and Ralph Johnson are both unaware of examples, they do exist. Case in point: The book Emergence of Communication and Language contains a number of interesting essays, including one by Luc Steels (who has some interesting essays about robots forming social languages that I've wanted to put on the front page for awhile).

Also, another example of 'program as language' is Uwe Assmann's work on Invasive Software Composition. Through the use of metamodeling he deconstructs all forms of composition systems. In order to retrofit a modularization design theory into a component language, you define composers and a componenet fragment language.

I think what Ungar was criticizing was how plain the paper comes across. I did like one point in the paper that I'll provide for readers without ACM access:

In Haskell, for instance, more of the program abstractions can be expressed directly as code abstractions; this is even more true when combined with mathematically minded programmers. This means that the program language (for high-level programming languages) is composed more of radicals, and less of compound “words”; this makes individual words in the language more synthetic and complex, but also decreases the need for complex uses of the program language. The higher level the concepts that can be expressed in the programming language formalism, the less remains for the informal program language to handle.

What I like about this point is that it is some of the most elegantly stated advice on design trade-offs and composition. It ranks right up there with Abelson & Sussman's SICP advice to build systems out of associative operators where possible.

[Edit below for more stuff]

Here is one other thought to explore from the paper:

Consider the common pattern of lock—do stuff—unlock. This is an idiom that is common across all interconnected programs, and hence is not an artifact specific language element. However, it provides an analogy by which to show that there exists a certain grammar in programs themselves that is at a higher level than the programming language grammar. Its basic rules are: you cannot unlock when you don’t have a lock; You shouldn’t do stuff before you have a lock; You shouldn’t lock and then immediately unlock, and then do stuff. If we were to write this in a context-free way, it would look like:
<locked-code> :- <get lock> <do stuff> <unlock>

This reminds me of Matthew Parkinson's position paper about component languages based upon class invariants: Class Invariants: The end of the road?. Parkinson is a separation logic guy, and member of the East London Massive cliq. His Observer pattern example is very much an idea stated in the same vein, and makes the case that component languages should use different assertions than class invariants, thus managing the definition of a 'component' based on use-site, rather than simply declare-site. Likewise, Parkinson's essay is not at all shocking to anyone who does UML Model Driven Engineering. Yet the basic idea is right in that this approach may be better than making a wholesale switch to another paradigm. My only caution is that too many authors pidgeonhole the structure of a design pattern according to its GoF formulation. First, not all design patterns have such structure. Second, most if not all GoF-specific design patterns could be found in a more generalized context, such as decoupling Observer from Subject via use of a Registry. [Edit: Third, some GoF design patterns are not best implemented with classes at all, but rather via mixins and traits. For example, the GoF State pattern is the ideal way to implement a contract that says the object migrates between various roles that have associated behaviors (you can do this in Scala and in Moose and with some flavors of Smalltalk). Implementing the GoF State pattern with classes directly is just plain ugly and lacks cohesive design properties - unless you are programming in a object-oriented simulation language like Beta with a first-class component fragment language for reuse of component building blocks.]

By Z-Bo at Wed, 2009-12-30 00:20 | login or register to post comments

Great direction. "Programs

Great direction. "Programs as languages" seems a good extension of the "libraries as languages" that most functional programmers are used to.

By naasking at Wed, 2009-12-30 04:51 | login or register to post comments

You mean DSLs?

You mean DSLs? They have a section that compares against that in their essay.

By Sean McDirmid at Wed, 2009-12-30 05:49 | login or register to post comments

Ralph's post distinguishes

Ralph's post distinguishes programming languages as "formal" languages, and program languages which are not formal. EDSLs are thus formal languages, but any library is a language in the same sense that programs are languages, if only poorly specified/informal languages. I'd definitely read the paper if it becomes publicly available.

By naasking at Wed, 2009-12-30 19:33 | login or register to post comments

Indeed

Indeed, programs can be seen as much more than... "just" programs.

I intend to (self-)publish an essay (on the rationale/design/underneath-theoretic digging/design choice of Y#).

That would go to elaborate about those intermediary observations (of thought) :

And, even more than "just" language, programs can actually be seen as subsets of theories (in a Logic and Maths sense) made "tangible" in an ad hoc fashion (by us, humans), through a programming language, and that are executable.

Those "tangible" subsets of theories, you can verify them being valid or not (note: valid, but not forcibly sound). You can, by the mere fact of executing them (the programs) against input environments.

When they terminates, they prove us that it exists at least one (output) environment/structure for the theorem's conclusion. Where's the theorem, from this PoV? It's "roughly" (need more precision, more formalism, more disciplined research, of course!) the data of:

1) the program itself;
2) the entry premises implicitly held or not, given by the program's input environment.

Is it a new theorem for mathematics themselves, for every new program? (Unclear to me, I only dared speculating a bit, there, from that specific PoV)

Anyway, I don't feel like having the strength to study further that aspect of PLs about the full implications on today's "standard" views of the definition of computability otherwise (Church Turing, etc). I'm not competent on such "hard" matters.

But, I will try to show it can be re-used as a useful (thinking-)framework in "softer" matters, where, precisely, the need for a strict computability theory is less "invading"/critical, and where it becomes relevant to take also into account the human activity's dimension -- for this instance, what can be another way to look at the principles underneath the construction of DSL-oriented model-to-artifact tool chains. I suppose it's more appropriate to use "principles" there, instead of "theorems".

The main difference between the latters and PLs with interpreters/runtime envs., is as follows. In the case of modeling tool chains with intermediary artifacts yielding others thru model processing tools, the resp. semantics of the agents/artifact producers are much more, by very construction, loosely-coupled, and practically never formalized anywhere. Still, they produce useful programs, libraries, that run (and produce the expected results), in a chain of worker programs, along with other config assets produced via code generators, template engines, and the like. All these producers proceed at many different levels; be they involved in generating business logic code, technical layers code, configurations, human-targeted documents, or schemas (often enters XML, then) for intermediary structured vocabularies validation, etc.

All this metadata "glue" we human designers present in, either type systems or in form of intermediary file system artifacts, be it consciously or not at all, allows for that to work in the end, and even when those executable peers in the tool chains (say, "model transformers") only communicate via partial/incomplete contracts, when we look at it at the closest. Thus, the so-called "loosely-coupled semantics", yet that turns out to be a single, "compact" one eventually, as if it were a single input-to-ouput producer program -- from the very first input models up to what you consider to be the final result of your modeling-artifacts chain.

Now, the crux of the issue my essay will be concerned with, in the case of aiming at building scalable DSLM-based software factories, is :

in the case of those DSL-modeling tool chains -- that are yet to come strictly speaking (and I suspect will inevitably do en masse, with platforms like SSM which probably happens to be merely the first of the kind for that broad a scope, and there'll always be room for innovation by others...) -- the usage of metadata is critical to ensure the minimal consistency / interoperability requirements between artifacts relying upon different technologies/implementations, programming/computation paradigms (functional vs. OO), etc.

Thus, I'm indeed speaking of all those "requirements" actually unexplicited (to the dumb computer), and accompanying also unformalized constraints, except for, again, in the brains of the software architects, developers, etc.

It's not an issue when the platform doesn't enable ever easier creation of new DSLs and processing tools. Because you can still rely on transmitting the intent of one model/artifact type's consumer/producer to the others by ad hoc config or, etc in the various tools' implementations themselves. You do so typically and purposely, so that you can safely assume later on (in the usage of the tool chain you're building) "them tools know each others enough", and are parties of the same, "controlled" modeling chain's input-to-expected-output context set -- that you know in its entirety, because you decided about its scope. But what to expect when you leave this strong assumption, when your modeling-driven tooling may encounter a new DSL, for some new technological or business domain-grounded purpose, anytime? Can we afford to leave the burden of making the decision/choosing the proper processing, on the DSL model's acceptor implementations only?

And, on the DSM potential's orientation of our thinking: when a newcomer DSML is around, how about trying to have the tooling "discover" by itself about yet unexpected, but turning it out to be useful for some purpose, capabilities of it (as a language)?

If these points above are seen as a sensical concern in that large an extent, then it really feels like a paradigm shift, that might impede the scability of the whole "Domain-Specific Modeling in-the-large" scheme, eventually (IMO).

The current trend of PLT is to try go towards maximal "provability" and "contractualization" in programs specifications, but only "locally" (which is a TOTALLY good thing in the long run for Programming Languages, of course) versus "globally", i.e., throughout the models-to-artifacts chain as a whole. Conversely, I believe this is something we just cannot achieve per today's state of computer language science and technologies, when dealing with unpredictable -- a priori -- appearances of very diverse, arbitrary Domain-Specific Languages that will be invented by people. Such languages will be wildly thrown in the tool chains, and even if we could predict when, most of them won't be "clean" enough to come with a uniformally, comprehensively formalized semantics. Let alone, even when semantic formalization is present, today's C.S. is still trying hard to have automatic subject-reduction proof tools standardized enough, for its own purpose...

And, the notation I used for that purpose of representing today's reality from this point of view let us suspect several times, in different contexts, the same thing. That such metadata, meant to talk "at a minimum" about some otherwise sub-specified/unformalized (then, unverifiable) semantics in modeling tool chains, cannot be satisfying if presented in the form of reifications only at the type system's dimension (in the models' processing programs/code).

Hence, the dire need for some "standard" / easily available reifications, as those models' meta data, at the input model's language dimension, more likely, instead (by analogy to reflective type systems representing reflected types with instances of another type, or some agreed serialization, etc).

(Well, it's already presented in my current Y# rationale; still rather clumsily/verbosely, though; its rephrasing is still ongoing, on there)

[FINAL EDIT 12/30/09; 11:40AM EST]

By Cyril at Wed, 2009-12-30 06:20 | login or register to post comments