1. 9

  2. 1

    For someone without the necessary background, what exactly are abstract machines here? The wiki seems to suggest it is just a lower level language that is higher than the end goal (machine code) but lower than the current level. E.g. opcodes for a VM. Is this the abstract machine referred to here?

    1. 2

      I would guess so.

      The problem is that every programming language, high or low level, has a corresponding abstract machine. So to say that “abstract machines don’t do much well” is misleading. If you compile to x86_64, you’re not avoiding abstract machines, you’re just targeting a different abstract machine.

      I think the authors who are “dissatisfied by abstract machines” are just dissatisfied with their choice of intermediate representation.

      1. 2

        I think abstract machines here mean something different from intermediate representation. Note that SSA is mentioned as an alternative to abstract machines, but SSA is an intermediate representation.

        The next to the last slide in Leroy’s presentation suggests that abstract machines here are useful for implementing bytecode interpreters, so vrthra’s “opcodes for a VM”. I think what is being said is that representations suitable for implementing bytecode interpreters are often not the best for intermediate representation of a native code compiler. When you state it that way, it is kind of obvious: I mean why they would be, compilers are not interpreters after all.

        1. 1

          For any given Turing-complete language, there are infinitely many abstract machines. However, I’m not sure that any of them are in natural correspondence. For example, what’s the abstract machine for Wang tiling? I can imagine several abstract machines, but I don’t see why one of them is naturally the corresponding abstract machine.

          This isn’t a facile objection. Consider Turing machines, and also consider Post’s correspondence problem for Turing machines. Which is the corresponding abstract machine: the Turing machine itself, or Post’s machine which assembles toy bricks? Is the deterministic approach the natural approach, or is non-determinism more natural?

        2. 1

          An abstract machine is a machine that isn’t implemented in hardware. They are slower to execute than hardware, since they must be emulated. They are also more flexible than hardware, allowing reprogrammable behavior at runtime.

          If an abstract machine is to be used in a compiler, then it needs to be between the user and the hardware. The idea is that the user’s code targets the abstract machine, and then the abstract machine is either implemented in software or its behaviors are compiled to native code for the target hardware. The abstract machine forms a “narrow waist”, a point in common between compilers to different hardware, just like an intermediate representation.

          Abstract machines are also found outside compilers. For example, emulators are abstract machines.