You state that there should only be the few basic types currently defined in Arc. Paul's idea was to eventually get rid of strings (they are a special kind of list) and even numbers (they are a special kind of list too...). But he finally didn't, and won't, at least for numbers. He also said that this view (as few basic types as possible) finally forced him to develop a basic type system (with annotate, type, rep and isa) to distinguish between the raw list '(a a a a a) as the number 5, as the string "aaaaa" or as an actual list of 5 symbols.

In a way or another, you need explicit types if you want some kind of dynamic typing. Assembly language work the opposite way : e.g. you state (explictly or not) the arg of your function is a number. If the user gave you what he considers a string, too bad for him, because you can't distinguish between them. That means your function can't be polymorphic and you are stuck in an even more contrived space than with user types.

You need an isa function (call it isa or hasa, never mind as for now). For example, car should have a list, and nothing else. To do so, you have to check its type. If you want to redefine car so as to take scanners, generators, ... into consideration, that's easy too : just define your own version of car : if arg is a list, call the original car, else arg is a generator à la Python, so funcall it :

  (let _ car car
    (def car (x)
      (if (isa x 'list)
        (_car x)
        ((x)))))

  (let _car car
    (def car (x)
      (if (isa x 'list)
          (_car x)
        (isa x 'generator)
          ((rep x))
        (isa x 'array)
          (a-get x 1)
          (err "Not a valid type for car : " type.x))))

That means you can do something this way, for example :

  (annotate (listtab `((car . ,(fn (self) (self 'car))) (cdr . ,(fn (self) (self 'cdr))) x)

  (let _car car
    (def car (x)
      (if (isa x 'list)
        (_car x)
        (let tx type.x
          (tx!car rep.x)))))

  (= _car car _cdr cdr)

  (def hasa (obj typ)
    (if (no typ)
      t
      (and (type.obj (car typ)) (hasa obj (cdr typ)))))

  (def car (x)
    (if (acons x)
        (_car x)
      (hasa x scanner)
        (let tx type.x
          (annotate tx (tx!car rep.x)))
        (err "bad object for car")))

  ; define scanner type-class
  (= scanner '(car cdr))

  (= mycar [_ 0] mycdr [cut _ 1])
  ; Say s can answer to car and cdr
  (= fns (listtab `((car ,mycar) (cdr ,mycdr))))
  (= s (annotate fns "abcde"))
  (car s)
  -> #3(tagged #hash((cdr . #<procedure: mycdr>) (car . #<procedure: mycar>)) #\a)
  (car rep.s)
  -> #\a

Well someone has to load-test this thing!

> And it is even a very clever one, actually.

Thanks :)

> having to use rep on annotated data is, I think, the biggest mistake of that type system.

This is exactly this problem that got me thinking about types. I've been tempted to create a few types with annotate already, but each time I stopped because I didn't want to have to reimplement every function to work on my new type. Each time, I found a different solution to the problem that didn't require new types, which started me thinking "hey, perhaps we don't need new types after all!"

But you're right that you'll always need new types eventually. The solution you suggested is, I think, the right one. It's a bit like the object system in ANSI Common Lisp (pg even used hash tables to store the object's methods!) but it uses annotate to associate methods with objects.

  (redef hasa (obj typ)
    (if (and (isa obj 'cons) (is typ scanner))
      t))

In such a case a has-a semantics means that circle "has-a" function to compute its area, a function to compute its circumference, etc. An ellipse "has-a" function to compute its area, a function to compute its circumference, etc. It doesn't matter whether the user thinks of circles as special cases of ellipses or not.

Perhaps the way to go would be to support interfaces without requiring type checking. Basically you simply say "all I care about is that this object can be passed to that function".

That said a semiformal way of expressing this - probably by giving a name to an interface (which is just a set of function symbols that an object supports) - might be useful. This way wouldn't necessarily be checked by the program - it might be useful to have it be read by the programmers as part of the code/documentation.

  (typeclass 'scanner 'car 'cdr)
  ; programmer reads: a scanner is anything that somehow supports 'car and 'cdr

  (def foo (a)
    " A ridiculously complex library function which does
      a lot of useful things and which the library user
      probably doesn't want to read in full, because he or
      she is using the library so that he or she doesn't
      have to think about it.
      See also [[bar]] "
    (must-have a 'scanner)
    ; programmer reads:
    ; "Anything I define which supports 'car and
    ; 'cdr can work on this function"
    (ridiculously-complex-expression-involving a))

The kind of thing you're suggesting here does look powerful (and most importantly, optional!) If you combine it with sacado's suggestion for putting the methods in the tag, then you have a very powerful type system indeed.

I just have one contentious thing left to say: when you move away from is-a typing to has-a typing, does it really make sense to use the word 'type' at all? Aren't we really talking about what your functions can do, rather that what your objects are? For example, if you define car and cdr to work on strings, have you added strings to a new sequence type or have you expanded the power of your functions? I prefer to think that you've done the latter, and save the word 'type' for the basic is-a types that every language has to have.