7 ms·

> I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. A tail call is a jum

by jhgb 4y ago

> I'm a huge functional programming evangelist, but high-level stuff like this does not belong in a low level language bytecode like WASM. A tail call is a jump. Jumps are not "high-level stuff". They're very simple instructions. If WASM can't do a jump, it is actually WASM that you can't call "a low level bytecode".

Spivak 4y ago
WASM doesn't have jumps [1]. And it's not as low-level as you might expect. But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other. https://webassembly.github.io/spec/core/syntax/instructions.html https://webassembly.github.io/spec/core/syntax/instructions....
- jhgb 4y ago
  I never expected WASM to be low-level to begin with, so I don't believe it could ever possibly be "as low level as I might expect". Something like NaCl (the original one) perhaps could have been called "low level". > But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other. I don't see how jumps are "fictional". Plenty of CPUs have them. Even actual stack CPUs, for that matter.
  - shadowgovt 4y ago
    Jump as a concrete implementation is easy to understand (it's just math on a program counter). But code is both a mechanical implementation and an abstract, often mathematical, concept. In the concept space, jump is as abstract as call, variable assignment, operator evaluation, etc. A Von Neumann machine is but one way to implement an abstract mathematical / conceptual machine. In the mathematical space, there's no "high level" vs. "low level," there's just "features a language has" vs. "features it does not." There are other abstractions that are actually harder / impossible to do correctly with jump in the language (stack unwinding comes to mind, which is why C++ solves the exceptions vs. setjmp / longjmp dichotomy by... Not solving it, and a program that uses both will just do something undefined. C++ without setjmp / longjmp would be a language with fewer undefined behaviors).
    - jhgb 4y ago
      Possibly, but when I talk about "low-level stuff", I usually imagine very concrete things that are suitable for physical hardware implementation. Things like what the simplest RISC-V chip is designed to do. Unlimited jumps definitely are one of those things. Notions of stack frames or block structured languages (limitations on jumps) etc. definitely aren't among them. So I couldn't possibly ever consider something like WASM to be "low-level", because it places constraints on your code that no reasonable physical CPU would ever enforce. [EDIT, from a deleted comment of yours: > The RISC-V chip is in the same family as the PDP-11 architecture. The Turing machine itself requires no JMP instruction, so it is possible to build a CPU without one. Has anyone done so? In general no, because the PDP-11 had profound impact on the world of physical computing. But one does see it from time to time; GLSL, for example, has no `goto` instruction because the graphics card shader hardware it was built to operate on does its magic by running exactly the same instructions on multiple data; jump would imply the ability for one of the instruction flows to be different from the others in its processing cell, which the hardware cannot support while maintaining the throughput it must to accomplish its task. I get what you're trying to say here, but sort of a guiding principle for me here for many years has been what I call "the principle of minimal total complexity". While you can keep making the CPU simpler in many cases, if that causes your program to become excessively long in the sense that the total size of the description of your program AND the device it's running on starts actually increasing, that's a place you don't want to design yourself into in practice. In case of sequential machines, I don't consider removal of features that makes programs unnecessarily long "making the machine even more low-level", that's just "making the machine dumber" to me. Feel free to look at the Oberon system (both HW and SW) to see what I have in mind by that -- that seems to be about as minimal a complete system as I can imagine in practice.]
      - deleted 4y ago
        [deleted]
      - shadowgovt 4y ago
        To be clear, I deleted that comment because it was inaccurate. GLSL has break, continue, and return, which are flow-control statements. It excludes goto, and my explanation for why it excludes goto is probably incorrect (but I don't have time today to rabbit-hole on why goto was excluded or why the SIMD architecture can support break and continue just fine while excluding goto). > In case of sequential machines, I don't consider removal of features that makes programs unnecessarily long "making the machine even more low-level", that's just "making the machine dumber" You may be interested to consider how incredibly complex the modern x86 architecture is to implement because it supports sequential program execution as a core invariant principle. As a result, modern computers (which strive to be faster than a PDP-11) have to do a massive amount of work to parallelize that sequential code because parallel execution is the only frontier of fast computation that remains. They literally rewrite the opcodes on the fly into something that can be SIMD'd and do branch prediction, where code is run speculatively just to discard the result. All to support the idea that deterministic flow control should be possible in 2022. It's a brilliant fantasy the chipset manufacturers have constructed for us so we don't have to reframe our thinking. I think I get what you're saying, but in modern times calling jump "low level" (or, for that matter, calling branching in general low level) is a very "Do you think that's air your breathing?" kind of position. I'm not aware of anyone seriously considering approaching the challenge of all this implementation complexity by throwing out fundamental assumptions of our PDP-descendant instruction sets and saying "Here's a new machine code, it's designed for parallel execution, the first assumption you must throw away is the order in which any of these instructions are executed." But I suspect we're getting very close to that day.
  - Spivak 4y ago
    I feel like you're ascribing some judgement to the word fictional, it just means that machines, real or virtual, present programs a model of computation that is an abstraction over the implementation. One such abstraction is the notion of a program that is a block of instructions executed in sequence with a program counter, registers, memory, a stack. But that's not the only abstraction you could imagine. The JVM for example eschews manual memory management. And WASM eschews the concept of a program counter, and arbitrary jumps, and instead only allows structured control flow.
    - jhgb 4y ago
      I feel like you're using the word "fictional" in a sense that renders all models of computation "fictional" to the same extent and hence renders the word "fictional" itself meaningless/uninformative. Personally I feel like there should be some distinction between features depending on how much supporting machinery you need to physically implement them. To me at least, "low-level features" are those that require the smallest amount of physical machinery to implement them. Things like bitwise operations, indirect addressing, arbitrary IP adjustments, etc. Definitely not things like enforcing stack discipline, enforcing block structure and such. (Just so that you know what I mean when I say "low-level". Opinions on that may differ very wildly, of course, and it's perfectly possible that other people use that term differently.) I'm not saying that "fictional" things are bad. Tail calls themselves are "fictional" to me in the sense that all tail calls are jumps but not all jumps are tail calls, and the distinction between a tail call and a general jump is too difficult to make for a reasonably sized physical machine and best left to the compiler. But that is not me being judgmental against tail calls, of course -- I love tail calls and consider their lack a huge design failure wherever they're absent.
- msla 4y ago
  WASM isn't particularly low-level, in that it's a compiler's IR, with a few concomitant restrictions on how control flow is allowed to work. Here's a piece on those restrictions, and how they make implementation more difficult: http://troubles.md/why-do-we-need-the-relooper-algorithm-again/ http://troubles.md/why-do-we-need-the-relooper-algorithm-aga... > WebAssembly isn’t designed as a front-end language for general programming though, so what’s the problem? Well, WebAssembly does have some constraints, specifically it must produce code that is valid. WebAssembly is a stack machine, and you can’t jump to just any label since that label might point to code that pops too many values off the stack, or pops the wrong types off the stack, or pushes too many values onto the stack. Also, to summarize another part, when a compiler targeting WASM sees control flow WASM can't directly express, it has to implement it in a loop-and-switch form, something called the Relooper algorithm; therefore, compilers taking WASM down to native code have to understand that, and undo it back into a performant form. This adds up to a lot of work most VMs don't require, hence the proposal to move WASM towards a control-flow model friendlier to tail-call optimization, which would bring it more in line with physical hardware.
ilaksh 4y ago
I don't think web assembly is low level at all. Actually the name is confusing because it's really not much like an assembly language.

by jhgb 4y ago

Spivak 4y ago

WASM doesn't have jumps [1]. And it's not as low-level as you might expect. But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other. https://webassembly.github.io/spec/core/syntax/instructions.html https://webassembly.github.io/spec/core/syntax/instructions....

jhgb 4y ago
I never expected WASM to be low-level to begin with, so I don't believe it could ever possibly be "as low level as I might expect". Something like NaCl (the original one) perhaps could have been called "low level". > But even still you're assuming that low level means a specific model of computation a la PDP-11 that's as fictional as any other. I don't see how jumps are "fictional". Plenty of CPUs have them. Even actual stack CPUs, for that matter.
- shadowgovt 4y ago
  Jump as a concrete implementation is easy to understand (it's just math on a program counter). But code is both a mechanical implementation and an abstract, often mathematical, concept. In the concept space, jump is as abstract as call, variable assignment, operator evaluation, etc. A Von Neumann machine is but one way to implement an abstract mathematical / conceptual machine. In the mathematical space, there's no "high level" vs. "low level," there's just "features a language has" vs. "features it does not." There are other abstractions that are actually harder / impossible to do correctly with jump in the language (stack unwinding comes to mind, which is why C++ solves the exceptions vs. setjmp / longjmp dichotomy by... Not solving it, and a program that uses both will just do something undefined. C++ without setjmp / longjmp would be a language with fewer undefined behaviors).
  - jhgb 4y ago
    Possibly, but when I talk about "low-level stuff", I usually imagine very concrete things that are suitable for physical hardware implementation. Things like what the simplest RISC-V chip is designed to do. Unlimited jumps definitely are one of those things. Notions of stack frames or block structured languages (limitations on jumps) etc. definitely aren't among them. So I couldn't possibly ever consider something like WASM to be "low-level", because it places constraints on your code that no reasonable physical CPU would ever enforce. [EDIT, from a deleted comment of yours: > The RISC-V chip is in the same family as the PDP-11 architecture. The Turing machine itself requires no JMP instruction, so it is possible to build a CPU without one. Has anyone done so? In general no, because the PDP-11 had profound impact on the world of physical computing. But one does see it from time to time; GLSL, for example, has no `goto` instruction because the graphics card shader hardware it was built to operate on does its magic by running exactly the same instructions on multiple data; jump would imply the ability for one of the instruction flows to be different from the others in its processing cell, which the hardware cannot support while maintaining the throughput it must to accomplish its task. I get what you're trying to say here, but sort of a guiding principle for me here for many years has been what I call "the principle of minimal total complexity". While you can keep making the CPU simpler in many cases, if that causes your program to become excessively long in the sense that the total size of the description of your program AND the device it's running on starts actually increasing, that's a place you don't want to design yourself into in practice. In case of sequential machines, I don't consider removal of features that makes programs unnecessarily long "making the machine even more low-level", that's just "making the machine dumber" to me. Feel free to look at the Oberon system (both HW and SW) to see what I have in mind by that -- that seems to be about as minimal a complete system as I can imagine in practice.]
    - deleted 4y ago
      [deleted]
    - shadowgovt 4y ago
      To be clear, I deleted that comment because it was inaccurate. GLSL has break, continue, and return, which are flow-control statements. It excludes goto, and my explanation for why it excludes goto is probably incorrect (but I don't have time today to rabbit-hole on why goto was excluded or why the SIMD architecture can support break and continue just fine while excluding goto). > In case of sequential machines, I don't consider removal of features that makes programs unnecessarily long "making the machine even more low-level", that's just "making the machine dumber" You may be interested to consider how incredibly complex the modern x86 architecture is to implement because it supports sequential program execution as a core invariant principle. As a result, modern computers (which strive to be faster than a PDP-11) have to do a massive amount of work to parallelize that sequential code because parallel execution is the only frontier of fast computation that remains. They literally rewrite the opcodes on the fly into something that can be SIMD'd and do branch prediction, where code is run speculatively just to discard the result. All to support the idea that deterministic flow control should be possible in 2022. It's a brilliant fantasy the chipset manufacturers have constructed for us so we don't have to reframe our thinking. I think I get what you're saying, but in modern times calling jump "low level" (or, for that matter, calling branching in general low level) is a very "Do you think that's air your breathing?" kind of position. I'm not aware of anyone seriously considering approaching the challenge of all this implementation complexity by throwing out fundamental assumptions of our PDP-descendant instruction sets and saying "Here's a new machine code, it's designed for parallel execution, the first assumption you must throw away is the order in which any of these instructions are executed." But I suspect we're getting very close to that day.
- Spivak 4y ago
  I feel like you're ascribing some judgement to the word fictional, it just means that machines, real or virtual, present programs a model of computation that is an abstraction over the implementation. One such abstraction is the notion of a program that is a block of instructions executed in sequence with a program counter, registers, memory, a stack. But that's not the only abstraction you could imagine. The JVM for example eschews manual memory management. And WASM eschews the concept of a program counter, and arbitrary jumps, and instead only allows structured control flow.
  - jhgb 4y ago
    I feel like you're using the word "fictional" in a sense that renders all models of computation "fictional" to the same extent and hence renders the word "fictional" itself meaningless/uninformative. Personally I feel like there should be some distinction between features depending on how much supporting machinery you need to physically implement them. To me at least, "low-level features" are those that require the smallest amount of physical machinery to implement them. Things like bitwise operations, indirect addressing, arbitrary IP adjustments, etc. Definitely not things like enforcing stack discipline, enforcing block structure and such. (Just so that you know what I mean when I say "low-level". Opinions on that may differ very wildly, of course, and it's perfectly possible that other people use that term differently.) I'm not saying that "fictional" things are bad. Tail calls themselves are "fictional" to me in the sense that all tail calls are jumps but not all jumps are tail calls, and the distinction between a tail call and a general jump is too difficult to make for a reasonably sized physical machine and best left to the compiler. But that is not me being judgmental against tail calls, of course -- I love tail calls and consider their lack a huge design failure wherever they're absent.
msla 4y ago
WASM isn't particularly low-level, in that it's a compiler's IR, with a few concomitant restrictions on how control flow is allowed to work. Here's a piece on those restrictions, and how they make implementation more difficult: http://troubles.md/why-do-we-need-the-relooper-algorithm-again/ http://troubles.md/why-do-we-need-the-relooper-algorithm-aga... > WebAssembly isn’t designed as a front-end language for general programming though, so what’s the problem? Well, WebAssembly does have some constraints, specifically it must produce code that is valid. WebAssembly is a stack machine, and you can’t jump to just any label since that label might point to code that pops too many values off the stack, or pops the wrong types off the stack, or pushes too many values onto the stack. Also, to summarize another part, when a compiler targeting WASM sees control flow WASM can't directly express, it has to implement it in a loop-and-switch form, something called the Relooper algorithm; therefore, compilers taking WASM down to native code have to understand that, and undo it back into a performant form. This adds up to a lot of work most VMs don't require, hence the proposal to move WASM towards a control-flow model friendlier to tail-call optimization, which would bring it more in line with physical hardware.

ilaksh 4y ago

I don't think web assembly is low level at all. Actually the name is confusing because it's really not much like an assembly language.