Toward Programming Languages for Reasoning – Humans, Symbolic Systems, and AI Agents

Toward Programming Languages for Reasoning – Humans, Symbolic Systems, and AI Agents

Toward Programming Languages for Reasoning – Humans, Symbolic Systems, and AI Agents

Mark Marron University of Kentucky USA mark.marron@protonmail.com

Abstract.

Integration, composition, mechanization, and AI assisted development are the driving themes in the future of software development. At their core these concepts are rooted in the increasingly important role of computing in our world, the desire to deliver functionality faster, with higher quality, and to empower more people to benefit from programmatic automation. These themes, and how they impact the human developers driving them, are the foundations for the next generation of programming languages. At first glance the needs of mechanization tools, AI agents, and human developers along with the various goals around development velocity, software quality, and software democratization are a broad and seemingly diverse set of needs. However, at their core is a single challenge that, once resolved, enables us to make radical progress in all of these areas.

Our hypothesis is that, fundamentally, software development is a problem of reasoning about code and semantics. This is true for human developers implementing a feature, symbolic tools building models of application behaviour, and even for language based AI agents as they perform tasks. While the particular aspects of reasoning that each agent struggles with varies to some degree, they share many common themes and, surprisingly, most mainstream languages extensively employ (anti)features that make this task harder or infeasible! This paper proposes a novel approach to this challenge – instead of new language features or logical constructs, that add more complexity to what is already a problem of complexity, we propose radical simplification in the form of the Bosque platform and language.

† † journal: PACMPL † † journalnumber: OOPSLA † † journalyear: 2023 † † publicationmonth: August † † copyright: none † † ccs: Software and its engineering General programming languages

1. Introduction

The introduction and widespread use of structured programming (structuredprogramming, ) and abstract data types (adts, ) marked a major shift in how programs are developed. Fundamentally, the concepts and designs introduced by these programming methodologies simplified reasoning about program behavior by eliminating substantial sources of, usually entirely accidental (silverbullet, ), complexity. This allowed engineers to focus on the intent and core behavior of their code more directly and, as a result, produced a drastic improvements in software quality and ability to construct large software artifacts. Just as accidental complexity is an impediment to human understanding of a program it is also an impediment to applying formal reasoning techniques, and other mechanization, to software systems. Despite the inability of structured programming to fully bridge the chasm of formal mathematical analysis, issues with loop-invariants and mutation-frames among others prevented the practical use of deep verification techniques, it did provide the needed simplifications for reasoning about limited forms of program behavior and supported a golden age of IDE tooling and compiler development (muchnick, ; kennedyallen, ).

This paper takes the view that the next phase of software development and programming languages will be defined by (1) componentization, (2) AI assistance, and (3) mechanization. We are already well into the first of these transformations where, in the last decade, service based (cloud) applications (restphd, ; serverlessdef, ), package ecosystems (semver, ; npm, ), and frameworks (react, ; express, ) have played critical roles in shaping how developers work. The second transformation, the rise of AI assisted development, arrived with the release of github’s Copilot tool (copilot, ). Suddenly, developers are looking at a landscape where they are curators of code generated by an AI agent, and integrating rich framework-functionality, in addition to writing application code directly!

In this new world, the ability for various agents and systems to understand and reason about application behavior is critical. Humans must reason about increasingly complex integrated systems, AI agents need to ingest and operate reliably on complex tasks and codebases, and, with the increased demands of AI/human agents, symbolic tooling must be able to scalably process these systems. All three of these audiences have challenges when reasoning about code written in mainstream languages today. Some of the challenges are shared, mutable state is always hard, while some are specific to a reasoning agent, e.g. symbolic analysis of iterative constructs or humans overlooking special case behaviors. However, all of the agents must share a common model for representing an application and, our hypothesis is that, foundationally the structure of this representation can be designed in a way to maximize the ability all three types of agents to reason about the semantics of an application.

This paper proposes a novel frame for conceptualizing the role and design of a programming language and software stack. Specifically, re-conceptualizing the programming language as the foundation for reasoning and mechanization, with development as a process of integration, validation, and composition. This task involves starting from first-principles and looking carefully at the impact each design choice has on the ability of agents to reason about and process code. Using this methodology we identify a set of seven major sources of complexity and ways, via language design, that they can be eliminated or minimized.

Using this insight we develop an intermediate language and surface syntax, BosqueIR and Bosque respectively, which take the novel approach of language design by the removal of problematic feature and reduction in power of various constructs – as opposed to the usual approach of introducing new language features or extending them with more powerful capabilities. This approach results in a symbolic reasoning friendly IR and a human/AI agent reasoning friendly surface syntax. Although seemingly simple this result has deep implications for the future of software-development, compilers, runtimes, and AI agents.

To demonstrate some of the possibilities that a language, like Bosque, creates we look at a case studies of long standing and impactful problems, a decidable theory for small-model program validation, and the new and critical problem of effectively generating (correct) code that matches developer/user intents using AI agents. In both of these cases a highly effective solution can be constructed via the straight forward framing of the properties of interest and the ability to effectively reason about how a piece of Bosque code interacts with these properties.

The contributions of this paper are:

  • •

A novel approach for conceptualizing the role and design of a programming language and software stack that is focused on the language as a substrate for reasoning, tools, and agents.

  • •

An analysis and enumeration of language features that impede analysis and reasoning (Section 2).

  • •

An intermediate program representation, BosqueIR, designed explicitly to support mechanized reasoning and analysis (Section 4) and a surface syntax, Bosque, optimized for humans and AI agents (Section 5).

  • •

Two case-study systems that demonstrate the viability and potential for this approach to language design in the future of software development (Section 7).

2. Complexity and Confusion

Our goal is to create a programming system that is optimized for reasoning – by humans, symbolic analysis tooling, and AI agents (Large Language Model (gpt4, ) type agents in particular). The approach we take is to identify and remove features or concepts that complicate reasoning for our agents. Based on a range of experiences and sources including developer interviews, personal experience with analysis/runtime/compiler development, and empirical studies this section identifies seven major sources of complexity that can be addressed via thoughtful language design. These are sources of various bug categories, increase the effort required for a developer (or AI agent) to reason about and implement functionality in an application, and greatly complicate (or make it infeasible to) automatically reason about a program.

2.1. Reasoning Agents and Challenges

We begin by looking at the three reasoning agent types we are considering – human, symbolic, and Large Language Model (LLM) systems. There are common themes in what aspects of reasoning each of these agents find challenging but, given the differences in their inference modes, we also see how they have unique challenges as well.

Human Developers:

Humans are remarkably adaptable and are able to understand code using many modalities including symbolic modeling, dynamic tracing of execution on concrete values, inferences from names and comments, grepping code, and even asking a teammate what they were thinking when the wrote it. Humans fundamentally have a limited amount of memory and tend to fatigue. Thus, they often take mental short-cuts and make assumptions based on limited syntactic signal and prior experience. These tricks are usually safe and eliminate substantial amounts of work. However, when there are subtle, unusual, or special context specific behaviors, these reasoning shortcuts will miss them and result in erroneous behaviors. These failures range from corner case bugs with indeterminate behaviors like unstable sorts (jssort, ), to large scale outages cased by oversights in recovery logic (failurefailure, ), or industry-wide security issues from assuming that a log statement would never access a remote server and execute un-trusted code (log4j, ). In hindsight all of these issues are “obvious” but as humans we are all subject to fatigue, oversights, and heuristic biases that let assumptions derived from surface syntax and implicit expectations lead to missing critical behaviors.

Symbolic Analysis Tooling:

Symbolic analyses in many ways are on the opposite end of the spectrum from a human developer in terms of their reasoning strengths and weaknesses. They do not understand anything apart from the code itself as written and do not bring any preconceived notions about what it might do. Thus, these agents will never overlook a subtle corner case or possibility. However, this attention to specifics and lack of intuitive understanding often leads to them getting “lost in the details” and being unable to scale to realistic codebases where they must deal with non-determinism, loop/inductive invariant generation, aliasing, and more. In practice, to be feasible, they are often simplified substantially, at a cost of imprecision, which generally leads to issues with false positives/negatives and reduces the value they can provide.

AI Agents:

Large-Language-Model (LLM) agents (gpt4, ) are an interesting addition to this spectrum. They can perform heuristic resesoning like humans but they do not get tired and can hold huge amounts of context while performing a task currently up to 32k tokens (“words”). However, these models are strongly syntax based and, as a result, if there are important semantic properties of the code that are not syntactically visible then the agent must fall back to likelihoods learned in the training data. These features make AI agents remarkably capable when performing certain coding tasks. However, these properties also lead them to making mistakes that can be quite perplexing. Current LLM’s (like GPT-4) are prone to making-up and using API’s that sound plausible but that don’t actually exist or using API’s in ways that defy common sense – for example picking a hard-coded time to schedule a meeting instead of correctly querying a schedule availability API to find a mutually open slot. The propensity to make these types of mistakes is compounded by the inability of these AI agents to leverage tools to validate assumptions in code they generate. Thus, just like human developers, improvements in symbolic reasoning based tools can lead to immediate improvements in the performance of statistically based AI agents as well.

2.2. Sources of Complexity

Given the capabilities of the agents we want to support, humans, symbolic tools, and AI systems, we next look at seven commonly appearing features in modern languages that impede their reasoning.

Mutable State and Frames:

Mutable state is a deeply complicated concept to model and reason about. The introduction of mutability into a programming language destroys the ability to reason about the application in a monotone (ppa, ) manner which forces the programmer (and any analysis tools) to identify which facts remain true after an operation and which are invalidated. The ability for mutable code to affect the state of the application via both return values and side affects on arguments (or other global state) also introduces the need to reason about the logical frame (frameproblem, ; seplogic, ) of every operation.

Implicit Behaviors:

Behaviors that are not explicit in the syntax of the code create opportunities for misunderstanding, oversights, and increase the cognitive load when reasoning. Examples of this include implicit nullability, the “billion dollar mistake”, unchecked exceptions, and APIs with undeclared implicit error behaviors. A common example is the min operation in C# vs. Python. In C# the min operator return is declared as Option so that the possibility of a invalid result is syntactically explicit in the declaration. In Python one must look into the API docs to find the comment that the min function throws an error on the empty list.

Hidden Semantics:

Similar to implicit behaviors, many languages have implicit rules that affect program behaviors. These include implicit type coercion, numeric truncation, and flow-sensitive or other advanced of type inference algorithms. These increase the cognitive load to understand a block of code as they require additional work to simulate a non-trivial hidden algorithm to extract implicit program semantics and create opportunities for simple oversights to create unexpected outcomes.

Loops, Recursion, and Invariants:

Loops and recursion represent a fundamental challenge to reasoning as the code describes the effects of a single step but understanding the full construct requires generalization to a quantified property over a set of values. Invariants (finvariants, ; hinvariants, ) provide the needed connection but a generalized technique for their computation is, of course, impossible in general and has proved elusive even for restricted applications.

Indeterminate Behaviors:

Indeterminate behaviors, including undefined, under specified, or non-deterministic or environmental behavior, require a programmer or analysis tool to reason about and account for all possible outcomes. While truly undefined behavior, e.g. uninitialized variables, has disappeared from most languages there is a large class of under-specified behavior, e.g. sort stability, map/dictionary enumeration order, etc., that remains. These increase the complexity of the development process and, as time goes on, are slowly being seen as liabilities that should be removed (jssort, ). Less obviously the inclusion of non-deterministic and/or environmental interaction results in code that cannot be reliably tested (flakey tests), behaves differently for non-obvious reasons, and frequently mixes failure logic widely through a codebase.

Data Invariant Violations:

Programming languages generally provide operators for accessing, and in imperative languages updating, individual elements in arrays/tuples or fields in objects/records. The fact that these accessors/updaters operate on an individual elementwise basis results in programmers updating the state of an object over multiple steps, or manually exploding an object before creating an updated copy, during this span invariants which normally hold are temporarily invalidated before being restored. During these intervals the number of details that must be tracked and restored can increase drastically increasing opportunities for mistakes and oversights to occur.

Equality and Aliasing:

Programming languages live at the boundary of mathematics and engineering. Although language semantics are formulated as a mathematical concept there are common cases, e.g. reference equality, pass by-value vs. by-reference, or evaluation orders, that expose and favor one particular hardware substrate, generally a Von Neumann architecture, either intentionally for performance or accidentally by habit or history. While seemingly minor these choices have a major impact on comprehensibility – merely exposing reference equality pulls in the complexity of reasoning about aliasing relations and greatly complicates compilation on other architectures.

3. Bosque Design Philosophy

The unique value proposition of Bosque is not based on a single big new feature, or even a number of smaller novel features, instead the novelty comes from a holistic process of simplification and feature selection with a single focus toward what will simplify reasoning about code. The first part of this process is eliminating, or minimizing, the sources of complexity identified in Section 2. This process primarily involves the design of the BosqueIR in Section 4. The second part of the process centers around how to connect this core IR to a user friendly surface syntax, and, how to make this syntax amenable to human and LLM agent understanding. This involves the development of the language structure and the introduction of a variety of intentional but subtle features that fade into the background and lead developers onto a path of producing clean code without effort or conscious thought.

The idea of a solver integrated or aware language has been explored in several contexts – examples include Rosette (rossette, ), why3 (why3, ), Dafny (dafny, ), and Ivy (ivy, ). The design of BosqueIR is unique in that it does not attempt to expose the solver, including limitations it has, to the developer. Instead it is designed to naturally encourage and simplify the mapping of code written by a non-expert developer (one who is not an expert in logics or provers) into one of many possible reasoning frameworks such as SMT solvers, deductive logical engines, abstract interpretation, and simple dataflow solvers.

At the core of BosqueIR is a let-based functional language. Although there are many functional languages that have key properties we want in the IR, in their attempts to also be general purpose languages or due to historical accident, they also end up with features like mutable cells, visible aliasing, lazy evaluation, non-local effects and flow, or indeterminate behaviors in their specifications. Thus, the BosqueIR can be seen as a highly regularized functional language that is fully aligned with the goal of eliminating the complexities identified in Section 2.

In Section 5 this paper shows how a selection of language features and syntactic structures can connect a regularized IR like the BosqueIR to a block-structured (and imperative looking) source language that developers are comfortable with. As described in Section 5 we can use syntactic sugar to support commonly used and easily understood programming constructs like block-structured code, reassignment of variables, updates through (shallow) references, early returns, and object-oriented data types. These constructs are heavily used and well understood features in modern software engineering so supporting them allows developers to easily express their intents in a natural way. However, by our careful construction, these features can in fact be compiled directly down into the core BosqueIR representation. Thus giving us the best of both worlds, where developers can express their domain and business logic in an intuitive syntactic form and, unlike in a standard imperative or object-oriented language, the underlying semantics are the well-behaved BosqueIR structures.

4. BosqueIR Intermediate Representation

Given the sources of complexity identified in Section 2, the first task is to construct an intermediate language (IR) that eliminates or reduces the impact of each of them. As many of the issues are tied to mutability and loops, the design process starts with a strict functional language core. This core uses classic let bindings, if-then-else conditionals, a special assert expression, and a restricted definition of equality.

4.1. Primitive Types and Values

The BosqueIR language provides a standard assortment of primitive types and values including a special none value (None type), a Bool, Nat and Int numbers, safe BigNat and BigInt numbers, along with Float, Decimal, and Rational numbers. The BosqueIR String type represents immutable unicode string values (a special ASCIIString is also provided). The language includes support for commonly used types/values in modern cloud applications like ISO/Plain times, SHA hashcodes, UUIDs, timestamps, and other miscellany.

4.2. Self Describing Types and Values

Structural Tuple and Record types provide standard forms of self describing types. Structural types do not allow subtyping (i.e. not covariant). This allows for an analysis to know, and precisely encode, the types of values in a structural type. This representation results in substantial simplifications when reasoning about operations on these values as lookups are always statically resolved. Examples of these types include:

[Int, String] //a tuple type

[5 i, ” ok”] //a tuple of type [Int, String]

{ p1: Int, p2: String} //a record type

{ p1=5 i, p2=” ok”} //a record of type {p1: Int, p2: String}

The BosqueIR representation also supports self describing ad-hoc union types. The sub-typing relation on union types is defined as being a subtype of any enumerated type in the union.

⬇ Int | None //a union type if true then 5 i else none //expression of type Int | None

4.3. Nominal Types

BosqueIR supports a nominal type system that allows the construction of object-oriented style type inheritance structures. Abstract concepts provide a means for inheritance and multi-inheritance via conjunction.

In the following example there are two concepts declared, WithName and Greeting, that define a field and abstract method respectively. The concrete entity GenericGreeting is declared to provide the Greeting concept and, implements the required sayHello method. The NamedGreeting provides both the WithName concept, so it inherits the field name and the Greeting concept. Using the name field it implements the sayHello method to return a customized string with the name information.

concept WithName {

field name: String;

concept Greeting {

abstract method sayHello(): String;

entity GenericGreeting provides Greeting {

override method sayHello(): String {

return ” hello world”;

entity NamedGreeting provides WithName, Greeting {

override method sayHello(): String {

return String:: concat(” hello ”, this. name);

In BosqueIR, nominal subtyping is based on the transitive closure of the provides relation. In this example the entity GenericGreeting is a subtype of just Greeting while the entity NamedGreeting is a subtype of both WithName and Greeting.

The nominal type system differs from many object-oriented type systems in that the concepts are always abstract and can never be concretely instantiated while entity (class) types are always concrete and can never be subclassed. This prevents confusion in type checks where an instance of test may be intended to check for an exact type but actually includes all subtypes as well. More generally this enables us to easily determine if a given operation has a single concrete behavior or may be dynamic in nature.

ListStructure

:=assign\displaystyle\;\;:=\;\;:=

List ⁢{e1,…,ej}⁢|slice⁢(l,i,j)|⁢concat⁢(l1,l2)⁢…List subscript𝑒1…subscript𝑒𝑗slice𝑙𝑖𝑗concatsubscript𝑙1subscript𝑙2…\displaystyle\texttt{List}\{e_{1},\ldots,e_{j}\}\;\;|\;\;\texttt{slice}(l,i% ,j)\;\;|\;\;\texttt{concat}(l_{1},l_{2})\ldotsList { italic_e start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , … , italic_e start_POSTSUBSCRIPT italic_j end_POSTSUBSCRIPT } | slice ( italic_l , italic_i , italic_j ) | concat ( italic_l start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_l start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ) …

ListAccess

:=assign\displaystyle\;\;:=\;\;:=

size⁢(l)⁢|get⁢(l,n)|⁢…size𝑙get𝑙𝑛…\displaystyle\texttt{size}(l)\;\;|\;\;\texttt{get}(l,n)\;\;|\;\;\ldotssize ( italic_l ) | get ( italic_l , italic_n ) | …

ListCompute

:=assign\displaystyle\;\;:=\;\;:=

map ⁢(l)⁢|filter ⁢(l)||join ⁢(l1,l2)|⁢…map 𝑙filter 𝑙join subscript𝑙1subscript𝑙2…\displaystyle\texttt{map}(l)\;\;|\;\;\texttt{filter}(l)\;\;|\;\;\;\;|\;% \;\texttt{join}(l_{1},l_{2})\;\;|\;\;\ldotsmap ( italic_l ) | filter ( italic_l ) | | join ( italic_l start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT , italic_l start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT ) | …

ListPred

:=assign\displaystyle\;\;:=\;\;:=

has ⁢(l)⁢|find ⁢(l)|⁢count ⁢(l)|…conditionalhas 𝑙find 𝑙count 𝑙…\displaystyle\texttt{has}(l)\;\;|\;\;\texttt{find}(l)\;\;|\;\;\texttt{% count}(l)\;\;|\;\;\ldotshas ( italic_l ) | find ( italic_l ) | count ( italic_l ) | …

ListIterate

:=assign\displaystyle\;\;:=\;\;:=

sum⁢(l)⁢|reduce ⁢(l)|⁢…sum𝑙reduce 𝑙…\displaystyle\texttt{sum}(l)\;\;|\;\;\texttt{reduce}(l)\;\;|\;\;\ldotssum ( italic_l ) | reduce ( italic_l ) | …

Figure 1. BosqueIR List Operations

4.4. Typedecls

Primitive datatypes are a frequent source of implicit non-syntactic information in code. Strings and integers are often used to represent semantically distinct concepts, like a zipcode or a temperature, just via convention and use. These uses make certain classes of bugs possible, like adding a temperature in Fahrenheit to one in Celsius, and hide important information in implicit channels. Sometimes this design is motivated by performance concerns, e.g. space/boxing overheads, but is often just an issue of simply wanting to avoid the effort to declare a new datatype and implement all the associated methods (particularly for numeric types).

The BosqueIR representation provides explicit support for these cases via a StringOf type and typedecl s that manage the new-type creation, ensuring that the type representation is isomorphic to the underlying type, generation of the standard operators, and allow customization of the underlying value with user-defined invariants.

The example below shows the declaration of a typed string Zipcode using a regex and the parametric StringOf type. These structured strings are frequently used in modern web applications – OpenAPI (openapi, ) and Microsoft TypeSpec (typespec, ) both natively support similar constructs. As shown in the example this allows us to declare typed string literals, check they satisfy the constraints on construction, and are used in type-safe ways.

typedecl ZipcodeValidator = /[0-9]{5}(-[0-9]{4})?/;

typedecl Zipcode = StringOf< ZipcodeValidator>;

typedecl Celsius = Float;

//create a literal zipcode string

“40502” Zipcode //Ok

” ABC” Zipcode //Type Error

function isNYZipcode(zc: Zipcode): Bool {…}

isNYZipcode(“40502” Zipcode) //Ok returns false

isNYZipcode(“40502”) //Error arg is a String

let temp = 10_Celsius + 1_Celsius //Type safe operation

The typedecl type constructor also supports creating new types for any primitive type such as Ints, Floats, UUIDs, etc. In the example a new type for the temperature Celsius is created and, all well-typed, operations are permitted on the new numeric types.

4.5. Key Types and Equality

Equality is a multifaceted concept in programming (lefthandequals, ) and ensuring consistent behavior across the many areas it surfaces in a modern programming language such as ==, . equals, Set. has, and List. sort, is source of subtle bugs (findbugs, ). This complexity further manifests when equality can involve referential identity which introduces issue of needing to model aliasing relations on values, in addition to their structural data, in order to understand the equality relation.

To avoid these behavioral complications, and the need to model aliasing, the BosqueIR language is referentially transparent. The only values which may be compared for equality are specific primitive values including none, booleans, primitive integral numbers, strings, and typedecls of these primitive types. In conjunction with the immutability of the values (Section 4.6) this ensures that BosqueIR code is referentially transparent and functions do not need to use frame rules (frameproblem, ).

4.6. Operations

The expression language for BosqueIR is designed explicitly with the needs of symbolic reasoning systems in mind. The language allows recursion but most code is expected to use a rich language of higher-order functor libraries (see Figure 1). Otherwise, the BosqueIR expression semantics are constructed to ensure referential transparency, that all expressions are side-effect free, that any expression deterministically evaluates to unique result value and, with the inclusion of an error-result, that they are total as well.

Primitive expressions include special constants like true, false, none, literal integral i values or literal float f values, literal strings s, and variables (either local, global, or argument). BosqueIR has the standard assortment of numeric and logical Operators. The constructor operations are all simple and explicit operations for tuples and records. The constructors for nominal entity types takes the type name + the full list of values to initialize the fields with. Deconstructing compound values is done with a standard indexing for tuples (e.iformulae-sequence𝑒𝑖e.iitalic_e . italic_i where i𝑖iitalic_i is a constant), or named property/field accessor (e.pformulae-sequence𝑒𝑝e.pitalic_e . italic_p and e.fformulae-sequence𝑒𝑓e.fitalic_e . italic_f respectively).

The type manipulation operators include standard is and as operations to test value types (or subtype) and to perform (checked) casts on them. The inject operation is used to convert a primitive value into a matching typdecl type and the and extract operation extracts primitive values. The assert operation provides a way to explicitly generate an error value (for user defined errors) in addition to implicitly defined error sources, like cast failures, out-of-bounds indexing, etc..

4.7. Collection Functors

Containers and operations on them play a major role in most programs and these semantics inherently involve reasoning over the container contents. Instead of introducing a primitive looping construct, and attempting to tackle the loop invariant generation problem, the BosqueIR language includes a rich set of container datatypes and functor based operations on them. In practice these operations, and parameterizeable functors, are sufficient to cover the majority of iterative operations (loopmining, ).

Figure 1 shows a sample of the operations that are provided for processing lists (maps, sets, stacks, and queues are also supported). These operations provide a structured way to process the values in collections. Most of these operations are familiar from libraries such as LINQ (linq, ), Java Streams (javastreams, ), or lodash (lodash, ). One unique restriction on them is that the lambda parameters are passed as parametric arguments which specialize each functor. This preserves the first-order nature of the language, since we do not need to pass function types, and as we see later, can be ensured with a simple syntactic restriction on how lambdas can be used in the source language.

5. Bosque Source Representation

The construction of the BosqueIR language, as described in Section 4, is free of many features that complicate reasoning w.r.t. application behavior. However, it is not particularly human (or LLM AI) friendly and does not address many problems identified in the context of implicit behaviors or hidden semantics. At a high-level the Bosque language is designed to be easily accessible to a developer coming from TypeScript, C#, or Java while mapping well to the restricted BosqueIR representation. Bosque uses a block-based structure, allows reassignment of variables, has an extensive set of control-flow operators, object-oriented language features, and other language features designed to simplify common programming idioms.

This section describes the specific features of the Bosque source language exposed to developers that are related to our key objective, supporting reasoning. Figure 2 is a partial implementation of a binary-tree in Bosque that contains many of these features. It uses the extended Algebraic Data Type (ADT) declaration form (Section 5.1) to declare the various types associated with a tree, early returns and other block structured control flow including variable re-assignment (Section 5.4), explicit flow-typing and binding ($) as described in Section 5.2, explicit recursion tags to denote recursive call paths (Section 5.8), and the use of data invariants (Section 5.6). Later we will describe how ref methods work and show how they allow simulated in place (Section 5.7) updates.

⬇

datatype ITree using {

size: Nat

} of

Nil {}

| Leaf { v: Int }

| Node {

invariant test size == l. size + r. size + 1 n;

field v: Int;

field l: ITree;

field r: ITree;

}

& {

const empty = Nil{0 n};

method isEmpty() {

return this?< Nill>;

}

recursive method has(x: Int): Bool {

match(this) {

Nill => return false;

| Leaf => return $. v == x;

| Node => {

if($. v == x) {

return true;

}

var tchild: ITree;

if(x < $. v) {

tchild = $. l;

}

else {

tchild = $. r;

}

return tchild. has recursive;

}

}

}

}

Figure 2. Bosque Binary-Tree Example

5.1. Enhanced Algebraic Data Types

The type system that is presented to the surface user of the Bosque language closely mirrors the type system of the core BosqueIR language. The major ergonomic addition in the Bosque source language is the provision of syntax for creating algebraic-data-types. This syntax allows for the compact subtyping, as provided by most ADT implementations, along with inheritance of fields and definition/override of methods, invariants, etc. These features make the ADT syntax more useful and practical.

In the binary-tree example these features allow us to declare a field size which is inherited by each of the cases, Nil, Leaf, and Node. The simple cases of Nil and Leaf are similar to the traditional ADT style where only the public fields are specified. When, inevitably the data types get more complex as in the case of the Node type, Bosque supports expanding the declaration with invariants and other type members. To simulate the desirable encapsulation properties of object-oriented languages this declaration allows a tailing block that can include any member type declarations. These are all defined in the scope of the enclosing ADT type, in our example the ITree type. The example includes declarations of a member constant, empty, and three member methods. This shorthand provides a compact way to group logically related subtypes and operations in addition to avoiding the need for mostly trivial class declarations (in our examples it would be 1111 abstract class plus 3333 concrete classes in a language like Java or TypeScript).

5.2. Explicit Flow Typing and Binding

A key principle in the design of the Bosque surface language is to ensure that, as much as possible, the behavior of an expression is explicit in the syntax. One area where behavior is often implicitly encoded is type flow and automatic inference/coercion. Flow based typing is a very convenient feature but requires a user of the language to know the flow-rules (typescript, ; rust, ) of the checker, and to run the algorithm, to understand type properties (rust, ; rustflow, ). As a balance between the convenience of implicit flow-typing and the simplicity of explicit type coercion, Bosque provides specialized explicit flow typing expressions and binding.

The explicit flow type operations shown in Figure 3 are designed to cover common idiomatic type tests (FlowSpecial), support standard is/subtype checks (FlowType), and enable flow type inference when testing against constant values (FlowEQ). The ability to negate these tests allows them to be used easily in control-flow contexts as well. These operations can be used for is-testing using the ? operator or as-casting using the @ operator. This explicit operations have the benefit of clearly indicating in the source which variables and type constraints are of relevance, it is applicable to arbitrary expressions as opposed to only variables or some limited forms, and it ensures that they compiler type-checker does not experience compounding growth in managing flow-type information (e.g. exponential path-sensitivity) or arbitrary limits on what inferences 1 1 1 From a engineering perspective it is also removes the very painful problem of later changes to these type-inference heuristics introducing (subtle) bugs into an application! are made (e.g. discard on path joins, only top-level variables, …).

FlowSpecial

:=assign\displaystyle\;\;:=\;\;:=

none⁢|some|⁢ok⁢|err|⁢resultnonesomeokerrresult\displaystyle\texttt{none}\;\;|\;\;\texttt{some}\;\;|\;\;\texttt{ok}\;\;|\;\;% \texttt{err}\;\;|\;\;\texttt{result}none | some | ok | err | result

FlowType

:=assign\displaystyle\;\;:=\;\;:=

< Type>

FlowEQ

:=assign\displaystyle\;\;:=\;\;:=

[literal]

FlowAlt

:=assign\displaystyle\;\;:=\;\;:=

FlowSpecial⁢|FlowType|⁢FlowEQFlowSpecialFlowTypeFlowEQ\displaystyle\emph{FlowSpecial}\;\;|\;\;\emph{FlowType}\;\;|\;\;\emph{FlowEQ}FlowSpecial | FlowType | FlowEQ

FlowOp

:=assign\displaystyle\;\;:=\;\;:=

FlowAlt|!FlowAltconditionalFlowAlt!FlowAlt\displaystyle\emph{FlowAlt}\;\;|\;\;\texttt{!}\emph{FlowAlt}FlowAlt | typewriter_! italic_FlowAlt

Figure 3. Bosque Flow Typing and Binding

Examples of these operations for type testing and coercion expressions include:

x? some //test if x is a subtype of Some

x@ some //coerce of x to a Some type or fail

x?!< Nat> //test if x is not a Nat

x@[5 i] //test if x is 5 and coerce to Int type

foo(x). f?< Bar> //test if arbitrary expression is type Bar

The typing tests also enable special narrowing statements in blocks – rebinding the type of the variable. In this case narrowing the type of x, which is initially declared as a Nat | none, to be a Nat (and raising a runtime error if it is not). This explicit narrowing, as opposed to an implicit flow-sensitive analysis around say, assert(x != none), enables us to explicitly encode the intent in the source so that it is explicit and obvious to humans or AI agents.

⬇ let x: Nat? = …; let e = x + 2 n; //type error … //check that x is a Nat (error otherwise) and narrow x@< Nat>; … let y = x + 2 n; //ok

The typing tests are also used in control flow expressions and statements to provide bindings in branches of control flow structures. Bosque provides the special variable that is automatically bound to the narrowed results of the conditional guard. Consider the following example where a variable may be Nat | none. With the flow-type check if none (x) we know that on the false branch the type of x must be a Nat. Instead of leaving this information implicit and simply reusing the variable x Bosque code leaves the type of x unchanged and introduces the new binder with the same value but the type restricted based on the test.

⬇ let x: Nat? = …; if none (x) { return 0 n; } else { //Binder for to value of x (with type Nat) return + 10 n; }

Finally, these FlowOp typing tests are also used to handle early return statements in blocks. In the following example the ?? operator syntactically reduces to if none (foo(…)) {return none;} let x = foo(…)@!none; while the @@ operator reduces to the code if ! (x) {return x@Int;} x@; . Thus, this syntax allows a developer to succinctly express these common check-and-early-return idioms in an explicit way and without filling the code with conditional flows that obscure the underlying algorithm.

function bar(k: Int): Nat | Int | None {

//test/narrow call result — return none if fails

let x: Nat | Int = foo(…) ?? ! none;

let e = x + 2 n; //type error

…

//check/narrow type of x — return Int otherwise

x @@ < Nat>;

return x + 2 n; //ok

}

These operators provide shorthand notation for common idioms (idioms, ) that developers use and ensure that they are syntactically surfaced in the code. This both simplifies writing the code, reduces the opportunities for developers to miss important behaviors, and provides AI agents with explicit representations.

5.3. Lambdas

Higher order functions are a powerful programming mechanism that can be used to great effect to simplify code. However, their use can also lead to difficult to reason about flows and inscrutable behaviors. Empirical work on the use of lambdas in large codebases (jlambda, ) provides a compelling quantitative result that matches the anecdotal intuition. In particular the vast majority of use of lambdas are in direct positions (87.5%percent87.587.5\%87.5 % are passed directly as arguments in calls) and very few examples of classic functional programming techniques, like currying, were seen.

With this in mind the Bosque language provides a syntactically restricted version of lambdas where they:

  1. (1)

Cannot be stored in local variables or returned as function/method results 2. (2)

Can capture arguments but cannot modify their values

Bosque lambdas are also split into two categories. Predicates are denoted with the pred keyword, which must return a Bool result, and other functions that may return any type with the fn keyword.

⬇ //takes a predicate l. allOf(pred(x) => x >= 0 i) //takes a function l. map< Int>(fn(x) => x + 1 i)

In combination these restrictions and conventions provide the vast majority of benefit that most developers get from lambda style expressions while prohibiting their more problematic uses. These restrictions also ensure that we can syntactically convert code using lambdas to a de-functionalized form where the functions are reduced to direct parametric specializations as needed by the BosqueIR language (Section 4.7).

5.4. Block Structure with Re-bindable Variables

Interviews and conversations with developers, ranging from fortune 100 companies to 3-person startups, suggested a strong preference for block-scoped flows and mutable variables over a classic-functional let-bound expression tree (which BosqueIR is). In order to unify these two representations we leveraged the loop-freedom of the source language to convert multiple-assignments and convergent-dataflow into dynamic single assignment form (dsaform, ). Consider the code:

⬇ function abs(x: Int): Int { var y = x; if (y < 0) { y = - y; } return y; }

This function shows the use of multiple updates to the same variable and block structured conditional flows. We distinguish between variables, let, that are fixed and those, var, that can be updated. This ability to set/update a variable as a body executes simplifies a variety of common coding patterns.

Since the language is loop free, it can be easily converted to a SSA form (ssa, ), and the loop freedom also ensures that any assignment is also a single assignment dynamically! A simple treeification pass, with the introduction of continuation functions if needed, also eliminates all DAG control flow. Thus, our block structured flows and updated variables becomes the following let-bound expression:

⬇ function abs(x: Int): Int { let (y = x) in if y < 0 then - y else y }

Similar transformations allow Bosque to support many other familiar block structured flow features. The running binary-tree example has an implementation utilizes these heavily, including early returns, merging control flows, creating and later assigning variables (the tchild variable) and checking for any possible uninitialized uses. These constructs are heavily used and well understood features in modern software engineering so supporting them allows developers to easily express their intents in a natural way.

5.5. Constructrors and Bulk Operators

Even with immutable objects there can be subtle challenges with constructor semantics and implementing operations which create a copy of a value with updates to some subset of the contained values. Constructor bodies where fields are initialized sequentially with, potentially other computation mixed in, can lead to issues where methods are invoked on partially initialized values. Updates to objects are often implemented by copying fields/properties individually while replacing the some subset with new values. These issues can lead to both subtle bugs during initial coding and also make it difficult to update data representations when refactoring code or adding a new feature at some later date.

Consider the code shown below. The use of atomic constructors prevents the partially initialized object problem (oinv1, ; oinv2, ; joed, ) when constructing the Baz object. This example also shows how the bulk algebraic operations simplify the update/copy of the Baz object and eliminate the problem of temporarily violated invariants during a series of single field updates 2 2 2 Fields can be declared as private, in which case these raw operations will not be visible outside the type declaration.. Bosque provides explicit support for data invariants, e.g. in the Node entity in our example) and described more below, these are automatically checked on both initial construction and any updates.

concept Bar {

field f: Int;

}

entity Baz provides Bar {

field g: Int;

field h: Bool;

}

//create a Baz value with all fields initialized

var x = Baz{1, 2, true};

//copy of x with f updated to 3 and h to false

var y = x.{ f=3, h= false};

To make these operations more useful they also handle the common case of wanting to update a field with a function of that field value. This is done by extending the range of where binders can be used and, for each field updated, creating a variable that is scoped to the update expression and that is bound to the original value of the field. In the code below this allows us to increment the value of the field f by 3333 and then assign the new value in the update.

⬇ //copy of x with f incremented by 3 var y = x.{ f=$f + 3};

5.6. Data Validation

Program logic checks are fundamental to quickly catching bugs and make implicit assumptions explicit in program. Thus, the Bosque surface language provides a rich set of validation features to support a broad range of uses including dynamic checking, static validation, optimization, and documentation for human (and AI) developers. Including them as first class components of the language provides several advantages over libraries or 3rd party implementations.

From a reasoning perspective having builtin validation operators ensures that every application will have the same look and semantics around assertions. It also gives the compiler and runtime direct knowledge of these special operations for example an optimizer can move them off the hot path aggressively, do short circuit evaluation of any message or line number computations, and, if they are disabled, can easily remove all of the dead code. In Bosque we use this awareness along with a new level, safety, that we ensure is always checked – e.g. the compiler is never allowed (optbug, ) to optimize it out!

Assert/Pre/Post:

The first form of validation is a classic conditional assert statement that can be used to place ad-hoc checks in a block of code. Bosque also supports pre/post conditions on functions and methods. These features allow developers to insert, explicit, information on expectations/assumptions for any bit of code or invocation.

Invariants and Validates:

The ability to explicitly state data invariants is one of the most powerful validation features in the Bosque language. These invariants allow a developer to state a property in a single location – this property ensures that at every creation site it must be preserved and provides a guarantee for every use of the type in a program. An example invariant is seen in the binary-tree example.

Ingesting data from external sources, such as command line args, network data, file reads, etc., is a critical task. Writing code to validate data, even structured data in JSON or XML form, is a tedious and error prone task (restler, ). Errors in this code are amplified as they open opportunities for external, and potentially malicious, sources to directly interact with the application.

By default Bosque checks all active invariants whenever an value is constructed. These are generally not as extensive as would be needed to fully validate untrusted inputs. Thus, Bosque provides a validate keyword that allows the specification of checks that must be run on eternal inputs. When compiling Bosque to executable code these validate checks are combined with the invariants in a special function that the host can use to create values from untrusted external data sources.

Figure 4 shows code from a sample trading application provided by Morgan Stanley that was ported to Bosque (see Section 7). In this code there are several invariants and external validations on the SaleInfo type. The check available >= 0I i