31 ms·

This was back in 1983 where most (all?) other languages did not have first-class procedures. If you can imagine programming without them and then being exposed

This was back in 1983 where most (all?) other languages did not have first-class procedures. If you can imagine programming without them and then being exposed to that, it would be a big deal. We take them for granted today.

AnimalMuppet 9y ago
Well, in 1992 (IIRC), I did a numerical integration in C. For a "first class function", it just took a function pointer. That approach would have been available in C in 1983...
- jlongster 9y ago
  That's not really the same thing at all. What's missing is the ability to close over values, which is a key part of first-class functions. You could not re-create the original example in C, which is to return a new function. You'd have to return some sort of object that keeps a reference to the function pointer, and provides a special mechanism for calling it, i.e. a poor man's closure.
  - klibertp 9y ago
    > What's missing is the ability to close over values, which is a key part of first-class functions. This is not true. You can have first-class function which are not closures: every dynamically-scoped Lisp works that way, see Emacs Lisp without `lexical-binding: t` and the `lexical-let` implementation.
    - vilhelm_s 9y ago
      And the derivatives example will not work, because it needs to close over the variable f. (setq dx .0001) (defun deriv (f) (lambda (x) (/ (- (funcall f (+ x dx)) (funcall f x)) dx))) (defun cube (x) (* x x x)) (setq cube-deriv (deriv #'cube)) (funcall cube-deriv 2) Error: Symbol's value as variable is void: f Setting lexical-binding to t, so that deriv returns a closure, fixes the problem.
      - vilhelm_s 9y ago
        Incidentally, I think comparing the elisp and the Scheme versions is instructive because it shows how much is going on "behind the scenes" in this lecture. Abelson and Sussman made it all seem natural and effortless, but the key ideas in this 1983 lecture come from Sussman and Steele's research on Scheme in the late 1970s. The blog post author marveled that the compiler could optimize all tail-calls, which was a new emphasis of Scheme (earlier Lisps only did a best-effort job), and which required e.g. changing the function calling conventions. He appreciated how the definition of derivatives looks like the mathematical definition; but it only looks this clean because of Scheme's choice to have a single namespace for functions and values (1-Lisp versus 2-Lisp), so we get rid of elisp's setq/funcall/#' cruft. And he wondered if the substitution model (which lets you think about programs like high school algebra, instead of modelling the execution in detail) could really always work. But it only works because of Scheme's choice to use lexical binding and closures. All of these were difficult design problems at the time, and different Lisps explored different choices. We really have Scheme to thank for a lot of programming language concepts which we take for granted nowadays.
  - AnimalMuppet 9y ago
    OK, for the example given, I don't see how closures are relevant. I could write the exact same derivative function in C in 1983. Are you saying that in general, closures are essential to first-class functions? Or are you saying that, in the derivative example, there's something going on with closures?
    - phailhaus 9y ago
      Are you sure? Because in the example given, it seems that the inner function needs access to the function f
      - AnimalMuppet 9y ago
        See smitherfield's examples. Yes, the inner function needs access to f. This means that it has to be passed in to the inner function. But in my view, that's not any different than (in the original example) having deriv-cube calling deriv with cube as an argument (or composing deriv and cube, if you prefer). You may say that the difference is that in Lisp, deriv-cube is a partial application, whereas in C you really can't do that. And you'd be right. But for this example, I don't see what difference it makes.
  - groby_b 9y ago
    Sigh. How soon they forgot. You create a thunk that provides the closure. Which used to be a common thing to do when you wrote C code. Note: I'm not saying that C could express closures and first-class function objects anywhere near as neatly as Lisp. But the idea that only Lisp allowed you to use them, and C was the land of straightforward procedural code... does not represent what I saw back then. Just as you can write FORTRAN code in any language, you can transfer ideas from other languages to C. What's great about Lisp is that it made the ideas easily accessible.
    - int_19h 9y ago
      There's no way to create a thunk in portable C even today, much less back then. You had to do some form of machine code generation on the fly, which instantly limited it to some particular architecture / calling convention at the very least.
- pmelendez 9y ago
  If I am not mistaken, you will need to know the signature of the function. Even if you use void* you would need to know the amount of parameters that the function uses.
  - AnimalMuppet 9y ago
    Sure. For numerical (one dimensional) integration, it took one (double) parameter. In 1992, C was getting to the point where I could make that type-safe. In 1983, not so much.
- smitherfield 9y ago
  He is right, you could do something roughly equivalent in 1983-era C, albeit a fair amount clunkier due to the lack of partial application or (any kind of) type-checking: #define DX (double)0.0001 double f_prime(f, x) register double (*f)(); double x; { return ((*f)(x + DX) - (*f)(x)) / DX; } #define DERIV(F, X) f_prime((F), (double)(X)) double cube(x) double x; { return x * x * x; } #define DERIV_CUBE(X) DERIV(cube,(X)) main() { printf("%f\n%f\n%f\n", DERIV_CUBE(2), DERIV_CUBE(3), DERIV_CUBE(4)); }
  - smitherfield 9y ago
    And in >=C89: #include <stdio.h> double deriv(double (*f)(double), double x) { static const double dx = 1e-8; return (f(x + dx) - f(x)) / dx; } static double cube(double x) { return x * x * x; } double deriv_cube(double x) { return deriv(cube, x); } int main(void) { printf("%f\n%f\n%f\n", deriv_cube(2), deriv_cube(3), deriv_cube(4)); return 0; }
  - deleted 9y ago
    [deleted]
- hota_mazi 9y ago
  And indeed it was: qsort() takes a lambda as a parameter, and it's probably as old as C itself.
amatic 9y ago
Can relate. I remember programing in basic, then c, then java.. and at one point thinking 'man, i wish i could send this function to this other function somehow'. Granted, didn't understand function pointers, but when much later i learned about functional languages, it was instant return to childhood obsession with programming.

AnimalMuppet 9y ago

Well, in 1992 (IIRC), I did a numerical integration in C. For a "first class function", it just took a function pointer. That approach would have been available in C in 1983...

jlongster 9y ago
That's not really the same thing at all. What's missing is the ability to close over values, which is a key part of first-class functions. You could not re-create the original example in C, which is to return a new function. You'd have to return some sort of object that keeps a reference to the function pointer, and provides a special mechanism for calling it, i.e. a poor man's closure.
- klibertp 9y ago
  > What's missing is the ability to close over values, which is a key part of first-class functions. This is not true. You can have first-class function which are not closures: every dynamically-scoped Lisp works that way, see Emacs Lisp without `lexical-binding: t` and the `lexical-let` implementation.
  - vilhelm_s 9y ago
    And the derivatives example will not work, because it needs to close over the variable f. (setq dx .0001) (defun deriv (f) (lambda (x) (/ (- (funcall f (+ x dx)) (funcall f x)) dx))) (defun cube (x) (* x x x)) (setq cube-deriv (deriv #'cube)) (funcall cube-deriv 2) Error: Symbol's value as variable is void: f Setting lexical-binding to t, so that deriv returns a closure, fixes the problem.
    - vilhelm_s 9y ago
      Incidentally, I think comparing the elisp and the Scheme versions is instructive because it shows how much is going on "behind the scenes" in this lecture. Abelson and Sussman made it all seem natural and effortless, but the key ideas in this 1983 lecture come from Sussman and Steele's research on Scheme in the late 1970s. The blog post author marveled that the compiler could optimize all tail-calls, which was a new emphasis of Scheme (earlier Lisps only did a best-effort job), and which required e.g. changing the function calling conventions. He appreciated how the definition of derivatives looks like the mathematical definition; but it only looks this clean because of Scheme's choice to have a single namespace for functions and values (1-Lisp versus 2-Lisp), so we get rid of elisp's setq/funcall/#' cruft. And he wondered if the substitution model (which lets you think about programs like high school algebra, instead of modelling the execution in detail) could really always work. But it only works because of Scheme's choice to use lexical binding and closures. All of these were difficult design problems at the time, and different Lisps explored different choices. We really have Scheme to thank for a lot of programming language concepts which we take for granted nowadays.
- AnimalMuppet 9y ago
  OK, for the example given, I don't see how closures are relevant. I could write the exact same derivative function in C in 1983. Are you saying that in general, closures are essential to first-class functions? Or are you saying that, in the derivative example, there's something going on with closures?
  - phailhaus 9y ago
    Are you sure? Because in the example given, it seems that the inner function needs access to the function f
    - AnimalMuppet 9y ago
      See smitherfield's examples. Yes, the inner function needs access to f. This means that it has to be passed in to the inner function. But in my view, that's not any different than (in the original example) having deriv-cube calling deriv with cube as an argument (or composing deriv and cube, if you prefer). You may say that the difference is that in Lisp, deriv-cube is a partial application, whereas in C you really can't do that. And you'd be right. But for this example, I don't see what difference it makes.
- groby_b 9y ago
  Sigh. How soon they forgot. You create a thunk that provides the closure. Which used to be a common thing to do when you wrote C code. Note: I'm not saying that C could express closures and first-class function objects anywhere near as neatly as Lisp. But the idea that only Lisp allowed you to use them, and C was the land of straightforward procedural code... does not represent what I saw back then. Just as you can write FORTRAN code in any language, you can transfer ideas from other languages to C. What's great about Lisp is that it made the ideas easily accessible.
  - int_19h 9y ago
    There's no way to create a thunk in portable C even today, much less back then. You had to do some form of machine code generation on the fly, which instantly limited it to some particular architecture / calling convention at the very least.
pmelendez 9y ago
If I am not mistaken, you will need to know the signature of the function. Even if you use void* you would need to know the amount of parameters that the function uses.
- AnimalMuppet 9y ago
  Sure. For numerical (one dimensional) integration, it took one (double) parameter. In 1992, C was getting to the point where I could make that type-safe. In 1983, not so much.
smitherfield 9y ago
He is right, you could do something roughly equivalent in 1983-era C, albeit a fair amount clunkier due to the lack of partial application or (any kind of) type-checking: #define DX (double)0.0001 double f_prime(f, x) register double (*f)(); double x; { return ((*f)(x + DX) - (*f)(x)) / DX; } #define DERIV(F, X) f_prime((F), (double)(X)) double cube(x) double x; { return x * x * x; } #define DERIV_CUBE(X) DERIV(cube,(X)) main() { printf("%f\n%f\n%f\n", DERIV_CUBE(2), DERIV_CUBE(3), DERIV_CUBE(4)); }
- smitherfield 9y ago
  And in >=C89: #include <stdio.h> double deriv(double (*f)(double), double x) { static const double dx = 1e-8; return (f(x + dx) - f(x)) / dx; } static double cube(double x) { return x * x * x; } double deriv_cube(double x) { return deriv(cube, x); } int main(void) { printf("%f\n%f\n%f\n", deriv_cube(2), deriv_cube(3), deriv_cube(4)); return 0; }
- deleted 9y ago
  [deleted]
hota_mazi 9y ago
And indeed it was: qsort() takes a lambda as a parameter, and it's probably as old as C itself.

amatic 9y ago

Can relate. I remember programing in basic, then c, then java.. and at one point thinking 'man, i wish i could send this function to this other function somehow'. Granted, didn't understand function pointers, but when much later i learned about functional languages, it was instant return to childhood obsession with programming.