There’s a famous site called Project Euler, where users write code to solve mathy problems such as “In a modified version of the board game Monopoly, on what three squares is a player most likely to land?” My former programming-contest coach advocated against using it to practice, because “It’s not really programming, and it’s not really math.”
I’m not going to begrudge anyone if they want to do it, but I took a look at Project Euler after seeing so many people do it, and was uninterested. Maybe because I did a lot of discrete math in high school or something …
Likewise I own “Elements of Programming” and also found little use for it. It’s not math and it’s not programming – great description.
However I definitely respect the STL and C++, and I happen to be doing more template programming than I’ve done in 20+ years right now – to write a pretty type safe garbage collector! This is the kind of thing where C++ really shines – where you need low level control, and you also want types and abstraction.
To me it looks like C++ and Rust are the only languages where you can do such a thing, and C++ came 25-30 years earlier. Alexandrescu proposed that “writing a garbage collector” in a language is a critical test for whether a language is a “systems language” or not, and there is some truth to that.
To me it looks like C++ and Rust are the only languages where you can do such a thing, and C++ came 25-30 years earlier. Alexandrescu proposed that “writing a garbage collector” in a language is a critical test for whether a language is a “systems language” or not, and there is some truth to that.
I’d add Ada and Common Lisp to the list, also.
In any case, I agree with you and the article author about “Elements of Programming.” I skimmed through it several years ago, and didn’t understand what the author was going for. There’s been a strong tie between math and computer science going back to before electronic computers even existed, but it seemed the author ignored all of it and came up with his own version using C++ template meta-programming to illustrate everything.
Ada has generics, classes, and equivalents for the low-level functionality of C++. Address arithmetic, for example, can be done with System.Address.
There is some low-level functionality that is absent from C or C++; you can specify the bit-order within bit fields.
Some of Stepanov’s early work on generic programming was done with Ada.
Edited to add the following text.
Henry Baker wrote a 1993 paper on an Ada 83 garbage collector.
History of T discusses a garbage collector written in Pre-Scheme, a Scheme subset.
Thanks, although I probably didn’t make clear what I was talking about. I’m not just talking about low-level control in high level languages, although that is relevant – I’m talking static types and metaprogramming and how they help you write a garbage collector.
I should have linked this previous comment where I linked to a paper by the authors/inventors of the Immix garbage collection algorithm. They implemented Immix and Rust and (surprisingly) found that its type system actually helped.
This is kind of a paradox because the essential nature of the garbage collector is to enforce a homogeneous view of memory on top of a heterogeneously-typed heap.
If you want a quick demo, look at figure 1. It’s an abstraction over a pointer.
I am finding the same thing in C++. I can implement an abstract type with storage that is a single pointer, and that is extremely helpful. v8 and SpiderMonkey do the same thing with Rooted<T>, Handle<T>, etc.
Apparently Rust goes even further, and you can even (paradoxically) use lifetimes to help with a GC, although I don’t have experience with that.
I looked at the Cheney algorithm in es shell and in femtolisp in C, and if you compare it with mine in C++, it looks VERY different. For one, you don’t have to push and pop variables to maintain precise stack roots – I just use a pointer-like type Local<T>. (I don’t think Ada can do this – looks like it has basic C-style address arithmetic) Again this is what all the JS VMs that we use do.
Key point: the layout depends on compiler flags, so you can’t just generate field bitmasks. Introspection with the compiler is useful!
I should probably write a blog post like “C++ features that help you write a garbage collector”:
pointer-like types, and templates
inheritance (e.g. from Obj, for object headers) – although I needed to use C-style macros for a different reason
more precise casting
offsetof and constexpr
Though the part in the History of T and locality of copying collection is pretty interesting (BFS vs DFS)! I’ll have to look into that more as it’s an issue I’ve been wonderiing about.
I’m not sure what you want a citation for? Are you asking for garbage collectors written in Ada and Common Lisp?
I don’t know of any off hand, but my intention was to point out that Ada and Common Lisp are two other languages offering high level abstractions but also low level control. I suppose I should have quoted the sentence above that paragraph.
Wow, I like this part:
I’m not going to begrudge anyone if they want to do it, but I took a look at Project Euler after seeing so many people do it, and was uninterested. Maybe because I did a lot of discrete math in high school or something …
Likewise I own “Elements of Programming” and also found little use for it. It’s not math and it’s not programming – great description.
However I definitely respect the STL and C++, and I happen to be doing more template programming than I’ve done in 20+ years right now – to write a pretty type safe garbage collector! This is the kind of thing where C++ really shines – where you need low level control, and you also want types and abstraction.
To me it looks like C++ and Rust are the only languages where you can do such a thing, and C++ came 25-30 years earlier. Alexandrescu proposed that “writing a garbage collector” in a language is a critical test for whether a language is a “systems language” or not, and there is some truth to that.
I’d add Ada and Common Lisp to the list, also.
In any case, I agree with you and the article author about “Elements of Programming.” I skimmed through it several years ago, and didn’t understand what the author was going for. There’s been a strong tie between math and computer science going back to before electronic computers even existed, but it seemed the author ignored all of it and came up with his own version using C++ template meta-programming to illustrate everything.
Citations?
Ada has generics, classes, and equivalents for the low-level functionality of C++.
Address arithmetic, for example, can be done with System.Address.
There is some low-level functionality that is absent from C or C++; you can specify the bit-order within bit fields. Some of Stepanov’s early work on generic programming was done with Ada.
Edited to add the following text.
Henry Baker wrote a 1993 paper on an Ada 83 garbage collector.
History of T discusses a garbage collector written in Pre-Scheme, a Scheme subset.
Edited again to add a Lisp example.
How to define new intrinsics in SBCL is an example of low-level support in a recent Lisp.
Thanks, although I probably didn’t make clear what I was talking about. I’m not just talking about low-level control in high level languages, although that is relevant – I’m talking static types and metaprogramming and how they help you write a garbage collector.
I should have linked this previous comment where I linked to a paper by the authors/inventors of the Immix garbage collection algorithm. They implemented Immix and Rust and (surprisingly) found that its type system actually helped.
https://lobste.rs/s/9duro8/rune_programming_language#c_2f90p3
This is kind of a paradox because the essential nature of the garbage collector is to enforce a homogeneous view of memory on top of a heterogeneously-typed heap.
If you want a quick demo, look at figure 1. It’s an abstraction over a pointer.
I am finding the same thing in C++. I can implement an abstract type with storage that is a single pointer, and that is extremely helpful. v8 and SpiderMonkey do the same thing with
Rooted<T>,Handle<T>, etc.https://old.reddit.com/r/ProgrammingLanguages/comments/ivyaw8/clawing_our_way_back_to_precision_spidermonkey/
Apparently Rust goes even further, and you can even (paradoxically) use lifetimes to help with a GC, although I don’t have experience with that.
I looked at the Cheney algorithm in es shell and in femtolisp in C, and if you compare it with mine in C++, it looks VERY different. For one, you don’t have to push and pop variables to maintain precise stack roots – I just use a pointer-like type
Local<T>. (I don’t think Ada can do this – looks like it has basic C-style address arithmetic) Again this is what all the JS VMs that we use do.And I also like these types:
https://github.com/oilshell/oil/blob/master/mycpp/gc_heap.cc#L13
You can sorta do that in C, although the inheritance helps too. The explicit
reinterpret_castvs.static_castin C++ helps a lot too.Cool trick I just learned with
offsetofandconstexpr: https://old.reddit.com/r/cpp_questions/comments/iz84pb/how_to_portably_calculate_field_offset_bitmasks/Key point: the layout depends on compiler flags, so you can’t just generate field bitmasks. Introspection with the compiler is useful!
I should probably write a blog post like “C++ features that help you write a garbage collector”:
Though the part in the History of T and locality of copying collection is pretty interesting (BFS vs DFS)! I’ll have to look into that more as it’s an issue I’ve been wonderiing about.
I’m not sure what you want a citation for? Are you asking for garbage collectors written in Ada and Common Lisp?
I don’t know of any off hand, but my intention was to point out that Ada and Common Lisp are two other languages offering high level abstractions but also low level control. I suppose I should have quoted the sentence above that paragraph.
See my sibling response: https://lobste.rs/s/bqnhbo/book_review_elements_programmnig#c_l7fnoh
The Rust paper is basically what I was talking about; the same is true in C++ but not other languages