Colin James

Code monkey interested in compilers for strict functional languages.

[Colin James @contificate]

Currently working on a tool for visualising instruction selection using tree pattern matching automata. Demonstration shows some trees from the LCC project compiler tiled with some random patterns.

[Colin James @contificate]

@filpizlo @JM0x5C When does it become a compiler? When you introduce sharing? I don't know which programs don't manipulate tree-shaped data, as most things are inductively defined. People tend to misinterpret "tree" as if we're talking about defining an AVL tree or something.

[Colin James @contificate]

@JM0x5C @filpizlo Don't worry. People who defend C++ here often don't know (or forget) how much of LLVM, GCC, etc. are generated from esolangs they maintain. E.g. if I recall correctly, the SelectionDAG backend for the x86 target in LLVM emits a C++ source file roughly 28MB in size.

[Colin James @contificate]

@valigo I didn't understand delimited control until I read and implemented https://t.co/5KjPGdnhqA - this paper couldn't be more grounded in practice, it contains PowerPC snippets for manipulating stack frames. There's always a resource that cuts through the noise.

[Colin James @contificate]

@ahm3dgg @AustinZHenley If it's any consolation, most mainstream compilers specify quite a lot in custom esolangs they maintain anyway. So, you might have the Cnile take that LLVM and GCC are some C++ monoliths, but actually much is generated (e.g. from LLVM Tablegen and GCC machine description files).

[Colin James @contificate]

@ahm3dgg @AustinZHenley There are also C and Java editions of that book. I can assure you that they are much harder to read.

E.g. the C edition is effectively an exercise in tagged union tedium. Appel actually uses ML-esque pseudocode in some of the snippets as it's such error-prone tedium in C.

[Colin James @contificate]

@debasishg Le Langage Caml (French)(https://t.co/EaerYrbMAD) has lots of good example programs that succinctly exercise features of the language. The book also happens to be a good resource for some of the examples it chooses as well (e.g. type inference with destructive unification).

[Colin James @contificate]

@satnam6502 Functional programmers are more likely to have the background in PLs to overcome the burden of implementation that C has. For example, I've defunctionalised an OCaml algorithm (in CPS) into C - more than once - to avoid error-prone reinvention of a conceptually neat approach.

[Colin James @contificate]

@kai_fall You understand that tagged unions are used extensively in C programming? Such an untenable position to take when mainstream C compilers represent so much using this encoding - even going as far as to maintain custom esolangs for performing pattern matching over them.

[Colin James @contificate]

@LewisCTech @FilasienoF If you like call/cc, it is worth checking out delimited control operators like shift/reset. Their direct implementation tends to involve segmented stacks - much like other lightweight thread impls. There is a great connection to CPS, trampolining CPS, and basic schedulers.

[Colin James @contificate]

@guizmaii As for delimited control operators, I think understanding how they are implemented is the best approach. The ideas are not new and are available (in less powerful ways) in many languages. The difference is you are given the reified (delimited) continuation as a value.

[Colin James @contificate]

@guizmaii Simplest way to start is to convert some functions into CPS as an exercise. There's many avenues you can go with CPS itself: its usage in compilers, defunctionalisation, trampolining, etc. Arguably, CPS should be taught explicitly and before monadic style.

[Colin James @contificate]

Toying with a visualisation of Pratt parsing in order to teach precedence climbing.

[Colin James @contificate]

@_RastaMouse Many domain specific languages converge upon a general purpose language, by necessity (avoiding a Turing tarpit). You could conceive of a restriction to an extant language to facilitate obfuscations more easily, and continue to benefit from the extant program corpus for testing.

[Colin James @contificate]

@htmasry Thanks! Yeah, it was more an experiment. I've kind of concluded that you would need more control over the compiler back-end to do it this way reliably (in spite of its shortcomings). That said, it was fun to piece together and will maybe help me in following the other approaches.

[Colin James @contificate]

Ported the ideas in "Direct Implementation of Shift and Reset in the MinCaml Compiler" by Masuko and Asai to AArch64 in order to compile and support an untyped lambda calculus extended with arithmetic + shift/reset delimited control primitives (by direct call stack manipulation).

[Colin James @contificate]

Wrote a toy pattern matching compiler that accepts type definitions + a match case as input and provides a visualisation of a potential decision DAG.

[Colin James @contificate]

@drathier @justinesherry This topic is of such recurring debate in various online circles I'm involved in that it spiralled into one of Matthias' students asking for permission to film his response to the question. I hope Matthias won't mind it being posted here. It's "just A" :)

[Colin James @contificate]

@ilfak

[Colin James @contificate]

Hacked together a PegJS parser for directly displaying IDA's graph description files on a webpage (with dagre + D3.js).