LISP basis for computable functions on S-Expressions.

Hi all,

I want to make a minimal set of LISP functions, by which all computable functions on S-Expressions
can be computed. {car, cons, cdr, atom, equal, if} is a basis. I don't know how to prove that this is the minimal. Can you help me?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

All you need is lambda, dah dah dah dah ...

... and normal-order evaluation.


You need lambda. You need if. You need list syntax.

For pure lambda calculus (think "lisp with no symbol tables") that's it.

If you want the convenience of naming procedures and variables, you have to add define, atom syntax, and quote. Quote gets you atomic literals as opposed to variable references from your atom syntax, and lists as opposed to procedure calls from your list syntax. This gets you a purely functional lisp with Church data.

Finally if you want mutation you'll need set! or setq or whatever you want to call it. This gets you an impure lisp with Church data.

And that's all you actually need, I think.

Because Church datums are generally not humanly readable in their raw form as a tightly woven knot or long chain of function applications on closures, reader syntax for constants of a few predefined data types (numbers, strings, and pairs/lists at least) are a giant step forward in usability.

Reader syntax can be applied to Church data or you can add other representations of data to your system. Church datums can use Lambda to create their own semantics. "raw data" representations on the other hand cannot. So if you represent data other than as a composition of functions and closures, They are just funny-looking "atoms" unless you also provide builtin functions that perform a minimal set of operations on them.

Most people choose to represent at least pairs in a non-church form, since a non-church read syntax parser for pairs and lists is actually simpler. So they have to implement pair operations such as cons, car, cdr as primitives rather than in terms of lambda. Most people choose to represent numbers in a non-Church form since numeric operations are vastly more efficient on them, thus have to implement addition, subtraction, etc as primitives rather than in terms of lambda. Etc.

I think that's enough to get you started.

Not Quite

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!

True, but they are duals in expressiveness.

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

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.


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


(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

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

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


(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 with that....

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.

No problem

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

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

Decides whether to -- but how?

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.

Church encoding

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

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!

On the topic of Sparta

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?

proving minimalism

I don't know how to prove that this is the minimal. Can you help me?

"Minimal" in what sense? and, in what sense is that supposed to be a basis set?