[plt-scheme] Smallest set of operators

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Fri Feb 2 15:31:20 EST 2007

On Feb 2, 2007, at 2:53 PM, Carl Eastlund wrote:

> I interpreted 'implement' differently than you.

That was exactly what I meant when I asked Paulo to read up on  
expressiveness. The word 'implement' is so imprecise that the  
question doesn't denote. Here are three meanings:

  1. implement = definable as a function/macro
  2. implement = definable via a compiler transformation
  3. implement = definable via an interpreter (with access to source  

Unless you describe 'implement' (technically the class of allowable  
translations), you haven't done your homework. And btw, even if you  
choose option (1), you are still in trouble because it is too vague.

Over decades people have random answers to this question without  
specifying 'implement' only to discover (or have discovered by  
someone else) that the answer is inconsistent.

-- Matthias

> I don't believe
> 'implement' necessarily means 'with a level of indirection similar to
> an interpreter/compiler'.  It remains for Paulo to explain which way
> he meant, but I believe my interpretation is consistent with his
> question and his responses.
> --Carl
> On 2/2/07, Robby Findler <robby.findler at gmail.com> wrote:
>> Paulo explicitly said "implement" when asked, not the below (but  
>> those
>> pointers were also provided to him, in Matthias's original reply).
>> Robby
>> On 2/2/07, Carl Eastlund <cce at ccs.neu.edu> wrote:
>> > On 2/2/07, Paulo J. Matos <pocm at soton.ac.uk> wrote:
>> > >
>> > > I'm really sorry but I really can't grasp what's so hard to  
>> understand
>> > > in my question. I keep saying that the set of primitive values  
>> (let's
>> > > call it this instead of operators) needs to belong to scheme.  
>> So, no
>> > > C, no lambda calculus, no whatever complicated name, logic or
>> > > calculus... Scheme!!! You get a set of scheme primitives to  
>> implement
>> > > the rest of the language. Which ones do you pick for a minimal  
>> set???
>> > > Is this too vague?
>> >
>> > Well it seems clear to me what you mean.  You want to start with a
>> > minimal subset of Scheme such that you can introduce the rest of  
>> the
>> > standard Scheme bindings just by programming in that subset.  So C
>> > isn't good enough because it's not a subset of Scheme, the lambda
>> > calculus isn't good enough because it can simulate, but not  
>> provide,
>> > the Scheme primitives, and so forth.
>> >
>> > In general, you'll need the most primitive constructors, accessors,
>> > and mutators for primitive types, the most expressive constructs  
>> for
>> > control flow (conditionals, continuations, etc.) and data flow
>> > (multiple values, etc.), and of course the macro system.  Some
>> > features might be expressible as others, but fundamental types that
>> > are guaranteed to be distinct must be provided natively, and
>> > fundamental language operations can't be simulated.
>> >
>> > I don't know that my answer is terribly illuminating - these
>> > guidelines seem pretty obvious to me - and I'm not going to take  
>> the
>> > time to actually go through the list and pick a "basis" for the
>> > bindings.  But this is the general process I'd go through if I did.
>> >
>> > --
>> > Carl Eastlund
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.