5 ms·

Understanding Clojure Transducers Through Types

73 points by jkkramer 12y ago

gipp 12y ago
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?
- tel 12y ago
  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`
- platz 12y ago
  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.
rrradical 12y ago
There are some interesting comments at the bottom from Rich Hickey.
pron 12y ago
> ...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.
- lmkg 12y ago
  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?
  - pron 12y ago
    > 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.
    - willismichael 12y ago
      "can't" is a far cry from "rarely". Multimethods can be dynamically created during runtime.
kvb 12y ago
Seems like parametricity ensures that Transducer a b is isomorphic to b -> [a] Am I missing something?
- deleted 12y ago
  [deleted]
- tel 12y ago
  Nope—https://news.ycombinator.com/item?id=8160327 https://news.ycombinator.com/item?id=8160327

73 points by jkkramer 12y ago

gipp 12y ago

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?

tel 12y ago
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`
platz 12y ago
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.

rrradical 12y ago

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

pron 12y ago

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

lmkg 12y ago
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?
- pron 12y ago
  > 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.
  - willismichael 12y ago
    "can't" is a far cry from "rarely". Multimethods can be dynamically created during runtime.

kvb 12y ago

Seems like parametricity ensures that Transducer a b is isomorphic to b -> [a] Am I missing something?

deleted 12y ago
[deleted]
tel 12y ago
Nope—https://news.ycombinator.com/item?id=8160327 https://news.ycombinator.com/item?id=8160327