Static vs dynamic typing: do what thou wilt

24Dec06

There has been a raging debate (just watch Reddit!) on static vs dynamic typing and programming language choice these days. Most participants seem honest enough to point out the advantages and disadvantages of each typing scheme — dynamic typing requires less grunt “typing” work but is significantly less “safe” than static typing — but don’t account for the flexibility of typing usage available to each language.

While from a strict definitional viewpoint static and dynamic typing are quite disjoint — type checking is either done at compile-time or left for runtime — there are quite a few intermediate schemes. Some languages (Visual Basic, IIRC) allow for Variant data types, for example; Haskell’s own take at this seems to be Data.Dynamic, but I don’t really know for sure.

There is, moreover, even in a language disallowing variant data types, a spectrum of typing strategies that runs from no-pasaran typeful programming to just exploiting cartesian products and sums from machine types. Say you want to represent pixels in an infinite-sized 2D display; let us explore some ways of specifying that.

  1. Military typing:

    Horizontal coordinates and vertical coordinates are really quite different types of information and should not ever be used in one single calculation. Therefore, we first have to define these coordinate types.

    data XPos = XP Int
    data YPos = YP Int

    Now we can define a pixel as the cartesian product of these types:

    data Pixel = Pixel XPos YPos

    Writing functions for this rather indirect type will require somewhat messy pattern matching:

    up (Pixel (XP x) (YP y)) = Pixel (XP x) (YP y+1)
    down (Pixel (XP x) (YP y)) = Pixel (XP x) (YP y-1)
    addpos (Pixel (XP x) (YP y)) (Pixel (XP x') (YP y')) = Pixel (XP (x+x')) (YP (y+y'))

    etc. If you wanted to do something strange like adding x and y coordinates, you’d have to go out of your way to define

    wacky (XP x) (YP y) = (XP x+y)

    You can’t even overload (+), since its type is

    (+) :: (Num a) => a -> a -> a

    and therefore we can’t add values of different data types even if we attempt to declare XP and YP as instances of Num. This is both a gift and a curse. What strong typing brings in to the table is that you can’t mess with the intuitive semantics of (+) — you can’t beat the proverbial wisdom to the effect that you can’t add apples and oranges. On the other hand, it’d sure be nice to have a general “lift” combinator that took functions from Ints and turned them on functions on XP or YP, etc — which you can’t, because such a function wouldn’t be typeable short of defining a WrappedInt class and doing away with the whole benefit of military typing. Instead, you have to live with

    liftX f (XP n) = XP (f n)
    liftX2 f (XP n) (XP n') = XP (f n n')
    liftX3 f (XP n) (XP n') (XP n'') = XP (f n n' n'')
    liftY f (YP n) = YP (f n)
    liftY2 f (YP n) (YP n') = YP (f n n')
    liftY3 f (YP n) (YP n') (YP n'') = YP (f n n' n'')
    addpos' (Pixel x y) (Pixel x' y') = Pixel (liftX2 (+) x x') (liftY2 (+) y y')

    liftXY f (Pixel (XP x) (YP y)) = Pixel (liftX f x) (liftY f y)
    liftXY2 f (Pixel (XP x) (YP y)) (Pixel (XP x') (YP y')) =
    Pixel (liftX f x x') (liftY f y y')
    -- ... not to mention the combinatorially explosive number
    -- of ways functions can be lifted to two coordinates
    -- (only to X, only to Y, one function to X another to Y...) ...
    addpos'' = liftXY2 (+)

    which is more general, but also requires more documentation.

  2. Binder typing:

    Military typing requires a Big Design Up Front. It also requires an army of programmers writing functions on coordinates and pixels. It helps enforce security, but is a major headache as well; if you’re not going to war, you might want to go with something weaker. A first “weakening” of the pixel specification is

    data Pixel = Pixel Int Int

    Pattern-matching for this type becomes cleaner:

    up (Pixel x y) = Pixel x y+1
    down (Pixel x y) = Pixel x y-1
    addpos (Pixel x y) (Pixel x' y') = Pixel (x+x') (y+y')

    The endless cascade of “lift” functions becomes quieter as well:

    liftXY f (Pixel x y) = Pixel (f x) (f y)
    liftXY2 f (Pixel x y) (Pixel x' y') = Pixel (f x x') (f y y')
    addpos' = liftXY2 (+)

    What is lost here is that the compiler no longer knows that X-coordinates and Y-coordinates are different things. New, wide avenues for human error are opened, but we may often consider that the price tag of military typing is not worth the benefits — we want to trust our programmers and end-users at least a little bit.

  3. Binder typing with tabs:

    An interesting syntactic variation of binder typing is obtained through the use of a record. A record type is identical in functionality to the cartesian product type defined above (you can even use the same functions, without any rewriting), except in that it creates “destructor” functions automatically by act of declaration:

    data Pixel = Pixel { hor :: Int, ver :: Int }

    This allows us to rewrite the functions above (which, again, still work with this record type) in a different, possibly less messy fashion:

    up p = Pixel (hor p) ((ver p)+1)
    addpos p p' = Pixel ((hor p) + (hor p')) ((ver p) + (ver p'))

    What has happened in effect is that the data declaration creates new functions hor :: Pixel -> Int and ver :: Pixel -> Int which can be used to break down the product type. In some cases, this makes the semantics of functions more transparent.

    liftXY f p = Pixel ((f . hor) p) ((f . ver) p)
    liftXY2 f p p' = Pixel ((f. hor) p p') ((f . ver) p p')

    If we define a constructor function we might be able to bypass pattern-matching altogether:

    point x y = Pixel x y
    liftXY f = liftM2 point (f . hor) (f . ver)

    All this, of course, is unnecessary if one’s willing to muck about with pattern-matching, and is only mentioned for the sake of ooh ahh.

  4. Plain lattice typing:

    In this modality, we do away with the data declarations, the special types and just use Haskell’s built-in tuple data type — like one would in pretty much any other programming language. Function definitions are soothingly familiar for the uninitiated:

    up (x,y) = (x, y+1)
    addpos (x,y) (x', y') = (x+x', y+y')

    Lifts are easy to define as well, and will apply not only to our pixels, but to any pair of numbers — say, height and weight of a person.

    liftXY f (x,y) = (f x, f y)

    An alternate, wizardly version of this, suggested on the irc channel is

    liftXY = join (***)

    Given that we haven’t declared any typing, this is “almost” dynamic typing! That is, Haskell is still “static” in the sense that any machine type clashes (for example, trying to add a string to an integer) will prevent compilation, but we’re no longer doing any type work.

    Summing up, static vs dynamic typing really just means compile-time vs runtime error checking. You need not impose any needless bureaucracy upon programming practice because of it.

    Most of the time, stronger typing than the last example will be employed. That can be annoying, at times. I used to do graphics with a homespun library that produced pixel matrices (actually, nested lists of lists) that would later be exported into a PPM image file. When I began using OpenGL, none of my functions would work, because Haskell’s OpenGL lib uses binder typing (pixels have types like Vertex4 GLFloat GLFloat GLFloat GLFloat); similar complaints have been on the rise inside the Haskell community itself; some people find they rewrite function logic because of incompatible typing models when moving from one project to the next, and building a coherent type model does require some Big Design Up Front.

    Part of this is an artifact of data constructors and functions being different entities; often, adding constructor and destructor functions aids the fluidity of app logic between typing models, as we have seen. In any case, we’ve seen from the examples above that it’s often simpler to do quick hacks that are bound only to machine types rather than Big Design Up Front.

    Bottom-up programming in Haskell need not be a matter of algebraic clarividence, particularly if you’re willing to give up some safety.



6 Responses to “Static vs dynamic typing: do what thou wilt”

  1. 1 David

    You don’t want to override (+) completely, but in this case it would be perfectly reasonable to make YP an instance of the Num typeclass like so:

    data YPos = YP Int deriving Eq

    // …

    instance Num YPos where
    (+) (YP x) (YP y) = YP (x+y)
    fromInteger z = YP (fromInteger z)

    up (Pixel x y) = Pixel x (y+1)

  2. 2 Daniel

    This is a pretty minor nitpick, but I don’t think this does what you want:
    liftXY2 f p pā€™ = Pixel ((f. hor) p pā€™) ((f . ver) p pā€™)

    If we have f :: Int -> Int -> Int, then I think (f . hor) :: Pixel -> Int -> Int. Maybe this:
    liftXY2 f p p’ = Pixel (f (hor p) (hor p’)) (f (ver p) (ver p’)))

    ~d

  3. Ah, yes. I didn’t test any code.

    I really should add a “You get my point” disclaimer.

  4. you should make pixel+1 vertex to remove all kernal sleeps

  5. i never knew so many kinds of typing existed

  6. sorry, what is this all about?


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: