Needed to implement a usable functional language

functional programming

I've done some programming in a more-or-less functional style, but I've never really studied pure functional programming.

What is the bare minimum needed to implement a functional language?

As far as I can tell, you need:

  • The ability to define a function
  • The ability to call a function
  • parameter substitution
  • Some kind of "if" operation that can prevent recursion like "?:".
  • Testing operators or functions like "Less than" or "Equals"
  • A core library of fundamental functions and operators (+ -…)

This implies that you do NOT need:

  • Looping
  • variables (except for parameters)
  • sequential statements

This is for a very simple mathematical usage–I probably won't even implement string manipulation.

Would implementing a language like this significantly limit you in some way I'm not considering? Mostly I'm concerned about the lack of sequential statements and ability to define variables, can you really do without these "Normal" programming features?

Best Answer

What is the bare minimum needed to implement a functional language?

A Lambda. That's all. (See the lambda calculus.)

From there, you can construct functions to perform every task and represent many values. You can define new (named) functions with the Y-combinator form (PDF), and represent several values (like true and false) as functions. (Taking the idea to the extreme, you can represent all integral values as Church numerals.)

You don't even really need a special if form. It can be constructed as a collection of functions. JavaScript example:

true = function(x,y){ return x; }
false = function(x,y){ return y; }
ifelse = function(x,a,b){ x(a,b)() }
not = function(x){ return x(false,true) }
and = function(x,y){ return x(y,false) }
or = function(x,y){ return x(true,y) }

bool = and(not(true),or(true,false))
ifelse(bool, 
    function(){ alert("true!") }, 
    function(){ alert("false!") }
)

Unlambda is a real language that takes this idea to the logical extreme. It has only one type (lambda functions), and a handful of special convenience forms such as the identity function, K- and S-combinators, and a print function (which, except for print, can all be expressed as a collection of lambdas).

Related Topic