5
$\begingroup$

With my thin knowledge on embedded systems, compilers, and computer architectures, I know that the basics of computer memory(physical) are sort of like an array, with addressing which work like pointers. I see that imperative programming(which eventually unwraps to assembly, or the Turing Machine) fits this architecture very well.

I am a bit interested to see if there is a counterpart of physical memory that might fit the functional programming style. By "fitting", I am making the assumption that all pure functional languages can unwrap to be immutable lambda expressions(via Lambda Calculus). Now, with the array-like memory structure, we have to allocate and gc objects under the scene in order to get lambdas to work(because lambda expressions do not address operations on memory directly). Just as a thought experiment, is it possible to have a device that fits the need of memory in lambda expressions, while not containing a garbage collector?

Yes, I know that some imperative programming languages do use garbage collectors. However, when boiled down to assembly, it doesn't. So I am more curious about the evaluation of "pure" lambda expressions.

Just as a note, the lambda expressions I talk about include the fixed point operator(i.e. recursion).

Improve this question
$\endgroup$
8
  • $\begingroup$ What do you mean by "device"? Why do you think you need garbage collection? A turing machine has infinite memory. $\endgroup$
    – Bergi
    Commented Aug 31, 2016 at 4:11
  • $\begingroup$ For "device" I mean physical memory. And, forget about the Turing Machine I just mentioned. I use the term to contrast Lambda Calculus. Think about Assembly and Lambda Expressions instead. $\endgroup$
    – Carl Dong
    Commented Aug 31, 2016 at 4:13
  • $\begingroup$ I think GC is needed because Lambda Expressions never manage memory. At least, not the "array" like memory we generally have. In which case, we need to find a way to allocate objects as we evaluate an expression, and destroy them after evaluation. $\endgroup$
    – Carl Dong
    Commented Aug 31, 2016 at 4:14
  • 1
    $\begingroup$ There's no need to destroy them. We just will run out of memory eventually for some inputs, like on every physical device. A garbage collector is an implementation detail that helps to reduce the memory requirements. It will use mutation (unlike lamda expressions) and be written in assembly (or something that compiles to it). $\endgroup$
    – Bergi
    Commented Aug 31, 2016 at 4:21
  • 1
    $\begingroup$ Yeah, Lambda Calculus seems much less "physical" than Turing Machine, Well, I agree CS stackexchange might be the place to go, though. Is it possible to move the question there? $\endgroup$
    – Carl Dong
    Commented Aug 31, 2016 at 4:38

1 Answer 1

Reset to default
3
$\begingroup$

The topic is fairly broad.

Functional hardware has been explored in e.g. Lisp machines.

More on the theoretical side, you may want to read about the various abstract machines which have been proposed for running functional languages. Some of them are the SECD machine, the CAM (categorical), the Krivine machine, the STG machine.

Perhaps a more radical approach can be learnt by looking at the various graph-reduction machines. A pioneering work by Lamping describes how lambda can be run faster by rewriting graphs (!), instead of expressions. More recently, linear logic simplified the several rewriting rules.

Some of these approaches can give you some hint at how a custom functional hardware should be made to speed up execution.

For conventional hardware, the STG machine seems one of the most promising approaches.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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