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.

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.

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.

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

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.

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.

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.

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.

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.

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).

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

vs

    [person for person in people if person.isvalid]

And the source code comments are the why.

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.

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.

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.

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

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.

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”.

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.

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 ;-)

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/

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

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 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.

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)

> 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.

> 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.

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

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

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.

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

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

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)

> 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)

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).

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

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 :-)

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...)

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?

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).

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.

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.

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.

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.

> 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, that's not news.

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.

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.

> 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.

> 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.

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.

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.