Hacker News Reader

Data flow, and FP, are about explicitly passing all the required dependencies into any step in the process, and getting back all the results

I always knew there was some relationship between FP and dataflow. There is something profound here. However, I'm not so sure that current FP languages are capturing this something in the best possible way. To me this:

http://www.lihaoyi.com/post/BasicFunctionalProgramming/CodeG...

Somehow seems far inferior to this:

http://www.lihaoyi.com/post/BasicFunctionalProgramming/Diagr...

Some syntactic sugar can help with this a bit; here's the same code rewritten using the pipe operator in Elixir:

    def make_tiramisu(eggs, sugar1, wine, cheese, cream, fingers, espresso, sugar2, cocoa)
      beat(eggs)
      |> beat(sugar1, wine)
      |> whisk
      |> beat(beat(cheese))
      |> fold(whip(cream))
      |> assemble(
        soak2seconds(fingers, disolve(sugar2, espresso)))
      |> sift(cocoa)
    end

It reads a lot closer to the recipe, though the nested multiple operations are still a bit hard to read. Separating them into their own named functions would probably be better.

In Clojure:

    (defn make-tiramisu [eggs sugar1 wine cheese cream fingers espresso sugar2 cocoa]
      (-> eggs
          (beat)
          (beat sugar1 wine)
          (whisk)
          (beat (beat cheese))
          (fold (whip cream))
          (assemble (soak2seconds fingers (dissolve sugar2 espresso)))
          (sift cocoa)
          (refrigerate)))

My first love was computer graphics and multimedia, the only software I liked were ones that:

1) had features called virtual entities: you don't crunch bytes, you manipulate the concepts, and only when needed you compute

2) non destructive edition: since 1) you can pile up operations without ever fearing loss of information, or memory usage for backup. The first audio editing software I had was Sound Forge, a simple one, every operation meant allocating a new space, computing, filling. This meant limited undo and higher resource requirements

3) from 1 and 2 you get laziness

(examples: nothing real shake, sidefx houdini, alias wavefront maya, sekd samplitude, anything by discreet. All these made far better use of your hardware. Compared to famous but non lazy ones such as Sound Forge or 3dsmax .. your poor desktop became pro tool (sic). Well until you hit the final render button of course)

Later I discovered FP and I laughed nervously.

Also many many highly rated CGI software use dataflow on a lazy DAG. GHC uses this for sharing computation in the evaluation model.

Here's a nice little paper from this year's ICFP about building a video editing tool using Racket.

https://dl.acm.org/citation.cfm?doid=3136534.3110274

> The Racket doctrine tells developers to narrow the gap between the terminology of a problem domain and general programming constructs by creating languages instead of just plain programs. This pearl illustrates this point with the creation of a relatively simple domain-specific language for editing videos. To produce the video proceedings of a conference, for example, video professionals traditionally use "non-linear" GUI editors to manually edit each talk, despite the repetitive nature of the process. As it turns out, video editing naturally splits the work into a declarative phase and an imperative rendering phase at the end. Hence it is natural to create a functional-declarative language for the first phase, which reduces a lot of manual labor. This user-facing DSL utilizes a second, internal DSL to implement the second phase, which is an interface to a general, low-level C library. Finally, we inject type checking into our language via another DSL that supports programming in the language of type formalisms. In short, the development of the video editing language cleanly demonstrates how the Racket doctrine naturally leads to the creation of language hierarchies, analogous to the hierarchies of modules found in conventional functional languages.

I tell people it's about focusing on inputs and outputs rather than worrying about inputs and side-effects.

It let's you develop complex programs with clear separation of responsibilities without having to try to keep the model of the entire state-space in your head at once.

Yeah, I find that pure functions (or pure functions living in immutable objects) makes my code immensely more composable and easier to work with (i.e. more adaptable and less expensive to own). If some business requirement changes I can recompose and tweak existing code without reading every line of code to figure out what side effects may unintentionally get triggered.

I never really properly learned TDD and always felt a bit bad about it. Then I discovered this side effect (or primary effect) of FP and felt like there was no real need for tests. Not sure if I'm just rationalizing but the ability to drop into the data flow and make changes or add features with confidence makes programming so much more fun.

The thing that stops you from doing data-flow freely in C or assembly is ownership of memory.

In a GCed language, you can freely your parameters into a complex returned structure; without GC, you can't mix up ownerships without a separate accounting system.

Consider:

    struct some_struct *f(int x, char *y)
    {
        struct some_struct *result = malloc(sizeof *result);
        if (x < 0)
            result->value = "negative";
        else
            result->value = y;
        return result;
    }

If you're writing functional code, the return values of your routines will normally be a function of the parameters, which often means wholesale inclusion. Without GC, you need to do a lot more preemptive copying, and freeing the resulting data structures is much more painful.

Alternative accounting systems can be used, e.g. arena or marker based allocation (freeing everything allocated when control returns to earlier points on the stack), or something else more involved. But it's not free.

C++11 allows you to write natural "value-oriented" code without paying a copying cost. This is thanks to RVO (return value optimization) and move semantics.

There is often a great deal of copy elision when passing things by value when the compiler can prove it the copying itself won't cause side effects.

You might have noticed that we were talking about C and assembly.

I do like that too. lambda is just "I need this and that for the body to make sense".

I also like that providing partial dependencies isn't an error, but yields a smaller-dependencies lambda (thanks curry I guess).

But more and more I go away from functions as a thing. Scheme compiler turn lambdas into goto+args, Prolog made me think of programs as forest/graphs that you walk... and yes if you look at functions as dependencies then you end up as a description of a dep. graph.. so graphs again.

> I also like that the focus on data-flow makes it clear you can do FP in any language.

Challenge to anyone who cares:

Do FP using Microsoft BASIC, circa 1980 or thereabouts (heck, if you want, use any BASIC from that era).

I'm pretty sure FP would be easier to demonstrate using Logo from that period than using BASIC.

/carry on...

> Do FP using Microsoft BASIC, circa 1980 or thereabouts (heck, if you want, use any BASIC from that era).

Well... anything without higher order functions & currying is gonna struggle with _beauty_ when it comes to Functional Programming... And Basics type system wouldn't be particularly enjoyable in the context of serious development...

That said, and supporting the OPs point: mapping the required functional data transformations, establishing a flow of transformed data, and producing code to support that transformation is highly achievable in typed imperative languages. In fact, it would be right at home in Basic...

Creating immutable, side-effect free functions in Basic that are then chained on matching output types and input types, and composing those functions in a control function, would look much closer to "bog standard" Basic than attempting OOP in Basic does. In fact, to a trained imperative Basic developer, it would look like very clean, composable, code that had logical and contained GOTOs and a well-reasoned strict relationship to changing data in incoming parameters...

You would not have any language support forcing you to Do The Right Thing, and there would be oodles of temp variables smart FP languages just compose away... but to do FP in MS Basic ca 1980? Just grab some imperative Basic, strip the side effects, and you're done. Basics later modules are a great conceptual match for Haskell and OCamls modules, too...

> I'm pretty sure FP would be easier to demonstrate using Logo from that period than using BASIC.

Logo is a LISP dialect created to teach (functional) programming and logic, so that claim would apply to lots of languages IMO :)

I think the idea that FP isn't highly grokable in imperative languages is a symptom of the biggest problem with functional programming: it's both far simpler than we imagine and more complex.

Do you remember if GOSUB <label> or GOTO <line number> can take the contents of a variable as an input?

If so, then higher-order functions seem possible.

Edit: it looks like in at least some versions of basic you can do:

ON switching_variable GOSUB first_label, second_label, third_label, ...

As you, I like the focus on data-flow, but I disagree when you said that:

> Making all dependencies explicit will force you into writing immutable code.

We have the opposite:

Writing immutable code will force you into making all dependencies explicit.

:) You sure you disagree? I said both, and the most important part is it works both ways. That's why I like the data-flow point of view; it more naturally gives rise to thinking about both immutability and explicit dependencies, and helps to avoid arguments over whether immutability is what defines functional programming.

Indeed I reacted a bit too quickly ! You are right. You were even going straight to the point when saying that "These are two sides of the data-flow coin."

But without immutable data structures, even in a language like C you end up with a very expensive copying for FP work.

Immutability typically requires lots of copying anyways, even in functional languages. There is no free lunch to be had.

I would say that the opportunity to freely share values without needing to defensively copy is of greater benefit, especially with an increasingly multicore future. Updating in-place also requires memory barriers, which don't scale.

Surely immutability works well when sharing values that shouldn't change anyways, in functional or other styles of programming.

What we are talking about here are immutable data structures that replace mutable ones, where mutability is pushed off to a higher reference cell (so instead of having a mutable set, we have a mutable variable that points to a new immutable version of the set). In both cases, locking is required if thread safety is desired.

Why do you need a mutable variable? I thought we were discussing functional programming, in which case they should be rarely needed :)

If you want to keep track of world-current, then you need a variable that changes from world-0 to world-1 somewhere. Conceptual mutability (change over time) doesn't go away because you are using immutable data structures.

In functional programming one should model change over time as a stream of immutable values, there is no "conceptual mutability" and no need for mutable variables.

"Things that change over time" = mutable. It's in the dictionary even.

Mathematics has successfully modelled change over time for hundreds of years without mutable memory cells in a computer.

Please don't build software that mutates my data. I want history/provenance and reproducibility. I don't mind the odd bit of optimisation, but your use of the phrase "conceptual mutability" would have me worried if I was a customer of yours :)

I can give you all that with imperative mutation:

https://www.microsoft.com/en-us/research/publication/program...

Of course, I'm a researcher who deals with this field daily, I'm not going to be your ideologue functional programmer who meets your ideological criteria for twisted language with a poor understanding of the wider field.

Less of the insults please, I've spent most of my career trying to escape the 'wider field'. The way we choose to model the world is clearly very different.

> If you want to keep track of world-current, then you need a variable that changes from world-0 to world-1 somewhere.

Putting on my FP hat: if you need the state of the current world then somewhere you need a side-effect free function that can report that state. If you're managing that state over time then you'll need other functions to handle that stream of immutable data.

Conceptual mutability very often isn't a change of data, it's a change in usage/reporting context.

And since we're in FP land we could compose those input and handling functions together and splay them across infinite vectors in both directions creating infinite functional chains of potential data interactions that are only calculated on demand based on incoming data. We can be highly confident that those calculations will scale from 1 to 1 million CPUs/machines. We can be highly confident about state-based testing of future states (a la Y2K bug). We can formally verify system behaviour and the underlying data flow. We can also safely and logically match those flows to new and interesting transformations through exhaustive pattern matching with guarantees that we are not impacting the current system behaviour...

Granted: there are likely mutable variables somewhere in that turtle-stack, but the overall systems relationship to state will not be impugned by them as long as they are appropriately contained.

Because that's how you do inter thread communication in haskell.

https://hackage.haskell.org/package/base-4.10.0.0/docs/Contr...

>An MVar t is mutable location that is either empty or contains a value of type t.

>They can be used in multiple different ways:

>1. As synchronized mutable variables,

I did say they were rarely needed, if one does need interthread communication then yes an MVar or two will probably be used under the bonnet somewhere. Threads can however be used without MVars. Haskell offers many concurrency and parallel programming primitives.

Compare with C++ where every smartpointer holds mutable state (even if it points to a immutable value) and triggers a memory barrier whenever it is accessed.

You do not understand how immutable data structures work; you are thinking about them from the context of mutation when they are very much not based on that mode of change. They are entirely different ways to organize data, and the implementations are quite different from what you seem to think they are.

> so instead of having a mutable set, we have a mutable variable that points to a new immutable version of the set

This is not at all how functional data structures work. You're assuming that the data structures are the same as non-functional data structures, but merely without the ability to mutate them. That is not correct. Proper functional data structures are implemented completely differently.

One obvious exception to this is the Swift language, which is not really a functional programming language, and it does not have functional data structures. It uses copy-on-write which is somewhat similar to what you describe, but is not how functional programming languages do it.

Strongly disagree. You can do radically less copying when GC is available. Yes, the graph needs to be traced eventually, but we know how to make GC fairly fast, especially if we can afford more memory.

Nobody really does that and it has serious multi threading problems. All the tricks to avoid copying are fragile in some way.

I think you need to study how the BEAM VM works with immutable data and GC in order to revise your opinion a bit, here

Isn't Erlang single threaded (i.e. no shared memory between threads)?

IIRC there is a sort of database bolted onto the language where threads can stash data if they need to.

ETS, DETS, Mnesia are shared mutable state DB's included in the box

You really should read up on the implementation of FP data structures in languages like Clojure or Haskell before making statements like this. You sound silly. Clojure's immutable data structures are thread-safe, fast, and quite different than your apparent idea of what these kinds of data structures actually are.

A major benefit of immutable data is worry-free sharing, and it's how you make persistent data structures fast. You simply can't afford to copy the whole world on every update.

There are some performance implications with NUMA, but there aren't serious multi-threading problems with immutable structures. Immutability means there isn't anything to race with, as long as initial construction is retired properly before other threads see anything, which is a compiler / runtime implementation problem, not an end user programmer problem.

This is not true at all. That's the whole point of functional data structures: they prevent copying for doing work on immutable data.

If you need a writable version of the data a copy must be made.

Now, you might argue such needs ought not arise. In practice, due to resource constraints, however, they often do.

That is not how functional data structures work. Check out Okasaki's book "Purely functional data structures" if you want to know what we are talking about here. There is not a whole copy of data being made. They use structural sharing and there is almost never a need for the implementation to make a data copy. You can have a piece of data that "changes" as it passes through the data flow, but in reality very tiny changes are actually happening behind the scenes, even if the perception to the programmer is that large changes are happening.

I know what you're talking about. I simply disagree with you. Not about "purely functional data structures", but about implementation details and how computation occurs in actual practice, in the context of their use.

The reason you disagree about implementation details is because you do not understand the implementations.

> I've spent a small amount of time trying to convince people that FP is a byproduct of immutability and not much else.

I'm not sure that's true in general; although it seems to hold in FP languages and FP-style in imperative languages, where we have "function-like things" (functions/subroutines/methods/etc.), an implicit 'arrow of time' (a sequence of instructions, irreversible reduction rules, etc.), some notion of "values" which can be passed around, mechanisms for naming/referencing/substitution/etc. and other such "ambient" language features that we might not think about too much since they're present in most mainstream languages.

If we step back from this imperative(-like) mainstream though, we find things like Prolog, miniKanren, SQL, Joy, Pure, Maude, Eve, Church, Unlambda, etc. whose semantics are based on relational algebra, answer-set programming, probabilistic programming, theorem proving, term-rewriting, stack models, etc. If we consider mutable vs. immutable variants of these languages, I don't think we'd find that immutability gives rise to FP as a byproduct.

For example, relational languages don't have a construct corresponding to functions; they have relations, which are more general since they are many:many rather than many:one. They also don't distinguish between "inputs" and "outputs", which allows relations to be "run backwards" (e.g. using `plus(5, x, 8)` to perform subtraction, with the result `x = 3`); this muddies the 'arrow of time', allowing a single "reduction step" to expand an expression (and perform an arbitrary amount of search in the process!). Such things are perfectly immutable (AFAIK languages like miniKanren enforce immutability, in a similar way to Haskell), yet I wouldn't call them "functional programming".

Similarly, the idea of "values" (and therefore referential transparency) can become murky: do we mean that an expression always evaluate to the same object-level term, or that querying an expression always chooses from the same set of possible terms, or that sampling an expression always draws from the same distribution over terms?

I've come across this 'murkiness' in the real world via Haskell's popular QuickCheck library, which provides a `Gen` monad that violates the monad laws: when given the same random seed, functions which should be equal may return different values. Yet `Gen` is "morally" a monad, since the probability distribution of those functions across arbitrary seeds is equal: https://hackage.haskell.org/package/QuickCheck-2.10.0.1/docs...

From the point of view of "writing my language-X project in a more functional style", I think going after immutability captures most of the idea, assuming "language-X" is some popular imperative/FP language. From the point of view of "language-X is functional because...", I don't think immutability captures much of the essence of FP at all.