4 ms·

I think the general feeling is that there are some code patterns that are safe and easy to do with dynamic typing, but impossible with simple type systems or mo

I think the general feeling is that there are some code patterns that are safe and easy to do with dynamic typing, but impossible with simple type systems or more complex with more advanced type system. An example would be Common Lisp's `map` function [0] (it takes a number of sequences and a function that has as many parameters as there are sequences). It would be hard to come up with a type for this in Java, and it would be a pretty complicated type in Haskell. Another example of many people's experience with static typing is the Go style of language, where you can't write any code that works for both a list of strings and a list of numbers. This is no longer common, but it used to be very common ~10-15 years ago and many may have not looked back. [0] http://www.lispworks.com/documentation/HyperSpec/Body/f_map.htm#map http://www.lispworks.com/documentation/HyperSpec/Body/f_map....

anonymoushn 6y ago
As an example of this, I've been working through Crafting Interpreters off and on. Chapter 5 consists mostly of discussion of the visitor pattern (is this the same thing as double dispatch?). The author notices that the amount of code that must be written to implement the design is so large that it's best to write a program to generate all of that code. I followed along as best I could, and at the end I wrote the equivalent code in my preferred language, which I've included in this comment: self[expr.type](self, expr)
the_af 6y ago
In my opinion, with few exceptions, the kind of programs advocates of dynamic typing want to write that static typing would have trouble dealing with, are artificial and not the common case. (Not "map" though, I need to review that case, but "map" is definitely a common and useful function!) > Another example of many people's experience with static typing is the Go style of language Remember that a lot of backlash against Go's type system comes from static typing advocates used to more expressive static type systems :) It'd be a shame if, after all we complained about Go's limitations, newcomers held Go as an example of why static typing is a roadblock...
- simiones 6y ago
  > In my opinion, with few exceptions, the kind of programs advocates of dynamic typing want to write that static typing would have trouble dealing with, are artificial and not the common case. (Not "map" though, I need to review that case, but "map" is definitely a common and useful function!) I mostly agree, don't get me wrong. And it's important to note that Common Lisp's `map` functions do more than what people traditionally associate with `map` - they basically do `map(foo, zip(zip(list1, list2), list3)...)`. Still, this is a pretty useful property, and it is very natural and safe to use or implement, while being impossible to give a type to in most languages. C++ can do it with the template system, as can Rust with macros (so, using dynamic typing at compile time). Haskell can make it look pretty decent (if you can stand operator soup) by relying on auto-currying and inline operators and a few helper functions. I would also note that the Haskell creators also though that this functionality is useful, so they implemented some of the required boilerplate in the standard lib already. In most languages, you can implement it with lambdas and zips (or reflection, of course). So I think that this is a nice example of a function that is not invented out of thin air, is useful, is perfectly safe and static in principle, but nevertheless is impossible to write "directly" in most statically typed languages. Just to show the full comparison, here is how using this would look in CL, Haskell and C#: CL (map 'list #'max3 '(1 3 5) '(-1 4 0) '(6 1 8)) Haskell max3 <$> ZipList [1 3 5] <*> ZipList [-1,4,0] <*> ZipList [6,1,8] OR (<*>) ((<*>) ((<$>) max3 (ZipList [1,2])) (ZipList [-1,4])) (ZipList [3,1]) C# new int[]{1,3,5}.Zip<int,int,Func<int,int>>(new int[]{-1,4,0}, (a,b) => (c) => max3(a, b, c)).Zip(new int[]{6, 1, 8}, (foo,c) => foo(c)) Note only the CL version, out of all these languages, can work for a function known at runtime instead of compile-time. None of the static type systems in common use can specify the type of this function, as they can't abstract over function arity. Here's a paper showing how this was handled in Typed Scheme: https://www2.ccs.neu.edu/racket/pubs/esop09-sthf.pdf https://www2.ccs.neu.edu/racket/pubs/esop09-sthf.pdf
Tyr42 6y ago
Haskell's not too bad once you understand ZipList http://learnyouahaskell.com/functors-applicative-functors-and-monoids http://learnyouahaskell.com/functors-applicative-functors-an... max <$> ZipList [1,2,3,4,5,3] <*> ZipList [5,3,1,2] > [5,3,3,4]
- tome 6y ago
  Yeah it's not at all complicated in Haskell. I'm not sure what GP is talking about.
  - simiones 6y ago
    I replied to the parent as well, but not only is the solution the parent showed significantly more complex than the CL version, I'm not even sure it actually does what I asked. More explicitly, the expression there seems to rely on knowing the arity of the function and the number of lists at compile time. Basically, I was asking for a function cl_map such that: cl_map foo [xs:[ys:[zs:...]]] = foo <$> xs <*> ys <*> zs <*> ... Edit: found a paper explaining that this is not possible in Haskell, and showing how the problem is solved in Typed Scheme: https://www2.ccs.neu.edu/racket/pubs/esop09-sthf.pdf https://www2.ccs.neu.edu/racket/pubs/esop09-sthf.pdf
    - tome 6y ago
      Sure it's possible in Haskell. I'm not sure where in that paper you got the impression it isn't. Of course one can't define variadic functions in Haskell, but that's a more fundamental difference from Clojure, not a "code pattern that [is] safe and easy to do with dynamic typing, but impossible with simple type systems or more complex with more advanced type system." > traverse_ print (sequenceA [ZipList [1,2], ZipList [3,4]]) [1,3] [2,4]
      - simiones 6y ago
        As far as I can tell, your example calls a unary function on each element of a list of lists. It's solving the variadic part of map, but not the part where I can call an N-ary function with each element of N lists. Basically, instead of your example I would like to do something like this: > cl_map (+) [ZipList [1,2,3], ZipList [4,5,6]] [5,7,9] > cl_map (+ 3) [ZipList [1,2,3]] [4,5,6] > cl_map max3 [ZipList [1,2], ZipList [3,4], ZipList [5,6]] where max3 x y z = max x (max y z) [5, 6] Can this be done? What is the type of cl_map? Note: If this doesn't work with ZipList, that's ok - the important part is being able to supply the function at runtime. Also, please don't assume that the function is associative or anything like that - it's an arbitrary function of N parameters.
dahauns 6y ago
IMO, Go is never a good example in static vs dynamic type system discussions (I mean, for this case: parametric polymorphism has been around since the 70s...). The language developers themselves have repeatedly stated that its type system being very limited is intentional. See e.g. here: https://github.com/golang/go/issues/29649#issuecomment-454820179 https://github.com/golang/go/issues/29649#issuecomment-45482... TBH, sometimes I wonder why they bothered with static typing at all...
- simiones 6y ago
  Sure, I know Go is a low blow to static typing. But in this particular regard, Java or C# don't fare much better either. This is not a question of just supporting parametric polymorphism, but of abstracting over the number of arguments of a function, which is not supported in almost any type system I know of; and then of matching the number of arguments received with the type of function you specified initially.
account42 6y ago
Not that complicated even in C++ template <typename... Lists, typename Func> auto map(Func && func, Lists &&... lists) -> std::vector<decltype(func(std::declval<typename std::decay<Lists>::type::value_type>()...))>;
- simiones 6y ago
  > std::declval<typename std::decay<Lists>::type::value_type>() Yes, nothing hard to understand or discover about that at all...
  - simiones 6y ago
    Replying to add: actually, not only is the type obscure, it also relies on knowing the lists at compile time, while the CL function can do this at runtime (note that there is no dynamic behavior, it's simply that C++'s type system can't abstract over function arity).
valenterry 6y ago
It's not that difficult to do in Scala, which is probably the language that comes most close to a mainstream language that has a typesystem powerful enough to express this. There are better languages for expressing this more natural (such as Idris) but in the end, the fallacy seems to lie in your claim that this would be "safe and easy to do with dynamic typing". That's what you think until you find out that your solution works in 99% of the cases, except in some special cases, because the compiler didn't have your back. Examples are the standard sort functions in Java and python, which were bugged for a very long time. Btw, here is the executable code in Scala: https://scalafiddle.io/sf/UrDu12b/1 https://scalafiddle.io/sf/UrDu12b/1 Posting it for reference in case Scalafiddle is down: import shapeless._, ops.function._ def multiMap[InputTypes <: HList, MapF, HListF, MapResult] (inputs: List[InputTypes])(mapF: MapF) (implicit fn: FnToProduct.Aux[MapF, InputTypes => MapResult]) = inputs.map(fn(mapF)) val testList2Elems = List( 3 :: "hi" :: HNil, 5 :: "yes" :: HNil ) multiMap(testList2Elems){ (num: Int, str: String) => s"$num times $str is ${List.fill(num)(str).mkString}" }.foreach(println) val testList3Elems = List( 3 :: "hi" :: 3 :: HNil, 5 :: "yes" :: 2 :: HNil, 2 :: "easy" :: 1 :: HNil ) multiMap(testList3Elems){ (num: Int, str: String, mult: Int) => s"$num * $mult times $str is ${List.fill(num*mult)(str).mkString}" }.foreach(println) // As expected, the compiler has our back and the following does not compile val testListWrongElems = List( 3 :: "hi" :: HNil, 5 :: "yes" :: "ups?" :: HNil ) /* * Whoops, does not compile, list shape not good for multiMap :) * multiMap(testListWrongElems){ (num: Int, str: String) => s"$num times $str is ${List.fill(num)(str).mkString}" }.foreach(println) */ /* * Whoops, does not compile, 2-sequences vs 3 argument function :) * multiMap(testList2Elems){ (num: Int, str: String, mult: Int) => s"$num * $mult times $str is ${List.fill(num*mult)(str).mkString}" }.foreach(println) */
- valenterry 6y ago
  I just checked the documentation of lisps implementation and it is different from my code. If the input lists have a different size, the shortest list decides the result length and everything else is discarded. This is of course possible to implement in Scala too, but I think it is a very bad thing to do that which can lead to bugs quite easy. I prefer my solution in that case.

anonymoushn 6y ago

As an example of this, I've been working through Crafting Interpreters off and on. Chapter 5 consists mostly of discussion of the visitor pattern (is this the same thing as double dispatch?). The author notices that the amount of code that must be written to implement the design is so large that it's best to write a program to generate all of that code. I followed along as best I could, and at the end I wrote the equivalent code in my preferred language, which I've included in this comment: self[expr.type](self, expr)

the_af 6y ago

In my opinion, with few exceptions, the kind of programs advocates of dynamic typing want to write that static typing would have trouble dealing with, are artificial and not the common case. (Not "map" though, I need to review that case, but "map" is definitely a common and useful function!) > Another example of many people's experience with static typing is the Go style of language Remember that a lot of backlash against Go's type system comes from static typing advocates used to more expressive static type systems :) It'd be a shame if, after all we complained about Go's limitations, newcomers held Go as an example of why static typing is a roadblock...

simiones 6y ago
> In my opinion, with few exceptions, the kind of programs advocates of dynamic typing want to write that static typing would have trouble dealing with, are artificial and not the common case. (Not "map" though, I need to review that case, but "map" is definitely a common and useful function!) I mostly agree, don't get me wrong. And it's important to note that Common Lisp's `map` functions do more than what people traditionally associate with `map` - they basically do `map(foo, zip(zip(list1, list2), list3)...)`. Still, this is a pretty useful property, and it is very natural and safe to use or implement, while being impossible to give a type to in most languages. C++ can do it with the template system, as can Rust with macros (so, using dynamic typing at compile time). Haskell can make it look pretty decent (if you can stand operator soup) by relying on auto-currying and inline operators and a few helper functions. I would also note that the Haskell creators also though that this functionality is useful, so they implemented some of the required boilerplate in the standard lib already. In most languages, you can implement it with lambdas and zips (or reflection, of course). So I think that this is a nice example of a function that is not invented out of thin air, is useful, is perfectly safe and static in principle, but nevertheless is impossible to write "directly" in most statically typed languages. Just to show the full comparison, here is how using this would look in CL, Haskell and C#: CL (map 'list #'max3 '(1 3 5) '(-1 4 0) '(6 1 8)) Haskell max3 <$> ZipList [1 3 5] <*> ZipList [-1,4,0] <*> ZipList [6,1,8] OR (<*>) ((<*>) ((<$>) max3 (ZipList [1,2])) (ZipList [-1,4])) (ZipList [3,1]) C# new int[]{1,3,5}.Zip<int,int,Func<int,int>>(new int[]{-1,4,0}, (a,b) => (c) => max3(a, b, c)).Zip(new int[]{6, 1, 8}, (foo,c) => foo(c)) Note only the CL version, out of all these languages, can work for a function known at runtime instead of compile-time. None of the static type systems in common use can specify the type of this function, as they can't abstract over function arity. Here's a paper showing how this was handled in Typed Scheme: https://www2.ccs.neu.edu/racket/pubs/esop09-sthf.pdf https://www2.ccs.neu.edu/racket/pubs/esop09-sthf.pdf

Tyr42 6y ago

Haskell's not too bad once you understand ZipList http://learnyouahaskell.com/functors-applicative-functors-and-monoids http://learnyouahaskell.com/functors-applicative-functors-an... max <$> ZipList [1,2,3,4,5,3] <*> ZipList [5,3,1,2] > [5,3,3,4]

tome 6y ago
Yeah it's not at all complicated in Haskell. I'm not sure what GP is talking about.
- simiones 6y ago
  I replied to the parent as well, but not only is the solution the parent showed significantly more complex than the CL version, I'm not even sure it actually does what I asked. More explicitly, the expression there seems to rely on knowing the arity of the function and the number of lists at compile time. Basically, I was asking for a function cl_map such that: cl_map foo [xs:[ys:[zs:...]]] = foo <$> xs <*> ys <*> zs <*> ... Edit: found a paper explaining that this is not possible in Haskell, and showing how the problem is solved in Typed Scheme: https://www2.ccs.neu.edu/racket/pubs/esop09-sthf.pdf https://www2.ccs.neu.edu/racket/pubs/esop09-sthf.pdf
  - tome 6y ago
    Sure it's possible in Haskell. I'm not sure where in that paper you got the impression it isn't. Of course one can't define variadic functions in Haskell, but that's a more fundamental difference from Clojure, not a "code pattern that [is] safe and easy to do with dynamic typing, but impossible with simple type systems or more complex with more advanced type system." > traverse_ print (sequenceA [ZipList [1,2], ZipList [3,4]]) [1,3] [2,4]
    - simiones 6y ago
      As far as I can tell, your example calls a unary function on each element of a list of lists. It's solving the variadic part of map, but not the part where I can call an N-ary function with each element of N lists. Basically, instead of your example I would like to do something like this: > cl_map (+) [ZipList [1,2,3], ZipList [4,5,6]] [5,7,9] > cl_map (+ 3) [ZipList [1,2,3]] [4,5,6] > cl_map max3 [ZipList [1,2], ZipList [3,4], ZipList [5,6]] where max3 x y z = max x (max y z) [5, 6] Can this be done? What is the type of cl_map? Note: If this doesn't work with ZipList, that's ok - the important part is being able to supply the function at runtime. Also, please don't assume that the function is associative or anything like that - it's an arbitrary function of N parameters.

dahauns 6y ago

IMO, Go is never a good example in static vs dynamic type system discussions (I mean, for this case: parametric polymorphism has been around since the 70s...). The language developers themselves have repeatedly stated that its type system being very limited is intentional. See e.g. here: https://github.com/golang/go/issues/29649#issuecomment-454820179 https://github.com/golang/go/issues/29649#issuecomment-45482... TBH, sometimes I wonder why they bothered with static typing at all...

simiones 6y ago
Sure, I know Go is a low blow to static typing. But in this particular regard, Java or C# don't fare much better either. This is not a question of just supporting parametric polymorphism, but of abstracting over the number of arguments of a function, which is not supported in almost any type system I know of; and then of matching the number of arguments received with the type of function you specified initially.

account42 6y ago

Not that complicated even in C++ template <typename... Lists, typename Func> auto map(Func && func, Lists &&... lists) -> std::vector<decltype(func(std::declval<typename std::decay<Lists>::type::value_type>()...))>;

simiones 6y ago
> std::declval<typename std::decay<Lists>::type::value_type>() Yes, nothing hard to understand or discover about that at all...
- simiones 6y ago
  Replying to add: actually, not only is the type obscure, it also relies on knowing the lists at compile time, while the CL function can do this at runtime (note that there is no dynamic behavior, it's simply that C++'s type system can't abstract over function arity).

valenterry 6y ago

It's not that difficult to do in Scala, which is probably the language that comes most close to a mainstream language that has a typesystem powerful enough to express this. There are better languages for expressing this more natural (such as Idris) but in the end, the fallacy seems to lie in your claim that this would be "safe and easy to do with dynamic typing". That's what you think until you find out that your solution works in 99% of the cases, except in some special cases, because the compiler didn't have your back. Examples are the standard sort functions in Java and python, which were bugged for a very long time. Btw, here is the executable code in Scala: https://scalafiddle.io/sf/UrDu12b/1 https://scalafiddle.io/sf/UrDu12b/1 Posting it for reference in case Scalafiddle is down: import shapeless._, ops.function._ def multiMap[InputTypes <: HList, MapF, HListF, MapResult] (inputs: List[InputTypes])(mapF: MapF) (implicit fn: FnToProduct.Aux[MapF, InputTypes => MapResult]) = inputs.map(fn(mapF)) val testList2Elems = List( 3 :: "hi" :: HNil, 5 :: "yes" :: HNil ) multiMap(testList2Elems){ (num: Int, str: String) => s"$num times $str is ${List.fill(num)(str).mkString}" }.foreach(println) val testList3Elems = List( 3 :: "hi" :: 3 :: HNil, 5 :: "yes" :: 2 :: HNil, 2 :: "easy" :: 1 :: HNil ) multiMap(testList3Elems){ (num: Int, str: String, mult: Int) => s"$num * $mult times $str is ${List.fill(num*mult)(str).mkString}" }.foreach(println) // As expected, the compiler has our back and the following does not compile val testListWrongElems = List( 3 :: "hi" :: HNil, 5 :: "yes" :: "ups?" :: HNil ) /* * Whoops, does not compile, list shape not good for multiMap :) * multiMap(testListWrongElems){ (num: Int, str: String) => s"$num times $str is ${List.fill(num)(str).mkString}" }.foreach(println) */ /* * Whoops, does not compile, 2-sequences vs 3 argument function :) * multiMap(testList2Elems){ (num: Int, str: String, mult: Int) => s"$num * $mult times $str is ${List.fill(num*mult)(str).mkString}" }.foreach(println) */

valenterry 6y ago
I just checked the documentation of lisps implementation and it is different from my code. If the input lists have a different size, the shortest list decides the result length and everything else is discarded. This is of course possible to implement in Scala too, but I think it is a very bad thing to do that which can lead to bugs quite easy. I prefer my solution in that case.