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.

What we learned

TODO

Overview

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

• Contents
• The big idea
• The design
• Programs, theories, machines, and the world
• The language
  • Blocks
  • Variables
  • Values
  • Lambdas, parameters, and arguments
  • Predicates, operators, and literals
  • Branching
  • Arrays
  • Maps
  • Strings
  • Input and Output
  • Signals and exceptions
• Run a script
• Tests
• Notes on the vision
• Notes on the language
• Notes on the interpreter
• Roadmap
  • Phase 1, language core
  • Phase 2, design the cybernetic constructs
  • Phase 3, intelligence
  • Nice to haves (unplanned)
• Work in progress
• expression

The big idea

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 design

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

Programs, theories, machines, and the world

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.

The language

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.

Blocks

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

Variables

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.

Values

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.

Lambdas, parameters, and arguments

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

Predicates, operators, and literals

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.

Branching

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.

Arrays

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.

Maps

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.

Strings

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

Input and Output

TODO

• std.write
• io.gets
• io.err
• WIP http
• io.file.read
• io.file.write
• documentation

Signals and exceptions

TODO

• A Lisp-style condition system but more focused on signaling.
• documentation

Run a script

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

Tests

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

Notes on the vision

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

Notes on the language

• 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 a remote 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.

Notes on the interpreter

• 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?

Roadmap

Phase 1, language core

• 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

Phase 2, design the cybernetic constructs

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

Phase 3, intelligence

• Prompt generation
• observation mechanisms
• evaluation mechanisms
• retry mechanisms
• shuffling mechanisms
• delegation and orchestration

Nice to haves (unplanned)

• language server protocol implementation
• repl
• tail call optimization
• static typing

Work in progress

• 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

expression

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