Hi all,
I think it would be a bit presumptuous to call this "FIG's equations of
software", but I stumbled across an interesting phenomenon while
developing my Ocean compiler system: the idea of derivatives and
integrals of software programs.
For examples of the concepts, I'll be presenting them in a simple
object-capability language, called Sandstone. Here is a sample source
file:
----------------------------------------------------------------------
.new(Out, Name): {
Hello = load('hello.ss').new('World');
return {
.greeting(Greeting: string): {
Out.format('~s, ~s and ~s!~n', [Greeting, Name, Hello.msg]);
};
.count(Name: atom): {
return 123;
}
}
};
.main(): {
Hello = .new(stdout, 'Michael');
Hello.greeting('Hello');
}
----------------------------------------------------------------------
And a grammar fragment (I have not implemented this, so it may contain
bugs, but I'm sure that somebody better with OMeta would be able to hack
it up quite quickly):
Main = Decl (_ ';' _ Decl)* _ ';'? _ !.
Decl = Ident Prototype? ':' _ Expr
Ident = '.' [_A-Za-z] [_A-Za-z]*
Prototype = '(' _ Formal (_ ',' _ Formal)* _ ')'
Formal = Var | Var ':' _ Atom
Var = [A-Z_] [A-Za-z_0-9]*
Expr = Call | Block | List | Tuple | Number | String ...
Block = '{' _ Statement (_ ';' _ Statement)* _ ';'? _ '}'
Statement = Decl | Call (_ Call)*
Call = Symbol Tuple? (Ident Tuple)*
Symbol = [^(). \t\r\nA-Z] [^(). \t\r\n]+
List = '[' _ Expr (_ ',' _ Expr)* _ ']'
Tuple = '(' Expr (_ ',' _ Expr)* _ ')'
The semantics may seem obvious from the example, but they are actually
designed to be radically variable. The syntax is intended to be a
human-friendly ocap assembly language of sorts. Just picture this
syntax with the "kernel" idea described in Ian's paper on the VPRI site
(which I had a little hand in implementing)... the semantics are
determined by the specific kernel (which may be dynamically extended or
swapped) much more than the "actual" code.
Definitions
***********
I would like to provide a more mathematical explanation of the following
concepts, but I'm afraid my limited (and ancient) calculus knowledge is
not up to the challenge. I rely on hand-waviness and hopefully you all
will still get my drift.
A method has an easily computable derivative with respect to a
parameter... it is done by dropping the parameter from the argument
list, and transforming all of its method calls into implicit kernel
calls:
d.new(Out, Name)
----------------
dOut
= .new(Name): {
Hello = load('hello.ss').new('World');
return {
.greeting(Greeting: string): {
format('~s, ~s and ~s!~n', [Greeting, Name, Hello.msg]);
};
.count(Name: atom): {
return 123;
}
}
};
The integral is a little more interesting. We perform an integral with
respect to a method and a set of implicit kernel calls. The process
introduces a fresh name as the first parameter, and makes all the
implicit calls in the set into method calls on the first param.
integral(.new(), {format, return})
= .new(K, Name): {
Hello = load('hello.ss').new('World');
K.return({
.greeting(Greeting: string): {
K.format('~s, ~s and ~s!~n', [Greeting, Name, Hello.msg]);
};
.count(Name: atom): {
K.return(123);
}
})
};
Unlike derivation, integration requires an oracle who understands the
semantics of the function.
This gets interesting when we integrate over .new(Name)'s implicit eval()
function (provided the oracle handles it):
integral(.new(Name), {format, eval})
= .new(K, Name): {
return K.eval({'Name': Name, 'K': K},
[
['Hello', '=', ['.new', ['load', (utf8, 'hello.ss')],
'World']],
['return',
(block, [('.greeting', [('Greeting', 'string')],
[['.format', K, (utf8, '~s, ~s and ~s!~n'),
(list, ['Greeting', 'Name',
(slot, 'Hello', 'msg')])]]),
('.count', [('Name', 'atom')], [['return', 123]])])
]
])
};
Laws
****
1. Abstraction:
.method2(K, ...) = integral(.method(...), {prim1, ..., primN})
.method2 has had its implicit primitives {prim1, ..., primN} reified as
explicit calls to K.
2. Evaluation/interpretation.
.meta(K, typeof(A1), ..., typeof(An)) === integral(.method(A1, ..., An),
{eval})
.meta(I, ...) = value of .method interpreted using kernel I
3. Optimization/compilation:
.method3(...) = d.method(X, ...)
---------------
dX
.method3 no longer varies with X, but instead relies on its evaluator to
provide the services previously attributed to X.
4. Entropy.
d integral(.method, prims)
----------------------------- = .method
d(first argument of integral)
but
integral(d.method(A, ...), prims)
---------------
dA
is not necessarily equivalent to .method since collapsing A's calls into
the environment may result in information loss, and the correct prims
set must be identified by an oracle as well.
Comments?
*********
I want to develop these ideas further, but I imagine it'll be quite some
time before I have something worthy of a paper or even a memo, so I
want to solicit public discussion even though they're in their infancy.
--
Michael FIG <mich...@fig.org> //\
http://michael.fig.org/ \//
_______________________________________________
fonc mailing list
fonc@vpri.org
http://vpri.org/mailman/listinfo/fonc
