Hacker News Reader

Comment by kibwen | Hacker News Reader

I think it's time we stop using the phrase "functional" to describe this paradigm; at this point, every imperative language made in the past 30 years has first-class functions, and there is no other first-class language feature common to all the self-described "functional" languages.

IMO, a more accurate term would be stateless programming. This paradigm is about minimizing state. Of course, as the OP mentions, state is often quite useful. But minimizing state, especially global state, particularly mutable state, and especially particularly global mutable state, is something even imperative language fans can get behind.

View on HN

> there is no other first-class language feature common to all the self-described "functional" languages.

This line of speech usually serves to corner FP in a self-contradicting definition that can be wrestled with, and it is really aggravating.

Functional programming as a concept is well defined, and it's not merely "first-order functions". The reason why many functional languages don't have the same feature set is that programming languages are works of engineering, and that the essence of engineering is to make tradeoffs.

For instance, F#, a functional language, has many non-functional bits, because the goal pursued was to bring FP to .net, and they made sensible choice to promote interop above functional purity.

Likewise, most people doing FP with Lisp in the early days still used mutable variables, because they were limited by the machines they had.

Another example is the ability to perform all kinds of side-effects in many FP languages (Erlang, Clojure, etc.). That doesn't mean FP practicioners are totally fine with having side-effects. It means that totally separating side-effects from code in a general-purpose programming language is not always easy, and that in the interest of having useful projects, sometimes this goal is set aside. On the other hand, programs running on more limited runtimes (eg. Elm in browsers) achieve it completely.

It is really a pity that so many people can't or don't want to acknowledge the nature of engineering work, and hold imperfections against the creators, or the concepts they try to implement.

I agree. Also in a practical sense, functional paradigms are sometimes or often implemented with a single global mutable variable as a sort of database. This pattern is quite typical for both Clojure programs and JavaScript frontend programs.

It is really more about controlling state and avoiding it where deemed unnecessary, rather than adherence to a total philosophy. This is done for practical reasons (avoiding pain mostly), not for ideological ones.

> Functional programming as a concept is well defined, and it's not merely "first-order functions".

Then, sincerely, what is the definition? Does that definition succeed in excluding languages that are not considered functional, e.g. C++, Java, Python, Go? And if it doesn't, and the definition is so broad as to encompass every language, then what is the useful purpose of going out of one's way to label a language as "functional"?

Functional programming languages, more often than not, distinguish themselves with some combination of the following features:

* First-order functions

* Partial function application / currying

* Type inference

* Algebraic data types

* Typeclasses

* An emphasis on pure functions (side effects must be explicitly annotated), opening up more possibilities for static analysis

* Lazy evaluation

This is not to say that the above features cannot be emulated by other languages. For instance, Rust has traits, which serve more or less the same practical purpose as Haskell typeclasses.

However, FP is designed to prioritize the above features, whereas other languages may not be.

> However, FP is designed to prioritize the above features, whereas other languages may not be.

This statement is pretty vauge and further supports kibwen's claim that a term "functional programming" ceased to be meaningful or is in the course of being so. I can't see the reason that Rust is not as functional as OCaml by your standard, as both fill four boxes out of seven (only OCaml has currying, only Rust has typeclasses). It can be argued that Rust was not originally designed as functional one, but that would be absurd because it doesn't relate to the current language.

This quote elsewhere in the thread lines up with my knowledge:

> Functional programming was never about first-class functions. It was always about programming with pure and total functions in their mathematical version.

Other people have correctly pointed out that this is an extremely ambitious idea, since, as they have noted, you can't build a turing-complete language with pure and total functions.

This very high bar explains why there has been so many different design decisions in languages, and why most fp languages make tradeoffs in order to reach a compromise between what they believe is important in that concept, and what they can pull in terms of usable software.

As I noted as a response to that thread, we have seen in the recent years languages that achieve pure/total functions, but this was only possible because so many forebearers had tried different designs, and comprmised to produce usable software they could iterate from.

> It is really a pity that so many people can't or don't want to acknowledge the nature of engineering work, and hold imperfections against the creators, or the concepts they try to implement.

This would be a great stretch if it was meant to be a reply rather than a generic statement. To me the increasing irrelevance of a term "functional" is in fact the biggest success of the FP: it is entering the realm shared by, say, the term "structural programming" which is so universal that it became meaningless. It is an amazing feat given that no other terms for programming paradigms ever have been close this much!

Given any standard about the FP, there is a definite disparity between languages that should be called functional and languages that are actually called functional. I think the increasing universality of functional paradigm explains this, and kibwen is merely proposing another term describing the latter.

Eh, syntactically it hides the state as in `f x` has the same value every time, but calling functional programming stateless is a stretch, I consider it a half-truth told the newcomers to understand the concept. Functional languages still have state but they're abstracted out to function call. E.g. if you have a recursive descent parser written in Haskell, your program will still have state, not every time you're in `expr` function you'll have the same conceptual state.

I think lack of mutation is a lot more pronounced, since it has very important implications to runtime (necessary O(logn) slow down) and requires a more sophisticated type system (linear type system) in order to emulate safe mutation.

In addition, every closure is also a 'state container,' as it were. This is how some functional languages e.g. Erlang emulate mutation. A function holds the desired state in a closure and evaluates to a new function closure with updated state. It's also how a stateful object system can be trivially implemented in Scheme.

A few of pieces of the Erlang OTP infrastructure are actually just an elaborate mechanism to reintroduce global mutable state i.e. the process registry or Mnesia.

You can use closures to store state in Erlang, but generally state is kept by passing it through to further function calls.

I would say this makes Erlang mostly have explicit state, rather than saying Erlang is stateless.

Ets is implemented in C as global mutable state, but you could implement it in Erlang as a process per table (and a process to hold the list of tables) with no loss of functionality. You would send messages to fetch data or update data, etc. It's a performance and memory efficiency optimization to do it with C, of course.

Pure functional languages, aka Haskell or Idris or whatever, don't have this property. A closure closes over values, and thus is a value, no state mutation involved.

Of course, your point about complex mechanisms to reintroduce mutation into specific contexts stands (usually via monads) but those are a very different Kind of object then the functions.

It’s important to note Erlang’s global state tools are about controlled global state. The process registry is more elaborate than a simple naming scheme in say Python or Java but really not much harder to use. However that controlled registry allows the process registry to become multi-node with minimal or no code changes for the clients. It’s comparable in power to but far simpler than Consul or etcd for finding services. I view micro services as fairly equivalent to Erlang actors as they both reinforce that state encapsulation. The same idea goes for mnesia or ETS which are comparable in power to Redis.

It's a bit more subtle but the lack of statements that is, everything returns a value, is an important feature/quality.

Expressional or equational programming

Functional languages do have statements.

   a : Int -> Int

   a x = x + 2

both `:` and `=` are statements, not expressions.

This is sometimes true, the `=` equivalent in Clojure is an expression, though:

   user=> (def a (def b 2))
   user=> a
   #'b

Lisps generally only have expressions (every form returns a value.

Lisp runtime implicitly runs each top-level expression as statement. When you run (def x y) it's not only true that this expression returns 'x, it's also true that it alters the static state of the program by adding 'x to the scope.

To make a purely statementless language, I think you need to make everything happen in a single monadic computation. E.g. in pseudo-Haskell-ish:

    main : Scope -> StaticIO Scope
    main scope0 = do
      scope1, x' <- def scope0 "x" Int
      scope2, xv <- dec scope1 "x" 3

But the main part is still statement.

At least in all of the discussions I have seen, the difference between statements and expressions is whether they return a value, not whether they have side-effects. So (def x b) is an expression, because it returns a value. {} in C is a statement, even though it has no side effects.

Now, there are some statements in CL as far as I remember - I believe (declaim x integer) is a kind of statement, at least in the sense above.

But you can write a CL program that doesn't use a single statement.

The return value of some forms is implementation dependent, but all forms return a value in CL:

    CL-USER(1): (defparameter *foo* (declaim (special x)))    
    *FOO*
    CL-USER(2): *foo*
    (X)
    CL-USER(3): (defparameter *bar* (declaim (type integer x)))
    *BAR*
    CL-USER(4): *bar*    
    (X)

In other cases, e.g. `(values)` which is an expression that returns no values, the value is nil

They are usually called declarations rather than statements, I think.

How do any of those qualify as statements? Statements represent actions in imperative programming languages. Declarations and definitions are not actions.

Before reading this article and its follow-on, I would have completely endorsed the view that global mutable state is the worst, but for the sorts of issues the author is writing about, it seems that global mutable state is precisely the thing that makes procedural solutions more straightforward. In this case, it seems to be an intuitive and straightforward model for how both the programmer and player view the problem.

Until you attempt to multithread the logic and everything breaks.

This is true to the extent that it’s true to say that functional programming requires you to make copies of immutable structures every time something changes, which is to say not at all.

Multithreading is a problem when you have chaotic ownership of writes and updates. There are decades of prior art showing that this is a manageable problem using various strategies, and it’s not helpful to talk in absolutes rather than discussing the relative trade offs.

When your problem domain has changing global state, do you not have synchronization issues - ensuring that stale data is not used, for example - regardless of how you program it? I recall an article making this point, possibly by the same author.

The only thing worse than global mutable state is a complicated and buggy structure that does the exact same thing that global mutable state does

It makes the most sense to me to default to immutable, but swap to mutable when appropriate.

The article didn't talk about global mutable state. Nobody likes global mutable state. Nobody, not even C programmers. If possible mutable state should always be local to a function.

Scroll down to where it talks about the game "Bumbler" - the game environment is global mutable state.

There's kind-of a name for it too, it's a variation on blackboard programming, just not specifically for AI: https://en.wikipedia.org/wiki/Blackboard_system

Functional programming was never about first-class functions. It was always about programming with pure and total functions in their mathematical version.

This may be true in your personal experience but that’s certainly not universal. A key distinction is when you learned this: 2-3 decades ago when most people were using languages without first-class functions, this was very commonly the most important feature mentioned because it was the most pronounced difference. That’s no longer emphasized as much now that this feature and related techniques has become mainstream.

I believe the statement GP made has been true since the days of Church.

It is not surprising that "what's the difference between your language and mine" will yield an answer that is different than what you'll get if you ask "what is that concept you're trying to build a language after?"

That might be pointing out an important distinction: did you learn this formally from that academic community or elsewhere? As a global assertion it’s wrong but it could be accurately representative if you’re only talking about subcommunities in the former case.

I have made another comment in this thread where I make a distinction between what people _try_ to achieve, and what tradeoffs they make on the way.

You are right that most functional languages do not have pure and total functions. However, the inspiration they take from is usually the pure/total functions as described above.

> It was always about programming with pure and total functions in their mathematical version.

Are you sure about this? A total function is defined for all of its possible inputs, i.e., it must always terminate. A functional programming language with only total functions isn't Turing complete.

Several recent languages that came from the FP community recently tend to achieve this. This is the case of Agda, for instance, and I believe Idris also has totality checking.

Maybe you mean optional totality? As in, a function can be declared to be total and the compiler tries to prove it?

A language cannot be Turing-complete if it completely forbids non-termination, there is no way around this. Or stated differently: If a language is Turing-complete, then there are programs that don't terminate. If a Turing-complete language only has functions which are total (i.e., which always terminate), then it has another mechanism which allows non-termination, e.g. unbounded loops and mutable state.

> A language cannot be Turing-complete if it completely forbids non-termination, there is no way around this.

I do acknowledge this. My point is that turing-completeness is not necessarily a desirable aspect of a language. You can check out Agda if you are interested in what can be done with a total language.

For some use-cases, like seting up a mainloop, you need an escape hatch because that mainloop is not going to be total. But not every program needs that. Conversely, a programming language that doesn't care about totality won't be able to sere other use-cases, such as building proven programs. My understanding is that it's much easier to build an escape hatch in total languages, than it is to retrofit non-total languages to prove programs.

> My point is that turing-completeness is not necessarily a desirable aspect of a language.

Ah, okay, I see.

> For some use-cases, like seting up a mainloop, you need an escape hatch because that mainloop is not going to be total. But not every program needs that.

Hmm, I would argue that in practice, nearly all programs will need that, because they're either potentially non-terminating (let's call this "type 1") or have a runtime with a bound which is not determined by any of its inputs ("type 2"). Examples for type 1 include firmware, kernels, drivers, database engines, any kind of server, all programs with a GUI, all REPLs, and many Unix-style utilities that process or generate streams (thing grep, cat, sed, dd). Examples for type 2 include all programs with non-blocking IO (because even if the input and output are known to be bounded, the number of read/write calls is potentially unbounded) and most programs which take a file name as input (because the file size is not part of the program's input).

That doesn't leave many exceptions. I admit, however, that in most cases you could structure your program so that it has a non-total mainloop which exclusively calls proven total functions. But I don't think this is very useful, because even in safety-relevant, hard real-time contexts, termination is not sufficient, but termination within a certain timespan.

> That doesn't leave many exceptions.

Examples of programs which are useful and terminate are batch programs. Besides that, even in a server, you may want to ensure that a subset of the program terminates. For instance, if you're using a serverless architecture, knowing that your lambda will terminate may be useful.

Much like the separation between pure and impure functions in fp, having a distinction between total and non-total functions means that you can limit your non-total code to a couple dozen LoCs, which is a reasonable thing to manually check.

> But I don't think this is very useful, because even in safety-relevant, hard real-time contexts, termination is not sufficient, but termination within a certain timespan.

Once you've broken the non-termination issue, it becomes much more reasonable to start working on time estimates. Basically, once you've said that the number of instructions needed to solve the problem is a function of your input size, calculating that function becomes a possibility.

That's not really true. Op is programming in erlang, which has never in it's history been pure functional, and specifically picked the functional paradigm for pragmatic reasons (function-internal immutability and limited global state gives the programmer guardrails), not for pure mathematical reasons.

"Functional programming" is a useful description for techniques/approaches. The unifying principle tends to be (a) semantics based on definition and substitution of values/expressions (e.g. no ambient state/context) and (b) 'direct' evaluation strategy for expressions (e.g. no search, like in logic programming).

"Functional language" is less concrete; it's just an informal way to imply how easy or awkward it is to use these techniques in a particular language (e.g. bash is "less functional" than ML).

I think it's called functional because it emerges from the lambda calculus (truly just lambdas at the bottom) – but note this definition excludes javascript-with-immutability as well as clojure, not sure if lisp counts

They all count. It's like an athletics competition: everyone is an athlete even if not all people compete in the same discipline, or reach the same performances.

The other phenomenon here is that an imperative program with immutable state is isomorphic (exactly the same) as a functional program.

Literally the same thing.

Reply on news.ycombinator.com