Squid ― type-safe metaprogramming for Scala

Introduction

Squid (for the approximative contraction of Scala Quoted DSLs) is a metaprogramming framework that facilitates the type-safe manipulation of Scala programs. Squid extends multi-stage programming capabilities with support for code inspection and code transformation. It has special support for library-defined optimizations [2] and helps with the compilation of domain-specific languages (DSL) embedded in Scala [1]. Squid uses advanced static typing techniques to prevent common metaprogramming errors, such as scope extrusion [3].

Link to the Squid tutorial.

Caution: Squid is still experimental, and the interfaces it exposes may slightly change in the future. This applies especially to the semi-internal interfaces used to implement intermediate representation backends (the Base trait and derived).

An Early Example

To give a quick taste of Squid's unique mix of capabilities, here is a basic (contrived!) example of program manipulation. The full source code can be found here, in the example folder. Much more detailed explanations of each feature can be found in the tutorial.

The core of Squid's frontend is its type- and scope-safe quasiquotation engine. We can write program fragments, or code values, by using the code interpolator:

import scala.io.StdIn

val c0 = code"Some(StdIn.readDouble)" // resolves types and imports statically

println(c0) // code"scala.Some.apply[scala.Double](scala.io.StdIn.readDouble())"

We can then compose programs incrementally from smaller parts:

val c1: ClosedCode[Double] = code"$c0.get"
// ClosedCode[T], an alias for Code[T,Any], is the type of closed terms

println(c1) // code"scala.Some.apply[scala.Double](scala.io.StdIn.readDouble()).get"

// A function that manipulates code fragments in context/scope C:
def mkPow[C](b: Code[Double,C], e: Code[Double,C]) = code"Math.pow($b, $e)"

val c2: ClosedCode[Double] = mkPow(c1, code"3")

// method `=~=` tests for alpha-equivalence of code values:
assert(c2 =~= code"java.lang.Math.pow(Some(StdIn.readDouble).get, 3.0)")

Now, let us define a Math.pow optimizer. We'll do a top-down rewriting until a fixed point is reached, thanks to the fix_topDown_rewrite method:

def optPow[T,C](pgrm: Code[T,C]): Code[T,C] = pgrm fix_topDown_rewrite {
  case code"Math.pow($x, 0.0)"       => code"1.0"
  case code"Math.pow($x, ${Const(d)})" // `Const` matches constants, so `d` has type Double
    if d.isWhole && 0 < d && d < 16  => code"Math.pow($x, ${Const(d-1)}) * $x"
}

And finally, let us build a compiler for fast power functions! Given an integer n, we return a function that has been runtime-compiled to multiply any number with itself n times, using only plain multiplications:

def mkFastPow(n: Int): Double => Double = {
  val powCode = code"${ (x: Variable[Double]) => mkPow(code"$x", Const(n)) }"
  // ^ The line above lifts a function of type `(v: Variable[Double]) => Code[Double, v.Ctx]`
  //   into a program fragment of type `ClosedCode[Double => Double]`
  val powCodeOpt = optPow(powCode) // optimize our pow function
  powCodeOpt.compile // produce efficient bytecode at runtime
}
val p4fast = mkFastPow(4) // equivalent to: `(x: Double) => 1.0 * x * x * x * x`
println(p4fast(42)) // 3111696.0

This is just the beginning. Squid has much more under the hood, including: normalizing intermediate representations; online optimization; mixin program transformers; cross-stage persistence; automatic lifting and controlled inlining of library definitions; painless compile-time optimization... An overview of Squid's features is given below, and a short example of some of them can be found here.

Getting Started

Squid currently supports Scala versions 2.12.x and 2.11.y for y > 2 (other versions might work as well, but have not been tested).

In your project, add the following to your build.sbt:

resolvers += Resolver.sonatypeRepo("snapshots")

libraryDependencies += "ch.epfl.data" %% "squid" % "0.4.0-SNAPSHOT"

Some features related to library-defined optimizations and squid macros, such as @embed and @macroDef, require the use of the macro-paradise plugin. To use these features, add the following to your build.sbt:

val paradiseVersion = "2.1.0"

autoCompilerPlugins := true

addCompilerPlugin("org.scalamacros" % "paradise" % paradiseVersion cross CrossVersion.full)

In case you wish to use a more recent version of Squid that has not yet been published, you'll have to clone this repository and publish Squid locally, which can be done by executing the script in bin/publishLocal.sh.

Overview of Features

Squid Quasiquotes

Quasiquotes are the primitive tool that Squid provides to manipulate program fragments –– building, composing and decomposing them. Quasiquotes are central to most aspects of program transformation in Squid.

You can find an in-depth tutorial about Squid quasiquotes here.

Note: In the original Squid papers [1] and [2], we used Code[T] as the type of program fragments. With the introduction of scope safety and our POPL 2018 paper [3], this type now takes an extra parameter, as in Code[T,C] where C represent the term's context requirements.
One cans still use type OpenCode[T] when context requirements are not important; this type has limited capabilities (no run or compile, for instance), but can be turned into a closed code type with method unsafe_asClosedCode. On the other hand, ClosedCode[T] (a synonym for Code[T,{}]) is the type of closed program fragments.

Type-Safe Code Manipulation

Unlike the standard Scala Reflection quasiquotes, Squid quasiquotes are statically-typed and hygienic, ensuring that manipulated programs remain well-scoped and well-typed and that variable bindings and other symbols do not get mixed up. Still, Squid quasiquotes support a flexible pattern-matching syntax and facilities to traverse programs recursively while applying transformations.

While Squid quasiquotes focus on expressions (not definitions), Squid also provides a way to embed arbitrary class and object definitions so that their methods can be inlined effortlessly, at the discretion of the metaprogrammer.

As a quick reference for Squid users, we provide a cheat sheet that summarizes the features of Squid quasiquotes. Also see the quasiquotes tutorial.

Multi-Stage Programming and Quoted Staged Rewriting

Squid fully support the multi-staged programming paradigm (MSP), allowing the composition and evaluation of program fragments at runtime (via runtime compilation or reflective interpretation).

In addition, since Squid provides type-safe code inspection capabilities (a novelty in the field of statically-typed staging), it can be used to achieve quoted staged rewriting (QSR) [2], an approach to program optimization that mixes the advantages of user-defined rewrite rules, strategic program transformation and MSP.

Library-Defined Optimizations

Squid provides tools to create static optimizers, which are used to optimize at compile time delimited portions of a user's codebase. Together with quoted staged rewriting, this capability allows for quite flexible and safe library-defined optimizations [2].

Click here to learn more about static optimizers.

Program Transformation Support

Squid supports the definition and composition of custom program transformers and transformation strategies. This is achieved via Scala mixin-composition and quasiquote-based rewriting declarations. Squid transformers are type-preserving, and they make sure that transformed programs remain well-typed and well-scoped.

Click here to learn more about Squid transformers.

Intermediate Representations

Squid quasiquotes, and Squid's infrastructure in general, are unique in that they are generic in the actual intermediate representation (IR) used to encode program fragments. Custom IRs can be implemented and plugged into Squid to gain the high-level, type-safe features offered by Squid. This is done by implementing Squid's object algebra interface [1].

[Click here to learn more about Squid intermediate representations.](lso see the quasiquotes tutorial

Squid Macros

Squid macros are an experimental type-safe alternative to legacy scala-reflect macros, based on Squid's infrastructure. The current implementation is a very rough prototype that should not yet be relied upon.

As an example, here is the short program transformation showed at the beginning of this document, rewritten as a Squid macro:

@macroDef(Embedding)
def myMacro(pgrm0: Double) = {
  // in this scope, `pgrm0` has type `Code[Double]`
  val pgrm1 = pgrm0 transformWith (new Lowering('MyPhase) with BottomUpTransformer)
  val pgrm2 = pgrm1 rewrite {
    case code"($xs:List[$t]).::($x).head" => x
    case code"(${Const(n)}:Int) + (${Const(m)}:Int)" => Const(n+m)
  }
  pgrm2
}

// the following should appear in a different project:
myMacro(Test.foo(1 :: 2 :: 3 :: Nil) + 1) // expands into `2.toDouble`

(Note: the macroDef feature currently lives in experimental branch squid-macros.)

Applications of Squid

Squid is still quite new and "bleeding edge". See the examples folder for some example uses. A little query compiler built with Squid can be found here. Another LINQ-inspired query engine build with Squid can be found here. We also built a small staged linear algebra library prototype [4], to be released soon.

Publications

[1]: Lionel Parreaux, Amir Shaikhha, and Christoph E. Koch. 2017. Squid: Type-Safe, Hygienic, and Reusable Quasiquotes. In Proceedings of the 2017 8th ACM SIGPLAN Symposium on Scala (SCALA 2017). (Get the paper here.)

[2]: Lionel Parreaux, Amir Shaikhha, and Christoph E. Koch. 2017. Quoted Staged Rewriting: a Practical Approach to Library-Defined Optimizations. In Proceedings of the 2017 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE 2017). Best Paper Award. (Get the paper here.)

[3]: Lionel Parreaux, Antoine Voizard, Amir Shaikhha, and Christoph E. Koch. 2018. Unifying Analytic and Statically-Typed Quasiquotes. In Proceedings of the ACM on Programming Languages (POPL 2018). (Get the paper here.)

[4]: Amir Shaikhha, Lionel Parreaux. 2019. Finally, a Polymorphic Linear Algebra Language. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). (Get the paper here.)