What is "K"? (previous)

If you’ve been around Pi Squared for a while, or even read any of our blog posts, there’s one thing you might be curious about, which is K. It’s a recurring topic, and for good reason—K is at the heart of what we do. In this guide, we’ll break it down for you.

The K framework is a semantics-based approach to language design and implementation. Instead of manually building tools like interpreters or verifiers for each programming language, K allows developers to define a language formally and extract a full set of tools automatically.

As illustrated below in Figure 1, with just a formal specification of a language’s syntax and semantics, K can produce a parser, an interpreter, and a symbolic deductive verifier, among other tools. This means that once a language is defined in K, you don’t need to write separate execution tools—it’s all derived from the semantics.

Figure 1: The central vision of the K framework.

K is scalable and has been used to formalize multiple real-world programming languages, including C, Java, JavaScript, Python, Rust, x86-64, the Ethereum Virtual Machine (EVM), and LLVM IR, making it suitable for both research and commercial applications.

At Pi Squared we depend on K’s abilities to achieve the following:

  • To define any programming language formally and generate correct-by-construction interpreters.

  • To automatically generate efficient execution models for blockchain-based computation.

  • To ensure that smart contracts and blockchain applications behave as expected—no hidden compiler bugs, no unforeseen behavior.

This is the foundation for making blockchain programming truly verifiable, correct, and performant.

How K works

In K, a definition of a language consists of three main components:

  1. Concrete syntax: A conventional BNF grammar that defines the structure of valid programs in the language.

  2. Execution state (configuration): A representation of the state maintained by a program during execution.

  3. Operational semantics: A set of rewrite rules that define how the program's state changes over time.

K uses rewrite rules to define execution in a precise way. A rewrite rule takes an initial configuration and transforms it into a new configuration based on predefined logic, ensuring that program execution follows the formal semantics.

A core feature of K is its ability to generate a language-agnostic interpreter. Given a K definition of a language, K automatically generates an interpreter that can execute any program written in that language.

LLVM-K: Making K Fast

Initially, K was designed to interpret programs using a language-generic tool, which essentially would run an interpreter inside another interpreter. However, generic interpretation can introduce additional overhead compared to language-specific execution.

As such, the current version of K builds on LLVM-K, which leverages LLVM IR to compile K into efficient native code. By generating a native interpreter, LLVM-K eliminates the extra layer of interpretation, significantly improving performance.

Last updated

Was this helpful?