Where do the names value/expression kept in functional programs?

Question

In C#, all the value fields like int, float are kept in stack and all the reference variables pointers are in stack and the actual values are kept in heap. (hope my understanding is correct here).
1. Since in functional programming model there is no value and reference type, where do the name symbol values are kept?
2.How does the stack and heap come into play on functional programs?
Thanks

Answer 1

You're trying to compare C#, which is one specific language, with functional languages all as a group. This is an apples-to-oranges comparison (or maybe more accurately, apples-to-spices comparison?).

Within imperative languages already you can observe differences between what values are stored in the stack vs. which ones go on the heap. For example, C and C++ (as I understand it) allow the programmer to manually choose which of these two ways they want for any type.

And another subtlety is the difference between what the language guarantees to the programmer vs. the way the language is implemented. One example is that recent versions of Oracle's Java VM have an optimization that they call "escape analysis", which is able to allocate an object on the stack if the VM can prove that the object reference does not escape the method (determined after inlining is performed). So even though Java calls its object types "reference" types, this doesn't mean that it will be allocated in the heap. Quoting this article by Brian Goetz:

The Java language does not offer any way to explicitly allocate an object on the stack, but this fact doesn't prevent JVMs from still using stack allocation where appropriate. JVMs can use a technique called escape analysis, by which they can tell that certain objects remain confined to a single thread for their entire lifetime, and that lifetime is bounded by the lifetime of a given stack frame. Such objects can be safely allocated on the stack instead of the heap. Even better, for small objects, the JVM can optimize away the allocation entirely and simply hoist the object's fields into registers.

Similar considerations apply to functional languages—it all depends on (a) what does the language promise, and (b) how the language implementation works and how sophisticated it is. But we can divide the functional language world into two important camps:

1. Eager functional languages like Scheme, Scala, Clojure or ML.
2. Lazy functional languages like Haskell.

There are several types of implementation for eager languages:

1. Pure stack-based implementations. These work same way as modern imperative languages. Common Lisp works this way. Since JVM functional languages use the same VM as Java does, so do they.
2. Pure continuation-passing style implementations. These are completely stackless—everything, including activation frames, is allocated on the heap. These make it easy to support tail-call optimization and first-class continuations. This technique I believe was pioneered by Scheme implementations, and is also used by the Standard ML of New Jersey compiler.
3. Mixed implementations. These typically are trying to be mostly stack-based but also support tail-call optimization, and maybe first-class continuations. Example: a bunch of random Scheme systems.

Lazy languages are another story, because the conventional call-stack implementation does not translate directly to lazy evaluation. The GHC Haskell compiler is based on a model called the "STG Machine", which does use a stack and a heap, but the way the STG stack works is different from imperative languages; an entry in the STG stack does not correspond to a "function call" as conventional stack entries do.