Understanding Clojure Transducers Through Types | Hacker News Reader

Understanding Clojure Transducers Through Types

conscientiousprogrammer.com

73 pointsjkkramer23 comments

There are some interesting comments at the bottom from Rich Hickey.

    trans :: (b -> a) -> (c -> a -> c) -> c -> b -> c

in Haskell is just

    trans f reduce c = reduce c . f

isn't it? What am I missing here?

He ends up calling that `mapping` later

    mapping :: (a -> b) -> Transducer b a
    mapping f xf r a = xf r (f a)

which, modulo a little renaming, eta-expansion, and point elimination is the same as your `trans`

your trans is just the "mapping" case. in general other functions can be applied to (c -> a -> c) -> c -> b -> c which will have more complex implementations than just composition.

Seems like parametricity ensures that

    Transducer a b

is isomorphic to

    b -> [a]

Am I missing something?

Nope—https://news.ycombinator.com/item?id=8160327

> ...a level of abstraction that I think has not been expressed much in the world of dynamically typed languages, although the techniques are two decades old in the Haskell community in a statically typed setting

Calling Clojure "dynamically typed" in this context (or any context), is confusing, as it is more of a mashup of a few ideas from functional and OO languages than a typical dynamically typed language. For example, Clojure does not have dynamic dispatch (except for multimethods, which are a limited form of dynamic dispatch) other than that offered by OO polymorphism (interfaces/protocols). In other words, it lacks the most important mechanism that lends dynamically typed languages like JavaScript and Ruby their power.

It is a language that, like Java/C#/Go, is based on interfaces, which are then mixed with some functional concepts. Unlike the aforementioned OO languages, Clojure usually uses only a handful of such abstractions (or interfaces; or protocols). So, while the translation to Haskell requires such concepts as type classes and higher-rank types, this has nothing to do with dynamic typing, and a lot to do with plain old OO polymorphism.

Clojure is dynamically typed in the sense that programs are not type-checked at compile time, values are tagged with types, and type errors are runtime errors. On other words, it is dynamic, in contrast to static type systems. This says nothing about strong vs weak typing, nor expressiveness of the type system, nor type-dependent semantics like polymorphism.

Personally I find it less confusing that dynamic typing is a small and comparatively well-defined concept, than mixing it in with aspects of polymorphism and dynamic dispatch. Dynamic dispatch doesn't seem to me to have much to do with dynamic typing; it's a fundamental tool of expression in C++ and Java, and those are both statically-typed languages.

I'm curious why you think multimethods are more limited than dynamic dispatch. It seems to me that their expressiveness is a strict superset of dynamic dispatch. Am I missing something?

> Clojure is dynamically typed in the sense that programs are not type-checked at compile time, values are tagged with types, and type errors are runtime errors.

Well, yes, but that has little to do with the way Clojure abstractions work; namely, they're not based on dynamic dispatch, but on OO-style polymorphism.

But BTW, your definition is not entirely complete, and the distinction between statically typed and dynamically typed is not always so clear cut when you're not talking about extremes such as Haskell and JavaScript.

Statically typed languages like Java, C++, C# and Scala can, and do have runtime type errors because they allow casting. They also all have type tags (well, optional in C++). I.e., most statically typed languages don't attempt to eliminate all type errors at compile time. Clojure indeed does very little static type checks (I think only function arity is checked).

Even in Haskell values must be tagged with types, and the type tags are inspected at runtime. Otherwise, pattern matching wouldn't work (pattern matching is always based on type reflection).

> I'm curious why you think multimethods are more limited than dynamic dispatch.

Because methods can't (or rarely do) "appear out of nowhere" or get installed at runtime as they do in, say, JavaScript or Groovy.

"can't" is a far cry from "rarely". Multimethods can be dynamically created during runtime.

Multimethods in general are not very common in Clojure. My point is that in order to understand Clojure you shouldn't think about it as you do about most dynamic languages, because its core mechanisms and abstractions are based on OO interfaces rather than dynamic dispatch.

You are very wrong about this. Clojure libraries are a very diverse ecosystem, and even a cursory analysis of the most widely used libraries will prove your assertion wrong. Heck, you can't even make custom printers (for your own types) in Clojure without extending the print-method multimethod.

Please don't speak for the Clojure community as a whole, because it spreads misinformation about both the libraries and the language itself. If you want to relate your personal experiences, fine, but your original post and this both convey a sense of absolutism in your characterization about Clojure's features that are just not true.

> Even in Haskell values must be tagged with types, and the type tags are inspected at runtime.

This does not fit my understanding of pattern matching in Haskell. Say you are matching over a value of type `Maybe String`. The type of the value is always `Maybe String`, it's just that its value might be `Just "foo"` or `Nothing :: Maybe String`. It is not to my knowledge tagged with type information at runtime in a compiled program, merely value information. The different values an ADT disjunction can take on all have the same type as each other.

> Otherwise, pattern matching wouldn't work (pattern matching is always based on type reflection).

What about pattern matching a String against a series of literal values? I don't see how this is based on type reflection, merely inspection of values.

In this context "tag" refers to the part of a value of type Maybe a which indicates whether that actual value is of the form Just a or Nothing. In other words, it's entirely runtime information distinguishing between various members of the same type

This is my understanding as well, and that's why I objected to the parent post's assertion that "even in Haskell values must be tagged with types, and the type tags are inspected at runtime". The enum/ADT discriminator tag is value information rather than type information.

Just and Nothing are different types even if the Haskell nomenclature doesn't call them so. The word "type" in Haskell means something different than it does in other languages. Haskell uses type to mean the mathematical notion of a set, while in CS, type usually refers to data memory layout. When comparing Haskell to other languages, we can't confuse terminology. In OO terms, for example, Just and Nothing are subtypes of Maybe, so the tag differentiating the two is exactly the same as that used to verify downcasts from the supertype Maybe to its subtypes, in, say, C++ or Java. Haskell implements the very same mechanism (call it reflection or RTTI).

Meh, that's a way to talk about it but the standard type system of Haskell doesn't include subtyping like that. It's possibly you could apply a subtyping analysis to Haskell, but it's certainly non-standard and I'm not sure what you really, literally gain.

Haskell doesn't call them subtypes, but they're implemented using type tags, just like RTTI. Haskell simply uses different words to mean the same thing (and the same words to mean different things). You can't say these aren't type tags just because Haskell doesn't call these things types.

I can say it's not a subtyping relationship because it happens entirely at runtime and my definition of types—the one consistent with what I referred to as Haskell's standard type analysis—does not include runtime dynamics.

If you want to pick a definition of typing which includes runtime information (and referencing RTTI, clearly you do) then we can shift to that vocabulary and talk about whether such an analysis includes a subtyping judgement. I'm not familiar with it.

But it's certainly not consistent with the standard Haskell type analysis. So there shouldn't be any surprise that the vocab doesn't match up.

> In other words, it lacks the most important mechanism that lends dynamically typed languages like JavaScript and Ruby their power.

I think you haven't spent much time using Clojure.

Your phrase "it is more of a mashup of a few ideas from functional and OO languages" seems intended to downplay the language as nothing important. By that metric, Ruby and Javascript are both "just" mashups of lisp/scheme, perl, smalltalk and self.

Clojure can be just as dynamic as JS & Ruby. On the JVM, protocols are implemented in terms of Java interfaces, because that's how you get fast dispatch, however, protocols share little in common with "standard" OO. There's no implementation inheritance, a protocol can be extended to any type (except for a few limitations caused by the JVM, those limitations don't apply to other implementations, like CLJS).

> For example, Clojure does not have dynamic dispatch (except for multimethods, which are a limited form of dynamic dispatch) other than that offered by OO polymorphism (interfaces/protocols). In other words, it lacks the most important mechanism that lends dynamically typed languages like JavaScript and Ruby their power.

Multimethods are actually a rather powerful form of dynamic dispatch. From the context, I think what you're referring to is late binding, which is when an identifier is resolved to a storage location / function implementation at runtime rather than at compile time. It's easy to get them confused, since late binding gives you dynamic dispatch "for free", but it is possible to have dynamic dispatch with early binding (as in C++, for example).

> Calling Clojure "dynamically typed" in this context (or any context), is confusing, as it is more of a mashup of a few ideas from functional and OO languages than a typical dynamically typed language.

A language's type system (or lack thereof) has nothing at all to do with dynamicity of dispatch nor binding.

I think you are underestimating the power of multimethods.

That clojure does not follow the duck typing approach of ruby and python but uses interces (protocols) does not make it a statically typed language. It is still dynamically typed to my understanding as the implementation of a protocol "method" is chosen at run time, i.e. _late_ binding.

For example: If I implement the ISeq data structure, I can use instances of my ISeq implementation in code that was written for lets say list processing (such as a function that uses ``(first val)``. The implementation is looked up at runtime. My program compiles, even if I call ``(first 4)``, it will lead in an error at runtime however, since the number 4 is not a sequence. Java is fundamentally different. It is checked at compile time whether the ``val`` does adhere to the interface. This is what makes it static.

Reply on news.ycombinator.com