4 ms·

Higher-order functions (funargs) do not equal first-class functions (lambdas). It happens to be that any language which supports first-class function must also

Higher-order functions (funargs) do not equal first-class functions (lambdas). It happens to be that any language which supports first-class function must also support higher-order functions, but the reverse is not necessarily true.

loganmhb 11y ago
That does not match my understanding of first class functions, nor Wikipedia's.[1] Python's inner defs are not anonymous functions (which is what people usually mean by lambdas) but they are definitely first class - they can be returned from a function, stored in a data structure and so on. I agree with the grandparent that the need to label the closure is just an inconvenience, not a disqualification. You can't have anonymous lambdas that aren't first class (how would you reference them?) but you can have first class functions that are not technically anonymous. [1]https://en.m.wikipedia.org/wiki/First-class_function https://en.m.wikipedia.org/wiki/First-class_function
- groovy2shoes 11y ago
  From TFWikipedia: "Some programming language theorists require support for anonymous functions (function literals) as well." I suppose I wasn't aware that that wasn't a universal requirement, but count me in with that group. I think it's useful to make a distinction between "higher-order" and "first-class" for this very reason (i.e., we can talk about languages that do make a distinction without resorting to overloaded terms). I mean, consider a language where this is the case: > "hello," .. " world" ==> "hello, world" > 2 + 2 ==> SYNTAX ERROR > def a = 2 ==> #<number "a"> > a + a ==> 4 Would you consider such a language to have first-class integers? Sort of on a tangent, but while I'm reminded of it: as far as Python's "lambdas" go, they're brutally gimped compared to Python's notion of a function, since what is allowed (and even required) of a function body in Python is much different than what is allowed of a "lambda" body.
  - ScottBurson 11y ago
    > Would you consider such a language to have first-class integers? Yes, I still would, because integers can be bound to variables, passed to and returned from functions, and stored in fields of objects. I would think that the language had a silly syntactic restriction -- which is the same thing I think about Python -- but it wouldn't materially change how I would write programs. It's just that, before any expression using an integer literal, I would have to name the literal. Well, same here. If you want to use a function too complicated to fit in Python's restricted lambda expression syntax, you have to use a named local function. I agree that it's silly, and I'd never design a language like that myself, but again it wouldn't materially change how I write programs -- it just means that what would have fit in one expression would now, in some cases, require multiple statements. Trying to draw a fine distinction between "higher-order" and "supporting first-class functions" doesn't appeal to me; I think of the latter as the definition of the former. (I'm sure I would have trouble remembering which was supposed to be which.) But again, I have no problem with criticizing the design decision -- just not using these terms :-)
    - groovy2shoes 11y ago
      Here's the thing, though: when some element of a language is subject to silly restrictions that other first-class elements of the language are not subject to, that element is, by definition, second-class. The reason being that you can't treat it the way you'd treat any other first-class element.
      - ScottBurson 11y ago
        I see where you're coming from, but still, after the function value is created, there's no restriction on its use. Contrast what some call second-class continuations, which can be invoked only once -- a much more severe restriction. I could see saying something like, Python functions are semantically first-class but syntactically second-class. Or maybe we should just call them "business-class" :-) (BTW your comment downthread about referential transparency is spot-on.)

loganmhb 11y ago

That does not match my understanding of first class functions, nor Wikipedia's.[1] Python's inner defs are not anonymous functions (which is what people usually mean by lambdas) but they are definitely first class - they can be returned from a function, stored in a data structure and so on. I agree with the grandparent that the need to label the closure is just an inconvenience, not a disqualification. You can't have anonymous lambdas that aren't first class (how would you reference them?) but you can have first class functions that are not technically anonymous. [1]https://en.m.wikipedia.org/wiki/First-class_function https://en.m.wikipedia.org/wiki/First-class_function

groovy2shoes 11y ago
From TFWikipedia: "Some programming language theorists require support for anonymous functions (function literals) as well." I suppose I wasn't aware that that wasn't a universal requirement, but count me in with that group. I think it's useful to make a distinction between "higher-order" and "first-class" for this very reason (i.e., we can talk about languages that do make a distinction without resorting to overloaded terms). I mean, consider a language where this is the case: > "hello," .. " world" ==> "hello, world" > 2 + 2 ==> SYNTAX ERROR > def a = 2 ==> #<number "a"> > a + a ==> 4 Would you consider such a language to have first-class integers? Sort of on a tangent, but while I'm reminded of it: as far as Python's "lambdas" go, they're brutally gimped compared to Python's notion of a function, since what is allowed (and even required) of a function body in Python is much different than what is allowed of a "lambda" body.
- ScottBurson 11y ago
  > Would you consider such a language to have first-class integers? Yes, I still would, because integers can be bound to variables, passed to and returned from functions, and stored in fields of objects. I would think that the language had a silly syntactic restriction -- which is the same thing I think about Python -- but it wouldn't materially change how I would write programs. It's just that, before any expression using an integer literal, I would have to name the literal. Well, same here. If you want to use a function too complicated to fit in Python's restricted lambda expression syntax, you have to use a named local function. I agree that it's silly, and I'd never design a language like that myself, but again it wouldn't materially change how I write programs -- it just means that what would have fit in one expression would now, in some cases, require multiple statements. Trying to draw a fine distinction between "higher-order" and "supporting first-class functions" doesn't appeal to me; I think of the latter as the definition of the former. (I'm sure I would have trouble remembering which was supposed to be which.) But again, I have no problem with criticizing the design decision -- just not using these terms :-)
  - groovy2shoes 11y ago
    Here's the thing, though: when some element of a language is subject to silly restrictions that other first-class elements of the language are not subject to, that element is, by definition, second-class. The reason being that you can't treat it the way you'd treat any other first-class element.
    - ScottBurson 11y ago
      I see where you're coming from, but still, after the function value is created, there's no restriction on its use. Contrast what some call second-class continuations, which can be invoked only once -- a much more severe restriction. I could see saying something like, Python functions are semantically first-class but syntactically second-class. Or maybe we should just call them "business-class" :-) (BTW your comment downthread about referential transparency is spot-on.)