News for hackers. Stuff that matters.
Re:Introducing MIR by nostrademons on Wednesday April 27, 2016 @12:54PM (#11582181)
It's been pretty common for compilers to require 3 different intermediate representations (parse tree, MIR, and LIR). My copy of Advanced Compiler Design and Optimization [1] (over 10 years old at this point) lists the 3-IR architecture on page 8. It references Sun's SPARC compilers, DEC's Alpha compilers, Intel's x86 compilers, and SGI's MIPS compilers as implementations that use it.

What has changed are the boundaries. Traditionally, semantic analysis (including typechecking) operated on the parse tree, which resembled the human-written language extensively. Optimization operated on MIR, then it'd be lowered to an architecture-specific LIR via register allocation and instruction selection, and another round of optimization (instruction scheduling, etc.) would be applied. The purpose of all of this was to provide multiple language front-ends on top of a single compiler. In the 80s and 90s, compilers were often written by the hardware vendor, so they would tightly optimize the MIR and LIR for their own architecture, and use the parse-tree => MIR lowering to support multiple surface languages.

LLVM chose a LIR that's closer to what many compilers had been using as MIR, and then moved the optimization passes into the LIR, and hid the architecture-specific backends within the LLVM project itself, out of the eyes of language designers. It could do this because of open-source: with a shared body of compiler code owned by everyone and gradual consolidation of the hardware market, it became easier to contribute your backend to LLVM than to maintain your own compiler stack and fight for adoption. (GCC actually had a fairly similar architecture first, but the GCC IR was very difficult to comprehend if you weren't a GCC maintainer, which made it impractical as a compilation target for outside projects. They generated C code instead and let GCC compile it.) That in turn made it much easier to write a compiler and experiment with language design, since you only had to figure out how to translate your language to LLVM's IR rather than work out the details of scheduling and register allocation. That, in turn, allowed greater complexity in language features: Swift and Rust have language features that go beyond what cutting-edge research was <10 years ago, and do so in a production language that you can use now. And so it's not surprising that they're now re-introducing a MIR to manage the additional complexity introduced by the new language features.

[1] http://www.amazon.com/Advanced-Compiler-Design-Implementatio...

Re:Introducing MIR by pcwalton on Wednesday April 27, 2016 @01:22PM (#11582444)
If you count the intermediate IRs that LLVM has, then Rust actually now has many more than three IRs: AST, HIR, MIR, LLVM IR, SelectionDAG, MachineInstr. Even before MIR, there were 5 IRs.
Re:Introducing MIR by Ericson2314 on Wednesday April 27, 2016 @03:12PM (#11583609)
Indeed, the more IRs, the better---structure your data to fit your task, not your algorithm to fit your data.
Re:Introducing MIR by infogulch on Wednesday April 27, 2016 @01:20PM (#11582426)
I tried to upvote you, but I fat-finger downvoted you instead. Sorry. :(
Re:Introducing MIR by BinaryIdiot on Wednesday April 27, 2016 @02:52PM (#11583433)
A slight side note: this is one of the most difficult parts with using Hacker News on a mobile device. I fat finger upvotes all the time! I wouldn't mind the ability to change a downvote to an upvote and vice versa, even if it was time limited so I could correct any incorrectly voted items.
Re:Introducing MIR by tetraodonpuffer on Wednesday April 27, 2016 @09:42PM (#11586049)
couldn't this be easily fixed by putting the downvote triangle on the other side of the time?

(upvote arrow) name xxx hours ago | parent | flag | (downvote arrow)

would make it less fat finger prone and still be pretty straightfoward to use (plus having downvote close to flag IMHO makes sense as well from a context perspective)

Re:Introducing MIR by odbol on Thursday April 28, 2016 @10:31PM (#11593418)
Could be easily fixed by one line of CSS to make the dang buttons larger, but apparently Hacker News can't be bothered to improve their shitty website.

EDIT: great community, shitty website.

Re:Introducing MIR by BinaryIdiot on Thursday April 28, 2016 @12:54AM (#11586617)
Yup that would work really well
Re:Introducing MIR by simcop2387 on Wednesday April 27, 2016 @03:30PM (#11583747)
Either that, or a way to hide the down vote on mobile. I hardly ever legitimately down vote so when i fat finger it on mobile it just makes me look like a jerk.
Re:Introducing MIR by MichaelGG on Wednesday April 27, 2016 @06:44PM (#11585213)
Except no one can see you did it, so it doesn't make you look like a jerk. A random downvote here and there shouldn't bother anyone. It's probably better off if we just realise this and never talk about it.
Re:Introducing MIR by nostrademons on Wednesday April 27, 2016 @07:01PM (#11585309)
Depends on context. I'm at +149 right now on the top-level comment, so one upvote that turned into a downvote isn't really a big deal. It could be pretty annoying if you've worked hard on a long comment and then it goes from 0 to -1 instead of +1 because of a fat-fingered downvote.
Re:Introducing MIR by spacemanmatt on Wednesday April 27, 2016 @03:28PM (#11583719)
I use the Android app Materialistic, and don't seem to have ui problems. YMMV.
Re:Introducing MIR by cyphar on Thursday April 28, 2016 @07:21PM (#11592623)
I use it too. The only problem is that the latest update broke the commenting (it only allows you to type one line). But I filed a bug report and it was fixed, so we just have to wait for the update. This is why I love free software. No begging in app comment sections.
Re:Introducing MIR by brynjolf on Thursday April 28, 2016 @03:01AM (#11586954)
I love that app so much. It is nearly perfect!
Re:Introducing MIR by iopq on Wednesday April 27, 2016 @04:50PM (#11584423)
I gotchu fam
Re:Introducing MIR by mietek on Wednesday April 27, 2016 @04:53PM (#11584450)
> Swift and Rust have language features that go beyond what cutting-edge research was <10 years ago

Such as?

Re:Introducing MIR by nostrademons on Wednesday April 27, 2016 @05:53PM (#11584890)
Type inference in the presence of OOP-style subtyping was largely considered to be impossible in 2005; there had been a lot of research results with System F:< and System Fw, along with a well-known undecidability result [1]. Attempts to introduce subtyping into research languages like Haskell and Ocaml gave us records [2] and objects [3], but neither of these were something that an ordinary mainstream programmer would want to use. Haskell's type system made it frustratingly easy to construct types that would force the typechecker into an infinite loop [4].

And now Swift not only allows these in a way that's familiar to existing mainstream programmers, it interoperates fully with Objective-C and offers additional features like polymorphic literals. And when polymorphic literals (previously allowed only by Haskell, and then not with user-defined types) makes typechecking take 12 hours [5], it's widely decried for being poorly implemented.

On the Rust end - the whole concept of the borrow checker was borrowed (sorry) from Cyclone [6][7], a research language of the early 2000s. I remember seeing it occasionally pop up on Lambda: the Ultimate [8] around 2004-2005, people seemed intrigued, but few people really took notice. Rust's big accomplishment is to generalize this to an "industrial strength" programming language, figuring out all the corner cases around mutability, traits, move-semantics, boxes, etc. that you need for this to work in real programming.

[1] http://repository.cmu.edu/cgi/viewcontent.cgi?article=3059&c...

[2] http://research.microsoft.com/en-us/um/people/simonpj/Haskel...

[3] https://realworldocaml.org/v1/en/html/objects.html

[4] https://downloads.haskell.org/~ghc/latest/docs/html/users_gu...

[5] https://www.reddit.com/r/programming/comments/4givdg/go_home...

[6] http://www.bennetyee.org/ucsd-pages/Courses/cse227.w03/hando...

[7] https://www.cs.umd.edu/~mwh/papers/ismm.pdf

[8] http://lambda-the-ultimate.org

Re:Introducing MIR by pcwalton on Wednesday April 27, 2016 @06:03PM (#11584955)
> On the Rust end - the whole concept of the borrow checker was borrowed from Cyclone

Not really. That's the lifetime system, which is not the same thing. "Existential Types for Imperative Languages", also by Dan Grossman, explains more of the motivation, but the borrow check is a hybrid of the two solutions he presents.

Borrowing itself is something with a long history, but the whole "unique loan paths" thing makes Rust's solution distinct from a lot of the stuff you find in the research literature.

Re:Introducing MIR by tomp on Wednesday April 27, 2016 @06:50PM (#11585238)
> Type inference in the presence of OOP-style subtyping was largely considered to be impossible in 2005

Type inference in a OO language is still considered, if not impossible, at least very impractical. Swift, Scala and Rust avoid most algorithmic complexity and ambiguity by mostly supporting only type propagation instead of type inference, and thus require annotations on function parameters.

Re:Introducing MIR by nostrademons on Wednesday April 27, 2016 @07:34PM (#11585476)
The big innovation there is in realizing that's enough. When I was into language design from 2004-2007, language designers usually assumed people wanted full global type inference. It turns out that local type propagation is an effective 80/20 solution for most practical programming tasks, which opened up a lot of hybrid type systems that would've been far too complex before.
Re:Introducing MIR by pshc on Thursday April 28, 2016 @01:25AM (#11586706)
Yes. A blessing in disguise. In hindsight, global type inference seems too unstable. Too much action at a distance; it's hard to evolve a codebase when local changes cascade. Type annotations keep things grounded.
Re:Introducing MIR by sklogic on Thursday April 28, 2016 @06:02AM (#11587603)
Nemerle had quite an interesting solution to this problem back then.

http://research.microsoft.com/en-us/um/people/moskal/pdf/msc...

Re:Introducing MIR by mietek on Thursday April 28, 2016 @11:43AM (#11589694)
Yes. It’s worth pointing out that this is the author’s MSc thesis, submitted in 2005.
Re:Introducing MIR by jeltz on Wednesday April 27, 2016 @08:46PM (#11585844)
What about Crystal? It has quite extensive type inference.
Re:Introducing MIR by yokohummer7 on Thursday April 28, 2016 @01:00AM (#11586634)
Unfortunately they also had to narrow down the scope of type inference recently. IIRC type annotations are now mandatory for class-level variables (member variables). This hindered the "Ruby-like" feeling, but they had to give up global type inference because it costed too much memory in some cases. I got an impression that global type inference is difficult (or, costly) in general.
Re:Introducing MIR by humanrebar on Thursday April 28, 2016 @07:34AM (#11587980)
I'm not sure I consider Rust to be object oriented.
Re:Introducing MIR by aseipp on Wednesday April 27, 2016 @06:20PM (#11585058)
> Haskell's type system made it frustratingly easy to construct types that would force the typechecker into an infinite loop [4].

It's more akin to C++ templates, where the type checker only has a bounded number of reductions it will do before it gives up. Aside from writing something that really is infinite and a limit of trillions of reductions - which wouldn't really be a useful program - it ends up as a type error as you'd expect. This also only happens with -XUndecidableInstances, which frankly isn't really one of the most common extensions, I'd say.

That said, in practice, most Haskell programmers seem to largely consider subtyping a misfeature anyway, and approximations of it elsewhere in the ecosystem use things like RankNTypes to give a 'feel' for subtyping where you can do things like "use any instance of a more general base type, in place of that type, right here". The infamous lens library does this to great effect.

> previously allowed only by Haskell, and then not with user-defined types

I don't know what you mean here - Haskell has, until recently, never allowed overloaded literals for certain syntactic forms, like lists. For the other cases, though, like numerics, you have always been able to have polymorphic literals, which can be instantiated to user-defined type. The most general type of `1` by itself with no defaulting is `1 :: Num a => a`, and there's certainly no problem with instantiating `a` to whatever user-defined type you have, providing it can sensibly be constructed from a base-10 decimal value (meaning, you have a function `toInteger :: Integer -> a`)

These days, lists are also syntactically overloadable by a similar convention, through value polymorphism/type classes.

Re:Introducing MIR by pjmlp on Thursday April 28, 2016 @02:27AM (#11586862)
Meanwhile companies like Google invest their money in languages that were already known to be possible in 1968.

http://cowlark.com/2009-11-15-go/

Re:Introducing MIR by Ygg2 on Thursday April 28, 2016 @05:45AM (#11587528)
I like Rust, but there is nothing wrong with Go (I think their decision to not have generics does have some merit). They just took trade-offs they needed. Nothing wrong with that.
Re:Introducing MIR by pjmlp on Thursday April 28, 2016 @06:06AM (#11587617)
I did like Oberon a lot, and appreciate Oberon-2 influence on Go, but I think there is a lost opportunity in a company like Google sponsoring such a design, when it could have done so much more helping advancing the state of art for mainstream developers.

In that regard, Apple and Microsoft do so much more to help developers improve their skill sets, given the programming languages and tools that they have brought into the market.

However, I do advocate Go for the use cases where developers still make use of C for user space applications, without any real need for C's low level features.

Also do believe that Go can actually be used for systems programming, even if not all scenarios from systems programming like for example, 8 and 16 bit embedded processors, can be covered.

The language is similar enough to Oberon and Limbo for it to be possible, just needs someone to write a bare metal runtime.