Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is there a functional language which allows to use stack semantics - automatic deterministic destruction at the end of the scope?

share|improve this question
    
Deterministic destruction is really only helpful with side-effects. In the context of pure functional programming, that just means ensuring that certain (monadic) actions always run at the end of a sequence. As an aside, it is easy to write a functional concatenative language that doesn’t need garbage collection. –  Jon Purdy Mar 10 '12 at 21:50
    
I'm interested in the contect of the question, whats one got to do with the otehr? –  mattnz Mar 11 '12 at 1:29
1  
In a functional language without garbage collection, I don't see how structural sharing of immutable data structures is possible. It may be possible to create such a language, but it's not one I'd use. –  dan_waterworth Mar 12 '12 at 9:41
add comment

3 Answers

Not that I know of, though I'm no functional programming expert.

It seems pretty difficult in principle, because values returned from functions may contain references to other values that were created (on the stack) within the same function, or might just as easily have been passed in as a parameter, or referenced by something passed in as a parameter. In C, this issue is dealt with by allowing that dangling pointers (or more precisely, undefined behaviour) may occur if the programmer doesn't get things right. That's not the kind of solution that functional language designers approve of.

There are potential solutions, though. One idea is to make the lifetime of the value a part of the type of the value, along with references to it, and define type-based rules that prevent stack-allocated values from being returned from, or referenced by something returned from, a function. I've not worked through the implications, but I suspect it would be horrible.

For monadic code, there's another solution which is (actually or almost) monadic too, and could give a kind of automatically deterministically-destructed IORef. The principle is to define "nesting" actions. When combined (using an associative operator), these define a nesting control flow - I think "XML element", with the left-most of the values providing the outer begin-and-end-tag pair. These "XML tags" are just defining ordering of monadic actions at another level of abstraction.

At some point (at the right hand side of the chain of associative composition) you need some kind of terminator to end the nesting - something to fill the hole in the middle. The need for a terminator is what probably means the nesting composition operator isn't monadic, though again, I'm not entirely sure as I haven't worked through the details. As all applying the terminator does is convert a nesting action into effectively a composed normal monadic action, maybe not - it doesn't necessarily affect the nesting composition operator.

Many of these special actions would have a null "end-tag" step, and would equate the "begin-tag" step with some simple monadic action. But some would represent variable declarations. These would represent the constructor with the begin-tag, and the destructor with the end-tag. So you get something like...

act = terminate ((def-var "hello" ) >>>= \h ->
                 (def-var " world") >>>= \w ->
                 (use-val ((get h) ++ (get w)))
                )

Translating to a monadic composition with the following execution order, each tag (not element) becoming a normal monadic action...

<def-var val="hello">  --  construction
  <def-var val=" world>  --  construction
    <use-val ...>
      <terminator/>
    </use-val>  --  do nothing
  </def-val>  --  destruction
</def-val>  --  destruction

Rules like this could allow C++-style RAII to be implemented. The IORef-like references cannot escape their scope, for similar reasons to why normal IORefs can't escape the monad - the rules of the associative composition provide no way for the reference to escape.

EDIT - I nearly forgot to say - there's a definite area I'm unsure about here. It's important to ensure that an outer variable can't reference an inner one, basically, so there must be restrictions one what you can do with these IORef-like references. Again, I haven't worked through all the details.

Therefore, construction could e.g. open a file which destruction closes. Construction could open a socket which destruction closes. Basically, as in C++, the variables become resource managers. But unlike C++, there are no heap-allocated objects that cannot be automatically destructed.

Although this structure supports RAII, you still need a garbage collector. Although a nesting action can allocate and free memory, treating it as a resource, there's still all the references to (potentially shared) functional values within that chunk of memory and elsewhere. Given that the memory could be simply allocated on the stack, avoiding the need for a heap free, the real significance (if there is any) is for other kinds of resource management.

So what this achieves is to separate RAII-style resource management from memory management, at least in the case where RAII is based on simple nesting scope. You still need a garbage collector for memory management, but you get safe and timely automatic deterministic cleanup of other resources.

share|improve this answer
    
I fail to see why a GC is necessary in all functional languages. if you have a C++ style RAII framework in place, the compiler can use that mechanism as well. Shared values are no problem for RAII frameworks (see C++'s shared_ptr<>), you still keep deterministic destruction. The one thing that is tricky for RAII are cyclic references; RAII works cleanly if the ownership graph is a Directed Acyclic Graph. –  MSalters Mar 12 '12 at 10:27
    
The thing is, functional programming style is practically built around closures/lambdas/anonymous functions. Without GC, you don't have the same freedom to use your closures, so your language becomes significantly less functional. –  comingstorm Mar 12 '12 at 17:29
    
@comingstorm - C++ has lambdas (as of C++11) but no standard garbage collector. The lambdas carry their environment in a closure too - and elements in that environment may be passed by reference, as well as the possibility of pointers being passed by value. But as I wrote in my second paragraph, C++ allows the possibility of dangling pointers - it's the programmers (rather than the compilers or runtime environments) responsibility to ensure that never happens. –  Steve314 Mar 12 '12 at 23:19
    
@MSalters - there are costs involved in ensuring that no reference cycles can ever be created. It's therefore at least non-trivial to make the language responsible for that restriction. Assigning to a pointer probably becomes a non-constant-time operation. Though it may still be the best option in some cases. Garbage collection avoids that issue, with different costs. Making the programmer responsible is another. There's no strong reason why dangling pointers should be OK in imperative but not functional languages, but I still don't recommend writing pointer-dangling-Haskell. –  Steve314 Mar 12 '12 at 23:32
    
I would argue that manual memory management means you don't have quite the same freedom to use C++11 closures as you do Lisp or Haskell closures. (I am actually quite interested in understanding the details of this tradeoff, as I would like to write a functional systems programming language...) –  comingstorm Mar 13 '12 at 0:26
show 2 more comments

If you consider C++ to be a functional language (it has lambdas), then it is an example of a language that doesn't use a garbage collection.

share|improve this answer
5  
What if you don't consider C++ to be a functional language (IMHO it isn't, although you can write a functional program with it, you can also write some extremely non-fucntional (functioning.... ) programs with it) –  mattnz Mar 10 '12 at 20:53
    
@mattnz Then I guess the answer doesn't apply. I am not sure what happens in other languages (like for example haskel) –  BЈовић Mar 10 '12 at 20:57
6  
Saying C++ is functional is like saying that Perl is Object-Oriented... –  Dynamic Mar 10 '12 at 21:45
    
At least c++ compilers can check for side effects. (via const) –  tp1 Mar 10 '12 at 23:09
    
@tp1 - (1) I hope this isn't going to regress into who's language is best, and (2) that's not really true. First, the really important effects are mostly I/O. Second, even for effects on mutable memory, const doesn't block them. Even if you assume there's no possibility to subvert the typesystem (generally reasonable in C++), there's the issue of logical constness and the "mutable" C++ keyword. Basically, you can still have mutations despite const. You are expected to ensure that the result is still "logically" the same, but not necessarily the same respresentation. –  Steve314 Mar 11 '12 at 3:12
show 4 more comments

I have to say that the question is a bit ill-defined because it assumes that there is a standard collection of "functional languages". Almost every programming language supports some amount of functional programming. And, almost every programming language supports some amount of imperative programming. Where does one draw the line to say which is a functional language and which is an imperative language, other than guided by cultural prejudices and popular dogma?

A better way to phrase the question would be, "is it possible to support functional programming in a stack allocated memory". The answer is, as already mentioned, very difficult. Functional programming style promotes the allocation of recursive data structures at will, which requires a heap memory (whether garbage collected or reference counted). However, there is a pretty sophisticated compiler analysis technique called region-based memory analysis using which the compiler can divide the heap into large blocks that can be allocated and deallocated automatically, in a way similar to stack allocation. The Wikipedia page lists various implementations of the technique, for both "functional" and "imperative" languages.

share|improve this answer
    
IMO reference counting is garbage collection, and having a heap doesn't imply that those are the only options anyway. C mallocs and mfrees using a heap, but has no (standard) garbage collector and only reference-counts if you write the code to do that. C++ is almost the same - it has (as standard, in C++11) smart pointers with built in reference counting, but you can still do manual new and delete if you really need to. –  Steve314 Mar 11 '12 at 23:25
    
A common reason for claiming that reference counting isn't garbage collection is that it fails to collect reference cycles. That certainly applies for simple implementations (probably including C++ smart pointers - I haven't checked) but it's not always the case. At least one Java virtual machine (by IBM, IIRC) used reference counting as the basis for its garbage collection. –  Steve314 Mar 11 '12 at 23:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.