Discussion from 2016: https://news.ycombinator.com/item?id=11766092

I also found this article on differentiable programming: https://pseudoprofound.wordpress.com/2016/08/03/differentiab... but a foundational TL;DR would be highly appreciated.

I think Richard Fateman's paper on the subject is a good introduction: https://people.eecs.berkeley.edu/~fateman/papers/ADIL.pdf

> end-to-end differentiable interpreter for the programming language Forth which enables programmers to write program sketches with slots that can be filled with behaviour trained from program input-output data. We can optimise this behaviour directly through gradient descent techniques on user-specified objectives

Neat. What sort of things have been achieved with machine-learning over algorithms, though? I've seen the topic crop up now and then, but I couldn't name any real successes.

I haven't read this paper, but the way deep learning is evolving is becoming more like general-purpose programming. People have even started calling it "differentiable programming". The basic driving force is that the neural network architectures people are using are becoming more and more complex, employing state and dynamically changing structures. To express this deep learning frameworks are becoming like general-purpose languages with the constraint that everything has to be differentiable for optimisation to work. So I don't think the driving force is that "normal" programs will have machine learned components, but that machine learning is becoming more like programming.

... and will soon be seen as (and actually be!) very mundane and not really AI at all, although a very useful tool. Just like optimizing compilers.

It still does the exact same thing as it did 10 years ago. Whether or not it is seen as OR is AI is a different topic. Anything that becomes more widely understood seems mundane and less sexy than when it is an emerging field.

On that different topic, real progress starts the moment it is not seen as AI.

> What sort of things have been achieved with machine-learning over algorithms, though?

See also this paper for a comparison of programming by example using gradient descent versus more standard alternatives:

https://arxiv.org/abs/1608.04428

The main takeaway is that gradient descent is not a silver bullet for searching over program space.

> with machine-learning over algorithms

It's not really machine-learning over algorithms, but more optimization over algorithms. These are essentially the algorithms which are already found to control robots and other various plants [0]. The idea is that sometimes you have a parameter somewhere which needs optimization. With these approaches you can leave it lingering in your code, and optimize it later as required in your setup or for your application.

[0] https://en.wikipedia.org/wiki/Model_predictive_control

> The idea is that sometimes you have a parameter somewhere which needs optimization

I don't get you. If I'm reading the summary correctly, the point of the paper is to have machine-learning sculpt a Forth program, not to have machine-learning optimise some constant used in a given program.

From the summary:

> our interpreter is able to effectively leverage different levels of prior program structure and learn complex behaviours such as sequence sorting and addition

Of course, if by 'parameter' you mean subroutine, the two ideas are rather similar - just define your parameter to be 'a Forth word that meets the spec'.

Aside: why Forth went with 'word' over something standard like 'function', I don't know.

> why Forth went with 'word' over something standard like 'function', I don't know

Because tokens in Forth are always separated by spaces, like words. Also, "Function" would be inaccurate because they are not mathematical functions but procedures or "subroutines" (the "standard" word in the middle of the seventies).

> tokens in Forth are always separated by spaces, like words.

So are arguments in LISP, but they still call them arguments.

'Word' was already taken by the processor folks, and we already had function/procedure/subroutine.

> "Function" would be inaccurate because they are not mathematical functions but procedures or "subroutines"

Sure, C functions aren't pure mathematical functions either. So? Function/procedure/subroutine are standard terminology. It's not all that confusing that a Haskell function doesn't behave the same way a C function does.

There are other options, like action/operation/method/event/verb/functor/transform. That Forth is stack-oriented doesn't really justify inventing a new term, to me at least.

Fun fact: the Factor programming language also uses 'word'.

In Moore’s unpublished 1970 book he says “subroutine” a lot and mostly references Fortran when comparing forth to other languages. He calls the input tokens “words” since they are delimited by spaces in a stream of other words. He builds a kind-of analogy by saying that words are given definitions in a forth dictionary. He also explicitly points out that he has used the same term “word” that they use for processor data size, to avoid any confusion.

All in all, I don’t think the terminology was considered as fixed as you seem to think it was in 1968. As you mentioned, people were misusing “function” as defined by centuries of mathematics... but because that caught on, your response to that is “so?” The weird things about forth did not stick, so they still seem weird today.

> So are arguments in LISP, but they still call them arguments.

I think (+(+ 1 2)3) is valid Lisp. The equivalent in Forth would be 1 2+3+, but it's not valid unless the word "2+3+" exists in your dictionary.

"word" was also taken by the machine architecture people. Nobody is confused between "three word structure" and "word processor".

> Also, "Function" would be inaccurate because they are not mathematical functions but procedures or "subroutines" (the "standard" word in the middle of the seventies).

From the paper: "Each word wi defines a transition function between machine states w_i: S → S" where S is...

> represented by a state S = (D,R,H,c), which contains two stacks: a data evaluation pushdown stack D (data stack) holds values for manipulation, and a return address pushdown stack R (return stack) assists with return pointers and subroutine calls. These are accompanied by a heap or random memory access buffer H, and a program counter c.

Maybe I'm missing something. If I wrote an implementation where state comprised two immutable lists for the stacks and an immutable map for the heap, wouldn't that capture the semantics of words in as a pure function?

That's not saying that the Word is a function in the programming sense. It's saying that, if you're doing static analysis of a program, there is a mathematical function that models the Word's behavior. In particular, it's doing the 'standard' trick where any computer program can be modeled as a function whose input is the entire computer (and possibly outside resources like the network), and whose output is that computer updated with any state changes that might have occurred.

But that function that describes the word's behavior on the computer isn't the same as the word itself. The word's input is the few words under it on the stack, and its input is something that goes on the stack. The function's input is the entire stack, and its input gets fed into the next function.

You're correct that you could right an implementation that reifies this concept, if you're so inclined. But that's still not the same thing. The 'function' is still on the meta-language level, not the language level where the word is.

> If I wrote an implementation where state comprised two immutable lists for the stacks and an immutable map for the heap, wouldn't that capture the semantics of words in as a pure function?

A good point that slipped my mind. One can interpret Forth as modifying a stack, or, just as valid, interpret it as mapping one stack to another.

Implementation detail is just that.

Forth words can alter the interpretation of subsequent characters in the input stream. The word \ consumes any characters between itself and a newline- it's one way of providing inline comments. The word s" consumes characters up to a terminating ", providing one kind of string literal. Parsing Forth, by design, is connected to both compiling and interpreting Forth.

The intertwined semantics and syntax of Forth seem sufficiently different from most languages to justify different terminology.

My personal hope is that this type of development will lead to the solution of one of the biggest problems with neural networks: their intransparency.

If the result of the learning and optimization is not just a bunch of weights in a graph, but a readable algorithm, that would be a huge step forward into seeing what was really learned. Also, the results might be more stable against the usual Deep Learning attacks.

Of course, the result would read more like disassembled machine code, but that's still better than what we had before. Human tasks might then include finding good variable names, rearranging the code for clarity, etc. That is, typical reverse engineering work.

This perspective strikes me as far too optimistic, for mostly the reasons you describe. I don't think evolving a general purpose programming language (even if not Turing-complete) is likely to produce more comprehensible systems than evolving a matrix, and in fact I would expect the opposite. Reverse engineering benefits from knowing that the original author was a human that can only handle so much complexity at once. Reverse engineering this sort of code will be more like molecular biology, where everything still depends on everything but you don't know how anymore, as opposed to linear algebra where the relationships are at least regular.

So does this combination procedural language + neural net architecture allow random modification of FORTH words or does it only allow random use of pre-defined subroutines with random values for parameters?

Random modification / creation of random algorithms sounds like Doug Lenat's Eurisko. The use of random values for parameters in a pre-defined subroutine sounds like a contraint propagation language like Prolog. I guess the random use of a pre-defined set of subroutines is similar to a system that does load balancing for choice between various algorithms instead of different machines.

It manipulates "sketches" which seem to act as a template and search strategy. E.g. for the word algebra problem, the neural net is told to look at the top 4 stack elements and figure out how to arrange a pair of arithmetic operations (the sentence is first "parsed" by a RNN.)