4 ms·

Right, I'm a big fan of functional programming, but I never got warm with functional languages. One big reason is the syntax. I'd love to be able to specify (in

Right, I'm a big fan of functional programming, but I never got warm with functional languages. One big reason is the syntax. I'd love to be able to specify (in pseudo C(++): typedef positive_int: int { ensure {this > 0} } typedef ambulance: vehicle { ensure {this.has_siren && this.has_bed && this.color == "red"} } and so on. (aside: The other main problem I have with functional languages is the following, I'm not sure what to call it but it bites me every time: You finally find out how to do what you want in an elegant functional way, you code it up and you're happy. Then, you want to make a small modification, but it turns out that it's impossible with the current code, and you have to rewrite everything with much less abstraction. I can't remember a great example from the top of my head, but a simple one is, you'd like to add a progress bar to a computation. It's trivial in imperative languages, but much harder in functional style.)

discreteevent 13y ago
Prof. Van Roy gives a good example of this in the Edx course "Paradigms of Computer Programming" He uses the simple example of trying to introduce code to a pure functional program that will record the number of times a particular function is called. To do this you need to modify the signature of every function on the call stack. No doubt there's some other way to do this and it probably involves a monad but he was dealing with a simple pure functional language in the example. His point was that in this sense the pure system is not modular.
- platz 13y ago
  Pure functional languages have this advantage: all flow of data is made explicit. And this disadvantage: sometimes it is painfully explicit. Of course, you could just pull a Clojure and throw everything into maps.
- sold 13y ago
  That's exactly the point of monads - see http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/ba.... Such a system is still pure, btw.
- tel 13y ago
  I'd say any functional language so simple as to have that problem is probably some small variant on lambda calculus... and that's essentially the assembly of FP. The same thing is going to happen in your SSA-d C++ code.
kazagistar 13y ago
Unless you can teach the compiler how to verify that arbitrary expressions will be true at compile time, you have created a glorified syntax for assert. The reason for the the often strange syntax and structure in functional languages, especially dependently typed ones, is to allow you to restrict how you can construct programs so that it can give you those stronger assurances at compile time. You don't want your program to crash or throw a runtime error when you try to convert an int to a natural, you want it to not be possible to do unsafely in the first place.
- captainmuon 13y ago
  > Unless you can teach the compiler how to verify that arbitrary expressions will be true at compile time, you have created a glorified syntax for assert. Well, right now some languages are able to verify that a variable is non-null at compile time (C#). It should be possible to add range requirements to numeric types (e.g. i > 5), and (non-)equality requirements for most types. Intersections and unions of these requirements is trivial, so the compiler could work out possibly allowed and disallowed value (ranges). If we only allow these simple constraints, it is essentially constraint-solving at compile time. The compiler can "understand" these simple types, and it can see that a positive int (or a non-null Vehicle) is required, and propagate that backwards and see whether it is violated. (One could go a bit further and add almost arbitrary expressions (of C++11 constexpr strength). If the compiler can't convert the expression to a union or intersection of things it understands, it can still check if a given constant violates the condition. E.g. it is known that x=5, and the precondition of a function is x2 != 25, then this is a violation. I don't know how useful this would be, though. One could also add "lemmas" to aid the compiler, e.g. "I guarantee that x > 10 in this branch".)
fzltrp 13y ago
> you'd like to add a progress bar to a computation. It's trivial in imperative languages, but much harder in functional style. That depends a lot on how you code your program. You'll havr as much difficulties in imperative style if you didn't think up front about that feature (or any similar ones). What you want is modularity, and it means the ability to separate concerns at the language core. Luckily, un FP, functions being first class, you can easily extract functions out of an algorithm, and the pass them as parameters. So in your example, you'd parameterize on the function which does that computation step, and plug in that very function wrapped with one doing the progress bar update. With a well written codebase, this sort of things are just one refactoring away. This exercise being easier or harder is mostly a question of being used to the language imho.
tel 13y ago
The way you've asked this it will lead people to think you're asking for very powerful static checking. If you instead just want runtime assurances then the typical (Haskell) method is a "smart constructor". For instance: -- exporting only the type Positive, the extractor `getInt`, and the -- smart constructor `pint` ensures constraint safety. module Positive (Positive (getInt), pint) where newtype Positive = Positive { getInt :: Int } -- creation of Positive types ensures that constraint pint :: Int -> Maybe Positive pint i | i > 0 = Just i | otherwise = Nothing Now if you want that `ensure` line to be checked every time the Positive type gets modified... well, hopefully you're not leaving it up to the compiler to do that naïvely as you'll waste a lot of checks. A similar method can be done with the ambulance type, though I don't think modeling the world like that in functional types is a good design.
- captainmuon 13y ago
  > The way you've asked this it will lead people to think you're asking for very powerful static checking That's exactly what I'm asking for :-). It should be possible to create restricted types that are checked at runtime. For example, the fabs function would return a float which is guaranteed to be >= 0. The sqrt function would require the argument to be positive. float x; ... // arbitrary code sqrt(x); // warning, possible invalid argument float y; y = fabs(...); // y is now float<positive> sqrt(x); // no warning float z; z = -1.0; sqrt(z); // error: invalid argument, argument z of type float // fails constraint z > 0. z is constant -1.0 It is an error if the compiler can prove it to be wrong. It would probably be a warning if the compiler can't prove it to be safe - but you could optionally make it an error (to prove critical code). There are some cases where it won't work - a la solve_halting_problem() - but you could add little proofs to help it. For example, you could declare that sin(x) is `float<positive>` if `x > 0 || x < pi`. This may sound crazy, but I think the parts are already out there. C#'s non-nullable types are a very weak version of this (the compiler can infer if something could possibly be null, and complains if you assign it to a non-nullable type). Many compilers also track uninitialized variables, and only let you assign to them, not from them. They are also effectively a restricted version of the original type (every time you declare a float argument, you actually mean float<initialized>). Another ingredient is control-flow analysis. For example there is the excellent PySonar [1] that performs a whole-program analysis of Python programs and is able to infer types (including union types where it is not sure). In Python, values and types are somewhat blurred IMHO. Instead of variables, Python actually has `names`, and each name has a `type` and a `value` inside. Inferring what `type` a `name` could have is a bit like inferring what value a variable could have in other languages. So I think some of the lessons learned there could be valuable for building a something like this, too. [1] http://yinwang0.wordpress.com/2010/09/12/pysonar/ http://yinwang0.wordpress.com/2010/09/12/pysonar/

discreteevent 13y ago

Prof. Van Roy gives a good example of this in the Edx course "Paradigms of Computer Programming" He uses the simple example of trying to introduce code to a pure functional program that will record the number of times a particular function is called. To do this you need to modify the signature of every function on the call stack. No doubt there's some other way to do this and it probably involves a monad but he was dealing with a simple pure functional language in the example. His point was that in this sense the pure system is not modular.

platz 13y ago
Pure functional languages have this advantage: all flow of data is made explicit. And this disadvantage: sometimes it is painfully explicit. Of course, you could just pull a Clojure and throw everything into maps.
sold 13y ago
That's exactly the point of monads - see http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/ba.... Such a system is still pure, btw.
tel 13y ago
I'd say any functional language so simple as to have that problem is probably some small variant on lambda calculus... and that's essentially the assembly of FP. The same thing is going to happen in your SSA-d C++ code.

kazagistar 13y ago

Unless you can teach the compiler how to verify that arbitrary expressions will be true at compile time, you have created a glorified syntax for assert. The reason for the the often strange syntax and structure in functional languages, especially dependently typed ones, is to allow you to restrict how you can construct programs so that it can give you those stronger assurances at compile time. You don't want your program to crash or throw a runtime error when you try to convert an int to a natural, you want it to not be possible to do unsafely in the first place.

captainmuon 13y ago
> Unless you can teach the compiler how to verify that arbitrary expressions will be true at compile time, you have created a glorified syntax for assert. Well, right now some languages are able to verify that a variable is non-null at compile time (C#). It should be possible to add range requirements to numeric types (e.g. i > 5), and (non-)equality requirements for most types. Intersections and unions of these requirements is trivial, so the compiler could work out possibly allowed and disallowed value (ranges). If we only allow these simple constraints, it is essentially constraint-solving at compile time. The compiler can "understand" these simple types, and it can see that a positive int (or a non-null Vehicle) is required, and propagate that backwards and see whether it is violated. (One could go a bit further and add almost arbitrary expressions (of C++11 constexpr strength). If the compiler can't convert the expression to a union or intersection of things it understands, it can still check if a given constant violates the condition. E.g. it is known that x=5, and the precondition of a function is x2 != 25, then this is a violation. I don't know how useful this would be, though. One could also add "lemmas" to aid the compiler, e.g. "I guarantee that x > 10 in this branch".)

fzltrp 13y ago

> you'd like to add a progress bar to a computation. It's trivial in imperative languages, but much harder in functional style. That depends a lot on how you code your program. You'll havr as much difficulties in imperative style if you didn't think up front about that feature (or any similar ones). What you want is modularity, and it means the ability to separate concerns at the language core. Luckily, un FP, functions being first class, you can easily extract functions out of an algorithm, and the pass them as parameters. So in your example, you'd parameterize on the function which does that computation step, and plug in that very function wrapped with one doing the progress bar update. With a well written codebase, this sort of things are just one refactoring away. This exercise being easier or harder is mostly a question of being used to the language imho.

tel 13y ago

The way you've asked this it will lead people to think you're asking for very powerful static checking. If you instead just want runtime assurances then the typical (Haskell) method is a "smart constructor". For instance: -- exporting only the type Positive, the extractor `getInt`, and the -- smart constructor `pint` ensures constraint safety. module Positive (Positive (getInt), pint) where newtype Positive = Positive { getInt :: Int } -- creation of Positive types ensures that constraint pint :: Int -> Maybe Positive pint i | i > 0 = Just i | otherwise = Nothing Now if you want that `ensure` line to be checked every time the Positive type gets modified... well, hopefully you're not leaving it up to the compiler to do that naïvely as you'll waste a lot of checks. A similar method can be done with the ambulance type, though I don't think modeling the world like that in functional types is a good design.

captainmuon 13y ago
> The way you've asked this it will lead people to think you're asking for very powerful static checking That's exactly what I'm asking for :-). It should be possible to create restricted types that are checked at runtime. For example, the fabs function would return a float which is guaranteed to be >= 0. The sqrt function would require the argument to be positive. float x; ... // arbitrary code sqrt(x); // warning, possible invalid argument float y; y = fabs(...); // y is now float<positive> sqrt(x); // no warning float z; z = -1.0; sqrt(z); // error: invalid argument, argument z of type float // fails constraint z > 0. z is constant -1.0 It is an error if the compiler can prove it to be wrong. It would probably be a warning if the compiler can't prove it to be safe - but you could optionally make it an error (to prove critical code). There are some cases where it won't work - a la solve_halting_problem() - but you could add little proofs to help it. For example, you could declare that sin(x) is `float<positive>` if `x > 0 || x < pi`. This may sound crazy, but I think the parts are already out there. C#'s non-nullable types are a very weak version of this (the compiler can infer if something could possibly be null, and complains if you assign it to a non-nullable type). Many compilers also track uninitialized variables, and only let you assign to them, not from them. They are also effectively a restricted version of the original type (every time you declare a float argument, you actually mean float<initialized>). Another ingredient is control-flow analysis. For example there is the excellent PySonar [1] that performs a whole-program analysis of Python programs and is able to infer types (including union types where it is not sure). In Python, values and types are somewhat blurred IMHO. Instead of variables, Python actually has `names`, and each name has a `type` and a `value` inside. Inferring what `type` a `name` could have is a bit like inferring what value a variable could have in other languages. So I think some of the lessons learned there could be valuable for building a something like this, too. [1] http://yinwang0.wordpress.com/2010/09/12/pysonar/ http://yinwang0.wordpress.com/2010/09/12/pysonar/