Major Revision ("call by name" expressions)

[Dan Cook]

The mixing of compiled and interpreted elements of OPIA has left MANY
ambiguities for me to sort out, and this has been a process for
months. I think I finally found a solution for most of these which
involves a revision of the kinds of interpreted variables there are
and how they are handled. You can skip the following explanation of
the OLD solution by looking for the section marked with "****", but I
give it to paint a better picture of what the issue is and why the
revision is better/neccessary:

The original idea was to have regular variables that store runtime
values (i.e. "byte num"), interpreted variables that store compile-
time values (i.e. "$int b"), alias variables that act as interpreted
aliases for other variables (i.e. "byte& num" or "$int& num"), and
const-alias variables that act as alias-variables, but can also alias
to any expression (i.e. "const byte& num") (the reason for allowing
const-alias-variables to alias to non-variable expressions is because
one cannot assign a new value to a const anyway; but this way there is
still the added efficiency of using an alias rather than a runtime
assignment). For example:

void foo(type num) { ... } // value of num is stored/accessed at
runtime (unknown at compile-time)
inline void foo($type num) { ... } // value of num is stored/accessed
at compile-time (num does not exist at runtime)
inline void foo(type& num) { ... } // num becomes a compile-time alias
to another variable passed to it
inline void foo(const type& num) { ... } // num becomes a compile-time
alias to any expression passed to it

The first issue comes from the fact that there are just too many types
of variables, and using the right kind in the right place is not as
obvious as it may seem (consider mixing intepreted and compiled
elements in the same function, and passing the function compiled and
interpreted variables and expressions in different places).

The biggest issue though is in how values would be passed to the const-
alias-variables. For example:

void foo(const byte& num) { ... a = num; ... b = num; }

If num was passed a variable, then there is no problem. However, is
num aliased to an expression that cannot evaluated at compile-time
(but at runtime), then it needs to be evaluated somewhere: either
immediately (and stored in a temporary variable), or where it is used
(this is more efficient, but may have side-effects if the caller does
not know when it will be evaluated). If it is evaluated immediately,
then the alias-concept becomes pointless. If it is evaluated later,
then should the entire expression be reused for both "a" and "b"? The
result is NOT the same for both options (consider if the expression
contained a function call -- how are we to know whether we want to
call the function each time, or just call it once to compute a one-
time value?). What if one method was favorable in one case, but the
another in another?

The final issue is that, in specifying that a variable is either
compile-time or interpreted, then one cannot use the same function for
both an interpreted computation and a compile-time computation -- that
might mean coding two versions of the same function; which means more
ambiguity!

A partial solution came to me when I read up on how to use data-flow
analysis with value-numbering and register-allocation techniques that
would optimize something like "inline void foo(byte a) { b = a }" to
associate "b" with "a" automatically, thus removing the concern about
redundant assignments. That gets rid of the need for const-alias-
variables to alias to non-variable expressions. However, there is
STILL a need to resolve the issue of when to evaluate expressions, and
making inline functions that can be used with different kinds of
values. This brings me to my new revision:

**** The major revision is NOT distinguish compile-time and runtime
values/expressions (noting that ALL expressions are evaluated as much
as possible at compile-time, such that "1+2+3*a" always becomes
"3+3*a"), and redefine interpreted variables as compile-time variables
that store entire expressions. The $-sign is disallowed as part an
identifier and becomes an operator to denote expression evaluation
(and thus the "interpreted datatypes" previously available are
replaced by compiled-datatypes preceded with a $-sign). I am still
debating on the syntax for most of this, but here is the gist of it
through some examples:

byte a; // the runtime variable a holds an unknown value
$byte n = 1+2+3*a; // the compile-time variable n now holds the
expression "3+3*a"
$byte p = 1+$n; // the compile-time variable p now holds the
expression "4+3*a"
$byte q = 1+n // the compile-time variable q now holds the expression
"1+n"

// THIS IS WHERE IT GETS INTERESTING:

n = a; // change the value of n to the expression "a"
$byte r = n // r now holds the expression "n"
byte b = p; // p is completely evaluated for runtime storage in b as
"4+3*a"
byte c = q; // q is completely evaluated for runtime storage in c as
"1+a"
$n = c; // evaluates to "a = c", which in turn evaluates to "a = 1+a"
$r = p; // evaluates to "n = p"
$$r = 5; // evaluates to "p = 5"
c = $q; // same as "c = q", because c is a runtime variable

The remaining loose ends and ambiguities that I know of are tied up
with these rules:
1: Expressions are only evaluated when marked with a $-sign, or when
needed for runtime storage
2: A $-sign on an expression that is already fully evaluated (i.e. $1)
yields the same expression.
3: Expressions stored in variables are operated on as a single unit
(i.e. $q*2 yields (1+n)*2 instead of 1+n*2)

========================

I am sure there may be some other ambiguities, so please let me know
if you come up with any, and what you propose (if you have a solution)

[Dan Cook]

This use of expression variables simulates functional programming,
pointers, call-by-name, and call-by-need all in one! (for compile-time
computations).

[Dan Cook]

Here is a more suitable proposition in which the $-sign means "the
expression of" instead of "evaluate". My only complaint with this
version is that it makes passing values as expressions have to be
explicitly declared as foo($(expression)), and I think that's ugly.

byte a; // the runtime variable a holds an unknown value

$byte n = $(2+3*a); // the compile-time variable n now holds the
expression "2+3*a"
$byte p = $(1+n); // the compile-time variable p now holds the
expression "1+n"

$byte q = 1+n; // the compile-time variable q now holds the

expression "1+2+3*a"

// THIS IS WHERE IT GETS INTERESTING:

n = $(a); // change the value of n to the expression "a"
$byte r = $(n); // r now holds the expression "n"

byte b = p; // p is completely evaluated for runtime storage in b

as "1+a"

byte c = q; // q is completely evaluated for runtime storage in c

as "1+2+3*a"
`n = c; // evaluates to "a = c", which in turn evaluates to "a
= 1+2+3*a"
`r = $(q); // evaluates to "n = $(q)"
``r = 5; // evaluates to "q = 5"
c = $(q); // illegal!

The remaining loose ends and ambiguities that I know of are tied up
with these rules:

1: Expressions are always evaluated, except when marked with a $-sign
2: Expressions stored in variables are operated on as a single unit
(i.e. `p*2 yields (1+n)*2 instead of 1+n*2)

=====================

If anybody has an better solutions (a modification of both or one of
these strategies), that would be great. What's your opinion?

[Dan Cook]

please note that in the previous posts, many // comments
were wrapped onto multiple lines because google groups
seems to do that automatically for some reason.

The statments starting with "expression" are NOT
statements, but part of comments that wrapped around!