4 ms·

Can someone TLDR this? It's pretty thick, and I can't help but think this is a solved problem with the ability to pass functions as arguments. What's the new in

Can someone TLDR this? It's pretty thick, and I can't help but think this is a solved problem with the ability to pass functions as arguments. What's the new insight here?

deleted 3y ago
[deleted]
amluto 3y ago
I can’t. I think it would have been nice if the article defined the terminology it used to describe its toy languages. But it really seemed like it was describing a language like C++ or Rust where a “computation” is a value that happens to be a callable function (std::function<int ()> or Fn() -> int, for example). A thunk is a value of callable (computable? is this really different?) type, and Return is the magic operation that wraps a value into a trivial closure, like: [val]() { return val; } in C++. Maybe there’s more to it than that.
- Dylan16807 3y ago
  It feels like half the text is dealing with arity confusion that only comes up because of a particular way of implementing functions. Because I agree, if you take a statically typed call-by-value language and "introduce little spurts of lazy evaluation" then don't you get the same flexibility? And you'll also know the arity at all times. There's something in the syntax I don't understand in the middle about unifying things, but then it later says you have to explicitly use "Return" on thunks in records to evaluate them, which sounds like the same thing a CBV language does. Are there other benefits I'm not understanding? Does the unification apply only to function parameters?
  - amluto 3y ago
    I found it almost impossible to understand. The syntax used for their examples was lisp-like, and the function arity seems unambiguous. There is no implicit currying in lisp as far as I know. Extra-confusingly, the definitions at the start were in a syntax resembling Haskell, but I think it has multiple mistakes.
crq-yml 3y ago
If you're in eager evaluation land, everything evaluates as you come to it, so you can handle all arguments at runtime by using a stack and no problem is felt. Once we say, "actually we don't evaluate until it's used" ambiguity arises. So the context of this is to solve a problem-in-practice with arguments in a lazy evaluation environment, which is that you don't know how many arguments you need to supply without doing the evaluation.
- analognoise 3y ago
  Is that what they mean by “calculating the arity”?
  - crq-yml 3y ago
    Yes, arity is "number of arguments". I don't have expertise in lazy evaluation myself, I've just been exposed to enough of it to explain the motivations.
- amluto 3y ago
  I’m very far from an expert in these styles of programming languages, but I’m pretty sure I’m missing something, and it’s not well explained in the OP. The OP uses a lisp-y syntax, fully parenthesized, for its code examples. But function arity isn’t so much an issue in these languages — you can infer it from the parentheses, and there’s no implicit currying. (The OP uses a Haskell-like syntax for its definitions, but I think it contains multiple mistakes, making it very hard to understand.) A language with implicit currying and eager evaluation specifically of function arguments just seems overcomplicated to me. It sounds like a stack machine in which you pop an element off the stack, evaluate it enough to determine its arity, then pop that many more elements, evaluate them, and then apply the function. This sounds unpleasantly dynamic and quite hard to implement efficiently. Am I missing something here?
  - bitwalker 3y ago
    I wouldn't read too much into the syntax - the Haskell-like definitions are just a succinct way to describe the AST representation for the toy call-by-push-value language the post is talking about. Similarly, the syntax that resembles LISP, is actually (I believe) just shorthand for how the language would be represented in an extended lambda calculus with call-by-push-value semantics. I think it's important to note that the post is clearly written for someone working on the implementation of compilers/type systems. So for example, in a compiler IR, especially those based on an extended lambda calculus representation, functions/closures are often curried, i.e. only take a single argument. As a result it can be an issue at a given call site to know whether a function is "saturated", i.e. all of its arguments have been applied so it will do some work and return the actual result; or whether it is only partially saturated, in which case it returns a new function that needs one less argument than before. I gather that this interacts poorly with typing in some situations, but I'm not super familiar with the issues here as I haven't gone down the rabbit hole of building a compiler with this kind of IR. That said, as someone who works as a compiler engineer, I do recognize the potential of call-by-push-value, namely that it reifies evaluation semantics in the IR, rather than it being implicitly eager or lazy, and thus having to hack around the lack of one or the other, i.e. implementing lazy evaluation on top of eager semantics or vice versa. Making it a first-class citizen enables optimizations that would otherwise be impossible or very difficult to implement. To be clear though, you can obviously implement lazy on top of eager, or eager on top of lazy, without call-by-push-value - but I think if you anticipate needing to do that, and you are building a new compiler, using a call-by-push-value IR might be a worthwhile approach to take. There might be more to it that I'm not really seeing yet in my brief reading of it, but the post made sense to me, it's just assuming a lot about the reader (i.e. that you are deeply familiar with compiler implementation, type theory, etc.).
charcircuit 3y ago
Imagine if functions were polymorphic over the ability to pass in a function as an argument. So both f(1) and f(() => 1) would be valid for a function that takes a number. It would also apply to variables and such too. So "const a = () => 1; const b = a + a;" would be possible to do.
- rezonant 3y ago
  This is a good explanation. So effectively it's making the lazy/eager distinction controlled by the caller and not the callee.
- Izkata 3y ago
  Ahh k. So like Rebol and Red have worked for decades: >> F: func [A][print type? :A print join "Arg: " A] >> F "Foo" string Arg: Foo >> F func [][return "Bar"] function Arg: Bar I really got spoiled learning Rebol as my first language, I'd already internalized a ton of concepts long before they were introduced during school and college. Higher-order functions were the first time I really realized it, I guess here's another to add to the pile. Even knowing this though, that post really is really obtuse. Definitely could have been better written. Basically in these languages, functions don't have a special syntax to be called, like F(), they just get called when used. So usage of a no-argument function is identical to a variable, and what happens depends on its datatype (function, string, whatever). The special :A syntax is to get the value without evaluating it if it is a function.
- vidarh 3y ago
  That's already the case for any dynamic languages, and it's just down to whether you write your code to be flexible about inputs. E.g def int(i) = i.respond_to(:call) ? i.call : i.to_i def f(i) = int(i) * 2 f in this case can take both ints and lambdas or anything call-able. In practice we'd usually do this via any of the normal conversion methods like expecting the caller to support to_i etc., and bear the complexity for us as needed unless there's a really compelling reason to think the caller will often want to defer the evaluation past the call site and into the method itself. That's usually very obvious when you come across it, like e.g. if the argument is expected to come from a remote source, but as long as the API for how the method uses the value is clear, substituting the value for a deferred calculation is easy.

Can someone TLDR this? It's pretty thick, and I can't help but think this is a solved problem with the ability to pass functions as arguments. What's the new insight here?

deleted 3y ago

[deleted]

amluto 3y ago

I can’t. I think it would have been nice if the article defined the terminology it used to describe its toy languages. But it really seemed like it was describing a language like C++ or Rust where a “computation” is a value that happens to be a callable function (std::function<int ()> or Fn() -> int, for example). A thunk is a value of callable (computable? is this really different?) type, and Return is the magic operation that wraps a value into a trivial closure, like: [val]() { return val; } in C++. Maybe there’s more to it than that.

Dylan16807 3y ago
It feels like half the text is dealing with arity confusion that only comes up because of a particular way of implementing functions. Because I agree, if you take a statically typed call-by-value language and "introduce little spurts of lazy evaluation" then don't you get the same flexibility? And you'll also know the arity at all times. There's something in the syntax I don't understand in the middle about unifying things, but then it later says you have to explicitly use "Return" on thunks in records to evaluate them, which sounds like the same thing a CBV language does. Are there other benefits I'm not understanding? Does the unification apply only to function parameters?
- amluto 3y ago
  I found it almost impossible to understand. The syntax used for their examples was lisp-like, and the function arity seems unambiguous. There is no implicit currying in lisp as far as I know. Extra-confusingly, the definitions at the start were in a syntax resembling Haskell, but I think it has multiple mistakes.

crq-yml 3y ago

If you're in eager evaluation land, everything evaluates as you come to it, so you can handle all arguments at runtime by using a stack and no problem is felt. Once we say, "actually we don't evaluate until it's used" ambiguity arises. So the context of this is to solve a problem-in-practice with arguments in a lazy evaluation environment, which is that you don't know how many arguments you need to supply without doing the evaluation.

analognoise 3y ago
Is that what they mean by “calculating the arity”?
- crq-yml 3y ago
  Yes, arity is "number of arguments". I don't have expertise in lazy evaluation myself, I've just been exposed to enough of it to explain the motivations.
amluto 3y ago
I’m very far from an expert in these styles of programming languages, but I’m pretty sure I’m missing something, and it’s not well explained in the OP. The OP uses a lisp-y syntax, fully parenthesized, for its code examples. But function arity isn’t so much an issue in these languages — you can infer it from the parentheses, and there’s no implicit currying. (The OP uses a Haskell-like syntax for its definitions, but I think it contains multiple mistakes, making it very hard to understand.) A language with implicit currying and eager evaluation specifically of function arguments just seems overcomplicated to me. It sounds like a stack machine in which you pop an element off the stack, evaluate it enough to determine its arity, then pop that many more elements, evaluate them, and then apply the function. This sounds unpleasantly dynamic and quite hard to implement efficiently. Am I missing something here?
- bitwalker 3y ago
  I wouldn't read too much into the syntax - the Haskell-like definitions are just a succinct way to describe the AST representation for the toy call-by-push-value language the post is talking about. Similarly, the syntax that resembles LISP, is actually (I believe) just shorthand for how the language would be represented in an extended lambda calculus with call-by-push-value semantics. I think it's important to note that the post is clearly written for someone working on the implementation of compilers/type systems. So for example, in a compiler IR, especially those based on an extended lambda calculus representation, functions/closures are often curried, i.e. only take a single argument. As a result it can be an issue at a given call site to know whether a function is "saturated", i.e. all of its arguments have been applied so it will do some work and return the actual result; or whether it is only partially saturated, in which case it returns a new function that needs one less argument than before. I gather that this interacts poorly with typing in some situations, but I'm not super familiar with the issues here as I haven't gone down the rabbit hole of building a compiler with this kind of IR. That said, as someone who works as a compiler engineer, I do recognize the potential of call-by-push-value, namely that it reifies evaluation semantics in the IR, rather than it being implicitly eager or lazy, and thus having to hack around the lack of one or the other, i.e. implementing lazy evaluation on top of eager semantics or vice versa. Making it a first-class citizen enables optimizations that would otherwise be impossible or very difficult to implement. To be clear though, you can obviously implement lazy on top of eager, or eager on top of lazy, without call-by-push-value - but I think if you anticipate needing to do that, and you are building a new compiler, using a call-by-push-value IR might be a worthwhile approach to take. There might be more to it that I'm not really seeing yet in my brief reading of it, but the post made sense to me, it's just assuming a lot about the reader (i.e. that you are deeply familiar with compiler implementation, type theory, etc.).

charcircuit 3y ago

Imagine if functions were polymorphic over the ability to pass in a function as an argument. So both f(1) and f(() => 1) would be valid for a function that takes a number. It would also apply to variables and such too. So "const a = () => 1; const b = a + a;" would be possible to do.

rezonant 3y ago
This is a good explanation. So effectively it's making the lazy/eager distinction controlled by the caller and not the callee.
Izkata 3y ago
Ahh k. So like Rebol and Red have worked for decades: >> F: func [A][print type? :A print join "Arg: " A] >> F "Foo" string Arg: Foo >> F func [][return "Bar"] function Arg: Bar I really got spoiled learning Rebol as my first language, I'd already internalized a ton of concepts long before they were introduced during school and college. Higher-order functions were the first time I really realized it, I guess here's another to add to the pile. Even knowing this though, that post really is really obtuse. Definitely could have been better written. Basically in these languages, functions don't have a special syntax to be called, like F(), they just get called when used. So usage of a no-argument function is identical to a variable, and what happens depends on its datatype (function, string, whatever). The special :A syntax is to get the value without evaluating it if it is a function.
vidarh 3y ago
That's already the case for any dynamic languages, and it's just down to whether you write your code to be flexible about inputs. E.g def int(i) = i.respond_to(:call) ? i.call : i.to_i def f(i) = int(i) * 2 f in this case can take both ints and lambdas or anything call-able. In practice we'd usually do this via any of the normal conversion methods like expecting the caller to support to_i etc., and bear the complexity for us as needed unless there's a really compelling reason to think the caller will often want to defer the evaluation past the call site and into the method itself. That's usually very obvious when you come across it, like e.g. if the argument is expected to come from a remote source, but as long as the API for how the method uses the value is clear, substituting the value for a deferred calculation is easy.