OpenEuphoria

Re: Homogeneous sequence

• Posted by Robert Craig <rds at RapidEuph?ria.co?> Aug 12, 2007
• 664 views

CChris wrote:
> You are painfully aware that type checking has a O(N) complexity, where N is
> not the legth, but the number of all atoms in all your subsequences. Reguar
> type checking is probably very inefficient here.

This reminds me of a proposed extension to the type system
that various people, including myself, have thought about before.
It would be intuitively clear, and somewhat useful, to allow
type declarations such as:

sequence of integer x
  sequence of object x
  sequence of sequence x
  sequence of sequence of atom x
  sequence of my_user_defined_type x
  etc.

In many cases this would reduce the type-checking cost from
O(n) to O(1), since the type-check could be limited to a
single value, e.g.

  x[5] = expression

would only have to test x[5], not all of x, as you would need
today if you made your own user-defined type that loops over
all of x to enforce that it only contain elements of say
integer, or some other type.

Stricter types would help to catch bugs earlier in the code, 
and document variables more precisely.

Type information, such as this, could also in many cases 
help the Translator to produce slightly faster C code.

I spent a lot of time thinking about this a few years ago.
I didn't proceed with it because:
  
  * I was worried that since the existing user-defined type
    system is not used all that much, perhaps this enhancement
    to the type system would not be used much either. People 
    might be content to just say:
         sequence x
    rather than the much wordier:
         sequence of integer x
    On the other hand, this enhancement might encourage much more
    use of user-defined types.

  * Newbies might be confused, and put off by all this, 
    thinking it was somehow necessary to provide full and proper
    types for everything.

  * It seemed at the time to be a fair bit of work, and extra 
    baggage added to the language, for just a small gain.

  * In many cases, the Translator deduces this information by
    examining all uses of a variable across the whole program.

But perhaps we should reconsider this idea.

Regards,
   Rob Craig
   Rapid Deployment Software
   http://www.RapidEuphoria.com