2

How are Haskell, Scala,... and functional programming languages in general implemented in the low level? That is, how a computer can actually run a functional program if it's Von Neumann? How is the code translated (usually interpreted, I don't know if there are compiled functional languages)?

nohamk
  • 325
  • 2
  • 11
  • 1
    The Glasgow Haskell Compiler (GHC) compiles to native code on a number of different architectures—as well as to ANSI C—using C-- as an intermediate language. GHC has become the de facto standard Haskell dialect – old_timer Mar 12 '16 at 02:35
  • The back end of the compiler transforms Core code into an internal representation of C−−, via an intermediate language STG (short for "Spineless Tagless G-machine").[7] The C−− code can then take one of three routes: it is either printed as C code for compilation with GCC, converted directly into native machine code (the traditional "code generation" phase), or converted to LLVM virtual machine code for compilation with LLVM. In all three cases, the resultant native code is finally linked against the GHC runtime system to produce an executable. – old_timer Mar 12 '16 at 02:35
  • 1
    30 seconds worth of googling... – old_timer Mar 12 '16 at 02:35
  • I was asking how it is done, not what. How do you translate it taking into account that C (and assembly) are imperative and procedural, not functional. OOP is slightly different, but in the end is imperative. I understand how an OOP program is implemented. But how do you do it with functional programming? – nohamk Mar 13 '16 at 00:20
  • 2
    @Jose It's not all black or white. In fact, you can write functional programs in C, even if C is not exactly a functional language. The same holds for Java. – Ingo Mar 13 '16 at 14:20
  • Von Neumann architecture is an implementation of Turing machine. In 1937, turing machine was proven to be idential to lambda calculus which is the basis of functional programming. https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis –  Apr 20 '16 at 01:00

2 Answers2

2

Short answer:

By converting the functions to sequences of actions (instructions in some virtual or real machine).

Longer answer:

Consider this functional program, using a Lisp notation to free us from syntactical difficulties:

;; function definitions
(defun square (x) (* x x))
(defun difference (a b)
  (if (> a b)
    (- a b)
    (- b a)))
;; actual program
(difference (square 5) 5)

Assuming strict (not lazy) evaluation, before you can compute the difference, you obviously need to calculate the square. Generalizing on this idea means that in order to compute a function, you first need to compute it's arguments. The order in which the arguments are computed may be unspecified, but for simplicity's sake let's assume that they're computed from left to right. Then, you could transform the above program (omitting function definitions) into the following imperative description:

1: use value 5 as parameter
2: call square using 1 parameter, use result as parameter
3: use value 5 as parameter
4: call difference using 2 parameters

This sequence of actions can be relatively easily compiled for example for a stack based machine:

square:
   dup ; duplicate top of stack
   mul ; pops 2 numbers from stack, multiplies them and pushes the result
   ret

difference:
   compare_greater_than ; uses the top 2 numbers from stack, pushes result
   jmpif L ; pops 1 number from stack, jumps if non zero
   swap ; swap top 2 numbers on stack
L: sub
   ret

main:
   push 5
   call square
   push 5
   call difference

Of course this is only a very rough sketch, but hopefully gives you an idea about where to start. I've implemented a small sketch as well as a more complete version in two of my other answers here. Both are examples of how interpreting a functional program might look like.

Then, there are also good tutorials on how to actually implement functional languages, like http://www.buildyourownlisp.com/.

My answer completely focuses on the "practical" approach. There's also a lot of theory which I left out completely, like the spineless tagless G-machine, transformation to continuation passing style or some serious graph stuff, but I hope my answer gives you an idea of where to start.

Community
  • 1
  • 1
Daniel Jour
  • 15,896
  • 2
  • 36
  • 63
2

You are committing logical fallacies, when you ask:

That is, how a computer can actually run a functional program if it's Von Neumann?

But our computers can compute anything that can be computed at all, irrespective of the hardware architecture. It is as if you were asking: How can a computer help in chemistry, when it consists of electronic elements.

Ingo
  • 36,037
  • 5
  • 53
  • 100