Crafting Interpreters: Superclasses | Hacker News Reader

Crafting Interpreters: Superclasses

craftinginterpreters.com

253 pointsazhenley46 comments

> Now onto the new instruction:

Adding a special VM instruction for such operations as inheriting from a class is a strikingly bad design decision.

You want to minimize the proliferation of VM instructions as much as possible.

A rule of thumb is: is it unreasonable to compile into a function call? Or else, is it likely to be heavily used in inner loops, requiring the fastest possible dispatch? If no, don't add an instruction for it. Compile it into an ordinary call of a run-time support function.

You're not going to inherit from a class hundreds of millions of times in some hot loop where the application spends 80% of its time; and if someone contrives such a thing, they don't necessarily deserve the language level support for cutting their run-time down.

It depends on the language, but in the Smalltalk vm I'm writing, super class methods get called a lot it seems. More than enough to have their own bytecode.

> You want to minimize the proliferation of VM instructions as much as possible.

I guess that seems like half the trade off to me, or else VMs would all be OISCs. What you really want to do is to approximate Huffman encoding in your ISA, balancing that with ease of parsing (so bytes generally rather than bits).

But this OP_INHERIT instruction isn't for calling methods; it's just for setting up the inheritance relationship.

The opcode OP_INHERIT takes two classes as parameter on the stack so this is equivalent to do a function/method calls with the class and the super class and let the function do the magic of filling the vtable, etc.

This is a good point. One of the things I have to balance with the book is teaching the optimal way to do something without dragging through reader through a large amount of verbose, grungy code. So sometimes (but not too often) I take a simpler approach even if it's not the best one.

With this VM, we have plenty of opcode space left, so it's natural to just add another instruction for inheritance, even if it does mean that the bytecode dispatch loop doesn't fit in the instruction cache quite as well.

I'll think about this some more. I'm very hesitant to make sweeping changes to the chapter (I want nothing more in life than for the book to be done), but this would be a good place to teach readers this fundamental technique of compiling language constructs to runtime function calls.

Probably sufficient to add it as a chapter footnote/challenge like you did with flexible array members for the string implementation. Maybe with a pointer to an example if you have time to find one.

This. Compromises are fine: real-world solutions make them all the time. What’s valuable to readers is displaying the reasoning behind them.

Hi Bob! I just want to tell you that I've just started reading your book and I'm enjoying it very much.

Maybe you could add a design note in the chapter with the mentioned content?

Keep it up!

> Maybe you could add a design note in the chapter with the mentioned content?

Great idea!

Made a note of it: https://github.com/munificent/craftinginterpreters/issues/62...

> technique of compiling language constructs to runtime function calls.

That can be as basic as generating a function call AST node directly from a construct, or doing a node-to-node transformation.

The compiler doesn't see anything but a function call node (though any source code tracking info and whatnot still references the original construct).

If you're doing things with the AST other than just generating code, you may want to have a node for that original construct. (For instance, feeding cross-referencing info to a language server or whatever.)

The implementation is actually a single-pass compiler so it goes from token stream straight to bytecode generation with no intermediate AST or other IR in between. Even so, it would be straightforward to emit the bytecode instruction sequence for a call to a special runtime function.

Well, the thing about this approach, I think, is that your code itself essentially becomes something like an image of your syntax tree (a la recursive descent parsing). That's fine if you want a sort of "toy" interpreter or interpreter that doesn't care about speed much.

But you're also using bytecode, which involves more caring about speed, so you've got a bit of a mismatch - as your code tries to match the multiple layers you're skipping, your code will get more complicated or your VM gets more arbitrary, so of the situation you have here.

> or interpreter that doesn't care about speed much.

This is the same approach taken by Lua and many of the original Pascal compilers, which had to run on very slow hardware, so there's pretty good precedent that you can get adequate performance.

> But you're also using bytecode, which involves more caring about speed, so you've got a bit of a mismatch

I wouldn't describe it as a mismatch as much as it is a trade-off. Because the compiler only has a peephole view into the source when it needs to generate code, many optimizations are off the table. However, because we have full control over the instruction set, we can sometimes tweak the bytecode format in order to more naturally align with the compiler.

In return for not needing an intermediate representation or AST, we get a much simpler compiler, especially in C where you have to worry about memory management.

It is reasonable to say this is a tradeoff. However, one of the costs is having the VM structure depend on the language structure, which kind of a software engineering no-no. But yes, tradeoffs always happen.

> which kind of a software engineering no-no.

Optimization along any axis (code size, simplicity, compile-time performance, runtime performance, memory size, etc.) always involves some level of violating software engineering norms.

One way to think of software engineering is that it's the practice of optimizing long-term developer velocity. Any practice that optimizes other factors generally does so at the expense of that. That's OK. Meta-software engineering is about knowing when long-term maintainability is the right factor to optimize for. :)

That is really only a political no-no. The issue is that if your VM takes off in popularity, some people get upset that it's a poor fit for their favorite language.

Technically, it's perfectly fine for a VM to be designed so that the semantic gap is small between it and the intended language family.

Languages evolve, and changes need to be made.

Many languages didn't support "arrow functions" AKA lambdas until fairly recently. Seeing how one would go about making large changes to the language is a good lesson to learn. One could argue that we should have known superclasses were going to be supported from the beginning, and I'd agree, hindsight is always 20:20.

Off-point. Lambdas are different, in the sense that with such functions you 1) need to think about the closure of the function 2) might need to reconsider what part of memory will be executable (you certainly don't want an executable heap). The change here is in the other direction - you remove a feature that is easily swapped with a builtin, which is implemented in terms of other already existing language features.

> Adding a special VM instruction for such operations as inheriting from a class is a strikingly bad design decision

I am struggling how this can be seen as a runtime instruction anyway - surely inheritance is a compile time semantic?

For statically-typed languages, yes, but many dynamically-typed languages allow class definition and inheritance at run-time. Read the classes and instances chapter to see that this interpreter indeed does.

Completely agree. Instruction sets are very inflexible. If a language has a new keyword or instruction, developers will spend a lot of time avoiding it at all costs and hiding it behind methods.

The new keyword requires a concrete class to instantiate. Abstractions such as interfaces cannot be used with new. The resulting instruction will directly reference that concrete class which makes it part of the software's binary interface. Its behavior can't be overridden: a constructor will always return an instance of the constructed class, never a subtype.

The factory design pattern was invented to solve these problems. Replacing new with normal method calls pretty much takes care of everything. The author himself has written about this on his blog:

http://journal.stuffwithstuff.com/2010/09/18/futureproofing-...

http://journal.stuffwithstuff.com/2010/12/14/the-trouble-wit...

Sharp edged words. High performance code only exists when you've developed experience from building low performance code.

I think a few explanatory notes and discussion of suitable alternative approaches is warranted but not a complete rewrite because its somehow wrong.

Each VM has its own quirks which produce their own opportunities. Why would this one be any different? Especially as a teaching instrument where it has to be simpler / clearer than a production codebase?

For those following this series, Bob's update email said: "This is the second to last chapter in the book, and the last chapter that adds new functionality."

As stated in the text, for `super` calls to work within a method, it’s necessary to know the class on which the method is defined. Here, that’s easy - it’s the class that the method is lexically defined within.

This is more difficult in a language which allows methods to be added to classes dynamically. IIRC both Python and JavaScript are in this category, but still calculate `super` lexically. Therefore, if a method is copied from one class to another, `super` within that method may refer to the wrong class.

Interesting point. I'd have to look at my implementation to be sure, but Lox will also have this quirk, won't it? You can freely assign values, (as I recall) including functions, to a property on an instance.

Or does it only come up when a method is added to the class?

> Lox will also have this quirk, won't it?

Possibly - I’m not sure about the details of method lookup in Lox. Does `this` even work correctly when a method is assigned to an instance?

If you store a function or reference to a method in a field on an instance in Lox, the function will remember its original `this` binding. That's what Python, C#, Ruby, etc. do and is generally what you want. It's not what JS does because JS doesn't really know what a "method" is, or at least didn't before classes were added.

Is it possible that there isn't a `this` binding? Does Lox allow access to "unbound" methods directly from a class, or are methods accessible only via instances?

Methods are only accessible from instances, so `this` is always meaningfully bound. If you try to use `this` outside of a class body, it's a static error.

OK, that solves the problem. The issue with unbound methods in Python is that they don’t yet have a value for `this`, but they do have a fixed value for `super`.

Lox makes a distinction between functions and methods, so you won't run into this problem. This is unlike JavaScript, but like most other object-oriented languages.

If you take a function (which may be a reference to a method) and store it in a field on some instance, the function remembers its original bindings to "this" and "super", which is generally what you want and expect.

Lox doesn't allow you to mutate a class by adding new methods to it.

> Therefore, if a method is copied from one class to another, `super` within that method may refer to the wrong class.

No, super() checks that "self" is an instance of the given class.

So if you take a method defined in a class hierarchy "A -> B", and attach it to an instance of "C" (i.e. c.foo = B.foo) and call it like "c.foo(c)", which you have to do, since you didn't invoke the descriptor protocol to bind the method, you will get a type error, because c is not an instance of A/B. That is also true if you attach the method to the class (C.foo = B.foo); you can call it like a method, but super() still checks the type and will complain.

Also, if you take a bound method and attach it to another object (i.e. c.foo = b.foo), it is already bound and you can't pass a "self" different from the object it's bound to. E.g. if you are passing around a callback that's a method.

Note how Class.method is just a function, while instance.method is a bound method. That's due to the descriptor protocol of functions (__get__/__set__).

> That is also true if you attach the method to the class (C.foo = B.foo); you can call it like a method, but super() still checks the type and will complain.

You're right. Here's some example Python code:

    >>> class A:
    ...     def foo(self):
    ...             print('A.foo')
    >>> class B(A):
    ...     def foo(self):
    ...             super().foo()
    ...             print('B.foo')
    >>> b = B()
    >>> b.foo()
    A.foo
    B.foo

    >>> class C:
    ...     def foo(self):
    ...             print('C.foo')
    >>> class D(C):
    ...     def foo(self):
    ...             super().foo()
    ...             print('D.foo')
    >>> d = D()
    >>> d.foo()
    C.foo
    D.foo

Now, if I do `D.foo = B.foo` and call `d.foo()`, I do indeed get a "TypeError: super(type, obj): obj must be an instance or subtype of type". That's better than getting `A.foo B.foo`, as happens in JavaScript.

However, if `super` were truly dynamic, I would have expected to get `C.foo B.foo`.

IIRC super() is actually syntactic sugar for super(ClassTheDefIsFoundIn, nameOfFirstArgument), because there is no way I can think of to implement that as a function at runtime.

Yes, I think that’s right. However, I think it would work better if classTheDefIsFoundIn were resolved dynamically rather than lexically. Perhaps it would have been possible to do this by modifying the descriptor protocol?

I'm not sure that's possible, because you could only work with type(self), and that breaks MRO traversal. (A chain of super().x() calls in a hierarchy like A->B->C would always call the first parent class, because it has no way to tell >where< in the hierarchy it is. That's the reason why the class argument is required.)

I think that would need an entirely differently designed mechanism and can't be bolted on.

IIRC in JavaScript every method of a class has a [[HomeObject]] property in it, referencing the class it was defined in to solve this problem

can someone weigh in on this vs thorsten ball's series of books? to my untrained eye they look fairly similar (at least thorsten's first book) but I'm not sure.

edit: i should say i'm wondering which is more appropriate for me. my experience is that i took a PL class during my MS where we implemented a small recursive descent parser for a language (and the concomitant logic for evaluating the language). i'm interested in getting better at writing languages.

Crafting Interpreters is in two parts. AFAIK each part corresponds to one of Thorsten Ball’s two books.

add on to what the other reply said, the second part is in pure c which means it likely gets far more gritty details as this book has to implement it's own hash map for storing the symbol table, since c doesn't have a huge standard library the way go does (note part 1 is in Java when he's building the AST runner instead of a bytecode compiler)

I think the books are complementary. There is definitely a different style in how they present info. I like both.

Hey! Thorsten Ball here. I'd say: yes, they're similar, but still two different perspectives on the same subject. (I actually recounted elsewhere [0] how Bob convinced me, 4 years ago now, that it's valuable to have multiple teachers of the same subject.)

So if you're into the topic I think you can get something out of my books ([1], [2]) even if you've read Bob's book before. And if you read mine, then Bob's book will also show you something new.

I'm currently working through Bob's book myself (chapter 23) and I'm enjoying it immensely: the language, Lox, shares a lot of things with the one in my books (Monkey), like first-class functions and closures, but also has classes which Monkey does not. So now I can read Bob's book and on one hand think "Ohh, I wonder how he does _that_" and on the other hand "classes! let's see how that works."

My books also use Go exclusively and Bob's uses Java and C. I enjoyed using IntelliJ and writing Java for the first time in my life a lot and was always a fan of C, so that was also really interesting, to see how the ideas translate across three languages.

[0]: https://lobste.rs/s/43h7rz/crafting_interpreters_handbook_fo... [1]: https://interpreterbook.com [2]: https://compilerbook.com

Very good, as always. I spotted a couple of typos: “inheritred”, “get out hands”.

Thanks, I'll fix those.

Reply on news.ycombinator.com