How would a CPU designed purely for functional programming be different?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

It would either change nothing or would harness massive parallel setting like in Reduceron and its successor PilGRIM¹ 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.