Hacker News Reader

Comment by phailhaus | Hacker News Reader

I'm having trouble understanding why the derivative example was so impressive to the author. Can someone explain? It seems trivial to do in any language where functions are first class citizens.

View on HN

> I'm having trouble understanding why the derivative example was so impressive to the author.

Says someone 35 years later. :)

Probably every (commonly found) derivative example, and the majority of languages with first class functions all come from this example.

MIT introducing Scheme and those two professors writing SICP are a large part of the reason for the current functional programming landscape. Without them I believe they'd still be as niche as APL.

I only got to read SICP almost a decade after finishing my degree, it wasn't even a thing at my university.

We got to learn FP via Caml Light, Standard ML, pure lambda calculus and we also had some LP classes via Prolog.

Those of us that learned Lisp did it to customize Emacs.

> Caml Light, Standard ML, pure lambda calculus

The first two being based lisp, and the third being what inspired lisp.

It's like saying: I learned low level imperative programming from using Go, C++, and register machines. Which, sure, but the C language was hugely influential to all of that.

>The first two being based lisp

Really?

What does ML, initially developed for theorem proving, have to do with Lisp?

Because lisp is good at anything? But especially alternative evaluation systems (of which theorem proving is one).

Because they took lisp and added types to it; via the ISWIM language document ("The Next 700 Programming Languages") which was based off of the original lisp.

Because the lisp language family is a formulation of lambda calculus and has first class functions, unlike any other language family at the time, and that is necessary for theorem proving that is based on lambda calculus.

Because they likely prototyped the system in a set of lisp macros before writing the language (all the authors knew lisp and had taught each other it).

Can you point me to a good reference paper about this?

No one has really written a paper about the history of all this (I also mentioned this paper [1] in one of my other comments). But if you read the original ML paper [0] you'll see how they developed the language (notably by using ISWIM's syntax as a base). Note also that they are solving a problem with LISP (and dismissing Algol languages entirely) by building in strong types.

[0] http://www.sciencedirect.com/science/article/pii/00220000789...

[1] https://archive.alvb.in/msc/11_infomtpt/papers/the-next-700_...

Better example would be symbolic differentiation[1][2] which requires more quirks even in modern languages[3][4]

[1] https://mitpress.mit.edu/sicp/full-text/sicp/book/node39.htm...

[2] https://github.com/clojure-numerics/expresso

[3] http://docs.sympy.org/latest/tutorial/intro.html#a-more-inte...

[4] https://github.com/yuemingl/SymJava#examples

Note that the simplistic approach doesn't scale well, as terms tend to "explode" in size and hence computation time.

There is a whole sub field of mathematics / computer science called "algorithmic differentiation", also known as "automatic differentiation".

The goal is to take an existing computer program and transform it into another computer program that calculates the derivatice just as efficiently (up to a constant factor of ~2 to 5, depending on how you measure), and with about the same numeric stability (by usual measures).

And this is just the start. Classic differentiation is also called "forward" mode. Understanding the "reverse mode", and why you want this for gradients, is even more mind-bending.

There is a whole world to discover here. The book "Evaluating Derivatives" is a good starting point for anyone interested.

http://epubs.siam.org/doi/book/10.1137/1.9780898717761

There are also many of beautiful papers on that topic.

It doesn't stop at forward-mode, and reverse-mode, because finding the optimal mode relates to a complicated graph problem, which, IIRC, is NP-hard in general. Not only that, but most of the difficulty is in getting these tools to work on arbitrary codebases, making it more a software engineering problem rather than a maths problem.

> It doesn't stop at forward-mode, and reverse-mode, because finding the optimal mode relates to a complicated graph problem, which, IIRC, is NP-hard in general.

Yes, there are combined forward-reverse-mode approaches as well as "cross country" approaches. That's in part of what I menat with a "whole world to discover".

> Not only that, but most of the difficulty is in getting these tools to work on arbitrary codebases, making it more a software engineering problem rather than a maths problem

Depending on your viewpoint, it is neither SE nor math, but a PL (programming languages) issue, meaning that viewing the program e.g. as register machine (classic assembly) yields to different approaches than viewing it as lambda calculus expression (which provided great results, but it is hard to transport the results back to languages like Fortran or C++).

Exactly. I've just started exploring dual numbers which are needed for automatic differentiation [0]. It's mind-blowing stuff, and it's easy to code in Lisp.

[0] https://en.m.wikipedia.org/wiki/Dual_number

What do you mean by reverse mode? I assumed integration, but that doesn't seem to be what you're talking about.

It's also sometimes called adjoint mode. See this: https://en.wikipedia.org/wiki/Automatic_differentiation#Reve...

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.

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.

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.

Lisp was the first language he encountered with first-class functions, and derivatives is an example showing why first-class functions are useful.

It was 1983, and the author cut his teeth in Z80 assembly language and stuff like that.

The fact that we have "any language where functions are first class citizens" owes a lot to Lisp research.

Indeed, posts like this are of historical interest, but today, take Python:

    dx = 0.0001
    def deriv(f):
        return lambda x: (f(x + dx) - f(x)) / dx

This works just the same as the author's example and looks even more like the calculus formula people are used to.

Now do the same using symbolic computation.

SymPy does it beautifully but it's much much more complicated than the equivalent in Scheme.

Symbolic differentation a topic covered in the early chapters of SICP. Doing the same in Python requires intimate knowledge of the dark corners of Python and is not at all suitable for an example in an introductory computer science class.

f(x + dx) does look more conventional than (f (+ x dx)), but

  (/ numerator
     denominator)

looks more like the conventional fraction syntax than putting a / somewhere in the middle of a line.

I'll give you that but also, ask 100 random people what "3/4" means and what "(/ 3 4)" means.

Are you sure random people are going to recognize "3/4" notation? It could be different for "3 ÷ 4", but I think "3/4" is not widely used outside of programming?

Have you ever looked at a cookbook?

http://www.tasteofhome.com/recipes/how-to-cook/how-to-cut-do...

Taken a drive?

https://c1.staticflickr.com/5/4149/5174138836_6603010a7d_b.j...

No, I didn't... At least, not in English. Good to know, thanks.

It is a country-specific convention. What's written as e.g. ½ in US would be more commonly written with a horizontal dividing line in many other places, or simply as 0.5. Similarly, 2.5 instead of 2½ etc.

It's used outside of programming in, say, mathematics. :)

Yes, I'm sure hardly any would say "three fourths" for (/ 3 4) and a lot of them would for 3/4. (A lot of them might also say "three or four".)

Incidentally Scheme syntax recognizes 3/4 as a rational number. It will do rational arithmetic without floating point problems.

Racket (and others?) gives you a sugar of (n . / . d) to infix any two-arg function if that's a stumbling block.

I don't know, things like 1/2 are pretty conventional fraction syntax.

But if you really wanted to, you could always do the same thing in Python, since newlines are basically just ignored inside parentheses:

   (numerator /
    denominator)

Or even place / on its own line if so desired.

The tricky thing here isn't first-class functions, but closures. For the example to work, the inner function construction has to implicitly capture the argument to the outer function.

Probably hadn't thought of passing a subroutine address to a routine in z80 machine language he was familiar with?

Yeah, I understand why this is difficult if not impossible to do in BASIC, but functions are first-class in just about any assembly language.

That said, remember that the author is talking about his experience as a first-year college student. When I went to college, I had extensive experience with BASIC (GW, Q, TI, and a bit of Visual), a year of C++ in high school, and a few vague attempts at assembly (386 and Z80) that got me nowhere. The idea of function pointers was one of those scary advanced C things that I had picked up to avoid, and certainly the corresponding assembly concept didn't occur to me. Of course I knew you could jump to a computed value, but the mindset was foreign. I sort of knew that this was doable with objects in C++ - I could define a base class with an abstract method calculate(), and make a Cube subclass - but thinking of functions as first-class still wasn't obvious.

Yes, pointers to pointers etc. are difficult to grasp, but then again, so is passing functions as arguments. Also, information wasn't as readily available then as it is now.

Anyways, to make a long story short, here's "mega-deriver" numerical calculus package I just whipped up in COMMODORE BASIC 2.0: http://imgur.com/94eNuSX

It should run (unmodified?) on all MS BASIC dialects of the time (including Apple II and VIC-20). Note the higher precision of floating-point numbers than the puny m86k lisp the OP linked to. This one's probably faster, too ;)

Passing function addresses as parameters is easy. It's more difficult to return a nested function that closes over the outer function's variables.

Not really in machine language or even BASIC (see below).

Your BASIC example doesn't have any local variables to close over. It just references a global. That defeats the whole point of closures.

Passing or returning first-class functions aren't a problem. First-class closures (function pointer + state) are.

You can create closures in CBM BASIC V2 by referencing arrays or creating thunks as an extension. But that's beside the original point. Implementing is not a lot of work but since my mega-deriver already solves the problem (derivation) elegantly and efficiently (most likely more efficiently than the original m68k lisp program), I really don't see any reason to use closures here. Do you?

> It seems trivial to do in any language where functions are first class citizens

When you put that in the historical context, you will see that first class function with dynamic scoping are coming around that time. Also, Scheme which was the LISP used in the story, was the first introducing proper support for lexically scoped first-class functions. I would guess that Javascript inherited this from Scheme.

I was hoping for a symbolic derivation.

Did that for simple polynomials back in the early 80s. The approximation of an arbitrary function is more interesting to me, precisely because I didn't do that, I guess :-)

Cal State (Stan) only had (some) Lisp available because I was interested in AI. We only had shallow treatment of it (GC scoffed at...), and I've only been discovering deeper features second hand by reading about it the last 10 or 15 years.

Reply on news.ycombinator.com