any functional language without GC?

If you think of it, memory allocation/de-allocation is really just side-effect, I wonder if there is a functional language that makes it explicit. Any advice is appreciated :-)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Explicit, or make sure GC is statically decidable

IIRC, PreScheme was restricted to constructs that could be easily translated to C, so the allocation had to be LIFO. I believe MLKit's regions also avoid real GCing. Of course, linear languages make allocation explicit (and deallocation mostly implicit in the consumption of arguments).

Note that memory [de]allocation are only side-effects if you consider them. The beauty of GC and implicit allocation is that it lets us ignore that aspect of the problem.

Processes

I think that you could program in Erlang without a GC and rely on process termination to reclaim storage. That should be like programming on Unix without calling free() and just making sure that each process terminates before malloc()'ing too much.

NB: It is a well-known but seldom used efficiency hack in Erlang to profile how much heap a particular type of short-lived process typically uses (e.g. a HTTP request handler) and use a special option on spawn to preallocate enough heap that the processes can usually terminate and be junked without GC'ing.

collecting processes

How does Erlang handle a process that is waiting for a message that will never arrive because no one knows its PID any longer? Seems like rather than eliminating GC, it just moves up a level and becomes a harder problem (distributed GC).

collecting processes

Erlang processes are like in Unix: explicit termination and not garbage collection. My impression is that distributed GC is not practical for applications that handle partial failure (i.e. real programs :-)

collecting processes

So this means if you are to subsitute processes for shared objects, you are eliminating GC by going back to manual resource management with all the same problems: leaked processes, dangling references to dead processes. It is not like programming without using free() since explicit process termination is equivalent to free().

Not quite

A process can terminate, which automatically does the clean-up. If you spawn a process to do some computation, once it sends back the result it can just go away, no action from the caller required.

Still, I agree, you wouldn't want to map objects to processes one-to-one.

Stack-based allocation

This sounds a lot like stack-based allocation/deallocation used in C/C++: "If you call a function to do some computation, once it returns the result its stack-based memory can just go away, no action from the caller required." Using processes in this way would seem to be equivalent to allocating everything on the stack, wouldn't it?

Yes, if you use processes in a specific way

If you immediately wait for acknowledgement from the spawned process, and each process terminates before the caller does, then you essentially have stack allocation (which is still an interesting way of dodging GC). But that's only one way of working with processes.

Observable side-effects

[...]memory allocation/de-allocation is really just side-effect[...]

Well maybe, but it's not usually an observable side-effect. So the presence of GC in a functional language doesn't affect your ability to reason about your programs as if they were side-effect free, which is the whole point, after all.

I'd say that GC (or some other form of automatic memory management) is pretty essential to functional programming, but that would depend on how you define a functional language.

For certain values of

For certain values of "manual" I'd consider type systems that effectively require you to prove all resources eventually die and give you room to prove when to be a way to allow manual memory management in a functional language - the region calculi underpinning MLKit and the like'd be an example.

ST monad in Haskell

The ST monad in Haskell makes memory operations pretty explicit. It's so explicit that you might be driven to look for languages that can hide this abstraction...

Functional programming without GC makes no sense

Local functions need to keep their free variables alive. There is no place to reclaim them explicitly.

Not to mention closures in

Not to mention closures in general.

Processes!

I will stick to my guns. You could meaningfully write e.g. Haskell programs without a garbage collector if you made them into cooperating Unix processes that will each terminate before generating too much junk. You could even keep them referentially transparent if they are just reading each other's results.

I had expected GNU utilities like ls, tail, and cat to take advantage of their short life span to ignore resource allocation but I just checked and it ain't so! For example cat can take many filenames as arguments and will close each file after copying and reallocate its buffers to match the next file's storage medium.

Details details details!

jhc

jhc is a Haskell compiler that attempts to use region inference instead of garbage collection.