{'fraction_non_alphanumeric': 0.030684049147420202, 'fraction_numerical': 0.007985352833476718, 'mean_word_length': 4.613422486379395, 'pattern_counts': {'":': 1, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Formal Fields: A Framework to Automate Code Generation Across Domains

Code generation, defined as automatically writing a piece of code to solve a given problem for which an evaluation function exists, is a classic hard AI problem. Its general form, writing code using a general language used by human programmers from scratch is thought to be impractical. Adding constraints to the code grammar, implementing domain specific concepts as primitives and providing examples for the algorithm to learn, makes it practical. Formal fields is a framework to do code generation across domains using the same algorithms and language structure. Its ultimate goal is not just solving different narrow problems, but providing necessary abstractions to integrate many working solutions as a single lifelong reasoning system. It provides a common grammar to define: a domain language, a problem and its evaluation. The framework learns from examples of code snippets about the structure of the domain language and searches completely new code snippets to solve unseen problems in the same field. Formal fields abstract the search algorithm away from the problem. The search algorithm is taken from existing reinforcement learning algorithms. In our implementation it is an apropos Monte-Carlo Tree Search (MCTS). We have implemented formal fields as a fully documented open source project applied to the Abstract Reasoning Challenge (ARC). The implementation found code snippets solving twenty two previously unsolved ARC problems.


Introduction
In this introduction we briefly review some relevant work in both code automation and machine reasoning. In section 2 we introduce formal fields as a set of necessary elements to do code execution across domains. In section 3 we have a closer look at the language. In section 4 we study the efficiency of the code searching algorithm and point out other ideas not yet implemented. In section 5 we summarize results of the implementation to the ARC challenge. Full results are available on github (Basaldúa 2020). Finally, we discuss how evaluating code in the context of formal fields leads to a pragmatic definition of understanding and how important the distinction between not knowing and not un-derstanding becomes if we intend to build multi-domain lifelong learning systems.

Automated code generation
Automated code generation, under different names, is one of the oldest problems in AI. In the 70s (Manna and Waldinger 1971) suggest theorem-proving to define specifications for automated programming and induction to construct programs with loops and recursion. You can find more historical examples in the introduction of (Devlin et al. 2017).
With the recent advances of Deep Learning (DL), the field, mostly under the name neural program synthesis, has experienced noteworthy progress. Key ideas start with neural Turing machines (Graves, Wayne, and Danihelka 2014), which extend the capabilities of neural networks by coupling them to external memory resources which they can interact with by attentional processes. (Zaremba and Sutskever 2015) add reinforcement learning to the idea and (Devlin et al. 2017) double the attention mechanism to adapt to noisy conditions.
It is worth noting that in code generation, DL is not as dominant as in other AI fields. If we clearly separate the searching background and compare different algorithms  including linear programming and discrete satisfiability solving, we see that "classical" approaches still play a major role. Best approaches are probably hybrid. In our implementation we do not use DL, but identify specific targets for deep reinforcement learning in future implementations.
A survey paper on the field (Kant 2018) concludes: "While it is still far from being solved or even competitive with most existing methods, neural program synthesis is a rapidly growing discipline which holds great promise if completely realized." Applying Reinforcement Learning (RL) to a program execution framework using NN is described in (Graves et al. 2016) and there is also previous work on learning to code from examples in (Zaremba et al. 2016). Using MCTS as a general optimizing algorithm to do AutoML is described in AutoML-Zero (Real et al. 2020) and MOSAIC (Rakotoarison, Schoenauer, and Sebag 2019).
For completeness sake, we mention approaches focusing on computer languages used by humans. Deep coder (Balog et al. 2016) predicts properties of the program by fitting outputs from inputs end to end with a neural network. Stratified synthesis (Heule et al. 2016) synthesizes the semantics of instructions whose semantics are unknown by bootstrapping from a set of instructions whose semantics are known. TransCoder (Lachaux et al. 2020) is a transpiler using unsupervised machine translation across high level languages trained on large data from source code repositories. Using a constraint solver (Pu et al. 2017) fit Python programs to match input-output examples.
In this article we use the term Automated Code Generation (ACG), since the neural part is not essential, and narrow it down to the case where: 1. The code is generated as a solution to a given problem.
The solution returned by the code can be evaluated by some function. 2. The code can be explicitly described in source form. It is a sequence of instructions rather than a set of arguments or weights used by some other program. 3. Once found, the code runs independently and its resource use is similar to an efficient human written program.

Machine reasoning and lifelong learning
In the discussion we advocate how formal fields are instrumental to build complex lifelong reasoning systems. This builds on top of some ideas we briefly introduce here. Semantic computation can be traced back to the origins of AI with Quillian's semantic memory(Minsky 1968). Later semantic networks (Sowa 1987) lead naturally to the need of a description logic (Baader et al. 2003). A classic approach to computer semantics has been storing information as semantic triples, e.g., (Miller 1998) and using some formal reasoning system to do inference with them. As the database grows, it inevitably becomes brittle, among other things because of its inability to manage uncertainty. There is also a deeper problem, the Symbol Grounding Problem (SGP). In the words of (Harnad 1990), it is the problem of making the semantic interpretation of a formal symbol intrinsic to the system, rather than just parasitic on the meanings in our heads. Despite claims about the SGP being solved, after reviewing fifteen years of SGP research, (Taddeo and Floridi 2005) concluded "All the strategies are semantically committed and hence none of them provides a valid solution to it." Shortcomings of current approaches to DL have been pointed out recently, e.g., (Marcus 2018). We precise "current approaches" because it could be argued that many limitations are not inherent to DL but related to how we use (and not re-use) learning. In an influential work (Bottou 2014) suggests a way to keep the best of both approaches: "Instead of trying to bridge the gap between machine learning systems and sophisticated 'all-purpose' inference mechanisms, we can instead algebraically enrich the set of manipulations applicable to training systems, and build reasoning capabilities from the ground up." In this direction, some efforts include (Garnelo, Arulkumaran, and Shanahan 2016) and (Hudson and Manning 2019) in the field of visual reasoning. The necessity to scale up to complex systems by using just one model is also identified in "One Model To Learn Them All" (Kaiser et al. 2017), a model architecture containing convolutional layers and an attention mechanism for multiple domains.
Formal fields are extremely efficient to run and hard to search. Therefore, reusing learned knowledge is key to building complex formal field based systems. This introduces the need for lifelong learning (Thrun 1998). In the same book chapter we find the following definitions: • Learning: Given a task, training experience and a performance measure, a computer program is said to learn if its performance at the task improves with experience.
• Lifelong Machine Learning (LML): LML, considers systems that can learn many tasks over a lifetime from one or more domains. They efficiently and effectively retain the knowledge they have learned and use that knowledge to more efficiently and effectively learn new tasks.
Recent work (Silver, Yang, and Li 2013) advocates for "more seriously considering the nature of systems that are capable of learning over a lifetime." A phenomenon (not only) related with lifelong learning is catastrophic forgetting. Originally known as catastrophic interference, it is described as "New learning may interfere catastrophically with old learning when networks are trained sequentially." (McCloskey and Cohen 1989). The problem is addressed with different approaches, e.g., (d'Autume et al. 2019).

The formal fields framework
The formal fields framework is a compilation of all the necessary elements to do ACG, both running code and searching programs that solve problems.

Prerequisites
We discuss language details later, for the definition of formal fields, language types, primitives and structure are introduced here. Table 1 summarizes the prerequisites and introduces the notation.
2.1.1 Types All arguments and returned values are strictly typed. All types except tuples are tensors. Tuples are ordered structures combining any types, including other tuples. Types support inheritance. Inheritance is also used implicitly: e.g., Tensors with a shape are inherited from generic tensors, numerical conversions are automatic from integer to floating point and from a smaller precision to a bigger precision. Inherited types can be used as arguments for all their ancestor types, but not the other way round. I.e., the behavior is covariant in the return types and contravariant in the arguments.

Primitives and FSL
A primitive is a function. Primitives are strictly typed. The set of primitives in a field is called the Field Specific Language (FSL).

Kinds
A kind is a data type that serves a purpose across the whole system. It can also have its own primitives. If it does, they will be included in the FSL. It has some resemblance with a class in computer languages (combining code and data), but, unlike objects of a class, instances of a kind are just data and have no methods.
For example: A wave is a kind. Speech is a wave. Speech to text, text to speech, speech to speech, are examples of fields.
2.1.4 Domain (X) and range (Y) A field has two special kinds: X and Y also referred to as domain and range. There is no limit on how complex a kind can be or how many types the primitives in the FSL use. These two kinds are special because they define both ends of a code snippet. A code snippet p is a function p(x ∈ X) → Y .

Code structure
In the formal fields framework code is a sequence of instructions that runs once. Conditional branching and iteration is done as discussed in section 3. The mechanism used to pass arguments to functions is a stack. Any execution tree can be written as a sequence. In higher level languages compilers translate source code into sequences of instructions. Both are functionally equivalent. Writing sequences directly is less human friendly, but still human understandable and removes overhead. A language kernel includes primitives for stack manipulation that are available in the FSL of any field: E.g., pushing constants, splitting tuples, swapping top elements, . . .

Primary structure: opcodes
An opcode is an executable code instruction. An opcode can be a primitive, which is a function, or a constant, which can be viewed as a function without arguments defined in the kernel.

Cores
A function that executes code is called a core. Code, in general, is any sequence of opcodes. There is a kernel functionĉ(s, o , L) → t ∈ T where s is a state of the stack, o is a sequence of opcodes and L is a FSL. The initial state of the stack s contains an element x ∈ X. This function can return any type in T , the set of types used in L.
The core checks types and errors in function calls and immediately stops on error. An error is just a kernel type and is in T .
In a field, this function becomes c(s, o ) → Y where Y is the set of sequences of Y . Note that the language is part of the field and not an argument anymore. More importantly, we are only interested in the opcodes that return y ∈ Y and we are interested in all of them, not just the last one. Possible constants of type Y in the code are not included as results.
2.2.3 Tertiary structure: code snippets A code snippet is a sequence of opcodes p ∈ O such thatĉ(x, p, L) ∈ Y This implies that, at least for that given x ∈ X it produces an error free result. The snippet is what we would less precisely call a program. ACG is about finding code snippets. We also define P as the space of all snippets.
2.2.4 Secondary structure: code items A code item is a minimal snippet. I.e., a snippet that only has one opcode, the last one, returning an y ∈ Y . Code snippets are built as sequences of items rather than one opcode at a time. Unlike code snippets which run end-to-end from X to Y , items run from some initial stack state s to Y . This state s is, initially, some x ∈ X and later becomes the stack state left by items running previously.

Formal field
A tuple (X, Y, L) where X, Y are two kinds and L is a FSL is called a formal field. The field has other things provided by the framework, e.g., a core and a kernel language that are shared by all the fields in the framework. The field provides the complete functionality to run code across two kinds. The implementation also provides some utilities to compile and decompile code to a human readable format, save and restore state to compute trees of snippets reusing previous runs, etc.

Formal relation
Formal relations implement supervised learning using formal fields. Here we systematize the necessary parts, in section 4 we describe how search works in our implementation.

Evaluation function
A function e(ŷ, y) → IR used to compare two elements in the range: the computedŷ and some ground truth y is called an evaluation function. Note that this function operates element-wise. It can be aggregated by some other function over a complete dataset. Also note that there is no restriction on how complex an element is, an element can be a pixel, an image or a batch of images.

Codebase
all snippets run on their example x i and produce the same result a hypothetical ground truth function y(x i ) would.
The codebase is used to create an initial set of code items by splitting the snippets and applying mutations to the resulting items. The codebase is also used to establish prior values for the original and mutated items.
2.4.3 Prior function A function u(q, B) → IR where q is a code item and B is a codebase is called a prior function. During search, each node defines some code item appended to a code snippet (the shortest path from root to its parent). Prior functions assign prior values to nodes. These prior values, combined with rewards, determine the order in which nodes are visited.

Value function
x ∈ X is an element in the domain, p ∈ P is a code snippet, y(x) ∈ Y is the ground truth value corresponding to x, and M = IR k is a value space of dimension k, is called a value function. Value spaces are multivariate because univariate representation cannot express the complexity of intermediate values (see 4.1). Note that the value function not only evaluates the finalŷ = p(x), but all the y = c(x, p) returned by each item in the snippet. The value v ∈ M of a node is converted later into a reward by the reward function.
A value function can be handcrafted, using such things as absolute evaluation: e(p(x), y), improvement by the last item e(ŷ t , y) − e(ŷ t−1 , y), . . . . An element x can include more than one examples, resulting in more computed values over all the examples (worst, mean, best, . . . ) for each of the previous, etc. Besides handcrafting, a deep neural network approach is suggested in section 4.

Reward function
The reward is used to guide search. After expanding a leaf, it propagates backwards from the last visited leaf up to the root node. The reward function is learned from a dataset built from the codebase (positive rewards) adding random mutations of snippets and snippets running on wrong domain elements as examples of negative rewards. In our implementation, the learning algorithm is Xgboost (Chen and Guestrin 2016). (F, B, e, u, v, w) where F ia a formal field, B is a codebase in that field, e, u, v, w are: evaluation, prior, value and reward functions is called a formal relation. A relation is all you need to do ACG. All other things: cores to run the snippets and a search algorithm are implemented in the framework for all relations in a multifield system. A field can be used in more than one relation. Table 2 summarizes the complete framework.

Bebop, a single-pass ACG language
The field of designing formal languages intended for symbolic computation and creating programs by other programs dates back to the origin of Lisp (McCarthy 1978). Unlike search (of programs or whatever) where a sound mathematical theory can be referred to as an optimal (most of the times impractical) gold standard, designing a language is based on simplifying and extending previous designs. In the case of languages for ACG, besides Lisp there are not many examples. Bebop is the implementation of the ideas described here. Bebop has a fully functional proof of concept implementation in Python (Basaldúa 2020) and an in-progress industrial level C++ implementation (Basaldúa 2017).
Reward function Formal relation (F, B, e, u, v, w) Field, codebase and functions

Language design considerations
The language grammar implemented in the framework is minimalistic and predictable resource-wise. This comes at a price as we discuss here.
3.1.1 Curbing hypothesis space When exploring our hypothesis space P , the most important hurdle comes from Church (Church 1936) and Turing (Turing 1937). The halting problem, at the time known as Entscheidungsproblem. As Turing immediately realized: "In a recent paper Alonzo Church has introduced an idea of effective calculability, which is equivalent to my computability, but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem. The proof of equivalence between computability and effective calculability is outlined in an appendix to the present paper." Oddly, the key idea that gives sense to AI, the idea that all computation systems, including biological, are equivalent also introduces the biggest hurdle: We have no way to know what a program will return other than running it. It may take infinite or practically infinite time to run and that running time is unpredictable too.
We could limit the number of instructions a program can execute before we arbitrarily declare it failed, or similar ideas. But, we considered a simpler although extreme measure: removing conditional execution completely.
3.1.2 How conditionals are implemented A good indicator that the idea is feasible are biological systems. Biological systems are built on top of code which is a sequence of codons (groups of three base pairs) executed in a single pass. The way nature does conditionals is using inhibition, epigenetics and other mechanisms. This is equivalent to setting weights to zero (inhibition) or connecting inputs of artificial neurons to memory cells representing some state (epigenetics). It can be done using just arithmetic without conditional jumps.
Another way to do conditionals is exploiting the richness of the type system. On the simplest level, a primitive can do things like detecting all the red elements in a picture returning them as a tuple, another primitive can take this tuple and filter only those vertically symmetric, etc. The language is just defining a pipeline of primitives that iterate internally.
A more complex example, like a shape moving over an image and stopping when some condition happens, can be represented by a primitive that takes a tuple of (shape, position, movement) and returns a tuple of the same type. Initially, movement is a vector indicating a direction. After the condition is satisfied, movement becomes (0, 0) and all subsequent executions do nothing.
Finally, iteration is an important use of conditional branching. Having no explicit looping instructions is not a functional limitation, unrolling loops is a common program optimization technique. Formal fields search code snippets by adding code items to existing snippets. Since there is no limit on how complex an item can be, there is no limit on how complex a loop can be. Therefore, when the evaluation sees some advantage in adding the same item again and again rather than doing something else, a snippet will be doing iteration, possibly combined with inhibition. Many algorithms will not show this gradually improving behavior that favors finding them. This evolutionary approach to coding finds solutions that are different from what humans would code, a usual behavior of machine learning algorithms.
3.1.3 Failing fast As mentioned, snippets have to run to be evaluated. There are two major incentives in running fast: 1. Snippets are the final product used for building lifelong learning systems and 2. Search should be able to run billions of snippet candidates on reasonable experimental settings.
Error is a normal return value for code and should be forced as early as possible. The kernel implements a Halt and Catch Fire (HCF) instruction that immediately breaks returning an error type. Primitives should use it as much as possible. Errors are raised by type checking and should also be raised in primitives by unexpected argument values, including just something becoming too big. E.g., There may be primitives repeating something n times. These primitives running on their own results can easily produce something gigantic, breaking it as soon as possible is essential.
3.1.4 Expressiveness vs. practicability tradeoff By removing conditional execution we have completely avoided the halting problem and made the hypothesis space "just" a combinatorial problem, like most machine learning problems. Assuming we have: structure, a fitting mechanism and the space contains enough "good solutions", the method is practical.
More flexible languages would be more elegant humanwise and achieve more with less code, Lisp being the best example, but besides textbook implementations of trivial programs extending themselves, we do not know how to code in these languages automatically. There are examples of translation across languages (formal to formal) or fitting parametrized programs to given outputs, but that does not match the definition of ACG (informal to formal, i.e., intelligent).
We call this the "expressiveness vs. practicability tradeoff": We decided to go practical first and later maximize expressiveness without compromising practicability.
Minsky's influential essay on language design (Minsky 1967) already stated how expressiveness can build on top of rigid grammar, just here "programmer" is a machine. "A rigid grammar need not make for precision in describing processes. The programmer must be very precise in following the computer grammar, but the content he wants to be expressed remains free." 3.1.5 Primitives, combination and abstraction A classic textbook on formal languages (Abelson, Sussman, and Sussman 1996) arranges design considerations in: 1. Primitive expressions: which represent the simplest entities the language is concerned with.
2. Means of combination: by which compound elements are built from simpler ones.
3. Means of abstraction: by which compound elements can be named and manipulated as units.
Bebop's minimalistic design in those terms is: Primitive expressions are at the core built on top of type inheritance and tuples. The means of combination is a sequence of opcodes that runs once. This is functionally equivalent to a noconditional execution tree. Finally, the means of abstraction are: 1. the idea of code items and 2. primitives written in Bebop, supported only in the Jazz implementation.

More on program structure
We already introduced primary structure (opcodes), secondary (items) and tertiary (snippets) formally in section 2. Here we describe some ideas that are key to create code items using the snippets in the codebase.
The first step is splitting the snippets. Breaking the sequences to make them finish at every non constant opcode returning an y ∈ Y . Then, building an "item base" with precomputed priors.
3.2.1 Alleles and constant fitting Two code items that are identical in their primitives but differ in the values of constants are known as alleles. When an item contains constants, that opens the question of constant fitting. The current implementation has two approaches to it: 1. Just copying successful alleles as they are, possibly more than one letting them "compete" in the search. 2. Only in case the evaluation function can identify the ground truth y to be reachable from the last computed element y t , the evaluation function can modify the item. E.g., if the solution to a problem is almost correct, just what is blue should be yellow, the evaluation function can append a "and recolor blue to yellow" suffix, "blue" and "yellow" being some constant arguments passed to a "recolor" primitive. Otherwise, once a code item is inserted in the search tree it is not modified. This is an opportunity for future improvement.

Form and isomorphism
The sequence of argument types and return types in a code item is known as its form. Two code items sharing the same form are known as isomorphisms.
There is a necessity to explore items that are not in the codebase. This is done by creating new items changing functions of existing items one at the time by other functions in the FSL that maintain the form. Other mutations include insertion and deletion of opcodes. These "never seen before" items have their priors assigned based on similarity to successful items. This may look very limited (one mutation only), but it has to be seen as a lifelong learning process. New items are tried and hopefully included in successful snippets and end up in the codebase. In the next generation we see mutations of successful mutations. Exploring possibly malformed items exploits the robustness of the framework: Everything in the tree runs from root, what doesn't, doesn't make it into the tree.

Generating code by search
We build code snippets by searching a tree starting at an empty root node. Every node represents appending a code item, and we have a formal relation R which implies: 1. We have a formal field, X → Y with a FSL and can run code on it.
2. We have a set of code snippets B from which we built a set of code items I as described in 3.2 with prior values defined over all items by a prior function u(q, B) → IR.
3. We have a value function v(x, p, y) → M and a reward function w(m) → IR to guide the search.

4.
We have an evaluation function e(ŷ, y) → IR to compare the output of a snippet p(x) with some ground truth y.

Efficiency of the search
After tackling the halting problem, we have to reckon with two more hurdles in order to understand ACG: 1. Even if running an item is a deterministic function, when we abstract the field away from the search, at the search level we have no understanding of what the program is doing. We cannot expect the program to reach a solution by gradually approaching the expected y like an optimization algorithm would do on a regular problem. We have to model that uncertainty (the search's ignorance on what the program is doing) as a Markov Decision Problem (MDP). Basically, accepting that what we evaluate at some stage t, the y t * ∈ Y * , is not the real state of the problem, but just a proxy. The real state would be described by some strong metric like the length of the optimal snippet that reaches y from y t . Such strong metric is, of course, not computable.
2. The only framework known to determine the value of our decision problem (what is the best item to append at each node) is based on backward induction. We can, at best, apply it to already found snippets, but it is not computable during search. Gathering knowledge about the "regularity" of the evaluation along the items of a (successful vs. unsuccessful) snippet is what we do when we learn the reward function using the codebase. This explains why learned reward functions work better than handcrafted ones, it is not about idealizations on how to reach a goal, it is about learned knowledge from the snippets that do vs. those that don't. Also, we don't even know if a snippet such that p(x) = y can be built with the DSL and the codebase at all, but we presume that we could always extend the language and the codebase to make that possible.

UCB as an approximation to Bellman value
The analysis of the value of each decision at a node (state) in terms of the immediate reward and the discounted values of its successor states is Bellman's equation (Bellman 1957a) formulated for a MDP (Bellman 1957b).
As mentioned, it is not computable in our case. The reason we refer to Bellman's equation is because what we use instead, Monte-Carlo methods, should be viewed as an approximation to it.
As stated in (Sutton and Barto 1998): "We would like to apply the approach of stochastic gradient descent (SGD) of the Bellman error, in which updates are made that in expectation are equal to the negative gradient of an objective function. These methods always go downhill (in expectation) in the objective and because of this are typically stable with excellent convergence properties. Among the algorithms investigated so far in this book, only the Monte Carlo methods are true SGD methods." When traversing the tree forward, the selection of the next node to visit uses the UCB formula (Kocsis and Szepesvári 2006) which is an evidence based balance between exploration and exploitation using a confidence interval of the binomial proportion.
At every node s , we select his child s i that maximizes: u(h + log((n +f )/f )) √ n /(n + 1) + g(r/n) where u is the prior value of the child, n is the number of visits of the child, r is the reward of the child, n is the number of visits of the parent and f, g, h are constants.
Under the following assumptions: 1. The reward is a true reward, e.g., a game won or lost rather than a value assigned by some learned reward function. 2. Or, at least, in expectation the rewards obtained from random walks starting at a node are proportional to the probability of the node being part of a successful snippet. In other words, the stochastic process, when adjusted to be a probability is an unbiased estimator of success. The UCB formula (1) is a true approximation of the Bellman value. And that approximation will have a mean absolute error proportional to 1/ √ n where n is the number of visits through the node.

The need for regularization
Another central question in supervised learning is: We want our model (snippet) to perform well on unseen data. Techniques like crossvalidation are an external layer to what we are discussing in this paper and should be used in combination with the formal fields framework. Here, we have a closer look at what overfitting is and describe a simple regularization technique used in our implementation.
By aggregating the evaluation e(ŷ, y) → IR over a set of predictions {ŷ i } ∈ Y comparing them element-wise with their ground truth values y i ∈ Y , we define a loss function l(y) → IR.
For three snippets, p(x) the best snippet found, p(x) the best snippet in P and our hypothetical ground truth function y(x), we can decompose the loss of p(x) as: l(p(x)) = l( y(x)) + Λ + λ where Λ = l(p(x)) − l( p(x)) is difference between the loss of the snippet and the loss of the best snippet existing in P and λ = l( p(x)) − l( y(x)) is the difference between the loss of best snippet in P that of the ground truth function.
Note that λ is the term representing the shortcomings of the FSL and the codebase, i.e., the underfitting, the lack of expressiveness and Λ represents the shortcomings of our search, the overfitting. Overfitting is a function growing with the degree of freedom in the snippet and decreasing with the degree of freedom in the range. The first idea to reduce overfitting is shortening the snippet.
The constants in the UCB equation 1 allow for adjustment between exploration and exploitation. Increasing exploration (going wide) tends to make shorter snippets, but the optimal balance may be compromised if exploration is used as regularization. Therefore, we introduced a more independent mechanism, a discount in the reward during backpropagation. This reduces the absolute values of the rewards propagated from longer snippets as they approach the root node compared with those of shorter snippets that obtained the same reward.

Using a Monte-Carlo Tree Search variant
Our implementation (Basaldúa 2020) uses an MCTS algorithm (Browne et al. 2012) using the canonical UCB function as described in equation 1 with one major modification. The simulation stage is replaced by a prediction of the reward using the reward function.
Algorithms for which an accurate simulator of the environment is not available, as it is the case of most real-world problems, cannot implement the simulation phase and have to replace it by the evaluation of some model. The field is known as model-based reinforcement learning a notable example is (Schrittwieser et al. 2019).   (Schrittwieser et al. 2019) has been very influential in the design of the search. In many ways we opted for minimalism and wanted to gather experience using "lower hanging" evaluation and reward functions, but we plan to implement more deep learning into the framework, including a MuZero engine.
4.3.2 Learning with self-modifying policies In modelbased RL, we do not have a simulation policy anymore, but we do have a tree policy. At the moment, both priors and constants in code snippets are static, re-using knowledge from the tree search to fit these constants has a huge potential. The idea of RL with self-modifying policies is described in (Schmidhuber, Zhao, and Schraudolph 1998) as "A learner's modifiable components are called its policy. An algorithm that modifies the policy is a learning algorithm. If the learning algorithm has modifiable components represented as part of the policy, then we speak of a selfmodifying policy (SMP)". These ideas have already been applied to MCTS in go (Basaldúa et al. 2013).

Training an autoencoder
The value function in our implementation is handcrafted, that requires domain knowledge and is probably worse than a deep learned function. Exploiting the fact that we have snippet results and ground truth values in the same kind, we could train an autoencoder to learn how to transform the former into the latter. The intermediate k-dimensional embedding becomes the value space. Then, we take only the encoding part and use it as a value function.

Experimental results
We very briefly describe the challenge our open source Python implementation tackles. Detailed results including code snippets, running times, solutions, parameters, etc. can be found in (Basaldúa 2020).

The ARC challenge
(Chollet 2019b) approaches intelligence as "skillacquisition efficiency". Rather than measuring it using performance at specific tasks, he advocates for performance at tasks never seen before.
To test state of the art algorithms (or humans) in general problem solving, (Chollet 2019a) created a set of intelligence tests in which an agent is expected to learn by a few examples a pattern that explains how some pictures were transformed into a given solution. Then, a new picture is shown without the solution. The agent is expected to apply the learned pattern to produce the hidden solution. Only a 100% perfect match is considered valid.
This challenge was proposed as a three month long Kaggle competition finishing May 28, 2020, where solutions, submitted as code, ran over 100 unseen problems.
Since during three months almost a thousand participants were allowed to submit solutions three times a day, by the end of the competition the tasks were not really unseen. Except for the winner, who built a search to create four instruction long programs in a domain specific language of his invention, all other submitted solutions were ensembles of "whatever worked" favored by the possibility of team merging of solutions found by trial. This explanation is based on what the authors themselves shared on the Kaggle platform. The winner mentioned spending time optimizing multi-core C++ code for the search part and guessing what the unseen ideas could be to implement them in his language. His code solved 20 out of the 100 hidden problems.

Results
We took a completely different approach given the short time frame and the need to implement everything. We did not give too much thought to the FSL. On the public dataset of 800 problems we built something that could solve a bunch of easy problems and then, gradually, extended it to some less easy cases. We finished our implementation four days before the deadline and ran 5 experiments from the May 24 to 27.

Result summary Total running time (hours)
70 Problems believed to be solved but "wrong" 4 Total problems solved 168 Total previously unsolved problems solved 56 Unique previously unsolved problems solved 22 Table 3: Aggregated results from five experiments using different settings.
The system performance was very slow, a single threaded pure Python implementation, somehow mitigated by 70 hours of total runtime. Some of the snippets labeled as "wrong" actually helped fixing the dataset. The experiments focused mostly on unsolved problems with a few already solved problems as controls. The search solved controls in different ways than the snippets already in the codebase. The total number of previously unsolved problems found, not counting repetitions across experiments, was 22. We would have considered anything above zero a success. Table 3 shows aggregated results.
There is no way to make a fair comparison with what other participants achieved. It would be necessary to know the size of the set of solvable problems for our unrefined and incomplete FSL. We know it can solve at least 131 of 800 problems, because that is the size of the codebase including the snippets found in the experiments. It is hard to code new solutions without extending the FSL, 150 could be a reasonable estimate. All other problems are just impossible without extending the FSL. To be fair, the same would happen to participants who built their own domain specific languages.

Discussion
So far, we have completed the description and analysis of the formal fields framework. We finish with some thoughts on how the framework fits into our idea for multi-domain lifelong reasoning systems.

Towards a pragmatic definition of understanding
Informally, before even defining what understanding is, most people, especially from outside the field, would doubt computers can understand at all. We could give them examples from a narrow field, classic computer chess, and give them the opportunity to experience how a simple minimax search, as it gets deeper, shows intelligent behavior. The program discovers strategy that has not been taught to it, easily beats its author, etc. The chess engine can be used to play, but also to solve problems, create new problems, return insights on strategic questions. One could write a five hundred page chess treaty from the discoveries made by a program with fifty lines of code defining the rules of the game. The same people would probably concede, Okay, the computer understands chess, but that is a narrow domain, it is not selfaware and would not invent a chess metaphor applied to another field.. We agree that is a fair point, just let's walk one step at a time and discuss what "the computer understands chess" means.
As a first approach: 1. We have a formal field named chess in which a language to write functions, a game state and actions have definitions.
2. We have a function f (s) → A named the rules returning a set of actions a ∈ A (legal moves, priors, . . . ) for each game state s.

We have an algorithm named minimax-search.
We could say: "Minimax-search understands the rules within the field of chess." Why is minimax-search so smart it can understand? Because it is an optimization algorithm, it can run, evaluate, optimize, fit, . . . . It is understanding the function since it is applying it and considers all implications relevant to optimizing. It is easy to argue this is a very narrow definition of understanding, but it is hard to argue this is not understanding. A very narrow definition is all we need. By abstracting the problem away, we have converted it into an optimization problem, something a computer definitely shows evidence of understanding.
Why do we need such a thing at all? Is it just an intellectual tour de force with no practical consequences?
1. In the first place, because we can. We already have a pragmatic definition of learning (see 1.2) and most people would agree it captures the essence of what learning is. Machine learning is a mainstream concept nowadays, it is not controversial that machines can learn. We had "bad experiences" with semantics in the past and not everyone would agree that a computer can understand a symbol, but a function in an optimization algorithm, that is something computers do understand. We can only make progress in machine understanding if we build a definition and then improve it if necessary.
2. More importantly, because we need it. The opposite of understanding is "not understanding" and that is not the same as "not knowing". That distinction is key to advance AI. Humans also don't understand many things and learn to live with it from the cradle. As we advance representing ideas as code, we need a way to establish this difference. Maybe, while we still represent word embeddings as vectors, we don't need it. Could we say "I don't understand this vector."? But then, we only have linear algebra to represent world semantics. If we represent words as code, we have unlimited semantic representation and we can expect a machine to naturally say such things as: "I don't understand this sentence, it doesn't run, I don't know that word, "optimistic molecule" doesn't make sense, . . . " Summarizing, it is always hard to coin an existing word with many nuances into a new formal definition. We argue that it is useful and necessary. It clearly outlines the difference between not knowing and not understanding in a similar way humans do. It is also similar to the accepted definition of understanding used in psychology: "being able to apply knowledge rather than just recalling it" (Bloom and others 1956).

Towards building lifelong learning systems
Formal fields are not intended to be seen as just an algorithm that solves problems in many domains. It is a building block to create lifelong learning systems that integrate all the domains at the same time, using one language grammar, one search algorithm and different FSLs.
The idea has been proven to work and learn from as few examples as a human would need. The Jazz implementation (Basaldúa 2017) under development will provide at least a two decimal orders of magnitude speed improvement, smaller footprint, efficient storage to save, fork or resume the state of any process and scalability across a cluster using technology already implemented in the platform.
Despite having been used on the abstract reasoning challenge first, most ideas have been thought of and tested with natural language in mind since the first open source release of the Jazz platform, Dec 2017. Natural language itself can be seen as code, text as a sequence of words and punctuation that are executable in some field assuming they can be understood within the field. The combination of handcrafted codebase snippets serving as examples, being extended gradually by ACG and the creation of more fields and concepts without having to discard previous knowledge, but building on top of it, is the vision. To reach it, we will have to do more research and software development.

Conclusion
In the first four sections we have introduced a narrow definition of ACG, presented the formal fields framework, discussed the language design and analyzed the efficiency of the search algorithm. The experimental results applied on one of the hardest known challenges, abstract reasoning, show that the whole idea works. All the experimental section is reproducible, code and data, and open sourced in (Basaldúa 2020).
Besides this proof of concept implementation, we have discussed future lines of research to build complex multidomain lifelong learning systems on top of the software stack included in the Jazz platform (Basaldúa 2017).
We also advocate for introducing a pragmatic definition of understanding (see 6.1) as a necessary notion in AI systems in which concepts are represented by code.