gsg

This works until the analogue of monotremes shows up to ruin your supposedly flawless categorisation.

System F doesn't have general recursion.

Extensions with a letrec-like construct are common, and are sometimes inaccurately called 'System F', but those languages do not have the properties of System F.

There are some examples, for example Crowbar is an OCaml tool that uses AFL to drive property based tests.

chrisseaton is talking about the bump-pointer allocator in a modern GC, not an implementation of malloc/free. The performance characteristics are quite different.

In a generational copying system an object that is bump allocated and then is dead before being copied out of the young generation is indeed cheap - dead objects in the young generation don't need to be freed or even looked at in any way because the space for the young generation can simply be reused after everything is copied out of it. The slow part is elsewhere.

Yes, this has been done a few times. CDR-coding was a hardware-assisted method of unrolling a Lisp list (complicated somewhat by the need to support mutation of car and cdr) that appeared on Lisp machines, and there's a Appel/Reppy/Shao paper on unrolling linked lists in the context of Standard ML.

There's also some interesting work on flattened versions of arbitrary tree structures: https://engineering.purdue.edu/~milind/docs/ecoop17.pdf

You can easily see by searching for 'kmalloc' (or 'malloc') at https://github.com/torvalds/linux/blob/master/include/linux/... that it does no such thing.

Here's the logic for adding a list node:

    /*
     * Insert a new entry between two known consecutive entries.
     *
     * This is only for internal list manipulation where we know
     * the prev/next entries already!
     */
    static inline void __list_add(struct list_head *new,
                                  struct list_head *prev,
                                  struct list_head *next)
    {
            if (!__list_add_valid(new, prev, next))
                    return;

            next->prev = new;
            new->next = next;
            new->prev = prev;
            WRITE_ONCE(prev->next, new);
    }

No allocation, just mutating some fields in preexisting list_head structures. Those are by convention stored as a field in whatever struct needs to be kept in the list, which is what 'intrusive' means.

BOUND is pretty slow, and requires an odd start/end pair to be placed in memory. I don't see any reason that it would be better than the usual unsigned comparison + branch that languages with bounds checking tend to use.

Besides, much of the difficulty with memory safety in C and C++ is the existence of pointers (or wrappers around them, like iterators), which do not come with an associated length. Length checking machinery can't help with that problem whether special instructions exist or not.

In short, it's doubtful that the availability of these old instructions would make any difference to the practicality of bounds checking on modern x86 machines whatsoever.

Sure, but that didn't change much between x86 and x86-64. Perhaps it got a little worse because the SIMD instructions aren't overflow check friendly.

That still exists though? add rax, rbx/jo overflow_error is how you do overflow checking on x86-64.

> As far as I understand it, this limitation is also the only thing preventing tail-call elimination in C/C++.

That is not the case. Guaranteed TCE requires deallocating the stack frame before jumping to the target, but that is not possible when an object is allocated in that frame and its address passed to the target function.

In C++ there is also the issue of destructors needing to run after the tail-call returns (in which case it is not really a tail-call).

C/C++ compilers can and do eliminate tail calls where possible, but there's no guarantee like you get from a compiler for a functional language.

Interesting if somewhat opaque. I'm familiar with defunctionalisation as an alternative to closure conversion in whole program compilers and as a description of how data types are derived from the lambda calculus - never seen a category theory take on the idea. I don't seem to be able to understand the category theory part though.

The suggestion to use a combination of CPS + defunctionalisation to serialise closures is notable, since that pair of transformations gives a fairly close correspondence between a subset of the lambda calculus (plus some primitives) and abstract machine code. Some of the old-school Scheme compilers used CPS as a low-level IR for that reason.

Lambda lifting is an alternative to closure conversion, so it doesn't get rid of closures so much as obviate introducing them at all.

The two transformations are fairly closely related, actually. You can view lambda lifting as closure conversion plus flattening, in the case where the code pointer is unnecessary.

My guess would be that they were thinking h <= SIZE_MAX / w, and added the most obvious logic to avoid a division by zero.

Monomorphising doesn't work for rank-n polymorphism, either. (This is mentioned on the page.)

A bunch of languages have something much like .let/.apply already, since it's pretty much just function application in reverse order:

    "foo" |> String.length |-> printf "%d\n" |> fun x -> x + 100

This is nonsense. Modern compilers don't work by generating the results you see with -O0 and then optimising; the poor quality of -O0 code is the result of skipping register allocation.

> Dataflow-directed, "work backwards" techniques might be the solution

Destination driven code generation is a known technique. It doesn't generate good enough results to have gotten much attention (better than what you get from -O0, though).

First, deriving is just pointer arithmetic and doesn't copy anything. Second, standard flat closure representations already involve copying parts of environments, with any sharing problems addressed by assignment conversion (turning variables that are assigned to into mutable cells, a reference to which can be copied into however many environments is necessary).

Mutually recursive functions can be closure converted without cycles by deriving closure values from each other rather than storing them in each other.

I see. It seems like that would still make calling supporting routines annoyingly expensive, but perhaps that (and the extra tag memory) doesn't matter as much as I think it does.

Good luck with the project.

How do you pass arguments? In two registers? On the stack?

There's a decent textbook written in the incremental style argued for by the author: Essentials of Compilation. It features compilers for seven languages, written in Racket, each with successively more advanced features.

https://jeapostrophe.github.io/courses/2017/spring/406/notes...

My complaint with |> is that it makes code with nesting look quite different based on argument position. Argument position is not a very interesting property, so it doesn't seem right for it to be influencing the shape of code in that way.

My preference is to use parens and introduce single-shot variables if nesting gets too deep. This works the same way for all code.

> some random OO language on Amiga that I've never really been able to track down

Maybe Amiga E? http://strlen.com/amiga-e/

So... the only way to stop a bad guy with a GAN is a good guy with a GAN?

Because S <: S in most (all?) type systems with subtyping.

You're right: it should be pushq $1/pop %rax (which is also three bytes, although there will be a prefix byte for registers r8 through r15).

Those compilers use CPS as an intermediate language - a bit like SSA form for functional languages - which is (mostly) independent of supporting first class continuations.

Support for first class continuations is a matter of tradeoffs. It's quite reasonable for an implementation to choose 'slow' continuations (in which call/cc copies the stack) in order to be able to use the more efficient native stack for function calls.

(EDIT: and in response to the linked post, it is quite possible to efficiently compile what would be contifiable functions in direct style - see the recent paper Compiling Without Continuations in which the GHC hackers do exactly that.)

push $1/pop %eax (6a 01 58) is shorter, but perhaps not the best idea.

Immediates are a bit of a mix. mov doesn't have very nice encodings, but many instructions do: push $1 is 2 bytes, addl $2, %eax is only 3 bytes.

There's no question that x86-64 could be improved on in terms of code density.

You might find http://esumii.github.io/min-caml/index-e.html interesting. While not as well-presented as munificent's current effort, it does present a working functional language compiler as a tutorial.