Lambda the Ultimate

I don't agree with this. Subtracting two pointers may result in a negative distance, but this is fine as it just represents the offset of the first pointer to the second.

The simplest example of this is decrementing a pointer (which is adding a distance of minus one to it). Consider the following 'C' code:

void f(int* p) {
   int* q = --p;
   int distance = q - p;
}

Note the distance between p and q is minus one, which is completely correct as it represents the offset applied to 'p'. Note the distance is an integer not a pointer, and it is negative.

All of this makes sense so far. Adding two pointers does not result in another pointer, consider an array:

[1,2,3,4,5]

The address of the first element '1' is zero, the address of the second element '2' is one, we can subtract them to get the distance of '1', but this is not an addess, it is the distance between the two pointers into the array. What happens if we add the address of '1' to the address of '2' the result is not an address, and it is not a distance, it is something else.

See: http://geomalgorithms.com/points_and_vectors.html

I think this has a clue in something called Affine Addition.

My take: A vector is a directed magnitude. There are no locations in a vector algebra, only displacements. There is a choice of coordinate system, which allows locations to be described by vectors, but the choice of coordinate system is arbitrary. An actual pointer in C is a choice of coordinate system, and once you have that you can add and subtract integers — which from a typing perspective are vectors, displacements relative to the choice of coordinate system. Conversion from one choice of coordinate system (pointer) to another would be an affine transformation — scaling for type of element pointed to, translation for address in memory.

To treat everything as a vector ignores this important point from the linked article:

We have already seen that the difference between two points can be considered as a vector. However, in general, it makes no sense to add two points together. Points denote an absolute position in space independent of any coordinate system describing them. Blindly adding individual coordinates together would give different answers for different coordinate reference frames.

So although we can add vectors we cannot add points (pointers) except in the special case of the affine-sum.

Points *can* denote absolute positions in space independent of any coordinate system describing them. But no usable representation of points does. They all describe the position of points relative to an origin, and that description is a vector.

Vector sums and vector differences are well understood. In averaging or subtracting two vectors, the difference between the endpoints and the origin cancels. In an average the resulting point is always the midpoint on a straight line between the two original points, and in a subtraction the result is always a point with the same distance and opposite direction from the first arg, as the second arg w/r/t the first arg. These operations have the same locally-defined results irrespective of origin. But in adding two points, the result depends on the origin according to the parallelogram rule of vector addition.

This is very similar to the set of mathematical rules that apply to simple numeric operations. The average of any two numbers is the midpoint between them regardless of where they are relative to the origin, and the difference is likewise the same distance and opposite direction from one of them as that one is from the other, regardless of origin. But the sum depends on the distance of each number from the origin as well as its distance from the other number.

In which case, you're no longer treating pointers as one dimensional vectors, but rather as one dimensional coordinates. Not the same thing at all.

I like this way of thinking about it. Basically:

int* mid_point(int* p, int* q) {
    int d = q - p;
    int m = d / 2; // half the distance
    return p + m;
}

I guess the weird bit is we can calculate this the other way, by adding and dividing by two, and get the correct answer, even though the 'sum of two points' is not a real thing.

This seems a little like 'i' being sqrt(-1), in that calculations involving imaginary steps can have real results.

I wonder if what we have here is an imaginary type? A type that is not in the universe of real things (like 'i' is not in the universe of real numbers). Perhaps the dimension of "p + q" is an imaginary-point, or a point in an imaginary-space?

If you choose to understand a "pointer" as a machine address, then you have chosen a coordinate system in which the origin is the address that the machine calls zero, and the scale is such that a unit on the coordinate axis is one byte (typically; some machines use a differently scaled address space). So to do "pointer arithmetic" in that sense, you've already chosen a coordinate system and converted the pointers into vectors.

To amplify my earlier remark about affine transformation: Type-casting a C pointer is a scaling operation. Adding an integer to a C pointer is translation. C doesn't support reflection, which is also an affine transformation, but if it did, that would be reversing the direction of the array: if you start with a pointer a (of some type), set b=a+10, then set b to the reflection of b (for which there is no notation in C), then you'd have two coordinate systems with the same scale, and origins at a distance of 10 from each other using that scale, but with opposite sense, so that (a+10)==b and (b+10)==a. And then (a+5)==(b+5).

[edit: typo, 4 instead of 5; doh]

Great, I think this is what I was looking for. I think I managed to understand the idea topologically, but could not relate it to an algebraic construct.

A pointer plus a size defines an affine space over the vector space of the memory, is there an algebraic equivalent to a (Cartesian) affine frame, IE a pair of Torsors or a pair consisting of a Torsor and a Vector?

I think there are certainly pointers for which relative addressing makes no sense, but in many ways every pointer can be considered an affine frame, if it includes a size element.

The kind of pointers you describe have an implicit size of one, hence you cannot legally increment or decrement them.

We can also have affine frames of size more than one, which represents an array of values. Arrays are very important due to memory locality issues (which can be more important than the 'O' performance of the algorithm on modern hardware). With an affine frame we can allow access to any element in the frame as an affine space (zero offset addressing, with all operations available on an integer or vector) you may recognise this space as the array index (and this holds for multi-dimensional arrays).

So I don't think there is any question of which memory model, all memories are vector spaces, over which you can define affine spaces (defined by an affine frame). Algebraically this makes pointers a Torsor, and the difference between pointers a Vector.

The only meaningful 'casting' is to take one array index and use it to access a different array, which corresponds to rebasing the affine space containing the vector (index).

C formally uses a segmented architecture. Addition of offsets to pointers or formation of offsets by subtraction is well defined if, and only if, the pointers point at the head of, into, or one past the end of an object.

Pointers which can be subtracted can also form a total order and support comparisons.

Function pointers live in a separate space and support no operations except equality.

Because of this C++ adds a requirement for a template expressing a total order over ALL pointers (namely less<>, I'm responsible for this one :) This is not available in C.

The consequences of the rules are profound. In C data structures containing sorted collections of pointers to heap objects all have unspecified behavior. In C++ the behavior is well defined provided the
data structures uses the less template as a comparator.

dlsym() cannot possibly be implemented because a void* is only a valid holding place for data pointers, it may not hold a function address.

Note: these are rules of the abstract machine. There are of course additional rules related to types.

C rules have been abused for decades, mainly by ignorant Unix programmers. Those of us who started with Dos on x86 machines know better. Despite the fact most architectures these days use linear addressing, ISO C never did. One must note, however, that working in an extension of C or using it for platform specific programming is perfectly legitimate, but the extensions should be documented. For compilers, such documentation is often a mandatory requirement of the ISO Standard.

C memory models are particularly difficult because the correctness of an operation is not statically defined but depends on the liveness of the underlying object required to permit a calculation. For example it is quite hard to answer a really basic question such as: if a heap object is deleted, can you copy a pointer to it?

You may think it is only a bit pattern but you're wrong. On the x286 processor using segmented addresses a pointer is 48 bits and includes a resource descriptor: loading an invalid descriptor into a segment register causes a machine fault. Are you sure you don't have to NULL out every pointer to a deleted heap object in another object you might copy??

I am not specifically targeting the malloc model, but thinking about the abstract algebra of pointers. By getting pointers to behave according to the appropriate abstract algebra, we can get something much more consistent than the malloc model.

I think we can treat regions as affine spaces. As we don't know the affine-frame you cannot relate coordinates in one affine space to another. This would be a finite affine space defined by an affine frame. The affine frame defines the origin with a Torsor,and the scale with a vector (this is the unit size for the affine space).
A region would be a Torsor (base address), a unit vector (the size of an object), and a size (how many objects/unit-vectors in this region).

By this definition malloc simply defines a new affine space.

The whole contiguous memory (as seen by the CPU) is a vector space, and hence pointers are Torsors. This view is useful when subdividing a region. It seems to me the external view of a region is that a region is defined by a pair of Torsors or a Torsor and a vector.

In reality there is no null pointer, zero is a valid address. Option types should be used instead.

So the model fits very well. I think we can define these things _from_ the algebraic constructs and get a usable pointer system without any of the untidyness.

I think the suggestion of using the terminology "torsor" was that a pointer would be an element of the group of additive integers and an offset would be a torsor of that group. You wouldn't use "vectors" as these require a scalar field that you don't have.

Also, I don't see how you're going to recover regions from an assumption that there aren't regions. Getting rid of regions is simplifying and corresponds to a "flat memory model" where all memory is addressable with a single pointer from a single offset. I don't think this is necessarily what the CPU will see. For example, don't x86 machines still support mapping some segment registers to different addressable memory?

I think you're missing some key points. NO modern desktop level machine has a flat memory space. They all use virtual memory mapping. Depending on the system, this is similar to a segmented architecture: it allows the same memory to be addresses with distinct addresses, and it allows addresses that "map" to segment faults (unmapped address space). Most OS allow adding disk storage directly into the memory space (mmap). Some allow processes to share memory (Windows certainly does).

The primary difference between modern VM architectures and x286 style segmentation is that the hardware support for VM allows more flexible arrangement of the segments, except for the 4K boundary restriction of the paging system. Its slower, but the cost is usually hidden by lookahead, pipelining, caching etc.

Torsors cannot be added together, they can only have an 'affine sum' operation defined on them. This is like points in a vector space cannot be added together, but we can perform an affine sum (which calculates the centre of mass of the points). This models pointers which cannot be added together. So:

pointers = Torsors (you cannot add them together, subtracting a pointer from a pointer gives a vector, we can add and subtract vectors to a pointer, and we can define the affine-sum an example of which is the mid-point of two pointers)

offsets = Vectors (you can add together and subtract freely, as they represent offsets, any operation on a vector results in another vector, for example if we have an offset of 2 from the start of an array and an offset of 3, we can add these together to get an offset of 5, which is something you cannot do with a pointer/Torsor).

memory = A vector space (which consists of points (behave as Torsors) and vectors (behave as Vectors), so memory is a vector space, as we have both addresses (points) and offsets (vectors)).

a region = An affine space, we have relative address (a vector) relative to an unknown affine frame. An affine frame consists of a Torsor (the base pointer for the region) and a Vector (defining the scale factor, which is the size of the objects in this region). So the affine frame for a region of 32bit words starting at address 0x1000 would be (0x1000, 4). The affine frame lets us translate between the underlying vector space and the affine space defined over it. So if we don't know the start address and/or object size (because it is opaque) we cannot translate from the affine space to the underlying vector space, and we are 'stuck' in the affine space, in which we can quite happily operate with vector offsets. The easiest example of this is an integer array index which behaves like a one-dimensional vector, and we can add indexes together meaningfully.

As of x86, the 64bit instruction set abandoned segment registers altogether, and all modern operating systems map a processes address space as contiguous memory starting from address zero. The MMU is used to make the process think it has a flat-memory-model machine all to itself.

Yeah I bungled my words about torsors. My point was that you (technically) might not want to use vectors, but rather elements of the additive integer group. I think I'm just recalling that some compilers were using segment registers for thread local storage. That memory was probably aliased and also accessible via. some flat address.

Doesn't an integer behave like a one-dimensional vector?

Vector spaces are defined in terms of a scalar field, which would include all the real numbers, which you probably don't want.

Even modules are more than you want since they're over a ring.

[Or are they?]

It would be realistic at least, as CPUs tend to wrap address spaces rather than have an overflow error, but I am not sure if it is a good idea to require this behaviour.

I think the critical properties are the difference between a point and a vector. Memory locations are like points (adding them is nonsensical, but an affine sum makes sense) and offsets are like vectors (and the relationships hold subtracting two points gives a vector, you can add and subtract vectors from points, you cannot add points, and you can add or subtract a pair of vectors). These are the important relationships I think.

Yes, you are right of course. There is something called a finite affine space that looks like an integer version of an affine space. I would guess a finite vector space us the same for points?

The CPU doesn't see a vector space. For a start that would require a field of scalars (integers don't form a field, integers modulo a prime do but that is hardly what is seen). So you're probably looking for the generalisation of a vector space, which is called an R-module, which only requires a ring. However the reality is nothing like that, the reality on say an Intel CPU is that an address is just a bit pattern and you can apply various instructions to it including addition and multiplication.

The whole point of a type system which has a model of pointers is to restrict the allowed calculations. No such restriction exists in C99 with casts since intptr_t and uintptr_t allow all arithmetic on pointers.

The question is not: what kind of algebraic structure do pointers form, but what kind of algebra SHOULD they form, that is, how should they be typed?

There is no simple answer: Cyclone, Rust, and Felix all have complex answers. ATS2 probably has the best theoretical answer (using dependent typing to define the size of point at objects).

FYI: Felix has an interesting model. Data types like arrays, records, tuples are product types. Values are first class (purely functional, immutable). Components are selected by projection functions (and they can be first class, i.e. be used as values).

Ok, so if you store a value in a variable, you get an object. That is, you can get the variable's address. So here is the trick: every product projection of type T is overloaded to also accept a pointer &T and returns a pointer to the corresponding component.

So now, the calculus of offsets is simply a composition of the projections. This gets rid of lvalues and removes the need for any kind of offset arithmetic. Now we have an algebraic structure for you: it's a category whose arrows are projections, the sole operator is composition.
[Well technically we also have closure formation]

So the question is reduced to: what kind of product types does the system support, because that defines the category of pointer operations.

I am thinking of a fairly normal semantics, so that there are objects stored at addresses. Externally of any object address arithmetic is meaningless, however objects may be composed of sub-objects, and address arithmetic within an object may may sense (depending on the object).

The starting observation for all this was if I have a memory range between pointers A and B (where I don't know the base address of the space), I get something meaningful from subtracting A from B (the distance between the pointers). However adding the pointers gives nothing meaningful (as we don't know the base address.

For example consider an array of 32bit words starting at address 0x1000 and ending at address 0x2000. I can take any two address pointers in the object, say 0x1010 and 0x1020, and subtract them to get a meaningful distance of '10' units. However adding them together is not valid, in fact it gives an address outside the object itself (0x2030) so adding the pointers together is meaningless. However averaging the pointers (0.5 * 0x1010 + 0.5 * 0x1020) = 0x1018 which is meaningful as it is the mid-point between the pointers.

Are you sure this is not simply a database issue? This would seem more likely to me that a sudden, radical change in moderation behavior.

was i granted some superpower on the ltu site i never knew about? wow. cool. :-) i wish somebody would tell me so i could decline it.

I have not seen the comment, so it definitely has nothing to do with me.

I would say that I am interested in discussing the mathematics of addresses and offsets, rather than discussing if addresses and offsets are useful for programming, which is an entirely separate discussion. So if it was relevant to the discussion please repost it.

When was your comment posted? There was a database crash on Sunday, due to overzealous webcrawlers. It's possible that caused an issue.

When was your comment posted?

Monday.