Higher-Order Virtual Machine (HVM) • Hacker News Board

Re: Higher-Order Virtual Machine (HVM)

#31

Post by kaba0 » Tue, Mar 28, 2023, 4:51 PM UTC

LightMachine wrote: post #21

kaba0 wrote: post #5

Interesting, though I can’t help but feel that the tone of the first few paragraphs could be a bit more.. humble? Even if the underlying model is much better, you can’t really compare a complete project to one that is alpha. Real world complexities catch up in the later phase of bigger projects. Nonetheless, I eagerly await its future.

I'm working on improving my communication :(

That’s the only thing that matters!

Re: Higher-Order Virtual Machine (HVM)

#32

Post by LightMachine » Tue, Mar 28, 2023, 4:53 PM UTC

zinclozenge wrote: post #29

Are there plans to expand documentation on how to use HVM as a general compilation target like LLVM?

Yes! But first we want to implement some essential features, like full lambda support and some high priority optimizations. Once HVM is ready to support production software, we'll provide docs on how to best use it as a general compilation target. This will be announced in our Discord server: http://discord.higherorderco.com/

Re: Higher-Order Virtual Machine (HVM)

#33

Post by LightMachine » Tue, Mar 28, 2023, 5:46 PM UTC

nerpderp82 wrote: post #22

LightMachine wrote: post #14

Earlier quoted context omitted.

Yes, starting next week or so! We'll be looking for engineers that have skills relevant to our projects, including compilers, low-level assembly optimization, functional programming, type theory, parallel computing, and so on. Right now, we're quite busy with incorporation and bureaucracy, but you should see job postings in our to-be-released landing page (higherorderco.com) soon. Meanwhile, I answer DMs on Twitter (…

What are your thoughts around WebAssembly, Typed Assembly [1] and will you be using BlueSpec [2] to implement these ideas in hardware? [1] https://www.semanticscholar.org/search?q=typed%20assembly%20... namely, Greg Morrisett and Neal Glew's work https://www.semanticscholar.org/author/J.-G.-Morrisett/14364... https://www.semanticscholar.org/author/MorrisettGreg/1643921... (semantic scholar incorrectly thinks there ar…

I love WASM - who doesn't? Maintaining a WASM target was included on HOC's current fundraise, and is essential to our JIT plans. I don't know much about typed assembly, but I guess it would enable optimizations that aren't possible without types, as well as increased safety - although I wonder if that's relevant, if the source language is already typed?

In general though, I think we should move away from procedural instructions towards "interactional" instructions. HVM's AST can be seen as an assembly language with high-level instructions like LAM-APP (lambda application) and FUN-CTR (pattern-matching), and that's possible precisely because beta reduction is O(1) on interaction nets. A hardware with HVM's interactional instructions could make let us break out of the Von Neumann bottleneck and make processors much faster. Here is a table of HVM's core instructions:

    .-----------------------------------------------------.
    | Opcode    | Effect                          | Cost  |
    |-----------|---------------------------------|-------|
    | APP-LAM   | applies a lambda                | 2     |
    | APP-SUP   | applies a superposition         | 4     |
    | OP2-NUM   | operates on a number            | 2     |
    | OP2-SUP   | operates on a superposition     | 4     |
    | FUN-CTR   | pattern-matches a constructor   | 2 + M |
    | FUN-SUP   | pattern-matches a superposition | 2 + A |
    | DUP-LAM   | clones a lambda                 | 4     |
    | DUP-NUM   | clones a number                 | 2     |
    | DUP-CTR   | clones a constructor            | 2 + A |
    | DUP-SUP-0 | clones a superposition          | 4     |
    | DUP-SUP-1 | undoes a superposition          | 2     |
    | DUP-ERA   | clones an erasure               | 2     |
    |-----------------------------------------------------|

I think BlueSpec is impressive and a good direction in the (arguably messy) hardware language domain. It is likely that we'll consider using it in our research and projects.

Re: Higher-Order Virtual Machine (HVM)

#34

Post by LightMachine » Tue, Mar 28, 2023, 5:47 PM UTC

artemonster wrote: post #18

LightMachine wrote: post #14

Earlier quoted context omitted.

Yes, starting next week or so! We'll be looking for engineers that have skills relevant to our projects, including compilers, low-level assembly optimization, functional programming, type theory, parallel computing, and so on. Right now, we're quite busy with incorporation and bureaucracy, but you should see job postings in our to-be-released landing page (higherorderco.com) soon. Meanwhile, I answer DMs on Twitter (…

Digital hardware engineers too?

Eventually, definitely, but less likely for this round.

Re: Higher-Order Virtual Machine (HVM)

#35

Post by LightMachine » Tue, Mar 28, 2023, 6:27 PM UTC

scotty79 wrote: post #7

For anyone interested how interaction nets work here's how one would program them directly: https://github.com/inpla/inpla/blob/main/Gentle_introduction...

Inpla is a very interesting project that is more elegant than HVM in several regards (as it doesn't need to worry about functional programming!) and should be more known. I've added a link to it from the HVM's repo a few months ago.

Re: Higher-Order Virtual Machine (HVM)

#36

Post by _a_a_a_ » Tue, Mar 28, 2023, 7:52 PM UTC

This seems very interesting, and I like your FAQ where you get honest, but your intro almost put me off:

"be up to exponentially faster than alternatives" – hmm

"Interaction Net, which supersedes the Turing Machine" – Interaction Net link points to a paper on Interaction Combinators. And talking about superseding Turing machines is embarrassing – do you have Oracle powers? (https://en.wikipedia.org/wiki/Oracle_machine)

"set to scale towards uncharted levels of performance" – that's just a bit cringy

I've come across claims of no GC needed and I don't buy it unless in restricted domains, and it would be nice to have a link towards what you mean by 'beta optimality'. I would like to see the sort benchmark being done something realistic (recursive bubble sort, the two words together don't look good). Also automatic parallelism..., Immutability apparently for free, everything higher-order, it seems you hit a lot of holy grails in one go. Rather too many for me to feel comfortable.

The FAQ by contrast is a whole lot more reasonable and upfront, perhaps be careful about overselling yourself?

Re: Higher-Order Virtual Machine (HVM)

#37

Post by sroussey » Tue, Mar 28, 2023, 8:19 PM UTC

LightMachine wrote: post #33

nerpderp82 wrote: post #22

Earlier quoted context omitted.

What are your thoughts around WebAssembly, Typed Assembly [1] and will you be using BlueSpec [2] to implement these ideas in hardware? [1] https://www.semanticscholar.org/search?q=typed%20assembly%20... namely, Greg Morrisett and Neal Glew's work https://www.semanticscholar.org/author/J.-G.-Morrisett/14364... https://www.semanticscholar.org/author/MorrisettGreg/1643921... (semantic scholar incorrectly thinks there ar…

I love WASM - who doesn't? Maintaining a WASM target was included on HOC's current fundraise, and is essential to our JIT plans. I don't know much about typed assembly, but I guess it would enable optimizations that aren't possible without types, as well as increased safety - although I wonder if that's relevant, if the source language is already typed? In general though, I think we should move away from procedural i…

The slowing of Moore’s Law was going to eventually lead to the loosening of the stranglehold that Von Nuemann machine design has on the industry. I’m glad to see things like this!

Re: Higher-Order Virtual Machine (HVM)

#38

Post by LightMachine » Tue, Mar 28, 2023, 8:56 PM UTC

_a_a_a_ wrote: post #36

This seems very interesting, and I like your FAQ where you get honest, but your intro almost put me off: "be up to exponentially faster than alternatives" – hmm "Interaction Net, which supersedes the Turing Machine" – Interaction Net link points to a paper on Interaction Combinators. And talking about superseding Turing machines is embarrassing – do you have Oracle powers? ( https://en.wikipedia.org/wiki/Oracle_machi…

I agree with most of your points, we should definitely rewrite and tone down the README. The FAQ was written a few months after, due to that kind of negative reception. To address your points, note that by "superseding" the Turing Machine, I do not mean they can compute uncomputable functions! The meaning is that, while both are equivalent in terms of *computability*, Interaction Nets have improved *computational* characteristics, such as strong confluence and concurrency. This is a very technical aspect that is addressed on the paper I linked. Regarding not buying the claim of no GC needed, this is interesting, since this is a well stablished result: HVM is entirely linear, so it can avoid global GCs for the same reason as Rust. The difference is that HVM is more inherently high level, since its support for lambda is way more first-class than Rust's closures, which are comparably slow and almost guarantee borrow-checker hell.

Re: Higher-Order Virtual Machine (HVM)

#39

Post by lliamander » Tue, Mar 28, 2023, 9:53 PM UTC

How does the compiler know which parts of the code can be run in parallel?

My understanding is that while parallelism (actually executing instructions simultaneously) is a property of the runtime, it depends upon concurrency (the separation of computations as independent) which is always something that has to be specified in the program source code.

Erlang has a similar property of "scaling with core-count for free" provided you write your program with a prodigious use of processes (which Erlang makes very easy and idiomatic). How is it that HVM is able to identify independent computations?

I admit to being only passingly familiar with Haskell-style FP, so perhaps the answer to my question is obvious.

Re: Higher-Order Virtual Machine (HVM)

#40

Post by stefanha » Tue, Mar 28, 2023, 10:11 PM UTC

Can someone explain or share references on how HVM (or GHC or similar computational models) beat optimized compiled imperative languages like C, C++, or Rust?

I took a quick look at the HVM runtime and can vaguely make out the shape of the memory and code that reduces terms. While it's cool to have a computational model that evaluates everything only once and avoids duplicating computation, if it does not compile programs to machine code to exploit hardware, then the single-core performance will be worse than C/C++/Rust.

Something that generates a few machines instructions in C/C++/Rust requires reducing a graph of terms - many CPU instructions for each reduction and many memory accesses that may have poor locality.

Is the idea that programs contain enough parallelism that is out of reach of human programmers so that HVM will make up for the single-core performance drag through parallelism?

Maybe I'm missing what the HVM compiler does?

Maybe hardware acceleration with FPGAs or ASICs could be applied?

In other words, can this beautiful and elegant computational model be implemented with efficiency that matches C/C++/Rust?