NOTICE: This repo is no longer under active development. All development has been moved to the TypeScript monorepo. Please see the next section for an overview of what we learned developing this version of Gadfly.
TODO
Gadfly is an experimental expression-oriented functional programming language, treewalk interpreter, and development environment. The ultimate goal is to provide a development environment for autopoietic copilot programs. The conventional aspects of the system are inspired by Lisp, Scheme, Smalltalk and Ruby. The (highly) experimental features draw on ideas from cybernetics, symbolic AI, and reinforcement learning as well as more recent research surrounding how to build and orchestrate autonomous agents.
This project and documentation are under heavy development. If you see something is missing, find an error, have a question, or have anything at all to say, please don't hesitate to open an issue or reach out to me directly. For a (slightly) more detailed overview of the project, check out the roadmap
- Contents
- The big idea
- The design
- Programs, theories, machines, and the world
- The language
- Run a script
- Tests
- Notes on the vision
- Notes on the language
- Notes on the interpreter
- Roadmap
- Work in progress
- expression
An autopoietic system is a system that is capable of producing and maintaining itself. Our first primary goal is to bootstrap autopoietic computer programs. Our second goal is to bootstrap autopoietic copilot programs (or just "copilot"). We define a copilot as a long-running program capable of satisfying requests to solve basic, human-level problems in some domain and whose primary user interface is natural language. We roughly define "basic, human-level" as a problem that in the year 2020 could probably be solved by a helpful human assistant but could probably not be solved by any single computer program.
The central idea behind Gadfly is that programming languages and language models have a very powerful (and very natural) kind of resonance. On the one hand, the structure and utilities provided by a programming language and runtime are perfect tools for channeling a language model's reasoning capabilities. On the other hand, the ontology provided by a language model is a beautiful solution to the multi-armed bandit problems that plague automatic program synthesis. A Gadfly program is, to my knowledge, a novel form of neuro-symbolic AI.
The Gadfly
language includes 7 novel keywords--GADFLY
, DAEMON
, RAPTURE
,
THEORY
, ORACLE
, MUSE
, and GHOST
--whose implementations integrate
language models directly into the core of the language.
The keywords GADFLY
, DAEMON
and RAPTURE
are directly related to AI-driven
code generation. The idea is that every child expression of a GADFLY
expression can optionally be wrapped in a DAEMON
. The parent GADFLY
expression is evaluated just like a do
expression with one major difference.
Before a GADFLY
expression returns its value to its parent, it analyzes the
return value, generates feedback about the value, communicates the feedback to
each DAEMON
child, gives the children time to modify themselves according to
the feedback, and then retries the evaluation. If the retries don't yield
satisfactory results, the GADFLY
expression goes into "rapture" by wrapping
itself in a RAPTURE
expression. A RAPTURE
expression is an expression that
is completely controlled by some external power and will ask for directions
before ever evaluating itself, very analogous to a debugger session.
The keywords ORACLE
and MUSE
are basically AI-implemented functions. You can
use them as generic functions, but they exist in the language essentially as
(de)serialization mechanisms for natural language. If you have some natural
language data and you want a structured "response" to it, then you consult the
oracle. If you have some structured data and you want a natural language
response to it, you consult the oracle. In other words, if you have something to
say and want facts, you ask the oracle. If you have some facts and need
something to say about them, you consult the muse.
The keyword GHOST
implements AI-driven control flow. When the interpreter
reaches a GHOST
expression, it asks the AI which branch to evaluate.
The THEORY
keyword is a little bit speculative and will probably not be part
of v0 but the tl;dr is that it's something like an embedded runtime test suite
that's used to "prove" the correctness of return values. See the next section
for some rambling details.
TODO: An example program
This section is mostly WIP and/or notes (some of them stale). I've some vague notions about theories, domains, and machines that feel resonant with the more "concrete" goals of the project, but they've fallen to the wayside as the design has progressed.
To solve a given problem you need a good theory of the problem's domain. We think of a Gadfly program as an evolving theory of a domain. This idea is behind all novel features of Gadfly (the language, runtime, and tooling). Certain keywords in the Gadfly language enumerate (more or less) these novel features.
The daemon
keyword is an expression which takes as its arguments a problem
and a theory. It is technically an iterator (like map
or for
). The daemon
applies the theory to the problem again and again until the problem is solved or
is deemed outside the theory's domain. On each unsuccessful application of the
theory to the problem, the daemon may modify the theory. The problem is simply a
request encoded as a natural language string. A theory is more complicated.
domain A natural language description of the kinds of problems the theory could be applied to.
signals A set of potential observations that could be made about the world that are relevant to theory. In particular, these are the observations required to verify solutions.
sensors A set of functions that, when called, return signals.
effects A set of functions that, when called, created signals in the world.
analyzer A program that can verify solutions. An analyzer is where sensors are called and signals interpreted.
synthesizer A synthesizer is a program that solves problems. A synthesizer is where effects are called.
Gadfly is dynamically and strongly typed. In Gadfly, everything is a
lexically-scoped expression. All expressions return a value and all values
are immutable. An expression is defined as a block, lambda,
predicate, or literal. Comments begin with the #
character and
continue until the end of the line. Whitespace is ignored except to separate
tokens.
For the rest of this section, italic text on a gray background
denotes an
expression signature. For all expression signatures, the *
character
indicates zero or more occurrences of the preceding expression. The +
character indicates one or more occurrences of the preceding expression. The ?
character indicates an optional expression. Unless otherwise noted, "number",
"string", "array", "map", and "lambda" are understood as expressions that
evaluate to that type of value.
At the bottom of each subsection in this section you'll find a brief summary of the ongoing and planned development related to that subsection. For a higher-level perspective, please see the roadmap.
A block is a sequence of expressions delimited by a keyword and end
. A
keyword determines its block's behavior or semantics. Most of the language's
keywords will be described throughout the rest of this section but you can also
find a comprehensive, runnable example in
examples.core.fly.
The simplest block is the do
block:
do expression* end
The expressions are evaluated in order and the value of the last expression is returned.
do
puts "hey" end
2
do
3 + 4
end
end
A Gadfly variable is an expression that resolves to a value by referencing
it. A variable is defined using a def
block and re-defined using a let
block. After a variable is defined it can be referenced in any expression.
def identifier expression end
Defines a variable with the given identifier. The variable resolves to the value of the expression. Variables are lexically scoped. If the variable is already defined in the local scope, it is an error. If the variable is defined in an outer scope, it will be shadowed in the local scope.
def surname "smith" end
let identifier expression end
Re-defines an existing variable with the given identifier. The variable resolves to the value of the expression. If the variable does not already exist, it is an error.
def val "hi" end
let val "goodbye" end
TODO
- Namespace declaration and resolution.
Every value is a string, number, array, map, lambda, or nil.
A string is created by enclosing characters in quotes.
"I am string"
A number is created by writing it out in decimal notation. All numbers are represented as floats internally.
1
0.1
10.0
There is no boolean type in Gadfly. All "boolean" operators take number
operands and treat 0
as false-y and any other number as truth-y. All other
values cause errors when used as a boolean.
An array is created using the array
block and is a number-indexed list of
values. See the arrays section for more details on arrays.
A map is created using the map
block and is a string-keyed dictionary of
values. See the maps section for more details on maps.
A lambda is created using the fn
block and can be thought of as a
parameterized do block or "anonymous function". See the lambdas
section for more details on lambdas.
A lambda is a "parameterized block" that is not evaluated until each time it
is called. A lambda can have zero or more parameters. A parameter is a
name that is defined each time the lambda is called. Parameters are declared
between |
characters. If the lambda takes zero parameters, the |
characters
must be omitted. The arguments to the lambda are the values of the
expressions in the calling block (using the .
keyword) bound to the lambda's
parameters.
fn (|identifier+|)? expression end
When the lambda expression is evaluated, it creates a lambda. The key difference
between a lambda expression and other expressions is that its subexpressions are
evaluated only when the lambda is called. The lambda can take zero or more
parameters. If the lambda takes zero parameters, the |
characters must be
omitted.
. expression* end
Calls the lambda expression. Each subexpression is evaluated and bound to the lambda's parameters. The lambda is then evaluated, returning the value of its last subexpression.
def add
# parameters are a and b
fn |a b|
a + b
end
end
.add
# arguments are 8 and 3, bound to a and b
2 * 4
3
end
map
array 1 2 3 end
fn |n i|
n + i
end
end
A predicate is an expression involving an operator and operands. See the operators section for more details on each operator. An operand is either a predicate or a literal. A literal is an expression without subexpressions (string, number, boolean, variable). A predicate evaluates to a number (because an operator evaluates to a number).
Because predicates cannot include blocks they cannot include function calls. This is somewhat cumbersome to us human programmers, forcing us to write many instances of trivial indirection, but I think we'll see strong benefits for code generation and program synthesis because it will make parse trees simpler. Maybe not, we'll see.
# Not predicates.
fn
std.write "hi" end
end
def val "hi" end
# Predicates.
val
val == "goodbye"
10 > 0 # => 1
100 / 20 # => 5
!val
TODO
- Unary negation seems to be broken right now.
The key difference between branching expressions and other expressions is that their subexpression are evaluated conditionally. The specific behavior of which subexpressions are evaluated depends on the keyword.
Note that branching expressions are not predicates, they may return any value.
if number expression expression end
If the number is truth-y, the first expression is evaluated. Otherwise, the second expression is evaluated. The value of the last evaluated expression is returned.
and (number expression)+ end
For each pair of subexpressions, if the first evaluates to a truth-y value, the
second is evaluated. If any of the subexpressions evaluate to a false-y value,
nil
is returned. Otherwise, the value of the last subexpression is returned.
or (number expression)+ end
For each pair of subexpressions, if the first evaluates to a truth-y value, the
second is evaluated and returned. If none of the subexpressions evaluate to a
truth-y value, nil
is returned.
while number expression+ end
While the first expression evaluates to a truth-y value, the rest of the expressions are evaluated. The value of the last subexpression is returned.
array expression* end
Creates an array whose values are the values of the subexpressions. The array is returned.
array.read array number end
The value of the array at the index of the number is returned.
array.write array number expression end
Clones the array and sets the value at the index of the number to the value of the expression. The cloned array is returned.
array.for array lambda end
For each value in the array, the lambda is called with the value bound to the lambda's first parameter and the index bound to the lambda's second parameter. The value of the last evaluated lambda is returned.
array.map array lambda end
For each value in the array, the lambda is called with the value bound to the lambda's first parameter and the index bound to the lambda's second parameter. An array whose values are the result of each lambda call is returned.
array.filter array lambda end
For each value in the array, the lambda is called with the value bound to the lambda's first parameter and the index bound to the lambda's second parameter. An array whose values are the values for which the lambda call returned a truth-y value is returned.
array.reduce array expression lambda end
For each value in the array, the lambda is called with the value bound to the lambda's second parameter and the index bound to the lambda's third parameter. When the lambda is called for the first value in the array, the first parameter is bound to the value of expression. For each subsequent value in the array, the first parameter is bound to the value returned by the previous lambda call. The value of the last evaluated lambda is returned.
array.push array expression end
Clones the array and appends the value of the expression to the cloned array. The cloned array is returned.
array.pop array end
Clones the array and removes the last value from the cloned array. The cloned array is returned.
array.unshift array expression end
Clones the array and prepends the value of the expression to the cloned array. The cloned array is returned.
array.shift array end
Clones the array and removes the first value from the cloned array. The cloned array is returned.
array.reverse array end
Clones the array and reverses the order of the values in the cloned array. The cloned array is returned.
array.sort array lambda end
Clones the array and sorts the values in the cloned array according to the value
returned by the lambda. The lambda takes two parameters, the values of which are
the values in the array. The lambda returns a negative number if the first value
should be sorted before the second, a positive number if the first value should
be sorted after the second, and 0
if the values are equal. The cloned (sorted)
array is returned.
array.segment array number number end
Clones the array and returns a new array whose values are the values of the cloned array between the first index and the second index (exclusive). The cloned array is returned.
array.splice array number array end
Clones the first array and divides it in half at the index of the number. It appends the values of the second array to the first half, and then appends the second half to the result. The result is returned.
map (string expression)* end
Creates a map whose keys are the strings and whose values are the values of the expressions. The map is returned.
map.read map string end
The value of the map at the key of the string is returned.
map.write map string expression end
Clones the map and sets the value at the key of the string to the value of the expression. The cloned map is returned.
map.delete map array end
The array is an array of strings. Clones the map and deletes the keys of the strings from the cloned map. The cloned map is returned.
map.extract map array end
The array is an array of strings. Returns a map whose keys are the keys of the strings and whose values are the values of the keys of the strings in the map. The new map is returned.
map.merge map map end
Clones the first map and then for each kv pair in the second map, sets the value of the cloned map at the key of the kv pair to the value of the kv pair. Returns the cloned map.
map.keys map end
An array whose values are the keys of the map is returned.
map.values map end
An array whose values are the values of the map is returned.
split string end
Returns an array whose values are the characters in the string.
concat string+ end
Returns a string whose value is the concatenation of the values of the strings.
substring string number number end
Returns a string whose value is the substring of the string between the first index and the second index (exclusive).
TODO
- regular expression engine
TODO
-
std.write
-
io.gets
-
io.err
- WIP
http
-
io.file.read
-
io.file.write
- documentation
TODO
- A Lisp-style condition system but more focused on signaling.
- documentation
Requires go
1.21 or higher. Learn how to install go
here.
go run . <path to Gadfly source>
Try running the examples:
for file in examples/*.fly; do
go run . $file
done
The goal is to have tests commensurate with the maturity of the project and its components. The near term goal is to have something like 100% coverage for the core language features. Basically, this means "all of the keywords and operators". We'll do this incrementally, in phases.
You can run the tests with:
./test.sh
TODO
- WIP Smoke coverage for all keywords and operators
- array
- strings
- map
- branching
- lambdas
- io
- http
- namespaces
- emitters
- exceptions
- variables
- predicates
- Edge-case coverage for all keywords and operators
- Happy-path coverage for at least one robust, traditional Gadfly program.
- Down the road Fuzzing for all keywords and operators
- Imagine a programming language designed from the ground up to be used by language models (LMs).
- An LM wouldn't need to generalize, it could write a new program for each new task it encounters.
- An LM could analyze running programs very quickly, it could modify running programs according to new data.
- Instead of importing code, an LM could search for similar code in a database and then repurpose it.
- Because an LM could analyze running programs very quickly, it could make sense to store all kinds of useful metadata in the parse tree.
- More generally, the parse tree could be something that is constantly manipulated by the LM.
- An LM could outsource subtrees to other LMs, there could be a whole ecosystem built around this idea.
- An LM could evaluate subtrees in parallel and then merge, prune, and recombine them according to certain policies.
- It's looking like the language will (unsurprisingly) be very Lispy. One way to
think about things is that
Gadfly
takes homoiconicity to wild extremes. - Right now the language is dynamically typed, but I feel like it would be better to have static typing. I don't have any great reasons to articulate why I feel that way other than maybe that it adds a ton of metadata to the parse tree. I don't know enough about programming languages to know whether lisps are amenable to static typing.
- I have this vague notion of a
remote
keyword, or something like that, where a subtree is farmed out to the network. I feel like aremote
node could be implemented in any language and basically implement any feature. - The syntax is intended to mirror the parse tree very closely. I imagine that developers will jump around a lot between the two. I want the homoiconicity to be very apparent.
- Everything about the language needs to be ridiculously printable, introspectable, and serializable. I want to be able to seralize the parse tree, wire it somewhere, and then execute it on another machine.
- you have a parse tree as well as metadata surrounding every execution that has ever occurred in the parse tree
- you never edit a node in the parse tree, you only deprecate them
- the parse tree represents a decision making process that the AI will incorporate
- one way to think about how this works is that it uses LLMs and execution history to discretize the continuous decision spac
- one way to think about what the copilot is doing is “how to write a program that proves a fact about the world”
- similar to the previous bullet, there’s a way to think about is synthesizing analytical facts and a fact is a subtree that can prove the thing
- the copilot’s toolbox is determined via lexically-scoped name resolution
- instead of a visual programming environment, you have a programming language which means you can use programming language theory and tools
- a core aspect of a copilot is that it must support delegation to other AIs
- every expression in the parse tree has a natural language representation of why it exists in the parse tree
- every node in a trajectory has a natural language description of it’s scope, it’s arguments, and a recapitulation
- one piece of metadata is “number of active trajectories”
- the parse tree must be fully serializable
- you can think of every subtree as a policy fit for some situation
- a gadflai program has something like sensors or actuators
- leaf nodes are always either facts or sensors?
- a pure function is a fact? something with an effect is a sensor?
- every subtree can have a supervisor? or every subtree can have a policy?
- design and implement the architecture
- lex
- parse
- eval
- closures
- mvp language features
- array
- strings
- map
- branching
- lambdas
- variables
- predicates
- WIP io
- namespaces
- emitters
- signals
- syntax highlighting
Like an exosuit for language models?
- the copilot architecture (analysis, synthesis, proving, observation, etc.)
- the user flow
- the persistence layer
- feedback and expansion
- delegation and orchestration
- Implement MVP tooling for the above and for the next phase
- Prompt generation
- observation mechanisms
- evaluation mechanisms
- retry mechanisms
- shuffling mechanisms
- delegation and orchestration
- language server protocol implementation
- repl
- tail call optimization
- static typing
- add an intepreter section at the top of the README
- merge the syntax and semantics sections in the README
- http keyword
- namespaces
- emitters
- try to get a rough draft of the interpreter section using notes
An expression is either a function, which means it has the form:
- signature
- named blocks
or a predicate, which means it's a bunch of operators