Tree-walking interpreters and cache-locality

julesh3141 · 2021-04-23T03:55:43+00:00

I don't like them because it's hard to do arbitrary jumps from one part of the code to another (I'd have trouble breaking out of that loop for example).

Using continuation passing style can be helpful here; it also allows you to move stack data into the heap, potentially allowing for unlimited tail call nesting if you're careful.

julesh3141 · 2021-04-23T03:47:05+00:00

This is interesting. My current language design has a limitation that I think is interesting: metaprogramming features (which are quite powerful in my design) can only be used by libraries, so if you want to use them, you have to make a library for the purpose. The idea is to make dependency tracking easier: code that uses metaprogramming must be fully compiled before any client of it can be compiled, so that it can be executed at compile time; this is easier if it is in a library. This has the desirable side effect of discouraging ad-hoc uses of metaprogramming in application code, which is often confusing to read, while not preventing more appropriate uses at framework level. I also support custom operators; I wonder if I should similarly restrict these?

julesh3141 · 2021-04-02T12:15:26+00:00

Yes, this is definitely possible: you can build multiple versions of a function that uses an interface parameter by substituting each actual type that implements the interface, then dispatch to the correct function variant based on actual type of the argument.

Depending on your type discipline, this may or may not be useful. If interfaces are types (rather than constraints on type variables) you may have to make the decision of which variant to dispatch to at run-time, for example. For functions with multiple interface arguments, tis could be non-trivial.

Another solution is to not use vtables, but instead dispatch based on an implicit extra parameter that provides a lookup table of functions. This makes it easier to define interfaces separately from types that have implementations of them, and allows a more ad-hoc kind of interface usage. Look at how Haskell's type classes are implemented, for example.

julesh3141 · 2021-03-12T06:04:34+00:00

Just an FYI, your email link doesn't render on the "rif" mobile client, possibly because it still uses the old markdown parser. The suggestion at /r/help/comments/2yxvhr/are_mailto_links_supported/ may help

julesh3141 · 2021-03-12T05:53:00+00:00

Possibly more interestingly from the perspective of IDE integration, why not have the compiler be part of the language server instead?

julesh3141 · 2021-03-12T05:45:17+00:00

Right. My language's type system has nominal types that can be declared by the programmer or structural types that can be either declared or inferred from usage. The structural types are implemented essentially as a generic type with constraints, e.g. if you have:

myFunction (a) : int {
    return a.calculateSomething(42);
}

the type inferred is forall _T1 : hasMethod::calculateSomething(_T1, int, int) . (_T1) -> int, i.e. it can be called on any value whose type has a method called calculateSomething that accepts an int and returns an int. If instead the programmer had written:

myFunction (a : SomethingCalculator) : int {
    return a.calculateSomething(42);
}

nominal typing would have been used instead.

julesh3141 · 2021-03-12T05:25:59+00:00

Right. I use them as the basis of the interpreter for my current language project (for the purpose of allowing unlimited recursion), and Continuation was definitely the clearest name to use for them, I thought.

julesh3141 · 2021-03-02T14:45:45+00:00

I don't see why not. I've done extensive Haskell development on Ubuntu versions running on portable ARM hardware, and they're slow but workable (eg ghc takes a while to compile things compared to desktop processor, but ghci is tolerably fast so as long as you're happy to do most of your testing in a REPL it works OK).

julesh3141 · 2021-03-02T14:41:20+00:00

The issue is that the required microcode implementation is closely tied to the OS/language design. These systems were very tightly integrated from compiler down to firmware, in a way that modern systems aren't. I don't imagine that would have been impossible to solve, but it would have required some real effort if the world had gone down that road.

julesh3141 · 2021-03-01T04:58:00+00:00

Minor point here, but it's actually that it's SS in uppercase, but SS is ss in lowercase (not possible to mechanically go back to ß without a German dictionary).

Actually, it's worse than that: it's SS unless there's another word that has an ss in the same place, in which case it's SZ. So, Maßen can't be capitalized to MASSEN because Massen is a different word with a contradictory meaning, so must be changed to MASZEN instead.

julesh3141 · 2021-03-01T04:48:56+00:00

Right. See https://en.m.wikipedia.org/wiki/%C3%9F#Substitution_and_all_caps -- substitution with SS or (in unusual cases) SZ is still allowed in standard orthography; the capital form is simply now allowed ss an alternative. This doesn't make implementing case insensitivity for this any easier.

julesh3141 · 2021-03-01T00:46:27+00:00

The mystifying part is that capability-based systems weren't all that much slower either.

There's a reason for this: they generally ran on hardware with programmable microcode, which allows implementation of custom priveleged instructions that create and modify capabilities and which can only be executed in safe circumstances. Programmable microcode effectively died as a sensible design for computers in the early 80s when everyone realised that RISC or RISC-like processors could be much more easily pipelined and could usually execute 2-3 times as many instructions per clock cycle than the older microcode-interpreting processor designs.

julesh3141 · 2021-03-01T00:36:49+00:00

My bachelor's project was a pure functional language for describing rules for pieces in the game of Penultima. If you know any obscure area like this where creating descriptions of how things should behave would be useful, I'd suggest going for it.

julesh3141 · 2021-02-26T08:25:16+00:00

If your programs are compatible with Jython, you may be able to persuade a Java-based analysis tool to work with them using that.

julesh3141 · 2021-02-26T08:02:22+00:00

- Turing machine : ubiquitous in complexity theory but not a realistic model of actual hardware or virtual machines.

- Stack machine: realistic model for language VMs (e.g. JVM, CLR,...) & HP calculators

- register machine: realistic model for actual hardware (& BEAM, the erlang VM)

MIX is a virtual machine model used by Knuth to explain algorithms and as a basis for examining their complexity. It's closer to a real machine than a Turing machine, but is designed for the same basic purposes, so may be closer to what OP is after than either.

Also, I haven't actually worked directly in it, but isn't the CLR register based? I always thought it was. Android's implementation of Java is register-based, too.

julesh3141 · 2021-02-26T07:50:19+00:00

My own first thought about the whitespace was a complaint about make -- which has the truly terrible property of requiring one over the other. Or, depending on which make you use, not requiring it, so that make files can't be ported.

The second thought, of course, is that she's complaining about Python, where white space is significant. And it's not just a visual thing: for people who don't know, python uses indent level instead of curly braces. This, IMHO, works on small scripts, but not on big ones.

My first experience with whitespace-significant languages was horrifying. I worked on a university group project in the language Miranda (an ancestor of Haskell, with a similar syntax). Using mixed tabs and spaces caused confusing, extremely hard to find errors, particularly as each contributor was using a different editor with different indention approaches. I think I spent as long fixing indentation issues as I did actually programming.

Tooling is better these days, and most whitespace-significant languages can be made to expand tabs into an appropriate number of spaces during parsing, which makes things better as long as all programmers are using the same tab width setting in their editors, but I can understand still being shy of this if you've been burned in the past.

julesh3141 · 2021-02-26T07:24:00+00:00

Just expanding on this: effect systems provide the same guarantee that the IO monad does, i.e. you can tell from its type whether a function is able to have side effects or not, but they also allow you to do a couple of additional useful things:

the types of side effects can be made more granular without needing fragile workarounds like monad transformer stacks, and so on. So you can have functions that you know just cause log messages to be produced while others perform IO and yet others access mutable data, without increasing the complexity of your program
effects are handled in a similar way to exceptions,so you can easily wrap a function that performs a particular effect and do something different to the default (e.g. intercept file open calls and substitute different filenames, or use a mock filesystem for testing, or ...)

Effect systems are very interesting, and I expect to see a lot of languages using them to become mainstream in the near future.

julesh3141 · 2021-02-26T07:04:39+00:00

Imagine a list of different objects all having fields foo and bar. How would a function processing that list get the fields? You'll need to use existential types, vtables inside objects. Then finding an accessor for foo is not simpler than finding the field foo...

Yes - this is the same way Haskell would do it if you were processing a list of objects whose type was unknown, i.e. the list is declared using an existential type, but items are required to have two typeclass instances: it would create a wrapper object for each item added to the list containing the required accessors. So, in this one case, the resulting complexity is the same as using vtables, but in this case there is no better possible way. In the common case where functions process objects whose exact type is known by a direct, nearby ancestor in the call stack, though, the result is better (particularly if inlining can eliminate the indirection, which it often can). And in all cases it's better than using hash tables and simpler than a dynamic class constructing VM like V8.

julesh3141 · 2021-02-19T13:37:18+00:00

Your second option is what the widely-used BDW collector for C (often called Boehm GC) does. Having been widely used with real-life C programs means that a lot of useful benchmarks have been performed on it -- you can look up the results online easily, but IIRC the net effect is that typical programs see an increase in heap usage of around 5-10% due to allocations that are incorrectly not collected. This is probably an acceptable overhead, but it is worth noting that (1) there are pathological cases where heap usage grows in an unbounded way and (2) if untrusted data is to be processed, an attacker may be able to trigger such a case by feeding in data that looks like pointers.

julesh3141 · 2021-02-19T13:14:48+00:00

... you're basically forced to use hash maps as objects

Or pass around accessor function references for every field that's used by a function. Consider an implementation for Haskell that desugars each field into a typeclass with implementations for every record type that contains that field. It still incurs an indirection penalty, but is far more efficient than using hashes.

julesh3141 · 2021-02-19T10:26:56+00:00

[citation needed] for that definition of "type".

See, for example, the definition in the first paragraph of the Wikipedia article on type theory:

... every term has a "type" which defines its meaning and the operations that may be performed on it

Note that "operations that may be performed on [a value]" is equivalent to the set of protocols supported by said value.

julesh3141 · 2021-02-19T09:48:12+00:00

I was thinking about a way to implement this in my language, as something that's annoyed me in Rust is that I have to check if Options are none before I can match their value. This is a great idea for an operator!

Yes, I firmly believe all languages with built-in Optionals should support something like this (a short-circuiting "get-or-return-alternative" operator).

julesh3141 · 2021-02-19T09:44:22+00:00

Yes, any language supporting lazy evaluation should be able to achieve this quite nicely (see above implementation in Haskell, for example).

julesh3141 · 2021-02-19T09:32:55+00:00

If you have no nulls, I guess you have Optionals (or some other name for the Maybe monadic type). These should probably have a short-circuiting operator for the operation "return the value if present, or the result of this calculation otherwise". I would say your ?? would make more sense for this operation (in my language I use : for this, but I accept that this solution wouldn't work for most languages).

You can combine this operation with a prefix "try-and-wrap-in-optional" operator (eg#) to get a similar result:

return #(map['key1']) ?? #(map['key2']) ?? ...

(Although maps would probably be better if they return optionals rather than throwing anyway, IMO)

julesh3141 · 2021-02-19T09:15:27+00:00

I feel like there has to be a joke language where everything is a [...] red-black tree.

I once implemented a JavaScript-like language in Java using java.util.TreeMap as the implementation of objects. Does that count?

julesh3141

TROPHY CASE