Hacker News Reader

Comment by lgessler | Hacker News Reader

Essentially, yes, but in a way that sounds more careful than what you saw in that Fortran program. If it absolutely has to be stateful, like with a db connection for example, then there's no getting around that, but what you can do is (1) not bury it in a bunch of stateful objects that didn't have to be stateful, which can cause cascading errors when either one of them misbehaves and also makes it difficult to isolate any one stateful component for testing or re-use, and (2) use special wrappers around it that will make the statefulness easier to deal with. (For examples of (2), see Clojure atoms and the Clojure library mount: https://github.com/tolitius/mount )

View on HN

More concretely, for every bit of state in the program I'm interested in two big questions, each with two subquestions:

1.) Who can access this state, and which of those accesses allow writes vs. which are read-only?

2.) What is the lifetime of that state, and what portion of that lifetime is mutable vs. read-only?

Java-style OOP can control #1, but makes no distinction between reads & writes. C++ const correctness and the val/var distinction in Kotlin/Ocaml/ES6/etc. can make that distinction, but only C++ forces you to think in terms of lifetimes. Rust borrowing probably comes closest to answering all 4.

I'm still waiting for a language feature that lets you say "This field of this struct is only mutable while this module is running, and once it completes it will never be changed", though. A lot of data structures are initialized in passes and then passed along as constant data: you construct the basic object structure with nothing but a few IDs, then you compute extra fields as necessary, then you're done and the object is never written to again. If you could keep the fields mutable during initialization (which may be a longer process than just constructor calls) and then seal them off once that's complete, you eliminate a whole class of bugs where a read-only client decides to mutate a field that should only be mutated from designated initializer.

That would be really cool, but I think enforcing that is undecidable. My gut tells me that having that language feature at compile time is the same as the Halting Problem.

I suspect that the ideal language (at least for human use) is one that is just shy of Turing completeness. Once a program compiles and an initial configuration phase has passed all loops would be bounded and all recursions would be guaranteed to terminate. Except for the case of programs that aren't supposed to terminate for which there would be a single construct allowing wrapping everything inside one and only one infinite loop.

In its full generality it's undecidable, but there are probably restrictions you can build into the type system to make it decidable. I was thinking something along these lines:

  class Symbol {
    @init(constructor) originalToken: Token
    @init(constructor) position: SourceLocation
    @init(Parser.parse) scope: SymbolTable
    @init(Parser.parse) declaredType: Type
    @init(TypeChecker.typecheck) inferredType: Type
    @init(DataFlowAnalyzer.computeLiveness) usages: List<Expr>
  }

And then the type system carries an extra bit of information around for whether a reference is fully-constructed or not, much like const-correctness. Fields marked with @init can only be written on a reference that's not fully-constructed. There's no compile-time enforcement for initialization order, though it'd be pretty easy to do this at runtime (convert them to null-checks or special not-initialized sentinel values). Newly-created references start out with the "initializing" bit set, but once they're returned from a function or passed into a function not in the list of legal accessors, they lose this bit unless explicitly declared.

It's basically the same way "mutable" works (in languages that support it), but with a separate state bit in the type system and extra access checks within the mutating functions to make sure they only touch the fields they're declared to touch. You can fake this now by passing mutable references into initialization functions and then only using const, but it's a bit less specific because many classes are designed to be long-term mutable through 1-2 specific public APIs but also need to be mutated internally for deferred initialization, and lumping these use-cases together means that deferred fields can be touched by the public API.

Pure functional languages are capable of this, although they likely aren't modeling it as you envision. Pure record constructors let you do perform arbitrary mutation on the stack (e.g. calling other functions to build field values), but once the constructor is called the returned reference is immutable.

This is likely cleaner than sharing a reference which is sometimes mutable and sometimes not. Rust of course allows for both mutable and immutable borrows, and that's a very powerful tool but it'd be complex if all you needed was field initialization.

The consensus across languages that's emerged is that initialization shouldn't be a group effort, with references escaping in various stages of partial initialization. Be it RAII in C++ or functional record constructors, the common theme is that initialization should be a single operation that can succeed or fail as a whole.

It's the consensus among languages, but I've got a pretty large collection of application code that does need to partially initialize in passes, and there's also a fairly long list of escape hatches in languages (eg. lateinit in Kotlin, friend in C++, builder pattern in Java) to let you do this. Languages are supposed to capture common patterns; I'd argue this is a common pattern that isn't captured all that conveniently by existing language mechanisms, though a number have tried.

> I'm still waiting for a language feature that lets you say "This field of this struct is only mutable while this module is running, and once it completes it will never be changed", though. A lot of data structures are initialized in passes and then passed along as constant data: you construct the basic object structure with nothing but a few IDs, then you compute extra fields as necessary, then you're done and the object is never written to again. If you could keep the fields mutable during initialization (which may be a longer process than just constructor calls) and then seal them off once that's complete, you eliminate a whole class of bugs where a read-only client decides to mutate a field that should only be mutated from designated initializer.

Why do you want to think of it as "the same" struct? It seems to me that the way to achieve this is having the partially initialised thing be a different type than the fully initialised thing, along with a linear type system that makes sure the partially-initialised one is consumed in the process of making the fully-initialised one.

You can do this, but unless all the intermediate types are auto-generated by the compiler, it's going to be a lot of typing (of the keyboard type). Many structs that require multi-pass initialization have many, many fields. Each field that isn't late-initialized is going to be duplicated for each following pass. That's the type of maintenance headache that compilers are meant for.

If you have higher-kinded types and a working record system you can do it by transforming your existing types. Even in more limited languages you might be able to make it manageable with phantom types, e.g. Java's "type-safe builder pattern".

(2) sounds very similar to the way I have typically handled db access in C++. However the kind of state I was referring to is more about the internal computational data used by the program than about external resources.

Reply on news.ycombinator.com