Tuesday, July 27, 2010

A reduced programming language

Not to bang on about the '=' operator, but this alternate definition described in previous posts seems like an interesting way to produce a reduced programming language... I'm not sure how useful it would be but it is a kind of interesting thought experiment.

If you have the equation 4 = x*x then its value is 4, but its value can only exist in a universe where x is 2 or x is -2. If we previously had the expression x = all reals; (by this I mean it is the contents of the set of reals, it isn't a set itself), then the later expression 4=x*x can only exist in the subuniverse of the first expression where x = 2,-2. It is not that the first expression x = all reals is now wrong exactly, but that for most elements e.g. x = 0, their existance has become infinitely unlikely.

Anyway what does it all mean, well it means that with a programming language that follows this '=' operator design we could write:
x = reals;
x = 3; <-- this expression evaluates to 3, and can only exist as a statement if x then becomes 3
but unlike most languages you could equally write
3 = x; <-- x becomes 3
and as eluded to in previous posts, you can use = in equations like so:
y = 2 * (x = 3); <-- x becomes 3, y becomes 6

'=' becomes like a filter on the previous expressions, for example:
x = reals;
x^2 = 4 <-- x becomes 2, -2
but if we write
x = reals;
x = -2;
x^2 = 4 <-- x will be -2, since it is a subnumber of values of its previous self

What if you write:
x = reals;
x = 4; <-- x becomes 4
x = 5;
In this case there is no subuniverse that can exist where 4=5, so the value of x=5 is void and x becomes void.

You can of course write very complicated equations and get answers, e.g.
(x^2.3 + x^-1.7)^(x+1) = 13;
The design will filter x appropriatly. However it is very hard for a programming language to solve arbitrary equations like this in general. Such a programming language would probably reference a large database of formula patterns on the net to provide a solution. This has the advantage that the user doesn't need to manually write its own solvers separately for every equation they have, and these complicated solvers can use stable, well trodden algorithms.
But also users should have syntax so they can write your own solver, for example:
(x^2 = 2*x)
<
// optional user defined solve function, can call a common routine:
solveQuadratic(...);
>

What if we want to perform some arithmetic on a 'number of' values? We can use the syntax:
(number of values)
{
}
which the block will be executed for each individual value, e.g:
(1, 2, 4)
{
print("value = ", value);
}
In fact, we can use 3 different notations for 3 different effects:
- a 'number of' something has no particular order, but can have more than 1 of the same value. 1,2,2,3 == 3,2,1,2. It optionally uses () to resolve ambiguity, so matches the use of () in functions and matches that (1,2),3 == 1,2,3 == 1,(2,3)
- a list of something has a specific order and can repeat values. It can use [] like arrays.
- a set of something has no specific order and number of repeated values is ignored. 1,2,2,3 == 3,2,1. It can use {}.

The result is that a list is executed in order, but a 'number of' and a set can be executed on separate threads.
(1,2,3)
{
// executed on separate threads
}
{1,2,2,3}
{
// executed on separate threads, only 3 executions
}


OK, so far so good. The thing I find interesting about such a language, is it has surprisingly few keywords...
- we can do an if statement like so:
(x=3)
{
print("x is ", x);
}
- we can do a while statement like so:
x = integers;
x >= 0;
[x < maxCount ]
{
...
}
- and hopefully you can see that a for statement and a do{}while can be written similarly.
- There is no ==, you just use the one = operator.
- Threading is done through the use of sets/'number of's rather than the serial lists.
- 'and' also can be used, you can write (x^2=4 and x<0) this evaluates to 'true' and x will be -2.

I'm not sure how it is supposed to cope with infinite expressions though:
x = reals
x >= 0;
(x<1)
{
y = y^0.9;
}
Perhaps an internal search algorithm can pick values and try to converge towards a solution... not very easy though... but an interesting and in some ways powerful language none-the-less.

Wednesday, July 21, 2010

What = really means, and a variation of sets

I have often wondered how = fits in as an operator in a strict mathematical setting. It doesn't seem right that is is simple a boolean function, why should the value trueness or falsehood matter to equations.
In a previous post http://tglad.blogspot.com/2010/07/that-crazy-formula.html, I followed a train of thought that lead to equality being seen as the 0th operator of modified hyper-operators (where 1st operator is +, 2nd is *, 3rd is power etc), I called this slight modification ultra-operators.
With this definition, equals only returns a value when the two values are equal, a bit like this in pseudo C++:
operator =(a, b)
{
if (a==b)
return a; // or b
}

This leads to a problem of definition, what is the value of 1=0? no value is returned, but we cannot therefore say the value is the empty set.. because who says it should be returning a set. If it returns the empty set, then we could equally say that 1=1 returns the set {1}. However, it is wrong to think of 1 and {1} as being the same thing, since by induction it should be the same as {{1}}, and {} would be the same as {{}} and none of these are true of sets.

The more correct answer has to be that = returns a number of results, that number may be 0, e.g. 1=0 returns 0 results, or it may be 1, e.g. 3=3 returns 1 result. Or it may return 2 results e.g. x^2=2+x.

But no-one has put these numbers into a set. In fact it is probably useful to give a name to this concept, so instead of a set of values, we have a 'number' of values. So whereas a set of the first 3 integers is {1,2,3}, a number of integers is 1,2,3. And the equivalent to the empty set is just 'empty' or void.
So void does not contain itself, and a single value like 3 is also the same as a 'number' of values 3 (the number happens to be 1). Also the number of values containing 1,2 and the third element being the number of values 3,4 is the same as the number of values 1,2,3,4. i.e. there is no containment going on.

So what to make of a common formula such as

x^2 = 2+x where x is a member of integers <-- which is a set

The problem with this common definition of the formula is that it doesn't say which member, it just says 'a' member.
The set version would be
{ for all x member of integers: x^2 = 2+x }
but this is more long winded, and gives a set of answers, which isn't part of the scope of basic arithmetic and doesn't match the value of other operators which just give values.

Instead, what the above (normal) formula is actually shorthand for is:
the 'number' of values
x^2 = 2+x for each x in the set of integers
which is short hand for:
0^2 = 2+0, 1^2 = 2+1, 2^2 = 2+2, 3^2 = 2+3, ....
a 'set' of values without the brackets, i.e. a 'number' of values.
since there are only two above that actually evaluate to anything, this can be shortened to:
-1^2 = 2+-1, 2^2 = 2+2
which evaluates to:
1, 4
i.e. the formula itself has a value.
Therefore you can do arithmetic on it:
3*(x^2 = 2+x)
which gives 3, 12.

Equality operator isn't a boolean function, it is simply a way of writing a value (or a number of values), writing 1, 4 is exactly the same as writing x^2=2+x, just as 2/4 is the same as 1/2.
So writing an equation with no answers is the same as writing nothing... writing 1,2,1=0,4 is the same as the numbers 1,2,4.

Interestingly some programming languages have picked up on this before mathematics has I think. Several languages will simply ignore expressions that don't add up, and the language C already give '=' a value, for example:
a = b = c; works because b=c has the value b (though admittedly this is also assigning c to b).

So in summary, if we all add 'number of' to the already existing 'set of' and 'list of' then we get a formal way to deal with multiple results. And since 'number of' has no container, the equivalent of the empty set {} or the empty list () is just 'empty' or void.

The same sort of thing should also work for inequalities, e.g. x<10 x member of reals is a 'number of' values, where the number happens to be infinite. Thus it has a (or many) value(s) and can be used in equations, e.g. 3 * (x<10) = x<30.

This will probably feed in to the soft numbers post coming in a few weeks.

That crazy formula

I rarely consider mathematical formulas on their own to be beautiful things, but there is something quite special about one formula in particular, here it is:
e^i*pi + 1 = 0
The formula is saying 'if you rotate 1 by 180 degrees then you get -1'.
It is a very satisfying formula, it contains a plus, a multiply and a power, and it contains possibly the four most useful numbers in mathematics, 0, 1, pi and e.

Another reason why it is a special formula came to me yesterday when I was investigating how the units of measurements combine in formulas.
If we square a velocity (in metres per second) we get a value in square metres per second squared. So if you write the units as a vector [metres, seconds] then a velocity is [1, -1] and a velocity squared has units [1, -1]^2 = [2, -2].
What if you multiply two measurements together? What units do you get if you multiply a velocity by an acceleration? You get [1, -1]*[1, -2] = [2, -3].
Can you see the pattern? Well here it is... if you take a measurement to the power x then you multiply the units by x. If you multiply two measurements then you add the units together. It seems that the units operate one 'level' down from the operation on the measurements themselves.
To clarify this idea of a 'level' we need to look at hyper operators. Here they are:
a (1) b means a + b
a (2) b means a * b
a (3) b means a ^ b
So what seems to be the case is that the units of measurements A (n) B are a (n-1) b (where lower case means units of).

So what happens if you add two measurements together? what happens to the units? Well what are the units of a velocity plus a time? or a position plus a velocity? A tough question... you could say that the resulting measurement is unitless, but that is actually wrong, a gradient (e.g. height/width) is unitless. The sum of two measurements seems to be 'less than' unitless, unlike a unitless measurement which has a vector [0,0,..,0], the sum isn't even that, it isn't even the empty set because it isn't a set, it is just empty, void.
However, you can still sum measurements if they have the same units... an acceleration plus an acceleration still has units [1, -2].

This is interesting because it means that we have defined a (0) operator, not only that but it is different from the normal 0 hyper operator (which is succession), we have:
a (0) b = void if a different to b
a (0) b = a if a same as b (or it can equal b, same thing)
I like this new version of the 0 hyper operator (maybe we should call them ultra operators from now on), because a (0) b is a binary operator and is symmetrical.
The best part about this operator is that it has an obvious meaning that we use in every equation ever written, it is the equals operator! It is actually an important change to how '=' is interpreted. Rather than thinking of a=b being a boolean expression, it is numerical expression that either returns the equal value, or simply doesn't return. A bit like this:
operator = (a, b)
{
if (a==b)
return a;
}

Anyway, where was I? Oh yes, this brings me around to the other reason why the formula at the top of the page is special. If we write it using ultra operators it looks like this:
e (3) i (2) pi (1) 1 (0) 0

It is quite a simple formula wouldn't you agree?

It makes me wonder whether there is some more that can be learnt from it.