# What is needed to implement a usable functional language

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?

• Shameless plug: I implemented a fairly simple dynamically-typed Haskell-wannabe interpreter for the TI-89 graphing calculator a few months ago. It supports lambda expressions, lazy evaluation, if/then, top-level let declarations, infix syntax based on Haskell, and several functions from the Haskell Prelude, but little else. It's rather slow on a 10MHz calculator (`sum (1..1000)` takes about one second). – Joey Adams Mar 1 '11 at 1:07

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,
• As an addendum to this, Haskell actually compiles all of its code through a lambda calculus-like language (called Core), augmented with `let` and `case` statements. So this kind of thing is used in practice, but needs some extras to be practical. – Dan Apr 28 '14 at 20:36