10 ms·

Computer language inventors are torn between a voice whispering “use the language Luke” and and a more gravelly “let your feelings for the compiler grow, embrac

Computer language inventors are torn between a voice whispering “use the language Luke” and and a more gravelly “let your feelings for the compiler grow, embrace the syntax side.” I did a two-day sprint through Zig a month ago and really really liked it. It has some quirks that I would have done differently, but overall I think it’s pretty cool. I just need a good small scale project to try it out on now. My favorite example of the “use the language” ethos is the way Zig does generics. I have hated generics/templates in every language I use them in. They are the gordian knot of confusion that most languages in pursuit of some sort of unified type theory impale themselves on (yes, I’m mashing metaphors here). But Zig just uses its own self to define user types and generics come along for free. It resonates (with me at least) as a realization of what Gilda Bracha has shared about how to reify generics. [1] https://gbracha.blogspot.com/2018/10/reified-generics-search-for-cure.html?m=1 https://gbracha.blogspot.com/2018/10/reified-generics-search...

jstimpfle 5y ago
I've grown used to the idea that generics (data structure macros, C++ templates...) aren't that useful. If I find myself in a situation where I'm thinking of a solution that involves generics, I stop and ponder what is actually the essence of the repeated stuff. It rarely is on the syntactic level, often it runs deeper. Probably the commonalities can be distilled into a data structure. Simple example: Intrusive linking headers (e.g. Linux kernel list.h). While those can benefit from an optional very very thin generics layer on top, essentially the code for linking e.g. nodes in a tree should be the same regardless of the data structure where the headers are embedded. Getting this right simplifies the code but can also speed up compile times.
- pcwalton 5y ago
  How do you write a generic quicksort function without generics? There are two ways I know of: (1) throw type and memory safety out the window and use void pointers plus size/alignment like qsort(3) does; (2) require that users manually write an interface with a swap(int i, int j) function like Go before generics does. Both solutions are really bad.
  - joe_guy 5y ago
    Void pointers also add an unfortunate layer of dereferencing. In C# for example, generics are important to keep values on the stack instead of the heap, not only avoiding garbage collection but improving data locality.
    - pcwalton 5y ago
      Well, a modern optimizing compiler can get rid of the indirection if it inlines qsort() and then inlines the comparison function. Of course, it needs to be able to see the source of qsort() to do so (which might be a problem if it's dynamically linked).
      - joe_guy 5y ago
        If I'm understanding correctly, you're saying a compiler will optimize out "void*" to instead be the value put into it, so theres no pointer dereference to get to it? That's what I am talking about. I don't know much about modern C optimizations.
        jstimpfle 5y ago
        There isn't any pointer to optimize out really, I don't think - at the machine level, a pointer is a pointer is an integer number regardless of its type at the source code level. What can be measureable though is function call overhead - if you write a sort function that takes a function pointer and your sort function calls that, there is a lot of work for saving the local state, preparing all the arguments for the function, etc. That work can potentially be avoided if the compiler can inline the function call into (a copy of) your sort function.
        joe_guy 5y ago
        At the machine level there is absolutely a difference. one means your data is right here, the other means the data is elsewhere. That poor data locality can cause cache misses and always consumes extra cycles.
- ncmncm 5y ago
  Generics are the way that useful semantics can find their way into useful libraries. A collection of useful libraries is what is needed to make a language useful. This is why C++ usage is still growing fast: almost every new feature makes it possible to write more powerful libraries that get, thereby, easier to use.
  - jstimpfle 5y ago
    This is a blanket assertion. Why should useful semantics require generics? Why can't they come with simple fixed data structures? If you can provide a nice counterexample to the example that I gave, this would be more convincing. Absent the absolute necessity of generics to support essential semantics, I'm probably in favour of a simpler generics-less version. I don't see why "more powerful libraries" get automatically easier to use. It could often be the opposite. There is a tradition in some C++ subcultures where they try to cram in as many invariants as possible into types, concepts, templates, etc. at all costs. I tend to think that if all this heavy machinery is needed, the functionality might be too complicated from the start.
    - ncmncm 5y ago
      If you were writing a library, and a language feature made it possible to make your library easier to use safely, why would you not? You might as well say, "I don't see why a more expensive dinner has to be tastier." It is always easy to make libraries that are hard to use, in any language, but those do not become popular if there are better alternatives. We need generics because users have types that they need libraries to work with. Your own example, of an intrusively-linked list, illustrates this: without generics, you could not write a linked-list library component that would be usable for that. This is why C programs are crammed with so many custom one-off hash tables: You cannot code a useful hash table library in C. Libraries start simple, and accumulate your "heavy machinery" as they are made more useful and usable for their growing family of users. A library that lacks users does not.
      - jstimpfle 5y ago
        It's more like, "I don't see why a tastier dinner has to be more expensive". It's a tradeoff situation, and while I might be willing to buy a great $50+ meal from time to time instead of just a $20 one, I don't have any inclination to pay $1000 even if the meal is a tiny little bit better than the just-great one. It's a matter of tradeoffs. Library design is a balancing act. > We need generics because users have types that they need libraries to work with. This is right where I become sceptical. Most libraries shouldn't care for the user's types at all. They should expose their own types so you can work the library - not the other way around. Please provide an actual use case where the library has to "know" about the user's types (and please don't mention std::sort. It's as common an example as is "Dog :: Animal" examples to argue for class inheritance, and is just as irrelevant). > Your own example, of an intrusively-linked list, illustrates this: without generics, you could not write a linked-list library component that would be usable for that. As I mentioned, linked list can tangentially benefit from a very very thing generics layer on top of a fixed data structure implementation. The layer does nothing more than "instanciate" the types, but there is no code generated. But then again, the added convenience / safety is minimal, I once wrote a C++ implementation that I was quite happy with, and never used it. > This is why C programs are crammed with so many custom one-off hash tables There are probably not huge issues with a design like "HashTable ht = { .hash = &foo_key_hash, .equals = &foo_key_equals }" (if quick results are what you're after), but yes it is nice to have a few lines of type-safe wrap generated over some generic container interface. An alternative reason why you'll find a good amount of custom hashtables in C code bases is, I suppose, that there are a lot of different ways to implement hash tables. Also writing a little code here might not be so bad. I've had 1 use case for a "hash" table in 2021 (glyph hash table for a new iteration of my font rendering code) and I've gotten away without even implementing it - the for-loop I've written has never shown up in any performance profile. Considering that container data structures are probably the highest profile application for generics, I'm still not convinced that generics are needed in a systems programming language...
- tsimionescu 5y ago
  > the code for linking e.g. nodes in a tree should be the same regardless of the data structure where the headers are embedded. Why should that be so? It's particularly NOT true for one of the simplest and most efficient data structures in any program: the array. The code that needs to work with an array needs to know exactly the size of each element of the array, so you basically can't have an efficient language that doesn't support generic arrays. Haskell maybe sometimes gets by with a very smart compiler and heavy use of laziness, but even C has support for generic arrays.
  - deleted 5y ago
    [deleted]
  - jstimpfle 5y ago
    You can totally make array iteration generic, just pass the element size. Not saying it is necessarily a good idea. I agree that there are cases where the "there should be a single central piece of code" argument is not a strong one, because the generic code is so simple that it should be inlined into the usage code. Arrays iteration is one example - but note that for example sorting code is, while the sorting algorithm might be generic, more than just generic array iteration. Doubly linked lists already profit from shared code in some ways, and definitely I'd find it a bad idea to replicate for example tree mutation code (RB tree or similar) for each node type. Embedding the header structure and keeping the links just between these embedded headers, to be able to reuse a common (compiled) piece of code is a very good idea here IMO.
sekao 5y ago
The way zig does generics is brilliant, and made me think "this is how every language should do it". One of those things that seems obvious in retrospect: just pass the types as normal parameters, and for generic data structures just represent their type as a function that receives those parameters and returns a new type. Man that's just beautiful. Only downside is, i suppose the types can never be inferred so they always need to be explicitly passed. But being explicit seems to be their thing anyway.
- naasking 5y ago
  Zig's approach isn't unique, it's basically what dependently typed languages do. The problem is that if you don't do it right, it's too expressive and the type checker can loop forever. Of course, this is also true of C++ templates since they're Turing complete, but it's not true of generics in most languages.
  - dnautics 5y ago
    > the type checker can loop forever Oversimplifying: Zig anyways gives you "compiler branching tokens" so your type system can't loop forever, if I'm not mistaken
    - uh_uh 5y ago
      Kind of how Ethereum uses "gas" to make sure that bad/lazy actors won't waste CPU cycles when running smart contracts.
      - dnautics 5y ago
        sure, but you aren't going to run out of compiler tokens unless you are trying to do something really crazy, like generate a precompiled table of prime numbers, as I have done. And I don't think you use them up in general, just when your compiler is taking certain branching operations (i don't actually know what the rules are)... I believe you can have a long program that consumes as many tokens as a short program, if their typesystems are the same and you don't ever use compile-time branches in the functions you're writing.
skybrian 5y ago
It looks very nice and I look forward to using it. A downside for package authors (once Zig gets to the point of having a package ecosystem) will be that syntax errors are checked only with the comptime parameters that are actually used at call sites. To maintain compatibility, authors of public APIs will need tests with commonly-used comptime parameters. It seems like a good way to avoid lots of type-level complexity in the language, though.

jstimpfle 5y ago

I've grown used to the idea that generics (data structure macros, C++ templates...) aren't that useful. If I find myself in a situation where I'm thinking of a solution that involves generics, I stop and ponder what is actually the essence of the repeated stuff. It rarely is on the syntactic level, often it runs deeper. Probably the commonalities can be distilled into a data structure. Simple example: Intrusive linking headers (e.g. Linux kernel list.h). While those can benefit from an optional very very thin generics layer on top, essentially the code for linking e.g. nodes in a tree should be the same regardless of the data structure where the headers are embedded. Getting this right simplifies the code but can also speed up compile times.

pcwalton 5y ago
How do you write a generic quicksort function without generics? There are two ways I know of: (1) throw type and memory safety out the window and use void pointers plus size/alignment like qsort(3) does; (2) require that users manually write an interface with a swap(int i, int j) function like Go before generics does. Both solutions are really bad.
- joe_guy 5y ago
  Void pointers also add an unfortunate layer of dereferencing. In C# for example, generics are important to keep values on the stack instead of the heap, not only avoiding garbage collection but improving data locality.
  - pcwalton 5y ago
    Well, a modern optimizing compiler can get rid of the indirection if it inlines qsort() and then inlines the comparison function. Of course, it needs to be able to see the source of qsort() to do so (which might be a problem if it's dynamically linked).
    - joe_guy 5y ago
      If I'm understanding correctly, you're saying a compiler will optimize out "void*" to instead be the value put into it, so theres no pointer dereference to get to it? That's what I am talking about. I don't know much about modern C optimizations.
      - jstimpfle 5y ago
        There isn't any pointer to optimize out really, I don't think - at the machine level, a pointer is a pointer is an integer number regardless of its type at the source code level. What can be measureable though is function call overhead - if you write a sort function that takes a function pointer and your sort function calls that, there is a lot of work for saving the local state, preparing all the arguments for the function, etc. That work can potentially be avoided if the compiler can inline the function call into (a copy of) your sort function.
        joe_guy 5y ago
        At the machine level there is absolutely a difference. one means your data is right here, the other means the data is elsewhere. That poor data locality can cause cache misses and always consumes extra cycles.
ncmncm 5y ago
Generics are the way that useful semantics can find their way into useful libraries. A collection of useful libraries is what is needed to make a language useful. This is why C++ usage is still growing fast: almost every new feature makes it possible to write more powerful libraries that get, thereby, easier to use.
- jstimpfle 5y ago
  This is a blanket assertion. Why should useful semantics require generics? Why can't they come with simple fixed data structures? If you can provide a nice counterexample to the example that I gave, this would be more convincing. Absent the absolute necessity of generics to support essential semantics, I'm probably in favour of a simpler generics-less version. I don't see why "more powerful libraries" get automatically easier to use. It could often be the opposite. There is a tradition in some C++ subcultures where they try to cram in as many invariants as possible into types, concepts, templates, etc. at all costs. I tend to think that if all this heavy machinery is needed, the functionality might be too complicated from the start.
  - ncmncm 5y ago
    If you were writing a library, and a language feature made it possible to make your library easier to use safely, why would you not? You might as well say, "I don't see why a more expensive dinner has to be tastier." It is always easy to make libraries that are hard to use, in any language, but those do not become popular if there are better alternatives. We need generics because users have types that they need libraries to work with. Your own example, of an intrusively-linked list, illustrates this: without generics, you could not write a linked-list library component that would be usable for that. This is why C programs are crammed with so many custom one-off hash tables: You cannot code a useful hash table library in C. Libraries start simple, and accumulate your "heavy machinery" as they are made more useful and usable for their growing family of users. A library that lacks users does not.
    - jstimpfle 5y ago
      It's more like, "I don't see why a tastier dinner has to be more expensive". It's a tradeoff situation, and while I might be willing to buy a great $50+ meal from time to time instead of just a $20 one, I don't have any inclination to pay $1000 even if the meal is a tiny little bit better than the just-great one. It's a matter of tradeoffs. Library design is a balancing act. > We need generics because users have types that they need libraries to work with. This is right where I become sceptical. Most libraries shouldn't care for the user's types at all. They should expose their own types so you can work the library - not the other way around. Please provide an actual use case where the library has to "know" about the user's types (and please don't mention std::sort. It's as common an example as is "Dog :: Animal" examples to argue for class inheritance, and is just as irrelevant). > Your own example, of an intrusively-linked list, illustrates this: without generics, you could not write a linked-list library component that would be usable for that. As I mentioned, linked list can tangentially benefit from a very very thing generics layer on top of a fixed data structure implementation. The layer does nothing more than "instanciate" the types, but there is no code generated. But then again, the added convenience / safety is minimal, I once wrote a C++ implementation that I was quite happy with, and never used it. > This is why C programs are crammed with so many custom one-off hash tables There are probably not huge issues with a design like "HashTable ht = { .hash = &foo_key_hash, .equals = &foo_key_equals }" (if quick results are what you're after), but yes it is nice to have a few lines of type-safe wrap generated over some generic container interface. An alternative reason why you'll find a good amount of custom hashtables in C code bases is, I suppose, that there are a lot of different ways to implement hash tables. Also writing a little code here might not be so bad. I've had 1 use case for a "hash" table in 2021 (glyph hash table for a new iteration of my font rendering code) and I've gotten away without even implementing it - the for-loop I've written has never shown up in any performance profile. Considering that container data structures are probably the highest profile application for generics, I'm still not convinced that generics are needed in a systems programming language...
tsimionescu 5y ago
> the code for linking e.g. nodes in a tree should be the same regardless of the data structure where the headers are embedded. Why should that be so? It's particularly NOT true for one of the simplest and most efficient data structures in any program: the array. The code that needs to work with an array needs to know exactly the size of each element of the array, so you basically can't have an efficient language that doesn't support generic arrays. Haskell maybe sometimes gets by with a very smart compiler and heavy use of laziness, but even C has support for generic arrays.
- deleted 5y ago
  [deleted]
- jstimpfle 5y ago
  You can totally make array iteration generic, just pass the element size. Not saying it is necessarily a good idea. I agree that there are cases where the "there should be a single central piece of code" argument is not a strong one, because the generic code is so simple that it should be inlined into the usage code. Arrays iteration is one example - but note that for example sorting code is, while the sorting algorithm might be generic, more than just generic array iteration. Doubly linked lists already profit from shared code in some ways, and definitely I'd find it a bad idea to replicate for example tree mutation code (RB tree or similar) for each node type. Embedding the header structure and keeping the links just between these embedded headers, to be able to reuse a common (compiled) piece of code is a very good idea here IMO.

sekao 5y ago

The way zig does generics is brilliant, and made me think "this is how every language should do it". One of those things that seems obvious in retrospect: just pass the types as normal parameters, and for generic data structures just represent their type as a function that receives those parameters and returns a new type. Man that's just beautiful. Only downside is, i suppose the types can never be inferred so they always need to be explicitly passed. But being explicit seems to be their thing anyway.

naasking 5y ago
Zig's approach isn't unique, it's basically what dependently typed languages do. The problem is that if you don't do it right, it's too expressive and the type checker can loop forever. Of course, this is also true of C++ templates since they're Turing complete, but it's not true of generics in most languages.
- dnautics 5y ago
  > the type checker can loop forever Oversimplifying: Zig anyways gives you "compiler branching tokens" so your type system can't loop forever, if I'm not mistaken
  - uh_uh 5y ago
    Kind of how Ethereum uses "gas" to make sure that bad/lazy actors won't waste CPU cycles when running smart contracts.
    - dnautics 5y ago
      sure, but you aren't going to run out of compiler tokens unless you are trying to do something really crazy, like generate a precompiled table of prime numbers, as I have done. And I don't think you use them up in general, just when your compiler is taking certain branching operations (i don't actually know what the rules are)... I believe you can have a long program that consumes as many tokens as a short program, if their typesystems are the same and you don't ever use compile-time branches in the functions you're writing.

skybrian 5y ago

It looks very nice and I look forward to using it. A downside for package authors (once Zig gets to the point of having a package ecosystem) will be that syntax errors are checked only with the comptime parameters that are actually used at call sites. To maintain compatibility, authors of public APIs will need tests with commonly-used comptime parameters. It seems like a good way to avoid lots of type-level complexity in the language, though.