gsg

"Modern Compiler Implementation" isn't too bad, but it is a general purpose introductory compiler text rather than being dedicated to functional languages. It does briefly touch on subjects like closure conversion and type inference, but doesn't give working code.

Appel's other compiler book, "Compiling with Continuations", goes into more depth while falling short of being a complete tutorial on writing a compiler for ML.

Itanium did have features for various kinds of speculation, though. You could load from an address even if it were potentially aliased with a subsequent store, with the processor doing a dynamic check to make sure the right value was observed (eg, performing a late load and blocking if it turned out there was an overlapping store).

It wasn't as effective as OoO in the end, but not for lack of attention to the problem.

In general you can't drop the contents of the arena on the floor in a GCed language, since you might have been wrong about those objects being short-lived (or because they are short lived, but they were allocated shortly before the young heap filled up and happen to still be alive). So tracing/copying is still necessary.

It is quite possible for objects that are expected to tenure to be allocated directly into the major heap. Many systems use various criteria to decide when this should be done. In particular it is common to allocate very large objects directly to avoid ever having to copy them.

There are also static analyses which attempt to determine which objects can be safely allocated in an arena-like way, that is, region inference. In some systems in addition to inference the programmer is given ways to specify that a given object should live within a certain region. MLkit is the usual example of such a system. Region systems don't seem to have been particularly popular, but there's still some work being done on them here and there.

I remember reading it a number of years ago. It's true that it may have been updated since then, although my guess would be that it has not.

This is about a decade old, I think. With a substantial optimisation suite added to ocamlopt since, some of it will be out of date. The advice on inlining in particular is obsolete.

Very understandable, type classes + inference + monads + do notation is quite a stack of unfamiliar machinery to understand all at once.

The return type is inferred, and the type is what the type class machinery is driven by. You can get some more visibility into that by playing in ghci:

    return 0 :: [Int] => [0]
    return 0 :: Maybe Int => Just 0

Having behaviour driven by return type takes a bit of getting used to.

return isn't syntax, it's a normal function of type Monad m => a -> m a. The "sniffing" that you are talking about is that overloading is done on the return type.

Why does it exist at all? Speaking loosely, monads are about composing functions that look like a -> m b. Here's regular composition alongside the 'monadic' one:

    (.) ::              (b -> c)   -> (a -> b)   -> (a -> c)
    (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)

As you can see, the same except for the m wrapping each function's results. Just like normal function composition, there is an identity element - that's what return is. Again, a comparison:

    id ::                a -> a
    return :: Monad m => a -> m a

Again, the same except for the m wrapping the result. Both composition operators are associative, and both have the same relationship with their identity operation:

    id . f  =  f     return <=< f  =  f
    f . id  =  f     f <=< return  =  f

(That's why there are monad laws, to ensure those properties hold.)

So return is very straightforward: it is the identity of functions that return monads. It's unfortunate that both the name and the presentation of monads in Haskell tend to obscure this.

You might be interested in http://blog.racket-lang.org/2017/04/type-tailoring.html, which argues for customised type checking.

Use Int64.t?

The Common Lisp answer is 0.3 and not 0.30000000000000004 because those are single float literals: for double float literals, we have (+ 0.1d0 0.2d0) => 0.30000000000000004d0.

I would imagine this is the case for several of the other examples, too.

There are some tools aimed roughly in this direction, such as https://github.com/TrustInSoft/tis-interpreter.

A major difficulty here is that undefined behaviour is a property of a particular execution of a C program, rather than a static property of the program itself. Tools that dynamically detect UB are useful, but will not demonstrate that there are no inputs for which a program will go wrong.

x86-64 vector compare instructions (mostly) produce masks, which are vector-sized values containing 1 for each bit of the input for which the comparison is true, and 0 where it is false. Since a vector analogue of x == x would be true everywhere, it would result in 0b1111....

It's true that the given C code doesn't have those semantics, but you can see what the GP was driving at if you squint a bit. Uh, and if you know how these instructions work already.

What you want is just a few lines up:

    1652 If an object that has automatic storage duration is not initialized explicitly, its value is indeterminate.

(x is an 'auto' variable in the given program.)

In general it's impossible. Consider this C program:

    void do_something(int *);

    int f() {
        int x;
        do_something(&x);
        return x;
    }

Is the return of x a use of initialized memory? Maybe. Relink the program and the answer might change.

The idea was that the syntax for declaring a data type mirrors the syntax for using that datatype. See https://www.bell-labs.com/usr/dmr/www/chist.pdf for Ritchie's own comments.

It was not a successful idea, but there was a method to the madness.

That's one possible design, but it's common to use a constant pool. Placing constants in the instruction stream is possible but awkward, since there is no guarantee that they are either aligned or of the right endianness (assuming you are trying to write a more or less portable system).

Constants that fit in a byte don't have this problem and can be easily placed in the instruction stream using dedicated byte constant instructions, sometimes including dedicated single-byte instructions for common constants like zero, one, etc.

From http://v8project.blogspot.com.au/2016/07/v8-at-blinkon-6-con..., at which there are a few more videos.

And if you want to go weirder, implicit int means that you can leave out the `int`:

    typedef x;

Even "better", C declarators can be empty in order to allow for struct/enum declarations that do not list any variables. So you can leave out the variable, add qualifiers, etc:

    typedef;
    const typedef;
    typedef const;

It's a really fun syntax in some ways.

This reminds me of an irritating problem in CPS based compilers where you can have a transformation that is obvious and legal except that after the transformation one of the relevant variables would not be in scope. The solution(s) are to decline to do that transformation, fart around with sinking and hoisting in order to get the scope right, or ditch scope and move to a graph model in which dependence is represented with explicit edges rather than being approximated by the lexical structure of the program.

I'm guessing that the lexical borrow problems that Rust are facing are an instance of the same problem. It will be interesting to read the follow up post and see what relation, if any, the suggested solution has to the graph approaches that I am familiar with.

It's the basis of efficient relocations in position independent code, which is now very common.

PIC can be emitted on older x86 machines without RIP-relative addressing, but the code is larger and slower. As an example, consider -m32 gcc output for the C program

    int x;

    int getx() {
        return x;
    }

With no PIC:

    getx:
	movl	x, %eax
	ret

With PIC:

    getx:
	call    __x86.get_pc_thunk.cx
	addl    $_GLOBAL_OFFSET_TABLE_, %ecx
	movl    x@GOT(%ecx), %eax
	movl    (%eax), %eax
	ret

And with -m64, which emits PIC and uses x86-64s RIP-relative addressing:

    getx:
 	movl	x(%rip), %eax
	ret

Hopefully that makes the motivation clear.

Perhaps MinCaml: http://esumii.github.io/min-caml/index-e.html

SML? Pascal?

Edit: I was really referring to language families, so including things like OCaml, Modula, etc.

Specialising LLVM for dynamic compilation might well come at the expense of LLVM's strengths as an AoT compiler, and it would probably not be easy in any case.

In addition to that, dedicated implementations can take various shortcuts to make their job easier - there are some nice examples given in the link. LuaJIT is example of a compiler project that benefits from being heavily specialised to a particular job, to remarkable effect.

Weird that it doesn't propagate the constant such that both functions are closed - maybe with a higher optimisation level.

> Note that for well-known procedures, all variables that are free in the lambda are also free in the caller

I don't think this is right, unless given an unnecessarily strict definition of `well-known`. A contrived counterexample:

    let example x y =
      let f =
        let z = big_calculation x in
        (fun t -> if t then z else 0) in
      (fun q -> f q + f y)

Here f is bound to a known function, which is only called and never escapes. All of the known-function optimisations should apply. However the variable z is not in scope at the call sites of f.

Optimising this example effectively is a bit tricky - the 'standard' thing to do is construct a closure that contains z (but need not contain a code pointer, since all call sites are known), which is itself contained within the closure for (fun q -> ...). A more aggressive method would be to discover that all references to f are within (fun q -> ...) and inline the free variables of f into its closure, avoiding an indirection.

It's quite a fun subject - there are various implementation tricks for curried functions and partial application too, which aren't very important in Scheme but are crucial for ML.

It isn't stable.

You could try to split the difference by using a wrapper around malloc that zeroes in production and doesn't under testing.

Of course, running significantly different code in production and test has its own issues.

The two-continuation style suggested there is familiar to me under the name "double barreled CPS", although usually in the context of compilation. Interesting to see it suggested for user code.

Dependent types allow for this kind of thing.

Another possibility that doesn't require such heavy language machinery is something like OCaml's private types, where the scope of unrestricted access is unsafe blocks rather than the body of a module. In this approach there is no type-level correspondence between the value of the length member and the extent of the array: private types only ensure that any potentially invariant-breaking mutation is restricted to a certain scope, not that the code is correct.

Nice article, but the language embedded here is exactly the untyped lambda calculus, not a Lisp. You can tell because there are no tags: pair is given as \x y sel -> sel x y, which is indeed the textbook way to encode pairs but does not provide enough to write CONSP.

If you wished to implement a subset of Lisp in LC faithfully you would need an encoding for sums - which would not be all that hard, but does reflect the distance between Lisp values and the raw abstractions of the lambda calculus. (There is also the more substantial matter of RPLACD, etc, but let's just pretend that particular rabbit hole is not there.)