gsg
Joined 16 years ago
Karma
893
Submissions
307
Member since
Dec 13
Recent submissions
Comment · 5 years ago
This works until the analogue of monotremes shows up to ruin your supposedly flawless categorisation.
Comment · 5 years ago
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.
Comment · 5 years ago
There are some examples, for example Crowbar is an OCaml tool that uses AFL to drive property based tests.
Comment · 5 years ago
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.
Comment · 5 years ago
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
Comment · 5 years ago
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);
}
Comment · 6 years ago
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.
Comment · 6 years ago
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.
Comment · 6 years ago
That still exists though? add rax, rbx/jo overflow_error is how you do overflow checking on x86-64.
Comment · 6 years ago
> 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.
Comment · 6 years ago
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.
Comment · 8 years ago
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.
Comment · 8 years ago
My guess would be that they were thinking h <= SIZE_MAX / w, and added the most obvious logic to avoid a division by zero.
Comment · 8 years ago
Monomorphising doesn't work for rank-n polymorphism, either. (This is mentioned on the page.)