Minimum set of primitives?

[Kragen]

On Wed, 18 Mar 1998, Rodrigo Ventura wrote:
> >>>>> "Chris" == Chris Hanson <cmh@greendragon.com> writes:
> 
>     Chris> What set of primitives would absolutely need to be supported for a sort of
>     Chris> "proto-Lisp", which could be used as an implementation language for a more
>     Chris> full-featured Lisp (for example, Scheme)?
> 
>         From the theoretical point of view, one can go as low as a
> Turing machine, and assert that a Turing machine can implement any
> language (in fact, any computable function).

The lambda calculus is equivalent to a Turing machine, and it's a lot
easier to use in Lisp :)

The theoretical point of view is not very useful.  Here's an
example of why:

If you have lambda, cons, car, cdr, some conditional (cond, if, what
have you) and null?, (oh, and some way of defining a function -- I'll use the
Scheme `define', with a single cell for either function or value) you
can implement arithmetic:

; Base-1 arithmetic with the lambda calculus.  Uses only cons, car, cdr,
; if, null? and define.  Uses quote for the restricted purpose of quoting
; the empty list.
; Kragen Sitaker, 1998-03-18

(define nil '())

(define #f (null? (cons nil nil)))
(define #t (null? nil))
(define zero nil)

(define incr (lambda (x) (cons nil x)))
(define decr (lambda (x) (cdr x)))
(define zero? (lambda (x) (null? x))

(define plus 
	(lambda (a b) 
		(if (zero? a) b
			(plus (decr a) (incr b)))))

; doesn't work if b>a; applies cdr to ().  The result of this
; depends on your Lisp/Scheme system.  It's OK in Lisp (returns nil,
; which means the result is zero if b>a; Scheme forbids it.  Most
; Scheme implementations will probably do the same as Lisp.
; SIOD does.
(define minus
	(lambda (a b)
		(if (zero? b) a
			(minus (decr a) (decr b)))))
(define arith-equal?
	(lambda (a b)
		(if (zero? a) (zero? b) 
			(if (zero? b) #f
				(arith-equal? (decr a) (decr b))))))

(define not (lambda (a) (if a #f #t))

(define arith-greater?
	(lambda (a b)
		(if (zero? a) #f
			(if (zero? b) (not (zero? a))
				(arith-greater? (decr a) (decr b))))))

(define arith-less?
	(lambda (a b) (arith-greater? b a))

(define multiply
	(lambda (a b) 
		(if (zero? a) zero
			(plus b (multiply (decr a) b)))))

etc.

> Of course some sets must be smaller
> than others, but our concern here also includes efficiency. The
> minimal set may not be the most efficient one. Of course it isn't. 

Agreed! Would you really want to use a Lisp that implemented arithmetic
like the above?  Probably not, for two reasons:

1. It's a lot slower than the native machine methods to do the same thing.
2. Its slowness grows as the numbers get bigger.  It would be better to
use base-2 or something.

#1 is a little disturbing.  It implies that the "minimal" set depends
on the machine you're using.  If your machine is an i386, it has
instructions to do BCD arithmetic, for example.  Assuming some users of
your Lisp have a use for BCD arithmetic, you really ought to provide
them with access to the underlying machine's BCD arithmetic
capabilities, instead of forcing them to implement their own in Lisp. 

(Not many people use BCD arithmetic these days, of course, but there may
be other features of your processor that you need to find some way of
exposing for efficiency: double-length multiply results and dividends,
carry flags for multiple-precision arithmetic, vector instructions,
quick multiplies and divides by powers of two, etc.  There may even be
features you need to find some way of exposing for expressiveness, such
as SMP inter-processor synchronization facilities.)

#2 is simply an accident of the particular simple example above, and is not
really important for the larger discussion.

OK, enough pontificating for now :)

Kragen