5 ms·

Having lambda doesn’t mean to be FP. One of the core features missing in Java (JavaScript also) is TCO(tail call optimization)

by rydel 8y ago

dnautics 8y ago
Julia is missing TCO and it is for sure functional.
pjmlp 8y ago
First of all not all FP languages have TCO, Scheme is probably the only one that actually requires it on its language specification. Secondly stuff like LINQ was already available in Smalltalk. So all those map/filter/fold/.... constructs from lambda calculus, which Java now enjoys. Then if we apply the modern concept of only Haskell is FP, then there are a couple of FP languages that won't meet the classification. Ah, and Haskell does not require TCO on their language specification, so it isn't an FP language according to your arbitrary definition.
- rydel 8y ago
  It depends. As we know, FP is all about not having side effects. Having “for” loop requires to mutate the pointer of given iteration.
  - pjmlp 8y ago
    Oh, and I thought all these years that OCaml was a FP language, go figure! open Printf;; printf "After all OCaml isn't a FP language\n"; for idx = 1 to 10 do printf "%d\n" idx done Same goes to Common Lisp, F#, Scala, Clojure.
- rydel 8y ago
  There are many definitions of FP. IMHO the “no side effects” is the best one. Even Clojure is functional, but partially IMHO, bc it is for JVM which has not been design for FP. And my definition is not an arbitrary one. This is the most broadly one I think. But when you use same word in different contexts, then the word might have different meaning.
  - pjmlp 8y ago
    Which means OCaml, Common Lisp, Scheme, F#, SML are out of the game as FP languages according to you.
    - rydel 8y ago
      Is I wrote: IMO these language are not fully functional. TCO/TCE is crucial for operations on tree like data structures. And also as I wrote: it all depends in which context we are talking to. Scheme specification makes it clear that TCO/TCE is required. If I am not wrong, F# is the same thing as Scala, but in .Net world(?) - Scala cannot be treaded as clear functional, because it is for JVM which was not designed for functional programming. Surely, many languages can have more or less functional functionalities, but having a subset of properties which defines what is functional, cannot be treated as functional in the full sense.
- rydel 8y ago
  Java class can be functional also. Depends how you look. If a class doesn’t operates on side effects, but keeps the mutation only inside the class, then the class can be defined as functional. But on the method level it might be not.
charlysl 8y ago
According to the pdf's author, the crucial feature of FP is that there is no visible non-determinism. This means that every time you call a function with the same arguments it is guaranteed that you will get the same result. The other key feature is that there are no visible side-effects when calling a function. Tail recursion of course is great to have, but you can certainly FP without it, even in a language that supports it. I mean, what if you don't put the recursive call in tail position in a function written in a language that supports tail recursion? It would still be FP.
- pjmlp 8y ago
  You can get that in Java as well. Just create a static class without member fields where the class plays the role of a poor man's ML module, with all static functions only interacting with their parameters. Then static import it into the client package.
  - charlysl 8y ago
    This is not the way to do FP in Java though. Even before lambdas were introduced, you could do FP in Java. This is actually the whole point of GoF design patterns such as Interpreter and Visitor, which together with Composite are the way to write recursive data definitions (and functions that operate on them) in Java (or C++). The whole idea of "Little Languages" is FP, representing operations as data, as an AST. How to do FP in Java is very well explained in the MIT OCW course 6.005 "Elements of Software Construction", 2008 [1], in particular in lectures 10, 11, 13, 14 & 15. Remember that you can create closures with inner classes. As for the fact that in Java you could have state inside, say, a Visitor, the program can still be FP, if you know what you are doing. The point is that when doing FP in a language like Java, you are adopting a definitional approach to FP, which is totally legit: any operation is FP if it is deterministic and has no visible side-effects (a corollary is that then it wouldn't have any observable state of its own, it would be reactive). This is sort of a "if it walks like a duck ..." approach to FP. In fact, this is exactly what is going on when you are doing reactive programming in a non FP language like Javascript, where there are no restrictions to doing destructive assignment anywhere. This doesn't stop you from doing reactive programming, as long as you follow certain guidelines (because the language won't stop you from infringing them and having state). How is this possible? The reason is that the OO computation model subsumes FP: anything you can express in an FP language, you can express in an OO language, and then some (although not as naturally, there is more plumbing in the way). The reverse is not true, and this is a good thing, it is exactly what allows FP to have all those desirable properties. [1] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-005-elements-of-software-construction-fall-2008/ https://ocw.mit.edu/courses/electrical-engineering-and-compu...
13415 8y ago
Tail call optimization is more or less unimportant, because you can express any recursion with iteration and most of the time the explicitly iterative version is even safer and better. TCO only adds zero-cost for recursions based on tail calls, that's nice to have but recursion is a bit of a hobby-horse of CS professors anyway. It only makes sense in languages that have their own stack, i.e., have no hard stack limit except for your main memory, otherwise you will run out of stack space soon. Iterative versions of functions are often easier to understand, too.
- lysium 8y ago
  Did you consider mutual recursive functions in your answer? For example implementations of parsers?
- Jtsummers 8y ago
  Recursion is great, IMHO, as a non-professor type. It allows for much clearer expressions of intent for my methods and functions than the iterative version often achieves. There are some recursive structures that are just much more natural than their iterative counterparts. Parsing (as lysium suggests in the sibling post), for example. But also things like graph and tree traversals, and many search algorithms related to those same structures. If you attempt a tree traversal iteratively, you have to maintain the return stack manually, rather than permitting the language to do it for you (assuming a full traversal and not a search, a search could be done iteratively without much trouble).
  - 13415 8y ago
    I'd say the opposite. Mutually recursive functions are notoriously hard to get right and debug, and many languages have stack limits. Often it's better to maintain the stack manually.
    - Jtsummers 8y ago
      That has not been my experience, but I know many people who agree with you. IME, the difference has been that I came into CS with a more mathematical (formal) approach to programming, and they tended to come at it with a more mechanistic approach (especially when I hear it from non-CS developers, often EEs).
zbuttram 8y ago
Just wanted to point out that JS has TCO coming, just a question of if/when engines have it implemented. Looks like Safari/JSCore is pretty much the only one so far though: https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation) https://kangax.github.io/compat-table/es6/#test-proper_tail_...
- rydel 8y ago
  Yes. I am well aware about that. I look forward to TCO/TCE be supported on other platforms.
lysium 8y ago
I think the concept you describe is better named tail call eliminiation. “Optimization” makes it sound as if you could turn it off or on for performance reasons. Instead, programs rely on tail call elimination being in place or otherwise they would not work.

Having lambda doesn’t mean to be FP. One of the core features missing in Java (JavaScript also) is TCO(tail call optimization)

by rydel 8y ago

Having lambda doesn’t mean to be FP. One of the core features missing in Java (JavaScript also) is TCO(tail call optimization)

dnautics 8y ago

Julia is missing TCO and it is for sure functional.

pjmlp 8y ago

First of all not all FP languages have TCO, Scheme is probably the only one that actually requires it on its language specification. Secondly stuff like LINQ was already available in Smalltalk. So all those map/filter/fold/.... constructs from lambda calculus, which Java now enjoys. Then if we apply the modern concept of only Haskell is FP, then there are a couple of FP languages that won't meet the classification. Ah, and Haskell does not require TCO on their language specification, so it isn't an FP language according to your arbitrary definition.

rydel 8y ago
It depends. As we know, FP is all about not having side effects. Having “for” loop requires to mutate the pointer of given iteration.
- pjmlp 8y ago
  Oh, and I thought all these years that OCaml was a FP language, go figure! open Printf;; printf "After all OCaml isn't a FP language\n"; for idx = 1 to 10 do printf "%d\n" idx done Same goes to Common Lisp, F#, Scala, Clojure.
rydel 8y ago
There are many definitions of FP. IMHO the “no side effects” is the best one. Even Clojure is functional, but partially IMHO, bc it is for JVM which has not been design for FP. And my definition is not an arbitrary one. This is the most broadly one I think. But when you use same word in different contexts, then the word might have different meaning.
- pjmlp 8y ago
  Which means OCaml, Common Lisp, Scheme, F#, SML are out of the game as FP languages according to you.
  - rydel 8y ago
    Is I wrote: IMO these language are not fully functional. TCO/TCE is crucial for operations on tree like data structures. And also as I wrote: it all depends in which context we are talking to. Scheme specification makes it clear that TCO/TCE is required. If I am not wrong, F# is the same thing as Scala, but in .Net world(?) - Scala cannot be treaded as clear functional, because it is for JVM which was not designed for functional programming. Surely, many languages can have more or less functional functionalities, but having a subset of properties which defines what is functional, cannot be treated as functional in the full sense.
rydel 8y ago
Java class can be functional also. Depends how you look. If a class doesn’t operates on side effects, but keeps the mutation only inside the class, then the class can be defined as functional. But on the method level it might be not.

charlysl 8y ago

According to the pdf's author, the crucial feature of FP is that there is no visible non-determinism. This means that every time you call a function with the same arguments it is guaranteed that you will get the same result. The other key feature is that there are no visible side-effects when calling a function. Tail recursion of course is great to have, but you can certainly FP without it, even in a language that supports it. I mean, what if you don't put the recursive call in tail position in a function written in a language that supports tail recursion? It would still be FP.

pjmlp 8y ago
You can get that in Java as well. Just create a static class without member fields where the class plays the role of a poor man's ML module, with all static functions only interacting with their parameters. Then static import it into the client package.
- charlysl 8y ago
  This is not the way to do FP in Java though. Even before lambdas were introduced, you could do FP in Java. This is actually the whole point of GoF design patterns such as Interpreter and Visitor, which together with Composite are the way to write recursive data definitions (and functions that operate on them) in Java (or C++). The whole idea of "Little Languages" is FP, representing operations as data, as an AST. How to do FP in Java is very well explained in the MIT OCW course 6.005 "Elements of Software Construction", 2008 [1], in particular in lectures 10, 11, 13, 14 & 15. Remember that you can create closures with inner classes. As for the fact that in Java you could have state inside, say, a Visitor, the program can still be FP, if you know what you are doing. The point is that when doing FP in a language like Java, you are adopting a definitional approach to FP, which is totally legit: any operation is FP if it is deterministic and has no visible side-effects (a corollary is that then it wouldn't have any observable state of its own, it would be reactive). This is sort of a "if it walks like a duck ..." approach to FP. In fact, this is exactly what is going on when you are doing reactive programming in a non FP language like Javascript, where there are no restrictions to doing destructive assignment anywhere. This doesn't stop you from doing reactive programming, as long as you follow certain guidelines (because the language won't stop you from infringing them and having state). How is this possible? The reason is that the OO computation model subsumes FP: anything you can express in an FP language, you can express in an OO language, and then some (although not as naturally, there is more plumbing in the way). The reverse is not true, and this is a good thing, it is exactly what allows FP to have all those desirable properties. [1] https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-005-elements-of-software-construction-fall-2008/ https://ocw.mit.edu/courses/electrical-engineering-and-compu...

13415 8y ago

Tail call optimization is more or less unimportant, because you can express any recursion with iteration and most of the time the explicitly iterative version is even safer and better. TCO only adds zero-cost for recursions based on tail calls, that's nice to have but recursion is a bit of a hobby-horse of CS professors anyway. It only makes sense in languages that have their own stack, i.e., have no hard stack limit except for your main memory, otherwise you will run out of stack space soon. Iterative versions of functions are often easier to understand, too.

lysium 8y ago
Did you consider mutual recursive functions in your answer? For example implementations of parsers?
Jtsummers 8y ago
Recursion is great, IMHO, as a non-professor type. It allows for much clearer expressions of intent for my methods and functions than the iterative version often achieves. There are some recursive structures that are just much more natural than their iterative counterparts. Parsing (as lysium suggests in the sibling post), for example. But also things like graph and tree traversals, and many search algorithms related to those same structures. If you attempt a tree traversal iteratively, you have to maintain the return stack manually, rather than permitting the language to do it for you (assuming a full traversal and not a search, a search could be done iteratively without much trouble).
- 13415 8y ago
  I'd say the opposite. Mutually recursive functions are notoriously hard to get right and debug, and many languages have stack limits. Often it's better to maintain the stack manually.
  - Jtsummers 8y ago
    That has not been my experience, but I know many people who agree with you. IME, the difference has been that I came into CS with a more mathematical (formal) approach to programming, and they tended to come at it with a more mechanistic approach (especially when I hear it from non-CS developers, often EEs).

zbuttram 8y ago

Just wanted to point out that JS has TCO coming, just a question of if/when engines have it implemented. Looks like Safari/JSCore is pretty much the only one so far though: https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation) https://kangax.github.io/compat-table/es6/#test-proper_tail_...

rydel 8y ago
Yes. I am well aware about that. I look forward to TCO/TCE be supported on other platforms.

lysium 8y ago

I think the concept you describe is better named tail call eliminiation. “Optimization” makes it sound as if you could turn it off or on for performance reasons. Instead, programs rely on tail call elimination being in place or otherwise they would not work.