Published as a conference paper at ICLR 2018 IMPROVING THE UNIVERSALITY AND LEARNABIL- ITY OF NEURAL PROGRAMMER-INTERPRETERS WITH COMBINATOR ABSTRACTION
To overcome the limitations of Neural Programmer-Interpreters (NPI) in its universality and learnability, we propose the incorporation of combinator abstraction into neural programing and a new NPI architecture to support this abstraction, which we call Combinatory Neural Programmer-Interpreter (CNPI). Combinator abstraction dramatically reduces the number and complexity of programs that need to be interpreted by the core controller of CNPI, while still allowing the CNPI to represent and interpret arbitrary complex programs by the collaboration of the core with the other components. We propose a small set of four combinators to capture the most pervasive programming patterns. Due to the finiteness and simplicity of this combinator set and the offloading of some burden of interpretation from the core, we are able construct a CNPI that is universal with respect to the set of all combinatorizable programs, which is adequate for solving most algorithmic tasks. Moreover, besides supervised training on execution traces, CNPI can be trained by policy gradient reinforcement learning with appropriately designed curricula.
Quality
The paper is very interesting and clearly motivated. The idea of importing concepts from functional programming into neural programming looks very promising, helping to address a bit the somewhat naive approach taken so far in the deep learning community towards program induction. However, I found the model description difficult to fully understand and have significant unresolved questions - especially *why* exactly the model should be expected to have better universality compared to NPI and RNPI, given than applier memory is unbounded just like NPI/RNPI program memories are unbounded.
Clarity
The paper does a good job of summarizing NPI and motivating the universality property of the core module. 
I had a lot of questions while reading:
What is the purpose of detectors? It is not clear what is being detected. From the context it seems to be encoding observations from the environment, which can vary according to the task and change during program execution. The detector memory is also confusing. In the original NPI, it is assumed that the caller knows which encoder is needed for each program. In CNPI, is this part learned or more general in some way?
Appliers - is it the case that *every* program apart from the four combinators must be written as an applier? For example ADD1, BSTEP, BUBBLESORT, etc all must be implemented as an applier, and programs that cannot be implemented as appliers are not expressible by CNPI?
Memory - combinator memory looks like a 4-way softmax over the four combinators, right? The previous NPI program memory is analogous then to the applier memory.
Eqn 3 - binarizing the detector output introduces a non-differentiable operation. How is the detector then trained e.g. from execution traces? Later I see that there is a notion of a “correct condition” for the detector to regress on, which makes me confused again about what exactly the output of a detector means.
Computing the next subprogram - since the size of applier memory is unbounded, the core still needs to be aware of an unlimited number of subprograms. I must be missing something here - how does the proposed model therefore achieve better universality than the original NPI and RNPI models?
Analysis - for the claim of perfect generalization, I think this will not generally hold true for perceptual inputs. Will the proposed model only be useful in discrete domains for algorithmic tasks, or could it be more broadly applicable, e.g. to robotics tasks?
Originality
This methods proposed in this paper are quite novel and start to bridge an important gap between neural program induction and functional programming, by importing the concept of combinator abstraction into NPI.
Significance
The paper will be significant to people interested in NPI-related models and neural program induction generally, but on the other hand, there is currently not yet a “killer application” to this line of work. 
The experiments appear to show significant new capabilities of CNPI compared to NPI and RNPI in terms of better generalization and universality, as well as being trainable by reinforcement learning.
Pros
- Learns new programs without catastrophic forgetting in the NPI core, in particular where previous NPI models fail.
- Detector training is decoupled from core and memory training, so that perfect generalization does not have to be re-verified after learning new behaviors.
Cons
- So far lacking useful applications in the real world. Could the techniques in this paper help in robotics extensions to NPI? (see e.g. https://arxiv.org/abs/1710.01813)
- Adds a significant amount of further structure into the NPI framework, which could potentially make broader applications more complex to implement. Do the proposed modifications reduce generality in any way?