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.
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.
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.
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).
[0] http://www.sciencedirect.com/science/article/pii/00220000789...
[1] https://archive.alvb.in/msc/11_infomtpt/papers/the-next-700_...
Really?
[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...
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.
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++).
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.
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?
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.
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.
(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
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.
#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));
} #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;
}The fact that we have "any language where functions are first class citizens" owes a lot to Lisp research.
dx = 0.0001
def deriv(f):
return lambda x: (f(x + dx) - f(x)) / dx
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.
(/ numerator
denominator)
Incidentally Scheme syntax recognizes 3/4 as a rational number. It will do rational arithmetic without floating point problems.
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...
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)
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.
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 or returning first-class functions aren't a problem. First-class closures (function pointer + state) are.
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.
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.