The Artima Developer Community
Sponsored Link

Weblogs Forum
A Type System is a Set of Tests

73 replies on 5 pages. Most recent reply: Apr 26, 2006 7:08 AM by Achilleas Margaritis

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 73 replies on 5 pages [ « | 1 2 3 4 5 | » ]
Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

That Floor Wax Dessert Topping joke Posted: Apr 21, 2006 6:22 PM
Reply to this message Reply
Advertisement
/* then why it sn't [type inference] already added to every popular dynamic language? I mean, OCaml isn't exactly new, right?
*/

Probably because each language starts out with a set of constraints that might make good new features hard to add later.

For instance, proper tail calls are a wonderful feature for a language or VM to have. Research on proper tail calls goes back at least twenty years. However, adding tail call support to C compilers is incredibly hard ( http://home.in.tum.de/~baueran/thesis/ ). In fact, the C++ Standard goes so far as to encourage tail call support, provided that you can pretend that things work the old C way. That "provided" part means that very few C++ compilers have tail call support. Once it's in, it's easy to maintain, but it's hard to get in.

OCaml has proper tail call support. However, it requires you to mark recursive functions as such as a hint so that the compiler can determine if tail calls are an option. Imagine if Io (no key words) wanted to offer such a feature. The constraint that you can't add a key word (to keep Io "clean") really makes giving the compiler such a hint incredibly hard.

Which, btw, does go back to the original topic: that hooks into the type system (or other systems in the compiler, IMO) would make for a more robust language. And that applies to both dynamic and static languages.

Another 'ferinstance: Perl. Perl created a really wild object system (which I like, btw). There are several different "equally valid" ways to create a Perl class (which, btw, is one reason Perl 6 is so long in the making: http://www.sidhe.org/~dan/blog/archives/000316.html discusses some trouble with Parrot handling several object systems). Perl *did* define how it walks the inheritance tree, but it also lets the object modify the inheritance tree at runtime, and each parent class gets a fallback method that could be triggered when you don't expect it.

This means, quite simply, that while Perl promises to walk the tree a specific way, it's possible that you'll get different results each time through! It sure would be nice if the programmer had a hook into that so he could override that in the cases where it's needed.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: That Floor Wax Dessert Topping joke Posted: Apr 21, 2006 6:27 PM
Reply to this message Reply
Oops. I thought by going text-only I'd avoid the markup issue. But I ended up with an "i" in brackets, hence the missing "i" and the rest of the post in italics.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: That Floor Wax Dessert Topping joke Posted: Apr 22, 2006 3:05 AM
Reply to this message Reply
OCaml has proper tail call support.

Actually, AFAIK, OCaml doesn't optimize all tail calls. I don't remember the exact details, but, IIRC, the optimization of tail calls depends on the number of arguments the function takes.

However, it requires you to mark recursive functions as such as a hint so that the compiler can determine if tail calls are an option.

No, that is incorrect. The rec keyword of OCaml isn't there to support tail calls. The rec keyword is there to make the scope of bindings more explicit. If anything, it plays a role with type inference, but not with tail call optimization.

Although the distinction isn't always extremely important, a tail call refers to a call in a tail position, while tail recursion refers to making recursive calls at tail positions. The problem is that in a language with first-class functions, it is not in general possible to statically distinguish recursive tail calls from non-recursive tail calls, which means that an implementation of proper tail call elimination can not rely on such an analysis.

Imagine if Io (no key words) wanted to offer such a feature. The constraint that you can't add a key word (to keep Io "clean") really makes giving the compiler such a hint incredibly hard.

Optimization of tail calls requires identifying calls in tail positions. Such an analysis is a very simple syntactic analysis and basically requires no hints in the form of keywords.

damien morton

Posts: 15
Nickname: dmost
Registered: Jan, 2004

Re: A Type System is a Set of Tests Posted: Apr 22, 2006 8:40 AM
Reply to this message Reply
A type system isnt a set of tests, it is rather a computer readable record of a set of design decisions.

When you declare:

def foo(x,y): return x+y

You have some intent in your head which isnt properly recorded by the code alone. Having type annotations helps record that intent.

def foo(Numeric x, Numeric y): return x + y;

Ahhhhh - now I and the compiler know better what this code is supposed to do.

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: A Type System is a Set of Tests Posted: Apr 22, 2006 4:07 PM
Reply to this message Reply
> A type system isnt a set of tests, it is rather a computer
> readable record of a set of design decisions.
>
> When you declare:
>
> def foo(x,y): return x+y
>
> You have some intent in your head which isnt properly
> recorded by the code alone. Having type annotations helps
> record that intent.
>
> def foo(Numeric x, Numeric y): return x + y;
>
> Ahhhhh - now I and the compiler know better what this code
> is supposed to do.


I hear you. Now, let me play a little trick. I'm going to rewrite what you just wrote to make a point:

>>>
A set of tests isn't just a set of tests, it is rather a computer readable record of a set of design decisions.

When you write:

public void total() {
return items.inject(0, (sum,item) { sum + item.price });
}

You have some intent in your head which isn't properly
recorded by the code alone. Having tests helps
record that intent.

catalog.add(new Item(4));
catalog.add(new Item(2));
assertEqual(6, catalog.total());

Ahhhhh - now I and the compiler know better what this code
is supposed to do.

<<<
See the parallel?

Erik Engbrecht

Posts: 210
Nickname: eengbrec
Registered: Apr, 2006

Turning things around Posted: Apr 22, 2006 10:47 PM
Reply to this message Reply
Example 1, static typing:
<doesn't show intent> def foo(x,y): return x+y
<shows intent> def foo(Numeric x, Numeric y): return x + y;

Example 2, testing:
<doesn't show intent>
>public void total() {
>return items.inject(0, (sum,item) { sum + item.price });
>}
<adds intent>
>catalog.add(new Item(4));
>catalog.add(new Item(2));
>assertEqual(6, catalog.total());

Now, what's the difference?

With the "test":
1. You have the intent spread over two files
2. Your IDE can't check it as you type
3. You weren't forced to write it (good and bad)
4. It's more verbose
5. It can express a wider range of ideas
6. The ideas it expresses are more fuzzy

With the "type":
1. The intent is with the declaration
2. Your IDE can check it
3. You were forced to write it (good and bad)
4. It's more concise
5. It can only express a limited set of ideas
6. It's more precise in the ideas it expresses

Both are validation. Tests are dynamic validation, types are static validation.

Leo Lipelis

Posts: 111
Nickname: aeoo
Registered: Apr, 2006

Re: A Type System is a Set of Tests Posted: Apr 24, 2006 2:37 PM
Reply to this message Reply
> A type system isnt a set of tests, it is rather a computer
> readable record of a set of design decisions.
>
> When you declare:
>
> def foo(x,y): return x+y
>
> You have some intent in your head which isnt properly
> recorded by the code alone. Having type annotations helps
> record that intent.
>
> def foo(Numeric x, Numeric y): return x + y;
>
> Ahhhhh - now I and the compiler know better what this code
> is supposed to do.

You're assuming that every instance of nonspecificity represents hidden intent.

I disagree.

Leo Lipelis

Posts: 111
Nickname: aeoo
Registered: Apr, 2006

Re: Turning things around Posted: Apr 24, 2006 2:40 PM
Reply to this message Reply
Erik,

You make an interesting point. It would be even more interesting if the compiler/interpreter enforced coverage and demanded the tests, and maybe even refuse to run the program without them. Well, maybe that's going a little too far, but I think it conveys the point.

Max Lybbert

Posts: 314
Nickname: mlybbert
Registered: Apr, 2005

Re: That Floor Wax Dessert Topping joke Posted: Apr 24, 2006 5:16 PM
Reply to this message Reply
/* [Vesa] No, that is incorrect. The rec keyword of OCaml isn't there to support tail calls. The rec keyword is there to make the scope of bindings more explicit.
*/

Thank you. I've followed your advice and taken another look at OCaml, but apparently I made some assumptions about what was going on.

I also forgot that Stroustrup has proposed using the auto keyword as a statement to the compiler to use some form of type inference: "We suggest that the auto keyword would indicate that the type of a variable is to be deduced from its initializer expression" (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1894.pdf).

However, aside from this, I believe the biggest hurdle in adopting type inference engines is the fact that what might be easy in the compiler could be extremely difficult in the syntax.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: A Type System is a Set of Tests Posted: Apr 25, 2006 6:29 AM
Reply to this message Reply
> If a person can have all the benefits of dynamic typing,
> such as interactive programming, duck typing, easy dynamic
> behaviors (as opposed to something grotesque like Java
> reflection API), small program size, while using a type
> inferance system, then maybe it almost makes no sense to
> use dynamic typing. The problem is that traditionally the
> languages that have been popular examples of static typing
> a) did not use type inference and b) were and are horrible
> in day to day usage compared to modern dynamic languages.

Mainstream programming languages are usually born out of practical problems, and thus they reflect the solution domain rather than a set of abstract set of mathematical principles. Take C++, for example: when it was born, Stroustrup had a specific problem in mind, to make AT&T applications better; he most probably did not care (or did not know) about type inference, or type inference algorithms where not discovered back then. Then Java came along, that wanted to be a better C++. The same story here: Java was born because C++ did not cut it as an object-oriented language for some kinds of applications.

The benefits of dynamic typing (incremental development, duck typing, etc) can also be achieved with static typing systems that have a dynamic development component. For example, there could be a C++ dynamic environment that compiles code as it is being typed by the programmer, providing incremental development and using templates for duck typing.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: A Type System is a Set of Tests Posted: Apr 25, 2006 6:33 AM
Reply to this message Reply
> In my opinion static types buy a lot less than people
> think. In particular, many arguments regarding reducing
> bug counts and reliability I think are unsubstantiated
> anecdotes. In my experience programs written in good
> dynamic languages tend to be pretty solid. Likewise,
> people do circumvent static typing by using the root
> object class when they feel lazy. So I understand static
> typing, as a tool at best, but not as any kind of
> guarantee at all. It still takes some discipline and
> maybe even wisdom to use it to full effect. But if you
> have such discipline and wisdom then you can use a
> dynamically typed language to an even greater effect.

Maybe that reflects your own experiences only. My experiences differ: I have seen Java programs "crashing" with bad cast exceptions because different people put different type of objects in collections, whereas that never happened in C++ due to templates.

Michael Feathers

Posts: 448
Nickname: mfeathers
Registered: Jul, 2003

Re: A Type System is a Set of Tests Posted: Apr 25, 2006 9:36 AM
Reply to this message Reply
> Maybe that reflects your own experiences only. My
> experiences differ: I have seen Java programs "crashing"
> with bad cast exceptions because different people put
> different type of objects in collections, whereas that
> never happened in C++ due to templates.

It's funny you mention that. I visit a lot of teams and class cast exceptions are rare. Programs are far more liable to crash with null pointer exceptions.

If the true concern is not having programs crash, then language designers should have dealt with the null issue earlier. As it stands, I only know of the Nice language and some halfway features in C# 2.0 that attempt to tackle this.

In most dynamically typed languages it's very easy to avoid crashes on null dereferences and do something better than just catching at the top level of your program: you subclass null provide your own behavior. I suspect that the reason most designers of statically typed languages don't allow this is because they are scared of giving developers that much control. But, it is yet another case where preventing people from doing bad things prevents them from doing good things as well. I don't know that we could calculate the monetary loss of crashes due to null pointer exceptions, but I'm sure it's rather large. I can't believe the simplified null that we have in most languages is worth that cost.

Re templates in C++, there was a very long period during which there were no templates in C++. I don't remember much in the way of bad casting. Programmers often created specialized collections (which has its own downsides). I think that the big experiment with casting out of collections happened in Java.

Erik Engbrecht

Posts: 210
Nickname: eengbrec
Registered: Apr, 2006

Null pointer exceptions Posted: Apr 25, 2006 10:59 AM
Reply to this message Reply
> It's funny you mention that. I visit a lot of teams and class cast exceptions are rare. Programs are far more liable to crash with null pointer exceptions.

What percentage of variables should never be null?

What precentage of those could be declared with an explicit scope that governs their lifetime?

I'm thinking of something like stack allocated and non-pointer/reference member variables in C++, sans the object slicing problems of stack allocation. Kind of like a smart-pointer that can't be null.

Anyway, that's off topic. But I think "can it be null or not" is usually more useful information than the type. It's not uncommon to write code that can work on a number of different types. But usually you can be certain whether null is acceptable or not.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

The null issue was solved decades ago Posted: Apr 25, 2006 11:21 AM
Reply to this message Reply
If the true concern is not having programs crash, then language designers should have dealt with the null issue earlier. As it stands, I only know of the Nice language and some halfway features in C# 2.0 that attempt to tackle this.

They did and it happened long time before the languages you mention were created.

In SML, the equivalent of a non-final Java object reference (meaning: any variable, field, or element declared with a class or interface type) is a value whose type is of the form 'a option ref.

The ref type constructor introduces a mutable cell that one can dereference and assign to. The option type constructor introduces the possibility that there may be SOME value or NONE (like null in Java) at all.

The important thing is that unless you explicitly say so, values in ML are neither options nor refs. So, unless you really explicitly need the complexity of either both or one of mutability and nullability, you can avoid introducing it.

In Java, you can't really avoid the complexity. All object references may be null and, unless explicitly declared final, can be assigned to.

Isaac Gouy

Posts: 527
Nickname: igouy
Registered: Jul, 2003

Re: A Type System is a Set of Tests Posted: Apr 25, 2006 12:40 PM
Reply to this message Reply
Michael Feathers wrote
-snip-
> Programs are far more liable to crash with null pointer
> exceptions.
>
> If the true concern is not having programs crash, then
> language designers should have dealt with the null issue
> earlier. As it stands, I only know of the Nice language
> and some halfway features in C# 2.0 that attempt to tackle
> this.

Just to beat this flat, I'll join Vesa Karvonen in saying language designers did deal with the null issue earlier, using static type checking - see Haskell & Clean.

(Ada is so large that I'm never sure what it does or does not provide, but if non-null pointer types were not already available in some form then they clearly will be available in Ada 2006. iirc C#2.0 adds nullable value types, it does not add non-null reference types.)


> In most dynamically typed languages it's very easy to
> avoid crashes on null dereferences and do something better
> than just catching at the top level of your program: you
> subclass null provide your own behavior. I suspect that
> the reason most designers of statically typed languages
> don't allow this is because they are scared of giving
> developers that much control.

Another day, another conspiracy theory? :-)

Michael, would you say that most designers of dynamically type checked languages don't provide explicit type declarations because they are scared of giving developers that much control?

imo that would just be an attempt to divert a discussion of technical merits by demonizing people with a different viewpoint.

Flat View: This topic has 73 replies on 5 pages [ « | 1  2  3  4  5 | » ]
Topic: A Type System is a Set of Tests Previous Topic   Next Topic Topic: Thinking in C, Beta 3


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us