Arc Forumnew | comments | leaders | submitlogin
Opinion: We should use "has-a" interface semantics, not "is-a" object semantics
13 points by almkglor 5943 days ago | 41 comments
Currently, Arc is pretty firmly embedded in the "is-a" thinking. An object currently has one, and only one, type, and it always "is-a" that type.

On the other hand, statically typed languages have started to move from simple is-a inheritance towards has-a interfacing. For example, Haskell's types don't actually inherit from one another - instead, each type may belong to 0 or more type classes. Membership in a type class means that the type must provide the functions belonging to the type class - a type which belongs to a type class "has-a" that type class. An object is-a type, but that type has-a (possibly 0, possibly multiple) type class

I wonder if a dynamically-typed language would be able to usefully make use of a formal has-a semantics.

In my experiments with user-defined types - file-table, scanner, and bidir-table - I always had to redefine 'isa, or at least hack around it. This is because some polymorphic arc.arc stuff - notably 'each - don't really work well with duck typing. They expect a specific type, and will only work on that type. In order to make my user-defined types work well with the arc.arc builtins, I had to hack around 'isa.

So I think we should really be using "has-a" semantics. For example, we can define that an object that "has-a" 'table interface must be able to provide methods for 'apply (as in (ob 'foo)), 'sref (as in (= (ob 'foo) 42)), and 'keys (as in, hmm, (keys ob)). It's is-a shouldn't actually matter to the basic arc.arc builtins; as long as the object somehow manages to support these functions, then as far as arc.arc is concerned it has-a way of working with the new types.

This probably means that we have a type system that is nearer to has-a type classes/interfaces than is-a type. An object might be is-a string-scanner underneath, but as long as it has-a 'car and 'cdr method then map should work on it, each should work on it, applying it to a function should work on it. And of course 'each must dispatch based on whether the object has-a scanner or table interface.

This isn't a "just for completeness" onion. It's plenty useful to be able to use the built-in (ontable ...) on a file-table, for example. If I suspect that file-table has a bug, I might instead use 'table to check. Or if I suddenly worry that someone might be reading my stuff I might build crypt-file-table. Or if the boss insists I can build db-table. And I want to rebuild as little as possible between modifications.

That said, the current system (overloading 'isa, and more recently with scanners also 'acons and 'alist) works, and works well. It just doesn't feel like it works right; it's like the fact that it works is immaterial.

3 points
28 points

6 points by cchooper 5942 days ago | link

I know I'll take a lot of flak for this, but I'm going to disagree vehemently with this suggestion. Someone has to play devil's advocate, and I guess it's going to be me :)

One of the things I've liked about Arc so far is the tiny number of types: characters, strings, symbols, numbers, lists, hashes, functions and macros. Having a very small number of types means that every function can be written to do something useful on each type. For example, I just wrote a library for converting any Arc value into its JSON equivalent so I could send them to a web client. It was really easy, because I had so few types to deal with. No need for polymorphic whatnot and abstract do-daas. Just use a simple case statement and you're there.

Elaborate type systems can solve a lot of problems. For example, I had a problem with alists, because I wanted them to be converted into objects, but general lists needed to be converted to arrays. How do you tell the difference between an alist and a normal list? If you had some kind of type system that allowed you to declare that your list is an alist then that would solve it. This is how complex type systems get started, but it's all downhill from there. Once your language starts relying on its type system for its power, you begin taking huge risks.

The problem is that when complex type systems fail, they fail hard. Despite endless academic papers on the subject, and a plethora of practical programming languages, no one has yet developed a type system that is powerful enough to allow people to express everything they want in a reasonably complex program. That wouldn't be a problem if the type system got you 99% of the way there and you had to do a small workaround for the last 1%. Unfortunately, what usually happens is that the 1% left over breaks the whole program. Suddenly you can't use that really useful parsing library, because it's defined over an abstract type that your type can't quite be mapped into. Suddenly the polymorphism features of your language become useless because your type isn't quite polymorphic in the way the language designers anticipated (perhaps you want function polymorphism but the language supports object polymorphism, or vice versa). All type systems fail eventually, and if your language relies on its type system for its power, then you might as well be writing machine code for all the use it will be.

Let's take just two examples. OOP started with multiple inheritance, but then people decided this was too error prone, so people moved so single inheritance. But that wasn't expressive enough, so we got interface inheritance, then generics, then mixins, then "composition over inheritance". Despite all this, you still can't express the relationship between circles and ellipses in any OO language.

Example 2: Haskell was inspired by the very powerful Hindley-Milner type system, which has type variables, polymorphic types and abstract types, but this still wasn't good enough, so they added classes. The ML people still didn't think this was good enough, so they added functors. Some people still didn't think this was good enough, so they proposed higher-level functors. There are endless proposals to add generics to the language too, and then there's dependent typing and all that malarkey. No matter how powerful your type system is, it's never enough.

Arc doesn't get its power from having a complex type system. It gets it from being able to express computations on a small number of types in a very concise manner. This kind of power can fail too, but it doesn't fail hard because Arc has the tools to make any problem simple: functions, macros and reprogramming the programming language. Type systems can save you writing lots of similar functions for slightly different types, but so can macros because they can generate the code for you. Type systems can distinguish between different implementations of cdr and car for different types, but you can also do that by redefining cdr and car to cope with those types, or by passing your own versions of cdr and car along with the object (perhaps even stored in the object itself: see the appendix on object systems in ANSI Common Lisp).

Complex type systems give you power, but they are a seduction that we should resist. They allow you to solve problems by constructing interesting types, but the set of problems you can solve is always strictly limited by the type system (and just because you can write your own type system doesn't mean the problem goes away, unless you can get your system to work seamlessly with everyone else's system).

A powerful set of functions over a small number of types is a much better way of doing this. Types are the sockets that allow functions to be connected together. You can either work with a small number of types that allow you to connect all your functions to each other, or you can create all kinds of different types and then use polymorphism/inheritance/type variables/has-a relationships to try and patch up the fragmentation problem. If you really have lots of types that are similar enough for your functions to work across them, then you should probably use fewer types.

On the other hand, I could be talking nonsense. Let's assume that until we have evidence to the contrary :)


4 points by sacado 5942 days ago | link

Wow, I think you won the price of the longest post so far. And it is even a very clever one, actually. And I think your view and almkglor's are not so far from each other.

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)
Ok, you're right until now cchooper, predefined types are enough for these situations, and that's how we should do in such cases. Now imagine we want to deal with lists, generators and arrays defined through FFI. You have to distinguish between the latter two, but how can you do that ? Encapsulating them in a cons whose car is a discriminant between both types will not work here, as a cons isa 'list. That's why you need a way to define these new types, and that is what annotate is for.

  (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))))
Now, about the distinction between isa and hasa. The wonderfull thing about annotate is that it is very generic ! It does not provide you with a way to say your data is of a specific type, it lets you annotate your data with whatever data you want ! The fact that it works with isa is a side effect actually, annotate does not care about isa. You can annotate with a symbol for sure, but also a string, a number, a list, a macro, a closure, a continuation, whatever !

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)))))
And you've got an object system where the car function is embedded into the data when you don't apply it to lists. That's it, you used annotate as it is now defined to create an has-a behavior. Almkglor has got many other funny ideas with typing, and I think all of them can be implemented simply with annotate and encapsulating old definitions of core functions and axioms into usertype-aware ones.

Maybe Arc needs a few more facilities right there (for example, having to use rep on annotated data is, I think, the biggest mistake of that type system. Please, pg, correct this !), but I think we've got everything we need. Almkglor only proposes a few macros and discipline in librarys, but this can be done with the current language definition (and ignored by everybody but him :)


4 points by sacado 5942 days ago | link

Just tried that, it works :

  (= _car car _cdr cdr)

  (def hasa (obj typ)
    (if (no typ)
      (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
It's a bit ugly, probably it could get a little better (the display is ugly, IMHO) but those wanting it could start doing funny things.


4 points by cchooper 5942 days ago | link

> Wow, I think you won the price of the longest post so far.

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.

So I'll modify my position and say that you should avoid creating new types, but if you have to do it, duck typing is the way to go.


2 points by almkglor 5942 days ago | link

For completeness ^^

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


1 point by sacado 5942 days ago | link

You could read this about annotate et al. :

I particularily like that one : "I expect type names will ordinarily be symbols, but they don't have to be. Either argument can be of any type. I can't imagine why users would want to have type labels other than symbols, but I also can't see any reason to prevent it."


1 point by cchooper 5942 days ago | link

You know, the first thing I thought when I read that x years ago was "You could pass around a load of functions as the type to do polymorphism"! I wonder if everyone has the same thought.


2 points by almkglor 5942 days ago | link

The point mostly is that those problems probably stem from is-a semantics. It might be that has-a semantics might work better.

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))


3 points by cchooper 5942 days ago | link

OK, maybe I flipped out a bit when I heard the word 'type' mentioned. It brought up nightmares of using Java and C++ and so forth.

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.

It's the word 'type' I'm objecting to now, not the general idea. Perhaps we need to get out of the typing mindset in order to really break new ground.


3 points by almkglor 5942 days ago | link

The value of types is the name you associate with an object. Instead of giving a really long list of "functions that should work on the object" you say "an object of this type". So instead of saying "an object that has 'car and 'cdr" you just say "scanner".

Brevity, brrevity.


7 points by kens1 5940 days ago | link

I'm finding Arc's type system to be kind of random. I'm not sure has-a vs is-a is the solution, but here are my issues:

a) Lots of operations operate on "sequences" (tables, lists, and string). Lots of other operations operate only on lists, or only on string and tables. There doesn't seem to be any real pattern. There also doesn't seem to be any fundamental "sequence" abstraction that supports implementation of more complex operations. It's more like "if list, do this. If string, do that. If table, do that."

b) Lots of string operations treat a list of characters and a string interchangeably. Lots of operations don't. Again, it seems pretty random.

c) Non-fundamental types, such as queues ( don't interoperate at all. That is, a sequence operation such as map will do entirely the wrong thing to a queue.

I don't know what the solution is, but it seems like there are some type abstractions struggling to escape from arc.arc..


1 point by sacado 5940 days ago | link

I guess these issues will eventually be fixed. These are only bugs, not design issues.

As for is-a vs. has-a, I was wondering, isn't the biggest mistake considering that a piece of data only has one type ? That is, isa & type are broken ?

Considering values have a list of types (instead of a single type) would fix a few problems. For example, what is the type of nil ? Is it a symbol or a list ? Yes, it is both, but to do so, pg had to define the alist function ! (type nil) returns sym and cannot let you know nil is a list. What is '(1 2 3) ? Is it a cons or a list ? It is a list, but its type is only cons. type should return a list (it is already possible through annotate) and the definition of isa should be :

  (def isa (x typ)
    (mem typ (type x))
That way, we would have

  (type nil) -> '(list sym)
  (type '(1 2 3)) -> '(list cons)
  (type '(1 . 2)) -> '(cons)
And the system would remain very generic (even more than now). Thus, almkglor's scanners would work with each (provided the definitions of car and cdr were adapted) :

  (type s) -> '(cons scanner)
  (isa cons s) -> t
Other representations would be possible, including the ones we already discussed here. The name isa does not necessarily mean we have an is-a semantic (and not has-a). Once again, each item in type is an annotation and can mean many things that are left to the programmer (it can be a class, a class type, a bunch of functions, whatever).

But the "objects-have-one-type" model seems broken. At least for lists, which is quite annoying for a Lisp !


2 points by almkglor 5939 days ago | link

"objects-have-one-type" model helps with nex3's defm:

  (defm something ((t f scanner))
    (do-something-on-scanner f))
  (defm something ((t f cons))
    (do-something-on-real-cons-cell f))
In this case, if we pass an object that is-a scanner and is-a cons, which method gets called?

This is the main reason I'm advocating is-a and has-a separation. We can say that an object is-a 'cons cell and has-a scanner. If something requires that an object is-a real, element-pointer-and-next-pointer 'cons cell, as opposed to somethingthing that requires that an object has-a 'car and 'cdr, we can make the distinction.

So we can say that an object is-a 'cons cell - it's what it really is, what it's implemented with. However, a 'cons cell has-a scanner interface, and if it's proper it has-a list interface, etc.

Separating is-a and has-a could also be useful for optimization of basic parts.

For example, a basic non-optimized diff algorithm might operate on has-a 'scanner, and use 'car and 'cdr operations. However a string-scanner is really just a wrapper around a string and an index into the string, as well as the string's length. Each 'string-scanner object contains three slots: one for the string, one for the index, and one for the length. This applies to each 'cdr on a string-scanner.

Now suppose we have a version of the diff algo which specifically detects if an object is-a string-scanner. It destructures the string-scanner into the string, index, and end, and instead of carrying around a triple of (string, index, length) it only carries the index, leaving string and length into local variables. This reduces memory consumption to only one-third.

(Note that the diff algo I posted a while back actually keeps entire sections of the list, in order to properly scan through their differences; that is, it keeps several scanners)


5 points by sacado 5939 days ago | link

Hmm, I think there are 2 really different concepts here :

- type declaration of real-implementation (what you call "is-a"),

- type declaration in the sense of "capabilities" an object has (what you call has-a).

I think they should really be distinguished. The former is about optimized compilation, the latter about which functions can be applied to a given object.

But optimization is linked to variables (e.g. "in this block n always holds an integer, s always holds a string and l is always a cons) and does not need to be declared until you want to compile something.

On the opposite, capabilities are linked to values (e.g., "n, s and l are all scanners, they all have scanner capabilities, you can apply car and cdr to all of them. This is currently true, but could change if values referenced by n, s or l change). These are mandatory, and have to be known dynamically (this is not a declaration in the static meaning, they can even change later). When you apply car to a variable, you must know if its attached value can answer it (and eventually how).

  (= str (string-scanner "foo bar baz"))
  (type str)
  -> (scanner string)

  (def scan (s)
    (if (no s)
      (cons (foo (car s)) (cdr s))))
There, the values held by s are considered as a scanner and a string, that is, car and cdr can be applied to them. A dispatch algorithm is applied to them on the moment we need it. If, at any moment, an object held by s cannot be applied the method car or cdr, we have an error. Until we want more speed, that's enough.

Now suppose we want more. All we have to do is :

  (def scan (s)
    (istype string-scanner s
      (if (no s)
        (cons (foo (car s) (cdr s)))))
That way, for optimization purpose, we state that s only holds string-scanner objects. It does not even have to care with the annotations you added to the value (or values) held by s. If an object held by s is not really a string-scanner, well, anything could happen.

I might be wrong, but I think super-optimizing CL compilers work that way. You say them "optimize that function, and btw, this var always holds strings, don't even bother checking and dispatching the right function".


4 points by almkglor 5939 days ago | link

Quite accurate. The main thing is that I think people should use has-a for everyday programming, and only use is-a if absolutely necessary, e.g. optimization.

My second proposal, probably lost somewhere in the confusion, is that has-a information would be connected to an object's is-a type.


3 points by Jesin 5939 days ago | link

This could be part of a temporary solution:

  (def my-isa (obj typ)
    (let a type.obj
      (if atom.a
          (is a typ)
          (some [is _ typ] a)))


3 points by sacado 5939 days ago | link

Yes, but then it does not work with the core functions (notably each & friends), as they are relying on isa. Renaming your function isa does not work either (that would be too easy) : atom and some call isa themselves, so you get in an infinite loop. Btw, obj is a macro (at least in Anarki, I don't know if it's present in the official Arc2), so your code has a red flag on it (although it does seem to work).

I tried this, it does work :

  (redef isa (x typ)
    (isa-rec type.x typ))

  (def isa-rec (types typ)
      (no types) nil
      (is types typ) t
      (isnt type.types 'cons) nil
      (is (car types) typ) t
      (isa-rec (cdr types) typ)))

  (isa nil 'sym) -> t
  (isa (annotate '(sym list) nil) 'sym) -> t
  (isa (annotate '(sym list) nil) 'list) -> t
  (isa (annotate '(sym list) nil) 'cons) -> nil
And now the funny part :

  (redef car (x)
    (if (isa x 'int)
      (if (> rep.x 0)
      (old x)))

  (redef cdr (x)
    (if (isa x 'int)
      (if (> rep.x 0)
        (annotate type.x (- rep.x 1))
      (old x)))
Both car and cdr now work on objects of type 'int (and objects of type 'cons, as before). If an object is both an int and a cons, its int being is taken into consideration. Every operation requiring 'cons cells or calling car and cdr can now be overridden to use ints instead (an int being a list whose car is the symbol 'a and whose cdr is that num - 1).

  (car 1)
  -> a
  (cdr 1)
  -> 0
  (cddr 2)
  -> 0
  (car (annotate '(int cons)) 3)
  -> a
  (len (annotate '(int cons)) 3)
  -> 3
Very funny things to do from there, but watch your fingers.


2 points by sacado 5939 days ago | link

Hmm, Playing with this stuff, I ran into that :

  (each c (annotate '(int cons) 3) (prn c))
  -> Error: "Function call on inappropriate object #3(tagged (int cons . nil) 3) (0)"
The problem is that each calls acons and alist, but they are defined in terms of (is (type x) 'cons) instead of (isa x 'cons). Once you redefine them, it works fine.

pg, do you still accept suggestions about the core functions ? Shouldn't acons and alist be defined with isa instead of is ? That would let us redefine them more easily. Btw, what do you think of all these discussions about types ?


2 points by almkglor 5943 days ago | link

Hmm. Mockup of how it would be used.

  ; In arc.arc, or maybe something equivalent in
  ; ac.scm.
  (typeclass 'cons 'car 'cdr 'scar 'scdr 'apply)

  ; In our library, where we can't (or at least,
  ; "shouldn't") redefine the built-in Arc 'cons
  ; typeclass.
  ; A perfect subset of 'cons.  
  (typeclass 'scanner 'car 'cdr)

  ; Dumps out a character scanner or list
  ; to a port
  (def dump-out (port l)
    ; Note: we expect has-a to return t
    ; even if l is a 'cons - i.e. the type
    ; system should be smart enough to
    ; realize that 'cons provides all the
    ; interfaces of 'scanner.  Prolly something
    ; like:
    ; (= all-functions (mappend [instance-functions-of _] (type-classes-of ob)))
    ; (all
    ;   [some _ all-functions]
    ;   (instance-functions-of requested-type-class))
    ; above can be optimized by using tables - put all
    ; of the requested type class's instance functions
    ; in the table, then remove everything that exists in
    ; all-functions; if we finish all-functions while
    ; table entries exist, we know the object doesn't
    ; have that type class
    (unless (has-a l 'scanner)
      (err "Not a scanner"))
    (map [write _ port] l))


5 points by nex3 5943 days ago | link

Now, the thing I like about implicit has-a relationships is that they guarantee less code than making it explicit, in that they're the same amount of code sans type declarations and checks. For example, the above would be simply

  (def dump-out (port l)
    (map [wrie _ port] l))
No typeclass declarations and no type checking. This also has the advantage of being identical to the code you'd write if you were completely unaware of a scanner abstraction.

Also, on a more philosophical level, I feel like type checking is just out of place in a dynamically-typed language like Arc.


4 points by almkglor 5943 days ago | link

Not really my point. The point is that the trivial check:

  (unless (has-a a 'scanner)
    (err "type error"))
May be closed into a macro:

  (mac type-declaration (a typ)
    `(unless (has-a ,a ,typ)
       (err "type error")))
...which ends up being the optimizing compiler's clue:

  (def dump-out (port l)
    ; a completely optional declaration
    ; for:
    ; (1) an non-optimizing interpreter, so that
    ; you have some chance of checking errors, and
    ; (2) the optimizing compiler, so that it can
    ; do some shortcuts.
    (type-declaration l 'scanner)
    (map [write _ port] l))

You can then trivially redefine type-declaration as:

  (= type-declaration
     (annotate 'mac nilfn))
To disable type-checking.

Oh and yeah: type checking is plenty in-place, if you're building a library. If the library's interface functions simply passed the object to library-internal code without checking, the error will pop up as coming from some code deep in your library, where your user might be less inclined to trace (because it might be your bug, not theirs). At least if you do the check on the interface functions themselves you have proof that the bug is in the user's code.

I agree it's out-of-place in most apps of course.


4 points by nex3 5943 days ago | link

But that macro, and the whole plumbing behind declaring and checking type classes, just don't have to exist if you make it implicit. It's a lot of added complexity for no gain in power. All you gain is a little type safety - and if you need type safety, Arc (and Lisp in general) is not your language.

I wonder how much type-checking major Lisp libraries really do have. In the dynamically-typed-language libraries I've looked at, there are more or less no type checks. In the Ruby community, they're specifically discouraged, because they limit the power of duck typing.


3 points by almkglor 5943 days ago | link

Yes, but who says it has to be used? In the majority of code, there won't be type checking, but we do want to say something like this:

  This function accepts a list of ordinal types
which we can simply put in-code as:

  (type-declaration a 'Scanner)
  (type-declaration (car a) 'Ordinal)
The point is that the function doesn't specifically accept a list of strings or numbers - it accepts a traversable sequence of anything that can be ordered. The type-declaration thing is just a notation to express that to someone else.


2 points by Jesin 5942 days ago | link

I think I am going to say here that from the little I have seen of Factor ( I really like its object system. Method calls look like normal words, but they work for anything that implements a method for that word. I'm going to use sequences as an example. Arrays, quotations (code blocks) and integers all implement the sequence protocol, so for example:

  { 2 7 1 } 3 add { 6 5 } append
makes the array { 2 7 1 3 6 5 }

  [ foo bar ] \ baz add [ foobaz barbaz ] append
makes the quotation [ foo bar baz foobaz barbaz ]

  4 7 add { "bar" "baz" } append 3 append
makes the array { 0 1 2 3 7 "bar" "baz" 0 1 2 }.

I think any object system we put in the language should include the ability to create types that define their own versions of functions like join, and the ability to inherit from other types.

This seems to fit well with the following design philosophy:

Can I? Yes.

Do I have to? No.

That is, it allows you to think about type definitions and OOP, but if you don't want to, you can still use types that you or other people have defined as if they were built in, without having to think about the OOP.


2 points by nex3 5943 days ago | link

I totally agree. One of the things I like most about Ruby and its type system is that it puts so much emphasis on has-a relationships. This is pretty much what I'm going for with stuff like redef, defm, and my formulation of settable-fn... even though they actually use is-a to check, the idea is that only certain basic functions - analogous to methods like #each in Ruby, or the instance functions of Haskell type classes[1] - need to use is-a to check, and all other functions assume that the basic functions work.

[1] I'm not that familiar with Haskell terminology, so this might be wrong.


3 points by almkglor 5943 days ago | link

[1] This is about correct; Haskell dispatches off the is-a ness of the type. However, code you write will generally ask for the has-a relationship:

  {- merge used for mergesort -}
  merge :: Ord a => [a] -> [a] -> [a]
  {- The "Ord a" above asserts that the type "a"
     should be an "Ord"inal, i.e. it should support
     < <= > >= == methods
  merge [] [] = []
  merge a []  = a
  merge [] b  = b
  merge a:as b:bs
        | a < b     = a:(merge as b:bs)
        | Otherwise = b:(merge a:as bs)
  {- Of course, I haven't programmed Haskell in a while,
     so the above code might be wrong. -}
If we had has-a relationships, we might say something like this in Arc:

  (def merge (a b)
    (unless (and (has-a (car a) 'Ord)
                 (has-a (car b) 'Ord)
                 (is (type a) (type b)) )
      (err "Type error, needs Ord"))
      (no a)
      (no b)
      ; now we're assured < works
      (< (car a) (car b))
        (cons (car a) (merge (cdr a) b))
        (cons (car b) (merge a (cdr b))) ))
Hmm. LOL. I can just imagine a macro to do that type checking for you:

  (type-check (list a b)
     (Ord a) ((a . as) (a . as)))
It's beginning to look lot like Haskell ^^. Heck. arc.arc is congruous to Haskell.Prelude


4 points by nex3 5943 days ago | link

Yeah, I've seen several ways to express has-a relationships. Statically typed languages like Haskell tend to express them as is-a relationships (e.g. Int is-a Ord), since that meshes well with type safety. Languages that embrace duck typing, like Ruby, tend to make has-a relationships implicit; just use the method (or in Arc's case, function) and assume that the receiver will react properly. This meshes well with the late-binding, screw-static-verification philosophies of these languages, which Arc generally shares, and the message-passing object model, which Arc does not.

This is where I assume Arc will end up building its type system, if it ever does embrace a single type philosophy[1]. Even if it doesn't have a message-passing model, its dynamism makes the implicit has-a model a good fit.

The only language I've seen that embraces explicit checks for has-a relationships, as opposed to expressing them as is-a or making them implicit, is Javascript. This is mostly because you're dealing with objects that have an inherently variable and ill-defined interface that you don't know a lot about at compile-time. I think most JS developers view it as an annoying necessity, though, so I'm inclined to believe it's the least pleasant way of dealing with has-a (despite being the most explicit).

[1] Speaking of which, I really think it should. This is sort of implicit in taking part in all these discussions about typing, I suppose, but I wanted to mention it anyway. Any sufficiently powerful, has-a-based type system won't be a constraint on the language, but will rather allow powerful abstractions like Ruby's #each and almkglor's scanner.


2 points by Jesin 5939 days ago | link

I agree with you, although your choice of terminology is confused. You're not arguing for has-a. Has-a means "contains as a part", not necessarily part of the interface. Yes, a car (the kind you drive) has-a steering wheel, but it also has-a engine.

You seem to mean a specific kind of is-a called polymorphism. Looking at OOP, it looks like the only truly useful capability of OOP that Arc doesn't have is polymorphism, which fits well with duck typing. It basically means, "I don't care what this is or how it works, as long as it can foobaz."


1 point by almkglor 5939 days ago | link

Actually, I am arguing for a "contains as a part" semantics. arc.arc does have polymorphism - there are functions that work on sequences like lists, strings, and tables. The problem, however, is that some of them don't work on user-defined types without munging with 'isa.

What I'm proposing is abstracting some very "basic operations" such as 'car and 'cdr, put them in some "types" (really closer to type classes/abstract base class), and then have the built-in types "contain as a part" the "basic operation type". Then the arc.arc polymorphic functions will work based on the "basic operation type" instead of the actual is-a type, and user-defined types don't have to munge 'isa.


1 point by absz 5939 days ago | link

But if you think about it as an abstract base class/mixin/interface, then the standard terminology is "is-a". For instance, in Ruby:

  module MyMixin # Like an interface
  class MyClass
    includes MyMixin # Like "implements MyMixin"
  foo =
  if foo.is_a? MyMixin
    puts "is-a"
    puts "has-a"
  # Output: "is-a"
I'd rather see the "basic types" not as a collection of basic components, but as a collection of basic interfaces one can implement, or basic type classes one can be a member of, or what-have-you; what I'd really rather do is duck most of it, like Ruby does. If I can define car and cdr for my type, map should work seamlessly.

Regardless, it sounds like a lot of the voices here are in agreement over some common set of the features this plan proposes, which is a good thing. Perhaps we should set the naming quibbles aside for now and try to flesh that out. Or perhaps we should settle on a name for what we are about to flesh out. Either way, it looks like something good could well emerge from this thread.


2 points by almkglor 5938 days ago | link

I vote we settle on a name first, because we need it to refer to stuff when we talk about it ^^


2 points by treef 5943 days ago | link

classes/types? I thought arc is a language where every thing can be done in a few lines ... i cant see extra typing systems save all that much lines but just increase the complexity of the language.


4 points by nex3 5943 days ago | link

There will never be a language where everything can be done in a few lines. There are just some concepts that take more than a few lines to express even in the most concise languages (see APL and descendants).

Also, as I mentioned elsewhere (, a properly-designed type system can do amazing things for increasing the conciseness of a language. For example, take Ruby's Enumerable mixin. This relies on an implicit has-a relationship (that the mixed-in class will define an #each method) to automatically make practically every list operation you could ever want - map, fold, zip - work on any type that it would make sense for.

In short, a well-designed type system means that objects that can act in the same way - like lists and arrays, or strings and input ports - can be manipulated with the same code. This ends up significantly decreasing the code size overall, since each function that operates on multiple types only has to be written once, rather than once for each type it uses.


2 points by absz 5942 days ago | link

To be pedantic, it was proven that any program can be expressed in one line of APL (two if you need I/O).

In any case, I agree wholeheartedly: classes, if used properly, are an incredibly good way to streamline code. (Don't use them for everything, though. Then you get Java.) Ruby's mixins are actually very, very convenient, and seem to me to mesh well with Arc's approach: anything that can be cared and cdred can be mapped, too, and Arc doesn't care. But I feel like referring to this style as has-a is slightly weird, and it threw me off for quite a while. An object doesn't have-an Enumerable, it is-an Enumerable. On the other hand, an object does have-an #each method, so it does make some sort of sense.

Another advantage of combining mixins/has-a and Arc is that we get implicit mixins. In Ruby, you need to define #each and you need to include Enumerable to get all the Enumerable methods. But in Arc, since there are only functions, defining each would allow you to pass your object to all Enumerable functions (or their equivalent) without having to (include-mixin 'Enumerable 'MyType).


3 points by almkglor 5942 days ago | link

My main objection is the current state of arc.arc : Every iteration construct works with lists or strings, but it won't work well with something that has 'car and 'cdr (they check by using 'acons and 'alist, which use (is (type foo) 'cons) - meaning I had to hack into 'acons and 'alist. For that matter I had to hack into 'isa too)

Generally is-a means "object is this and only this", meaning single inheritance, which was really my meaning. But a scanner isn't a cons (it's a subset of cons; it will fail on scar and scdr). It does has-a 'car and has-a 'cdr.


2 points by Jesin 5933 days ago | link

I think the reason you keep saying has-a is that you're using conses as an example. A cons does has-a car and has-a cdr, but this is too restrictive. For example, say you wanted to make a type that acts like a list, that is, it supports map, each, reduce, all, rev, some, len, nthcdr, and so on.

  arc> (= a (my-listtype 'foo nil t 'bar))
  (foo nil t bar)
  arc> (car a)  ; has-a car
  arc> (cdr a)  ; has-a cdr
  (nil t bar)
  arc> (map no a)  ; has-a map (?!)
  (nil t nil nil)
  arc> (rev a)  ; has-a rev (?!)
  (bar t nil foo)
  arc> (some no a)  ; has-a some (?!)
  arc> (all no a)  ; has-a all (?!)
See what I mean? (Note: I fully agree that it would be really cool if the above actually worked, I'm just arguing that the name has-a makes no sense here.)


1 point by almkglor 5933 days ago | link

has-a scanner interface just means that: it has-a car and has-a cdr. 'map et al. now require an object which has-a scanner interface, and will simply use basic 'car and 'cdr operations to work. This supports genericity: just write 'map et al once, then any new type you create just needs to give 'car and 'cdr, and say it has-a scanner interface, and the existing map will work.

Now suppose we have another type, which has-a 'collide function, which handles the events where it is collided with in the game space. A ship has-a collide function, and the basic collission detection code is something like this:

    (while t
      ((afn (game-elements)
         (iflet (first . rest) game-elements
           (each e rest
             (when (overlapping first e)
               (collide first) (collide e))))
The above now works on ships. Now suppose we add a new type of game element: a missile. We simply define its 'collide function, and declare it as having that function; now it magically works without changing the collision-detecting code.


1 point by nlavine 5940 days ago | link

Agreed. This is exactly the problem that should be fixed. Your way would do it, although there are also some others.

Ironically, one great way is just to do no safety checks at all - the opposite of typing. I agree that we need something else, though.


1 point by absz 5942 days ago | link

Right. I concur--it's just the name that I felt was slightly odd. The approach is a good one.


1 point by ndanger 5943 days ago | link

It sounds like Python's abstract base classes ( & mix-ins (which is, INMHO a good idea for Python, I haven't used Arc enough to judge).


1 point by almkglor 5943 days ago | link

"Abstract Base Class" also happens to be the term preferred in C++ for Haskell's "type class" and Java's "interface". So it probably is-a python abstract base class ^^.

That said the problem with using a "base" class with an inheritance model is that it's deucedly difficult to think in terms of multiple inheritance (multiple inheritance is so hard most languages don't use it). Mix-ins help ameliorate this by being a has-a relationship.