Hacker News Reader

Comment by jlongster | Hacker News Reader

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.

View on HN

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.

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

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.

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

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.

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.

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?

Are you sure? Because in the example given, it seems that the inner function needs access to the function f

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.

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.

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.

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.

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.

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

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

And indeed it was: qsort() takes a lambda as a parameter, and it's probably as old as C itself.

Reply on news.ycombinator.com