Braindump: Optional types and analysis

[Bob Nystrom]

Here's one of the things I've been mulling over but never found the time to work on:

When I first designed Wren, I deliberately chose to make it dynamically typed even though I also like static types and often program in them. (Wren is implemented in one, after all.) This was a pragmatic choice, not a philosophical one. I think wonderful software can be written with or without types. My thinking was:

• Dynamically typed languages scale down better. You can make a very simple dynamically typed language that is still very expressive and powerful. Scheme and Lua are excellent examples. With static types, as you cut complexity, you tend to lose expressiveness in very painful ways. Pascal, C, and Go (to some degree) are examples of this where it feels like the types are present but not flexible enough to always be helpful.
  
  
• Likewise, the implementation is simpler. My #1 goal with Wren has been to have an implementation small and simple enough that even regular programmers can feel comfortable embedding it in their app and hack on it. With dynamic types, you can put a full parser, compiler, object representation, and bytecode VM in a few thousand lines of code. The execution model is simpler because there's no separate explicit compile step, binary format, etc.
  
  
• Dynamic types fit within my own skills. I'm not the world's greatest language designer or implementer. I wanted to be able to actually get Wren done. My first language, Magpie, is a really neat language in a lot of ways, but it's honestly too ambitious. I didn't have the design or implementation skills to get it complete and fast enough. With Wren, I deliberately designed a language I could ship. Designing a good static type system is *really* hard.

Since Wren is mostly aimed at scripts and embedding in larger applications, my expectation is that most Wren programs will be relatively small. I find static types are less important in smaller scale programs where you can hold more of it in your head. So I figured I could get away with not needing a static type system.

Optional types

At the same time, types are nice. The trend in languages right now is toward them. Most new quickly growing languages are statically typed: Rust, Kotlin, Swift. Every popular dynamically typed language seems to be growing a type system: TypeScript for JS, Hack for PHP, type hints in Python 3. I can't say I've ever enjoyed hacking on a program larger than 10,000 lines in a dynamically typed language.

Optional types are an interesting approach to getting the benefit of static types while keeping most of the nice properties of dynamic types listed above. An optional type system, as the name implies, is a non-mandatory static checking system layered on top of a dynamic language. You can put type annotations in your code, and in your editor you'll get some of the checking you expect. But the runtime implementation retains the simplicity and flexibility of dynamic types.

I have a lot of experience with this. My first hobby language, Magpie, was initially optionally typed. My day job is working on Dart, which was originally an optionally typed language. It is a cool approach and has worked very well for languages like TypeScript and Hack.

However, my experience with Dart is that it has some really unfortunate long-term consequences. The hope with optional types is that you get the best of both words: the safety of static types and the flexibility and simplicity of dynamic types. In practice, I found you often get the opposite: the complexity and verbosity of static types, and the performance and runtime failures of dynamic types.

It's very hard to design an optional static type system that is sound and has no runtime checking. TypeScript's type system isn't sound: you can write valid, error-free TypeScript programs that will fail with a type error at runtime. Dart 1.0's type system was also unsound.

Designing a sound static type system requires either a very complex type system (which the fans of dynamic types won't tolerate) or requires deferring some checks to runtime. The latter is what languages like C# and Java do. Most type errors are caught statically, but things like array covariant and downcasts are checked at runtime.

If you do any runtime checking, that means your types need to actually be available at runtime. For example:

class Test {

  static addThing(list : List<Object>) {

    list.add("not int")

  }

  static main() {

    var nums: List<num> = [1, 2, 3]

    addThing(nums)

    System.print(nums[-1].abs)

  }

}

That call to .abs will fail at runtime if you allow addThing() to stuff a string into that list. But in order to prevent that, you need to know what kind of list it is. You could check this safely at compile time by making lists invariant: saying that a List<num> is not a subtype of List<Object>. This is what Java does. But only having invariant generics is really painful in practice, especially in a language like Wren that doesn't have a separate set of immutable collection types.

Java solved this with wildcards, which are famously complex (and turned out years later to have a hole in them anyway). The other approach you can take is to check List.add() at runtime based on the list's type. But that requires List to keep track of its type argument at runtime. So now you've lost the clean layering of an optional type system. You do have the implementation complexity of implementing reified generics. You quickly end up needing generic methods as well (it's no fun if calling List.map() discards all useful type information).

This is the path we went down with Dart and it eventually became clear that half a type system is often worse than no type system at all, at least for the kinds of programmers using Dart. This is one of the main reasons Dart 2 now has a full "classic" static type system. Our users are much happier for it.

So, these days, my general feeling is that optional types aren't an ideal solution unless you have a huge ecosystem of existing dynamically-typed code that you want to reuse and interoperate with (see: JS, Hack, etc.). Wren is not currently in that boat.

Dynamic analysis?

After reaching that conclusion, I wondered what that left for Wren. (Which, I should stress, is just my personal feeling. Other people may disagree and I may be wrong.) If you look at the value proposition for static types, it's something along the lines of:

• Performance. If you know statically the types of things, you can usually generate more optimal code.
• Safety. Find more errors at compile time so that they can't happen at runtime.
• Safe mechanical refactoring.
• Navigation in your editor. Go to definition, find uses, find overridden and overriding methods, go to superclass, find subclasses, etc.
• Clarity and understanding the codebase. What types of objects are stored in this field? Is this method ever called or overridden? Basically seeing beyond the program text to its semantics.
  

Optional typing completely discards the first one since, by definition, the types don't affect the runtime behavior. The fact that most optional type systems are unsound sacrifices the next two as well. What that really leaves you with is just wanting a better way to get around and learn the codebase.

Do we need static types for that? If you ever talk to a Smalltalker, they'll tell you the answer is emphatically "no". A good live debugging and editing experience is more than enough and (they claim) much more powerful than static types. Lispers often say the same thing. But those two languages also tend to push you towards an entirely new user experience for working with code. Smalltalk has "images" and no real separation between application and IDE. Lisp has the REPL, SLIME, etc.

I wonder if there's a halfway point where we give users the same text-based IDE/editor experience they are used to working with for code. In that editor, we can show them the types of variables and fields, let them navigate around, etc.

Except that instead of basing this all on static types, we do it dynamically. The idea I have is that we some instrumentation to Wren. While running, every time it stores a variable or field, it sends an event over some debugger protocol saying "Hey, the variable at source location blah just stored an object of type Foo." When you call a method, it says "The method call to 'foo()' at source location blah just resolved to 'foo' on Bar." An analysis server collects those and tracks the known dynamic types of every storage location and call in the program.

Hover over a variable and it shows you actual types of objects that got stored in the variable while the program is running. Right-click a method call and say "go to definition", it will show you the set of classes that that call ever dispatched to.

In some ways, this is more powerful than static analysis, because it doesn't tell you the types that things could be. It shows you precisely what concrete classes actually flowed through the program. On the other hand, you lose the safety. Code that is never executed gets no information and code that isn't well-covered may give you less information than you want.

I don't know if this idea would actually pan out in practice. There's a ton of unanswered UX questions around when the analysis state gets discarded and regenerated, how to handle locations that end up with lots of types. Generics are (as always) difficult.

But, if I were to try to build an IDE-like analysis experience for Wren, I'd give this a try.

Cheers!

– bob

[Brian Slesinsky]

Interesting!

If you had a database containing all the type relationships seen so far, it might be interesting to have a debugger feature for "break on previously unseen type".

Comparing type databases generated in testing versus production might be useful. Or perhaps upstream versus downstream dependencies.

--
You received this message because you are subscribed to the Google Groups "Wren" group.
To unsubscribe from this group and stop receiving emails from it, send an email to wren-lang+...@googlegroups.com.
To post to this group, send email to wren...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/wren-lang/CAMu6JH_aewutBMbFz%3DNg4n5LQZ9pfYewDbHei1WV-jcOneenWA%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.

[Michel Hermier]

That look a lot like a push request I made ^^ at 100%