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

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

Efficient Guided Generation for Large Language Models: Extensions to Iterative Parsing

বৃহৎ ভাষার মডেলের জন্য দক্ষ নির্দেশিত প্রজন্ম: পুনরাবৃত্তিমূলক পার্সিংয়ের এক্সটেনশন

Effiziente geführte Generierung für große Sprachmodelle: Erweiterungen zum iterativen Parsing

Generación guiada eficiente para modelos de lenguaje grandes: extensiones al análisis iterativo

Génération guidée efficace pour les grands modèles de langage : extensions à l'analyse itérative

बड़े भाषा मॉडल के लिए कुशल निर्देशित पीढ़ी: पुनरावृत्त पार्सिंग के लिए विस्तार

大規模言語モデルの効率的なガイド付き生成: 反復解析の拡張

대규모 언어 모델을 위한 효율적인 유도 생성: 반복 구문 분석 확장

Geração guiada eficiente para grandes modelos de linguagem: extensões para análise iterativa

Эффективная управляемая генерация для больших языковых моделей: расширения итеративного анализа

Büyük Dil Modelleri için Verimli Kılavuzlu Oluşturma: Yinelemeli Ayrıştırmanın Uzantıları

Tạo hướng dẫn hiệu quả cho các mô hình ngôn ngữ lớn: Phần mở rộng cho phân tích cú pháp lặp

大型语言模型的高效引导生成：迭代解析的扩展

You have probably read that JavaScript is an interpreted language, while others argue that it's not an interpreted language and that it's actually a compiled language. This can be confusing, I was often confused because I received conflicting answers whenever I read books or articles about JavaScript being an interpreted or compiled language. But the truth is that it depends on how the language is implemented. Let me explain. To clarify this point, let's first examine what are compiler and interpreter also the difference between them Compiler A compiler is a software tool that translates human-readable source code into machine-executable code. The process of compilation involves several stages, including lexical analysis syntax analysis (parsing) semantic analysis code generation optimization During lexical analysis, the compiler breaks down the source code into a series of tokens, which are individual units of meaning. For example, in the statement , the tokens would be , , , , and . The lexer also assigns a type to each token, such as "identifier", "operator", or "literal". "x = 5 + 3;" "x" "=" "5" "+" "3" Then, during syntax analysis (parsing), the compiler checks the order and structure of the tokens to ensure that they form a valid program. This involves analyzing the grammar of the programming language and constructing a syntax tree that represents the structure of the program. After the syntax analysis is complete, the compiler performs semantic analysis to check for logical errors in the code. This involves verifying that the program follows the rules of the language, such as type checking, scoping rules, and function calls. Once the compiler has verified the correctness of the program, it generates machine code or bytecode that can be executed by the computer. This involves translating the syntax tree and semantic information into low-level instructions that can be executed by the computer's hardware. Finally, the compiler performs optimization to improve the efficiency of the generated code. This process involves analyzing the code and making changes to improve the memory usage. Overall, the compiler is an essential tool for translating human-readable source code into machine-executable code. The compilation process involves several stages, each of which is critical for producing correct and efficient code. Interpreter An interpreter is a program that reads and executes code written in a high-level programming language directly, without requiring an intermediate compilation step. Unlike a compiler, which translates the entire source code into machine code before execution, an interpreter reads and executes the source code line by line, translating and executing each statement as it is encountered. When an interpreter runs a program, it first performs lexical analysis and parsing of the source code to generate an abstract syntax tree (AST) representing the program's structure. The interpreter then walks through the AST, executing each node in turn. During execution, the interpreter may generate and manipulate additional data structures to represent the state of the program, such as a symbol table for tracking variable values. One advantage of using an interpreter is that it allows for more dynamic and interactive development, as programmers can test and modify their code on the fly without having to recompile the entire program. However, interpreting code can be slower than executing compiled code, since the interpreter has to perform additional work to translate and execute each statement. Overall, an interpreter provides a convenient way to execute code in a high-level language, but may not be as performant as compiled code in certain situations. Compiler vs. Interpreter in a simple way There is a lot of technical information about compilers and interpreters, so let's make it simple: And like everything else in life, let's try to understand it with a cup of tea. Let's say you want to make a cup of black tea, you go to Google and search for the ingredients list, this is what you came up with: Black tea leaves Water Sugar (optional) Milk (optional) There are 2 ways to make the tea, the Compiler or the Interpreter way. The compiler will first, before doing any steeping, organize all the ingredients in front of him, the specific amounts of every single ingredient, only then, will he steep all the ready components of the tea. The interpreter will take his cup and will start by reading the ingredients, line by line. he will boil the water, add the tea leaves, steep them for a few minutes, add sugar or milk if desired, and then strain the tea into the cup. The build (preparation) time of the compiler will be longer than the interpreter's. However, the run (steeping) time will be much shorter. Now that you know the difference let’s talk about JavaScript. Is JavaScript Compiled or an Interpreted Language? When I first started learning JavaScript, I, like many others, was taught that it was an interpreted language, and I believed it for a long time. However, after conducting further research, I have come to realize that this is not entirely accurate. While many people still consider JavaScript to be an interpreted language, there is evidence to suggest that it is actually a compiled language. One example of this can be seen in the way that the JavaScript engine handles bugs. When you encounter a syntax error in your JavaScript code, the engine will typically alert you to the problem before it even begins executing the code. This suggests that the code is compiled and validated before it is executed, which is a characteristic of compiled languages. You can try this for yourself by opening the following HTML code in your browser and checking the console: console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World!); The last line of code is missing a closing quotation mark, which should trigger a syntax error. However, if JavaScript were truly an interpreted language, the console would have already printed the first nine lines before throwing an error. Instead, the program crashes immediately, Uncaught SyntaxError: Invalid or unexpected token Thats indicating that it was compiled and validated before execution. While there is still debate over whether JavaScript is truly a compiled language or not, it's clear that it's not entirely accurate to call it an interpreted language. Another way to prove that JavaScript is not an entirely interpreted language is through the concept of . For example, consider the following code: hoisting max(1, 2);
// 2
function max(num1, num2){
  return num1 > num2 ? num1 : num2;
} In traditional programming languages, a function must be defined before it can be called. However, in JavaScript, the function can be called before it is defined. This behavior is known as , and it's a fundamental aspect of how JavaScript works. hoisting Note: We will explore more about `hoisting` in other blog for now this explanation is enough. How does the JavaScript engine know about the function before it reaches the declaration? The only reasonable answer to this question is that the code must first be compiled before execution. max So, JavaScript is a compiled language, right? Well, it's complicated. In the past, every programming language was fairly easy to categorize as either compiled or interpreted. However, with the modern approach of running source code, a sort of "in-between" area has been created. How does JavaScript actually get translated? JavaScript has come a long way since its inception as a simple scripting language. In the early days, JavaScript engines were only interpreters, which executed code line by line. However, as JavaScript became more popular and its use cases expanded, performance issues emerged. Interpreting code on-the-fly resulted in a loss of performance, especially for complex applications. This led to the development of new engines that use a just-in-time (JIT) compiler. A JIT compiler is different from traditional compilers, such as those used for C++. Traditional compilers have plenty of time to optimize the code during compilation, but JIT compilers must compile code just before it's executed. As soon as the JavaScript code is about to run, it gets compiled into executable bytecode. Despite the differences in how JavaScript is compiled compared to other compiled languages, the process still follows some of the same rules as traditional compilers. The JavaScript code is parsed before execution, which makes it look like a parsed language. However, the code is converted to binary form before execution. To better understand this process, let's take a closer look at how code execution works behind the scenes: First, the code is transpiled using tools like Babel or Webpack. The transpiled code is given to the engine, which parses it to an Abstract Syntax Tree (AST). The AST is then converted to bytecode that is understood by the machine. This is an Intermediate Representation (IR), which is further optimized by the JIT compiler. After optimization, the JS Virtual Machine (VM) executes the code. Some people argue that the JS VM is "interpreting" the bytecode, but this is not entirely accurate. If we were to use that definition, we would also have to say that Java, which is another JVM-driven language, is also interpreted. Thus, we can conclude that JavaScript is executed in three phases: Parsing Compiling Executing JavaScript code is initially interpreted before any execution begins. For example, consider the following code: console.log("Hello");
for(var i = 0;i<4;i++) {
    console.log(Hello);
} The output shows the interpreter behavior in the above code example, where first is printed to the console, and then an error is reported. This output strongly supports the fact that JavaScript is an interpreted language. Hello While it may seem like JavaScript code is being executed line by line, this is only true during the parsing phase. In reality, the entire code is compiled at once to convert it into machine-readable code before execution. Therefore, JavaScript is a just-in-time compiled language that uses an interpreter in its first phase. Note: JavaScript can operate in an interpreted manner in older browsers. However, every modern browser currently supports "JIT", so JavaScript code is always compiled. Whether JavaScript is compiled or interpreted depends on the environment in which it is run. If it runs in older browsers, it's interpreted. If it runs in modern browsers, it's compiled. Explaining JIT in JavaScript Now that we have a basic understanding of how JavaScript works and what JIT compilers are, let's delve deeper into how JIT compilers work and why they're important. But don't worry, we won't get too technical with jargon. Instead, we'll explore JIT compilers in simple terms to understand how they work, why they're important, and the reason they were introduced in the first place. JIT (just-in-time) compilation is a technique used by modern JavaScript engines to improve the performance of JavaScript code. Unlike traditional compilers that optimize code during compilation, JIT compilers take a middle-ground approach. They initially interpret the code and then selectively compile parts of it that are used repeatedly. This approach balances fast start-up time with improved performance. When a JavaScript engine encounters a function, it can either interpret the code on-the-fly or compile the code before execution. Interpreting the code can be faster to start execution but slower in terms of overall performance, as the code is translated line-by-line each time the function is executed. Compiling the code before execution can be slower to start, but it can result in faster execution due to machine code optimizations. In this approach, the code is compiled into machine code, which is then executed by the processor. JIT compilers take a middle-ground approach, where they initially interpret the code and then selectively compile parts of it that are used repeatedly. As a result, JIT compilers offer a balance of fast start-up time and improved performance. To understand how JIT compilers work, let's consider an example: function add(a, b) {
  return a + b;
}

for (let i = 0; i < 100000000; i++) {
  add(i, i + 1);
} In this code, we have a simple function that adds two numbers and a loop that calls this function million times with different inputs. add 100 When the JavaScript engine first encounters this code, it will interpret it on-the-fly and execute it. However, as the loop runs repeatedly, the engine detects that the function is being called repeatedly and decides to compile it to machine code to improve performance. add The compiler analyzes the code and optimizes it for the specific inputs being used in the loop. JIT For example, it may decide to inline the function, which means replacing the function call with the actual addition code, eliminating the overhead of calling a function. Additionally, it may also perform other optimizations such as constant folding or dead-code elimination, which remove unnecessary computations. add Overall, JIT compilers help improve the performance of JavaScript code by selectively compiling parts of it that are used repeatedly, while still allowing for fast start-up times. Now that we have a better understanding of how the JIT compiler works, let's delve into the issues we previously discussed and their underlying causes. Why the Pre-execution syntax error alerts Let's explore the reason behind syntax error alerts in JavaScript using the same example we discussed earlier. console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World from javascript!");
 console.log("Hello World!); In the case of the code example provided, the JavaScript engine compiles the code before execution, and the syntax error is detected during the compilation phase. This is because the engine uses the compiler that optimizes code on the fly as it's executed. When the engine encounters an error during the compilation phase, it immediately throws an error without executing any code. JIT Therefore, the fact that JavaScript detects syntax errors during the compilation phase suggests that it's more like a compiled language than an interpreted one. What is the story of hoisting? Let's now understand the hoisting in the context of engine using the code we used before: JIT max(1, 2);
// 2
function max(num1, num2){
  return num1 > num2 ? num1 : num2;
} So, how does the JavaScript engine know about the function before it reaches the declaration? max The answer lies in the Just-In-Time ( ) compilation process that occurs behind the scenes when JavaScript code is executed in modern browsers. JIT During the optimization step, the compiler can analyze the code to determine which functions are likely to be called frequently and which variables are likely to be accessed repeatedly. By identifying these patterns, the compiler can optimize the code for faster execution, which can result in significant performance gains. JIT In the case of hoisting, the compiler can recognize the pattern of a function being declared at the top of its scope and optimize the code accordingly. Conclusion In summary, while JavaScript is commonly thought of as an interpreted language, it is actually a Just-In-Time compiled language. Modern JavaScript engines use a compiler to optimize the code for execution. This compiler allows JavaScript to be executed much faster and in an efficient way than traditional interpreted languages. While the compiling of Javascript works in a different way, if compared to other compiled languages, it still follows some rules that reflect the process of compiling. JIT JavaScript code is parsed before execution, which makes it look like a parsed language, but the code is actually converted to binary(machine code that is directly executed by the computer's hardware) form before execution. This conversion process involves several steps, including transpiling the code, parsing it to an Abstract Syntax Tree ( ), converting it to bytecode, and optimizing it with a compiler. AST JIT So, to answer the question the answer is that it is a bit of both. It is interpreted in older browsers, but in modern browsers, it is compiled with the help of a compiler. "Is javascript compiled or interpreted language?" JIT Also published . here

Is Javascript a Compiled or an Interpreted Language?

183 Stories To Learn About Engineering

Recently, Air2phin, a scheduling system migration tool, announced its open source. With Air2phin, users can migrate the scheduling system from Airflow to Apache DolphinScheduler in two steps, which brings great convenience to users who need to migrate the scheduling system. What is Air2phin? Air2phin is a scheduling system migration tool, which aims to convert Apache Airflow DAGs files into Apache DolphinScheduler Python SDK definition files, to migrate the scheduling system (Workflow orchestration) from Airflow to DolphinScheduler. It is a multi-rule-based AST converter that uses LibCST to parse and convert Airflow's DAG code. All its rules are defined using Yaml files and provide certain custom rule extension capabilities. Recently, Air2phin has released version 0.0.12, which provides rich functions and can better help users complete the migration from Airflow to Apache DolphinScheduler. Note: AST is the abbreviation of Abstract Syntax Tree (Abstract Syntax Tree), which is a data structure that represents the grammatical structure of code in a tree structure. In a compiler, the AST is produced by a lexer and a parser. The lexical analyzer converts the source code into a stream of tokens, and the parser converts the stream of tokens into an abstract syntax tree. AST is a tree structure, which consists of a series of nodes, each node represents a grammatical structure in the code (such as expressions, statements, functions, classes, etc.), and the relationship between nodes represents the embedding of grammatical structures. set of relationships. Why open-source Air2phin? Some people may ask, why do I need a migration tool? This is because with the development of business, the original workflow orchestration system used by enterprises or organizations can no longer meet the current needs, and the workflow orchestration system needs to be migrated to a new platform or updated to a new version. After research, many users need to migrate the scheduling system from the open-source workflow orchestration system Airflow to Apache DolphinScheduler. During the migration process, since data processing tasks may involve dependencies between multiple systems, the migration process needs to be completed without affecting business operations. At this time, the dispatching system migration tool can play an important role. It can reduce manual intervention, complete the migration work between the two dispatching systems as automatically as possible, and can be compatible with multiple versions between multiple systems. Intervention completes the migration. To this end, WhaleOps has specially developed the open-source migration tool Air2phin, which allows users to migrate the scheduling system from Airflow to Apache DolphinScheduler in two steps, bringing great convenience to users. To let everyone better understand the importance of Air2phin, let's start with the background knowledge of the scheduling system and understand the benefits of migrating the scheduling system from Airflow to Apache DolphinScheduler. Why migrate from Airflow to DolphinScheduler? What is a workflow orchestration system? A workflow orchestration system manages data flow in a manner that respects orchestration rules and business logic. Workflow orchestration tools allow users to convert multiple related tasks into workflows that can be scheduled, run, and observed, helping companies better manage and control business processes, thereby improving business efficiency. Workflow orchestration is one of the indispensable components in data processing. It is responsible for executing data processing tasks according to predefined rules and logic to ensure that the data processing process is executed smoothly as expected. Popular workflow orchestration systems include Apache DolphinScheduler, Apache Airflow, Apache Oozie, Azkaban, etc. What is Airflow? Among them, Apache Airflow is an open-source workflow orchestration system, which can help users create, schedule and monitor complex workflows. Originally developed by Airbnb and open-sourced in 2016, Airflow is now maintained by the Apache Software Foundation. Written in the Python language, Airflow is highly scalable and flexible and supports a variety of task types, such as calculations, data processing, notifications, interactions, and more. Airflow's workflow is defined by writing Python scripts, and its functionality can be extended using operators and hooks provided by Airflow, as well as custom operators and hooks. However, it has flaws that cannot be ignored, such as the need for in-depth secondary development, the high cost of upgrading from the community version; the high iteration cost of Python technology stack maintenance; scheduler loop scanning Dag folder delays reduces the performance; and poor stability in production environments and so on. Apache DolphinScheduler, born under the business needs of the new data era, is an open-source distributed workflow scheduling system, which makes up for the weaknesses of previous scheduling systems, and aims to provide enterprise users with a reliable, efficient, and easy-to-use workflow scheduling platform. Multiple task types are supported, such as computing, data processing, ETL, etc. Compared with Airflow, DolphinScheduler adopts a distributed architecture and provides a variety of task types. Users can define dependencies between tasks, set task priorities and schedule policies, etc. It uses a visual interface to create and manage workflows, which is in stark contrast to Airflow, making it easier to operate and more friendly to non-programmers. After research and comparison, for many users, migrating the scheduling system to Apache DolphinScheduler is a better choice to reduce costs and increase efficiency. How to install and use Air2phin Air2phin is a python package, which can be installed through the Python package installation tool pip, see air2phin getting start for details. python -m pip install --upgrade air2phin A simple example We use a simple example to illustrate how to use Air2phin. We have intercepted part of the code in airflow tutorial.py as an example of Air2phin conversion to illustrate how Air2phin can be converted into dolphinscheduler python sdk step by step. picture Figure 1: Part of the code in airflow tutorial.py Figure 2: How Air2phin is converted into dolphinscheduler python sdk step by step Suppose you save part of the content of airflow tutorial.py to the file tutorial_part.py, and want to convert it into the definition of dolphinscheduler python sdk, you only need one line of command to complete it. The result is shown in Figure 2. Because the command adds the --inplace parameter, Air2phin will directly overwrite the original file. If you don't need to overwrite the original problem, you don't need to use the --inplace parameter, and Air2phin will add a tutorial_part-air2phin.py file to save the converted content. air2phin migrate --inplace tutorial_part.py We can see that this conversion triggers multiple conversion rules, including Convert airflow.DAG to pydolphinscheduler.core.process_definition.ProcessDefinition, this rule is in the third line (import statement) and the sixth line DAG context Convert airflow.operators.bash.BashOperator to pydolphinscheduler.tasks.shell.Shell, this rule is used in tasks t1, t2 In addition to the corresponding class conversion, we need to convert the attributes of the class, such as converting airflow.DAG.schedule_interval to ProcessDefinition.schedule, and modify the content of some values, such as converting timedelta(days=1) to' 0 0 0 * * ? *' Finally, we only need to install pydolphinscheduler and run the converted file through python to complete the workflow migration. For details, see pydolphinscheduler usage (https://dolphinscheduler.apache.org/python/main/start.html# installing-pydolphinscheduler). # Install apache-dolphinscheduler python -m pip install apache-dolphinscheduler # Submit workflow to dolphinscheduler python tutorial_part.py When running python tutorial_part.py, we must ensure that the dolphinscheduler API and python gateway service have been started, and the corresponding ports have been opened. For details, see Starting python gateway service. So far, we have explained how Air2phin completes the migration through a simple example. Working principle of Air2phin How do Airflow and dolphinscheduler python sdk work? Before understanding how Air2phin works, it is very important to understand how Airflow and dolphinscheduler python sdk work. It will help us better understand the migration steps of Air2phin and deal with problems more calmly. The information related to Airflow workflow is stored in the DAG file, and then the DAG file is placed in the specified directory of Airflow, and the Scheduler of Airflow will scan and analyze the DAG file of Airflow at a certain interval, so the DAG file is passively Scanned and updated. How Airflow works: Similar to Airflow, all workflow-related information is defined through Python files, but dolphinscheduler python sdk submits workflow information through artificial triggering and runs the command python workflow file name to complete the active Task submission. dolphinscheduler python sdk: Air2phin workflow After understanding the submit/discover workflow mechanism, it will be more conducive to our understanding of the working principle of Air2phin. Because both Airflow's DAG file and DolphinScheduler's Python sdk definition file are written in Python, most of Air2phin's code deals with the differences between the two, and finally converts Airflow's code into dolphinscheduler python sdk and definitions. Air2phin uses LibCST (https://libcst.readthedocs.io/en/latest/) to implement the abstract syntax tree parsing of airflow python DAG code, and then through LibCST's Transformer (https://libcst.readthedocs.io/en/ latest/tutorial.html#Build-Visitor-or-Transformer) combined with the transformation rules and finally transformed into the definition of dolphinscheduler python sdk. The overall workflow of Air2phin is as follows: Get the original Airflow DAG content from stdin or a file Load all transformation rules from yaml file Parse Airflow DAG content into a CST tree via LibCST Transform dolphinscheduler python sdk definitions via LibCST Transformer Air2phin Best Practices Migrate entire folders instead of individual files When users want to migrate Airflow to DolphinScheduler, most of them want to migrate the whole system instead of a single file. Air2phin provides the ability to migrate the entire folder by just changing the path from the file path to a folder. # Migrate the entire ~/airflow/dags folderair2phin migrate --inplace ~/airflow/dags Add custom rules Some of the Airflow users self-define Hooks or Operator. User-defined Operators cannot be converted through Air2phin's built-in conversion rules, so users need to add custom rules and tell Air2phin the location of the rules. For example, suppose we have an operator called MyCustomOperator that inherits most of the functions of PostgresOperator, with only a different name. Its definition is as follows: from airflow.providers.postgres.operators.postgres import PostgresOperator class MyCustomOperator(PostgresOperator): def __init__( self, *, sql: str | Iterable[str], my_custom_conn_id: str = 'postgres_default', autocommit: bool = False, parameters: Iterable | Mapping | None = None, database: str | None = None, runtime_parameters: Mapping | None = None, **kwargs, ) -> None: super().__init__( sql=sql, postgres_conn_id=my_custom_conn_id, autocommit=autocommit, parameters=parameters, database=database, runtime_parameters=runtime_parameters, **kwargs, ) It is used in multiple DAGs in Airflow in the following way: from custom.my_custom_operator import MyCustomOperator with DAG( dag_id='my_custom_dag', default_args = default_args, schedule_interval='@once', start_date=days_ago(2), tags=['example'], ) as dag: t1 = MyCustomOperator( task_id='my_custom_task', sql='select * from table', my_custom_conn_id='my_custom_conn_id', ) Now we need to convert this Operator. We can customize a conversion rule and name it MyCustomOperator.yaml. The content is as follows. The main content is the definition of migration.module and migration.parameter, which determine the conversion rule: name: MyCustomOperator description: The configuration for migrating airflow custom operator MyCustomOperator to DolphinScheduler SQL task. migration: module: - action: replace src: custom.my_custom_operator.MyCustomOperator dest: pydolphinscheduler.tasks.sql.Sql parameter: - action: replace src: task_id dest: name - action: replace src: my_custom_conn_id dest: datasource_name Then use the --custom-rules parameter to specify conversion custom parameters, and the conversion of custom rules can be applied: # Specify the custom rule path as /path/to/MyCustomOperator.yaml air2phin migrate --inplace --custom-rules /path/to/MyCustomOperator.yaml ~/airflow/dags Make Air2phin run faster By default, Air2phin runs the conversion of DAG files in one process. When you have many DAG files, Air2phin conversion is very time-consuming. We provide a parameter to start multi-process to run Air2phin conversion --multiprocess, which can be specified as the user machine's CPU amount to reduce conversion time: # Specify air2phin to start 12 processes to convert at the same time air2phin migrate --inplace --custom-rules /path/to/MyCustomOperator.yaml --multiprocess 12 ~/airflow/dags FAQ Q: Why did you choose to parse Airflow DAG files instead of databases? A: Because the completed workflow information is only in the Airflow DAG file, the Airflow database only has basic workflow information, no task definition information, and no task relationship. We choose to complete it by parsing the Airflow DAG file instead of the database transform. Q: Why do I need to transfer through the dolphinscheduler python sdk instead of submitting to DolphinScheduler myself? A: Because Airflow DAG is defined by Python, there are many Python features in Airflow DAG, we don't want to convert these features into structured data (the conversion may cause information loss), it happens that DolphinScheduler already has Python sdk, so It is easier to convert directly through LibCST. Q: Why use LibCST instead of python's built-in AST? A: Because LibCST is more suitable for us, the comment information will be lost when the Python built-in AST library is parsed into AST, but we hope to keep some information. And LibCST provides more visitors to ensure that we can implement replacement more conveniently. Reference: air2phin (https://github.com/WhaleOps/air2phin) Also Published Here

How to Migrate from Airflow to Dolphinscheduler in Two Steps

Hello everyone, in the last article I introduced the Turtle Graphics Android App project with implementation details and resources about the scripting language, editor, generating documentation…etc, after I published the app and got more than 2000 downloads a few times and good ratings and feedback, I decided to add support for code formatting and in this article, I will talk in detail how a simple code formatter works and how I implemented it in the Turtle Graphics app. As programmers, Code formatters are an essential tool in our day-to-day jobs, They make it easier to read the code if it is formatted, but did you ask yourself how it works? Before talking about Code formatter, let’s first talk about how Compilers represent your code from text to data structure to do the process on it such as type checking. Let’s start our story from your file that contains a simple hello world example fun main() {
   print("Hello, World!")
} The first step is to read this text file and convert it into a list of tokens, A token is a class that represents a keyword, number, bracket, string, …etc with this position in the source code for example data class Token (
   val kind : TokenKind,
   val literal : String,
   val line : Int,
) We can also save the file name, column start and end so when we want to report an error we can provide useful info about the position for example Error in File Main Line 10: Missing semicolon :D This step is called scanner, lexer or tokenizer and at the end, we will end up with a List of tokens for example { FUN_KEYWORD, "fun", 1 }
{ IDENTIFIER, "main", 1 }
{ LEFT_PAREN, "(", 1 }
{ RRIGHT_PAREN, ")", 1 }
{ LEFT_BRACE, "{", 1 }
{ IDENTIFIER, "print", 2 }
{ LEFT_PAREN, "(", 2 }
{ STRING, "Hello, World!", 2 }
{ RRIGHT_PAREN, ")", 2 }
{ RIGHT_BRACE, "}", 3 } The result is a list of tokens val tokens : List<Token> = tokenizer(input) Note that in this step we can check for some errors such as unterminated string or char, unsupported symbols …etc After this step, you will forget your text file and deal with this list of tokens, and now we should convert some tokens into nodes depending on our language grammar for when we saw FUN_KEYWORD that means we will build a function declaration node and we expect name, paren, parameters …etc In this step, we need a data structure to represent the program in a way we can traverse and validate it later and it is called Abstract Syntax Tree (AST), each node in AST represent statement such as If, While, Function declaration, var declaration …etc or expressions such as assignments, unary …etc, each node store required information to use them later in the next steps for example Function Declaration data class Function (
   var name : String,
   var arguments : List<Argument>,
   var body : List<Statement>
) Variable Declaration data class Var (
   var name : String
   var value : Expression
) This step is called parsing and we will end up with an AST object that we can use later to traverse all nodes. var astNode = parse(tokens) If the language statically types such as Java, C, Go …etc we will go to the Type Checker step, the goal for this step is to check that the user use type correctly for example, if the user declares a variable with int type it should store only integers on it, the if condition must be a boolean type or an integer in a language like C …etc After this step, we will end up with the same AST node but now we know that it is valid and we can now compile it to any target or evaluate it, But also we can do the formatting, static analysis, optimization, check code style …etc For example suppose that we want all developers to declare variables without using _ inside the name, to check that we will traverse our AST node to find all Var nodes and check them fun checkVarDeclaration(node : Var) {
   if (node.name.contains("_") {
      reportError("Ops your variable name ${node.name} contains _")
   }
} But now we need to format it, so how to do that? It's the same we traverse our AST and for each node, we will write it back to text but formatted for example fun formatVarDeclaration(node : Var) : String {
   var builder = StringBuilder()
   builder.append(indentation)
   builder.append("var ")
   builder.append(node.name)
   builder.append(" = ")
   builder.append(formatValue(node.value))
   builder.append("\n")   
   return builder.toString()
} In this simple method, we rewrite the node to string but with correct indentations and add a new line after it so now 2 variables are declared in the same line, the value also is formatted using another function you can use Visitor design pattern to make it easy to handle all nodes. At the end of this step, we end up with a string that represents the same input file but formatted and then we write it back to the file. This is the basic implementation of code formatter, a real production code formatter must handle more cases, for example, what if the code is not valid?, should I format only valid code? should we read the whole program every time we want to format or compile the code? Now back to Turtle graphics, In this project i already did all the required steps before and has a ready AST, so i just rewrite it with code as you saw above ^_^ i read it from the UI format it and write it back to UI in my case If you are interested and want to read more I suggest Read at least one Compiler book such as Crafting interpreters Read about Language Server Protocol (LSP) Watch Typescript Compiler explained by the Author Anders Hejlsberg Think if you have Your program as AST what else you can do with it I hope you enjoyed my article and you can find me on GitHub Linkedin Twitter Enjoy Programming 😋.

Stories, News & Mentions about LEXER

Lexer’s Stories on HackerNoon

Lexer's News & Mentions