Swift and the Legacy of Functional Programming | Hacker News Reader

Swift and the Legacy of Functional Programming

realm.io

91 pointsckurose185 comments

I'm curious, does every else find this

    let persons = names
        .map(Person.init)
        .filter { $0.isValid }

easier to read than this?

    var persons: [Person] = []
    for name in names {
        let person = Person(name: name)
        if person.isValid {
            persons.append(person)
        }
    }

I understand and appreciate the value of compact code, but I find the first one harder to read. A lot of inferred/token based coding is harder for me to mentally parse.

  let persons = [ p | n <- names
                    , p <- peopleNamed n
                    , isValid p ]

is even better, if your programming language has comprehensions.

Eh, maybe for more complicated examples, but I think that comprehension is a lot more complicated than:

  filter isValid (map peopleNamed names)

Except that doesn't support multiple people with the same name.

Well I was basing mine on the original. If peopleNamed in fact returns a list, then I'm not really sure what it's doing to create that? (I assumed your example was Haskell, in which case I don't think it can do anything particularly useful)

In any case, all you'd need to add is something like concat.

its almost a wash in this case, but when you start having a very complicated flow, the first way becomes easier and easier in relation.

It also depends on the language obviously. In this example, the first example has special tokens for the filter. It doesn't have to be so.

The first is much more declarative. When everything in the language looks and acts like that, it's pretty easy to read.

When it's optional, well, sadness ensues.

I think part of the answer is that for many functional is a new hotness. The same thing happened with Scala (probably still does). With type inference and functional shortcuts, you can get a lot into one compact space. This is "impressive".

The other thing is that experience brings the ability to track what's going on. The formulation of the answer here is probably new to you. As you get use to this, or Streams for Java, or threading for Clojure, etc, you'll understand it by default.

If you learn Haskell or OCaml, you'll prefer the first snippet. I took a couple of MOOCs and blogged how I incorporated what I learned into my Swift:

https://h4labs.wordpress.com/2016/09/30/functional-swift-usi...

I think it depends what you're used to. I used to be a Scala programmer, then I moved to JS.

At the moment I'm working in Objective-C, and I literally just wrote a loop to filter an array and form a new array with the results like the one in the example - and god I wish there was an as straight-forward, easily understandable functional way in Obj-C to do it like in the Swift example.

I miss these 'nice' things - I don't need the fully functional Haskell package, but I like having some of the nice things Swift has, just because I got used to them and can actually write and read them better, and it is definitely more elegant!

It's ugly, but possible:

  NSArray *filteredArray = [array filteredArrayUsingPredicate:[NSPredicate predicateWithBlock:^BOOL(id object, NSDictionary *bindings) {
      return [object test];
  }]];

You mean something like:

    a  := #(1 2 3 4 5).
    Transcript show: (a printString); cr.
    b := a select: [:x | x \\ 2 == 0].
    Transcript show: (b printString); cr.

Sadly Objective-C isn't really Smalltalk.

I used to find the first example more difficult to read until I learned Haskell. Now I find it much more explicit about what's happening.

In the first example, because I know what "map" means, I know that `Person.init` is applied to each name. And then I know that only the valid `Person`s are returned by the `filter` call.

In the second example, I have to understanding the unique logic of the loop block to get to the same conclusion.

Yes, I find the first one easier to read. It might be me being weird, but I suspect you just haven't built up the instincts to read the first one more quickly. There's no "magic" or anything tricky going on here — it's just a normal use of map and filter. Even good and useful things can seem less readable before you're used to reading them.

I think if the second one is easier, you've more or less been taught to think like a microprocessor. That happens to most of us after a few years of writing imperative code. The more abstract functional approach is, however, conceptually simpler and more powerful at the same time. (For example, the first one is completely open to being performed in parallel.)

With a little experience, functional programming is quite straightforward. Practically everything comes down to map, filter, and fold, or whatever they're called in a given language.

I can't help thinking like a microprocessor. Even when mixing functional style into my code, my brain tries to get a grasp on how it's going to be processed.

So the first example looks to me like two loops (hopefully the compiler does a better job on that), while the second one is obviously one loop.

I am already trying to guess how a compiler would parallelize that...

The second one might be obviously a single loop, but it is not obvious that it is O(n) and depends on the implementation of "append". It also tells you nothing about how the memory gets accessed and I'm assuming here that the for loop works just as well over linked lists and over arrays. In other words your knowledge that this is a single loop can be very misleading when thinking of expected performance. Which is fine because we work with abstractions such that we don't have to think about such details all the time, because that's not doable.

The first example is simply more abstract. It might be a single loop in case the implementation is lazy, it might be two loops in case it is strict. However, look closer. Those filter and map operations can be applied to basically anything you want, including asynchronous / infinite streams.

Your second loop on the other hand would have a hard time being translated to anything else than something that works on finite lists and that builds a finite buffer and not doing anything else while doing this.

Or in other words, your knowledge about this manual loop is not transferable ;-)

Excuse my ignorance but why is the first one parallelizable but not the second?

They're both parallelizable, but the second one is harder to automatically parallelize.

There are guarantees about the way a map function works. It doesn't mutate its input, it only has access to one element at a time, you can't access the data structure you're building, etc.

All of these traits are true of the imperative version as well, but it's a lot harder to write a program which understands that. Meanwhile, you know that's how map and filter work, so it's trivially easy to know that those guarantees hold.

As a matter of fact loops that mutate state are not parallelizable because you can't analyze what they do in order to infer intent and thus some imposed ordering with which you could efficiently distribute the required work while at the same time guaranteeing correctness - solve that and you'd solve the Halting problem ;-)

Can't be done.

Well, you can't solve it in the general case. But parallelizing compilers can and have been written that perform a conservative analysis -- they can prove some subset of all parallelizable loops as parallelizable, and for the ones they can't prove as such, they err toward 'remain serialized'.

For a simple example, code that performs regular array-based accesses, where index computations are simple affine functions (a*i + b) of a single iteration variable 'i', is a case that's received a lot of attention. See e.g. Polly for LLVM.

In the first one, you are simply telling it to map and filter every element. Since you can do that to each element in an independent way and the code is more abstract, the map and filter can be done in parallel without you knowing (I'm not sure if would execute in parallel in Swift, I know that in java you can change the way it does it by using parallel streams).

But in the second example, you are telling it to iterate over each element, sequentially. Since you are telling step by step what needs to be done, it's not parallelizable unless you implement it to be so.

Put another way, the first example is about data flow. The required value is specified declaratively, in the form of an expression.

The second example is about control flow. The required behaviour is specified imperatively, in the form of a statements to be executed in a defined order, and the combined effect of those statements is to update the list until it has the required value.

In the second case, the programmer specifies more details explicitly. In this case, those extra details probably aren’t helping, but the optimiser still has to prove that transforming the control flow (for example, into a parallelised form) really will give the same observable behaviour. In the first case, the optimiser doesn’t have to prove the things the programmer never specified anyway, so it has more latitude in how it implements the underlying computation.

As a matter of fact, any implementation of the same algorithm has the same parallelizing possibilities. You just need a smart enough compiler.

But a "smart enough compiler" is what compiler people say when they are talking about their version of the abstract anthropogenic equivalent AI. The fact is that the first one is much easier to parallelize, so that real implementations actually do it, while the second one is not done on practice. And it's easier to parallelize because there are some extra guarantees on the signature of those functions that a for loop does not give.

Maybe we aren't speaking the same language, but I never mentioned parallelism in my text.

We could talk about why the first example could be parallelized of course, but that's not what I wanted to talk about and you missed the point ;-)

Actually, I responded to the wrong post. I meant to post my reply to svachalek.

> For example, the first one is completely open to being performed in parallel

So what do you actually have to do to make this actually run in parallel? Or do you truly get it automatically?

I don't think that will happen in Swift, but conceptually there's nothing that stops the compiler from doing it since you're not specifying the order that anything happens. Some Haskell compilers can automate parallelization of the equivalent code. But pragmatically speaking, you can convert code in this style to parallel code without changing the algorithm; for example various "map-reduce" servers are built around the idea of mapping and reducing, which are fundamental concepts of functional programming.

In contrast, in the imperative form, you are specifying how items are appended to a list, which means that any attempt to do it in parallel could change the order of the operations and therefore the order of the result. Sure, a sufficiently smart compiler could in theory figure out what "should" happen and see how to optimize it, but in practice today's smartest compilers can barely handle the functional case.

Don't know about Swift, but in Haskell you substitute parallel versions of map and filter that are guaranteed to mean the same thing.

Hence why "structure and interpretation of computer programs" is a very important read.

For me the problem with Haskel (and, by extension, Swift) is the syntax is very complicated. The example above is better taught through a functional language that has almost no syntax like a Lisp.

  (filter (fn[p] (p :valid?)) 
    (map (fn[n] (Person n) names))

Haskell's syntax isn't actually that complicated. There are some common functions with operator names that can be hard to read if you're not used to them, but those are library defined. The syntax itself is actually fairly simple.

And incidentally, this would probably be something like (EDIT: made example more realistic):

  filter personIsValid (map initPerson names)

in Haskell. Which looks much cleaner than the lisp to me.

That's because your code assumes those convenience functions exist while the parent's code writes out the anonymous functions.

The direct translation of yours' to Clojure would be:

    (filter valid-person? (map init-person names))

Meanwhile, the direct Haskell translation of the parent comment is:

    filter (\p -> isValid p) (map (\n -> Person n) names)

Huh? No, anyone who writes it in Haskell would not use those lambda abstractions. You would just use "filter isValid (map Person names)".

I'm assuming Person is a record constructor, is isValid here a field in that record or another function?

Haskell doesn't distinguish the two. If you define Person with named fields including isValid, you automatically get a function named isValid that returns that field, or you can write your own isValid function that examines the whole Person.

No one would ever write the latter, because (\p -> isValid p) is equivalent to isValid.

However you're right that the function names would probably be a little longer in practice, and I've edited my example to reflect that. (But they're not convenience functions, they just have longer names due to Haskell's more limited namespacing)

Not a Haskell expert, but maybe monomorphism restriction can require you to perform an eta abstraction. Just saying.

Except in these two brief examples, Haskell employs syntactic sugar with hidden semantics that nobody but an acolyte would understand (periods and two kinds of brackets mean what?). At least the Lisp scoping here is explicit and employs minimal abstruse sugar.

I'll admit Lisp's myriad nesting of brackets is not ideal either. But surely there are more elegant and intuitive notations for functional scoping than is seen here.

I'm not sure what you're talking about? My example contains no periods and only one kind of brackets? Did you reply to the wrong post?

Admittedly, it might be written with $ in practice, but that's a fairly simple idiom, and I tend to avoid it.

Lisp provides its own solution to the nesting of parentheses: if you're writing an expression which is too deep, you can invent an ideal syntax which more direclty expresses what you want to say. Then teach Lisp to understand that syntax. Then there is a myriad of parentheses in the macros which implement the syntax; elsewhere, there are fewer parentheses.

Very simple example: once upon a time, in the early 1960's, Lisp only had the COND operator. There was no IF. Programmers often had to make two-way decisions using COND, writing things like (COND (condition then-expr) (T else-expr)). Too many parentheses. So they came up with the IF macro allowing (IF condition then-expr else-expr). This simply expanded to the COND. Six parentheses are reduced to two.

Like most other programmers, Lisp programmers care about not writing mountains of distracting, irrelevant code that is hard to understand. That's why the backquote syntax was invented for instance. Before the backquote syntax, macros were difficult to write.

Say you wanted to transform the syntax (foo bar) into (let ((bar (whatever))) (do-something bar)).

You had to write a macro function which took the object (foo bar) as a single argument, analyzed it, and then constructed the output. Suppose we already have the BAR part of the (foo bar) from in a variable called SYM. Then we have to do something like:

   (list 'let (list (list sym '(whatever))) (list 'do-something bar))
   ;; I'm not going to bother to get this right

With the invention of the backquote, this could be rewritten like this:

   `(let ((,sym (whatever))) (do-something ,sym))

A nice template which looks like the output that we want, and indicates the places where we want to stick the variable BAR symbol, held in SYM.

Obviously, backquote templates have parentheses. But the notation itself isn't parentheses; it consists of the backtick syntax, and the commma operator for interpolating values. Also a ,@ operator for splicing lists. In some Lisp dialects, the backtick is transformed into a nested list object. For instance `(a b ,c) might turn into (quasiquote a b (unquote c)) "under the hood".

Lispers also invented destructuring: being able to write the macro with a kind of pattern match for the syntax, so that the elements of the to-be-transformed-form are pulled apart into separate variables.

Lisp is not a finished language. New ideas continue, and new surface syntax like the backquote is not off the table. Usually, Lisp programmers would, I think, prefer that such new syntax integrate into Lisp by not "disturbing" surrounding syntax by involving it in ambiguity. Something tidy and simple that has a big payoff is best.

Lisp programmers are not tone-deaf to notational advantages, and do not regard macros as the one and only way to reduce verbosity.

I'm conducting my own one-man research program into improving Lisp and have come up with some great new ideas.

I have a Lisp dialect which is quite ergonomic, leading to terse programs for everyday "data munging" tasks (and continuing to get better).

That you have to put parentheses around expressions does not make the syntax go away in Lisp. The 'has almost no syntax' is mostly a misconception. Syntax in Lisp is provided by special operators (LET, ...) and macros (DEFUN, ...).

Often people assume the relatively simple syntax for s-expressions is the syntax of the programming language Lisp. It isn't. Lisp syntax is defined on top of s-expression.

Other than the $0, yes I do. Easier to read and think about in respect to operations on a collection.

It's a matter of habit more than code readability.

Five years ago, I would have found the second form easier to read. These days, not only do I find the first form much clearer but I find the second one a bit smelly because it mutates data.

It's actually surprising how quickly you get used to the first form of code once the language you use supports it.

In this case, it's unfortunate that there's no, "will this name create a valid person object?" predicate. much much better to filter the names, then make the objects.

In this case, as long as append is O(1), i think the imperative version has a big benefit, it avoids building the name size list of persons. If you've got a billion names and 2 valid person objects, the imperative version is a big win. Of course that predicate i mentioned is the right way to go though.

I think the right way to do it is with a fold. But that's not built in, so hard to expect of novices.

I see what you're saying about mutation, i guess i have a higher tolerance for mutating stuff that you have the only reference to. I'm not really sure doing a += [validPerson] is much of a win. (but i think would be the right answer in a fold)

Most languages implement map and filter in terms of lazy sequences so they would not allocate an intermediate list (Scala is an exception but I believe you can request laziness).

hmm, i don't think lazyness is enough. for example, in the billion names example, let's say the first and last elements are valid. at the first step you'll wind up with something like

   validPerson : thunk

after n steps where n < 1e9

   validPerson : invalid : invalid : invalid : ... : thunk

then finally at n = 1e9

  validPerson : invalid : ... : validPerson

because the intermediate calculations still need to happen.

getting that first answer is cheap and quick. getting the second answer requires evaluating those billion - 1 thunks.

maybe you're thinking of list fusion? AFAIK, only haskell does that.

Perhaps i'm misunderstanding your point. But even then, lisp, scheme, smalltalk, python and perl don't implement map and filter in a lazy way. Of course, i'm thinking in terms of haskell lazy, perhaps, again, i'm misunderstanding and you mean something else.

In retrospect, i think i'll revise my opinion and say map.filter is probably a bigger code smell than referentially transparent mutation.

I understood from your comment that the imperative version "avoids building the name size list of persons" that you thought the declaritive version would construct an intermediate List[Person] the same size as the source list of names. Most modern languages (e.g. C#, F#, Clojure, Rust) implement map and filter using lazy sequences rather than eagerly constructing intermediate collections (admittedly I don't have much experience with the languages you list).

The use laziness will avoid the need to construct a large intermediate collection of Person instances. Obviously you'll need to iterate the entire source collection to find all valid Persons but the same applies to the imperative version. The lazy version composes better however and avoids extra work if some downstream caller only requires the first n valid Persons.

Oh! yes. Yes we're on the same page as far as laziness goes. The lazy version will only construct as much of the intermediate list as you need to get the next answer, and potentially the garbage collector can reclaim the parts of the intermediate list that have already gone past.

But, there's already a good clean functional composable answer to this kind of thing,

fold takes an operation (like map does) a list (like map does) and an accumulator for building up results, and it returns the resulting accumulator.

   foldl(op, names, acc){
       if(names.empty)
           return acc
       else
           foldl(op, names.tail, op(names.head, acc)
   }

so with tail recursion, you get no stack growth. (i mean head like the first element of names, and tail as everything else)

the op would look something like

   op(name, acc){
      let p = Person.init(name)
      if(p.isValid)
          return acc += [p]
      else
          return acc
      }

So fold trundles down the list of names, the op checks each name to see if it's good, and only adds the good names to the final list. whenever fold notices it's out of more names to try, it just returns whatever the current accumulator might be.

Map forces you to build the intermediate representation, which the imperative version avoids.

Even Java manages to get your example to work efficiently with map/filter. It's not rocket science. Just because some library designers screwed it up doesn't invalidate the whole concept.

but java provides collect. which is, like, the right way to do it.

I'm just sort of mystified that people are defending map.filter over filter.map (which isn't crazy, as name.isValidPerson isn't provided.) but, you know, fold is a thing.

> so they would not allocate an intermediate list

Not quite. Lazy sequences make it so that thinking about fusion/deforestation makes sense. This is an optimization the compiler can make. Naively, you still end up with as many allocations as before (just in a different order).

In Haskell, this sort of optimization is actually user-customizable using REWRITE RULES. And you get it for lists out of the box.

> In this case, it's unfortunate that there's no, "will this name create a valid person object?" predicate. much much better to filter the names, then make the objects.

No "object" is made if the name can't create a "valid person object", it'll return a stack-allocated null/nothing value. That pattern is also much better for concurrency issues.

> much much better to filter the names, then make the objects.

You're just duplicating the validation logic (or worse, the "objects creation" assumes it's given valid names and does no checks)

> You're just duplicating the validation logic (or worse, the "objects creation" assumes it's given valid names and does no checks)

I think the right way to do it is with a fold.

In Haskell you'd use `mapMaybe :: (a -> Maybe b) -> [a] -> [b]`[0], it's a combined map+filter+map specialised for Maybe (option types). Rust has Iterator::filter_map[1] which does more or less the same thing.

[0] http://hackage.haskell.org/package/base-4.9.0.0/docs/Data-Ma...

[1] https://doc.rust-lang.org/std/iter/trait.Iterator.html#metho...

Personally, I prefer the map/filter approach because people is now a let constant, but I work at a startup with people that don't come from a software development background that would have next to no idea what that line even means. So don't forget your code's target audience, I've personally had to back off some of the more functional styling in Swift just so I'm not the only one that can maintain our code base.

For that reason, I really wish Swift had list comprehensions, just because it's the first "slightly functional" exposure most non-developers get if they come from Python.

I don't think it's THAT difficult to learn to understand functional style programming. I like to think that I would consider trying to show my team mates the joys and positive aspects of functional programming before I just wrote them off, were I in your situation.

Practice will help make the former more readable.

It helps, for me, that I have more of a math background (academically) than CS (dual majors, but strongly preferred the math coursework).

For me, I see three ways to write, as an example, a summation:

  n
  Σ g(i)
  i=1

  vs.

  seq(1,n).map(g).sum() // or something similar

  vs.

  for(i = 1; i < n; i++)
    sum = g(i)

In my mind, the first is what I see, and is what shows up on paper. The second is what I want to write (and will in any language that lets me). The third is what I often have to write when a language requires that I be more explicit (like C).

Shouldn't that be += in the third example?

Yep. Another reason a simple 'sum' is nicer than what C gives us.

Or a reason to go back to checking all code I try to type in.

Or:

  (1...i).reduce(0) { $0 + g($1) }

There is a certain straightforwardness about the second format, because it is general and plain. But at the same time, it could be anything -- it's much harder to tell at a glance that a for loop is a filter than it is to tell that `filter` is a filter.

I definitely hear what you're saying. In this particular case I find the more succinct map/filter a little easier to grok, but as soon as you have a bunch more clauses with some flatMap() and reduce(), the "functional" way can get out of hand quickly. In simple cases, I prefer (Python's) list comprehensions. In more complex cases, I prefer the loop(s).

I find Python's list comprehensions mind-numbing in many simple cases, such as [x for x in xs if some_condition(x)] rather than just xs.filter(some_condition). We're repeating the variable name three times and zero of those times convey any useful information, and we don't find out until the very end of the line that the everything except "[", "]" and "some_condition" was ignorable.

And in cases where a data-deriving loop has so much going on directly in the loop body that it makes map/filter/reduce hard to read, there's very often some refactoring that would improve either version.

This is the one case where python's list comprehension syntax isn't so efficient. Don't worry about it - be consistent and use it nevertheless. It doesn't matter much.

In the cases where x gets also transformed or you do some unpacking the syntax is very efficient and easy to read: [f(y) for x, y in items if g(x)]. Basically it's a poor man's relations programming (think databases). It's brilliant. (And definitely easier to read and write than the Haskell list comprehension syntax).

In this particular case I find the more succinct map/filter a little easier to grok, but as soon as you have a bunch more clauses with some flatMap() and reduce(), the "functional" way can get out of hand quickly.

Funnily enough, I find exactly the opposite: for me, the functional style is significantly easier to work with when things get crazy. I think this is mostly because you tend to be composing recognisable patterns, which in turn means the only custom code you’re writing is the “interesting” parts, like deciding exactly which data to select or exactly how to combine each pair of elements. With lots of loops and conditionals and early exits, I also have to work out whether the code is really doing what it looks like or whether there are edge cases that work differently, and even the “what it looks like” part can wind up scattered across several places in the code that are some distance apart.

Some of the projects I work on do a lot of quite intricate manipulations of complicated data structures. Earlier incarnations were written in Python, but even there I found myself using a functional style for most of these situations as the code base grew in size and complexity. More recently, for various reasons including that one, I’ve been writing this sort of code in Haskell, a language designed for that programming style and therefore cleaner in both syntax and semantics. IMHO, it would be hard to overstate how much easier the newer code is both to write originally and to read, fix and extend later. Possibly the most striking thing is how much shorter the code is: the functional style combined with a language and libraries designed to support it really is remarkably expressive for data crunching work compared to the “longhand” form of writing out all of the loops and conditionals manually.

I often wish it was only the reading. That may be a matter of getting used to it and there may be pluses to the functional style. But when it comes to using a debugger loops seem to be so much more approachable.

With the map, you know, as soon as you see the map that you're making a new list based on an old list. With the for loop, you have to read and understand every single line of the for loop to understand what it's doing.

I find it easier to read with the exception of the anonymous variables. In scala, I would write

    val persons = names
        .map { name => Person(name = name) }
        .filter { person => person.isValid }

Dunno, it's fairly obvious what you're working with, being explicit doesn't buy that much (for me at any rate).

    val persons =
      names.map(Person.apply).
      filter(_.isValid)

For me it's neutral, except for one critical difference.

I've been shepherding a bunch of front end Javascript tests, and recently had to go through fixing a systemic problem with how we were handling multiple promises.

The broken code didn't look too different from your second example, but the same three people made the same mistake repeatedly, leading to tests that generated empty lists and thus didn't verify anything.

Now, I'm not claiming this is a good pattern of testing. Indeed in all of the straightforward cases I removed the array entirely, and with great relish (especially since it also sped up the tests dramatically). And there are obviously some gaps in their theory of testing that they didn't notice the problem until I pointed it out.

But it did illustrate to me again that there are (alarmingly) a lot of people struggling with basic data manipulation, and if your language supports anything like list comprehensions, I think you should probably get used to using them. It keeps those gaps out, and makes people decompose the problem instead of mashing together a block of conditional code that reads like a Choose Your Own Adventure.

    persons = [person for person in (Person(name) for name in names) if person.isValid()]

This is Python.

i've been struggling with python incomprehensions since time immemorial. map/filter are a breeze.

It's easy. The first bit:

    [person

tells you that you're getting a list of persons. That's the most important part. The rest is telling you how they're getting in that list.

It's almost like a select query in (pseudo) SQL.

    select person from people where person.isvalid = true

    [person for person in people if person.isvalid]

I don't see why either is more difficult. For the functional version, you just need understand the meaning map and filter, and for the imperative version, you need to understand the meaning of for loops and append.

No, but this shouldn't be taken as an indictment of FP general. I prefer

    persons = filter isValid (map init names)

to both. Swift just isn't really a functional language in any useful sense.

I find the first one to be far easier to read. You can basically just read it from top to bottom and know exactly what it does. "Take names, turn each one into a Person, keep the ones that are valid."

The second one takes a lot more work. First, I have to read through the code and recognize that this is a loop that accumulates values into a new array. Then I have to pick it apart and see exactly where the accumulation takes place, and how that value is derived. It's not hard by any means, but the first one is far more straightforward.

Is the first one two loops or one?

It depends. Using lazy data structures, transducers, or a number of other common tricks would turn it into one loop. Haskell, Clojure, Ruby, Scala, Swift, and many other languages make it pretty easy to do.

Two. These methods are not lazy by default. Of course, you have to know the language pretty well to know that, but I do. For anyone wondering, you can write names.lazy.map(...) to get lazy evaluation.

The real answer is that it doesn't matter. Just like for most code, the output assembly or machine code doesn't matter.

Naïvely, two. The compiler can probably figure out that the semantics are the same and choose depending on what its model says will be faster.

Pitching in with the sea of other voices: I prefer the first. Vastly.

In fact, while I still have issue reasoning about some aspects of functional programming when writing the code - it is magnitudes easier for me to read, maintain, modify, or extend the code.

I think the readability is a bit of a wash.

But the second one is more debuggable than the first, which I think is even more important than readability.

In the first case, you need to rewrite the control structure to even be able to inspect anything:

    let allPersons = names.map(Person.init)
    {log allPersons[0].name}
    {breakpoint}
    let persons = allPersons.filter { $0.isValid }

There are lots of data structures in this style of programming that don't have any names. Who knows what kind of data structures map and filter create in order to do their work. Are we allocating 2 arrays? 1? None? In the procedural style, everything that exists in memory has a name.

It's also totally unclear what the order of operations is. Are Person.init and $0.isValid alternated? Is the `map` run in full before the `filter` starts? No way to know.

People talk shit about procedural programming, as if it's antiquated. But the core promise of functional programming—that you can stop thinking about the underlying procedures—never seems to fully pan out. So when you inevitably need to start digging under the hood to figure out what your declarative code actually means in practice, you end up having to think procedurally anyway. Now you're thinking procedurally, but your code is declarative, and the runtime is trying as hard as it can to prevent you from knowing what's exactly happening moment to moment.

I think there are specific cases where a declarative interface is the right abstraction. CSS is a good example. But these are narrowly defined domains with relatively clear semantics that get frequent use, so the time it takes to learn the semantics will pay off.

The idea of littering your entire codebase thickly with declarative APIs, each of which has unique control structures that must be understood in order to read code, is not a good approach in my opinion.

This is what Rails is, and it creates a situation where you are captive to your tools: you can do a lot very easily, but you cannot stray far beyond the declarations that your library author overlords have chosen for you, or you quickly find yourself in a space where in order to not shoot yourself in the foot you need to have a huge body of internals in your head.

> But the second one is more debuggable than the first, which I think is even more important than readability.

The first is less likely to require debugging in the first place.

> There are lots of data structures in this style of programming that don't have any names.

So you can only reason about things that have names? Now we know where idiomatic Java comes from.

> Who knows what kind of data structures map and filter create in order to do their work.

In most reasonable implementations, the only data structure being created is the final result (a functorial value in map's case, a sequence in filter's case). For example, in SML:

    fun map _ nil = nil
      | map f (x :: xs) = f x :: map f xs

    fun filter _ nil = nil
      | filter p (x :: xs) =
        if p x then x :: filter p xs
        else filter p xs

> But the core promise of functional programming—that you can stop thinking about the underlying procedures—never seems to fully pan out.

Functional programming doesn't promise freedom from procedures. It promises (and delivers) freedom from physical object identities when you only care about logical values.

---

@banachtarski:

Code that's likely to require debugging (say, because it implements tricky algorithms) should be isolated from the rest anyway, regardless of whether your program is written in a functional style or not. Say, in Haskell:

Bad:

    filter (\x -> tricky_logic_1) $
    map    (\x -> tricky_logic_2) $ xs

Good:

    -- Now trickyFunction1 and trickyFunction2 can be
    -- tested in isolation. Or whatever.
    trickyFunction1 x = ...
    trickyFunction2 x = ...
    
    filter trickyFunction1 (map trickyFunction2 xs)

> The first is less likely to require debugging in the first place.

I'm all for functional languages but this scares me a bit. What do you do when you need to debug something and everything ends up being harder to debug but "less likely to need debugging." I've actually run into this situation a number of times and faced with a sea of linked compound expressions, debugging can be a daunting proposition.

Comment out all but the first and output the result. If it's what you expected, uncomment next line and output the result. Is it what you expected. Repeat... Debugging is just a specialized form of troubleshooting so the same rules apply. Bring the system to a known good, and increase until you find where it breaks.

You have a ton of these types of statements. Which one do you apply the treatment too? Your approach only allows doing this troubleshooting approach to a single place at a time easily.

How do you debug several places at the same time?

You have a ton of those statements, that's why you organize them in functions, and go debugging high level functions before you go into lower level ones, and then into atomic statements.

Anyway, you'll almost certainly want to do that in an repl. I don't know if swift supports one, if not that would be a real drawback.

They do, it's really slick how well they have it integrated.

It's still a net win in my experience. The minor inconvenience of inserting a few temporary variables to hold intermediate values is much less than the burden of all the additional reading and debugging needed when you spell out every step for everything you want to do.

It's kind of strange to me. We generally acknowledge that not repeating yourself and dividing responsibilities sensibly leads to better code that has fewer bugs and is easier to reason about. And yet when we consider doing the same thing with iteration, we say, "Whoa, hang on. Why can't we just write out the whole thing every time instead of factoring the common bits into a function?"

> So you can only reason about things that have names?

I think the point was that you can debug things that have names because they are separately watchable.

But apart from that breaking things down and naming them can make for easier comprehension. This is true in written English: Naming actors when explaining something and using an active voice is generally recommended. e.g "The user enters a password and the program encrypts it and stores it in the database" Rather than: "Passwords will be stored encrypted"

But also in mathematics. When working something out it's better to name intermediate values (x,y) and then use them in new equations rather than use the equivalent of a point free style that you sometimes see in functional programs.

> I think the point was that you can debug things that have names because they are separately watchable.

Note I said “reason”, not “debug”. When manipulating algebraic expressions, I don't need to give every subexpression a name - that would be torture!

You're 100% right about debugability. It's the main reason I don't push to use haskell every day. That said, I think we really need to get clever and think of good tools to debug in spite of these difficulties. Most complex bugs are from interacting systems that can't be found by step debugging. For example, the following code is considered pythonic, and for good reason:

    fs = [f(x) for x in xs]

The other commenter's points about being cleaner and less prone to debugging are totally legit. If we can make e.g. list/set comprehensions debuggable, we can probably make other FP idioms debuggable and get the best of both worlds.

Kinda reminds me of microservices, actually. Tough to debug, but good in other ways.

I find it easier to read but I'd struggle to come up with it myself from zero

I find the first example much more intuitive. It declares intent, rather than the mechanics of delivery. And that's where we need to be heading as programmers.

This. So much. Declaring intent (what) is much more useful than declaring the mechanics (how). I don't typically care about the "how", just the "what". And the more readable that is, the better.

And the source code comments are the why.

In Python, the only good language, this could be expressed as:

    [person for person in (Person(name) for name in names) if person.isValid()]

or:

    filter(lambda p: p.isValid, map(Person, names))

or:

    persons = []
    for name in names:
        person = Person(name)
        if person.isValid():
            persons.append(person)

So much for "There's Only One Way To Do It". :)

That is long gone, specially regarding string formatting.

In fairness, the list comprehension would probably be the most "Pythonic" way to do this. The nested iterator might be discouraged (under "explicit is better than implicit," perhaps), so a more Pythonic snippet might look like:

    persons = [Person(name) for name in names]
    valid_persons = [person for person in persons if person.isValid()]

Take this all with a grain of salt, though -- I haven't spent that much time internalizing classical Pythonicness.

I find it much easier. It might be a question of getting used to it.

I found the first one easier to read up until I got to the lambda syntax. Map and Filter are intuitive to me, but I wasn't at all clear what { $0.isValid } was doing.

Coming from ruby and using a lot of maps and functional constructs I personally think the first one is way easier to read.

Me too. The first one is harder to read, and also the first one is harder to extend if the business rules change.

Yo, would be nice to have some functional programming language with decent syntax to program apple machines. Let's call it Dylan to honor the most recent winner of the Nobel prize for literature.

Just kidding. The bottomline of this page and talk is that Swift is still not functional. But you can do cool things with it.

I dunno; I think the bottom line of this page is that functional programming is a set of approaches for solving problems, and some of those approaches can be done in Swift.

Haven't read the article yet, but the problem I find with this attitude generally is that the constraints found in FP are what I find valuable, and what are usually missing from languages which support functional approaches.

Well said. I can write exceedingly low defect code without folds. I can't do so with implicit IO everywhere, ad hoc polymorphism, and dynamic typing.

My take was that you can solve problems by breaking things down. In functional programming you do so with functions. In Swift you can do so with types.

https://en.wikipedia.org/wiki/Dylan_(programming_language)

(for those who didn't get the joke... ;-)

Ask five programmers to define functional programming, get fifteen different answers.

Same thing can be said for object-oriented programming, unfortunately.

Most people would agree that in functional programming we can pass functions around as first class objects. What we disagree on is the definition of function.

That's just one aspect of functional programming. By that definition, almost any modern language is functional.

Every modern language is functional. :P But more accurately, every modern language is generally multi-paradigm.

Take it from the other side: why would a language that allows to create higher-order functions/closures not be called functional?

Because that makes the term meaningless. You may as well ask "why don't we call any language that lets you do two actions in sequence 'procedural'?"

A term does not necessarily become meaningless when it applies to a lot of things. "Functional" might be a broad category after all, not the exclusive name of a subset of functional languages. And if your language allows different paradigms, it will be called "functional and imperative and object-oriented... ". At best, if a property is so common that most language have it, it can be assumed to be satisfied by default. As for "procedural", the definition on wikipedia is a little more precise and does not apply to all languages: https://en.wikipedia.org/wiki/Procedural_programming.

That doesn't make the term meaningless, it just means that "functional programming" is a victim of its own success.

If you can apply the term to every programming language in widespread use today[1], then yes, it is pretty useless. There is real value in having the term "functional programming" be meaningful and denote a certain class of languages; defining that as "any language with first-class function values" is too broad as to render the term meaningless.

[1] Even C has this with Apple's Blocks extension (http://clang.llvm.org/docs/Block-ABI-Apple.html).

Most languages only have higher-order procedures, not higher-order functions.

As for closures, well, closures are an implementation technique. Not distinguishing between language features and implementation techniques is a part of an established tradition that comes from Lisp, but that doesn't make it any less wrong.

> Most languages only have higher-order procedures, not higher-order functions.

What do you mean by that?

Functions have the following properties:

(0) A function maps every element of its domain to a unique element of its codomain.

(1) Functions don't exist in time, let alone change over time.

(2) Two functions with the same domain and codomain are equal if they map the same domain elements to the same codomain elements.

Since when do so-called “first-class functions” in most programming languages behave like this?

No, wrong. You can pass pointers to functions in C.

It is a bit snarky, but also has a ground truth: pointers to functions aren't functions.

More importantly, you cannot make functions in C. For example, one cannot write a function that, given pointers to functions that compute 1/x and sin(x), returns a pointer to a function that returns 1/sin(x)

That's not a function, that's a closure. And you can simulate that in C by creating a struct that contains the function pointer and the set of captured data (and then when you invoke the function you pass the struct to it as a parameter).

Yes, hence the distinction between first-class features and others, which you have to implement yourself.

The parent comment said C function pointers aren't functions. They are. They just aren't closures.

I always thought FP == pure functions. I guess not?

I would call a language like Haskell "purely functional" and a language like OCaml "impurely functional". A functional programming language to me is a programming language where functions are in charge of data. In a language like Java, data is in charge of functions (broadly speaking). In a language like Prolog, relations are in charge of data. It's all about what perspective the programmer has between the abstraction and the data.

You have it backwards. In Java, collections of procedures (aka objects) are in charge of data. In Haskell and OCaml, data exists independently of the procedures that will operate on it.

If they are truly functional programmers, asking them will always return the same referentially transparent answer. Only side-effecting functions would return different answers at different times :-)

Seems to me that's because functional programming continues to evolve (which is great!) and newfangled properties and semantics get folded in.

To me the core is "no side effects" though (for pure FP). It's interesting to see what others consider to be the most salient feature(s).

and if it was about OOP, you'd get a hierarchy of answers that no one can follow and is unsound ;)

It is the programming style I learned to program in Lisp and Caml Light, and when Haskell was still known as Mirada.

The author of this article did reference a classic treatment, though: John Backus's lecture.

A compact definition of functional programming is using only expressions, never statements. This leads to the idea that the effect or meaning of every computation must be encoded in its return value.

The term "functional programming" is overloaded, but I think there's a sensible way to split the term into two halves.

"Purely functional programming" is writing programs to resemble mathematical functions, with referential transparency and absence of side-effects and so forth. Also know as "what Haskell does."

"Function-oriented programming" is writing programs using functions as your main tool for abstraction, encapsulation, defining interfaces, unit of code division, etc. This part of functional programming is more typified by the Lisp family.

Most languages that are considered functional generally encourage both of these aspects, partly because they work well together. The confusion over definition comes from these two halves getting tangled, and some languages or programmers emphasizing one half over the other.

Non-functional languages that are becoming "more functional" are generally importing features from the "function-oriented" side of things, and adopting the "purely functional" aspect as a best practice convention, if at all. It's probably more accurate to say that they enable a functional style of programming, rather than that the are functional.

Actually, both of those families come from lambda calculus, except in different way. Lisp comes from untyped lambda calculus (and adds things like car, cdr and eq on top of it), while Haskell (and ML) comes primarily from typed lambda calculus.

I offer a definition of "functional programming" as "based on semantics of lambda calculus".

Here are some features that the lambda calculus doesn't have: n-ary functions for n other than 1, macros (or any other means to analyze its own syntax), dynamically scoped variables, physical object identities, etc. In the untyped lambda calculus, any two alpha-equivalent terms are internally indistinguishable - in fact, you can even make them externally indistinguishable using a nameless representation of syntax like “de Bruijn indices”.

So much for “Lisp comes from [the] untyped lambda calculus”.

Lisp does not come from lambda calculus. Anonymous functions in Lisp get their LAMBDA name from lambda calculus, that's all. MacCarthy admitted that he didn't even understand lambda calculus properly, which is why early Lisp was dynamically scoped: lambdas didn't capture lexical variables. Whereas lambda calculus is lexical. Lexical scoping was adopted in later Lisp dialects and into Common Lisp, making those dialects retroactively related to lambda calculus. (Emacs Lisp shows the traditional behavior of dynamic scoping; therefore it couldn't be said to be related to lambda calculus.)

Lambda calculus is a formalization of number theory which builds up numbers from functions. An important result is that lambda calculus is Turing complete. It shows that we can boostrap numbers and number theory from almost out of nothing, using Church numerals.

Lisp has never built numbers out of Church numerals; it had ordinary integers.

Also, lambda calculus, typed or not, does not have its own syntax as a data type. It doesn't have symbols. You don't quote a symbol and pass it to a function and so on.

So that's basically it; there is a link between Lisp and lambda calculus due to the use of the word lambda in a related way, and a somewhat stronger link between lexically scoped Lisps (which came later) and lambda calculus.

I guess you're right, it doesn't come so much from lambda calculus as I claimed, it was more inspired by it. Although to be fair, in the time the Lisp appeared, it was the closest thing (by a wide margin) to lambda calculus. I think it was a valiant effort to bridge the gap in that direction (and the design choices were influenced by the trade off that he also wanted a practical programming language).

Also, even languages like Haskell are not based only on theoretical lambda calculus, but they also have primitives for data types, which could be, in theory, represented by lambda expressions.

Your "function-oriented programming" has an older and more suitable term: https://en.wikipedia.org/wiki/Procedural_programming

You see, if a function isn't pure, then it isn't a (mathematical) function. But we tend to overload terms because of their marketability.

In the same way that some companies wanted to overload "open source". The general rule of thumb is that if something is desirable by the market, then it is going to get overloaded either by people not knowing what they are talking about or by sales people.

Procedural programming usually does not include the use of higher-order functions, and "function-oriented" here seems proper for Lisp and some styles of Python, with their heavy use of filter/map/apply/parallel-map-reduce etc.

In mathematics a function is a mapping having the property that each input is related to exactly one output. This brings with it certain properties you can rely on. In particular functions themselves are also values that can be passed around as parameters or returned by other functions, hence higher order functions.

It's regrettable that we overloaded the word "function", given we could have used procedures or subroutines to denote, you know, jumps in code that trigger effects and push/pop the call stack.

And as proof, applying filter/map and other similar operations with side-effecting procedures is a really, really bad idea, because such operators are usually implemented with lazy behavior (in order for "fusion" to happen) and laziness doesn't blend well with side effects, with the result becoming non-deterministic. E.g. at least people that worked with Map-Reduce frameworks should know what I'm talking about.

Or in other words, there is no such thing as "function-oriented", there's just local application of FP where it seems to be making sense, but with all the caveats that entails.

There's only one definition that matters: functional programming is programming with mathematical (pure) functions.

As a consequence you get referential transparency and thus equational reasoning. But change this definition and the term becomes meaningless.

Though by this definition, Lisp, the granddaddy of functional programming languages, is not a functional programming language.

It indeed isn't. Here's my litmus test. Is 2^100 always equal to 2^100? Let's ask SBCL:

    * (eq (expt 2 100) (expt 2 100))
    
    NIL

Damn object identities, ruining muh equalities.

(Disclaimer: I'm not saying functional programming is the right approach for writing every program, but if a language can't even get arithmetic and relational operators right...)

Structural equivalence is given by EQUALP and has of course its own limitations (but works with trees, user-defined structs and hash-tables, for example). Of course, if you use the identity comparison, you get different results. I agree CL does not fit your definition of functional programming.

An implementation is permitted to make "copies" of characters and numbers at any time. The effect is that Common Lisp makes no guarantee that eq is true even when both its arguments are "the same thing" if that thing is a character or number.

http://www.lispworks.com/documentation/lw51/CLHS/Body/f_eq.h...

I'm aware of EQUALP. But the problem remains that it's possible to distinguish between supposedly “equal” values. Lisp and Scala are first and foremost object-oriented languages - whatever values you want to manipulate are always subordinate to objects whose physical identity in memory matters in the language's semantics, no matter how irrelevant they might be for your problem domain.

On the other hand, in Haskell and ML, due to their superior value-oriented design, there's no way to distinguish between “this 123456789” and “that 123456789”, or between “this list [1,2,3]” and “that list [1,2,3]”. There is only one number 123456789 and one one list [1,2,3] in the language's semantics, no matter how many copies of their representation might exist in memory.

I am also aware of that. I am not really trying to convince you of anything, mostly trying to prevent casual readers from being taught Common Lisp from you. Look at the example you just gave, this is beyond ridiculous. I would prefer if you were focusing on what you want to fight "for", not what you want to fight "against".

You like having a strong separation between the language and its implementation. I get it. Note however that if you are the Haskell compiler, you can know things the programmer cannot, or you can inject code that can perform manipulations the programmer cannot express. There probably is an identity equality operator down there, that people cannot access. If you like that, I can understand; I can understand the appeal for a strict separation of concerns and the desire to express only the high-level intent. But really, I think this is not much different in CL and that you are focusing on implementation details. In CL the separation is not enforced, and that is your main problem with it.

The CL compiler is defined at the language specification level. You have access to internals, by choice, just as if you were writing Haskell ASTs using an Haskell compiler's internal API. As such, you can cross abstraction barriers whenever you need. We already discussed about this once, you can use purely functional data-structures (see FSET) and EQUALP and code to that functional interface and pretend there is no computer down there. Then, if you want, you can play with packages and symbols to make MAP & co. refer to the parallel version (see LPARALLEL), re-compile and have parallel code (this works best with unqualified symbols and different package definitions for the same file).

In all PL discussions, there is eventually mention of an hypothetical sufficiently smart compiler. The CL point of view is (among other things) that such a compiler is one where a programmer can easily add its own extensions. That allows you to express the intent of the program clearly in one place and have the implementation details elsewhere.

> Note however that if you are the Haskell compiler, you can know things the programmer cannot, or you can inject code that can perform manipulations the programmer cannot express.

Those would be implementation details, not part of the language itself. Hence...

> There probably is an identity equality operator down there, that people cannot access.

... this doesn't make sense.

> You have access to internals, by choice, just as if you were writing Haskell ASTs using an Haskell compiler's internal API.

However, there's no way to portably manipulate compiler internals in Haskell. Heck, Haskell syntax, unlike Lisp syntax, can actually be represented in multiple ways: named variables, de Bruijn indices and levels, HOAS, etc. And this is a good thing.

> In all PL discussions, there is eventually mention of an hypothetical sufficiently smart compiler.

I wouldn't have brought it up myself.

> The CL point of view is (among other things) that such a compiler is one where a programmer can easily add its own extensions.

There's no dichotomy between extensibility and abstraction enforcement, even if you try to set up one.

> ... this doesn't make sense.

In order to have an ML, you take a subset of Common Lisp and specialize/extend it in a very specific direction. The part that are removed from Lisp are the one you don't care about. I care about being able to use different equivalence classes, including the ones the compiler is going to require, like identity equality, because this matters when I implement abstractions myself.

> However, there's no way to portably manipulate compiler internals in Haskell.

Yes, why not, that would be damn useful. The alternative is to hack each implementation in its own way.

> Heck, Haskell syntax, unlike Lisp syntax, can actually be represented in multiple ways: [...]

Do you get the difference between internal and external representations? When you see (lambda (a) (+ a 1)), you don't know how the code is represented internally and how its value, when executed, is represented internally (when my compiler performs data-flow analysis, it uses a specific internal representation I don't need to know). Yet, you have access to a uniform API, defined at the language level, to manipulate data. That's why you can have the same source code working on the JVM, interpreted using a C/C++ runtime or directly expressed as assembly. In that sense, there is a separation between the language and its implementation. But part of the language specification is also there to guarantee a uniform way of building new extensions and integrate them with the compiler. That is a good thing. What is not enforced is how and when each feature is used. If that matters, dump a specialized Lisp image that you call the "compiler" and call it with Make on a file expressed in your custom DSL.

> There's no dichotomy between extensibility and abstraction enforcement, even if you try to set up one.

I am not trying to set up one. Just read more carefully.

> Do you get the difference between internal and external representations? When you see (lambda (a) (+ a 1)), you don't know how the code is represented internally and how its value, when executed [emphasis mine], is represented internally

I'm not talking about representations of semantic objects. I'm talking about representations of syntax. In Lisp's case, you don't get to choose - the macro system critically depends on a particular representation (named variables). Have fun writing macros that operate on HOAS.

> In Lisp's case, you don't get to choose - the macro system critically depends on a particular representation (named variables)

Please tell me how Haskell represents HOAS and how this is not possible in Lisp.

Also, read Barzilay's paper (http://scheme2006.cs.uchicago.edu/15-barzilay.pdf), or about the Ergo Project (1988! http://repository.cmu.edu/cgi/viewcontent.cgi?article=2763&c...).

> Please tell me how Haskell represents HOAS and how this is not possible in Lisp.

I'm not talking about representing some object language's syntax in Haskell or Lisp. I'm talking about representing Haskell or Lisp's syntax in some other metalanguage (possibly Haskell or Lisp itself). How would you implement a macro expander that operates on HOAS?

> Barzilay's paper (http://scheme2006.cs.uchicago.edu/15-barzilay.pdf)

The object language implemented in that paper isn't the whole of Scheme, and in particular, it doesn't have macros.

> Ergo Project (1988! http://repository.cmu.edu/cgi/viewcontent.cgi?article=2763&c...)

Sorry, I can't find an explicit description of any object language's syntax in this paper.

> How would you implement a macro expander that operates on HOAS?

Hmm, you would expect that HOAS actually be helpful in this area in some ways. Since variables are no longer resolved by matching symbols to binding information in a scoped environment (all we have is direct names references to the binding inserted in the code, or something like that), we don't have hygiene issues when we move code around without having to do any alpha-renaming, or gensyms. It sounds rather convenient, unless we expressly want to do something non-hygienic.

So how would we implement a macro expander? Like we implement anything else: in whatever way that implementation satisfies the specification of macros under HOAS. What is the specification: that is the question. What are HOAS macros, or macros under HOAS?

Not having a formal specification, we might want at least some examples: OK, I have this HOAS artifact, and would like to be able to write it in a more condensed way using this other HOAS: now how to make one into the other? That gives us a function, where we can identify the inputs, which have to be arguments to the macro somehow and so it goes.

Some kind of dual macro system could be useful: a raw source code macro system for doing un-hygienic things, and then a parallel one which kicks in when the code is converted to HOAS.

> It sounds rather convenient, unless we expressly want to do something non-hygienic.

Agreed. I wouldn't want to do anything non-hygienic, but, from what I can tell, most other macro users aren't exactly very fond of everything being strictly hygienic. It's precisely implementing the unhygienic bits that would be unreasonably hard with HOAS.

In what language do we input code as HOAS, and target that representation with macros?

(Can't we expand macros in a conventional representation with symbols and environments and then go to HOAS?)

(It's not news that macros are weak in some sense; I mean you can shoot yourself in the foot with the classic non-hygienic ones; you can disrespect even the first order abstract syntax that you're working in: the macro can re-locate a piece of raw syntax which contains identifier references into the wrong scope where those references resolve otherwise.)

Anyway, have fun fishing for mackerel with your bear trap?

The “conventional” representation of syntax using explicitly named variables is utterly inconvenient and error-prone for anything other than parsing. The very first thing I want to do after parsing is convert the syntax tree to de Bruijn indices/levels or HOAS.

You could expand some conventional macros first, then go to HOAS with what is left (and then do another pass with a separate HOAS macro system, perhaps).

How the heck do you handle hierarchical run-time environments in these representations? Especially mutable ones? If we have this:

  (let (a b c)
     (let (d e f)
        (lambda ())) ;; escapes somehow
     (let (g h i)
       (lambda ()))) ;; ditto
     (lambda ())) ;; ditto

These lambdas capture different, overlapping environments which share the (a b c) bindings. If there is an inner loop which repeatedly instantiates the (d e f), then new closures are made with different instances of these variables: yet those closures all share the same (a b c) bindings.

So we can't just flatten the entire lexical scope to some HOAS terms and pretend that its hierarchical structure doesn't exist.

Mutable shared environments is an absolutely terrible idea. All this achieves is to gratuitously make it unsafe to call in parallel multiple closures created in the same environment. A saner approach is to let variable bindings be immutable, and only then let some variables have (not necessarily static) type “mutable cell” (something like Rust's `Rc` or `Arc`).

Even if environments are immutable, the problem has to be solved somehow that the environments are hierarchical. Newly instantiated versions of a sub-environment share the same super-environment. For instance, a local tail call occurring in the scope of some stable outer bindings, capturing different versions of the tail call inner variables.

I fail to understand why hierarchical environments pose a problem for HOAS. Environments map variables to their values, and they're used to give meaning to non-closed terms (containing variables that aren't bound within the term itself).

The whole point to HOAS is making unbound variables irrepresentable in the first place (which is the source of the accidental variable capture problem), eliminating the need for environments as separate data structures. For example, this is the HOAS representation of closed terms of the untyped lambda calculus:

    datatype term = Lam of term -> term
                  | App of term * term

Note there is no need for a separate constructor for free variables.

In Lisp, symbols are very important. And symbols are identity. An identity with other dressing, such as having a character string name which is somewhat of a semantic footnote.

"Functional programming" doesn't restrict the kinds of obejcts you can work with. An identity value, whose virtue is that it is different from other identities, is a legitimate concept which can be treated under functional programming.

I guess your problem is that you don't want non-symbolic objects from behaving like identities; only symbolic ones.

That is to say, two symbols are equal iff they are actually the same symbol, otherwise not---but other kinds of entities are treated differently.

There is something to be said for having just one kind of equality, which is appropriately defined for every kind of object.

Pragmatic issues get in the way though.

Let's consider "this list [1,2,3]" versus "that list [1,2,3]". What if we have lazy lists (as those things tend to crop up in functional languages, particularly non-strictly evaluated ones). Is "this infinite list [1,2,3, ...]" equal to "that infinite list [1,2,3,...]" even if they are generated by completely separate lazy procedures?

Your equality then has to basically test that two Turing computations are equivalent: that the underlying lazy generation procedures themselves are computing the same thing, even if in different ways.

In that vein, what do you do about structures with cycles and shared structure? Is the list #1=(1 . #1#) equal to another one that is also #1=(1 . #1#). (Lisp's equal functions don't have to handle this; but we could specify an equal function which does).

Equality is not so simple that we can just cover all of its nuances with a blanket rule based on some handwaving principle.

> An identity value, whose virtue is that it is different from other identities, is a legitimate concept which can be treated under functional programming.

Of course. But I don't want object identities to be the only values I can manipulate. I like having values like the list [1,2,3].

> Your equality then has to basically test that two Turing computations are equivalent: that the underlying lazy generation procedures themselves are computing the same thing, even if in different ways.

Indeed, this means that equality of higher-order values is undecidable. Therefore, don't rely on testing whether higher-order values are equal - you just can't! This is also why laziness by default is such a bad idea.

> In that vein, what do you do about structures with cycles and shared structure?

In Standard ML, `val rec xs = 1 :: xs` simply doesn't compile. The right-hand side of a `val rec` definition must be a function literal. This guarantees that inductive data types (such as lists and trees) mean the right thing, and that structural recursion on them always terminates.

> Equality is not so simple that we can just cover all of its nuances with a blanket rule based on some handwaving principle.

I'm not handwaving anything.

I don't see how support for multiple equalities makes something not a functional language.

Functional doesn't mean "the semantics of everything is tied to its printed syntax" so that if two things look the same in the syntax, they denote the same thing. (Right?)

Suppose we take Haskell and give it an equal operator which can tell that two bignums are different instances and not equal. Does it cease being functional? What if we don't use that operator anywhere in a program and don't even know it exists; how do we know the language is not functional?

> Functional doesn't mean "the semantics of everything is tied to its printed syntax" so that if two things look the same in the syntax, they denote the same thing. (Right?)

I don't care about syntax. I want to manipulate the values I care about, not object identities. I want to operate on numbers, strings, lists, trees, what have you. Not memory cells that allegedly contain representations of numbers, strings, lists, trees, what have you. This is strictly a semantic issue.

> I don't see how support for multiple equalities makes something not a functional language.

FWIW, what most languages call “physical” or “reference equality” is a special case of structural equality (which is always the prior notion). Structural equality of mutable cells (which have dedicated types in Haskell and ML) happens to be physical equality.

> Suppose we take Haskell and give it an equal operator which can tell that two bignums are different instances and not equal. Does it cease being functional?

Yes.

> What if we don't use that operator anywhere in a program and don't even know it exists; how do we know the language is not functional?

Then you're doing functional programming in a non-functional language.

> What if we don't use that operator anywhere in a program and don't even know it exists; how do we know the language is not functional?

;-)

If a tree falls in a forest and no one is around to hear it, does it make a sound?

If a program satisfies a property but the compiler cannot prove it, can we still rely on it?

> If a program satisfies a property but the compiler cannot prove it, can we still rely on it?

It's very simple: You can rely on what you can prove. This applies both to compiler authors and compiler users. That sometimes one can prove things the other can't shouldn't come off as a surprise. Neither party has all the information: The compiler author doesn't know the intended meaning of the program submitted to the compiler by the user. The user doesn't (need to) know the internal details of how the compiler works.

Well, I would just use EQL.

If you want to use Haskell, use Haskell. Common Lisp works differently.

I don't even like Haskell, so, no, thanks. I was just arguing that Common Lisp isn't a functional language.

Well, that's not news.

The original LISP was influenced by Alonzo Church's lambda calculus, see: https://dl.acm.org/citation.cfm?id=367199 - however if you'll study its history the first Lisps were only experiments and for example they didn't have lexical scoping, but dynamic scoping. The Lisp descendant that made FP doable was Scheme, bringing lexical scoping and call/cc.

And today's Common Lisp is definitely not Scheme, or an FP language. You can do FP in CLisp of course, since it's quite capable, but CLisp is a general purpose language and is used as such. And in my small experience from playing with it, there isn't much FP in CLisp, but YMMV.

Lisp in general is a big family. Emacs Lisp for example has absolutely nothing to do with FP.

Of course you can romanticize about Lisp and it definitely has some cool descendants like Clojure, but you know, don't do it too much :-)

The talk discusses how you can incorporate a few functional techniques (map, filter) but the speaker's main goal seems that he wants Swift to be changed to allow for a couple of other functional ideas to be brought into the language.

Where's the Swift proposal for the enhancements? Product and Sum support? Algebraic data types?

I enjoyed the talk, thank you.

The part about "lifting" a type was an 'aha' moment for me and now I understand!*.

I mean, I did this intuitively, but now I know the name of the technique, which is really good.

Thank you, I've learned something new today!

There seem to be a lot of "pretend" functional languages around these days. I have recently been engaging with Scala. Having heard and read so much about how it embraces functional style I was kind of shocked to find the number of limitations and practical impediments to actually using it that way. I am starting to wonder if functional programming has finally fallen victim to the same problem that has afflicted all other methodologies - becoming too popular, part of the hype cycle and getting misinterpreted and misapplied everywhere as a consequence.

Scala is about as functional as it gets - the only remotely mainstream language that's more so is Haskell, IME. What kind of issues did you have?

This sounds pretty misinformed. There are plenty of choices in between Scala and Haskell; Clojure and Elixir are two other relatively popular languages that come to mind.

You might have fallen victim to misinformation yourself.

In general, functional programming in Scala tends to be more FP, with code tending to be more pure than in Clojure and I have no experience with Elixir, but I have some experience with Erlang and FP code in Scala tends to be held at a higher standard than in Erlang.

Of course, you've picked 2 dynamic languages as examples and FP in dynamic languages is different than that practiced in static languages like Haskell or Scala. LISP developers for example don't think so much about monads or other abstractions with mathematical foundations, because LISP developers tend to work around such needs by doing macros (which then have composability problems) or by bending the rules a little, or in other words I've seen no LISP to make a serious attempt at reasoning about I/O in a pure way.

And IMO code in static languages tends to be more pure because of the types, because by having an expressive type system, the developers then want that type system to explain everything. Or in other words, dynamic languages are cool for your day job, but if you want to actually feel what FP is all about, you're better off going for a static languages like Haskell, or even Scala or OCaml.

PS: http://typelevel.org/

Thanks for your reply, I think this is a matter of interpretation of what functional actually means. I personally consider the fact that Scala allows you to get away with immutability so easily (as evidenced with the implementation of all the immutable collections) a very bad thing. It might be just a matter of taste, though; Scala was my gateway drug to functional programming, and I considered implicit parameters and all these immutable containers something very un-functional.

You cannot get away with these things as easily in the Erlang VM (and thus Elixir). I agree with your assessment that Clojure with its macros is an ugly hack, and requires discipline to get right.

Having said that, Haskell also takes a lot of discipline to get right (no lazy I/O, for example), and allows you to get away with ugly things as well (unsafePerformIO). The type system makes it a lot easier to get right though (or in other words, more difficult to do the wrong thing).

ML sits somewhere in between Scala and Haskell. Like Haskell, ML has typed mutable data (`foo` and `foo ref` are different types). Like Scala, ML doesn't distinguish between effectful and effect-free procedures.

Scala is similar to Lisp and other higher-order-but-not-quite-functional languages in that it's littered with unwanted object identities. All you need to do is use the `eq` method to see when two “equal” objects are really not the same.

I didn't mean that the language itself isn't functional - it certainly wants to be. But when I tried to naively apply it using the idiomatic constructs that I found online I got a lot of performance and memory issues. In fact some code that I wrote in Groovy (which I thought would be slow) was much faster than the naive port I did to Scala (which is commonly said to hit nearly native java speed). When I dug into those by profiling it turned out that I needed to have a deep understanding of how the compiler was treating Scala constructs to avoid performance pitfalls. A good example is here:

https://issues.scala-lang.org/browse/SI-1338

Another is that I've almost never managed to use recursion in my algorithms because Scala seems to have very limited ability to successfully optimize tail recursive calls.

Another problem is all kinds of unexpected boxing, unboxing, and implicit conversions of collections that I wasn't expecting.

Again - all the language features are there, just in practice it isn't working out for me very well when I try to use them idiomatically. I'm still learning. But I also learned Haskell and the experience was very different - once I figured out the idiomatic way to do something it usually was also well optimized.

RIP the term "Object Oriented" as Alan Kay defined it.

Reply on news.ycombinator.com