Minimum set of primitives?

[Rodrigo Ventura]

>>>>> "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 question here is different. I believe there are several
sets of primitives on top of which any lisp-like language can be
implemented. For instance, you can implement an "if" construct using a
"case", or a "case" using "if"'s. 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. But
we are not interested in a very complex set of primitives. It seems to
me that the pre-scheme, on top of which scheme48 is implemented, is
too complex to be easly used to build more complex languages.

        Simplicity and efficiency are the two main concerns here,
IMHO. The resulting set may not be minimal in a strict sense.

        Regards,

-- 
--

*** Rodrigo Martins de Matos Ventura, alias <Yoda>
***  yoda@isr.ist.utl.pt, http://www.isr.ist.utl.pt/~yoda
***   Instituto de Sistemas e Robotica, Polo de Lisboa
***    Instituto Superior Tecnico, Lisboa, Portugal
***     PGP Public Key available on my homepage
*** Key fingerprint = 0C 0A 25 58 46 CF 14 99  CF 9C AF 9E 10 02 BB 2A