5 ms·

Programming with a Differentiable Forth Interpreter (2016)

104 points by ghosthamlet 9y ago

exikyut 9y ago
Discussion from 2016: https://news.ycombinator.com/item?id=11766092 https://news.ycombinator.com/item?id=11766092 I also found this article on differentiable programming: https://pseudoprofound.wordpress.com/2016/08/03/differentiable-programming/ https://pseudoprofound.wordpress.com/2016/08/03/differentiab... but a foundational TL;DR would be highly appreciated.
- sedachv 9y ago
  I think Richard Fateman's paper on the subject is a good introduction: https://people.eecs.berkeley.edu/~fateman/papers/ADIL.pdf https://people.eecs.berkeley.edu/~fateman/papers/ADIL.pdf
MaxBarraclough 9y ago
> 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.
- 317070 9y ago
  > 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 https://en.wikipedia.org/wiki/Model_predictive_control
  - MaxBarraclough 9y ago
    > 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.
    - astrobe_ 9y ago
      > 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).
      - MaxBarraclough 9y ago
        > 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'.
        richard_todd 9y ago
        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.
- noelwelsh 9y ago
  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.
  - jacobush 9y ago
    ... 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.
    - aje403 9y ago
      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.
      - 0xdeadbeefbabe 9y ago
        On that different topic, real progress starts the moment it is not seen as AI.
- vog 9y ago
  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.
  - andrewflnr 9y ago
    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.
- rapidcheckout 9y ago
  > 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 https://arxiv.org/abs/1608.04428 The main takeaway is that gradient descent is not a silver bullet for searching over program space.
whitten 9y ago
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.
- sehugg 9y ago
  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.)
deleted 9y ago
[deleted]

104 points by ghosthamlet 9y ago

Discussion from 2016: https://news.ycombinator.com/item?id=11766092 https://news.ycombinator.com/item?id=11766092 I also found this article on differentiable programming: https://pseudoprofound.wordpress.com/2016/08/03/differentiable-programming/ https://pseudoprofound.wordpress.com/2016/08/03/differentiab... but a foundational TL;DR would be highly appreciated.

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

MaxBarraclough 9y ago

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

317070 9y ago
> 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 https://en.wikipedia.org/wiki/Model_predictive_control
- MaxBarraclough 9y ago
  > 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.
  - astrobe_ 9y ago
    > 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).
    - MaxBarraclough 9y ago
      > 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'.
      - richard_todd 9y ago
        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.
noelwelsh 9y ago
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.
- jacobush 9y ago
  ... 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.
  - aje403 9y ago
    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.
    - 0xdeadbeefbabe 9y ago
      On that different topic, real progress starts the moment it is not seen as AI.
vog 9y ago
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.
- andrewflnr 9y ago
  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.
rapidcheckout 9y ago
> 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 https://arxiv.org/abs/1608.04428 The main takeaway is that gradient descent is not a silver bullet for searching over program space.

whitten 9y ago

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.

sehugg 9y ago
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.)

deleted 9y ago

[deleted]