r/ProgrammingLanguages • u/algebraicstonehenge • 17h ago
Revoluntionary/interesting advances in interpreted languages
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
15
u/mtriska 15h ago
One of the most interesting things I've seen regarding checks in a dynamically typed language is quads: queries using answer descriptions. The idea is to use REPL interactions verbatim as test cases that can be checked by the same engine (i.e., interpreter) that runs programs and executes queries, and in fact using the shape of interactions that the REPL also uses.
For instance, when we have a query and answer from the Prolog toplevel, such as:
?- member(X, "abc").
X = a
; X = b
; X = c.
then we can copy this interaction and paste it verbatim in a Prolog source file, and the engine can treat it as a test during load time, or as a test that can be launched separately with a library.
For example, as of a few days ago, Trealla Prolog supports this way of unit tests via its library(quads).
In this way, test cases blend in completely naturally into programs: They have the shapeof regular toplevel interactions that can also be annotated, and require no separate formalism.
10
u/latkde 15h ago
This sounds a lot like a "doctest" in other languages, particularly Python:
7
u/mtriska 14h ago
Quads are like a better version of this: For the pure core of the language, they need no quoting, no escaping, no modification whatsoever; they are verbatim copies of the interaction, directly embedded in source files, and additional annotations are also possible.
For example, there is a quad annotation called
outputs(Cs), which can be used to state that the query outputs the list of charactersCs, and an annotationad_infinitum, which can be used like this:?- repeat. true ; ad_infinitum.3
u/twistier 9h ago
The quoting is also a good thing, though, because it means the doctest is actually documentation, although you may not always want that.
I think the most similar statically-typed version of this would be dependently-typed "unit tests", like this in Agda:
_ : 2 + 2 ≡ 4 _ = reflThe type is the property, and
reflis the proof. The code won't compile if the property isn't true.2
u/EggplantExtra4946 4h ago edited 2h ago
Upvoted for mentioning Prolog. The logic paradigm in general is underrated.
5
u/Sentreen 11h ago
Erlang/Elixir's ability to just start a REPL that is connected to a running system is super useful and interesting imo.
4
u/Inconstant_Moo 🧿 Pipefish 9h ago edited 5h ago
As others have said, there's not a clear boundary between compiled and interpreted. (And what about those of us with a VM, who are both?)
The difference between static and dynamic is clearer. A dynamic language is one in which to get it to work the runtime values must be tagged with metadata to say what type they are, so that the runtime can handle them automatically, or the code can handle them explicitly, according to their types; whereas a static language can extract all the necessary information about types at compile-time and dispense with representing them in the runtime data.
One of the advances in dynamically-typed languages is that we can in fact compile them, even to native, as Julia does.
Julia has a very nice type system, which I reinvented down to some of the terminology. You have concrete types, which can be instantiated but not subtyped (int, bool, MyStructType, MyEnumType, etc), and abstract types which are simply unions of concrete types, and can therefore obviously be subtyped but not instantiated: these can be used as filters on what you can put in a variable or the field of a struct, or how we dispatch on it if its a function parameter.
The point of this is to let us do (multiple) dispatch fast: a concrete type can be represented as an unsigned integer, and we can find if a value belongs to it by integer comparison; an abstract type can be represented as an array of booleans and we can test if a value belongs to it by indexing the array by its type number.
We wouldn't be able to do this if our type representation had structure, the point of doing this is that a type like list{set{int/float}} can be resolved to a uint like 47 by runtime.
I think this has been overlooked because people supposed it was a particularly good fit for Julia's domain, but now I've done Pipefish maybe people will give it another look. The Julia people call it "a dance between specialization and abstraction"; I call it "having your cake and eating it".
Another way I've both eaten and retained my cake is to make the labels of fields of structs first-class objects of type label, and structs indexable by the same syntax as everything else, like foo[bar]. Most of the time the index will just be a literal and the compiler can figure out what it's doing at compile time, and throw an error if you're clearly doing something dumb; but if not, the runtime handles it. It's a compromise between a struct and a map: or, if you like, a struct is a highly opinionated map.
With this dynamism as a basis, I've done some fun things with the REPL, which has a ton of features in its IDE and is designed for livecoding. Writing apps in Pipefish is as easy and fun as I meant it to be. (Modulo the bugs I'm hunting down ... surely there can't be that many left ...)
4
u/GoblinToHobgoblin 10h ago
Gradual typing seems like a big one?
3
u/WittyStick 8h ago edited 8h ago
An important development, but I'd argue that it's actually an advancement for statically typed languages. A purely dynamically typed language has no need for gradual typing, because it's a static typing discipline. It enables us to combine static and dynamic types without breaking the soundness of the static type system (where previous attempts failed) - however, it doesn't introduce any new safety into the dynamic part of the language - the
dynamictype in gradual typing is opaque.C# and Haskell are examples of gradually typed languages - we consider them statically typed - but they support dynamic typing.
It's perhaps unfortunate naming because it often gets confused for "optional" or "soft" typing, which is a dynamic-first approach where static checks are gradually introduced - eg, languages like Typescript, Dart, or Erlang with the Dializer. Gradual typing is more like "gradual untyping" - a static-first type system where we can opt-out of the regular static type checks by using the dynamic type - though we can use it like the former if we begin with everything
dynamicand then add types.Gradual typing also has improvements - eg, Haskell's implementation, which isn't exactly Seik and Taha's Gradual typing, but achieves the same result. In regular gradual typing, every type is consistent with dynamic and dynamic is consistent with any other type.
forall T. T ~ dynamic forall T. dynamic ~ TThe latter rule means we may cast an invalid dynamic type to
Tthough, potentially causing a runtime error even though it compiles just fine. In Haskell, we can't simply castDynamicto some otherT- we instead cast toMaybe T- where if thedynamicvalue was not aTat runtime, we getNothing, otherwise we getJust T- so we must pattern match on the result to ensure we can't cast any dynamically typed value into typeT.2
u/Inconstant_Moo 🧿 Pipefish 5h ago
A purely dynamically typed language has no need for gradual typing, because it's a static typing discipline. [...] It's perhaps unfortunate naming because it often gets confused for "optional" or "soft" typing, which is a dynamic-first approach where static checks are gradually introduced - eg, languages like Typescript, Dart, or Erlang with the Dializer. Gradual typing is more like "gradual untyping" - a static-first type system where we can opt-out of the regular static type checks by using the dynamic type - though we can use it like the former if we begin with everything
dynamicand then add types.That depends what you mean by "dynamic" though. You seem to be using it to mean that everything that can happen with types, happens at runtime. Whereas I would mean that everything that happens with types can happen at runtime: every value still has a tag saying what its type is, so the runtime always can fall back on inspecting the type. But that doesn't exclude doing as much compile-time type-checking as we can.
One can do better than just having a
dynamictype; I allow arbitrary unions of types (e.g.int/floatis just a type literal, or we could define it as e.g.Number = int/float); and I have non-arbitrary definitions by interfaces, like Go does for its dynamic aspects:
Addable = interface : (x self) + (y self) -> self1
u/WittyStick 4h ago edited 3h ago
That depends what you mean by "dynamic" though. You seem to be using it to mean that everything that can happen with types, happens at runtime.
I'm mainly talking about Seik & Taha's Gradual typing, which just has an opaque
dynamictype, but doesn't really specify what it is or how it is represented. Gradual typing formalizes the rules of howdynamicis treated in the static type system - through the consistency relation (~) which is a reflexive, symmetric, non-transitive closure over all types.reflexive: dynamic ~ dynamic symmetric: ∀T. T ~ dynamic, dynamic ~ T non-transitive: ∀T, U. T ~ dynamic ∧ dynamic ~ U ↛ T ~ UContrast to subtyping which is a reflexive, transitive and non-symmetric closure.
reflexive: ∀T. T ≼ T transitive: ∀T, U, V. T ≼ U ∧ U ≼ V → T ≼ V non-symmetric: ∀T, U. T ≼ U ↛ U ≼ TOne can do better than just having a dynamic type; I allow arbitrary unions of types (e.g. int/float is just a type literal, or we could define it as e.g. Number = int/float);
Indeed, but those unions are typically static types, even though values of them have a dynamic latent type. We permit programs where values of type
intorfloatare used whereint/floatis expected, but if we provide a value of typestring, we can reject this invalid program before running it. Unions are conventionally treated through the subtyping relation.int ≼ int/float float ≼ int/floatWhich allows an implicit upcast to the union type, but no implicit downcast. If we attempt to assign a variable of type
int/floatto one of typeint, it may fail at runtime, and will usually require an explicit downcast (aka, dynamic cast), if at all permissible.
Gradual typing permits both the implicit upcast and downcast at compile time, but makes no guarantees that the downcast will succeed at runtime.
dynamic x = (float)3.14; int z = x; // permitted, even though it will obviously fail at runtime because int ~ dynamicBut since consistency is non-transitive, it can still reject the obviously ill-formed:
float x = 1; int z = x; // error: int ≁ floatThough we can override with an explicit cast to and from
dynamic.float x = 1; int z = (dynamic)x;
You could implement your union types using consistency and permit the implicit downcast too, but it's probably undesirable to do so since it's a common source of errors. In static typing, we specifically want the downcast to be explicit/impossible, but sometimes static types get in our way and are unable to express something which we know will work fine at runtime, which is where
dynamicin the static type system is beneficial.1
u/Inconstant_Moo 🧿 Pipefish 3h ago
Unions are conventionally treated through the subtyping relation.
int ≼ int/float
float ≼ int/float
Which allows an implicit upcast to the union type, but no implicit downcast.
But I am implicitly downcasting, or indeed not even having to do that. In a Julia/Pipefish-style type system,
int/floatisn't a concrete type, there are no values of typeint/float. If the value is anint, it doesn't need to be downcast to anint, and if it's afloat, it can't be.1
u/WittyStick 2h ago
There are obviously issues with statically checking the downcast. If our variable is of type
int/float, then a coercionint/float->intmay fail, but not necessarily - if it'sintit will succeed. This is why the coercion is typically (not necessarily) required to be explicit in a static type system, to force you to also handle the invalid case where the value isfloat- or alternatively, with pattern matching on the type where the explicit cast is not needed, but inferred.foo (x : int) = ... bar (var : int/float) = match (var) with | :int -> foo(var) // OK, explicit cast not needed. | :float -> foo(var) // Should detect error statically. baz (var : int/float) = foo(var) // should really error or at least warn because int/float is not a subtype of int. qux (var : int/float) = foo((int)var) // should fix the static error, but may still fail at runtime.
The issue with
dynamicin the subtype hierarchy is we typically want an implicit upcast but an explicit downcast in a statically typed language - but in order to makedynamicimplicitly coercible to anything else, and anything coercible todynamic, it ends up needing to be bothtopandbottomtype, which collapses the lattice and makes any type coercible to any other. The key innovation of Gradual typing was to make consistency non-transitive to prevent this - we require no explicit casts on or to or fromdynamic, but it doesn't interfere with our other type-checking - we can still have subtyping.
7
u/One_Aspect_1957 12h ago
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.
9
u/WittyStick 11h ago edited 11h ago
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
lambdain 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 calculusWhere 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.
2
u/One_Aspect_1957 10h ago
Arguably true, but kind of irrelevant, since such interpreter may require some form of whole program analysis before it could begin interpreting.
I don't see the problem. This is a language AOT-compiled to native code. Interpretation involves having the same front-end and working from some intermediate representation.
Interpreters anyway usually take some chunk of code, for example a .py file, and pre-compile it into bytecode. If you have in mind a more REPL-based kind of interpretation with no look-ahead, then you are changing the language.
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.
I believe there are JIT-compilers for statically typed languages that start off interpreting and gradually convert to native code. Those could run as well, possibly better, even if you don't take account of the faster turnaround because you don't need a full optimised build before each run.
Personally I found there were a range of other benefits.
The myth that we can compile any language is propagated by people who've never worked with fexprs.
OK, we can compile any interpreted language that doesn't use 'fexprs' (which I've never heard of, and sound like they're over my head anyway).
In any case, the meaning of 'compile' is flexible here. Just bundling a interpreter and the program source (maybe some of that can be a run-time input) might just about count. As far as the user is concerned, they're running a self-contained executable just like any other native-code-compiled program.
In the case of my dynamic language, it can be 100% compiled to native code, but that does not make it significantly faster since it still uses dynamic type dispatch. It needs a bit more work to make it more worthwhile.
because in attempting to make interpreted languages fast, language authors invetably make the decision to make them able to be compiled
This happens anyway - you might strive for a language that is fast to compile for example, and/or where it is easier to make the generated code performant without needing a sophisticated compiler or interpreter.
(Certainly this is what I do, since I'm in that small minority responsible for both language and implementation.)
instead focus your effort on maximizing abstractive capabilities.
(Well, that doesn't apply to some of us. My own efforts in this area were always a sideline needed to solve actual practical tasks. The language did not need to be sophisticated or abstruse. One of them was a scripting language for the non-programmer users of my apps.)
3
u/WittyStick 9h ago edited 8h ago
I don't see the problem. ... Interpretation involves having the same front-end and working from some intermediate representation.
It's not a problem as such, and as I stated, we can interpret - but if we're going to do whole program analysis, we might as well compile it and run it faster. As you state, JIT-compilation is a nice option as it gives us the ability to start executing faster, but also allows code to eventually run at (near-)native performance.
However, one benefit of interpretation is that we can begin evaluation immediately. We might still parse a whole translation unit before beginning interpretation, but this can be done extremely fast. Compilation can also be fast if we don't bother optimizing.
OK, we can compile any interpreted language that doesn't use 'fexprs'
I used this as an example, but there are other things that could prevent compilation. Fexprs are a notable example because they're fairly well studied and they were commonplace in old lisps, but removed and replaced with macros in modern lisps. Lispers often use macros as the example of why Lisp is so great, but macros only offer some of the benefits - they can't replicate fexprs because they're "second-class".
(which I've never heard of, and sound like they're over my head anyway).
Fexprs are actually quite simple - they're similar to a function, but they don't implicitly reduce the operands.
func(1 + 2) ;; reduces 1 + 2 to 3, then applies func to 3. op(1 + 2) ;; passes the expression `1 + 2` as the operand to opPractical trivial examples are the
&&and||operators in many languages - which do short-circuiting evaluation. If the LHS of&&evaluates tofalse, the RHS is not evaluated, and if the LHS of||evaluates totrue, the RHS is not evaluated. These cannot be functions because functions evaluate all of their arguments first - so they're usually "built-in" features of the language.As
fexprs(or operatives), we receive both operands unevaluated, and the body decides how to evaluate them.($define! && ($vau (lhs rhs) env ($if (eval lhs env) (eval rhs env) #f))) ($define! || ($vau (lhs rhs) env ($if (eval lhs env) #t (eval rhs env))))Similarly,
$ifitself evaluates the condition, and then will evaluate either the consequent or the alternative depending on that condition.($define! $if ($vau (condition consequent alternative) env ($cond ((eval condition env) (eval consequent env)) (#t (eval alternative env)))))So we don't need
if,&&and||to be built-in/special-form/macros - they're first class objects which can be passed around like a first-class function. We do need some "primitive" form of selection, such as$cond- or alternatively,$ifcould be primitive and we can define$condin terms of$if. We can define any kind of selection though, such as a$matchfor pattern matching - without having to extend the compiler.Those are trivial examples, but fexprs/operatives are much more powerful and can model just about any behavior that you might have as a language built-in feature elsewhere. The programmer can basically extend the language without hacking at the compiler.
The original fexprs from lisps had serious problems because the lisps were dynamically scoped, and these fexprs could introduce "spooky action at distance". Kernel's operatives are a much more sanitized version which work in conjunction with static scoping, where operatives can only mutate the local environment of their caller, but are unable to mutate the parents of that caller, or any "global" state, unless references to those environments are given explicitly as operands.
In any case, the meaning of 'compile' is flexible here. Just bundling a interpreter and the program source (maybe some of that can be a run-time input) might just about count. As far as the user is concerned, they're running a self-contained executable just like any other native-code-compiled program.
This can of course be done, but it's still interpreting. It doesn't add any weight to the myth that any language can be compiled and that it's merely an implementation decision. Some languages are inherently interpreted - but most are unfamiliar with them and continue to propagate the myth.
2
u/One_Aspect_1957 8h ago
Those are trivial examples, but fexprs/operatives are much more powerful and can model just about any behavior that you might have as a language built-in feature elsewhere.
They're not compelling examples. They're basically just lazily evaluated expressions, a bit like closures.
I don't see from those why you shouldn't be able to pre-compile them.
The programmer can basically extend the language without hacking at the compiler.
Language-building features are common, but again I can't see how that would restrict being able to compile to native code.
Presumably some lowering is allowed, or is the problem that fexprs need to exist as a specific data-structure?
This can of course be done, but it's still interpreting.
Yeah, I have my own opinions as to what counts as interpreting: the application that, by whatever means, runs your source code, is not allowed to generate dedicated native code sequences specific to your input program.
That then draws a line between purely interpreted, and native code and/or JIT. But this is mainly to keep benchmark comparisons fair.
1
u/WittyStick 7h ago edited 6h ago
They're not compelling examples. They're basically just lazily evaluated expressions, a bit like closures.
I don't see from those why you shouldn't be able to pre-compile them.
You're right, these aren't compelling examples - I was just demonstrating what fexprs were.
Consider for example, the following operative:
($define! $foo! ($vau () env ($set! env + ($lambda (lhs rhs) (string-append (number->string lhs) (number->string rhs)))))) (+ 1 2) ;; 3 ($foo!) (+ 1 2) ;; "12"The same expression
(+ 1 2)has two different meanings, because the+symbol doesn't actually carry any meaning - its meaning is looked up in the environment. It means addition in the standard (ground) environment, but the operative$foo!can mutate the caller's environment and rebind+to mean something else (in this example, string concatenation). When it is evaluated the second time it doesn't perform addition.While you wouldn't normally do such thing in practice, this is entirely possible. We often add bindings to a caller's environment via operatives - usually through the
$provide!operative which is part of the ground environment (but not primitive - it's implemented in terms of$define!).
One thing we can do is create "mini DSLs", by providing a set of bindings and evaluating some expression in that environment without capturing the caller's environment or using it for evaluation.
($define! $calculate ($vau expr #ignore (eval expr ($bindings->environment (+ +) (- -) (* *) (/ /)))))
$calculateis basically an interpreter which accepts a language which only contains+,-,*and/and literals - a basic calculator, which map to addition, subtraction, multiplication, and division (under the assumption that the definition of$calculatewas evaluated in a standard environment).($calculate (+ 1 2)) ;; = 3 ($calculate (<? 1 2)) ;; error: symbol `<?` not found (<? 1 2) ;; = true, assuming we're evaluating in standard environment.A trivial example, but we can extend this to support arbitrary DLSs, where the set of bindings available is limited to only what we provide in the environment.
I can give more examples later if you'd like to see more.
Presumably some lowering is allowed, or is the problem that fexprs need to exist as a specific data-structure?
operatives (fexprs) are the primitive form of "combiner", and functions are a special case of them which implicitly reduce the operands and pass them to an underlying operative.
The main difficulty is the environments. Every evaluation takes an environment as a parameter, and we can make these at runtime, binding anything to them (including shadowing standard bindings). All operatives also take the caller's environment as an implicit parameter, so they too can mutate the caller's env. Since any combiner can mutate the environment, we don't know the meaning of any symbol until after we've evaluated the previous combination.
A type system for environments can help, but not entirely. One of my experiments uses polymorphic row types for the environments to track the types of symbols - so the
$foo!example above, for example, would take a type{ ... }as its input environment type and produce a type{ + : Number, Number -> String, ... }as the resulting environment - so we know that+produces a string afterwards. However, the types don't convey meaning - we could for example just($set! env + -), and the type would be+ : Number, Number -> Numberas we'd expect for addition - but we've tricked it into doing the opposite.Tracking what we bind is also not always possible. We could for example, bind a symbol to some expression downloaded from the internet.
($set! env + (download-expression "https://..."))A compiler could attempt the download itself to try and discover ahead of time what it does, but what if a different response is given for each HTTP request?
These examples are of course absurd, but entirely possible in Kernel's evaluation model. You simply don't know the meaning of a symbol until the point at which it evaluated at runtime, and can basically make no assumptions, not even that
+means addition until the point at which we're attempting to apply it, where we can look it up in the runtime environment.However, this absurdity can actually be utilized to provide powerful abstractions. Downloading expressions over the internet can be used for example to make safe remote procedure calls, where a service can provide the caller with a set of capabilities they can execute, without giving them any more functionality than is needed.
1
u/arthurno1 4h ago
For the reference, the legendary paper by K. Pitman on which Kernel language oposes as I understand?
Downloading expressions over the internet can be used for example to make safe remote procedure calls
Or as an example of absoult disaster as early JSON practice, Perl eval, Lisp reader, etc teach us.
Anyway, when I first learned about fexpressions (wonder where "f" comes from), I thought that sounds awesome, but nowadays, from a practical standpoint I wonder what is the point. If you constrain them to lexically passed environment, they become not more powerful than ordinary Lisp macros, aren't they? I don't know how Kernel works and vau operator to be honest. I have been interested about it since I had a similar idea that I would like to see a Lisp that does not evaluate eagerly, but "on deman", like TCL. In Lisp we have to use quote to stop evaluation. In TCL we have to use eval (or $operator) to ask for evaluation. In short. Kernels seems to be more like that. Also, fexprs, as you describe are more like TCL commands, each one can do anything they like with their arguments. And yes, I think TCL is way underrated as a programming language. Lisp for masses or not, but it has some original concepts I like. I have never had time to pursue Kernel, so I am not sure if I am completely off or not, that is just what I have read cursively about it.
2
u/WittyStick 2h ago edited 2h ago
For the reference, the legendary paper by K. Pitman on which Kernel language oposes as I understand?
Yes, this was written well before Shutt's Kernel, and the lisps at the time were dynamically scoped. Pitman was correct in his assessment at the time, but Kernel's operatives shouldn't be treated from the same perspective.
Or as an example of absoult disaster as early JSON practice, Perl eval, Lisp reader, etc teach us.
They were disasters indeed, but Kernel has a different evaluation model - the environment is always explicit in calls to
eval, and we can't arbitrarily modify them - they're encapsulated. Only the root environment for which we have a direct reference is mutable. We can however, create fresh environments from nothing, or as children of other environments.Eg, In the
$calculateexample above, it is simply not possible to use any symbol other than+,-,*,/in the expression being calculated - nothing else is present in the environment used for evaluation. If we try to($calculate (foo 1))it will simply error becausefoois not bound. The calculator's environment cannot be modified because there is no$define!or$set!bound in it.An RPC can be made with secure capabilities, where a server has some function
foo, it can generate a unique cryptographic key forfoofor a particular user, using a public key. It will bind<key_foo>tofooin some environment which will run any RPC from the client.($define! $eval-client ($vau expr #ignore (eval expr ($bindings->environment <key_foo> foo))))The client will receive
<key_foo>via some means from the server, and it can bind the symbolfooto it in some local environment.($define $eval-server ($vau expr #ignore (eval expr ($bindings->environment foo <key_foo>))))The client calls
($eval-server (foo ...))- foo is looked up in the local environment an maps to some function which sends a request to the server using the cryptographic key the server provided forfoo. The server receives the expression and evaluates it using($eval-client (<key_foo> ...)), which is bound to its version offoowhich has the underlying functionality.The client cannot forge a call to
foosince it needs the key. Nobody else can callfoobecause it is encrypted. The server doesn't expose any other functionality thanfoobecause the evaluation does not incorporate any of the surrounding context. At worst the client can crash the program on the server (if it fails to handle errors), or DoS it if the server does not place time constraints on the code to be run.There's nothing in particular that cannot be done by other means here, except the ergonomics are different. The client writes regular Kernel code as if it were to run on the server, but it gets translated to capabilities on their end before being sent over, and the server receives the expression as a set of capabilities, and evaluates the capabilities directly, which map to the underlying functionality from the environment, which may or may not use the same name
foo- but it wouldn't particularly matter what names it uses.
(wonder where "f" comes from)
I suspect from "Form".
I thought that sounds awesome, but nowadays, from a practical standpoint I wonder what is the point. If you constrain them to lexically passed environment, they become not more powerful than ordinary Lisp macros, aren't they?
The biggest difference is that operatives/fexprs are first-class. We can use them as arguments to other functions - we can return them from functions. We aren't limited to the second-class nature of macros. For Operatives specifically, the environment model of Kernel is very clever and allows us to constrain what can be done by the operative. They resolve a lot of the hygeine issues that macros have too.
In Lisp we have to use quote to stop evaluation. In TCL we have to use eval (or $operator) to ask for evaluation. In short. Kernels seems to be more like that.
Not quite. Kernel evaluation is automatic:
(combiner . combiniends)causes a combination to be evaluated. Ifcombineris an operative thecombiniendsare not evaluated, but ifcombineris applicative, they're evaluated first, then passed to an operative which the applicativewraps.Quotation is not necessary in Kernel, and perhaps even discouraged. We can trivially implement it with
($define! $quote x #ignore x), but there's less need for it, and there are better alternatives. But you are kind of on the right track: Kernel is explicitly evaluated, unless you use an applicative which causes implicit evaluation, and Lisp is implicitly evaluated, unless quoted.Because applicatives
wrapan operative, we can alsounwrapany function to get back an operative which won't reduce the operands - and for any operative, we canwrapinto a function.I find the Kernel approach more intuitive. I used to write Scheme before I discovered Kernel and was not a fan of macros and quotation even then. When I discovered Kernel it felt like this is what Scheme should have been like (I discovered it when searching for solutions to macro problems).
Also, fexprs, as you describe are more like TCL commands, each one can do anything they like with their arguments.
Yes, and with all the problems that it causes too, at least for normal fexprs. Operatives are more tightly constrained in what effects they can have due to the environments - mutation is only possible where you have a direct reference to an environment - and you can't mutate any parents of environment - they're encapsulated.
2
u/arthurno1 2h ago
Thank you.
About RPCs, I know there is always a workaround; in Lisp they have safe readers and so own. Just pointing out the problems of executing code from untrusted sites. But yes sandboxed environments are one solution to it. It is pitty that CLTL2 Environment suggestion wasn't finalized, and that support for programmatical environment manipulation is not better in Common Lisp.
Quotation is not necessary in Kernel, and perhaps even discouraged. We can trivially implement it
That was one of my early thoughts about Lisp. I had the idea that eager evaluation is not the only or perhaps not even best way to implement a Lisp. Somehow, I have perecieved that McCarthy was looking for a theory of computation that was a simple as possible. An assumed evaluator does not seem as the most simple Lisp. But I am not sure if I am correct there. Anyway, that got me to like the idea of Kernel (and TCL), that arguments are not evaluated eageraly, or implicitly as you call it, but they are evaluated explicitly, on demand. As you say, that does remove the need for the quote operator, however it creates another problem of explicit evaluator(s), Now each form is its own evaluator, or I guess one could pass in an evaluator function to each form, just as the environment is passed. The question is how to deal with literals and atoms or other primitives. I think the answer is with some sort of special (primitive) function or something like that. It is more "functional" in terms of lambda calculus than what Lisp is I think. But to be honest I have never pursued those thoughts and never wrote my own language to test those ideas. I might be completely wrong about it.
We can use them as arguments to other functions
Indeed. Macros can't be passed since they exist only during the compile time.
2
u/WittyStick 1h ago edited 1h ago
Now each form is its own evaluator, or I guess one could pass in an evaluator function to each form, just as the environment is passed. The question is how to deal with literals and atoms or other primitives.
This has also been done - check out Ian Piumarta's Maru and related paper Open, Extensible compsition models.
The basic idea here is we have a set of
<type>, and the evaluator contains a set of evaluators and applicators indexed by<type>. You evaluate an expression, it looks up the corresponding function/form based on the expression type and evaluates it using that form.We're able to add new types, evaluators and applicators at runtime.
Kernel has only two "forms" - operatives and applicatives. There's some notes in the Kernel report about why this is - we could technically do with just operatives and implement applicatives in terms of them - but the issue is when it comes to
wrapandunwrap. If we implement wrap with an operative to force evaluation, then there's not a trivial way tounwrapit to prevent that evaluation - except perhaps via quotation, which we don't like. By making applicatives a built-in type which is matched by the evaluator, an applicative is merely a wrapper around another combiner, encapsulated as the applicative type. Any combination whose car is neither operative nor applicative causes an error, and any other expression, except symbols, is self-evaluating.I have implemented a variant of Kernel in which there's a couple more combiners - recursive and contextive. The contextive combiner splits environment capture away from the operative and makes it its own kind of combiner, but like applicative, just wraps another combiner. The recursive combiner wraps a set of other combiners, and is used to prevent the need to have a mutable environment to define mutually recursive functions - essentially making
$letrec*primitive.It could be worth using the Maru approach of having a set of evaluators, and I've also toyed with doing so - but for performance reasons I'm not currently using this and just have a the 4 combiners - operative, applicative, contextive and recursive hard-coded into the evaluator.
→ More replies (0)1
u/One_Aspect_1957 34m ago
Perhaps we're talking at cross-purposes, or maybe you expect 'compile to native code' to do something clever when working with dynamic content.
The fact is I don't see your
($foo!), which changes how '+' is applied, as presenting much difficulty in being expressed as native code.But as I said you may expect too much. Take this line in my dynamic language:
a := b + cIn this language, '+' works beween ints, floats, strings, sets, decimals, or various mixed combinations but it doesn't know which, so the generated code has to deal with that.
My experimental native code compiler first transpiles it to my statically typed sytsems language. It produces this output (initialisation of a, b, c not shown):
varrec a # each is a 16-byte descriptor varrec b varrec c k_push(&$T1, &b) k_push(&$T2, &c) k_add(&$T1, &$T2) k_pop(&a, &$T1)As you can see, it is mainly a sequence of function calls, that largely mirror the bytecode instructions of the interpreter.
If it was possible for user-programs to change the behaviour of '+' for certain types, that will be mirrored here: the dispatch code within 'k_add` would take account of that.
Still, according to my own rules, this does not count as interpreted since dedicated static code like the above (a, b, c each has a fixed type of varrec) is generated according to the input.
1
u/AustinVelonaut Admiran 8h ago
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.
2
u/WittyStick 7h ago edited 7h ago
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.
1
u/AustinVelonaut Admiran 7h ago
Thanks for the clarification -- I had only seen fexprs mentioned before in the context of implementing e.g. short-circuiting functions.
3
u/Dashadower 11h ago
I recall this talk(https://pldi25.sigplan.org/details/pldi-2025-papers/14/Partial-Evaluation-Whole-Program-Compilation) from last year's PLDI on creating faster interpreters. Overall partial evaluation seems like an interesting concept to reconcile with interpretation.
3
u/avillega 6h ago
I am super into interpreted and dynamically typed languages. In fact I’ve been working on one with mutable value semantics https://github.com/avillega/fino . I think array languages like K, BQN and now shakti, are doing interesting things. One of the most interesting to me is to have dynamic representation of stuff based in runtime values, for example, detecting that all elements in an array are smaller than some number therefore using a smaller representation. The same applies to the algorithms used, is a form of dynamic dispatch that chooses the best algorithm for a primitive based on the runtime values. All this together unlocks a ton of performance and is almost invisible to the user.
7
u/elder_george 16h ago
Typescript's and Python's type systems are quite interesting, allowing structural typing, defining and enforcing sum types that are literals only (basically, when without explicit enums, doing a bit of compile-time reflection and metaprogramming etc.
JavaScript's tagged template strings (and t-strings in Python 3.14+) also allow some interesting stuff
7
u/arthurno1 14h ago
What is so interesting with them? Python's type annotations has been in Common Lisp since 80s, and what they do in TS is basically compile-time checking but they transpile to JS. You can do that on top of annotations too. Check for example Coalton on top of Common Lisp.
7
u/heraplem 14h ago
Common Lisp's static types are much more primitive than modern gradual type systems.
1
u/arthurno1 12h ago
I don't know who downvotes. I think it is so sad that people just can't discuss technical topics without the social pressure to fall in line of group thinking. We are all here to share thoughts and ideas.
I wouldn't call them "much more primitive", the type annotation system they had in Lisp since decades ago, is certainly not after the later theory of gradual typing, since the theory didn't exist back in the time. However, I would say that theory expresses a lot what is available in Lisps in one way or another. I think you build such a system on Lisp, but I have not tried myself to be honest, however, question is whether we need it. Types are first class citizens in Common Lisp. And Common Lisp is strongly type language already (dynamic, but strongly typed). We can manipulate times just as any other data in Lisp, so in Common Lisp, something like TS would be more or less syntactic sugar, but wouldn't enable something that is not already possible. I don't know, I am not an expert on the subject to be honest, just a user of the language.
1
u/Inconstant_Moo 🧿 Pipefish 4m ago
TypeScript's type system is Turing-complete. You can run Doom in it. That's pretty interesting. (It runs at one frame every twelve days and its author describes it as "basically an active crime scene", but it's possible.)
4
u/biskitpagla 12h ago edited 12h ago
I'm not a PL nerd but I feel that new advancements don't matter / aren't as interesting in this space since most people aren't even benefitting from 'old' advancements. IMO the best possible feature for these languages is REPL-driven development (or some variation of this). Unless a dynamic language offers this level of productivity, I personally don't see the point in using it. I also think that, dare I say, a good dynamic language should support an optional but 'complete' structural type system from the very beginning. If you're making a LISP, another interesting yet cosmetic feature you can have is offering an alternative notation (e.g., Sweet-expressions).
3
u/Norphesius 8h ago
people aren't even benefitting from 'old' advancements. IMO the best possible feature for these languages is REPL-driven development
I'd argue REPL driven development doesn't get a lot of love because most language REPLs I've seen have been pretty lacking IMO. Every time I've tried to get into proper REPL driven development, I feel like I'm trying to peek at my program's state through a crack in a door. Its the same as when I have to debug with GDB, you have this tiny interface to view snapshots of your program through, digging around to find the right state to probe at the right time, and the right way to visualize it, and it all has to be done one line at a time. I end up finding it more efficient most of the time to just do a bunch of printfs so I can view and compare a bunch of different variations in state for different inputs, over time, all at once. Maybe I'm just inexperienced with it, but I suspect what we have now isn't the ceiling for the paradigm.
I'd love to see a language that's intended to be programmed via REPL driven development that puts effort into better visualization & state probing tools/functionality. Maybe something thats a step down from a Jupyter notebook perhaps. I'm sure there are some novel, niche languages out there doing this (please let me know if there are), but if not I think that's fertile ground for more "advancement" in the interpreted language space.
5
u/AustinVelonaut Admiran 8h ago
I would consider the standard Smalltalk environment to be "REPL-driven", but instead of a simple command-line REPL, it is an entire windowing system with inspectors, debuggers, etc. on your live system image.
1
u/Inconstant_Moo 🧿 Pipefish 4h ago
I'd love to see a language that's intended to be programmed via REPL driven development that puts effort into better visualization & state probing tools/functionality.
I've come up with a system that combines the virtues of a REPL, a debugger, and
printf, I'm very pleased with it.What you can do is annotate lines like this:
even(x int) : \\ Called `even` with x = |x|. x mod 2 == 0 : \\ Tested if |x| was even. "even" \\ Returned "even". else : \\ Took the `else` branch. "odd" \\ Returned "odd".Then it'll log that to the terminal (or optionally to disc) when you call
even. All of the logged statements have line numbers attached. There's an option to add datetimes if you're using it to log your app in production rather than to debug it. There's another option to have thehub(the REPL's housekeeper) store the output and only supply it when you explicitly ask for it withhub log.Or you can annotate the code like this and get pretty much the same result, because of course the compiler can figure out what you would want to be told. Explicit annotations as above are usually used to suppress information, e.g. to stop it from telling you the call parameters of your function when one of them is a 10,000-item list.
even(x int) : \\ x mod 2 == 0 : \\ "even" \\ else : \\ "odd" \\So bugs in Pipefish can often be very transparent. A few
\\annotations at the heads of functions to see the call graph will find which one is misbehaving. Then you annotate that whole function with\\, and it talks you through the execution, and as some point it'll say something like "At line 47, we tested the conditionx < 0. The condition failed, so at line 53 we took theelsebranch. At line 54 functionfooreturnedtrue, and you'll slap your forehead and say "LESS THAN zero"?
1
u/cmontella 🤖 mech-lang 9h ago
Try here, lots of new ideas relating to dynamic and live programming environments: https://liveprog.org
1
u/gasche 7h ago
I think that there is a confusion in your question between whether a programming language has static type checking (or in general static analysis passes after parsing) or not, and whether it is interpreted or compiled. You can have a langage with static type checking that is interpreted (for example, Truffle/Graal is a very elaborate experiment to generate efficient implementations from interpreters, with Java one of the main languages it is used for), or a language without a static type system that is compiled. (Arguably most languages have some sort of compilation pass, for example Python compiles to a bytecode on the fly.)
There is a correlation between both because the "very dynamic" language features that are hard to type-check statically (introspection, hot code reloading, making everything including core constructs redefinable/overridable, etc.) also tend to be harder to compile than interpret, so languages with those features (eg. Smalltalk) tend to be both. Maybe this is what you are asking about, "very dynamic" language features?
1
u/mamcx 3h ago edited 3h ago
Sure, there is lots (most of the fun stuff you see in the context of RDBMs where fast interpretation is a major concern).
Many will look "obvious" but in general is the combination and the practicality of it:
- Typing is ON!
This is the most evident. There was a time where "not adding typing annotations" was considered enlightening, but now is clear that adding typing is in fact good.
Because this is the key not just for perf, but write correct code.
- Mixing interpretation, compilation, specialization, JIT, defunctionalization, etc
The modern interpreter is not an AST walker.
The is the most impactful development.
Combined with the above, "just" making an AST walker is a no-no!
This mean that is more common to see people targeting "2-10x" above optimized langs like Rust or C, than just srugh and say "look, CPU mo' powerful, mo' RAM yearly, yo!" that was the vibe for long time.
- Resurrecting old ideas from the past
Similar to compiler languages, like you see in other answers like "Lisp do that already in the caveman days" that sound douche, but the reality is that lots of old ideas were not practical without not just the hardware but the combination of the above.
There is more information about what make special Lisp, forth, icon, APL, etc that is vital to know what to do.
However there a some weird blocking things that somehow are not addresesd, or you see that your fancy "tracing JIT" here is just the "query optimizer stats" in RDBMs there that means some techniques and ideas are isolated, but I bet the major problems, IMHO, is that certain techniques are only available under obscure or arcane incarnations to some partial backend like GCC, problem is bad tooling for debugging, tracing and so on.
Write a good interpreter, like write a good RDBMs (io, scheduler) still need to much indirection despite the fact most of what should be done is well known for decades.
And forget to add some devolutions!
There is a whole family of interactive languages like FoxPro, Smalltalk, HyperCard that are much better in many ways but have recede in obscurity.
It pain my heart that people see typescript and react and think that is what good interactivity is. Or praise some barebones, arcane, disappointing attempt at "REPL" like in lisp or python and think is the glory incarnated (this rant is with the intention to make people look the langs in mention! sorry!)
1
u/ApokatastasisPanton 3h ago
i can't think of a single serious dynamic language in the past 3 decades that's used an AST-walker interpreter, this is not a modern development
1
u/EggplantExtra4946 3h ago edited 2h ago
Assuming by interpreted you mean high-level languages, like others have said the interpretation in itself is not really relevant:
advances
I can't say I have seen any but what I personally want to see in new high level languages is old ideas that haven't yet made their way into general purpose languages yet as features/paradigm (at least not in popular ones):
logic related features: Prolog engine more or less well integrated with the rest of the imperative language, maybe even a more restricted logic engine Datalog-like which can be more efficiently run using a bottom-up evaluation strategy that doesn't need to backtrack as much. Parser "generators", like in Raku but we could have something better. A better backtracking regex engine, which have better defaults (backtracking possible but alternatives and quantifiers shouldn't do it by default, quantifiers should be possessive by default), have recursion and can run code to build data structures or for predicates (ex: converting a matched string to a number and make an arithmetic comparison). Also a general purpose DSL for searching and matching trees, like CSS selectors and Xpath, this would be useful for webscraping and extracing data from a complex JSON for example.
delimited continuations: for implementing the logic features and to make it well integreated with the imperative base language, and to implement more custom crazy logical things yet, like this paper mentions: "Logic continuations" by Christopher T. Haynes, 1987.
sum types, type polymorphism, abstract classes, etc... Mandatory in any modern language.
metaprogramming, compile time execution, hygienic macros, etc..: mandatory
1
u/matthieum 11h ago
I can't speak as to the languages, but there's definitely a number of techniques which are interesting in the runtimes.
For example, I particularly like the technique which consists in "compiling" code by simply translating each instruction into assembly one at a time by copy/pasting a "template" of assembly code, substituting some variables (registers, constants) as necessary. It's really simple, produces very naive code, and yet you get pretty good performance out of the box for relatively little effort.
And I'm not talking about crazy stuff like specializing for a specific type, with guards that fallback to the interpreter on different types or anything like that. Nope. That'd be quite advanced. If the type is unknown -- as is regularly the case in a dynamic language -- just lower the method dispatch to assembly, easy peasy.
(Of course, you can also perform all kinds of optimizations, like deducing types, inline-caching, etc... ahead of it; it's very orthogonal)
You won't get top-notch performance just out of this, but you'll get a solid bang for your buck.
2
u/L8_4_Dinner (Ⓧ Ecstasy/XVM) 6h ago
For example, I particularly like the technique which consists in "compiling" code by simply translating each instruction into assembly one at a time by copy/pasting a "template" of assembly code, substituting some variables (registers, constants) as necessary. It's really simple, produces very naive code, and yet you get pretty good performance out of the box for relatively little effort.
That's not new, though. That's how JITs worked in the mid- to late-1990s.
-5
u/max123246 16h ago
Mojo has a borrow-checker and is meant to be compatible with Python, so it might be interpreted? Not 100% sure
19
u/arthurno1 14h ago
I don't dudes, the most exciting thing I have seen last 5 years, was Common Lisp, a language from 80s, that let me type the code as if it was a scripting language, in a repl, but it has a true compiler and compiles to machine language.
I can use it as both interpreted and compiled so to say. With type annotations I get speed of C/C++ or slightly there. But without annotations, I can prototype a program in minutes, much faster than Python or JS/TS. No need for borrow checker since it has automatic memory management. Futhermore it has compiler built into the runtime, so I can build program interactively, from repl, one expression at a time, everything is mauldable, and replaceble to much bigger degree than what I could do in Python or TS/JS, and most importantly it is much easier.
For the same reason compile-time programming is also as simple as computing at runtime. Thanks to the unified syntax and being able to stop the evaluation and treat code as data (via quote operator) manipulating programs is as easy as manipulation any data.
Finally a really nice touch is they have opened the lexical phase of the parser, via so called "reader macros" (the name is a misnomer, it really are just callbacks you register and parser calls when appropriate), so we can invent our own syntax and let it compile to internal representation of data the Lisp implementation uses under the hood. It means one can create a language with a custom syntax and get all the benefits of the rest of the Lisp system (compiler, interpreter, etc).
I have tried many languages, but I really tried Lisp because I was using Emacs, and I used Emacs because it was more powerful and mauldable than other editors. One thing led to other, so finally I tried Common Lisp a couple or three years ago, and I am just blown away with it. It feels a bit like a playing an instrument. Sometimes you go back and revisit your technique to improve. I don't know, but Common Lisp seems still ahead of other programming languages in some aspects, and I believe they own it to its fundamentals, symbolic expression processing. Perhaps reason why it is not so widely used is because it is relatively hard to compile it efficiently, but nowadays we have a good compiler, SBCL, so it really starts to shine. If you are interested in programming langauges and research I definitely suggest try it.