# Rebol Programming/Advanced/Identity

Author: Ladislav Mecir
Rebol is an expression-oriented language. A successful evaluation of an expression yields a value. After successfully performing two expression evaluations we can legitimately ask whether we obtained two values or just one that is actually a result of both evaluations.
In the past, the question became a subject to dispute. The answers in the mailing list ranged from:
    "Only the Rebol designer can answer such a question." (S opinion)
to:
    "Two expression evaluations never yield one Rebol value. If the evaluations are discernible then their results can be discerned too." (N opinion)
The "S opinion" can be called "skeptic" since it expresses skepticism about our ability to find the correct answer to the question. In response to the "S opinion" we summarize the properties of Rebol identity and show that we are able to find out whether two successful expression evaluations yield one Rebol value. We do it by defining an identical? function "mechanically" doing just that.
Examining the "N opinion" one is tempted to call it "nihilistic" since it suggests that "two expression evaluations never yield one Rebol value". The acceptance of this idea has even more thorough consequences than the acceptance of the "S opinion", which at least allows us to ask Rebol designer when in doubt. As opposed to that, the "N opinion" might discourage us from reasoning about identity of Rebol values and from using it for practical purposes. Our definition of the identical? function looks sufficient to refute this opinion too, showing that Rebol identity exists and is practically usable.
During our quest for the Rebol identity we discuss other (once disputable) matters like "Is a given value mutable?" or "Which attributes a given value has?" and implement a couple of (hopefully interesting) functions.

## Acknowledgments

I would like to say thanks to Joel Neely, Romano Paolo Tenca and many others who discussed the subject with me on the Rebol mailing list.

## Notes

This version of the article was tested in Rebol/View 2.7.6.3.1. Other versions of the interpreter may differ in a few details.
A reader, wanting to check all the examples can run this code:
, which defines the functions from this article.

## Relations

The goal of our quest, the identical? function has to accept any result or results of two expression evaluations and yield a logic! type value.
Let's call a function having these properties a relation.

## Reflexivity

As is well known, we can refer to Rebol values using Rebol blocks or words. Example:
The effect is that the a-char variable refers to the character as we expected:
Let's now evaluate this expression:
The effect is that now even the first entry of the above block refers to the character.
For the referring operation to behave consistently we expect that for any non-empty block the expression
shall yield true and the same consistency requirement leads us to expect that for any variable var the expression:
shall yield true too. This property we call reflexivity.

## Symmetry

Let's have a block block having two entries such that the expression
yields true. Knowing that we can conclude that the two entries of the block refer to one value. If that is true then
shall yield true too. Using the same reasoning we expect that for every two variables var1 and var2 if
yields true then the expression
shall yield true too.
This property we call symmetry.

## Transitivity

Analogically as above we can come to the conclusion that the identical? function shall have the following property:
If block is a block having three entries and both
and
yield true then
shall yield true too.
If var1, var2 and var3 are variables and both
and
yield true then
shall yield true too.
This property we call transitivity.

## Equivalence

Definition (Equivalence): We call any Rebol function having the above described properties (i.e. a relation that is reflexive, symmetric and transitive) an equivalence.
In accordance with our previous observations we restate that Rebol identity has to be an equivalence.
Let's use the definition to find out whether some functions are equivalences. For example, the never function implementing the "N opinion" from the summary
is a relation that is both symmetric and transitive. However, it isn't reflexive and therefore it isn't an equivalence.
On the other hand, the always function
is an equivalence, although a trivial one.
Observation: The same? function isn't an equivalence.
Proof:
* The same? function is undefined for unset! and error! type values and therefore it isn't a relation.
* The same? function is undefined for closed ports and therefore it isn't a relation.
* The same? function is undefined for money! values with different denominations and therefore it isn't a relation.
* The same? function does not return a logic! type value when obtaining struct! type values as arguments and therefore it isn't a relation.
* The same? function isn't transitive when comparing decimal! values.
* The same? function isn't transitive when comparing date! values.
Any of the above points suffices to demonstrate our observation q.e.d.
Observation: No equivalence comes built into the interpreter.
Actually, no relation comes built into the interpreter. This can be verified by examining every built-in function like we did in the case of the same? function.
Terminology: Let's have an equivalence eq and a block block having two entries. If the expression
yields true, we say
    "For the eq equivalence the value referenced by the first entry of the block block is equivalent to the value referenced by the second entry of the block block."
, or
    "For the eq equivalence the value referenced by the first entry of the block block is indiscernible from the value referenced by the second entry of the block block."
If the above expression yields false, we say
    "For the eq equivalence the value referenced by the first entry of the block block is not equivalent to the value referenced by the second entry of the block block."
, or
    "For the eq equivalence the value referenced by the first entry of the block block is discernible from the value referenced by the second entry of the block block."

## Fineness

To be able to compare equivalences we use
Definition (Fineness): We say that equivalence eq1 is finer or as fine as eq2 (resp. eq2 is coarser or as coarse as eq1) if for any block block having two entries for which
yields true,
yields true too.
Definition (Equal fineness): We say that equivalence eq1 is as fine as eq2 if for any block block having two entries holds that:
yields true if and only if
yields true.
Observation: The above defined always function is the coarsest equivalence.

## Definition of Rebol identity

The notion of equivalence doesn't define identity completely since, e.g. the always function is an equivalence, but it isn't the identity we are looking for.
To define the identity we employ a fundamental logic principle known as
Observation (Indiscernibility of identicals): No value can be discerned from itself.
As a corollary to this principle we obtain
Observation (Leibniz's law): The identical? function has to be the finest equivalence in Rebol.
Proof: We demonstrated that identical? has to be an equivalence. Let's have an equivalence eq and a block block having two entries for which the expression
yields true. If the identical? function is the Rebol identity, we know that the first and second entries of the block refer to one Rebol value. According to the principle of indiscernibility of identicals the eq equivalence cannot discern first block from second block, which proves that identical? is finer or as fine as eq q.e.d.
We use Leibniz's law to define
Definition (Identity): We call an equivalence identity if it is the finest equivalence in Rebol.
Observation: Any two identities must be of equal fineness.
Proof: If we had two identities with different finenesses, one of them wouldn't be the finest q.e.d.
Observation: The above defined identity (if it exists) satisfies the principle of indiscernibility of identicals.
The proof is left as an exercise to the reader.
While we succeeded to uniquely define the identity, we are only half-way done since we didn't yet succeed to implement it.
To be able to implement the identity we need to collect more informations about Rebol values.

## The type attribute

Let's note that every Rebol value has a type. A type-comparing equivalence can be defined as follows:
Observation: The equal-type? function discerns values with different datatypes.
Observation: The same? function does not always discern values that have different datatypes.
Proof: If we define
then
yields true, while
yields false.
If we define
then
yields true, while
yields false q.e.d.

## The new-line attribute

Observation (the new-line attribute): Every Rebol value has a new-line attribute.
Proof: In the case of the type attribute we didn't need to prove that every Rebol value has a type since it is widely documented, there are many examples of values with various types and there is a type? native that returns a type of any given value.
To prove the existence of the new-line attribute we need to document it, provide examples of values with distinct new-line attribute values and define a new-line-attribute? function returning a new-line attribute of any given value.
We start with the documentation. The new-line attribute is a value that can be either true or false. It marks the positions of line breaks in a block. If a block entry refers to a value having the new-line attribute set to true, the mold function will insert a line break when molding the block.
The new-line-attribute? function examining the new-line attribute of any value can be defined as
It isn't hard to observe that the new-line-attribute? function returns just true or false for any given value.
Another function called new-line-attribute can return values with the new-line attribute set as required
Now we can define
, i.e. we successfully demonstrated that there are values with the new-line attribute set to false as well as values with the attribute set to true.
Now we demonstrate that molding a block having an entry referring to the one-nl value creates a string containing line-break
This completes the proof of our new-line attribute observation q.e.d.
The knowledge of the new-line attribute and our above defined new-line-attribute? function can help us to define a function comparing the new-line attribute
It is easy to observe that the equal-new-line? is an equivalence discerning values with distinct new-line attributes. Illustration:
On the other hand, it is equally easy to observe that the same? function does not discern values with distinct new-line attributes:

## Functions that do not modify their arguments

In Rebol, some functions modify their arguments (it is usually stated in their documentation). It is not easy to write a simple definition of what the phrase "a function modifying its argument(s)" means, so, let's start with simple examples
When observing the behaviour like
, a reader unfamiliar with the meaning of the "function modifying its argument" phrase may be tempted to say that "f1 modified the argument value 1 to return the value 2". This is not the case since the modification we are trying to describe here has to be of a different nature.
To help us with the demonstration, let's use the apply function applying a given function to arguments submitted in a block (the function is defined in the %identity.r file).
In the case of the above f1 function we can use apply to obtain
Note: we use the /only refinement of the apply function to make sure the function obtains the arguments contained in the block "as is".
If we examine the block of arguments after the call, we see that it looks unchanged, which suggests that the argument value hasn't been modified by f1
Let's see another example
Now again, one may be tempted to say that f2 changed the argument value, but when verified
one observes that the block containing the argument value remains unchanged.
Another function, for which a reader may not immediately know whether the function modifies its argument is the new-line-attribute function defined above. Let's check
This shows that while the function yields a value with the new-line attribute set to true, the original argument value remains unchanged having the new-line attribute set to false.

## Functions modifying their arguments

We use the set function as our first example of a function modifying its first (the word) argument.
This example shows that the first argument (the variable a) originally referred to one block, while after being set it now refers to another block.
Our next example will examine the behaviour of the change function.
In this case we see, that the change function changed its first argument too.
Note: functions may modify other values than their arguments too - e.g. it isn't hard to define a parameter-less function modifying something.

## Expressions modifying their values

In the case of functions we illustrated the meaning of the phrase "a function modifying its argument". A question may arise, whether an expression modifies the value(s) in it or not.
We can convert the situation to the function case by defining an appropriate function and examining the behaviour of the function instead.
Example: let's find out whether an expression like
modifies the values in it or not. To find out, let's define a function as follows:
and supply the appropriate values as arguments
In this case our finding is that the expression actually doesn't modify the values in it.
Here is a case of an expression modifying the value in it
, as we will find out examining
Contrast the above with a seemingly similar case
, which shows that in this case the first argument remains unmodified.
Pardon? The last example is the case of a situation, where a reader probably springs to attention. It is evident that even the last expression changed something! The only problem is that we didn't correctly guess what it was! So, let's try again, this time guessing that the expression modifies the variable
, and indeed, our second guess is proven correct.

## Mutable and immutable values

Definition (Mutable values): Values that can be modified we call mutable values.
Definition (Immutable values): Values that cannot be modified we call immutable values.
Observation: Rebol variables are mutable (see the set and tuple examples).
Observation: Rebol blocks are mutable (see the change example).

## Mutations used to discern values

While our excursion to the realms of modifying functions looked like a detour on our quest, now we show that mutations can be used to discern values. In the following example we define two bitsets
, so, according to the same? function bs1 and bs2 are indiscernible. Let's define a special equivalence called equal-mutation? as follows
This equivalence can discern the above bs1 and bs2 bitsets

## Implementation of the identity

We have collected all the necessary informations. The same? function is close to our goal, so we will try to use it as much as possible and take care of the cases when it fails to do what we want.
Observation: The finest equivalence in Rebol is

## Indices of series

The index? function gives us useful information about series. Unfortunately, it doesn't work as expected sometimes:
The example demonstrates that the index of the block b although printed as 1 once, was actually 2 all the time!
We can define a function able to yield a "more stable" value:
Test:

## Rebol identity is independent

While we used the same? function above to obtain an "efficient" implementation of identical?, identical? actually doesn't depend on the same? function.
Proof: We can write another (even though a less efficient) implementation of identical? not using same? or =? at all:
Discussion: To some readers this finding may look only like a coincidence. To explain why it is not a coincidence, consider that the user might restrict the language unsetting the same? function. We demonstrated that the restricted language would still have its identity, and that the identity would be "fully featured" in the sense that it would reflect all attributes of Rebol values accessible to the user. If the addition of the same? function added any additional attribute, such an attribute would not be really useful, being accessible solely to the same? function.

## Applications

Having implemented Rebol identity, let's try to define other interesting notions and functions.

## Relatives

Example (Errors and objects):
In this example the change affected the object referenced by the word h and the error referenced by f and g, while it didn't affect the error value referenced by i. We can say that the values referenced by g and h, while not being the same, are relatives in a sense.
A similar property is observable for words too:
Let's define an equivalence coarser than identical? corresponding to the property we have seen in the previous examples. The relatives? equivalence yields true if every change of its first argument is a change of its second argument and vice versa, every change of its second argument is a change of its first argument.
Usage:

## Identity of references

In the example showing that the set function modifies its first argument we caused the variable a' to refer to another block. A different formulation may look as follows: "We changed the variable a's reference."

### Variables and references

Let's see another example of the behaviour:
Similarly as before we can say that we didn't change the block, but in this case it looks that we changed the a's as well as the ax's reference. Indeed, a and ax are aliases and use a common reference, which means that a's reference and ax's reference are just different names for one reference.
In other words, we can speak about the identity of references too. The same-variable? function from [Contexts] checks identity of references of its argument words.

### Series and references

Yet another example of the behaviour:
Our question: "Did we change the block referred to by second c?" The answer is no, similarly as above, because the block referred to by second c was referred to by first c too and we see no change of first c. The conclusion: "We changed the second c reference only." Moreover, we see that both second c and first d are only different names of one reference.
Here is a function checking the identity of two series references. The function uses the PICK function's indexing convention, although a less complicated indexing would lead to simpler implementation:
Let's check our previous finding:
Unfortunately, this isn't the whole truth. Although our implementation and findings are correct, some access methods don't work for series in some state. That is why we obtain:
, which looks as if the references weren't the same, although the difference is caused by pick, which didn't use the reference after examining d.
An attentive reader may notice that we left out the identity of bitset references, but that case is rather simple, so it can be left as an exercise for the reader.

## Finding a reference to a value

It might be useful to have a function able to find a reference to a given value:
Another function of this kind may be a function searching for a relative of a given value:

## Finding values with a given property

Application of the find-reference function, a function able to recursively find out whether a block or its subblocks contain a value with a given property. The function works even for cyclic blocks:

## Comparing state

Two values may be in equal state even if they aren't identical. Let's define another equivalence able to find out whether two Rebol values are in equal state. Because the defined function will be an equivalence, it will not have the main disadvantages of the equal?, strict-equal?, etc. functions.
There is a problem with complicated values. Two functions shouldn't be found equal if they can yield different results. It is impossible to define a general comparing algorithm that would be able to find out whether two complicated functions are equal if they aren't the same. That is why I use a trivial approach (find out whether the values are identical) for functions. This approach is used for ports too.
The below defined equal-state? function will test every possible attribute of values that is available without their mutation. For some applications coarser equivalences may be more suitable.
An auxiliary function:
Observation (Another informal description of identical?): Two Rebol expression evaluations yield one value, if the state of the result of the first expression evaluation is equal to the state of the result of the second expression evaluation and every mutation of the result of the first expression evaluation is a mutation of the result of the second expression evaluation.
Corollary: Two expression evaluations in Rebol yield one value if the result is immutable and the state of the result of the first expression evaluation is equal to the state of the result of the second expression evaluation.

## Finding out whether a given block is cyclic

We can use a lot of different definitions of block cyclicity. The first one is probably the most strict:
Here is another one that yields results more closely related to results of native functions:

## Attributes of Rebol values

Attributes of Rebol values are the values that are associated with them. The state of a Rebol value is a "composition" of its attributes. As discussed above, every Rebol value has these general attributes:
* type attribute,
* and new-line attribute
For the values of none! and unset! types, the above are their only attributes, i.e., the values of the none! and unset! types do not have any type-specific attribute.
When a Rebol value is changed, at least one of its attributes changes. Let's call an attribute of a Rebol value that can be changed a volatile attribute, and an attribute that cannot be changed a regular attribute.
Observation (Attributes and mutability): A value is mutable if it has at least one volatile attribute.
Observation: Both the type and the new-line are regular attributes.
Other types have additional type-specific attributes listed below.

## Chars

Type-specific attributes:
character code
Chars are immutable.

## Logic values

Type-specific attributes:
truth/falsity
Logic values are immutable.

## Datatypes

Type-specific attributes:
datatype code
Datatypes are immutable.

## Integers

Type-specific attributes:
number code (32-bit signed, two's complement, one's complement, or signed with magnitude)
Integers are immutable.

## Decimals

Type-specific attributes:
number code (64-bit IEEE 754 binary floating point)
Decimals are immutable.

## Money

Type-specific attributes:
currency code (three letters), number code (64-bit IEEE 754 binary floating point)
Money are immutable.

## Pairs

Type-specific attributes:
x-coordinate (first coordinate, 32-bit signed integer), y-coordinate (second coordinate, 32-bit signed integer)
Pairs are immutable.

## Dates

Type-specific attributes:
year, month, day, time, zone
Dates are immutable.

## Time values

Type-specific attributes:
hour, minute, second
Time values are immutable.

## Tuples

Type-specific attributes:
length, first byte, second byte, third byte, ... , tenth byte
Tuples are immutable.

## Events

Type-specific attributes:
face, event type, offset, key, time, control, shift, double-click
Events are probably immutable.

## Unbound words

Type-specific attributes (for more info on words see Bindology):
spelling
Unbound words are immutable.

## Variables

Type-specific attributes (for more info on words see Bindology):
spelling, binding, value reference
The value reference attribute is volatile; Rebol variables can refer to different values during their lifetime.

## Series

Type-specific attributes:
index, length, element references
The length attribute is volatile (can be changed by the insert function), element references are volatile too (can be changed by the change function).
The index attribute of any-strings and any-blocks is regular as opposed to lists, where it is volatile.
The subtypes of series are:
* any-string!
* any-block!
* list!
The any-string! datatype consists from: binary!, email!, file!, issue!, string!, tag! and url!
The any-block! datatype consist from: block!, get-path!, lit-path!, paren!, path!, and set-path!

## Images

Images are like series with the distinction that they can be indexed using pairs.

## Hashes

Hashes are essentially blocks using hash table for lookup.

## Bitsets

Type-specific attributes are:
length, element references
Element references are volatile. (The insert and remove functions change element references.)

## Structs

Type-specific attributes are:
spec, binary code
The binary code attribute is volatile.

## Libraries

Type-specific attributes:
path, state
Both the path and state attributes are volatile.

## Objects/contexts

Type-specific attributes:
set of variables
The set of variables of an object cannot be enlarged, except for the global context. The global context can be enlarged using make, to and load functions.
Individual variables are volatile (see above).

## Errors

Rebol errors are relatives with objects. They can be transformed to objects using the disarm function.

## Ports

Type-specific attributes:
index, ...
Ports are relatives with objects (see the relatives? function above). They are mutable.

## Actions, natives, ops

Type-specific attributes:
spec, implementation
The spec attribute is volatile.

## Routines

Type-specific attributes:
spec, ref
The spec attribute is volatile.

## Functions

Type-specific attributes:
spec, body, function context (similar to object)
The spec and body attributes are volatile, individual variables in the function context are volatile too.

## Typesets

Type-specific attributes:
set of datatypes
Typesets look immutable.

## Symbols

Symbols look more like a datatype leaked from the implementation than like a true Rebol datatype.
The end.