3

Every functional language that compiles to native code relies on quite big runtime written in C programming language (well at least ones that I know of, for example Haskell, OCaml, Gambit/Chicken Scheme, SBCL, Mercury). Basically C is used to implement all the low level stuff like garbage collection, lazyness, OS abstraction layer and etc.

I'm interested if it is even possible to implement functional programming language all in itself, without doing anything in other programming language like C? If it is possible how for example garbage collection would need to be implemented?

I know that there are some projects that somehow compile OCaml, Haskell and Erlang to run on bare bones Xen hypervisor. Does the Xen provide low level features like garbage collection or there is still some C layer involved in these projects?

Is there still any functional programming language that doesn't rely on C runtime?

gnat
  • 21,442
  • 29
  • 112
  • 288
user2102508
  • 195
  • 2
  • 6
  • 1
    It's certainly possible. If nothing else, one can program all those bits in machine code and let the compiler add them to all programs. But I suppose you were looking for something more glamorous? –  Mar 02 '15 at 08:32
  • Some non-functional languages also have a runtime coded in C or C++ (in particular the JVM for Java) – Basile Starynkevitch Mar 02 '15 at 09:11
  • Some JVMs are written in C++. Some are written in Java. There is one written in Ruby, I believe, and one written in ECMAScript. – Jörg W Mittag Mar 02 '15 at 09:22
  • 4
    Lisp was written in 1958 (for high level programming languages, only Fortran is older than it)... C was written in 1972... so just by that it is certainly possible to write a functional language without C. The [Lisp machine](http://en.wikipedia.org/wiki/Lisp_machine) was even bare metal functional programming. –  Mar 03 '15 at 01:43
  • @MichaelT Lisp isn't really the best example of functional programming. Just because it was the first (I think) to support lambda's, closures and higher order functions does not mean it is a functional language by the modern definition of the word. – ALXGTV Jun 30 '15 at 14:01
  • 3
    @ALXGTV it was one of the first languages that one would put in the functional grouping though in the 50s, they weren't as concerned with the name (which has evolved). The point is that Lisp existed a decade before C and also had a bare metal implementation - neither of which were based on a C runtime. That these *existed* makes the answer to the "is it possible" a simple "yes". –  Jun 30 '15 at 14:05
  • There's nothing special about C; it just happens to be convenient for implementing the parts that you can't implement in the language itself. In the not-too-distant future Rust will probably be a viable contender. – user253751 Jul 01 '15 at 07:55
  • Related fact: Operating system kernels, and standard libraries, aren't implemented purely in C, they're implemented mostly in C with a bit of assembly - just like your language runtime is generally implemented mostly in your language with a bit of C. – user253751 Jul 01 '15 at 07:56
  • Interesting that this question is currently on -1 whereas [this one](http://programmers.stackexchange.com/questions/267086/is-every-language-written-in-c?lq=1) is at +140 – Alex Jul 01 '15 at 11:31

3 Answers3

7

Is there still any functional programming language that doesn't rely on C runtime?

Yes, at least if you consider (like I do) that Lisp variants are functional languages (because they have the application and abstraction operators of the lambda-calculus), and that any language with closures and abstraction is functional:

  • Bones is an implementation of Scheme, compiled to x86-64 assembly code in nasm syntax, which can be built without using any C compiler (but uses gcc as a linker only; with enough knowledge, you could replace that with ld).

  • Scheme48 is another implementation of Scheme which is entirely compiled to C; AFAIK its runtime system (including its GC) is coded in a subset of Scheme called PreScheme, and is translated to C (so IIUC no human written C code exist in it)

  • Jacques Pitrat's CAIA system is a declarative language bootstrapped artificial intelligence system (and all of its C code is generated by itself), so contains no human-written C code (but uses C as a target object language, like many other implementations)

  • Lissac is an object oriented language with some functional abilities (AFAIK it has closures so can count as functional programming language) entirely compiled to the x86-64 code.

  • old LISP machines from the 1980s did not rely on C at all.

You are probably asking: how can be a runtime system written in a high-level functional language (sort of chicken and egg problem, called bootstrapping compilers). The answer is "simple" in principle; you need to ensure that the lower part of your runtime does not need any runtime (e.g. any garbage collection) when it runs. This may be tricky to code (if you don't have tools ensuring that property) and generally need some knowledge about implementation details of the compiler, and uses some basic unsafe construct (e.g. the one requesting memory from the OS, e.g. thru POSIX mmap function or the underlying mmap(2) system call)

I know that there are some projects that somehow compile OCaml (...) to run on bare bones Xen hypervisor

You are probably thinking of MirageOS, an unikernel coded mostly in Ocaml. But it uses an adaptation of Ocaml runtime (notably the GC) ported to Xen and hand-coded in C. Xen is an hypervisor emulating (in a VM) some kind of x86-64 hardware system, so don't provide any garbage collector (but abstracts some common hardware devices and perhaps very low level drivers).

Notice that C is widely used as a "portable assembler". You could use LLVM (or C-- by S.Peyton Jones & Norman Ramsey, which unfortunately stalled) for that role (but LLVM is written in C++).

Community
  • 1
Basile Starynkevitch
  • 32,434
  • 6
  • 84
  • 125
5

Is there still any functional programming language that doesn't rely on C runtime?

The answer to this exact question is yes: C is not the only low-level language which is suitable as a compilation target (although definitely the most popular one). For example, the Embedded ML described in Functional Programming for Embedded Flight Software Development by A. J. Harris has a Forth runtime (as well as a C one).

The answer to your other question, namely "is it possible to implement a functional language all in itself", i.e. without a huge runtime written in an external language, is also yes as far as I'm concerned. Uniqueness Types, as presented in e.g. the Clean language, enable possibility to model destructive updates while maintaining a referential transparency. The Mercury language, which is mentioned in your question, has a Compile Time Garbage Collection feature, which eliminates the need for a conventional GC. Lazyness, I believe, has to be handled explicitly, i.e. you can't have true call-by-need semantics without the runtime support, but you still can implement lazy data structures which would cover most of the need for lazyness.

I believe the reason we don't see any mainstream functional languages implemented this way is that although possible, it's rather impractical to do so, due to both efficiency and language complexity reasons.

M-x
  • 216
  • 1
  • 2
  • In Haskell, laziness is just implemented with thunks - that is, the value becomes a function that calculates the value the first time it is used and then caches (memoizes) it as long as it remains in scope for. – Benjamin Gruenbaum Jun 30 '15 at 08:45
2

In principle? Yes. C is a programming language like all others. What C can do, other languages can be made to do.

In practice? Rarely. C is near-ubiquitous as a systems programming language (there are exceptions, but they will be provided in the outraged comments, so I don't bother listing them), and it is almost always a better idea to use what is already available than to write your own low-level OS wrapper. (There is also a bit of synergy in that many OS kernels are themselves written in C, so calling conventions etc. are a bit easier to handle when you use C). There is value in having a universal standard, even if it is such an old, warty standard as C is, therefore people rarely bother avoiding it on purpose.

Kilian Foth
  • 107,706
  • 45
  • 295
  • 310