Explanation in more simple terms

[Dimev]

This seems like a very cool project, and I'm trying to understand how it works.

I've dabbled with haskell and lambda calculus before a bit, but I lack a lot of the theoretical background behind both to really understand what's going on.

So from what I understand it's based off of interaction calculus, which is like lamba calculus but different semantics and more explicit cloning?

And then where does the rule rewriting come from?

[zicklag]

This repo had a somewhat higher level explanation that helped the concept make more sense to me:

https://github.com/VictorTaelin/absal-ex

[Dimev]

So instead of using lambda calculus you use interaction nets, which has 2 rewriting rules:

• annihalation
• duplication

and turns out there's a good parallel way to implement those.

and then the HVM language gets compiled to that and run?

Still not entirely sure how interaction nets here can work as computation tho.

[zicklag]

Yeah, that's my understanding so far. Apparently interaction nets can be used to implement a subset of Lambda Calculus.

If you want to understand the basics of Lambda Calculus I found this site to be extremely helpful: https://lambdaexplorer.com/.

I'm not exactly sure what the node labels and such mean in the interaction nets, but it looks like it might be a way to represent substitution, similar to lambda applications in lambda calculus.

I'd like to undertand it better myself, so maybe I'll look into it more if I get the chance and try to write a higher-level introduction blog post.

It'd be great to supplement with some animated and/or interactive demos of how to take HVM/lambda calculus and convert it to interaction nets and then see the interaction nets collapse, and such.

[Dimev]

ye, that would be pretty cool.

[zicklag]

I just published a blog post: Interaction Nets, Combinators, and Calculus off of my recent research. Let me know if it helps, and if you have any feedback!

[Dimev]

Thanks! That does seem to clear up some parts at least.

[chkoreff]

In my Fexl project I have implemented a production quality scripting language based on lambda expressions, and I've been using it almost exclusively in our business for about 8 years.

I just thought I'd mention it since you're talking about lambda interpreters:

https://github.com/chkoreff/Fexl

[chkoreff]

If you want to understand the basics of Lambda Calculus I found this site to be extremely helpful: https://lambdaexplorer.com/.

I tested vulnerabilities there, first with a classic infinite loop (the fixpoint of the identity function):

((\f.(\Q.Q Q)(\x.f (x x))) (\x.x))

That one did fine, terminating with "Normal form execution exceeded. This expression may not terminate."

Good so far. But then I plopped in what I call the "Metastasis" function which runs forever and continually eats up more memory:

((\Y.(\S.Y S S S) (\x.\y.\z. (x z) (y z))) (\f. (\Q. Q Q) (\x. f (x x))))

WARNING: THAT ONE IS EVIL. If you run it and watch "top", you'll see your browser process running at 100% CPU and eating up gigabytes of memory. You have been warned.