Lambda the Ultimate

Greetings,

Ehrhard and Regnier described a functional programming language -- the differential lambda calculus -- which added to the lambda calculus a commutative monoid structure and a differential operation. One feature of this calculus is that application is linear in the first argument.

I am studying a weaker system that adds only the commutative monoid structure, and I insist that application preserves addition in the first argument (which is implied in E.R.'s system). This means:
(g+h)*m = g*m + h*m
0*m = 0
(where * is application)

The above has the feel of non-determinism to it. Given 'g' or 'h' applied to 'm' the result is 'g' applied to 'm' or 'h' applied to 'm.'

However, in general:
g*(m+n) =/= g*m + g*n

So it is not as if 'g' makes a non-deterministic choice of 'm' or 'n.' While some have called this non-determinism, others have called parallelism.

Any thoughts on what the correct word describing such an application might be?

The recent mention of the Nile programming language reminded me to post about the STEPS 2011 Progress Report.

The overall goal of STEPS is to make a working model of as much personal computing phenomena and user experience as possible in a very small number of lines of code (and using only our code). Our total lines of code‑count target for the entire system “from end‑user down to the metal” is 20,000, which—if we can do a lot within this limit—we think will be a very useful model and substantiate one part of our thesis: that systems which use millions to hundreds of millions of lines of code to do comparable things are much larger than they need to be.

...

Our general approach is to pick an area whose parts seem to be related—for example: 2.5D anti‑aliased alphaed computer graphics—try to find the mathematical relations that cover the desired phenomena, design a “problem oriented language” (POL) that is a “runnable math” version of the mathematics, implement that language, then use it to write the program code for the target area.

...

STEPS is now to the point where it is more fun to use and demonstrate than to talk and write about. Quite a bit of the original proposal is now working well enough to give all our presentations and write this entire report for the NSF and Viewpoints Research Institute websites. In the STEPS system, this document is live: the examples are actually runnable demos; the code shown is changeable and testable, etc.

A large part of the work over the last year has gone into making the test versions more real and usable.

Previous discussion of this project on LtU includes:

• Steps Toward The Reinvention of Programming The NSF grant proposal (2006)
• STEPS Toward The Reinvention of Programming: First Year Progress Report
• Programming and Scaling, a lecture by Alan Kay