Unions, program proofs and the Halting Problem

[Brendan]

Hi,

I think you have a problem of "anything I don't understand is puke."

Nobody should need to understand any of the things on that my "puke list". I do superficially understand all them, but I don't understand all the subtle little details of any of them.

For example, I don't understand how the compiler knows that you haven't used a borrowed pointer when you should've used an owned pointer (or used owned when you should've used borrowed). If it can't determine that you've used the right pointer, then it just converts one problem into a different problem without reducing the total number of problems. If it does know which pointer you should've used, then it could've auto-detected the owned/borrowed part instead of placing the burden on the programmer. Regardless of how you look at it, it's useless.

I also don't understand how it works for shared global data. For an example; let's imagine you've got a "main" function that detects if the CPU supports AVX or not and sets a global function pointer; then starts 10 threads, and then the main/initialisation thread terminates. After that those 10 threads use the function pointed to by the function pointer. Who owns this function pointer and who has borrowed it? If the main/initialisation thread owned it what happens when the main/initialisation thread terminates (the lifetime of the owned pointer expires while 10 threads are still borrowing it)?

For another example, what happens if you've got one global shared pointer to an "8:8:8" pixel buffer (a pointer to u32 data that was allocated on the heap) and another global shared pointer to a "5:6:5" pixel buffer (a pointer to u16 data that was allocated on the heap); and you've got 3 threads. One thread converts "8-bit green" from one buffer into "5-bit green" and stores it in the other buffer while doing Floyd–Steinberg dithering for green; and the other 2 threads do the same for red and blue at the same time (note: this is the only way I've found to use multiple CPUs to speed up Floyd–Steinberg dithering). Now let's also say that there's other threads drawing data in the "8:8:8" pixel buffer, except there's actually 2 of these "8:8:8" pixel buffers and you do something like page flipping (e.g. swap the global pointers to the "8:8:8" pixel buffers before starting the conversion/dithering so that other threads can be drawing in one buffer while your 3 threads are processing the other). Which of all these pointers are owned and which are borrowed? How does Rust know that the "blue thread" is only using the pointer/s to access the bits corresponding to blue? How does Rust know that no thread accesses anything beyond the end of a buffer?

The only thing in that list that's absolutely necessary is marking pointer ownership.

Given that we've been wandering all over the place (untagged unions vs. structure member co-location, tagged unions/enums, thread safety, pointer safety, etc) I wrote a "puke list" for the entire language rather than focusing on pointers alone.

Marking pointers as owned and borrowed (managed is gone and has been replaced with standard library types Rc<T> and Gc<T>) is the core feature of Rust pointer safety. Much like your language marks variables with ranges, Rust marks which place in the code is responsible for managing memory. It doesn't do anything behind your back, it doesn't generate any extra operations at runtime, it just enables better static analysis.

I'm not sure I want to get into memory management; but I've come to the conclusion that only having a single memory allocator is stupid (bad for cache coherency, bad for type checking, bad for profiling memory usage, etc). Also note that my OS has almost always had "process space" and "thread space" (with different allocators for different spaces) too. Once you start looking at having lots of special purpose allocators everywhere, marking all those places sounds like a nightmare.

You just have two symbols for pointer types in most code- ~u32 is an owned pointer and &u32 is a borrowed pointer. Owned pointers are freed when they go out of scope (so you can't leak memory) and track moving ownership (so you can't do multiple frees or use them from multiple threads, etc.), and borrowed pointers are verified not to outlive the owner (so you can't use after free or keep a reference when transferring ownership).

To improve performance I often deliberately "leak" memory - e.g. rather than freeing all the little pieces one at a time before a thread or process terminates, I'll just terminate the thread or process and let the kernel free the underlying pages. Of course (for thread termination) this only works when the OS has "thread space" (a large part of the virtual address space that is thread specific).

Marking safety extends this so you (or a library) can define new uses of pointers and enforce that they are used as intended. There is a third type- *u32 is a raw pointer and is used to implement new abstractions (like shared atomic types) and to interface with C. Safe is the default, so you only have to mark things unsafe in the implementation of new abstractions, like mutexes, reference counters, etc. This is a good thing, as the compiler makes sure you know the places you could screw up, and encourages you to put them behind interfaces rather than scattering them everywhere.

So the average programmer would get tired of bothering with owned/borrowed, and would just use raw pointers for everything? Cool!

Traits and implementations are, in general, not related to pointers. They are used to specify interfaces and that specific types implement them. Some of these are built-in and automatically determined by the compiler. For example, there's a Copy trait (it could have been renamed, not sure) that means a type is copyable without extra care like dealing with ownership moves.

Once you get rid of owned/borrowed everything can be copied safely without traits. Apart from that; if you can do something with a type then there's a function to do something with a type, and you only need to check if the function exists (unless some fool decides to have generic functions and you're screwed).

Vector types are just arrays, without C's pointer decay or other such nonsense. They are bounds-checked at runtime to maintain pointer safety, but I agree it would be more useful to do this with dependent types. They haven't done this because other language features are higher priority- the team is not opposed to it and it could be added in the future. Vectors do currently have some built-in behavior like resizing for heap-allocated vectors that is in the process of moving to the standard library.

I'll be doing bounds-checking (for arrays and "bounded pointers") at compile-time; and prefer to let people create their own higher level stuff (e.g. resizing) on top of that.

Attributes have nothing to do with pointer safety. They're used for what is essentially the equivalent of command line arguments that are stored in the source file. Linking, warnings, etc. They're also used for conditional compilation, which I don't get your objection to since your language has it in a very similar form.

I don't have a preprocessor at all (no macros and no conditional compiling). Instead of conditional compiling I rely on code optimisers and dead code elimination (e.g. rather than doing "#define USE_SOMETHING" and "#ifdef USE_SOMETHING" I'll do "const bool use_something = true" and "if(use_something) {"). Instead of macros I just have functions. Java does something similar.

I do have "multi-target", but this is only useful for a specific use case; and for that specific use case it's less hassle for the programmer and much more powerful than conditional code can be. For example; one of my ideas (for unit testing) is to compile all versions of a multi-target function that can be executed, and automatically check if they're all equivelent (e.g. so that it's easy to determine if your optimised assembly version/s of a function behave the same as the original higher level code version). Also note that my "multi-target" is designed to allow (e.g.) many different versions of a function for 32-bit 80x86, where different versions use different CPU features (e.g. with/without MMX, with/without SSE, etc) and the compiler automatically selects the best version that the target CPU supports (based on target CPU's supported features).

Macros have nothing to do with pointer safety in Rust. They are, however, better than C macros (which are why, I assume, you call them puke)- they are based on the AST rather than text, so there's no problems with e.g. extra parentheses around arguments, and they are clearly marked- all macro names end with !. So assert!(), fail!(), println!(), are basically functions on actual language constructs that run at compile time. They also let printf be type checked at compiler time.

In my opinion, once you fix all the problems with "C like" macros (e.g. including the ability to do type checking on macro parameters), you end up with functions.

Lambdas and closures have nothing to do with pointer safety. They are made safe by it, but nothing else. They don't hide anything behind your back either- their environment, the compiler-checked version of the "void *user" parameter for callbacks in C can be specified to live on the stack or heap just like in C.

Just use function pointers.

Generic functions have nothing to do with pointer safety. Instead, they have to do with not forcing the programmer to write braindead copy-pasted versions of functions on things like lists, trees, etc. without losing the ability of the compiler to check things.

I want to make it easier for programmers to write fast code than it is for them to write slow code. I need to encourage programmers to write the best code for their specific case and force them to actually think about what their code is asking the CPU to do; and I need to prevent them from just using "works for everything but ideal for nothing" trash.

For an example; let's say someone needs a list sorted in descending order. The best way is to create the list in descending order in the first place. The worst way is to create the list in random order because it's easier, then use a generic "sort()" to sort it in ascending order because it's easier, then use a generic "reverse()" to convert it into descending order because it's easier.


Cheers,

Brendan

[Rusky]

For example, I don't understand how the compiler knows that you haven't used a borrowed pointer when you should've used an owned pointer (or used owned when you should've used borrowed). If it can't determine that you've used the right pointer, then it just converts one problem into a different problem without reducing the total number of problems. If it does know which pointer you should've used, then it could've auto-detected the owned/borrowed part instead of placing the burden on the programmer. Regardless of how you look at it, it's useless.

I also don't understand how it works for shared global data. For an example; let's imagine you've got a "main" function that detects if the CPU supports AVX or not and sets a global function pointer; then starts 10 threads, and then the main/initialisation thread terminates. After that those 10 threads use the function pointed to by the function pointer. Who owns this function pointer and who has borrowed it? If the main/initialisation thread owned it what happens when the main/initialisation thread terminates (the lifetime of the owned pointer expires while 10 threads are still borrowing it)?

Typically, whoever does the allocation gets the owned pointer. This type is inferred, so you just say "let foo = ~Something;" Function arguments and return values are about the only place you have to specify ~ vs &, and in that case it's something you already have to think about regardless so you may as well have compiler-checked documentation for whether a function takes responsibility for freeing the memory or not. The majority of functions will probably just use &.

Shared global data uses & with the lifetime 'static, as it isn't freed- there is no ~. Writing a mutable global is unsafe, but since you're just doing it once at the beginning you just mark that one place and you're good. If you were to start writing it a lot, all the extra unsafe blocks would be a hint that you should think about concurrency.

For another example, what happens if you've got one global shared pointer to an "8:8:8" pixel buffer (a pointer to u32 data that was allocated on the heap) and another global shared pointer to a "5:6:5" pixel buffer (a pointer to u16 data that was allocated on the heap); and you've got 3 threads. One thread converts "8-bit green" from one buffer into "5-bit green" and stores it in the other buffer while doing Floyd–Steinberg dithering for green; and the other 2 threads do the same for red and blue at the same time (note: this is the only way I've found to use multiple CPUs to speed up Floyd–Steinberg dithering). Now let's also say that there's other threads drawing data in the "8:8:8" pixel buffer, except there's actually 2 of these "8:8:8" pixel buffers and you do something like page flipping (e.g. swap the global pointers to the "8:8:8" pixel buffers before starting the conversion/dithering so that other threads can be drawing in one buffer while your 3 threads are processing the other). Which of all these pointers are owned and which are borrowed? How does Rust know that the "blue thread" is only using the pointer/s to access the bits corresponding to blue? How does Rust know that no thread accesses anything beyond the end of a buffer?

Rust's pointer safety isn't granular enough to deal with members of an array separately, let alone bit fields. I wouldn't put those pointers in globals (what if you want to run more than one conversion at once?), but the problem still stands. If they were in globals you wouldn't have the owner problem; when they're not in globals they're owned by whatever function is controlling those threads (as that's the code responsible for allocating the buffers and handing them out).

As for knowing that each thread only accesses certain bits, that's going to be up to you, especially considering that the 5:6:5 are not accessible atomically anyway. I will emphasize that this case is no worse than your language or C, but other cases are better.

Knowing that threads don't access beyond the end of the buffer is currently done with runtime array bounds checking. We've already agreed multiple times that it would be nicer to use dependent types.

I'm not sure I want to get into memory management; but I've come to the conclusion that only having a single memory allocator is stupid (bad for cache coherency, bad for type checking, bad for profiling memory usage, etc). Also note that my OS has almost always had "process space" and "thread space" (with different allocators for different spaces) too. Once you start looking at having lots of special purpose allocators everywhere, marking all those places sounds like a nightmare.

To improve performance I often deliberately "leak" memory - e.g. rather than freeing all the little pieces one at a time before a thread or process terminates, I'll just terminate the thread or process and let the kernel free the underlying pages. Of course (for thread termination) this only works when the OS has "thread space" (a large part of the virtual address space that is thread specific).

Rust already has arena allocators in its standard library. They simply give you borrowed pointers with the same lifetime as the allocator, which is all handled by the library declarations so you generally don't have to deal with it. This also solves your "leak" use case. In the more complicated case where memory gets allocated and freed, I don't see how marking pointers from different allocators is any worse than your system- you still have to keep track of which allocator to give memory back to. May as well have the type system help you.

Hmm, maybe with your own type wrapped around a raw pointer, implementing some traits... but that would need a way to specify at compile time which allocator it belongs to, as well as which type it points to... I guess that's a horrible idea, because every allocator needs to have its free() called a different way for efficiency, and every pointer type needs a different layout in memory. Oh wait. Pointers and arrays are already generics built into every language on the planet.

So the average programmer would get tired of bothering with owned/borrowed, and would just use raw pointers for everything? Cool!

Nope, the type system won't let you as e.g. dereferencing a raw pointer is unsafe. Honestly it's not that complicated, it just takes getting used to, the same way marking variable ranges would. It's something you already have to think about in a systems language- who is going to free memory- the language just helps you.

Once you get rid of owned/borrowed everything can be copied safely without traits.

...according to the language. Until you accidentally copy a pointer and free it twice. Which is a problem you have regardless of whether your language has owned/borrowed, so the language should help you with it to improve its ability to catch errors.

I don't have a preprocessor at all (no macros and no conditional compiling). Instead of conditional compiling I rely on code optimisers and dead code elimination (e.g. rather than doing "#define USE_SOMETHING" and "#ifdef USE_SOMETHING" I'll do "const bool use_something = true" and "if(use_something) {"). Instead of macros I just have functions. Java does something similar.

I do have "multi-target", but this is only useful for a specific use case; and for that specific use case it's less hassle for the programmer and much more powerful than conditional code can be. For example; one of my ideas (for unit testing) is to compile all versions of a multi-target function that can be executed, and automatically check if they're all equivelent (e.g. so that it's easy to determine if your optimised assembly version/s of a function behave the same as the original higher level code version). Also note that my "multi-target" is designed to allow (e.g.) many different versions of a function for 32-bit 80x86, where different versions use different CPU features (e.g. with/without MMX, with/without SSE, etc) and the compiler automatically selects the best version that the target CPU supports (based on target CPU's supported features).

Sometimes it's simply impossible to get away without conditional compilation. You can use optimized-out if-branches all you want until one of them uses some API or machine instruction that doesn't exist on your target platform. Then the only ways out are 1) allow undefined references and hope they get optimized out, or 2) conditional compilation through either the build system and multiple files or something the compiler actually understands, like multitarget. Rust's falls in the last category, as conditional compilation is done based on things like the target architecture, target OS, etc. so all your multitarget features are possible.

In my opinion, once you fix all the problems with "C like" macros (e.g. including the ability to do type checking on macro parameters), you end up with functions.

Do these functions run at compile time so you can type-check printf? Can they manipulate syntax so you can have assert fails, log output, etc. print the source file and line, or generate new items like entries in a statically-generated table?

Just use function pointers.

They are function pointers, where you can write the function definition right where it's used, and where the "void *udata" parameter is type checked.

I want to make it easier for programmers to write fast code than it is for them to write slow code. I need to encourage programmers to write the best code for their specific case and force them to actually think about what their code is asking the CPU to do; and I need to prevent them from just using "works for everything but ideal for nothing" trash.

For an example; let's say someone needs a list sorted in descending order. The best way is to create the list in descending order in the first place. The worst way is to create the list in random order because it's easier, then use a generic "sort()" to sort it in ascending order because it's easier, then use a generic "reverse()" to convert it into descending order because it's easier.

Even the Linux kernel uses generics for things like walking linked lists. Whether you acknowledge it or not, there are some functions and types that are always exactly the same, and there's no point in duplicating them just for the sake of the few cases where they should be different.

[embryo]

Without the "in edx", parameters get passed on the stack.

For me it seems like heavy mix of the high and low levels. We can have a low level function, implemented in assembly, but it's parameters are exposed to the high level. If we use something like "in edx" then it leads to some restrictions for the compiler and to some additional attention from the developer. But if the function parameters always have the same meaning as for the standard high level function call, then the compiler is free to choose any method of parameter value access and the developer makes less bugs because the call has no difference from it's standard meaning.

[Brendan]

Hi,

For another example, what happens if you've got one global shared pointer to an "8:8:8" pixel buffer (a pointer to u32 data that was allocated on the heap) and another global shared pointer to a "5:6:5" pixel buffer (a pointer to u16 data that was allocated on the heap); and you've got 3 threads. One thread converts "8-bit green" from one buffer into "5-bit green" and stores it in the other buffer while doing Floyd–Steinberg dithering for green; and the other 2 threads do the same for red and blue at the same time (note: this is the only way I've found to use multiple CPUs to speed up Floyd–Steinberg dithering). Now let's also say that there's other threads drawing data in the "8:8:8" pixel buffer, except there's actually 2 of these "8:8:8" pixel buffers and you do something like page flipping (e.g. swap the global pointers to the "8:8:8" pixel buffers before starting the conversion/dithering so that other threads can be drawing in one buffer while your 3 threads are processing the other). Which of all these pointers are owned and which are borrowed? How does Rust know that the "blue thread" is only using the pointer/s to access the bits corresponding to blue? How does Rust know that no thread accesses anything beyond the end of a buffer?

Rust's pointer safety isn't granular enough to deal with members of an array separately, let alone bit fields. I wouldn't put those pointers in globals (what if you want to run more than one conversion at once?), but the problem still stands. If they were in globals you wouldn't have the owner problem; when they're not in globals they're owned by whatever function is controlling those threads (as that's the code responsible for allocating the buffers and handing them out).

As for knowing that each thread only accesses certain bits, that's going to be up to you, especially considering that the 5:6:5 are not accessible atomically anyway. I will emphasize that this case is no worse than your language or C, but other cases are better.

The conversion would be done by a video driver for "generic framebuffer" (everything else involving graphics would/should be resolution independent); so you only need multiple conversions at the same time when you've got multiple separate video drivers.

If the destination buffer is cleared to zero first; then it's simple to do an atomic "lock or [dest],eax".

I'm not sure I want to get into memory management; but I've come to the conclusion that only having a single memory allocator is stupid (bad for cache coherency, bad for type checking, bad for profiling memory usage, etc). Also note that my OS has almost always had "process space" and "thread space" (with different allocators for different spaces) too. Once you start looking at having lots of special purpose allocators everywhere, marking all those places sounds like a nightmare.

To improve performance I often deliberately "leak" memory - e.g. rather than freeing all the little pieces one at a time before a thread or process terminates, I'll just terminate the thread or process and let the kernel free the underlying pages. Of course (for thread termination) this only works when the OS has "thread space" (a large part of the virtual address space that is thread specific).

Rust already has arena allocators in its standard library. They simply give you borrowed pointers with the same lifetime as the allocator, which is all handled by the library declarations so you generally don't have to deal with it. This also solves your "leak" use case. In the more complicated case where memory gets allocated and freed, I don't see how marking pointers from different allocators is any worse than your system- you still have to keep track of which allocator to give memory back to. May as well have the type system help you.

Hmm, maybe with your own type wrapped around a raw pointer, implementing some traits... but that would need a way to specify at compile time which allocator it belongs to, as well as which type it points to... I guess that's a horrible idea, because every allocator needs to have its free() called a different way for efficiency, and every pointer type needs a different layout in memory. Oh wait. Pointers and arrays are already generics built into every language on the planet.

Don't be silly. Different allocators need different code, so generics are a waste of time. Of course it's (almost) never just memory allocation and deallocation.

For an example (in C); let's say you've got a "file buffer" structure like this:

Code: Select all

typedef struct file_buffer {
    struct *nextFreeList;
    char *fileName;
    int fileHandle;
    uint8_t *buffer;
    unsigned int bufferSize;
    unsigned int bufferPos;
} FILE_BUFFER;

Then you've got your free pool of file buffer structures (and some stuff for managing the pool):

Code: Select all

FILE_BUFFER fileBufferPool[MAX_BUFFERS];    //Note: Assumes kernel supports "allocation on demand"
int nextUntouchedSlot = 0;
FILE_BUFFER *freeFileBufferList = NULL;

The allocator might look like this:

Code: Select all

FILE_BUFFER *createFileBuffer(char *fileName) {
    int slot;
    FILE_BUFFER *fileBuffer;
    int fileNameLength;
    char *tempFileName;

    // Pre-allocate copy of file name string

    fileNameLength = strlen(fileName);
    tempFileName = malloc(fileNameLength + 1);
    if(tempFileName == NULL) {
        return NULL;
    }
    memcpy(tempFileName, fileName, fileNameLength);

    // Allocate the file buffer structure

    if(freeFileBufferList != NULL) {
        fileBuffer = freeFileBufferList;
        freeFileBufferList = fileBuffer->next;
    } else {
        slot = nextUntouchedSlot++;
        if(slot >= MAX_BUFFERS) {
            nextUntouchedSlot--;
            free(tempFileName);
            return NULL;
        }
        fileBuffer = &fileBufferPool[slot];
    }

    // Pre-configure it and return it

    fileBuffer->fileName = tempFileName;
    fileBuffer->fileHandle = -1;
    fileBuffer->buffer = NULL;
    fileBuffer->bufferSize = 0;
    return fileBuffer;
}

The deallocator might be:

Code: Select all

int destroyFileBuffer(FILE_BUFFER *fileBuffer) {

    // Do sanity checks

    if( (fileBuffer < &fileBufferPool[0]) || (fileBuffer > &fileBufferPool[nextUntouchedSlot]) ) {
        return FAIL;
    }
    if( (fileBuffer - &fileBufferPool[0]) % sizeof(FILE_BUFFER) != 0) {
        return FAIL;
    }

    // Do cleanup

    if(fileBuffer->fileHandle >= 0) close(fileBuffer->fileHandle);
    free(fileBuffer->fileName);
    if(fileBuffer->buffer != NULL) free(fileBuffer->buffer);

    // Add structure back to pool and return OK

    fileBuffer->nextFreeList = freeFileBufferList;
    freeFileBufferList = fileBuffer;
    return OK;
}

Of course:

• the "freeFileBufferList" could be a lock-free list (using "compare and swap")
• the "slot = nextUntouchedSlot++;" and "nextUntouchedSlot--;" can both be done atomically on 80x86 ("lock xadd" and "lock sub")
• with the previous 2 things, the entire allocator and deallocator could be lockless
• you could add a "bool isFree;" member to the structure if you want better sanity checking
• it has good cache locality (e.g. all FILE_BUFFER structures are as close together as possible)
• the "recycle recently freed" behaviour helps avoid cache misses
• if someone makes a mistake and tries to allocate an infinite number of these structures, it's going to run out reasonably quickly and won't allocate all RAM and cause the OS to start swapping (it's like having fine granularity RAM quotas)
• it'd be trivial to add a global "bool aboutToTerminate;" and do "if(aboutToTerminate) { return OK }" in the middle of the cleanup in "destroyFileBuffer()"
• the "lazy cleanup" makes it much easier to maintain the rest of the code (note: similar benefits as constructors and destructors in OOP languages)
• after profiling it, you might (or not) find that it's better to remove the "if(fileBuffer->buffer != NULL) free(fileBuffer->buffer);" instead of freeing and re-allocating those

Note that this is only one allocator that is designed for one purpose. The same basic idea of using an array of structures as a memory pool won't work for variable sized allocations (at least not without wasting a lot of RAM), won't work if there's no allocation on demand (e.g. boot code, and maybe kernel code for some kernels), would probably be bad if there's very little virtual memory to work with (due to pre-allocating a large amount of space). It may be optimised for "no concurrency" or "with concurrency" (whether you want lock-free or not), could be customised for various CPU features (Intel's recent transactional extensions maybe?), might need to be customised to suit whatever error logging/handling an executable happens to use (e.g. maybe the deallocator should call some sort of "panic()" when sanity checks fail, or maybe have some code in the allocator that adds a "used more than 75% of the file buffer memory pool" message to a log when appropriate), etc.

Basically; even though this is already an allocator designed for one specific purpose, there's still different things that can be done to make it better (more specific) for the actual use case.

Once you get rid of owned/borrowed everything can be copied safely without traits.

...according to the language. Until you accidentally copy a pointer and free it twice. Which is a problem you have regardless of whether your language has owned/borrowed, so the language should help you with it to improve its ability to catch errors.

Assuming "free it twice" means "free the data it points to twice"; see the notes for my allocator example above (specifically; the "you could add a "bool isFree;" member to the structure if you want better sanity checking" part). If it's not a problem for a language that doesn't have owned/borrowed (like C), then...

I don't have a preprocessor at all (no macros and no conditional compiling). Instead of conditional compiling I rely on code optimisers and dead code elimination (e.g. rather than doing "#define USE_SOMETHING" and "#ifdef USE_SOMETHING" I'll do "const bool use_something = true" and "if(use_something) {"). Instead of macros I just have functions. Java does something similar.

I do have "multi-target", but this is only useful for a specific use case; and for that specific use case it's less hassle for the programmer and much more powerful than conditional code can be. For example; one of my ideas (for unit testing) is to compile all versions of a multi-target function that can be executed, and automatically check if they're all equivelent (e.g. so that it's easy to determine if your optimised assembly version/s of a function behave the same as the original higher level code version). Also note that my "multi-target" is designed to allow (e.g.) many different versions of a function for 32-bit 80x86, where different versions use different CPU features (e.g. with/without MMX, with/without SSE, etc) and the compiler automatically selects the best version that the target CPU supports (based on target CPU's supported features).

Sometimes it's simply impossible to get away without conditional compilation. You can use optimized-out if-branches all you want until one of them uses some API or machine instruction that doesn't exist on your target platform.

These problems aren't really possible. There's 2 compilers (one used by programmers to create a "portable executable" and one used by the end-user to convert it into a native executable for their CPU). If it uses an instruction that doesn't exist then the worst case is the user gets a compile time error. Of course these end-user compile time errors should be rare ("multi-target" requires a higher level code version in case none of the assembly versions are usable on the end-user's CPU). For my OS there is only one API (the kernel API) and it uses a standardised set of error codes and guarantees that an unsupported function returns the standard "unsupported function" error. I'm not expecting this language to be ported to other people's OSs (it's specifically designed for my "everything redesigned" OS and I'd assume it'd be like driving a submarine on a highway for other OSs).

In my opinion, once you fix all the problems with "C like" macros (e.g. including the ability to do type checking on macro parameters), you end up with functions.

Do these functions run at compile time so you can type-check printf? Can they manipulate syntax so you can have assert fails, log output, etc. print the source file and line, or generate new items like entries in a statically-generated table?

I have no intention of supporting functions with variable argument lists. There's no need to manipulate syntax so you can have assert function that accepts a bool (and an error message, line number, whatever) as an argument. I have no idea what you mean by "log output".

For statically generated tables, just use a function instead. For example; let the compiler convert "myFunction(arg1 as range 0 to 123, arg2 as range 0 to 456") (myResult as u32)" into the equivalent of "myTable[123][456] as u32" at compile time. Note: some restrictions apply, mostly the function would need to be a "pure function" and the resulting table would need to be reasonably sized.

I want to make it easier for programmers to write fast code than it is for them to write slow code. I need to encourage programmers to write the best code for their specific case and force them to actually think about what their code is asking the CPU to do; and I need to prevent them from just using "works for everything but ideal for nothing" trash.

For an example; let's say someone needs a list sorted in descending order. The best way is to create the list in descending order in the first place. The worst way is to create the list in random order because it's easier, then use a generic "sort()" to sort it in ascending order because it's easier, then use a generic "reverse()" to convert it into descending order because it's easier.

Even the Linux kernel uses generics for things like walking linked lists. Whether you acknowledge it or not, there are some functions and types that are always exactly the same, and there's no point in duplicating them just for the sake of the few cases where they should be different.

Am I supposed to care? A small amount of code duplication is better than the alternative; and if a programmer isn't able to write their own correct linked list code in less time than it takes to remember how to use a shrink-wrapped version then I'd prefer they go and work on the Linux kernel instead (or be forced to re-implement it repeatedly until they learn how to program).


Cheers,

Brendan

[Brendan]

Hi,

Without the "in edx", parameters get passed on the stack.

For me it seems like heavy mix of the high and low levels. We can have a low level function, implemented in assembly, but it's parameters are exposed to the high level. If we use something like "in edx" then it leads to some restrictions for the compiler and to some additional attention from the developer. But if the function parameters always have the same meaning as for the standard high level function call, then the compiler is free to choose any method of parameter value access and the developer makes less bugs because the call has no difference from it's standard meaning.

I'm not too sure that I've understood what you're saying here...

Are you suggesting something like "myParameter as u32 in any", where the compiler chooses which register to use for "any"? If you are, then you're right - something like that would make it easier to write assembly and give the compiler/optimiser more freedom.


Cheers,

Brendan

[embryo]

I'm not too sure that I've understood what you're saying here...

If it's because of my english - just tell me where it is wrong, I appreciate any help in this area.

Are you suggesting something like "myParameter as u32 in any", where the compiler chooses which register to use for "any"?

Yes. And even "in any" may be omitted. If there is no free register at the moment (all registers are occupied with something more important), then compiler can place the value on the stack.

[Rusky]

The conversion would be done by a video driver for "generic framebuffer" (everything else involving graphics would/should be resolution independent); so you only need multiple conversions at the same time when you've got multiple separate video drivers.

If the destination buffer is cleared to zero first; then it's simple to do an atomic "lock or [dest],eax".

So there's no such thing as multiple frame buffers for a single driver? And there still is the possibility of separate video drivers. Regardless, even using globals, owned/borrowed pointers are not a problem here.

Don't be silly. Different allocators need different code, so generics are a waste of time. Of course it's (almost) never just memory allocation and deallocation.
...
Basically; even though this is already an allocator designed for one specific purpose, there's still different things that can be done to make it better (more specific) for the actual use case.

Your example is not hindered by owned/borrowed pointers, nor is there a reason to limit that system to file_buffers. You could parametrize it with a struct that implements a trait to handle the file_buffer-specific construction and destruction, as well as potentially a trait to provide hooks for error handling, etc. None of your bullet points has anything to do with file_buffers specifically- they would be equally if not more useful for things as widely varied as game engines, network drivers, small thread/coroutine contexts, etc. So you can copy and paste your allocator around for different use cases and then add all your optimizations to all of them separately, or you can do it in one place.

(specifically; the "you could add a "bool isFree;" member to the structure if you want better sanity checking" part). If it's not a problem for a language that doesn't have owned/borrowed (like C), then...

Oh, so your language catches that at compile time without adding a field to every allocated object?

These problems aren't really possible. There's 2 compilers (one used by programmers to create a "portable executable" and one used by the end-user to convert it into a native executable for their CPU). If it uses an instruction that doesn't exist then the worst case is the user gets a compile time error. Of course these end-user compile time errors should be rare ("multi-target" requires a higher level code version in case none of the assembly versions are usable on the end-user's CPU). For my OS there is only one API (the kernel API) and it uses a standardised set of error codes and guarantees that an unsupported function returns the standard "unsupported function" error. I'm not expecting this language to be ported to other people's OSs (it's specifically designed for my "everything redesigned" OS and I'd assume it'd be like driving a submarine on a highway for other OSs).

So you solve those problems with conditional compilation (multitarget). Good, we agree.

I have no intention of supporting functions with variable argument lists. There's no need to manipulate syntax so you can have assert function that accepts a bool (and an error message, line number, whatever) as an argument. I have no idea what you mean by "log output".

So you want the programmer manually to type in the source file name and line when they assert, when they write out a log message, etc.?

For statically generated tables, just use a function instead. For example; let the compiler convert "myFunction(arg1 as range 0 to 123, arg2 as range 0 to 456") (myResult as u32)" into the equivalent of "myTable[123][456] as u32" at compile time. Note: some restrictions apply, mostly the function would need to be a "pure function" and the resulting table would need to be reasonably sized.

Doesn't work when you don't just want a table as an optimization, like with processor-defined tables.

edit: you do seem to be fond of copy and paste; at least look at something that tries to make it not suck First Class Copy & Paste

[Brendan]

Hi,

Don't be silly. Different allocators need different code, so generics are a waste of time. Of course it's (almost) never just memory allocation and deallocation.
...
Basically; even though this is already an allocator designed for one specific purpose, there's still different things that can be done to make it better (more specific) for the actual use case.

Your example is not hindered by owned/borrowed pointers, nor is there a reason to limit that system to file_buffers. You could parametrize it with a struct that implements a trait to handle the file_buffer-specific construction and destruction, as well as potentially a trait to provide hooks for error handling, etc.

I could parameterise it with a struct that implements a trait, but if I really wanted to obfuscate it (make it harder to read, harder to maintain, etc) then there are more effective ways (especially for C). I do agree that your "system of puke" wouldn't be limited to just file_buffers and could be recycled if I wanted to make other allocators worse too.

None of your bullet points has anything to do with file_buffers specifically- they would be equally if not more useful for things as widely varied as game engines, network drivers, small thread/coroutine contexts, etc. So you can copy and paste your allocator around for different use cases and then add all your optimizations to all of them separately, or you can do it in one place.

The "benefits" of making the code pointlessly over-complicated do not justify the disadvantages for the programmer/s themselves (trying to follow logic that's spread everywhere), for the people writing tools for the language, or for people trying to learn the language.

(specifically; the "you could add a "bool isFree;" member to the structure if you want better sanity checking" part). If it's not a problem for a language that doesn't have owned/borrowed (like C), then...

Oh, so your language catches that at compile time without adding a field to every allocated object?

No, and neither does yours (oops, I mean someone else's) - Rust would let you free the same memory 20 times from within an "unsafe" block.

These problems aren't really possible. There's 2 compilers (one used by programmers to create a "portable executable" and one used by the end-user to convert it into a native executable for their CPU). If it uses an instruction that doesn't exist then the worst case is the user gets a compile time error. Of course these end-user compile time errors should be rare ("multi-target" requires a higher level code version in case none of the assembly versions are usable on the end-user's CPU). For my OS there is only one API (the kernel API) and it uses a standardised set of error codes and guarantees that an unsupported function returns the standard "unsupported function" error. I'm not expecting this language to be ported to other people's OSs (it's specifically designed for my "everything redesigned" OS and I'd assume it'd be like driving a submarine on a highway for other OSs).

So you solve those problems with conditional compilation (multitarget). Good, we agree.

I've already provided several reasons why "multi-target" is not the same as conditional complication. It's bad that you can't read.

I have no intention of supporting functions with variable argument lists. There's no need to manipulate syntax so you can have assert function that accepts a bool (and an error message, line number, whatever) as an argument. I have no idea what you mean by "log output".

So you want the programmer manually to type in the source file name and line when they assert, when they write out a log message, etc.?

I don't know. To be honest, I haven't thought much about how the OS should handle crashes yet (where "assert()" is just a voluntary crash). My current thoughts are that the kernel should notify something that the process crashed, and that "something" should decide what to do (e.g. attach a debugger to the crashed process immediately, or display a "this program crashed because..." dialog box, and/or send a report to the developer's email address, etc).

For statically generated tables, just use a function instead. For example; let the compiler convert "myFunction(arg1 as range 0 to 123, arg2 as range 0 to 456") (myResult as u32)" into the equivalent of "myTable[123][456] as u32" at compile time. Note: some restrictions apply, mostly the function would need to be a "pure function" and the resulting table would need to be reasonably sized.

Doesn't work when you don't just want a table as an optimization, like with processor-defined tables.

Yes it does. Note: What I mean here is that I'm too lazy to figure out all the very different things that you could've meant by "processor-defined tables" and show that it is possible for each possible case in the hope of getting lucky and covering whatever it was that you failed to describe adequately.

edit: you do seem to be fond of copy and paste; at least look at something that tries to make it not suck First Class Copy & Paste

A smart person can invent something complicated; but it takes a genius to describe something complicated in a way that can be understood. Only a complete moron would write sentences like "Speculative execution of queued hypotheticals provides concurrency as a semantically transparent implementation optimization." and expect others to read it. Perhaps you should've attempted to clearly describe whatever your point might be, rather than merely providing a link to a seemingly random piece of academic gibberish?


Cheers,

Brendan

[Rusky]

I could parameterise it with a struct that implements a trait, but if I really wanted to obfuscate it (make it harder to read, harder to maintain, etc) then there are more effective ways (especially for C). I do agree that your "system of puke" wouldn't be limited to just file_buffers and could be recycled if I wanted to make other allocators worse too.

The "benefits" of making the code pointlessly over-complicated do not justify the disadvantages for the programmer/s themselves (trying to follow logic that's spread everywhere), for the people writing tools for the language, or for people trying to learn the language.

It's called separation of concerns. Separating parts of the code that address separate issues (allocating memory, initializing a file buffer, etc.) makes code easier to read, maintain, and test. The only possible reason "logic that's spread everywhere" (not really) could be a problem is if you have a bad editor. Especially in your case where you want good IDE support, you could easily show the allocator and the file_buffer code right next to each other.

No, and neither does yours (oops, I mean someone else's) - Rust would let you free the same memory 20 times from within an "unsafe" block.

As has been stated many times, outside of unsafe blocks you still get your code verified. There's a large difference of degree between "most code is verified" and "no code is verified."

I've already provided several reasons why "multi-target" is not the same as conditional complication. It's bad that you can't read.

I can read, your reasons are just wrong. Multitarget provides multiple implementations of a function, which are selected based on the configuration of the target. That is the definition of conditional compilation.

Doesn't work when you don't just want a table as an optimization, like with processor-defined tables.

Yes it does. Note: What I mean here is that I'm too lazy to figure out all the very different things that you could've meant by "processor-defined tables" and show that it is possible for each possible case in the hope of getting lucky and covering whatever it was that you failed to describe adequately.

Statically declare the initial contents of your GDT using a function. I dare you to make that simpler and more clear than just using a table directly, and without requiring static constructors to verify that it's initialized (that *is* puke).

A smart person can invent something complicated; but it takes a genius to describe something complicated in a way that can be understood. Only a complete moron would write sentences like "Speculative execution of queued hypotheticals provides concurrency as a semantically transparent implementation optimization." and expect others to read it. Perhaps you should've attempted to clearly describe whatever your point might be, rather than merely providing a link to a seemingly random piece of academic gibberish?

...or someone whose target audience knows those concepts already and wants to focus on what they actually did? Which, by the way, is right in the abstract: "Inclusions reify copy & paste edits into persistent relationships that propagate changes from their source into their destination." That way you could implement your file_buffer allocator, copy and paste it somewhere else for a different allocator, and then fixing a bug or adding a feature in one would (optionally) fix it in the other.

[Brendan]

Hi,

I could parameterise it with a struct that implements a trait, but if I really wanted to obfuscate it (make it harder to read, harder to maintain, etc) then there are more effective ways (especially for C). I do agree that your "system of puke" wouldn't be limited to just file_buffers and could be recycled if I wanted to make other allocators worse too.

The "benefits" of making the code pointlessly over-complicated do not justify the disadvantages for the programmer/s themselves (trying to follow logic that's spread everywhere), for the people writing tools for the language, or for people trying to learn the language.

It's called separation of concerns. Separating parts of the code that address separate issues (allocating memory, initializing a file buffer, etc.) makes code easier to read, maintain, and test. The only possible reason "logic that's spread everywhere" (not really) could be a problem is if you have a bad editor. Especially in your case where you want good IDE support, you could easily show the allocator and the file_buffer code right next to each other.

Each line of source code is concerned with something slightly different; so instead of having a function with 20 lines of source code it's better to have 20 functions with one line of source code each, then spread those 20 functions into as many different files as possible (e.g. one file for lines of code that use multiplication, one file for lines of code that contain loop starts, on file for lines of code that use branches, etc).

Obviously you can take "separation of concerns" too far. To prevent taking things too far, you also need to group related things together. Code to allocate a file buffer and code to initialise a file buffer are very strongly related - when you create a file buffer you always do both (allocate then initialise). Code to allocate a "person structure" and code to initialise a "person structure" would also be very strongly related (both are parts of person structure creation). A file buffer has nothing to do with a "person structure" in any way whatsoever; so grouping anything related to "file buffer" with anything related to "person structure" is silly.

No, and neither does yours (oops, I mean someone else's) - Rust would let you free the same memory 20 times from within an "unsafe" block.

As has been stated many times, outside of unsafe blocks you still get your code verified. There's a large difference of degree between "most code is verified" and "no code is verified."

Except you're using a deliberately biased comparison, and it's actually "most code is verified" vs. "most code is verified".

My tools won't verify everything at compile time (e.g. pointers), and Rust won't verify everything at compile time (e.g. anything that had to be "unsafe"). You've picked one thing my tools won't verify to focus on and now you're trying to pretend there's no verification at all for anything. Should I also should pick one thing that Rust won't verify and whine about Rust having no verification at all for anything?

I've already provided several reasons why "multi-target" is not the same as conditional complication. It's bad that you can't read.

I can read, your reasons are just wrong. Multitarget provides multiple implementations of a function, which are selected based on the configuration of the target. That is the definition of conditional compilation.

I see - you've artificially extended your private definition of "conditional compilation" to include cases where the programmer doesn't need define their conditions (e.g. "#define FOO") or specify most conditions (e.g. "#ifdef FOO").

Doesn't work when you don't just want a table as an optimization, like with processor-defined tables.

Yes it does. Note: What I mean here is that I'm too lazy to figure out all the very different things that you could've meant by "processor-defined tables" and show that it is possible for each possible case in the hope of getting lucky and covering whatever it was that you failed to describe adequately.

Statically declare the initial contents of your GDT using a function. I dare you to make that simpler and more clear than just using a table directly, and without requiring static constructors to verify that it's initialized (that *is* puke).

Do you actually think this is hard?

Code: Select all

GDT[] as const u64 = {
    0                         ;NULL entry
    createGDTentry(0, u32.max, CPL0CODE)
    createGDTentry(0, u32.max, CPL0DATA)
    ...
}

functiondef createGDTentry(base as u32, limit as u32, type as u8) (result as u64) {
   ...
}

A smart person can invent something complicated; but it takes a genius to describe something complicated in a way that can be understood. Only a complete moron would write sentences like "Speculative execution of queued hypotheticals provides concurrency as a semantically transparent implementation optimization." and expect others to read it. Perhaps you should've attempted to clearly describe whatever your point might be, rather than merely providing a link to a seemingly random piece of academic gibberish?

...or someone whose target audience knows those concepts already and wants to focus on what they actually did? Which, by the way, is right in the abstract: "Inclusions reify copy & paste edits into persistent relationships that propagate changes from their source into their destination." That way you could implement your file_buffer allocator, copy and paste it somewhere else for a different allocator, and then fixing a bug or adding a feature in one would (optionally) fix it in the other.

Instead of saying "reify copy & paste edits into persistent relationships that propagate changes from their source into their destination" why didn't they just say "when you're trying to customise a copy to be suitable for something completely different/unrelated, optionally trash the original"?


Cheers,

Brendan

[Rusky]

Code to allocate a file buffer and code to initialise a file buffer are very strongly related - when you create a file buffer you always do both (allocate then initialise).

But you don't always use the same combination of allocator and initializer, nor is every type's allocator different. Thus, there are cases that generics enable separation of concerns to a degree that it is still good.

Except you're using a deliberately biased comparison, and it's actually "most code is verified" vs. "most code is verified".

"most pointers verified for correct lifetime" vs "no pointers verified for correct lifetime"
Not to mention I was primarily comparing it to C, where it is pretty much "most code verified" vs "no code verified"

I see - you've artificially extended your private definition of "conditional compilation" to include cases where the programmer doesn't need define their conditions (e.g. "#define FOO") or specify most conditions (e.g. "#ifdef FOO").

Rust's conditional compilation specifies precisely the same information as multitarget (e.g. #[cfg(target_arch="x86")] as an attribute on the following item).

Do you actually think this is hard?

Good work. Now, do a table that you want to fill out with a for loop. How well does that work without macros?

Instead of saying "reify copy & paste edits into persistent relationships that propagate changes from their source into their destination" why didn't they just say "when you're trying to customise a copy to be suitable for something completely different/unrelated, optionally trash the original"?

Because that's not what they meant?

[Brendan]

Hi,

Code to allocate a file buffer and code to initialise a file buffer are very strongly related - when you create a file buffer you always do both (allocate then initialise).

But you don't always use the same combination of allocator and initializer, nor is every type's allocator different. Thus, there are cases that generics enable separation of concerns to a degree that it is still good.

And yet the minor advantages for a few trivial cases still don't justify all the disadvantages.

I see - you've artificially extended your private definition of "conditional compilation" to include cases where the programmer doesn't need define their conditions (e.g. "#define FOO") or specify most conditions (e.g. "#ifdef FOO").

Rust's conditional compilation specifies precisely the same information as multitarget (e.g. #[cfg(target_arch="x86")] as an attribute on the following item).

For 32-bit 80x86 alone, I have an old list of 43 different groups of instructions that may or may not be supported by the target CPU. This list only includes things that applications care about, and since I wrote it at least 5 more groups were created (SSE 4.1, SSE 4.2, AVX, transactional extensions, etc).

Now; imagine I write 20 different versions of a function for "32-bit 80x86 assembly" (where each version uses different combinations of "possibly not supported" instructions) and only tell the compiler that all of them are for 32-bit 80x86; and then the compiler decides which one of those 20 different versions are best for the target CPU. Is this how "#[cfg(target_arch="x86")]" works (e.g. compiler auto-selects from many "32-bit 80x86" variations without any hint from the programmer)? Is this how conditional compiling works in C?

Do you actually think this is hard?

Good work. Now, do a table that you want to fill out with a for loop. How well does that work without macros?

Can you give me a realistic scenario (e.g. an example of "looping macro table creation" from an existing project)?


Cheers,

Brendan

[Rusky]

And yet the minor advantages for a few trivial cases still don't justify all the disadvantages.

Maybe in the use cases you've thought about. Not true in the general case.

Now; imagine I write 20 different versions of a function for "32-bit 80x86 assembly" (where each version uses different combinations of "possibly not supported" instructions) and only tell the compiler that all of them are for 32-bit 80x86; and then the compiler decides which one of those 20 different versions are best for the target CPU. Is this how "#[cfg(target_arch="x86")]" works (e.g. compiler auto-selects from many "32-bit 80x86" variations without any hint from the programmer)? Is this how conditional compiling works in C?

I'm only going on what examples of multitarget you've given thus far. In any case, even with your extensions described here, it's still conditional compilation. The conditions are just more complicated- #[cfg] could just as well specify those variations (not sure if it does atm), but when you get to the point of writing a function in assembly 20 times you've reached my version of puke. Why are you writing assembly for many combinations of x86 features? Why are you, and not the compiler, translating your intent into the available machine instructions?

Can you give me a realistic scenario (e.g. an example of "looping macro table creation" from an existing project)?

I would do it with the IDT if the linker had better relocation support; I currently do it for ISR stubs with nasm macros (hah, do that with a function); depending on your design you could do it for a static page table or two based on the layout of the kernel image.

[Brendan]

Hi,

And yet the minor advantages for a few trivial cases still don't justify all the disadvantages.

Maybe in the use cases you've thought about. Not true in the general case.

I'm not sure that I've ever written a "general case"...

Now; imagine I write 20 different versions of a function for "32-bit 80x86 assembly" (where each version uses different combinations of "possibly not supported" instructions) and only tell the compiler that all of them are for 32-bit 80x86; and then the compiler decides which one of those 20 different versions are best for the target CPU. Is this how "#[cfg(target_arch="x86")]" works (e.g. compiler auto-selects from many "32-bit 80x86" variations without any hint from the programmer)? Is this how conditional compiling works in C?

I'm only going on what examples of multitarget you've given thus far. In any case, even with your extensions described here, it's still conditional compilation. The conditions are just more complicated- #[cfg] could just as well specify those variations (not sure if it does atm), but when you get to the point of writing a function in assembly 20 times you've reached my version of puke. Why are you writing assembly for many combinations of x86 features? Why are you, and not the compiler, translating your intent into the available machine instructions?

Assembly doesn't work like that (it is what you'd expect for higher level language source code though).

Can you give me a realistic scenario (e.g. an example of "looping macro table creation" from an existing project)?

I would do it with the IDT if the linker had better relocation support; I currently do it for ISR stubs with nasm macros (hah, do that with a function); depending on your design you could do it for a static page table or two based on the layout of the kernel image.

I think I see what you're getting at.

My language doesn't support assignment for arrays (e.g. you can't do "myArray[1234] as u32 = initArray()" or "firstArray[1234] as u32 = secondArray"). This means that to initialise an array with a "for each entry in array" loop you'd have to call an "initArray()" function in your executable's startup code. That "initArray()" function can't be a pure function (it must have side effects - writing to the array), so the compiler probably won't optimise it out. The end result is run-time array initialisation.

Of course I'm only worried about "version 1" at the moment; and I'm deliberately making the language and the compiler simple because I intend to discard it anyway (after using it to write a minimal OS, the IDE, and a native compiler). Eventually (after all that is done) I'll think about adding extensions to the original language (potentially including a way to do the equivalent of "myArray[1234] as const u32 = initArray()").


Cheers,

Brendan

[Rusky]

Macros can also be used for embedded domain-specific languages (typically called EDSLs), which can make your program significantly clearer by essentially creating a new scripting-ish language within the main one for a particular library. They can also be used to add new "language" constructs that would be overly verbose, repetitive, or executed at runtime without them. As long as you don't go overboard with them and make something unreadable for an outsider (this is helped in Rust by making it very clear where a macro!() is used, and by the culture of how often to use them defined by the standard library).

Generics and traits do have their place when used judiciously, as do well-designed conditional compilation and closures/lambdas. I notice you're not complaining about owned/borrowed or standard library tasks/vectors or recursive types...