What is needed to implement a usable functional language

Question

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?

• Joey Adams: 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).

Answer 1

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).

• Bill K: I'll accept this because it was well thought out and interesting--but it was almost the exact opposite of what I was asking. I was wondering how difficult it would be to program, what the users would be missing (this is for very simple math-based use cases). In fact, the one thing I probably would not implement is Lambda functions, adds complexity for little value if you can simply want to define functions and call them. Thanks though, I spent quite a while learning from this response.
• greyfade: @Bill K: Sorry, I thought my answer covered it all. But to answer the rest of your question: All you need beyond this is some way to interact with the environment (I/O, system calls, etc.) It doesn't make programming any more difficult, and you don't need those other "normal" features. Scheme and Haskell demonstrate this well, since both are implemented as just a thin layer over lambdas.
• Dan: 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.