HN Theater @HNTheaterMonth

It's sort of funny that linus torvalds actually talked about why that sort of iteration is better: https://youtu.be/o8NPllzkFhE?t=861

I think he puts it pretty well (although he them also goes on to say dumb little snippets like that really don't matter in the big picture). Essentially, by making a doubly indirect pointer you get to treat the first element exactly the same way you are going to treat every other element.

⬐ Mikhail_Edoshin

Exactly. And using such indirection often allows you to write a single search function and then use it to simply find and return the element, or find the spot and do something else: insert a new one, or replace or delete what you've found.

⬐ userbinator

However, Linus would object to hiding the true type of list (it's actually a pointer) --- as do I, since I was a little confused by that fragment at first, wondering what exactly was doubly indirected about it. It looks very different from the usual implementation of a "virtual head", which uses a single-indirect pointer only.

I'm reminded of Linus Torvald's interview at Ted [1] where he talks about programming "taste", and compares the following two code snippets:

  remove_list_entry(entry)
  {
      prev = NULL;
      walk = head;

      while (walk != entry) {
          prev = walk;
          walk = walk->next;
      }

      if (!prev)
          head = entry->next;
      else
          prev->next = entry->next;
  }

  remove_list_entry(entry)
  {
      indirect = &head;

      while ((*indirect) != entry)
          indirect = &(*indirect)->next;

      *indirect = entry->next;
  }

[1]: https://www.youtube.com/watch?v=o8NPllzkFhE

⬐ westoncb

This is an especially interesting comparison because while it does clearly exhibit the sort of elegance only achievable through the elimination of special cases, it's also a good demonstration of the tradeoffs one sometimes has to make for this purpose.

The second is significantly 'cleaner,' but with pretty bad readability [0]. The first version has excellent readability.

In practice, the way I'd evaluate the two is by looking at how much other code depends on (or at some point may depend on) the piece under consideration. If nothing else or only very little depends on the code, I'll opt for readability; if it's likely to be somewhat foundational and other stuff is going to grow on it, I'll opt for the more abstract, cleaner version, and document thoroughly.

[0] I'm guessing the readability isn't nearly as bad if the first example is using a common C idiom; I don't use C enough to know. My main criterion for judging readability is: how much does the structure of the code match the conception of the algorithm you're starting with. The conception here has to do with navigating links; the pointer stuff is incidental complexity.

⬐ im3w1l

To me the main readability problem of the first example is that it does the head check as the last step rather then first step. Meaning we have to consider "wait, when is this null again".

The main problem with the last one is that it's not immediately obvious what the "indirect" represents. When it clicks that it is "the pointer to potentially update", it's pretty easy to understand.

⬐ ummonk

The 2nd one would be significantly more readable with explicit typing (to make it clear that you're dealing with a pointer to pointer).

Though I think putting the head check at the beginning like you said will make the first example very reasonable (and relatively compact too).

  remove_list_entry(entry)
  {
      if (head == entry) {
          head = entry->next;
      } else {
          prev = head;
          while (prev->next != entry) {
              prev = prev->next;
          }
          prev->next = entry->next;
      }
  }

⬐ userbinator

There's a third alternative, which I've heard of as "virtual head", that removes the extra indirections in the loop and removal:

    while(p->next != entry)
     p = p->next;
    p->next = entry->next;

I've deliberately not shown the initialisation of p, because it's a bit tricky in C (but trivial in Asm); p is not initialised to the head, nor the address of the head, but to a "virtual" node centered around the head, such that p->next will initially access the head. If the next field is at the beginning of the structure, p does point to the head; else p points to a location before the head. It would be something like (char*)&head - offsetof(Node, next);

⬐ DerekL

You can get the same effect by using a “dummy” node. The dummy node has a next pointer, but no data, and the dummy node always exists at the front of the list. The list structure contains the dummy, instead of using a pointer to the front of the list.

    struct Node
    {
        struct Node* next;
    };

    struct DataNode
    {
        struct Node* next;
        struct Value value;
    };

    struct List
    {
        struct Node dummy;
        // You can also add length, etc.
    };

    // entry must be in list
    void remove_list_entry(struct List* list, struct Node* entry)
    {
        Node *prev = &list->dummy;

        while (prev->next != entry) {
            prev = prev->next;
            assert(prev != NULL);
        }
    
        prev->next = entry->next;
        free(entry);
    }

⬐ rovolo

For those curious how to create the "virtual head" in C:

    struct entry { int value; entry * next; };

    entry * head = NULL;
    void remove_entry(entry *target) {
        long offset = (long)&((entry*)0)->next;
        entry * curr = (entry*)((long)&head - offset);

        while (curr->next != target)
            curr = curr->next;

        curr->next = target->next;
    }

But I'm not sure how portable that is. It is portable if the next pointer is the first member of the struct though. From 6.7.2.1.13 in the C99 standard:

>A pointer to a structure object, suitably converted, points to its initial member

    struct entry { entry * next; int value; };
    ...
        // virtual entry where &(curr->next) = &head
        entry * curr = (entry*)&head;

Note that it's exactly the same logic as the grandparent since

    *curr = curr->next

    indirect = curr
    *indirect = *curr
    *indirect = curr->next
    indirect = &(curr->next)

But, I think that the virtual head entry is an easier mental model.

C99 standard: http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf

⬐ gumby

That first case is hideous (hope Linus agreed with me!) but does remind me of my favorite computer scientist joke:

===

The physicist is showing his friend the programmer a thermos.

"You see, you can put a hot drink inside, and then take it with you. It doesn't matter how cold it gets outside; when you pour the drink out it's still hot!"

The programmer is quite impressed.

The physicist continues, "Or you can put a cold drink inside, and then take it with you. It doesn't matter how hot it gets outside; when you pour the drink out it's still cold!"

Now the programmer is really dumbfounded.

He asks, "But how does it know?"

===

Unfortunately though I like the joke, I still see waaay too much code written by the programmer in the joke.

⬐ foota

Is the joke that the programmer interprets it as the drink waiting to pour out? Or?

⬐ jakeinspace

I interpret the story as though the programmer thinks about the world (in this case, the thermos) as actors, acting explicitly on their inputs. This type of thinking aligns with code full of conditional statements, such as checking the input liquid temperature rather than what the thermos does (just keeping the liquid at the same temperature).

⬐ jmmcd

To be more explicit, I see "how does it know?" as analogous to code like this:

    if (condition == True)
        return True
    else
        return False

⬐ taneq

It's a joke about type systems (as I read it). HotDrink and ColdDrink are both subclasses of Drink, and Thermos has a method "void fill(Drink * drink)" and a method "Drink * pour()". The programmer is asking how the calling code knows whether the Thermos is returning a HotDrink * or a ColdDrink * when pour() is called.

Of course, the answer is "the code should know beforehand what's in there". If someone hands you a thermos with no clue what's inside, then you either have to assume it could be hot OR cold (ie. just use the base Drink * pointer) or you have to check the temperature (ie. explicitly check the type of the return pointer using runtime type information or some kind of Variant-style wrapper.

⬐ travisjungroth

The joke is how does the thermos know whether to keep the drink hot or cold and that a programmer thinks that must be how the system works.

⬐ gumby

A non-programmer will just figure the programmer is a bozo (you could tell this joke with a physicist and a geologist, or any combination of <local-in-group-0> and <local-out-group-0>): that's simply how thermoses work.

But a thermos with a switch on the top to say "insert hot" or "insert cold" would be absurd. A thermos is simply a container _with no concept of temperature_, just isolation: it just maintains the state blindly; whether that state is hot or cold is managed by the "caller" who inserts and extracts the contents, inspecting them itself if it wants to know what had been put into it.

Yet I still see plenty of code that does have a variable to indicate what's inside, perhaps an enum {hot, cold} or worse a bool. Yuck -- you should simply store the thing and if you need to know its state you look at it. That variable is something to get out of sync; something you need to be careful to set and maintain, something at threat to a race condition or ill-timed interrupt. Bleagh. If your first language was FORTRAN, OK. Otherwise there is no excuse.

Sadly I see shit like that in pedagogical examples too, which is malpractice.

⬐ coliveira

Many modern languages require programmers to know exactly what is stored in any location. This is done in the name of "safety", but is just dumb. Code that needs to know the types of absolutely everything is simply slow and requires enormous repetition (or a system of boilerplate generation such as the STL).

⬐ warent

"I still see plenty of code that does have a variable to indicate what's inside, perhaps an enum {hot, cold} or worse a bool. Yuck -- you should simply store the thing and if you need to know its state you look at it."

Now I'm confused... How are those two things different? The variable indicating what's inside is going to be coming from the actual state itself, no?

It sounds like perhaps you're talking about some case where a developer has somehow copied a state and referred to the copy somewhere else. Or are you talking about a computed variable of some part of the state being a code smell?

⬐ AstralStorm

He's talking about explicit state, which can be a code smell when you can have equality efficient (or more) stateless solution.

The mind behind Linux | Linus Torvalds

https://www.youtube.com/watch?v=o8NPllzkFhE

⬐ cyberjunkie

I didn't expect to like it. But despite his slight nervousness, his simplicity and his brutal honesty and self-criticism resonated well with me.

Really good, no-nonsense talk. Good watch!

⬐ brudgers

A few months ago: https://news.ycombinator.com/item?id=11387424

Tesla is really great, but there exists a "take" on Edison that makes him also not so bad.

Here, listen to Linus talk about him a bit:

https://youtu.be/o8NPllzkFhE?t=17m24s

Linus: "I'm more of an Edison..." (TED2016, Feb. 2016)