[Apr 14 Discussion] An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes

[charles-rs]

Thread for discussion of paper here

[ayakayorihiro]

Overall I think this is a very interesting paper on the implementation of a very interesting language! SELF gives the programmer a lot of freedom and power via the lack of classes and types, and computation using message passing. This poses various challenges to the implementation, which the authors address via using maps for object representation, and devising techniques like dynamic customized compilation, type prediction, message inlining, and more. It would be interesting to know what specific techniques/ideas may have been passed down to modern JIT compilers.

One thing that I find curious is that their evaluation does not include any comparison against an implementation of SELF itself? (no pun intended) This isn't the first paper on SELF, so I assume there was some prior implementation of the language... but I may be wrong there. But I do think it would have been better if they had some naive, non-efficient implementation to compare against so they can highlight the effects of their optimizations! But I may be having a big misunderstanding here, please correct me if I am!

Also as a side note, I think the programming environment for SELF that was described in the paper is as seen on this video here. I don't have much to say about it besides that it's very different from what I expect an IDE to look like! It's interesting to see how people may have programmed about 30 years ago though.

[sampsyo]

It's a very good question about exactly what has "echoes" in modern JIT compilers. The main thing, IMO, is the overall gestalt rather than any individual technique: that is, that you can start with a language intentionally designed with a lot of dynamic complexity in the semantics, and then use specialization to generate code that is predicated on certain run-time conditions that matches what you'd generate for a much more "static" language.

But that aside, certainly stuff like "type prediction" is still bread-and-butter in today's compilers.

About comparing with prior implementations, it's a good point… the original Self paper from 1987 ("The Power of Simplicity"; bold title!) is exclusively concerned with the design of the language rather than the implementation. It has a grand total of three sentences to say about an implementation:

Craig Chambers, Elgin Lee, and Martin Rinard have built a prototype environment for Self including a browser, inspector, debugger, and interpreter. This system is intended to help us gain a deeper understanding of the language and implementation challenges. We have written and run small Self programs in this environment.

And that's what you needed to publish a paper in 1987, apparently! I would hazard a guess that the team divided up the work into two papers: the design paper and the follow-on implementation paper, and this Chambers paper is the first proper/published implementation of the language.

[charles-rs]

Throughout this paper, i found myself really questioning the motivation of SELF. It wasn't till a few pages in that I realized this was a real language designed for reasons other than "being difficult to compile" This original paper helps contextualize it a bit!

[tonyjie]

This original Self paper really solved my puzzles about the motivation of SELF. When I first read the implementation paper of SELF, I found this programming language has unique characteristics (no class or variable, having prototype and message) but I didn't know why. Getting to know the design motivation also helps with understanding its implementation in this paper.

[5hubh4m]

This paper was super interesting; but like how visiting an old science museum is interesting. You get to feel excited about the great olds who came up with all the techniques that are considered ordinary and commonplace in today’s day and age.

[susan-garry]

Yes, and you also get to think about all the ideas that run counter to today's common sense and wonder which of our ideas and assumption will be turned on their heads in a few years.

[zzzDavid]

This paper is about a dynamic object-oriented language called SELF. It doesn’t have class or variable, instead it has prototype and message. The paper proposes two methods to alleviate the space and time cost of object-oriented dynamic languages. For the space cost, it uses map as a mechanism to allow objects in an inheritance family to share non-assignable data. Each child only has to store a copy of assignable data. For the time cost, it segragates object references and bytes area, so that byte array objects are never scanned, and object headers are never parsed. I think these two methods are transferrable to general dynamic language implementation, and are probably already used in modern implementations.

The other interesting thing is its compiler design. The paper mentions that dynamic language has little static type information, which makes type inference and optimization difficult. Interestingly, SELF just enumerate all possible types for a function and compile different machine code for each.

The paper also mentions that SELF supports dynamic inheritance, the ability to change inheritance relationship at runtime. I’ve never used such feature before (or I have used it without knowing), so I’m curious about when would it be useful to change inheritance at runtime.

[charles-rs]

im also curious about when changing inheritance at runtime would be useful... This seems like a very dangerous and not very useful feature, but then again maybe there's a reason we've all written java programs and not self

[chhzh123]

I by accident know one of the use cases based on the experience of my previous research project. Dynamic inheritance can be useful when there are several implementations for a function interface, but the implementations can be only known at runtime. For example, we can imagine a scenario where a long-running system is deployed on the cloud, and users can submit their jobs to this system. The system defines a base class BaseJob with a virtual function exec, and users can define their own Job class inherited from BaseJob. Since different users can define different exec functions and submit the job at different time points, it means the inherence relationship is built at runtime when the job is accepted by the system. In this way, user-defined classes/functions can be packed as an external library to be submitted, and there is no need to compile the runtime system and those jobs at the same time, which can be viewed as an advantage of dynamic inheritance. This blog also describes this situation and provides a tricky implementation in C++.

[sampsyo]

I may be stating the obvious here, but the most prominent place that Self's prototype-based inheritance lives on today is in JavaScript. Classes are a relatively new addition to the JS standard; the OG JS was basically a Self clone with Java-like syntax.

At least in (pre-classes) JS, the ability to dynamically change the prototype chain was not used very often. That doesn't mean it didn't serve a purpose; it was there for language simplicity and for weirdo special cases. But means that (as in this paper) JITs were/are very optimized for the static "class-like" use of prototype chains; the weird special cases could be slow and off the critical path. That's kinda the magic of the JIT+Self combo: you can have very costly/weird language features, and you "pay as you go", i.e., the common case can go fast and the uncommon case can still be possible.

[anshumanmohan]

I thought the discussion about memory segregation in S3.2 was interesting, and it got me thinking about the applicability of this technique in other languages. Of course we separate the stack and the heap, but, within the heap, malloc just gives us an arbitrarily-chosen chunk of memory of the right size. We don't expect, or get, finer-grained control. Later on, we need to disambiguate blocks that could be pointers, and down that road lies conservative management. Any thoughts on why it's not more common to carefully separate pointers from objects that could masquerade as pointers?

[5hubh4m]

Object map filters are kind of doing this - disambiguating pointer-like values which could not be pointing to allocated objects.

[sampsyo]

I don't have exhaustive knowledge here, but I'm not 100% certain it is uncommon! I could imagine modern GCs doing some version of this (e.g., having a special heap just for large arrays of ints and floats because you very rarely want to scan them).

[anshumanmohan]

Oops, sounds like this is my bad then!

[sampsyo]

Not at all; I am just guessing, like you!

[andreyyao]

First of all, I was slightly triggered by this sentence from the introduction:

Like Smalltalk, SELF has no type declarations, allowing programmers to rapidly build and modify systems without interference from out-of-date type declarations.

Did they mean that the concept of type declaration was archaic, or that there might be out-of-date type signatures in an existing code? I hope it's the latter, which is indeed an advantage of dynamic languages...

The dynamic inheritance seems like an interesting concept, but the example they gave was nonsatisfactory. It seemed like something that can be easily accomplished by an if statement.

This clone family thing does immediately ring a bell about languages from the ML family. Immutable OCaml/SML types correspond to non-assignment slots in SELF, I think, and there are similar "sharing" things going on between members of a clone family, similar to that of persistent values and data structures in ML.

[charles-rs]

I fear that they actually might mean something like types getting in the way of rapid development, which I can sort of agree with. When writing lisp programs, i've certainly found it the case that there is a convenience starting out to not have to worry about types, but then again lisp only really has one type. I also think it is something of a hindrance to not even HAVE the option to use compile time types, but maybe i just have a preference for incremental typing. It seems to me like some kind of explicit, compile time type system has been widely accepted as a key to writing correct programs, but perhaps SELF is more concerned with writing programs quickly than correctly?

[sampsyo]

I think it's important to remember that this paper was part of the "invention" of dynamic languages in the modern era. (Lisp aside, of course—everything descends from Lisp.) Today, we are all excruciatingly familiar with the debate between "strong static type systems just get in the way of my creativity and slow me down" vs. "dynamic languages make it hard to scale up software beyond a few hundred lines without creating thousands of self-inflicted bugs." Regardless of where any of us stands on that particular opinion spectrum, it's important to realize that today it is a spectrum: that is, static languages (C, Java, Rust) are all very popular, and dynamic languages (Python, JavaScript) are also very popular in the real world. SmallTalk/Self are the first examples of attempts to popularize the latter end of the spectrum, at a time when the former end was truly dominant.

[andreyyao]

@charles-rs

but maybe i just have a preference for incremental typing

Incremental typing does seem to be more popular among dynamic languages these days(from my limited perspective), with Python 3.6 supporting optional type annotations, and also stuff like Typed Racket, etc. I guess giving the users the ability to choose the strength of the type system based on their goal(big project vs. rapid prototyping) is pretty helpful.

[andreyyao]

it's important to realize that today it is a spectrum: that is, static languages (C, Java, Rust) are all very popular, and dynamic languages (Python, JavaScript) are also very popular in the real world.

I have been thinking about this "spectrum" of type staticness and how it relates to other language features and paradigms. What I mean is that although whether a language is statically or dynamically typed does affect where/how it's used in many cases, the type systems are definitely not the only factor. For example, an OCaml user might be using it for its strong static Hindley-Milner typing system, they might also only really care about the nice first-class functions, default immutability, etc. Similar, a Python user MIGHT have chosen Python for its dynamic typing, but that's not guaranteed.

Now both python and javascript now have typing extensions (for example, typescript). But I wonder if certain language features or even collections of language features make a given language more flexible in type strictness.

[andrewb1999]

I found this paper interesting, but definitely in more of a foundational way rather than presenting a lot of ideas that are new to me (makes sense because of when this paper was published).

Although I agree with the point made in lecture that there's no such thing as a "dynamic language", some parts of this paper show the importance of codesign between the language and the compiler. This goes beyond just dynamic sematics lending themselves to dynamic compilers; the specific dynamic sematics affect the details of the compiler/interpreter. For example, the way SELF handles objects and the use of maps in the compiler implementation are intertwined. This fact is kinda obvious in hindsight, but it's still good to see a concrete example.

[sampsyo]

Just to be clear, I have no beef with the term "dynamic language"! Some languages imply a lot of dynamic semantics. What I don't like is "compiled language" vs. "interpreted language".

[JonathanDLTran]

I thought the customized compilation work was intriguing, because of the relative simplicity of the idea, yet how powerful the idea is in getting optimization potential. I feel this ties into the idea of optimizing the common case, where the compiler anticipates common cases and optimizes on those common cases using inlining. I imagine this principle, particularly message splitting, could be applied in languages like Python, where the plus operator would be used generally for ints and floats. I also feel this is similar to what was presented in lesson 11, where branches can be pushed as far upwards as possible, so that hopefully, there is only straightline code after the branches, with each choice of straightline code being the target of further optimization.

I am also curious about how often primitive inlining or message splitting can be applied. I feel it would be interesting to see how many times each of these opportunities is allowed to be used, compared to the total number of possible chances.

[sampsyo]

Good point! A more modern version of this paper would absolutely need to contain those statistics to quantify the effectiveness/applicability.