Program Rewriting

[David Barbour]

I've been taking a serious look at program rewriting recently. 

By 'program rewriting', I mean taking a general purpose programming language with rewriting semantics, and directly implementing those semantics as the primary mode of evaluation. For example, we might create an 'evaluator' process that takes as input a program, chugs and churns, then outputs a valid representation of the same program. There is no additional input outside the program itself, though we could explicitly inject some inputs into our program before providing it to our evaluator. There are no side-effects outside the resources (time, space, energy) required for evaluation. No outputs beyond a program and some heat.

Program rewriting isn't a new idea to me. However, I've never considered it seriously. It's further from the mainstream even than purely functional programming. Also, my last real exposure to term rewriting was circa 2004, many years before I grokked monadic effects models and how programming without side effects could possibly be a thing. So, I've always been somewhat dismissive of rewriting.

But I'm taking a serious look now, inspired from a passing mention in a forgotten article. And I believe that, taken together with pure effects models, program rewriting could eliminate or ameliorate a LOT of software engineering problems, including:

* resource management - evaluating with quotas

* debugging, both active and after action

* rendering animations of program evaluation

* partial evaluation and staging

* expressive spreadsheet style HCI

* integration of domain specific languages

* lightweight linking and separate compilation

* working with very big data and code

* efficient orthogonal persistence

* simplified serialization, input validation

* parallelism and distributed computing

I decided to take today off my normal labors and instead write a blog article [1] detailing the above points, especially the debugging stuff. A lot of the points interact with and augment each other.

[1] https://awelonblue.wordpress.com/2016/08/29/program-rewriting/

Thoughts and comments are welcome. But as an example, I'll expand on one point here:

* expressive spreadsheet style HCI

With program rewriting, our input is a program and our output is a different representation of the same program. In the trivial case, our program might be `(11 + 12)` and our evaluated program `23`. Most spreadsheet languages don't go too far beyond what I'd consider trivial cases. But if we use rewriting as the basis for evaluation of a general purpose language, we can both perform meaningful, useful evaluations even for functions and objects. And we can always render this result, minimally as a program. If our program represents an object of appropriate type, the spreadsheet might additionally know how to render it graphically. 

[John Carlson]

Seems like you really want programming by demonstration ala Bret Victor? Where variables become boxes with values in them.  How does program rewriting help programming by demonstration?

--
You received this message because you are subscribed to the Google Groups "Augmented Programming" group.
To unsubscribe from this group and stop receiving emails from it, send an email to augmented-programming+unsub...@googlegroups.com.
To post to this group, send email to augmented-programming@googlegroups.com.
Visit this group at https://groups.google.com/group/augmented-programming.
For more options, visit https://groups.google.com/d/optout.

[John Carlson]

I kind of wonder about the choice of DSLs over desktop apps:  Number calculators, date calculators, string calculators, table lookups, array calculators etc.    Seems like you could package a DSL into an app and make it so more people could use it.  You just need a DSL integrator (a recorder app).   See my paper. Or AppleScript.

To unsubscribe from this group and stop receiving emails from it, send an email to augmented-programming+unsubscri...@googlegroups.com.

[John Carlson]

And then I wonder if there is a real difference between a DSL, a class, a microservice, and an app.

[John Carlson]

An app specifying the legal input and output grammar in DSL terms.

[John Carlson]

In more other words, focus on the user interface, so more people can program using your language.

John

[John Nilsson]

I've been contemplating a rewriting based language, with spreadsheet inspired HCI for a while now. A thought that struck me just the other day was that this is essentially what Conal Eliotts Tangible Functional Programming is: http://conal.net/papers/Eros/ so there's some inspiration

BR,

John

--
You received this message because you are subscribed to the Google Groups "Augmented Programming" group.

To unsubscribe from this group and stop receiving emails from it, send an email to augmented-programming+unsub...@googlegroups.com.

[John Nilsson]

To expand a bit.

The language I had in mind was to be an interactive environment, in the way Small talk was, implementing a kind of meta language workbench. Unlike you, i guess, I was imagining this to be a staged environment, where the final output was a program binary. An interactive compiler if you will.

Small focused DSLs, in the style of VPRIs chains of meaning, would be defined as interpreters (here viewing interpreters as more or less isomorphic to objects in OOP, thus borrowing much of the machinery for composition, abstraction and validation from the OOP camp, but with a focus on composable DSLs, not unlike OMeta/Ohm).

Like you mentioned in the post, I also saw subprograms as linked through cryptographic hashes. Making version control an integral part of linking. I'm a fan here of elms forced semver. Perhaps one could implement versioning of modules by hashing interfaces and unit tests.

BR,

John

To unsubscribe from this group and stop receiving emails from it, send an email to augmented-programming+unsubscri...@googlegroups.com.

[David Barbour]

Thanks for responding, John and John. I'll respond in chronological order.

I find Bret Victor's works inspiring, but I don't believe "variables as boxes with values in them" is what I want. My vision leans towards a more physical metaphor, where computation is represented by objects in our environments that we can connect, compose, dissect, and share. Not standing 'above' the code like a dumb god, gazing at variables and hoping to comprehend them, but 'within' the code such that our actions themselves build and apply, where understanding of code can build on simple intuitions (e.g. locality of interaction). 

Obviously, the keyboard-video-mouse devices for human-computation interaction is more amenable to standing above and outside the code. But I believe the development of AR and VR devices will support a significant shift in our computing metaphors.

A consequence of my vision is that languages I'm developing don't have 'variables' at all, at least not fundamentally. I've selected a concatenative language for the foundation, rather than a lambda calculus. This makes it easier to model human actions as streams of code, rather than modeling human thinking with symbols. It also simplifies composition and dissection of objects constructed in the language. Purity is essential for my vision, as it allows understanding of objects by experimentation, simulation, and examples without side-effects becoming an issue. I've further developed alternative application models (I don't believe `int main(args)` plus side effects is a very good model).

To get back to your second question - "how does program rewriting help for programming by demonstration"? 

A lot of the environment setup hassle would be eliminated, and feedback from computation would be omnipresent. With program rewriting, code is an active substance that oozes together and interacts upon composition even very from a `main` function. Every part of the codebase a implicit testing grounds because there is no need to 'invoke' a test to begin evaluation. 

I didn't understand your point about DSLs, nor could I find your paper with a quick search.

On your last point - "focus on the user interface, so more people can program using your language" - I'm taking that from the other end. I have a vision for HCI that existing languages do not support, because it requires lowering the barriers to composing and sharing of computable things between normal users. So I'm making a language suitable. I believe Program Rewriting actually simplifies quite a few of the user experience issues I was encountering in a prior prototype.

Regards, 

Dave

[Raoul Duke]

Seriously exciting stuff.

[David Barbour]

John,

I am familiar with Conal Elliott's work on tangible values. I've not been able to take much from the technical side of his work (deep arrows), but the general vision of programs being something 'tangible' and was one of my early inspirations and is a good fit for a more physical computing metaphor like I described to John Carlson, above.

I don't mind extracting an application as a binary for performance, but I do not believe it should be the primary mode of computation. Fortunately, we can get a great deal of performance by a different approach - e.g. surgical precision JIT [1] together with 'staging' at the language layer - without sacrificing adaptability, expressiveness, or debuggability. 

I'm mostly unhappy with composition, abstraction, validation from the OOP camp, though I don't mind purely functional object models (it's the pervasive aliasing of state that I find problematic with OOP). That said, DSL interpreters can be understood many ways. E.g. as GADTs with monadic interpreters.

[1] http://tcloud.sjtu.edu.cn/wiki/images/9/96/Surgical-Precision-JIT-Compilers.pdf

[John Nilsson]

The thing with the tangible values I found inspiring wasn't so much the visual aspects of it but how how composed values "collapse" into simpler values, the partial evaluation bit of it. This is how I imagined you could add abstraction to spreadsheets, which also has expanded and collapsed views in the way formulas collapses into values when viewed as cells.

As for how abstractions as such would be expressed I think it was a bit inspired by Cat (a stack based, typed, concatenative language), and a thought that stacks could be replaced by first class environments and rewriting, so you could have a concatenative language with partial evaluation. Instead of the usual ordered parameter lists, and/or curried functions with partial application, functions take environments and produce environments. A program like "{a=1}{b=2}{c=a+b}" would evaluate to "{c=3}". While "{b=2}{c=a+b}" evaluates to "{c=a+2}" (composition is at least associative, perhaps even commutative).

The thing with producing binaries was primarily aimed at making compilation just the application of library function to enable greater flexibility, and primarily meta programming. I happen to believe that our current mixing of mechanics of the final runtime, and the various abstractions and meta-programming we apply to model the problem domain is the wrong approach. So by separating the meta-programming part from the mechanics part we get to model our domain freely, with no regard to mechanics, and then apply the necessary transformations to derive actual mechanics. Perhaps this is what MDE is all about.

Borrowing from OOP is not so much about OOP-being a great success. Rather it is, at this point, a mature and well explored design space. The insight that good OOP about modeling behavior, but usually really bad at modeling data, is whats leads me to think that you could perhaps get experienced OOP-developers to adopt an interpreter based language if it looks and feels a bit like programming OOP.

Thanks for the link btw.

Have you looked att the OBJ languages? ( http://cseweb.ucsd.edu/~goguen/sys/obj.html )

BR,

John

--
You received this message because you are subscribed to the Google Groups "Augmented Programming" group.

To unsubscribe from this group and stop receiving emails from it, send an email to augmented-programming+unsub...@googlegroups.com.

[John Carlson]

Your "streams of code" representing actions is a lot like programming by demonstration and the movie or film of actions idea in the TFP google video (in the Q&A).   It also follows along Bret Victor's work where he keeps track of actions taken in his drawing visualization.  This is the recorder I was speaking of.  I also have a picture of my recorder in my paper at http://www.google.com/url?sa=t&source=web&cd=3&ved=0ahUKEwjw7fTM--nOAhVDmh4KHaZ-CwcQFggrMAI&url=http%3A%2F%2Fdsmforum.org%2Fevents%2FDSVL01%2Fcarlson.pdf&usg=AFQjCNFJvcV-Slhnf1EJSFLXnjTpLEMruw&sig2=mpDlLuHBFfD6MahyFwTuxQ

What I would like to see in a further concept beyond mine is using selectors (class, id or attribute based) from the environment instead of branches or conditionals.  I believe this technique might avoid a large program with a lot of branches.

--
You received this message because you are subscribed to the Google Groups "Augmented Programming" group.

To unsubscribe from this group and stop receiving emails from it, send an email to augmented-programming+unsub...@googlegroups.com.

[David Barbour]

On Tue, Aug 30, 2016 at 2:25 PM, Dobes Vandermeer <dob...@gmail.com> wrote:

Have you seen PURE?

http://purelang.bitbucket.org/

I have heard of it, but I've never really looked. It does seem to have good rewriting semantics. Thanks.

 

[Jake Brownson]

I don't have much insight to lend here, but just wanted to say I'm finding this line of thinking pretty fascinating.

--

You received this message because you are subscribed to the Google Groups "Augmented Programming" group.

To unsubscribe from this group and stop receiving emails from it, send an email to augmented-progra...@googlegroups.com.
To post to this group, send email to augmented-...@googlegroups.com.

[David Barbour]

I do like the idea of having a predictably commutative subset within the concatenative language. 

Years past, I pursued a similar approach, albeit typefully. The environment would contain multiple stacks of values, by type. I could create new types by naming them (e.g. `A:Int → B:Int → C:Int` would pop a value each off the A:Int and B:Int stack, and push one onto the C:Int stack). However, I eventually decided the name-juggling and generalization of subprograms to work with multiple names (e.g. via `add<A,B,C>` templating), was verbose, complicating, annoying, and difficult to render/visualize.  So I went back to anonymous data on a stack. 

I am curious whether `{c=a+b}` will scale to more interesting programs, or encounter similar problems.

Regarding the 'mixing of mechanics and meta-programming', I believe that controlled separation is useful. Much like a free monads with effects interpreters is more expressive and accessible compared to embedding a specific implementation into a monadic type [1]. Use of GADTs and similar can be very convenient for domain modeling independently of the host language. If you want to take it really far, look into Adam Megacz's work on Generalized Arrows [2].

Regarding OBJ, my first experience with term rewrite systems was CafeOBJ and Maude for a university class, back circa 2004. It is unfortunate that Professor Goguen, whose site you linked, died in 2006.

Anyhow, generic support for term-rewrite models is not what I mean by 'program rewriting'. I'm referring to implementing a single, general purpose language (such as a lambda calculus or kell calculus or concatenative combinators) via rewriting, then modeling other things in that general purpose language just as we do today. 

[1] http://okmij.org/ftp/Computation/free-monad.html

[2] http://www.megacz.com/berkeley/garrows/