Lambda the Ultimate

You don't need "if" given normal-order evaluation. The untyped lambda calculus really is quite spartan.

You can be even more spartan, though, and stick with the SK combinator calculus!

You don't need "if" given normal-order evaluation. Conversely you don't need normal-order evaluation given "if." One of them is needed for the bare semantic minimum, but it doesn't matter which. I pointed at "if" because it's an easier concept to communicate.

Why do you need normal order evaluation?

(define (if p a b) (p a b)))
(define (true a b) (a))
(define (false a b) (b))

For the OP: Algebraic data types.

Product

(define (pair a b) (lambda (f) (f a b)))

(define (first c) (c (lambda (a b) a)))
(define (second c) (c (lambda (a b) b)))

Sum

(define (left a) (lambda (f g) (f a)))
(define (right b) (lambda (f g) (g b)))

(define (case v f g) (v f g))

With these you can define booleans, numbers, lists & much more.

Why do you need normal order evaluation?

A contemplation of that question is prompted by Exercise 1.5 in Section 1.1.6 of SICP.

Wrap the then and else forms in a lambda, like in the implementation of if, true and false I gave in my previous message:

(define (if p a b) (p a b)))
(define (true a b) (a)) <-- note the parens around a
(define (false a b) (b)) <-- note the parens around b

Example:

(if true (lambda () 2) (lambda () 4))

It doesn't look good, but that wasn't a requirement of the OP. You *only* need lambda, you do not need normal order evaluation if you don't have if.

The problem is that with your definition of 'if', in the absence of normal-order evaluation, you may have to evaluate a nonterminating (or just unneccessary) consequent or alternate when you call it.

The point is that even without normal order evaluation, you can control evaluation order by wrapping things in lambdas. So to use 'if' with the definition Jules gave, instead of writing,

if p a b

as you would in a normal order language, you instead write,

if p (\x.a) (\x.b)

The 'if' function decides whether to evaluate the consequent or alternative based on the predicate. This doesn't have the same interface as the 'if' we are used to, and so you could argue that this isn't a "real lisp." But, it does have the same expressive power.

Exactly. If you have macros you could provide a syntax that automatically wraps things in lambdas:

(defmacro (if p a b) `(if* ~p (lambda () ~a) (lambda () ~b)))

You could also argue that lambda + normal order evaluation certainly isn't a real Lisp ;)

To paraphrase what you said: The if function evaluates the consequent if the the predicate is true, and the alternative otherwise. But this definition is circular!

Smalltalk uses lambdas in its version of if, which is p ifTrue: [x] ifFalse: [y]. But the reason that that works is that class dispatching is considered primitive, and so class True implements this method as evaluating x only, and class False as evaluating y only, unwrapping just one of the lambdas. But obviously the implementation of class dispatching involves conditionals!

With normal order, if is really just an ordinary function.

The definition of if that Jules gave is a function. The secret sauce is in the definitions of true and false. Look at Jules' definitions above. They each take two arguments, with true evaluating and returning the first argument and false evaluating and returning its second argument. All if does is pass both options to the predicate (which is assumed to be a properly encoded boolean).

Class dispatching does not have to be implemented with conditionals. You can store pointers to the methods in a table (vtable) and call this.class.vtable[method](this,args). This does not involve conditionals, only array lookups and function calls.

It seems impossible at first, and I didn't believe it when I saw it, but you really can implement conditionals without conditionals!

You can be even more spartan, though, and stick with the SK combinator calculus!

Then there's also Iota and Jot. Discussed before, but there's a fixed link here: Iota and Jot: the simplest languages?