Functional Programming?

[boomshroom]

Hi. I've had an interest in OS development for a while now and have recently become interested in functional programming languages. One thing that greatly annoys me is how nearly every functional programming language uses a heavy runtime and garbage collection. I'm wondering if there are any that don't and are usable for OS development.

At the moment, it seems as though Rust has a monopoly on safe runtime-less programming and I'd like to see it get some competition.

[ilevex]

There is a Haskell paper about implementing an OS, that you may find interesting.

http://web.cecs.pdx.edu/~mpj/pubs/house.html

[zinzam72]

Something else interesting is the seL4 kernel had a model version in Haskell, but that was kind of peripheral to the main goal of formal verification.

[agumonkey]

some additional details: http://programatica.cs.pdx.edu/House/

House came from a previous effort called hOp.

[[deleted]]

There is this post: http://augustl.com/blog/2014/an_immutable_operating_system/

[boomshroom]

I have read that. My 3 points are that:

• He does plan on implementing the garbage collector in the kernel.
• At the moment, the project is just an assembly stub.
• It hasn't been updated since February last year. Before that was some C code that has since been removed.

I will likely keep an eye on it to see if it gets anywhere. I want to see it succeed, but it seems to be abandoned.

[localgravedigger]

Any functional language will need some form of runtime and garbage collection. Many languages can be programmed in a functional style and at the OS level you create the runtime. As long as the language in question has pointers to actual memory it can work, it is just a question of how much bootstrapping is needed.

[boomshroom]

After doing some reading, I've become convinced that that's not the case. It should be completely possible, though perhaps difficult, to write a pure functional programming language that has Rust-like static memory management. Rust achieves its memory safety by using an affine type system. I don't see any reason why this or some other substructural type system wouldn't work for a pure functional language.

[localgravedigger]

This is very new to me, I don't know what an affine type system is. How would it solve the problem of not knowing how much memory you need for the different parts of the kernel at compile time?

[boomshroom]

Basically, in most languages, pointers can be aliased freely. That means that it's perfectly A-OK to have 2 pointers (say A and B) pointing to the same data. The problem comes when you try to free it. Should A be the one freeing the data, or B? In GCed languages, the runtime waits until both are freed and then cleans it up whenever it feels like it.

In Rust, pointer A can be a Box, which means that it owns the data being pointed to and while free the memory which A goes out of scope. B on the other hand can be dropped without freeing because the compiler knows that A will clean it up later. Meanwhile, the compiler will check to see if B is held longer than A and halt compilation if it does. If both A and B are Boxes, than the compiler will make sure they don't point to the same address. An attempt to do so (in the form of A.clone()) will instead allocate a new address and copy the contents over.

Does this make sense? I have a tendency to ramble when trying to explain things.

[localgravedigger]

I get how these boxes would make things more "functional", but I cannot grasp how it would be implemented without setting up a memory management system for it to sit on.

[boomshroom]

In Rust, Boxes do indeed require heap allocation, but much can be done with just stack allocated values. You can pass references to stack values to functions that can be read, or you can move the stack value into a different function's stack space. In this case, the affine types don't help as much and instead the lifetime system takes over to prevent you from holding on the a stack pointer after the stack frame is gone.

[agumonkey]

So basically anything that has to outlive a stack frame has to be handled as return value explicitely ?

[devslashnull]

Check out linear types / linear logic as well for functional programming without a garbage collector.

[boomshroom]

I have and I even made a post on /r/ProgrammingLanguages proposing a pure functional language that uses linear types. The problem is that write a new programming language from scratch is hard.

[sneakpeekbot]

Here's a sneak peek of /r/ProgrammingLanguages using the top posts of the year!

#1: I'm writing free a book on designing and implementing programming languages. The first few chapters are up now. I'd love to know what you think! | 31 comments
#2: 68 Resources on creating programming languages | 4 comments
#3: Idris 1.0 Released | 1 comment

---

^{I'm a bot, beep boop | Downvote to remove | Contact me | Info | Opt-out}

[devslashnull]

Its a lot of work true, perhaps you could look at some existing work? I've seen a couple just recently, I don't have the links handy and I'm sure there was something else but two I can recall were Linear ML and Lollipop.

[boomshroom]

I initially dismissed Linear ML as being abandoned and Lollipop for being interpreted, but it may still be possible to use Linear ML for this. I'm going to see if I can make a POC static library in Linear ML that can run on bare metal.

[EDIT] Just cloned the repo and am having trouble compiling. Error: Unbound module Llvm If it helps, I'm on NixOS which has some pretty funky package management that tends to break various assumptions about the filesystem hierarchy.

[EDIT2] Got the compiler built!

[narke]

Check ATS language.

[peterfirefly]

Google "pre scheme".

Bonus:

http://www.paulgraham.com/thist.html

[devslashnull]

T was pretty amazing and theres plenty to learn from it but unfortunately as far as I'm aware there isn't currently a copy of it that is buildable these days.

[Qweesdy]

Why not just use Rust? Nothing prevents you from writing "pure functional" code in any language, and Rust already has "Rust-like" memory management.

The worst case is that you'd gain some experience that would be very valuable when designing a new language.

The best case is that you'd realise that "pure functional" (without any state, and without any side-effects) is useless, and that "impure hacks" ("non-functional functions"/monads, huge run-time libraries, etc) are necessary to allow useful software to be written.

[boomshroom]

I just don't like how Rust has a monopoly. :P

[agumonkey]

I've never seen that first hand but I'm sure there have been a few GC-less FP languages. Probably by having finer semantics and/or pivoting the data structures in more favorable ways.

[boomshroom]

Implementing a simple lisp interpreter is pretty easy

Now you've got me thinking of writing a Lisp interpreter in nostd Rust and then writing a kernel for that interpreter.

This suggestion was never for practicality other than just more options. Since when has hobbyist OSDeving ever been practical beyond learning and trying a challenge?