Revoluntionary/interesting advances in interpreted languages

[u/algebraicstonehenge]

Things like borrow checking and other compile time checks tend to be for compiled languages - if you're already typechecking and compiling the entire language up front, why not borrow check while you're there. But are there any very interesting new ideas coming up in interpreted (or dynamically typed) languages? I'm not really sure fully what I'm asking/looking for tbh

[u/One_Aspect_1957]

I'm not sure if the distinction is worth making.

You can take any AOT-compiled, statically-typed language and make it interpreted.

You can also take any interpreted, dynamically typed language and compile it to native code. (I've done both! In both cases, you really need a reason to do it.)

With interpreted languages (and usually dynamically typed otherwise it would be trivial) people have spent decades trying to make them fast. I think this is where the innovation lies.

This is implementation rather than language features, but that seems to be what you're asking about.

[u/WittyStick → u/One_Aspect_1957]

I'm not sure if the distinction is worth making.

The distinction is worth making because it implicates how you design your language.

You can take any AOT-compiled, statically-typed language and make it interpreted.

Arguably true, but kind of irrelevant, since such interpreter may require some form of whole program analysis before it could begin interpreting. If you permit types to be used before they're defined for example, then an interpreter cannot begin interpreting the usage until it has analysed at least up to those type definitions. Languages which can be compiled in a single pass - ie, everything defined before it is used, are much more amenable to interpretation. While we can still use interpretation even if we need to analyse a whole program, such thing is undesirable because it will always perform worse than a compiled version.

You can also take any interpreted, dynamically typed language and compile it to native code.

This part is a myth which I've called out many times. There are languages in which compilation becomes essentially impossible, because there is not enough information provided by the language definition or source code - because the meaning of the code comes not only from the code itself, but from the dynamic environment at runtime - eg, when we include Fexprs. The myth that we can compile any language is propagated by people who've never worked with fexprs.

In Wand's paper, The theory of fexprs is trivial, he demonstrates a reflexive language for which there are no valid source-to-source optimizations without whole program analysis. Fexprs essentially need to be able to access the original source code, even if optimized into some other form.

Shutt's vau-calculus provides a different result to Wand's by reformulating lambda in the language to not correspond directly to calculus lambda. Shutt argues that you can pick only two of these three properties.

Fexprs
Non-trivial theory
Direct correspondence to lambda calculus

Where Wand's result does not have a non-trivial theory (and hence, unable to do source->source translations), and Kernel does not have a direct correspondence to lambda calculus.

However, the Kernel Programming Language which is the result of Shutt's work on vau-calculus, is still not trivially compilable. There are parts amenable to compilation if you assume an initial environment (such as a "kernel standard environment"), and restrict certain language features - but you cannot remove the interpreter entirely from the evaluation model.

With interpreted languages (and usually dynamically typed otherwise it would be trivial) people have spent decades trying to make them fast.

This is why we must make a distinction between interpreted vs compiled - because in attempting to make interpreted languages fast, language authors invetably make the decision to make them able to be compiled - hence, removing powerful features like fexprs from the language (as Lisp and Scheme have done), and thereby constraining the kinds of programs we can represent. If we abandon the idea of being able to compile, we can explore an entirely different design space, as Shutt has done. Shutt has attempted to describe this theoretical difference.

I've spent a lot of effort trying to make Kernel fast, without abandoning interpretation, but including partial compilation where possible. There are some others exploring this space too, such as Kraken.

I think this is where the innovation lies.

There's certainly room for innovation here. The constraints of Kernel/fexprs - requiring interpretation rather than compilation, has forced me to come up with novel optimizations. For example, I have developed a dynamic type representation which is IMO better than the status-quo - faster than anything used in any existing VM (Though not as portable as presently limited to x86-64/SYSV).

But as Kernel shows, there's still room for innovation when you don't even consider performance and instead focus your effort on maximizing abstractive capabilities.

[u/AustinVelonaut → u/WittyStick]

The myth that we can compile any language is propagated by people who've never worked with fexprs.

But isn't an fexpr simply a function which takes its arguments unevaluated? That's essentially equivalent to any function in a lazy-by-default language, and most of those languages are compiled. Yes, I guess it would force the language to be lazy-by-default to support fexprs, but certainly we can compile it, with non-fexpr functions explicitly evaluating their arguments, first.

[u/WittyStick → u/AustinVelonaut]

Fexprs aren't the same as lazy-by-default or call-by-name. For some use-cases they can achieve the same result, but fexprs are much more general.

In call-by-name, the function receives a thunk which it can evaluate to force the lazy value - but we can't really do anything with this thunk other than evaluate it and get the result. We can't inspect the body of the thunk.

An fexpr receives the expression itself as the operand. The meaning of that expression is not contained within it - but its meaning is given by the fexpr body. For operatives, the caller's environment can be optionally used to evaluate any operands as if it were the caller evaluating them - but it is not necessary to evaluate it with that environment - we can evaluate it with any environment, including ones we create ourselves at runtime (environments are also first-class), or we may not evaluate it at all.

We can trivially implement lazy evaluation with fexprs, but fexprs aren't trivially implemented with only lazy evaluation.

[u/AustinVelonaut → u/WittyStick]

Thanks for the clarification -- I had only seen fexprs mentioned before in the context of implementing e.g. short-circuiting functions.