CPU's are to an extent designed with in mind the software that people will write for it, implicitly or explicitly.

It seems to me that if you look at the design of instruction set architectures, they are very "imperative", in the sense that each instruction encodes an imperative style command. It also seems to me that the current instruction set architectures have evolved partly based on the type of code programmers produce.

If one would design a CPU from scratch, knowing that it would only ever run programs written in a functional programming style, how would that CPU be designed differently from existing CPU's?

  • 9
    $\begingroup$ John Backus in his "Can Programming Be Liberated from the von Neumann Style?" mentions few such works (section 15). $\endgroup$ Feb 11 '19 at 9:54
  • $\begingroup$ Look for (graph) reduction machines or visit your local research library hoping to find a copy of W. Kluge's out-of-print book The Organization of Reduction, Data Flow, and Control Flow Systems (MIT Press, 1992). $\endgroup$
    – Kai
    Feb 11 '19 at 22:43
  • 2
    $\begingroup$ Also Koopman's book An Architecture for Combinator Graph Reduction (AP, 1990). Looking into Lisp machines is probably also worthwhile. en.wikipedia.org/wiki/Lisp_machine $\endgroup$
    – Pseudonym
    Jul 31 '19 at 7:36
  • $\begingroup$ I think fundamentally our machines will always be imperative as they execute over time, mutating their state. $\endgroup$
    – orlp
    Jul 31 '19 at 8:08
  • $\begingroup$ A couple useful CPU features would be native support for thunks and more efficient jumping. Also the CPU might be able to take some shortcuts knowing that certain locations in memory won't be overwritten in a certain scope and the CPU would not need to maintain a stack in the same way as in stack-based languages. $\endgroup$ Jul 31 '19 at 14:26

Actually, it has been done: https://en.wikipedia.org/wiki/Lisp_machine

One aspect in CPU design for FP is garbage collection. GC is very important for functional languages. Common implementations require that the GC can distinguish between pointers and non-pointer data. Effectively, that means storing an extra bit along your data. This is the reason that, for example, OCaml integers are only 31 bit on 32-bit architectures and 63 bit on 64-bit architectures. Integer arithmetic then involves awkward extra shifting operations. Other languages (or other OCaml data types) may waste whole machine words for that extra bit, thus using 128 bits for 64-bit integers. A CPU that is natively designed towards GC might have a 65-bit data bus but 64-bit arithmetic.

That said, a lot of non-functional languages also have garbage collection and would thus profit from respective architectures.

Another thing that comes to mind is that memory usage of FP typically is much more scattered than that of imperative programs. Mainly because it is less natural to use arrays. In consequence, these programs profit less from caching contiguous chunks of memory. So, an FP CPU might use different caching strategies.


It would either change nothing or would harness massive parallel setting like in Reduceron and its successor PilGRIM1 with a huge stack.

Statement that it would change nothing seems bold at first, but since CPU is sequential, there is a translation process (compilation) that uses available hardware to its extend for efficiency. Shall there be another architecture, some operations would be faster, some would need hacking tricks to speed it up.

Architecture that would make a difference would require map operation and lists to run faster (not the whole story, but it suffices to show the effect). There is no possibility to create dynamic changing hardware to natively run lists, so these gets stored in contigous memory. We stick to array representation of some form. For map, to run in non-sequential setting - we get back to Reduceron. So effectively one central processing for consecutive instructions, and support for parallel processing.

What might be different is possibility to load multiple functions and run them without frames juggling - but adding multiple units for functions would create a mess with accessing memory.

Adding to kne's answer, the GC would be benefitial to run as coprocessor, it would be very neat feature.

1: PilGRIM is properly described in Boeijink A., Hölzenspies P.K.F., Kuper J. (2011) Introducing the PilGRIM: A Processor for Executing Lazy Functional Languages. In: Hage J., Morazán M.T. (eds) Implementation and Application of Functional Languages. IFL 2010. Lecture Notes in Computer Science, vol 6647. Springer, Berlin, Heidelberg.

  • $\begingroup$ "There is no possibility to make recursion native". Could you explain why this is? It seems surprising at first to me. $\endgroup$
    – user56834
    Aug 3 '19 at 5:35
  • $\begingroup$ Also, is the reduceron something that could be a hard cpu, instead of running on a fpga? $\endgroup$
    – user56834
    Aug 3 '19 at 5:37
  • $\begingroup$ My bad, I meant native recursion, but it is probalby irrelevant. I have to revise a bit. $\endgroup$
    – Evil
    Aug 3 '19 at 8:50

First a bit of a joke: as running a 100% functional program never can do anything useful, it would suffice to have only a NOP instruction. ( I open this for flame wars ).

So, there will need to be some imperative instructions for IO and the usual support for imperative programming.

Otherwise it partly depends on the actual language used. The two on top of my mind are Haskell and Erlang.

I would Believe that Haskell could benefit from support for lists and maps. A list could be supported by specific hardware memory mappings, turning the linked list into a consecutive set of adresses. First element might be on adress n, second on adress n+1 and so on. To remove the first element from the list, you would simply change the pointer n. Finally, when you delete the n pointer all memory could be freed. Maps could be supported as associative arrays -- enter the search value and the memory system returns the item. No need for iterative searches.

Erlang in turn could benefit from support of messages/processes and tail recursion with full state. Messages and processes could be supported in various ways, one example might be to have an extremely large amount of processing cores. Tail recursion could be improved by a memory controller knowing allowing the state to be copied a lot faster, perhaps not copying large chunks of data but instead simply modifying the memory system pointers.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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