Based at the old Lexer Plantation house, Frightmare Manor combines a dark history with the fun of Halloween. With four different haunted houses to go through, Frightmare Manor is where True Terror lives.

True Terror lives in an old Talbott Plantation

Officers of the Tau Gamma Phi fraternity were among those identified as suspects in the killing of Philippine College of Criminology student Ahdlryn Lery Bravante in Quezon City, police said yesterday.

Frat leaders tagged in PCCR hazing death

Philippine College of Criminology student Ahldryn Lery Bravante in Quezon City were intoxicated with alcohol, police said yesterday.

Some fratmen in PCCR hazing were drunk – QCPD

The Quezon City Police District (QCPD) on Thursday filed a case for violation of the Anti-Hazing Law against 16 members of the Tau Gamma Phi Fraternity-Philippine College

QCPD charges 16 frat members in hazing death of criminology student

Among those charged were Justine Artates, Mark Leo Andales, Lexer Angelo Manarpies and Kyle Michael de Castro, all officers of the Tau Gamma Phi fraternity, who are in the custody of the QCPD. The suspects underwent inquest proceedings on Wednesday afternoon.

16 suspects in criminology student’s hazing charged

Another suspect in the alleged hazing of criminology student Ahldryn Leary Bravante has surrendered, the Quezon City Police District (QCPD) said on Thursday. The QCPD identified the fifth suspect as 18-year-old John Xavier Arcosa.

Two more Bravante hazing suspects have surrendered —QCPD

A fourth year student of the Philippine College of Criminology died from at least 60 blows to the body during initiation rites by suspected members of the Tau Gamma Phi fraternity, the Quezon City Police District said yesterday.

PCCR hazing: Student suffered 60 blows – QCPD

Twenty members took turns in hitting Ahldryn Leary Bravante with paddles during the initiation rites of the Tau Gamma Phi, two of the suspects have told investigators of the Quezon City Police District.

20 fratmen, 60 paddle hits figured in Bravante 'hazing'—QCPD

Twenty members took turns in hitting Ahldryn Leary Bravante with paddles during the initiation rites of the Tau Gamma Phi.

The police have taken custody of four of the 12 suspects in the suspected hazing death of 25-year-old Ahldryn Leary Bravante, a fourth-year criminology student of the College of

Police take custody of 4 frat men in suspected hazing death

Lexer

lexer

In the of this series on how to build a WebAssembly programming language, we constructed a lexer. In this post, we’ll cover the next phase of our compiler, parsing. Parsing is the portion of our compiler that takes the token stream generated by the lexer and converts it into an (AST). last post abstract syntax tree An AST is a tree-like data structure that organizes the tokens into a logical hierarchy that can more easily be translated into machine code. Thankfully, because wispy is an S-expression language, our code is essentially an AST. Take the following stream of tokens: already “(“, “add”, “3”, “(“, “sub”, “2”, “1”, “)”, “)” Each set of parentheses represents a subtree, where the first token is the operator node and the following tokens are its operands. If we run into another opening parenthesis before the current set is closed, we know it represents an operand that itself is a subtree. The above stream of tokens would be organized into a tree that looks like this: If you're interested in writing a parser for a more complex C-like syntax, see my previous series. Building A Programming Language More About AST As we did with the lexer, we'll start by defining our types. These types will define the structure of our AST. Each type represents a “Node”, the circle from our diagram in the intro. Here are the basic nodes. We'll gloss over them, as they aren't a lot different from the tokens we defined in the lexer: // src/types/ast.mts

export type IntNode = {
  type: "int";
  value: number;
};

export type FloatNode = {
  type: "float";
  value: number;
};

export type IdentifierNode = {
  type: "identifier";
  identifier: string;
};

export type TypedIdentifierNode = {
  type: "typed-identifier";
  // Note that here, we break down the identifier into its components
  identifier: string;
  typeIdentifier: string;
}; A new concept to the AST is the . A is an expression made up of a group of other nodes. BlockNode BlockNode For example, is a block of three nodes: (add 1 2) An identifier that evaluates to a function, . add An Int that simply evaluates to the number . 1 An Int that simply evaluates to the number . 2 How the block itself gets evaluated is up to the compiler. We'll get to that in the next post. Here's the definition: // src/types/ast.mts

export type BlockNode = {
  type: "block";
  expressions: AstNode[];
}; Finally, we define the . Like the type from the lexer, is a discriminated union that can be one of any other node we previously defined: AstNode Token AstNode export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode; You may have noticed that has an array of s, Since a , s can contain child . In other words, is a recursive type. This ability to recursively represent children that can have children is the foundation of our AST. It's where the tree in AST is allowed to form. BlockNode AstNode AstNode can be BlockNode BlockNode BlockNodes BlockNode At this point is finished and should look like . src/types/ast.mts this file Now export the types from as we did with the token types: src/types/index.mts // src/types/index.mts
export * from "./token.mjs";
export * from "./ast.mjs"; Constructing the AST Now that we've defined the AST, it's time to build one. Create a new file and add all the imports we'll use: src/parser.mts // src/parser.mts
import {
  Token,
  IdentifierNode,
  TypedIdentifierNode,
  IdentifierToken,
  TypedIdentifierToken,
  FloatToken,
  FloatNode,
  IntToken,
  IntNode,
  AstNode,
  BlockNode,
} from "./types/index.mjs"; Now we can define our top level parse function. The parse function takes the tokens generated by the lexer and returns a that acts as our tree’s root. BlockNode // src/parser.mts
export const parse = (tokens: Token[]): BlockNode => {
  const blocks: BlockNode[] = [];

  // This loop is run as long as there are tokens to consume
  while (tokens.length) {
    // consumeTokenTree converts an array of tokens into a tree of tokens, more on that later.
    const tree = consumeTokenTree(tokens);

    // parseBlock turns our new tree of tokens into an actual BlockNode, recursively. More on that later as well.
    blocks.push(parseBlock(tree));
  }

  // Finally we return the top level BlockNode
  return {
    type: "block",
    expressions: blocks,
  };
}; Next, we define the function. converts a flat array of tokens, into a tree of tokens. consumeTokenTree consumeTokenTree Given this wispy expression: (add (sub 3 1) (sub 5 2)) The lexer will produce this array of tokens: // Note: I've simplified the Token format to just be strings to keep things short
["(", "add", "(", "sub", "3", "1", ")", "(", "sub", "5", "2", ")", ")"]; will take that flat array and turn it into a tree. This is as simple as putting every token in between a set of bracket tokens into an array. So our token array from above becomes this token tree: consumeTokenTree () ["add", [, "sub", "3", "1"], ["sub", "5", "2"]]; Here's the actual definition of : consumeTokenTree // src/parser.mts

// This is token besides for the bracket tokens
export type NonBracketToken = Exclude<Token, "parenthesis" | "square-bracket">;

// The token tree is made of NonBracketTokens and other TokenTrees
export type TokenTree = (NonBracketToken | TokenTree)[];

const consumeTokenTree = (tokens: Token[]): TokenTree => {
  const tree: TokenTree = [];

  // Ensures the first token is a left bracket and then discards it, defined below this function.
  consumeLeftBracket(tokens);

  while (tokens.length) {
    // Preview the next token
    const token = tokens[0];

    // Check to see if the next token is a left bracket.
    if (token.type === "bracket" && getBracketDirection(token) === "left") {
      // If it is, we just ran into a sub-TokenTree. So we can simply call this function within
      // itself. Gotta love recursion.
      tree.push(consumeTokenTree(tokens));
      continue;
    }

    // Check to see if the next token is a right bracket
    if (token.type === "bracket" && getBracketDirection(token) === "right") {
      // If it is, we just found the end of the tree on our current level
      tree.shift(); // Discard the right bracket
      break; // Break the loop
    }

    // If the token isn't a bracket, it can simply be added to the tree on this level
    tree.push(token);

    // Consume / discard the token from the main tokens array
    tokens.shift();
  }

  // Return the tree. Don't forget to check out the helper functions below!
  return tree;
};

const consumeLeftBracket = (tokens: Token[]) => {
  const bracketDirection = getBracketDirection(tokens[0]);

  if (bracketDirection !== "left") {
    throw new Error("Expected left bracket");
  }

  return tokens.shift();
};

const getBracketDirection = (token: Token): "left" | "right" => {
  if (token.type !== "bracket") {
    throw new Error(`Expected bracket, got ${token.type}`);
  }

  // If we match a left bracket return left
  if (/[\(\[]/.test(token.value)) return "left";

  // Otherwise return right
  return "right";
}; Now that we have a token tree, we need to turn it into a block. To do so, we create a function that takes the tree as its input and returns a : parseBlock BlockNode 1const parseBlock = (block?: TokenTree): BlockNode => {
  return {
    type: "block",
    // This is where the recursive magic happens
    expressions: block.map(parseExpression),
  };
}; As you may have noticed, maps each item of the tree with a yet to be written function. takes either a or a and transforms it to its corresponding type. parseBlock parseExpression parseExpression TokenTree NonBracketToken AstNode Here's the definition: const parseExpression = (expression?: TokenTree | NonBracketToken): AstNode => {
  // If the expression is an Array, we were passed another TokenTree, so we can
  // pass the expression back to the parseBlock function
  if (expression instanceof Array) {
    return parseBlock(expression);
  }

  // The mapping here is pretty straight forward. Match the token type and pass the
  // expression on to a more specific expression parser.
  if (isTokenType(expression, "identifier")) return parseIdentifier(expression);
  if (isTokenType(expression, "typed-identifier")) return parseTypedIdentifier(expression);
  if (isTokenType(expression, "float")) return parseFloatToken(expression);
  if (isTokenType(expression, "int")) return parseIntToken(expression);

  throw new Error(`Unrecognized expression ${JSON.stringify(expression)}`);
}; Let's define the function. This function is pretty neat and demonstrates one of the most powerful features of TypeScript, . Simply put, tests the expression and narrows down the type to a specific . This allows TypeScript to be certain we are passing the correct tokens to their corresponding parser functions down the line. isTokenType custom type guards isTokenType TokenType Here's the definition: export const isTokenType = <T extends Token["type"]>(
  item: TokenTree | NonBracketToken | undefined,
  type: T
): item is Extract<Token, { type: T }> => {
  return isToken(item) && item.type === type;
};

const isToken = (item?: TokenTree | NonBracketToken): item is NonBracketToken => {
  return !(item instanceof Array);
}; There's a lot happening there, so let's walk through it. First up, we have a generic definition, . This is essentially saying that T must be one of the possible values of the field. Typescript is smart enough to know that means T must be one of . <T extends Token["type"]> Token.type "int" | "float" | "identifier" | "typed-identifier" | "bracket The next interesting piece of code is the return type predicate . This predicate tells TypeScript that if the return value of is true, then must be the whose type matches the string passed as the parameter. item is Extract<Token, { type: T }> isTokenType item Token type In practice that means that if we were to pass an unknown to , typescript will be able to correctly narrow the value to a more specific token, like . Token isTokenType IntToken Now that we have our custom type guard defined, we can define the actual token parsers. The first three are simple; they essentially just return a copy or slightly modified copy of the token: const parseFloatToken = (float: FloatToken): FloatNode => ({ ...float });

const parseIntToken = (int: IntToken): IntNode => ({ ...int });

const parseIdentifier = (identifier: IdentifierToken): IdentifierNode => {
  return {
    type: "identifier",
    identifier: identifier.value,
  };
}; The final parser is the . Remember that a typed identifier takes the form . Parsing it is as simple as splitting the string by the colon. The first value of the returned array is the , the second is the . Here's the definition: parseTypedIdentifier identifier:type identifier type const parseTypedIdentifier = (identifier: TypedIdentifierToken): TypedIdentifierNode => {
  const vals = identifier.value.split(":");

  return {
    type: "typed-identifier",
    identifier: vals[0],
    typeIdentifier: vals[1],
  };
}; Here’s the finished file That's all the code required for a working parser. Before we move on, let's update the main file to view the output of the parser: src/index.mts // src/index.mts
#!/usr/bin/env node
import { readFileSync } from "fs";
import { lex } from "./lexer.mjs";
import { parse } from "./parser.mjs";

const file = process.argv[2];
const input = readFileSync(file, "utf8");

const tokens = lex(input);
const ast = parse(tokens);
console.log(JSON.stringify(tokens, undefined, 2)); Build and run project: npx tsc
wispy example.wispy If all goes well, the output should look like . this With that, the parser is finished. We can now convert the stream of tokens from the lexer into an AST. In the next post, we can get into the juicy bits: generating and running machine-readable code. today to see how Courier works to make product notifications delightful! Request a demo

How to Build a WebAssembly Language for Fun and Profit: Parsing

Cómo construir un lenguaje WebAssembly para divertirse y obtener ganancias: análisis

Comment créer un langage WebAssembly pour le plaisir et le profit : analyse

मनोरंजन और लाभ के लिए WebAssembly भाषा कैसे बनाएं: पार्सिंग

楽しみと利益のために WebAssembly 言語を構築する方法: 構文解析

Como construir uma linguagem WebAssembly para diversão e lucro: análise

Cách xây dựng ngôn ngữ WebAssembly để thú vị và lợi nhuận: Phân tích cú pháp

如何为乐趣和利润构建 WebAssembly 语言：解析

Lexical Analysis

This is my first article—I’m trying to learn this craft. It’s a compilation of comments I’ve made on various platforms across the web. I’ve tried to make some sense of an inherently fragmented discussion. Hope this helps ease your concerns about all the AI hype. This is my first article—I’m trying to learn this craft. It’s a compilation of comments I’ve made on various platforms across the web. I’ve tried to make some sense of an inherently fragmented discussion. Hope this helps ease your concerns about all the AI hype. Stone Soups I don’t know how to cook, at least not at the level of people who claim they can. But I do have plenty of experience with "Vibe Cooking." I could probably teach a class on it. I know how to fry an egg and make instant noodles; I know you need to add a bit of water when reheating rice and that butter is better than oil or margarine when frying an egg. Nothing more sophisticated to report. I know how to boil water, throw in some noodles (without the seasoning packet because it’s pure sodium), add some tomato sauce, and mix in whatever leftovers I have from the previous day. I season it with salt, oregano, and parsley if I have any, plus some pepper. If there’s ground beef, great. If not, a hot dog or boiled egg will do—I handle that in a parallel task. If I’m feeling extra creative, I throw in some beans and crispy potato sticks. The result is the famous "stone soup" dish. It’s funny to watch, maybe even TikTok-worthy, but I won’t be opening a restaurant or making money off it—unless, of course, I had thousands of followers. Since I’m a nobody in the grand scheme of things, I just make it for myself. And it gets the job done because I don’t enjoy cooking and have no desire to learn. Influencers might strike gold here. Plenty of them are blowing up on Instagram and TikTok doing worse. It’s probably just a bandwagon effect—I don’t see it as a sustainable business. But it’s fascinating to watch. X/@levesio recently shared his goal of making $1 million ARR with his fly-game, built entirely through vibe coding. A pretty profitable stone soup. I’m keeping a close eye on it to figure all this out. Vibe Cooking (Coding) Isn't a Threat No top chef has ever lost sleep over the rise of kitchen gadgets or the industrialization of instant noodles. Plenty of regular folks are making vibe-cooking meals at home with ramen and pasta. The upside: They don’t have to spend money eating out. And yet, restaurants are still packed, and food trucks still line the streets next to hot dog stands. I compare AI assistants to kitchen appliances like microwaves, using the same perspective as Chef Gordon Ramsay: they’re incredibly useful, but if you rely on them for everything, your food will turn out awful. Just knowing how to use a microwave or an air fryer doesn’t make you a chef. Top chefs still own professional knife sets because so much of their work is hands-on and artisanal. That won’t change anytime soon. The same goes for programming—especially when it comes to game development, which is almost an art form. Vibe coding has brought a lot of curious newcomers into the tech field—the so-called citizen developers—and that’s great. Encouraging people to learn programming and creating job opportunities benefits any country. I see huge potential in improving tools for vibe coding. Maybe soon, we’ll get better approaches to handling the non-deterministic nature of LLMs. But I don’t think many of them will stick around. At first, it’s fun—until the AI stops "vibing," and you actually have to roll up your sleeves and dive into the code. Coding can be tedious for some; it requires methodical thinking. I’ve already seen posts from people who built a SaaS and lost patience fixing bugs. Now they just want to sell it and move on. SaaS That’s why I’m not convinced that vibe coding is a sustainable business model for citizen developers. Coding is just one piece of the puzzle—most people don’t understand how we can sit for eight hours staring at a screen, “chewing” through code. Computer science has evolved massively over the last few decades; there’s a lot to learn, and the technical jargon alone is intimidating. But I could be wrong. As I said, I’m watching this space closely because it’s fascinating. The AI Boogeyman Back in the ’90s, CASE tools and code generators stirred up the same kind of panic. Marketers swore programming jobs would disappear. They sold well at first, mostly due to psychological pressure rather than real utility. But soon, people got fed up with "programming" because they weren’t cut out for it—or didn’t want to learn something new. And when maintenance time came around, no one wanted to sit down and fix the spaghetti code these tools generated. They dumped it on analysts and developers, who usually decided it was better to scrap everything and start over. Now, I see many developers genuinely worried about losing their jobs or struggling to stay in the industry. The rise of vibe coding is making it worse, fueled by AI hype. Big tech and startups are promoting this sensationalism, but programmers aren’t their real target—investors are. That’s why there are so many sketchy AI demos (see: the infamous Devin). It doesn’t matter if it “still” doesn’t work 100%. As long as it wows people, it’s got potential. That’s why billions are being poured into AI—because of its potential. This fear-mongering around junior devs doesn’t make sense. Companies are slashing salaries, cutting hiring, and spreading fear that AI will take over junior roles—all to keep the AI hype going and inflate stock prices. They’re discouraging the next generation. Eventually, it’ll end up like the COBOL market—where the experienced devs are aging out, and no new talent wants in. In my opinion, this entropy is temporary. Things feel chaotic due to the hype, but it will stabilize. AI won’t replace programmers—it’ll push companies to invest more in software development due to the efficiency AI brings. That means more job openings, especially for juniors. But patience is key while this “circus” winds down. Brave New World We’re witnessing another shift in computer programming. We’ll keep coding, but the "modus operandi" will change—just like it did when we moved on from punch cards and floppy disks or when Flash was replaced by HTML5 and modern frontend frameworks. The '90s and early 2000s brought a wave of new programming languages, and I believe we’ll see more in the coming years. Recently, AI has introduced a fresh batch of IDEs and tools, just like the early 2000s gave us Eclipse, Xcode, IntelliJ IDEA, Android Studio, and VS Code. In tech, people don’t cling to the past. (Almost) everyone adapts quickly—it’s part of the job. There’ll probably be even bigger impacts. AI chatting sites are affecting platforms like Stack Overflow and CodeProject, which now face the risk of extinction, just like Google impacted other search engines. Social media is increasingly full of AI-powered bots, YouTube now has AI-made videos, and Spotify is loaded with artificially generated music. The work AI does in coding is still mostly autocomplete, based on what it’s scraped from the web. The other day, I asked ChatGPT to generate a lexer and parser in Python for JavaScript. It spat out a program using the ply library—code that was straight from a GitHub repo. It just copied and pasted someone’s work... ply But these are fascinating times, living through this evolution with these tools at our fingertips. Using the ChatGPT app to practice English fluency is surreal—20 years ago, that’d be sci-fi. And sometimes GitHub Copilot suggests code that blows my mind, like it’s reading my thoughts. That lexer/parser I mentioned? I asked ChatGPT to explain parts of the code, and it did it perfectly, like I was chatting with the repo’s author. A New Evolution in Programming If you, reader, are Gen Z, you don’t have any memory of life without cell phones. I’m Gen X—I lived decades before using a mobile phone and remember what life was like with payphones on the street and a landline at home. I closely followed the impact of smartphones after 2008. It changed the world, made things a lot better, and it’ll get even better with AI. AI assistants in programming are the same deal: there’s no going back—use it or become obsolete; adopt it or turn into a hermit living in the mountains. It won’t replace a developer, but we’ll use it throughout whatever we’re programming. If you work on the Linux kernel, you’ll use it sparingly. If you’re at some corporation, you’ll use it for everything. Java programmers haven’t written constructor methods or getters and setters by hand in ages. It’s all auto-generated (thank you, Lombok!), and no one’s ever cared. An AI assistant like MS Copilot will help a ton with generating code, but we’ll still have to debug, write a lot of code, fix bugs, and so on. Plus, you often need to tweak and thoroughly test whatever it suggests or generates. If you don’t memorize phone numbers, you rely on your phone for that. You’ll become dependent on AI in programming the same way you depend on internet access, running water, gas, and electricity. You rely on banks, credit cards, and supermarkets, and soon you’ll rely on a personalized AI agent. Life goes on... There are still tons of opportunities to explore in IT, and there’ll be even more demand now that AI is “raising the bar.” We’ll see new programming platforms, new phones and computers (quantum chips!), and new professionals in demand, especially in development. Don’t worry about imposter syndrome—just focus on staying updated and knowing enough to critique and fix AI-generated code. Focus on your work, study what interests you, and don’t compare yourself to anyone. Wishing you success!

Vibe Coding and Stone Soup: Why AI Won’t Replace Developers Anytime Soon

Future Work in Rust Co-Assurance

Author:
(1) David S. Hardin, Cedar Rapids, IA USA (david.s.hardin@gmail.com). Table of Links 1 Introduction 2 Dancing Links 3 The Rust Programming Language 4 RAC: Hardware/Software Co-Assurance at Scale 5 Rust and RAR 5.1 Restricted Algorithmic Rust 6 Dancing Links in Rust and 6.1 Definitions 6.2 Translation to ACL2 6.3 Dancing Links Theorems 7 Related Work 8 Conclusion 9 Acknowledgments and References 3 The Rust Programming Language The Rust programming language has garnered significant interest and use as a modern, type-safe, memory-safe, and potentially formally analyzable programming language. Google [29] and Amazon [25] are major Rust adopters, and Linus Torvalds has commented positively on the near-term ability of the Rust toolchain to be used in Linux kernel development [1]. And after spending decades dealing with a never-ending parade of security vulnerabilities due to C/C++, which continue to manifest at a high rate [24] despite their use of sophisticated C/C++ analysis tools, Microsoft announced at its BlueHat 2023 developer conference that is was beginning to rewrite core Windows libraries in Rust [6]. Our interest in Rust stems from its potential as a hardware/software co-assurance language. This interest is motivated in part by emerging application areas, such as autonomous and semi-autonomous platforms for land, sea, air, and space, that require sophisticated algorithms and data structures, are subject to stringent accreditation/certification, and encourage hardware/software co-design approaches. (For an unmanned aerial vehicle use case illustrating a formal methods-based systems engineering environment, please consult [7] [23].) In this paper, we explore the use of Rust as a High-Level Synthesis (HLS) language [26]. HLS developers specify the high-level abstract behavior of a digital system in a manner that omits hardware design details such as clocking; the HLS toolchain is then responsible for “filling in the details” to produce a Register Transfer Level (RTL) structure that can be used to realize the design in hardware. HLS development is thus closer to software development than traditional hardware design in Hardware Description Languages (HDLs) such as Verilog or VHDL. Most incumbent HLS languages are a subset of C, e.g. Mentor Graphics’ Algorithmic C [21], or Vivado HLS by Xilinx [31], although other languages have also been used, e.g. OCaml [15]. A Rust-based HLS would bring a single modern, type-safe, and memory-safe expression language for both hardware and software realizations, with very high assurance. For formal methods researchers, Rust presents the opportunity to reason about application-level logic written in the imperative style favored by industry, but without the snarls of the unrestricted pointers of C/C++. Much progress has been made to this end in recent years, to the point that developers can verify the correctness of common algorithm and data structure code that utilizes common idioms such as records, loops, modular integers, and the like, and verified compilers can guarantee that such code is compiled correctly to binary [18]. Particular progress has been made in the area of hardware/software co-design algorithms, where array-backed data structures are common [10, 11]. (NB: This style of programming also addresses one of the shortcomings of Rust, namely its lack of support for cyclic data structures.) As a study of the suitability of Rust as an HLS, we have crafted a Rust subset, inspired by Russinoff’s Restricted Algorithmic C (RAC) [27], which we have imaginatively named Restricted Algorithmic Rust, or RAR [13]. In fact, in our first implementation of a RAR toolchain, we merely “transpile” (perform a source-to-source translation of) the RAR source into RAC. By so doing, we leverage a number of existing hardware/software co-assurance tools with a minimum investment of time and effort. By transpiling RAR to RAC, we gain access to existing HLS compilers (with the help of some simple C preprocessor directives, we are able to generate code for either the Algorithmic C or Vivado HLS toolchains). But most importantly for our research, we leverage the RAC-to-ACL2 translator that Russinoff and colleagues at Arm have successfully utilized in industrial-strength floating point hardware verification. We have implemented several representative algorithms and data structures in RAR, including: • a suite of array-backed algebraic data types, previously implemented in RAC (as reported in [10]); • a significant subset of the Monocypher [30] modern cryptography suite, including XChacha20 and Poly1305 (RFC 8439) encryption/decryption, BLAKE2b hashing, and X25519 public key cryptography [12]; and • a DFA-based JSON lexer, coupled with an LL(1) JSON parser. The JSON parser has also been implemented using Greibach Normal Form (previously implemented in RAC, as described in [14]). The RAR examples created to date are similar to their RAC counterparts in terms of expressiveness, and we deem the RAR versions somewhat superior in terms of readability (granted, this is a very subjective evaluation). In this paper, we will describe the development and formal verification of an array-based circular doubly-linked list (CDLL) data structure in RAR, including the Dancing Links optimization. Along the way, we will introduce the RAR subset of Rust, the RAR toolchain, the CDLL example, and detail our ACL2-based verification techniques, as well as the ACL2 books that we brought to bear on this example. It is hoped that this explication will convince the reader of the practicality of RAR as a high-assurance hardware/software co-design language, as well as the feasibility of the performing full functional correctness proofs of RAR code. We will then conclude with related and future work. This paper is available on arxiv under CC BY 4.0 DEED license. Author: (1) David S. Hardin, Cedar Rapids, IA USA (david.s.hardin@gmail.com). Author: Author: (1) David S. Hardin, Cedar Rapids, IA USA (david.s.hardin@gmail.com). Table of Links 1 Introduction 1 Introduction 2 Dancing Links 2 Dancing Links 3 The Rust Programming Language 3 The Rust Programming Language 4 RAC: Hardware/Software Co-Assurance at Scale 4 RAC: Hardware/Software Co-Assurance at Scale 5 Rust and RAR 5 Rust and RAR 5.1 Restricted Algorithmic Rust 5.1 Restricted Algorithmic Rust 6 Dancing Links in Rust and 6.1 Definitions 6 Dancing Links in Rust and 6.1 Definitions 6.2 Translation to ACL2 6.2 Translation to ACL2 6.3 Dancing Links Theorems 6.3 Dancing Links Theorems 7 Related Work 7 Related Work 8 Conclusion 8 Conclusion 9 Acknowledgments and References 9 Acknowledgments and References 3 The Rust Programming Language The Rust programming language has garnered significant interest and use as a modern, type-safe, memory-safe, and potentially formally analyzable programming language. Google [29] and Amazon [25] are major Rust adopters, and Linus Torvalds has commented positively on the near-term ability of the Rust toolchain to be used in Linux kernel development [1]. And after spending decades dealing with a never-ending parade of security vulnerabilities due to C/C++, which continue to manifest at a high rate [24] despite their use of sophisticated C/C++ analysis tools, Microsoft announced at its BlueHat 2023 developer conference that is was beginning to rewrite core Windows libraries in Rust [6]. Our interest in Rust stems from its potential as a hardware/software co-assurance language. This interest is motivated in part by emerging application areas, such as autonomous and semi-autonomous platforms for land, sea, air, and space, that require sophisticated algorithms and data structures, are subject to stringent accreditation/certification, and encourage hardware/software co-design approaches. (For an unmanned aerial vehicle use case illustrating a formal methods-based systems engineering environment, please consult [7] [23].) In this paper, we explore the use of Rust as a High-Level Synthesis (HLS) language [26]. HLS developers specify the high-level abstract behavior of a digital system in a manner that omits hardware design details such as clocking; the HLS toolchain is then responsible for “filling in the details” to produce a Register Transfer Level (RTL) structure that can be used to realize the design in hardware. HLS development is thus closer to software development than traditional hardware design in Hardware Description Languages (HDLs) such as Verilog or VHDL. Most incumbent HLS languages are a subset of C, e.g. Mentor Graphics’ Algorithmic C [21], or Vivado HLS by Xilinx [31], although other languages have also been used, e.g. OCaml [15]. A Rust-based HLS would bring a single modern, type-safe, and memory-safe expression language for both hardware and software realizations, with very high assurance. For formal methods researchers, Rust presents the opportunity to reason about application-level logic written in the imperative style favored by industry, but without the snarls of the unrestricted pointers of C/C++. Much progress has been made to this end in recent years, to the point that developers can verify the correctness of common algorithm and data structure code that utilizes common idioms such as records, loops, modular integers, and the like, and verified compilers can guarantee that such code is compiled correctly to binary [18]. Particular progress has been made in the area of hardware/software co-design algorithms, where array-backed data structures are common [10, 11]. (NB: This style of programming also addresses one of the shortcomings of Rust, namely its lack of support for cyclic data structures.) As a study of the suitability of Rust as an HLS, we have crafted a Rust subset, inspired by Russinoff’s Restricted Algorithmic C (RAC) [27], which we have imaginatively named Restricted Algorithmic Rust, or RAR [13]. In fact, in our first implementation of a RAR toolchain, we merely “transpile” (perform a source-to-source translation of) the RAR source into RAC. By so doing, we leverage a number of existing hardware/software co-assurance tools with a minimum investment of time and effort. By transpiling RAR to RAC, we gain access to existing HLS compilers (with the help of some simple C preprocessor directives, we are able to generate code for either the Algorithmic C or Vivado HLS toolchains). But most importantly for our research, we leverage the RAC-to-ACL2 translator that Russinoff and colleagues at Arm have successfully utilized in industrial-strength floating point hardware verification. We have implemented several representative algorithms and data structures in RAR, including: • a suite of array-backed algebraic data types, previously implemented in RAC (as reported in [10]); • a significant subset of the Monocypher [30] modern cryptography suite, including XChacha20 and Poly1305 (RFC 8439) encryption/decryption, BLAKE2b hashing, and X25519 public key cryptography [12]; and • a DFA-based JSON lexer, coupled with an LL(1) JSON parser. The JSON parser has also been implemented using Greibach Normal Form (previously implemented in RAC, as described in [14]). The RAR examples created to date are similar to their RAC counterparts in terms of expressiveness, and we deem the RAR versions somewhat superior in terms of readability (granted, this is a very subjective evaluation). In this paper, we will describe the development and formal verification of an array-based circular doubly-linked list (CDLL) data structure in RAR, including the Dancing Links optimization. Along the way, we will introduce the RAR subset of Rust, the RAR toolchain, the CDLL example, and detail our ACL2-based verification techniques, as well as the ACL2 books that we brought to bear on this example. It is hoped that this explication will convince the reader of the practicality of RAR as a high-assurance hardware/software co-design language, as well as the feasibility of the performing full functional correctness proofs of RAR code. We will then conclude with related and future work. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

The Case for Rust Programming as a Game-Changer for High-Level Synthesis

Author:
(1) David S. Hardin, Cedar Rapids, IA USA (david.s.hardin@gmail.com). Table of Links 1 Introduction 2 Dancing Links 3 The Rust Programming Language 4 RAC: Hardware/Software Co-Assurance at Scale 5 Rust and RAR 5.1 Restricted Algorithmic Rust 6 Dancing Links in Rust and 6.1 Definitions 6.2 Translation to ACL2 6.3 Dancing Links Theorems 7 Related Work 8 Conclusion 9 Acknowledgments and References 5 Rust and RAR The Rust Programming Language [16] is a modern, high-level programming language designed to combine the code generation efficiency of C/C++ with drastically improved type safety and memory management features. A distinguishing feature of Rust is that a non-scalar object may only have one owner. For example, one cannot assign a reference to an object in a local variable, and then pass that reference to a function. This restriction is similar to those imposed on ACL2 single-threaded objects (stobjs) [4], with the additional complexities of enforcing such “single-owner” restrictions in the context of a generalpurpose, imperative programming language. The Rust runtime performs array bounds checking, as well as arithmetic overflow checking (the latter can be disabled by a build environment setting). In most other ways, Rust is a fairly conventional modern programming language, with interfaces (called traits), lambdas (termed closures), and pattern matching, as well as a macro capability. Also in keeping with other modern programming language ecosystems, Rust features a language-specific build and package management sytem, named cargo. 5.1 Restricted Algorithmic Rust As we wish to utilize the RAC toolchain as a backend in our initial work, Restricted Algorithmic Rust is semantically equivalent to RAC. Thus, we adopt the same semantic restrictions as described in Russinoff’s book. Additionally, in order to enable translation to RAC, as well as to ease the transition from C/C++, RAR supports a commonly used macro that provides a C-like for loop in Rust. Note that, despite the restrictions, RAR code is proper Rust; it compiles to binary using the standard Rust compiler. RAR is transpiled to RAC via a source-to-source translator, as depicted in Fig. 3. Our transpiler is based on the plex parser and lexer generator [28] source code. We thus call our transpiler Plexi, a nickname given to a famous (and now highly sought-after) line of Marshall guitar amplifiers of the mid-1960s. Plexi performs lexical and syntactic transformations that convert RAR code to RAC code. Recent improvements in the plexi tool include better handling of array declarations, as well as providing support for Rust const declarations. The generated RAC code can then be compiled using a C/C++ compiler, fed to an HLS-based FPGA compiler, as well as translated to ACL2 via the RAC ACL2 translator, as illustrated in Fig. 3. This paper is available on arxiv under CC BY 4.0 DEED license. Author: (1) David S. Hardin, Cedar Rapids, IA USA (david.s.hardin@gmail.com). Author: Author: (1) David S. Hardin, Cedar Rapids, IA USA (david.s.hardin@gmail.com). Table of Links 1 Introduction 1 Introduction 2 Dancing Links 2 Dancing Links 3 The Rust Programming Language 3 The Rust Programming Language 4 RAC: Hardware/Software Co-Assurance at Scale 4 RAC: Hardware/Software Co-Assurance at Scale 5 Rust and RAR 5 Rust and RAR 5.1 Restricted Algorithmic Rust 5.1 Restricted Algorithmic Rust 6 Dancing Links in Rust and 6.1 Definitions 6 Dancing Links in Rust and 6.1 Definitions 6.2 Translation to ACL2 6.2 Translation to ACL2 6.3 Dancing Links Theorems 6.3 Dancing Links Theorems 7 Related Work 7 Related Work 8 Conclusion 8 Conclusion 9 Acknowledgments and References 9 Acknowledgments and References 5 Rust and RAR The Rust Programming Language [16] is a modern, high-level programming language designed to combine the code generation efficiency of C/C++ with drastically improved type safety and memory management features. A distinguishing feature of Rust is that a non-scalar object may only have one owner. For example, one cannot assign a reference to an object in a local variable, and then pass that reference to a function. This restriction is similar to those imposed on ACL2 single-threaded objects (stobjs) [4], with the additional complexities of enforcing such “single-owner” restrictions in the context of a generalpurpose, imperative programming language. The Rust runtime performs array bounds checking, as well as arithmetic overflow checking (the latter can be disabled by a build environment setting). In most other ways, Rust is a fairly conventional modern programming language, with interfaces (called traits), lambdas (termed closures), and pattern matching, as well as a macro capability. Also in keeping with other modern programming language ecosystems, Rust features a language-specific build and package management sytem, named cargo. 5.1 Restricted Algorithmic Rust As we wish to utilize the RAC toolchain as a backend in our initial work, Restricted Algorithmic Rust is semantically equivalent to RAC. Thus, we adopt the same semantic restrictions as described in Russinoff’s book. Additionally, in order to enable translation to RAC, as well as to ease the transition from C/C++, RAR supports a commonly used macro that provides a C-like for loop in Rust. Note that, despite the restrictions, RAR code is proper Rust; it compiles to binary using the standard Rust compiler. RAR is transpiled to RAC via a source-to-source translator, as depicted in Fig. 3. Our transpiler is based on the plex parser and lexer generator [28] source code. We thus call our transpiler Plexi, a nickname given to a famous (and now highly sought-after) line of Marshall guitar amplifiers of the mid-1960s. Plexi performs lexical and syntactic transformations that convert RAR code to RAC code. Recent improvements in the plexi tool include better handling of array declarations, as well as providing support for Rust const declarations. The generated RAC code can then be compiled using a C/C++ compiler, fed to an HLS-based FPGA compiler, as well as translated to ACL2 via the RAC ACL2 translator, as illustrated in Fig. 3. This paper is available on arxiv under CC BY 4.0 DEED license. This paper is available on arxiv under CC BY 4.0 DEED license. available on arxiv

RRR—Rust, RAR, and RAC: The Trifecta for Co-Design Excellence

Author:
(1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Table of Links Abstract and Introduction
Dancing Links
The Rust Programming Language
RAC: Hardware/Software Co-Assurance at Scale
Rust and RAR
Dancing Links in Rust
Related Work
Conclusion, Acknowledgments, and References 5 Rust and RAR The Rust Programming Language [16] is a modern, high-level programming language designed to combine the code generation efficiency of C/C++ with drastically improved type safety and memory management features. A distinguishing feature of Rust is that a non-scalar object may only have one owner. For example, one cannot assign a reference to an object in a local variable, and then pass that reference to a function. This restriction is similar to those imposed on ACL2 single-threaded objects (stobjs) [4], with the additional complexities of enforcing such “single-owner” restrictions in the context of a generalpurpose, imperative programming language. The Rust runtime performs array bounds checking, as well as arithmetic overflow checking (the latter can be disabled by a build environment setting). In most other ways, Rust is a fairly conventional modern programming language, with interfaces (called traits), lambdas (termed closures), and pattern matching, as well as a macro capability. Also in keeping with other modern programming language ecosystems, Rust features a language-specific build and package management sytem, named cargo. 5.1 Restricted Algorithmic Rust As we wish to utilize the RAC toolchain as a backend in our initial work, Restricted Algorithmic Rust is semantically equivalent to RAC. Thus, we adopt the same semantic restrictions as described in Russinoff’s book. Additionally, in order to enable translation to RAC, as well as to ease the transition from C/C++, RAR supports a commonly used macro that provides a C-like for loop in Rust. Note that, despite the restrictions, RAR code is proper Rust; it compiles to binary using the standard Rust compiler. RAR is transpiled to RAC via a source-to-source translator, as depicted in Fig. 3. Our transpiler is based on the plex parser and lexer generator [28] source code. We thus call our transpiler Plexi, a nickname given to a famous (and now highly sought-after) line of Marshall guitar amplifiers of the mid-1960s. Plexi performs lexical and syntactic transformations that convert RAR code to RAC code. Recent improvements in the plexi tool include better handling of array declarations, as well as providing support for Rust const declarations. The generated RAC code can then be compiled using a C/C++ compiler, fed to an HLS-based FPGA compiler, as well as translated to ACL2 via the RAC ACL2 translator, as illustrated in Fig. 3. This paper is available on arxiv under CC 4.0 license. Author: (1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Author: Author: (1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Table of Links Abstract and Introduction Dancing Links The Rust Programming Language RAC: Hardware/Software Co-Assurance at Scale Rust and RAR Dancing Links in Rust Related Work Conclusion, Acknowledgments, and References Abstract and Introduction Abstract and Introduction Dancing Links Dancing Links The Rust Programming Language The Rust Programming Language RAC: Hardware/Software Co-Assurance at Scale RAC: Hardware/Software Co-Assurance at Scale Rust and RAR Rust and RAR Dancing Links in Rust Dancing Links in Rust Related Work Related Work Conclusion, Acknowledgments, and References Conclusion, Acknowledgments, and References 5 Rust and RAR The Rust Programming Language [16] is a modern, high-level programming language designed to combine the code generation efficiency of C/C++ with drastically improved type safety and memory management features. A distinguishing feature of Rust is that a non-scalar object may only have one owner. For example, one cannot assign a reference to an object in a local variable, and then pass that reference to a function. This restriction is similar to those imposed on ACL2 single-threaded objects (stobjs) [4], with the additional complexities of enforcing such “single-owner” restrictions in the context of a generalpurpose, imperative programming language. The Rust runtime performs array bounds checking, as well as arithmetic overflow checking (the latter can be disabled by a build environment setting). In most other ways, Rust is a fairly conventional modern programming language, with interfaces (called traits), lambdas (termed closures), and pattern matching, as well as a macro capability. Also in keeping with other modern programming language ecosystems, Rust features a language-specific build and package management sytem, named cargo. 5.1 Restricted Algorithmic Rust As we wish to utilize the RAC toolchain as a backend in our initial work, Restricted Algorithmic Rust is semantically equivalent to RAC. Thus, we adopt the same semantic restrictions as described in Russinoff’s book. Additionally, in order to enable translation to RAC, as well as to ease the transition from C/C++, RAR supports a commonly used macro that provides a C-like for loop in Rust. Note that, despite the restrictions, RAR code is proper Rust; it compiles to binary using the standard Rust compiler. RAR is transpiled to RAC via a source-to-source translator, as depicted in Fig. 3. Our transpiler is based on the plex parser and lexer generator [28] source code. We thus call our transpiler Plexi, a nickname given to a famous (and now highly sought-after) line of Marshall guitar amplifiers of the mid-1960s. Plexi performs lexical and syntactic transformations that convert RAR code to RAC code. Recent improvements in the plexi tool include better handling of array declarations, as well as providing support for Rust const declarations. The generated RAC code can then be compiled using a C/C++ compiler, fed to an HLS-based FPGA compiler, as well as translated to ACL2 via the RAC ACL2 translator, as illustrated in Fig. 3. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Verification of a Rust Implementation of Knuth’s Dancing
Links Using ACL2: Rust and RAR

Author:
(1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Table of Links Abstract and Introduction
Dancing Links
The Rust Programming Language
RAC: Hardware/Software Co-Assurance at Scale
Rust and RAR
Dancing Links in Rust
Related Work
Conclusion, Acknowledgments, and References 8 Conclusion We have developed a prototype toolchain to allow the Rust programming language to be used as a hardware/software co-design and co-assurance language for critical systems, standing on the shoulders of Russinoff’s team at Arm, and all the great work they have done on Restricted Algorithmic C. We have demonstrated the ability to establish the correctness of several practical data structures commonly found in high-assurance systems (e.g., array-backed singly-linked lists, doubly-linked lists, stacks, and dequeues) through automated formal verification, enabled by automated source-to-source translation from Rust to RAC to ACL2, and have detailed the specification and verification of one such data structure, a circular doubly-linked list employing Knuth’s “Dancing Links” optimization. We have also successfully applied our toolchain to cryptography and data format filtering examples typical of the sorts of algorithms that one encounters in critical systems development. In future work, we will continue to develop our toolchain, increasing the number of Rust features that we can support in the RAR subset, as well as continuing to improve the ACL2 verification libraries in order to increase the ability to discharge RAR correctness proofs automatically. We will also continue to work with our colleagues at Kansas State University on the direct synthesis and verification of RAR code from architectural models, as well as working with colleagues at the University of Kansas on verified synthesis of Rust code from high-level attestation protocol specifications written using the Coq theorem prover. 9 Acknowledgments Many thanks to Donald Knuth for his detailed study of exact cover problems in general, and the “Dancing Links” optimization in particular, that can now be found in Volume 4B of his seminal series, The Art of Computer Programming. It was a pleasure discovering this particular corner of Computer Science, beginning when the author accidentally stumbled upon a previously recorded Knuth “Christmas Lecture” on the subject in late 2022. Previous foundational work on hardware/software co-assurance in Rust was funded by DARPA contract HR00111890001. The views, opinions and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Many thanks to David Russinoff of Arm for developing and improving the RAC toolchain, without which most of the current work would not be possible. Thanks also go to the anonymous reviewers for their insightful comments. References [1] Ron Amadeo (2021): Google is now writing low-level Android code in Rust. Available at https://arstechnica.com/gadgets/2021/04/ google-is-now-writing-low-level-android-code-in-rust/. [2] Amazon Web Services (2022): Announcing the Kani Rust Verifier Project. Available at https://model-checking.github.io/kani-verifier-blog/2022/ 05/04/announcing-the-kani-rust-verifier-project.html?fbclid=IwAR2M_ B1IEBfkVhIXSuuAxt3McC_QpUnTuzDq9jG40HOaJzxw8z1Nw9XU_i4. [3] V. Astrauskas, A. B´ıl ´y, J. Fiala, Z. Grannan, C. Matheja, P. M ¨uller, F. Poli & A. J. Summers (2022): The Prusti Project: Formal Verification for Rust (invited). In: NASA Formal Methods (14th International Symposium), Springer, pp. 88–108, doi:10.1007/978-3-031-06773-0_5. Available at https://link.springer. com/chapter/10.1007/978-3-031-06773-0_5. [4] Robert S. Boyer & J Strother Moore (2002): Single-Threaded Objects in ACL2. In: Practical Aspects of Declarative Languages, 4th International Symposium, PADL 2002, Portland, OR, USA, January 19-20, 2002, Proceedings, LNCS 2257, Springer, pp. 9–27, doi:10.1007/3-540-45587-6_3. [5] Sally Browning & Philip Weaver (2010): Designing Tunable, Verifiable Cryptographic Hardware Using Cryptol. In David S. Hardin, editor: Design and Verification of Microprocessor Systems for High-Assurance Applications, Springer, pp. 89–143, doi:10.1007/978-1-4419-1539-9_4. [6] Thomas Claburn (2023): Microsoft is busy rewriting core Windows code in memory-safe Rust. Available at https://www.theregister.com/2023/04/27/microsoft_windows_rust/. [7] Darren Cofer, Isaac Amundson, Junaid Babar, David Hardin, Konrad Slind, Perry Alexander, John Hatcliff, Robby, Gerwin Klein, Corey Lewis, Eric Mercer & John Shackleton (2022): Cyber Assured Systems Engineering at Scale. In: IEEE Security & Privacy, pp. 52–64, doi:10.1109/MSEC.2022.3151733. [8] Xavier Denis (2022): Creusot. Available at https://github.com/xldenis/creusot. [9] Peter H. Feiler & David P. Gluch (2012): Model-Based Engineering with AADL: An Introduction to the SAE Architecture Analysis & Design Language, 1st edition. Addison-Wesley Professional. [10] David S. Hardin (2020): Put Me on the RAC. In: Proceedings of the Sixteenth International Workshop on the ACL2 Theorem Prover and its Applications (ACL2-20), pp. 142–145, doi:10.4204/eptcs.327.13. [11] David S. Hardin (2020): Verified Hardware/Software Co-Assurance: Enhancing Safety and Security for Critical Systems. In: Proceedings of the 2020 IEEE Systems Conference, doi:10.1109/SysCon47679. 2020.9381831. [12] David S. Hardin (2022): Hardware/Software Co-Assurance for the Rust Programming Language Applied to Zero-Trust Architecture Development. ACM SIGAda Ada Letters 42(2), pp. 55–61, doi:10.1145/3591335. 3591340. [13] David S. Hardin (2022): Hardware/Software Co-Assurance using the Rust Programming Language and ACL2. In: Proceedings of the Seventeenth International Workshop on the ACL2 Theorem Prover and its Applications (ACL2-22), pp. 202–216, doi:10.4204/EPTCS.359.16. [14] David S. Hardin & Konrad L. Slind (2021): Formal Synthesis of Filter Components for Use in SecurityEnhancing Architectural Transformations. In: Proceedings of the Seventh Workshop on Language-Theoretic Security, 42nd IEEE Symposium and Workshops on Security and Privacy (LangSec 2021), doi:10.1109/ SPW53761.2021.00024. [15] Jane Street Group, LLC (2023): Hardcaml: An OCaml library for designing and testing hardware designs. Available at https://github.com/janestreet/hardcaml. [16] Steve Klabnik & Carol Nichols (2018): The Rust Programming Language. No Starch Press. [17] Donald E. Knuth (2022): The Art of Computer Programming. 4B: Combinatorial Algorithms, Part 2, Addison-Wesley. [18] Ramana Kumar, Magnus O. Myreen, Michael Norrish & Scott Owens (2014): CakeML: a verified implementation of ML. In Suresh Jagannathan & Peter Sewell, editors: The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, San Diego, CA, USA, January 20-21, 2014, ACM, pp. 179–192, doi:10.1145/2535838.2535841. [19] Andrea Lattuada, Travis Hance, Chanhee Cho, Matthias Brun, Isitha Subasinghe, Yi Zhou, Jon Howell, Bryan Parno & Chris Hawblitzel (2023): Verus: Verifying Rust Programs Using Linear Ghost Types. Proc. ACM Program. Lang. 7(OOPSLA1), doi:10.1145/3586037. [20] Yusuke Matsushita, Takeshi Tsukada & Naoki Kobayashi (2021): RustHorn: CHC-Based Verification for Rust Programs. ACM Trans. Program. Lang. Syst. 43(4), doi:10.1145/3462205. [21] Mentor Graphics Corporation (2016): Algorithmic C (AC) Datatypes. Available at https://www.mentor. com/hls-lp/downloads/ac-datatypes. [22] Mentor Graphics Corporation (2020): Catapult High-Level Synthesis. Available at https://www.mentor. com/hls-lp/catapult-high-level-synthesis/. [23] Eric Mercer, Konrad Slind, Isaac Amundson, Darren Cofer, Junaid Babar & David Hardin (2023): Synthesizing Verified Components for Cyber Assured Systems Engineering. In: Software and Systems Modeling, 22, pp. 1451–1471, doi:10.1007/s10270-023-01096-3. [24] Matt Miller (2019): A proactive approach to more secure code. Available at https://msrc-blog. microsoft.com/2019/07/16/a-proactive-approach-to-more-secure-code/. [25] Shane Miller & Carl Lerche (2022): Sustainability with Rust. Available at https://aws.amazon.com/ blogs/opensource/sustainability-with-rust/. [26] Razvan Nane, Vlad-Mihai Sima, Christian Pilato, Jongsok Choi, Blair Fort, Andrew Canis, Yu Ting Chen, Hsuan Hsiao, Stephen Brown, Fabrizio Ferrandi, Jason Anderson & Koen Bertels (2016): A Survey and Evaluation of FPGA High-Level Synthesis Tools. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 35(10), pp. 1591–1604, doi:10.1109/TCAD.2015.2513673. [27] David M. Russinoff (2022): Formal Verification of Floating-Point Hardware Design: A Mathematical Approach, second edition. Springer, doi:10.1007/978-3-030-87181-9. [28] Geoffry Song (2020): plex: a parser and lexer generator as a Rust procedural macro. Available at https:// github.com/goffrie/plex. [29] Jeff Vander Stoep & Stephen Hines (2021): Rust in the Android platform. Available at https://security. googleblog.com/2021/04/rust-in-android-platform.html. [30] Loup Vaillant (2022): Monocypher: Boring Crypto that Simply Works. Available at https://monocypher. org. [31] Xilinx, Inc. (2018): Vivado Design Suite User Guide: High-Level Synthesis. Available at https://www.xilinx.com/support/documentation/sw_manuals/xilinx2018_3/ ug902-vivado-high-level-synthesis.pdf. This paper is available on arxiv under CC 4.0 license. Author: (1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Author: Author: (1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Table of Links Abstract and Introduction Dancing Links The Rust Programming Language RAC: Hardware/Software Co-Assurance at Scale Rust and RAR Dancing Links in Rust Related Work Conclusion, Acknowledgments, and References Abstract and Introduction Abstract and Introduction Dancing Links Dancing Links The Rust Programming Language The Rust Programming Language RAC: Hardware/Software Co-Assurance at Scale RAC: Hardware/Software Co-Assurance at Scale Rust and RAR Rust and RAR Dancing Links in Rust Dancing Links in Rust Related Work Related Work Conclusion, Acknowledgments, and References Conclusion, Acknowledgments, and References 8 Conclusion We have developed a prototype toolchain to allow the Rust programming language to be used as a hardware/software co-design and co-assurance language for critical systems, standing on the shoulders of Russinoff’s team at Arm, and all the great work they have done on Restricted Algorithmic C. We have demonstrated the ability to establish the correctness of several practical data structures commonly found in high-assurance systems (e.g., array-backed singly-linked lists, doubly-linked lists, stacks, and dequeues) through automated formal verification, enabled by automated source-to-source translation from Rust to RAC to ACL2, and have detailed the specification and verification of one such data structure, a circular doubly-linked list employing Knuth’s “Dancing Links” optimization. We have also successfully applied our toolchain to cryptography and data format filtering examples typical of the sorts of algorithms that one encounters in critical systems development. In future work, we will continue to develop our toolchain, increasing the number of Rust features that we can support in the RAR subset, as well as continuing to improve the ACL2 verification libraries in order to increase the ability to discharge RAR correctness proofs automatically. We will also continue to work with our colleagues at Kansas State University on the direct synthesis and verification of RAR code from architectural models, as well as working with colleagues at the University of Kansas on verified synthesis of Rust code from high-level attestation protocol specifications written using the Coq theorem prover. 9 Acknowledgments Many thanks to Donald Knuth for his detailed study of exact cover problems in general, and the “Dancing Links” optimization in particular, that can now be found in Volume 4B of his seminal series, The Art of Computer Programming. It was a pleasure discovering this particular corner of Computer Science, beginning when the author accidentally stumbled upon a previously recorded Knuth “Christmas Lecture” on the subject in late 2022. Previous foundational work on hardware/software co-assurance in Rust was funded by DARPA contract HR00111890001. The views, opinions and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Many thanks to David Russinoff of Arm for developing and improving the RAC toolchain, without which most of the current work would not be possible. Thanks also go to the anonymous reviewers for their insightful comments. References [1] Ron Amadeo (2021): Google is now writing low-level Android code in Rust. Available at https://arstechnica.com/gadgets/2021/04/ google-is-now-writing-low-level-android-code-in-rust/. [2] Amazon Web Services (2022): Announcing the Kani Rust Verifier Project. Available at https://model-checking.github.io/kani-verifier-blog/2022/ 05/04/announcing-the-kani-rust-verifier-project.html?fbclid=IwAR2M_ B1IEBfkVhIXSuuAxt3McC_QpUnTuzDq9jG40HOaJzxw8z1Nw9XU_i4. [3] V. Astrauskas, A. B´ıl ´y, J. Fiala, Z. Grannan, C. Matheja, P. M ¨uller, F. Poli & A. J. Summers (2022): The Prusti Project: Formal Verification for Rust (invited). In: NASA Formal Methods (14th International Symposium), Springer, pp. 88–108, doi:10.1007/978-3-031-06773-0_5. Available at https://link.springer. com/chapter/10.1007/978-3-031-06773-0_5. [4] Robert S. Boyer & J Strother Moore (2002): Single-Threaded Objects in ACL2. In: Practical Aspects of Declarative Languages, 4th International Symposium, PADL 2002, Portland, OR, USA, January 19-20, 2002, Proceedings, LNCS 2257, Springer, pp. 9–27, doi:10.1007/3-540-45587-6_3. [5] Sally Browning & Philip Weaver (2010): Designing Tunable, Verifiable Cryptographic Hardware Using Cryptol. In David S. Hardin, editor: Design and Verification of Microprocessor Systems for High-Assurance Applications, Springer, pp. 89–143, doi:10.1007/978-1-4419-1539-9_4. [6] Thomas Claburn (2023): Microsoft is busy rewriting core Windows code in memory-safe Rust. Available at https://www.theregister.com/2023/04/27/microsoft_windows_rust/. [7] Darren Cofer, Isaac Amundson, Junaid Babar, David Hardin, Konrad Slind, Perry Alexander, John Hatcliff, Robby, Gerwin Klein, Corey Lewis, Eric Mercer & John Shackleton (2022): Cyber Assured Systems Engineering at Scale. In: IEEE Security & Privacy, pp. 52–64, doi:10.1109/MSEC.2022.3151733. [8] Xavier Denis (2022): Creusot. Available at https://github.com/xldenis/creusot. [9] Peter H. Feiler & David P. Gluch (2012): Model-Based Engineering with AADL: An Introduction to the SAE Architecture Analysis & Design Language, 1st edition. Addison-Wesley Professional. [10] David S. Hardin (2020): Put Me on the RAC. In: Proceedings of the Sixteenth International Workshop on the ACL2 Theorem Prover and its Applications (ACL2-20), pp. 142–145, doi:10.4204/eptcs.327.13. [11] David S. Hardin (2020): Verified Hardware/Software Co-Assurance: Enhancing Safety and Security for Critical Systems. In: Proceedings of the 2020 IEEE Systems Conference, doi:10.1109/SysCon47679. 2020.9381831. [12] David S. Hardin (2022): Hardware/Software Co-Assurance for the Rust Programming Language Applied to Zero-Trust Architecture Development. ACM SIGAda Ada Letters 42(2), pp. 55–61, doi:10.1145/3591335. 3591340. [13] David S. Hardin (2022): Hardware/Software Co-Assurance using the Rust Programming Language and ACL2. In: Proceedings of the Seventeenth International Workshop on the ACL2 Theorem Prover and its Applications (ACL2-22), pp. 202–216, doi:10.4204/EPTCS.359.16. [14] David S. Hardin & Konrad L. Slind (2021): Formal Synthesis of Filter Components for Use in SecurityEnhancing Architectural Transformations. In: Proceedings of the Seventh Workshop on Language-Theoretic Security, 42nd IEEE Symposium and Workshops on Security and Privacy (LangSec 2021), doi:10.1109/ SPW53761.2021.00024. [15] Jane Street Group, LLC (2023): Hardcaml: An OCaml library for designing and testing hardware designs. Available at https://github.com/janestreet/hardcaml. [16] Steve Klabnik & Carol Nichols (2018): The Rust Programming Language. No Starch Press. [17] Donald E. Knuth (2022): The Art of Computer Programming. 4B: Combinatorial Algorithms, Part 2, Addison-Wesley. [18] Ramana Kumar, Magnus O. Myreen, Michael Norrish & Scott Owens (2014): CakeML: a verified implementation of ML. In Suresh Jagannathan & Peter Sewell, editors: The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, San Diego, CA, USA, January 20-21, 2014, ACM, pp. 179–192, doi:10.1145/2535838.2535841. [19] Andrea Lattuada, Travis Hance, Chanhee Cho, Matthias Brun, Isitha Subasinghe, Yi Zhou, Jon Howell, Bryan Parno & Chris Hawblitzel (2023): Verus: Verifying Rust Programs Using Linear Ghost Types. Proc. ACM Program. Lang. 7(OOPSLA1), doi:10.1145/3586037. [20] Yusuke Matsushita, Takeshi Tsukada & Naoki Kobayashi (2021): RustHorn: CHC-Based Verification for Rust Programs. ACM Trans. Program. Lang. Syst. 43(4), doi:10.1145/3462205. [21] Mentor Graphics Corporation (2016): Algorithmic C (AC) Datatypes. Available at https://www.mentor. com/hls-lp/downloads/ac-datatypes. [22] Mentor Graphics Corporation (2020): Catapult High-Level Synthesis. Available at https://www.mentor. com/hls-lp/catapult-high-level-synthesis/. [23] Eric Mercer, Konrad Slind, Isaac Amundson, Darren Cofer, Junaid Babar & David Hardin (2023): Synthesizing Verified Components for Cyber Assured Systems Engineering. In: Software and Systems Modeling, 22, pp. 1451–1471, doi:10.1007/s10270-023-01096-3. [24] Matt Miller (2019): A proactive approach to more secure code. Available at https://msrc-blog. microsoft.com/2019/07/16/a-proactive-approach-to-more-secure-code/. [25] Shane Miller & Carl Lerche (2022): Sustainability with Rust. Available at https://aws.amazon.com/ blogs/opensource/sustainability-with-rust/. [26] Razvan Nane, Vlad-Mihai Sima, Christian Pilato, Jongsok Choi, Blair Fort, Andrew Canis, Yu Ting Chen, Hsuan Hsiao, Stephen Brown, Fabrizio Ferrandi, Jason Anderson & Koen Bertels (2016): A Survey and Evaluation of FPGA High-Level Synthesis Tools. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 35(10), pp. 1591–1604, doi:10.1109/TCAD.2015.2513673. [27] David M. Russinoff (2022): Formal Verification of Floating-Point Hardware Design: A Mathematical Approach, second edition. Springer, doi:10.1007/978-3-030-87181-9. [28] Geoffry Song (2020): plex: a parser and lexer generator as a Rust procedural macro. Available at https:// github.com/goffrie/plex. [29] Jeff Vander Stoep & Stephen Hines (2021): Rust in the Android platform. Available at https://security. googleblog.com/2021/04/rust-in-android-platform.html. [30] Loup Vaillant (2022): Monocypher: Boring Crypto that Simply Works. Available at https://monocypher. org. [31] Xilinx, Inc. (2018): Vivado Design Suite User Guide: High-Level Synthesis. Available at https://www.xilinx.com/support/documentation/sw_manuals/xilinx2018_3/ ug902-vivado-high-level-synthesis.pdf. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Rust Implementation of Knuth's Dancing Links: Conclusion, Acknowledgments, and References

Author:
(1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Table of Links Abstract and Introduction
Dancing Links
The Rust Programming Language
RAC: Hardware/Software Co-Assurance at Scale
Rust and RAR
Dancing Links in Rust
Related Work
Conclusion, Acknowledgments, and References 3 The Rust Programming Language The Rust programming language has garnered significant interest and use as a modern, type-safe, memorysafe, and potentially formally analyzable programming language. Google [29] and Amazon [25] are major Rust adopters, and Linus Torvalds has commented positively on the near-term ability of the Rust toolchain to be used in Linux kernel development [1]. And after spending decades dealing with a never-ending parade of security vulnerabilities due to C/C++, which continue to manifest at a high rate [24] despite their use of sophisticated C/C++ analysis tools, Microsoft announced at its BlueHat 2023 developer conference that is was beginning to rewrite core Windows libraries in Rust [6]. Our interest in Rust stems from its potential as a hardware/software co-assurance language. This interest is motivated in part by emerging application areas, such as autonomous and semi-autonomous platforms for land, sea, air, and space, that require sophisticated algorithms and data structures, are subject to stringent accreditation/certification, and encourage hardware/software co-design approaches. (For an unmanned aerial vehicle use case illustrating a formal methods-based systems engineering environment, please consult [7] [23].) In this paper, we explore the use of Rust as a High-Level Synthesis (HLS) language [26]. HLS developers specify the high-level abstract behavior of a digital system in a manner that omits hardware design details such as clocking; the HLS toolchain is then responsible for “filling in the details” to produce a Register Transfer Level (RTL) structure that can be used to realize the design in hardware. HLS development is thus closer to software development than traditional hardware design in Hardware Description Languages (HDLs) such as Verilog or VHDL. Most incumbent HLS languages are a subset of C, e.g. Mentor Graphics’ Algorithmic C [21], or Vivado HLS by Xilinx [31], although other languages have also been used, e.g. OCaml [15]. A Rust-based HLS would bring a single modern, type-safe, and memory-safe expression language for both hardware and software realizations, with very high assurance. For formal methods researchers, Rust presents the opportunity to reason about application-level logic written in the imperative style favored by industry, but without the snarls of the unrestricted pointers of C/C++. Much progress has been made to this end in recent years, to the point that developers can verify the correctness of common algorithm and data structure code that utilizes common idioms such as records, loops, modular integers, and the like, and verified compilers can guarantee that such code is compiled correctly to binary [18]. Particular progress has been made in the area of hardware/software co-design algorithms, where array-backed data structures are common [10, 11]. (NB: This style of programming also addresses one of the shortcomings of Rust, namely its lack of support for cyclic data structures.) As a study of the suitability of Rust as an HLS, we have crafted a Rust subset, inspired by Russinoff’s Restricted Algorithmic C (RAC) [27], which we have imaginatively named Restricted Algorithmic Rust, or RAR [13]. In fact, in our first implementation of a RAR toolchain, we merely “transpile” (perform a source-to-source translation of) the RAR source into RAC. By so doing, we leverage a number of existing hardware/software co-assurance tools with a minimum investment of time and effort. By transpiling RAR to RAC, we gain access to existing HLS compilers (with the help of some simple C preprocessor directives, we are able to generate code for either the Algorithmic C or Vivado HLS toolchains). But most importantly for our research, we leverage the RAC-to-ACL2 translator that Russinoff and colleagues at Arm have successfully utilized in industrial-strength floating point hardware verification. We have implemented several representative algorithms and data structures in RAR, including: • a suite of array-backed algebraic data types, previously implemented in RAC (as reported in [10]); • a significant subset of the Monocypher [30] modern cryptography suite, including XChacha20 and Poly1305 (RFC 8439) encryption/decryption, BLAKE2b hashing, and X25519 public key cryptography [12]; and • a DFA-based JSON lexer, coupled with an LL(1) JSON parser. The JSON parser has also been implemented using Greibach Normal Form (previously implemented in RAC, as described in [14]). The RAR examples created to date are similar to their RAC counterparts in terms of expressiveness, and we deem the RAR versions somewhat superior in terms of readability (granted, this is a very subjective evaluation). In this paper, we will describe the development and formal verification of an array-based circular doubly-linked list (CDLL) data structure in RAR, including the Dancing Links optimization. Along the way, we will introduce the RAR subset of Rust, the RAR toolchain, the CDLL example, and detail our ACL2-based verification techniques, as well as the ACL2 books that we brought to bear on this example. It is hoped that this explication will convince the reader of the practicality of RAR as a high-assurance hardware/software co-design language, as well as the feasibility of the performing full functional correctness proofs of RAR code. We will then conclude with related and future work. This paper is available on arxiv under CC 4.0 license. Author: (1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Author: Author: (1) David S. Hardin, Cedar Rapids, IA USA david.s.hardin@gmail.com. Table of Links Abstract and Introduction Dancing Links The Rust Programming Language RAC: Hardware/Software Co-Assurance at Scale Rust and RAR Dancing Links in Rust Related Work Conclusion, Acknowledgments, and References Abstract and Introduction Abstract and Introduction Dancing Links Dancing Links The Rust Programming Language The Rust Programming Language RAC: Hardware/Software Co-Assurance at Scale RAC: Hardware/Software Co-Assurance at Scale Rust and RAR Rust and RAR Dancing Links in Rust Dancing Links in Rust Related Work Related Work Conclusion, Acknowledgments, and References Conclusion, Acknowledgments, and References 3 The Rust Programming Language The Rust programming language has garnered significant interest and use as a modern, type-safe, memorysafe, and potentially formally analyzable programming language. Google [29] and Amazon [25] are major Rust adopters, and Linus Torvalds has commented positively on the near-term ability of the Rust toolchain to be used in Linux kernel development [1]. And after spending decades dealing with a never-ending parade of security vulnerabilities due to C/C++, which continue to manifest at a high rate [24] despite their use of sophisticated C/C++ analysis tools, Microsoft announced at its BlueHat 2023 developer conference that is was beginning to rewrite core Windows libraries in Rust [6]. Our interest in Rust stems from its potential as a hardware/software co-assurance language. This interest is motivated in part by emerging application areas, such as autonomous and semi-autonomous platforms for land, sea, air, and space, that require sophisticated algorithms and data structures, are subject to stringent accreditation/certification, and encourage hardware/software co-design approaches. (For an unmanned aerial vehicle use case illustrating a formal methods-based systems engineering environment, please consult [7] [23].) In this paper, we explore the use of Rust as a High-Level Synthesis (HLS) language [26]. HLS developers specify the high-level abstract behavior of a digital system in a manner that omits hardware design details such as clocking; the HLS toolchain is then responsible for “filling in the details” to produce a Register Transfer Level (RTL) structure that can be used to realize the design in hardware. HLS development is thus closer to software development than traditional hardware design in Hardware Description Languages (HDLs) such as Verilog or VHDL. Most incumbent HLS languages are a subset of C, e.g. Mentor Graphics’ Algorithmic C [21], or Vivado HLS by Xilinx [31], although other languages have also been used, e.g. OCaml [15]. A Rust-based HLS would bring a single modern, type-safe, and memory-safe expression language for both hardware and software realizations, with very high assurance. For formal methods researchers, Rust presents the opportunity to reason about application-level logic written in the imperative style favored by industry, but without the snarls of the unrestricted pointers of C/C++. Much progress has been made to this end in recent years, to the point that developers can verify the correctness of common algorithm and data structure code that utilizes common idioms such as records, loops, modular integers, and the like, and verified compilers can guarantee that such code is compiled correctly to binary [18]. Particular progress has been made in the area of hardware/software co-design algorithms, where array-backed data structures are common [10, 11]. (NB: This style of programming also addresses one of the shortcomings of Rust, namely its lack of support for cyclic data structures.) As a study of the suitability of Rust as an HLS, we have crafted a Rust subset, inspired by Russinoff’s Restricted Algorithmic C (RAC) [27], which we have imaginatively named Restricted Algorithmic Rust, or RAR [13]. In fact, in our first implementation of a RAR toolchain, we merely “transpile” (perform a source-to-source translation of) the RAR source into RAC. By so doing, we leverage a number of existing hardware/software co-assurance tools with a minimum investment of time and effort. By transpiling RAR to RAC, we gain access to existing HLS compilers (with the help of some simple C preprocessor directives, we are able to generate code for either the Algorithmic C or Vivado HLS toolchains). But most importantly for our research, we leverage the RAC-to-ACL2 translator that Russinoff and colleagues at Arm have successfully utilized in industrial-strength floating point hardware verification. We have implemented several representative algorithms and data structures in RAR, including: • a suite of array-backed algebraic data types, previously implemented in RAC (as reported in [10]); • a significant subset of the Monocypher [30] modern cryptography suite, including XChacha20 and Poly1305 (RFC 8439) encryption/decryption, BLAKE2b hashing, and X25519 public key cryptography [12]; and • a DFA-based JSON lexer, coupled with an LL(1) JSON parser. The JSON parser has also been implemented using Greibach Normal Form (previously implemented in RAC, as described in [14]). The RAR examples created to date are similar to their RAC counterparts in terms of expressiveness, and we deem the RAR versions somewhat superior in terms of readability (granted, this is a very subjective evaluation). In this paper, we will describe the development and formal verification of an array-based circular doubly-linked list (CDLL) data structure in RAR, including the Dancing Links optimization. Along the way, we will introduce the RAR subset of Rust, the RAR toolchain, the CDLL example, and detail our ACL2-based verification techniques, as well as the ACL2 books that we brought to bear on this example. It is hoped that this explication will convince the reader of the practicality of RAR as a high-assurance hardware/software co-design language, as well as the feasibility of the performing full functional correctness proofs of RAR code. We will then conclude with related and future work. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Rust Implementation of Knuth's Dancing Links: The Rust Programming Language

Author:
(1) Brandon T. Willard, Normal Computing;
(2) R´emi Louf, Normal Computing. Table of Links Abstract and Intro
LLM Sampling and Guided Generation
Iterative FSM Processing and Indexing
Extensions to Iterative Parsing
Discussion, References and Acknowledgments 4. Extensions to Iterative Parsing In this section, we move our focus to general parser-guided generation and start with a simple walk-through for a Python-like grammar provided as a CFG. Consider a vocabulary consisting of strings like "d" and "ef" that can be combined to produce Python-like syntax according to an implicit CFG, and assume that these strings are sequentially sampled and concatenated according to a process like Algorithm 1. Furthermore, consider a terminal symbol DEF in the CFG that corresponds to the string "def" and is given by the trivial regular expression def. Also, consider a NAME symbol given by the regular expression [^\W\d]\w* (e.g. Python identifiers). We want to sequentially parse strings sampled from the aforementioned vocabulary in a way that adheres the Python syntax. For example, the following could be one such sequence: ["d", "ef", " f", "oo(", "):", " ", "pass"]. All the elements of the sequence are by definition elements of the vocabulary. Concatenating the sequence produces "def foo(): pass", which is a valid sequence of tokens defining a function. In the situation we’re considering, we will have observed all the tokens up to a certain point and know nothing about the ones after that point. For instance, at the third observation in the example sequence, we have the concatenated string "def f". If we were to lex/parse this string a traditional approach would return the symbol sequence DEF NAME, which misidentifies the "f" as a complete NAME token. As we can see from the rest of the sequence, the correct NAME token will be "foo". In general, the next valid strings that can be sampled from the vocabulary are ones that either continue expanding/advancing the NAME currently starting with "f" (as the full sequence in our example does), and/or


anything that begins with "("–i.e. an LPAR symbol with regular expression (–and proceeds to specify a valid argument signature. In the first case, the "f" can be seen as a partially matched NAME symbol in Python, and–recalling that its regular expression is [^\W\d]\w*–we can say that it matches both sub-patterns (i.e. [^\W\d] and \w*) in the regular expression. Our use of FSMs formalize the notion of sub-patterns by way of an FSM’s states. In this case, the regex for NAME can be represented by an FSM, M, with three states: 0 (i.e. the initial state q0), 1 (i.e. [^\W\d]), and 2 (i.e. \w*), where 1, 2 ∈ F. Using Algorithm 3, we would obtain the FSM state sequences (0, 1), (1, 2), (2, 2) for "f" and the FSM, M, corresponding to the NAME symbol. These FSM sequences for "f" tell us that matching can start for this vocabulary string in the states 0, 1, or 2, and it can end in states 1 or 2. According to case 1. above, parsing can be continued–for the NAME symbol–after previously ending in states 1 or 2. According to case 2., the next string could also start with or contain an LPAR, implying that M would have terminated, which it can given that 1 and 2 are final states in M at which the parsing would have stopped after reading "f". M terminating also indicates that a NAME symbol was completed, and that a transition to a state accepting LPAR was allowed by the grammar. In this illustration, the next valid vocabulary strings are at least "d", "ef", "pass", " ", "oo(", because all of those strings would expand the partially matched NAME, and the last one would also progress the parse state to one that reads an LPAR. The remaining string, "):", from the subset of the vocabulary we’ve considered would result in a sequence with invalid syntax. In relation to the FSM indexing approach, this means that Algorithm 4 would map FSM states 0, 1, and 2 to the subset "d", "ef", "pass", " ", "oo(" for the symbol NAME and its FSM, M. This illustration omits the underlying parser states that determine which grammar symbols and transitions are allowed. We use pushdown automata (PDA) as a means to extend the FSM approach and address the remaining details. 4.1 Pushdown Automata Formulation We define pushdown automata using the following 6-tuple representation [Sipser, 1996, Definition 2.13]: In order to construct an indexing approach for a PDA-driven parser, we need to use the connection between a CFG’s symbols–via a corresponding PDA’s alphabet–and the lexing and scanning steps that produce the symbols read by a PDA. More specifically, parsers are supported by lexers and scanners that identify symbols from a sequence of character inputs, as we implicitly illustrated in Section 4. Ordered lists of terminal symbols can be constructed for each parse/PDA state based on the symbol and stack transitions allowed by the map δ in each state. This means that we can construct an FSM for each parse state that is the union of each FSM corresponding to a terminal symbols read by the state. A scanning step will then identify a set of possible terminal symbols V ⊂ Σ for the characters read since the last fully identified symbol in the parsing process. For example, in the initial state q0 of a PDA for the Pythonlike CFG in Section 4, scanning and lexing the string "de" will result in V = {DEF, NAME}: i.e. DEF for any vocabulary string completing the string "def"–followed by a string not also read by the NAME FSM (e.g. "def ")– and NAME for any other strings read by its FSM (e.g. "default"). Note that steps of the scanner–and sampling steps of the LLM–will eventually reduce the set V until a single terminal symbol v ∈ V is determined. By applying Algorithm 3 to each string in V using the combined FSMs for each parse state, we can determine parser configurations that consist of the PDA states, the corresponding FSM states, and the potential terminal symbols. By analogy with the steps in Algorithm 3, we can use the pre-image of the PDA’s transition map to determine PDA stack values that will read the PDA states q ∈ Q and terminal symbol sets V of a parser configuration: The stack values provided by this map are needed in order to find paths– if any–through the PDA that allow successful, complete parses of each string in V starting from their possible parser configurations. For parser state and terminal combinations that correspond to REDUCE operations of an LALR(1) parser, these parser configurations will consist of more than just the topof-stack values in Γ; they will consist of sub-stacks corresponding to all valid prefixes for the REDUCE operations entailed by a vocabulary string. Ultimately, each parser configuration that permits a complete parse of a vocabulary string is added as an entry in the index for the PDA, and, in this case, the index will need to be a trie data structure in order to allow queries against the parser’s stack values. This paper is available on arxiv under CC 4.0 license. Author: (1) Brandon T. Willard, Normal Computing; (2) R´emi Louf, Normal Computing. Author: Author: (1) Brandon T. Willard, Normal Computing; (2) R´emi Louf, Normal Computing. Table of Links Abstract and Intro LLM Sampling and Guided Generation Iterative FSM Processing and Indexing Extensions to Iterative Parsing Discussion, References and Acknowledgments Abstract and Intro Abstract and Intro LLM Sampling and Guided Generation LLM Sampling and Guided Generation Iterative FSM Processing and Indexing Iterative FSM Processing and Indexing Extensions to Iterative Parsing Extensions to Iterative Parsing Discussion, References and Acknowledgments Discussion, References and Acknowledgments 4. Extensions to Iterative Parsing In this section, we move our focus to general parser-guided generation and start with a simple walk-through for a Python-like grammar provided as a CFG. Consider a vocabulary consisting of strings like "d" and "ef" that can be combined to produce Python-like syntax according to an implicit CFG, and assume that these strings are sequentially sampled and concatenated according to a process like Algorithm 1. Furthermore, consider a terminal symbol DEF in the CFG that corresponds to the string "def" and is given by the trivial regular expression def. Also, consider a NAME symbol given by the regular expression [^\W\d]\w* (e.g. Python identifiers). We want to sequentially parse strings sampled from the aforementioned vocabulary in a way that adheres the Python syntax. For example, the following could be one such sequence: ["d", "ef", " f", "oo(", "):", " ", "pass"]. All the elements of the sequence are by definition elements of the vocabulary. Concatenating the sequence produces "def foo(): pass", which is a valid sequence of tokens defining a function. In the situation we’re considering, we will have observed all the tokens up to a certain point and know nothing about the ones after that point. For instance, at the third observation in the example sequence, we have the concatenated string "def f". If we were to lex/parse this string a traditional approach would return the symbol sequence DEF NAME, which misidentifies the "f" as a complete NAME token. As we can see from the rest of the sequence, the correct NAME token will be "foo". In general, the next valid strings that can be sampled from the vocabulary are ones that either continue expanding/advancing the NAME currently starting with "f" (as the full sequence in our example does), and/or anything that begins with "("–i.e. an LPAR symbol with regular expression (–and proceeds to specify a valid argument signature. continue expanding/advancing the NAME currently starting with "f" (as the full sequence in our example does), and/or continue expanding/advancing the NAME currently starting with "f" (as the full sequence in our example does), and/or anything that begins with "("–i.e. an LPAR symbol with regular expression (–and proceeds to specify a valid argument signature. anything that begins with "("–i.e. an LPAR symbol with regular expression (–and proceeds to specify a valid argument signature. In the first case, the "f" can be seen as a partially matched NAME symbol in Python, and–recalling that its regular expression is [^\W\d]\w*–we can say that it matches both sub-patterns (i.e. [^\W\d] and \w*) in the regular expression. Our use of FSMs formalize the notion of sub-patterns by way of an FSM’s states. In this case, the regex for NAME can be represented by an FSM, M, with three states: 0 (i.e. the initial state q0), 1 (i.e. [^\W\d]), and 2 (i.e. \w*), where 1, 2 ∈ F. Using Algorithm 3, we would obtain the FSM state sequences (0, 1), (1, 2), (2, 2) for "f" and the FSM, M, corresponding to the NAME symbol. These FSM sequences for "f" tell us that matching can start for this vocabulary string in the states 0, 1, or 2, and it can end in states 1 or 2. According to case 1. above, parsing can be continued–for the NAME symbol–after previously ending in states 1 or 2. According to case 2., the next string could also start with or contain an LPAR, implying that M would have terminated, which it can given that 1 and 2 are final states in M at which the parsing would have stopped after reading "f". M terminating also indicates that a NAME symbol was completed, and that a transition to a state accepting LPAR was allowed by the grammar. In this illustration, the next valid vocabulary strings are at least "d", "ef", "pass", " ", "oo(", because all of those strings would expand the partially matched NAME, and the last one would also progress the parse state to one that reads an LPAR. The remaining string, "):", from the subset of the vocabulary we’ve considered would result in a sequence with invalid syntax. In relation to the FSM indexing approach, this means that Algorithm 4 would map FSM states 0, 1, and 2 to the subset "d", "ef", "pass", " ", "oo(" for the symbol NAME and its FSM, M. This illustration omits the underlying parser states that determine which grammar symbols and transitions are allowed. We use pushdown automata (PDA) as a means to extend the FSM approach and address the remaining details. 4.1 Pushdown Automata Formulation We define pushdown automata using the following 6-tuple representation [Sipser, 1996, Definition 2.13]: In order to construct an indexing approach for a PDA-driven parser, we need to use the connection between a CFG’s symbols–via a corresponding PDA’s alphabet–and the lexing and scanning steps that produce the symbols read by a PDA. More specifically, parsers are supported by lexers and scanners that identify symbols from a sequence of character inputs, as we implicitly illustrated in Section 4. Ordered lists of terminal symbols can be constructed for each parse/PDA state based on the symbol and stack transitions allowed by the map δ in each state. This means that we can construct an FSM for each parse state that is the union of each FSM corresponding to a terminal symbols read by the state. A scanning step will then identify a set of possible terminal symbols V ⊂ Σ for the characters read since the last fully identified symbol in the parsing process. For example, in the initial state q0 of a PDA for the Pythonlike CFG in Section 4, scanning and lexing the string "de" will result in V = {DEF, NAME}: i.e. DEF for any vocabulary string completing the string "def"–followed by a string not also read by the NAME FSM (e.g. "def ")– and NAME for any other strings read by its FSM (e.g. "default"). Note that steps of the scanner–and sampling steps of the LLM–will eventually reduce the set V until a single terminal symbol v ∈ V is determined. By applying Algorithm 3 to each string in V using the combined FSMs for each parse state, we can determine parser configurations that consist of the PDA states, the corresponding FSM states, and the potential terminal symbols. By analogy with the steps in Algorithm 3, we can use the pre-image of the PDA’s transition map to determine PDA stack values that will read the PDA states q ∈ Q and terminal symbol sets V of a parser configuration: The stack values provided by this map are needed in order to find paths– if any–through the PDA that allow successful, complete parses of each string in V starting from their possible parser configurations. For parser state and terminal combinations that correspond to REDUCE operations of an LALR(1) parser, these parser configurations will consist of more than just the topof-stack values in Γ; they will consist of sub-stacks corresponding to all valid prefixes for the REDUCE operations entailed by a vocabulary string. Ultimately, each parser configuration that permits a complete parse of a vocabulary string is added as an entry in the index for the PDA, and, in this case, the index will need to be a trie data structure in order to allow queries against the parser’s stack values. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Stories, News & Mentions about LEXER

Categories

Trending Topics

Stories, News & Mentions about LEXER

Lexer’s Stories on HackerNoon

Lexer's News & Mentions

Categories

Trending Topics