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.
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.
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.
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.
The no non-determinism feature is very good example why TCO/TCE is crucial - each time you call a recursive function the state is changing- another stack is created. Therefore the same function which operates on unknown argument size(list, tree) can have different behavior - stack overflow might happen or not and we don’t know when.
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.
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.
Sounds good in theory but is never going to work in practice. Even static functions can store state and access global singletons, disk or the internet. Java doesn't have a way to specify constness of arguments either so preventing mutating an argument is very difficult.
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.
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.
> TCO only adds zero-cost for recursions based on tail calls
TCO isn't about recursion; it applies to any function call in tail position. Some toolchains only manage to avoid over-allocating stack frames for self-recursive tail calls, but that isn't full TCO, and it doesn't help for other interesting case like mutual recursion, state machines, or continuation-passing style. Compilers which compromise on full support for TCO emit programs with built-in memory leaks; they fail to free data which is no longer needed, and thus unnecessarily exhaust their stack allocation.
Programs which use built-in iterative constructs are still recursive; all that "recursion" means is that the control flow folds back on itself. A traditional "while" loop looks like: (1) stop if a condition is false; (2) otherwise do something; (3) do it again. The "it" in (3) is a recursive reference to the loop.
Now, unstructured explicit recursion is barely better than unstructured "goto", so I'm not advocating that everyone start using tail calls in place of loops. However, bare loops are in much the same position with respect to higher-order primitives such as non-strict folds—and those higher-order primitives are much easier to implement in environments which properly support TCO. Languages where TCO is not customary tend to suffer from a proliferation of built-in constructs—iteration, generators, list comprehensions, coroutines, and the like are all implemented as language features requiring custom code generation, where another language where TCO is customary might relegate such primitives to a library.
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).
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.
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).
Those are not FP languages. They are, at best, "functional-first" multi-paradigm languages. (Common Lisp and Scheme are in this category.) Unfortunately, FP is more about what is excluded (side effects) than what is included (closures, continuations, sum types, etc.), so mixing FP with any amount of imperative/procedural code tends to result in an awkward and less efficient form of imperative programming without the primary benefit of FP (referential transparency).
The "function" in "functional programming" refers to mathematical functions, which are fixed mappings from inputs to results with no side effects. If your "functions" can have side-effects then they're not functions, they're procedures. Programs composed of effectful procedures are imperative, not functional.
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.