top | item 36406558

(no title)

I have written a few functional programming languages built on lambda calculus based backends, but I've had problems with compiling it efficiently; it's hard (at least to me)! I find that combinator based compilers are difficult, but very elegant; I've written a few in the past but problems always spring up when trying to evaluate expressions properly AND do side-effects correctly. I would love to pursue writing a combinator compiler, but I haven't yet come up with a good system of combinators that can represent I/O and foreign functions properly; although this probably isn't even as difficult as writing a compiler to a Turing-tape architecture.

discuss

TheMode|2 years ago

[0] and [1] seem pretty promising to me, although I believe that the problem come from the fact that these languages do not expose a way to describe a sequence of bits, which may make them not lambda calculus anymore, but probably much more usable (you could then implement a soft version of integer/float operations and a compiler that convert this code into a single instruction, easier as there is no side effect guarantee)

> but I haven't yet come up with a good system of combinators that can represent I/O and foreign functions properly

I do not believe that you should support either.

I/O could simply be the program arguments & the final reduction of the expression. The input being your mouse position and the output being a window shouldn't be the responsibility of your program.

Foreign functions are IMO a bad idea, especially if the goal is for the program to outlive you, you lose the guarantee if these functions depend on the environment. Why couldn't you copy/paste the code into your own project?

[0] - https://esolangs.org/wiki/Binary_lambda_calculus

[1] - https://esolangs.org/wiki/Dependently_Typed_Binary_Lambda_Ca...

JonChesterfield|2 years ago

Reify side effects in some fashion and then run the combinator graph reduction at compile time, as far as reasonable to do so. Partial evaluation works really well.

Basically combinators for the pure parts and functions that get optimised much less enthusiastically for IO or FFI.