Scheme is weak typed

[sans-hubris]

GnuVince asked me a while back about the typing mechanism of Scheme. I don't think I answered the question correctly. Yes, Scheme is weak typed.

Oh, and ML's type-inferencing and parametric polymorphism is pretty cool, I must admit. Much cooler than C++ and templates.

[GnuVince]

;)

It seems that functionnal languages have some of the most interesting features (O'Caml -> type inference, Scheme -> elegent, Brainfuck -> can use small keyboard)

[PrBacterio]

Actually thats not true. The phrase 'weakly typed' is usually used to refer to languages such as C, in which the typing system can be circumvented and/or the correctness of typing is not enforced at all times.

Scheme and Lisp, on the other hand, are what one ordinarily calls 'dynamically typed', that means, all typing information is observed at run-time; there is no compile-time type checking.

But they are still strongly typed: It is impossible for an object of, say, type 'a, to be used as an object of type 'b: This will always result in a typing error, though only at run-time (not at compile-time).

Consider, though, this simple, example C program:
struct _foo { int bar, baz; float frobozz; };
struct _bar { int bar, baz; char frobozz[8]; };

void foo_as_bar(struct _bar *bar)
{
struct _foo *foo = (struct _foo *)bar;
foo->bar = 1;
foo->baz = 2;
}

int main()
{
struct _bar bar;
foo_as_bar(&bar);
return 0;
}

This demonstrates that C is weakly typed: There is no type-checking done here in function foo_as_bar: The typeing error - that in function foo_as_bar the object is used as an object of type struct _foo, even though it is given, in function main, an object of type struct _bar - is never caught and simply results in undefined behaviour.

In Lisp and Scheme, errors like this would be caught - though only at run-time. These languages simply dont impose any kind of compile-time type-checking (though many good compilers do some type inferencing for optimization purposes) because there is no compile-time typing system that is flexible enough to allow for every possible, well-typed program to pass its type-checker.

[sans-hubris]

I'm not going to be pedantic about this, PrBacterio.

Your descriptions still leave an itch in my head that I can't quite scratch. Something seems like it's missing in this discussion of type systems and type environments, but I can't put my finger on it.

C is statically strongly typed, but dynamically weakly typed. That's what your code sample demonstrates to me, anyway. With C++, certain features of static weak typing are incorporated, however.

As far as Scheme goes (this may not be true of LISP, though, and I'm not sure about LISP, really), it is dynamically strongly typed in that list operations can't be performed on symbols (i.e. "(car 'a)" doesn't make any sense and you would get an error.) However, such operations wouldn't make any sense in the first place, unless you wrote in some support for operator overloading in Scheme.

I'll take your word for it on this stuff though because the programming languages class that I took didn't have a lot of time to study how the various typing systems work, much less implement one. I'm not even sure I would have been thrilled about implementing one either. Implementing static scoping was difficult enough.

[PrBacterio]

Originally posted by sans-hubris
As far as Scheme goes (this may not be true of LISP, though, and I'm not sure about LISP, really), it is dynamically strongly typed in that list operations can't be performed on symbols (i.e. "(car 'a)" doesn't make any sense and you would get an error.) However, such operations wouldn't make any sense in the first place, unless you wrote in some support for operator overloading in Scheme.

Of course the CAR operation does not make any sense except if its argument is a CONS; that is why you need a dynamic (i.e. runtime) type-checker to check whether the argument is of the correct type before applying the operation to it.

Now, on the other hand, take this small C program, for example:
struct _bar { char qux[8]; };

void mistake(double *foo)
{
struct _bar *bar = (struct _bar *)foo;
bar->qux[7] = '\b';
}
Now, the operation "bar->qux[7]" does not make any sense in this context, either, because *bar does not even have a member of the name "qux" - it is not even a struct, but a double. But the compiler simply ignores this in this case and produces the same code it would were bar really of type "struct _bar *". The result is undefined, because what happens is dependant on what representation the compiler uses internally to represent those struct's on the machine level.

Now, a Scheme compiler has some sort of representation for its data on the machine-level too. So it would be possible, in the same vein, to blindly apply the CAR operation to, say, a symbol - it simply wouldn't make any sense and the result, like in this C program, would be entirely dependant on the internal representation used for those datatypes. For example, most Scheme compilers represent a CONS cell as a pointer to a memory location containing two Scheme values; and a Symbol as an odd Integer which, when the least-significant bit is set to zero, becomes a pointer into some sort of symbol table. Thus, applying the CAR function to a symbol would, if there was no run-time type-checking, return whatever the symbol table contains at that specific adress, most likely a long integer consisting of the first 4 or 8 characters of the symbol. But Scheme compilers don't do this and neither do they provide a mechanism for doing this. C, on the other hand, does provide such a facility - but only if the programmer explicitly states that he wants to bypass C's (static) type-checking mechanism. But that still makes C a weakly-typed language.

Type-checking is the operation of checking, before execution of each operation (whether at compile-time or run-time), whether the consistuent arguments are valid for the given operation. And a lack of type-checking will result in undefined behaviour if the case occurs that arguments of the wrong type are given to a specific operation. So, this has got nothing to do with overloading, as overloading is the selection of the appropriate operation depending on the type of its arguments.

Note that I this is not to say anything against C; I like C, its one of my favourite languages. Its simply that the definition of the words weakly-typed and strongly-typed are pretty clear-cut, and C is weakly-typed. Java - which I don't like - on the other hand is, by a mixture of dynamic and static type-checking, strongly-typed, for example.