DEV Community: Mark Hammons

A quick explanation of Path Dependent Types

Mark Hammons — Mon, 17 Jan 2022 13:26:41 +0000

Scala has had the concept of Path Dependent Types for a long time, and in Scala 3 this concept has been used to formalize the type system (see: DOT Calculus). However, you have probably wondered for a long time what practical benefits Path Dependent Types bring over generics if you're like me.

Well, path dependent types are very helpful for working with types who are only truly knowable at runtime.

C, time_t, and Path Dependent Types

I've been writing code to have Scala and C interoperate recently, and doing so has introduced me to some unique challenges. One of them was defining the type time_t so that users can use it in C bindings if need-be.

time_t is a part of the c standard library, but its implementation is left to the library implementing the library. On an i386 Linux (i386 is a 32-bit Intel arch) machine, time_t is equivalent to a JVM Long, while on i386 MidnightBSD it's equivalent to a JVM Int. Since my library bases its C bindings on types, this means that I have a serious problem:

if I define time_t as type time_t=Int my library is only useable on MidnightBSD machines
if I define time_t as type time_t=Long my library is only useable on Linux machines
if I define time64_t and time_t then my library works on both, but user code becomes locked down to one OS, and they have to worry about what OS to develop for.

If only types could be defined at runtime... if I could write

type time_t = if os == Linux then Long 
else if os == MidnightBSD then Int 
else Nothing

Then I'd have no problems!! If only there was a way to write types that are defined depending on the path the program takes at runtime...

Oh! Path Dependent Types!!

Making things work

With a couple of traits I can make things work for my users. First I need a prototype for time_t:

trait time_t_proto:
  type time_t
  val time_t_integral: Integral[time_t]
  implicit class time_t_ops(time_t: time_t) 
    extends time_t_integral.IntegralOps(time_t)
  implicit class time_t_ord(time_t: time_t) 
    extends time_t_integral.OrderingOps(time_t)

This version of time_t is what Scala will use at compile time, and in it we promise that time_t will have an Integral typeclass defined no matter the runtime value. Then we tell the compiler how to extend time_t with functionality like a + operator or < operator via the time_t_ops and time_t_ord implicit classes. This lets users do basic ordering and arithmetic on these types as if they were Int or Long despite their type being unknown at compile-time.

Now we need the "implementation":

trait time_t_impl[U](using val time_t_integral: Integral[U]) 
  extends time_t_proto:
  type time_t = U

This doesn't look like much of an implementation, but it's written this way so it can be mixed into a large, arch specific Platform type.

trait Platform extends time_t_proto

object PlatformI386 extends Platform, time_t_impl[Int]
object PlatformX64 extends Platform, time_t_impl[Long]

val platform: Platform = if arch == i386 then PlatformI386 
else if arch == x86_64 then PlatformX64
else ???

Finally we have our end result. The design used for the time_t_proto and impl allows for multiple of these proto types and impl types for other platform specific C types (dev_t for example). It also allows us to quickly and easily define a set of bindings for the myriad computing platforms. Finally, the appropriate Platform implementation is selected at runtime and assigned to the platform value, giving users a way to use platform specific types without writing in a platform specific way.

The end result is that users can define their bindings like so:

import platform.time_t
def time(timer: Ptr[time_t]): time_t = bind

and this binding will work regardless of the computer it's accessed on, because the appropriate, path dependent type info will be loaded and used at runtime, while giving the compiler enough information and assurances at compile time to keep things completely type-safe.

Of course, the users in question can still write platform specific code if they wish.

import PlatformX64.time_t
def time(timer: Ptr[time_t]): time_t = bind

The above code works just fine, and time_t in the above code is understood to be Long at compile-time instead of being an unknown type. However, this code would no-longer work everywhere, and that's a big draw of writing for the JVM.

Could this be done with generics?

In short, no. We could not achieve the same effect with the same amount of work using generics. We could try to do the above with generics, but generics would fail us. Lets say we modified the proto traits and the Platform trait to take a generic instead of the embedded type time_t:

trait time_t_proto[time_t]:
  val time_t_integral: Integral[time_t]
  implicit class time_t_ops(time_t: time_t) 
    extends time_t_integral.IntegralOps(time_t)
  implicit class time_t_ord(time_t: time_t) 
    extends time_t_integral.OrderingOps(time_t)

trait time_t_impl[U](using val time_t_integral: Integral[U]) 
  extends time_t_proto[U]

trait Platform[A] extends time_t_proto[A]

object PlatformI386 extends Platform[Int], time_t_impl[Int]
object PlatformX64 extends Platform[Long], time_t_impl[Long]

val platform: Platform[?] = if arch == i386 then PlatformI386 
else if arch == x86_64 then PlatformX64
else ???

The above code will very certainly compile, but how will the user get their time_t type? The ? type here corresponds to the correct type, but it's unusable for our users. Worse, our code has become more complex, and to get Platform to truly work the way we want, we'd probably have to do a lot of work to turn it into a god object that manages all parts of binding to C.

In summary

Path dependent types are a very powerful feature of Scala, but they are generally not well understood in the community. I believe that the problem of platform specific types (like C's time_t) easily illustrates the need for path dependent types, and how they can outshine generics in some situations.

The wonder of context functions

Mark Hammons — Tue, 21 Dec 2021 16:11:33 +0000

There have been many new features released in Scala 3, but one of the ones that had seemingly little use to me was context functions.

Context functions in Scala 3 are the ability to express a function that needs context (not direct input) in order to evaluate. This probably doesn't mean a whole lot in black and white, so I'll demonstrate with an example:

//a method that needs two Int inputs
def add(a: Int, b: Int) = a + b

//a function that needs two Int inputs
val add = (a: Int, b: Int) = a + b

//a method in scala 2 style that requires context
def getExecutionContext(implicit ec: ExecutionContext): Unit = ec.reportFailure(new Exception("foo"))

//a function that requires context
val getExecutionContext = (ec: ExecutionContext) ?=> ec.reportFailure(new Exception("foo"))

Basically, context functions are to methods that require context what functions are to methods. You can capture and pass around a context function, and even assign it to a val. This does not seem to be much to write home about, but it's actually a very powerful concept.

Dependency Injection

Dependency injection is something that's frequently needed in Scala, and the community has produced a number of solutions for it. Some examples are

Macwire - Stitches together classes based on their constructors to provide compile time dependency injection
Reader monad and Kleisli - The reader monad is a category theory compatible way to build up and inject dependencies.
ZIO's RIO and URIO types - These effect types carry around context with them and can be used for dependency injection purposes
Implicits - these have been suggested as a method of dependency injection

With context functions, implicits become incredibly suitable for dependency injection, and may be the best option for the pattern. This is because the parameters of context functions:

Can curry: (A,B) ?=> C can become A ?=> B ?=> C automatically
Can uncurry: A ?=> B ?=> C is equivalent to (A,B) ?=> C
Don't care about order: A ?=> B ?=> C is equivalent to B ?=> A ?=> C
Can be inferred: val getExecutionContext: ExecutionContext ?=> Unit = summon[ExecutionContext].report(new Exception("foo")) is equivalent to our previous implementation.

These four properties add up to a powerful dependency injection mechanism:

trait Fooer:
  def foo(a: Int): Int

type Fooed[A] = Fooer ?=> A

val fooer: Fooed[Fooer] = summon[Fooer]

def fn(i: Int): Fooed[String] = 
  fooer.foo(i)

val value: Fooed[Double] = fn(3).toDouble

@main
def run = 
  given Fooer with
    def foo(a: Int) = a * 3

  println(value)

As you can see above, fn needed a Fooer, which needed to be passed into value if value wanted to use fn. In Scala 2, this would've necessitated that value be a method, but now it can be a val. But what about mixing dependencies?

trait Fooer:
  def foo(a: Int): Int

type Fooed[A] = Fooer ?=> A

val fooer: Fooed[Fooer] = summon[Fooer]

trait Barrer:
  def bar(d: Double): String

type Barred[A] = Barrer ?=> A

val barrer: Barred[Barrer] = summon[Barrer]

def method(i: Int): Fooed[String] = 
  fooer.foo(i).toString

def fn(d: Double): Barred[Short] = 
  barrer.bar(d).toShort

These dependencies can be composed

val value1: Barred[Fooed[String]] = 
  (method(3)*fn(2.0)).toString

Reordered

val value2: Fooed[Barred[String]] = value1

And eliminated piece by piece:

val value3: Fooed[String] = 
  given Barrer with
    def bar(d: Double) = d.toString
  value2

As you can see, context functions make for a powerful dependency injection mechanism. They also don't require mapping, flatmapping, etc like the Reader monad requires. Best of all, this abstraction doesn't have the runtime overhead of the Reader monad or Kleisli, and so can be used to add context to any effect type without paying a price for it.

Regarding real-world uses of this concept, I used it today to put natchez tracing in my http4s project. While the project is still small, I was shocked at the lack of invasiveness of this approach compared to usage of Kleisli to achieve the same effect.

While Scala 3 has introduced a massive amount of new, helpful concepts, the introduction of context functions may well be one of the most helpful, and yet most underrated of these.

SLinC Update Dec 6, 2021

Mark Hammons — Mon, 06 Dec 2021 01:36:22 +0000

Over the past month I've been developing SLinC, a library to generate bindings to C functions from pure Scala code using Java 17's foreign incubator.

I'm doing my best to design SLinC to be easy to use to generate C bindings, while still having them be performant, and I think this second update reaches that goal.

Binding C functions

C functions are fairly simple to bind in SLinC. You write a method definition with the name of the C function, and the params with corresponding scala types, and use the bind macro and SLinC will generate a binding for you.

def atof(string: String)(using SegmentAllocator): Double = bind

A using SegmentAllocator clause is needed in the function definition if one or more of the parameter inputs, or the result, requires allocation of native memory. In this case, Strings require allocation because the String must be copied into native memory as a C-String before it can be passed on. In general, Strings and Struct types cause the need of a SegmentAllocator.

When using a method binding that requires an allocator, you can wrap it in a scope.

val result = scope {
  atof("5.0")
} //result == 5.0

Scopes control memory allocation and deallocation. Once a scope has ended, any memory that was allocated using that scope will be immediately freed.

Defining Structs

Structs in SLinC are represented by standard case classes which derive the Struct typeclass.

case class div_t(quot: Int, rem: Int) derives Struct

Structs can be serialized (pushed into native memory) and passed to/returned from functions.

val ptr: Ptr[div_t] = div_t(5,2).serialize
def div(numer: Int, denom: Int)(using SegmentAllocator): div_t = bind

scope{
  div(5,2)
} //result == div_t(2,1)

Structs are pass by value. When used as a method parameter, the structs contents will be copied into native memory for usage by the C world. When used as a method return, the struct data will be copied out of native memory into the JVM heap.

Pointers

Pointers in SLinC are datatypes that have information about accessing a region of native memory. They have a dereference operator and an update operation.

val ptr = div_t(5,2).serialize //push the struct into native memory

!ptr //result == div_t(5,2)
!ptr = div_t(2,1)
!ptr //result == div_t(2,1)

Pointer dereferencing/updating involves copying the entire data type being pointed to into/out of native memory. This can be fairly expensive, especially if you only want to update a small portion of native memory, so partial dereferencing has been provided.

!ptr.partial.quot //result == 2
!ptr.partial.quot = 0
!ptr //result == div_t(0,1)

Partial dereferencing enriches the pointer type (which uses Scala 3's programmatic structural types) with a set of members that are Ptr versions of the original members of the struct. In short, ptr.partial gives you access to the following type:

Ptr[div_t] {
  val quot: Ptr[Int]
  val rem: Ptr[Int]
}

This enriched type is calculated on a per-struct basis at compile-time and is fully compatible with nested structs.

Libraries

New types have been added to allow users to write bindings for non-standard lib libraries: Library and Location.

Library is used to define bindings for a library as well as how to load the library.

object Testlib extends Library(Location.Local("slinc/test/native/libtest.so")):
   case class a_t(a: Int, b: Int) derives Struct
   case class b_t(c: Int, d: a_t) derives Struct

   def slinc_test_modify(b_t: b_t)(using SegmentAllocator): b_t = bind

In the above example, we bind to a library that is at slinc/test/native/libtest.so, relative to the current working directory of the program. System is a location type used to load libraries that are on the system path, and Absolute is for binding to libraries using an absolute filesystem path. These values and bindings are not done at compile-time, but rather when the object is first accessed, so you can have your program search for a library and then use that path as the basis for your library binding. Likewise, it's not necessary to have your library binding be an object. It can be a class or trait as well.

Performance

At present, I've been mainly comparing SLinC performance to JNA. I am too lazy to learn and write JNI code, and JNR has proven to be difficult to get the bindings right for. At present, SLinC is 50x more performant on benchmarks like calling div from the standard library as opposed to JNA. When it comes to simpler methods like getpid SLinC is still more performant, but the difference is way less stark.

I plan on adding features that will help SLinC's performance in the near future, like something like a young generation native memory segment for copying structs into for copy by value parameters and such.

Behind the scenes

Most of what SLinC does at the moment is cut down on boilerplate via macros. A quick example of this is a binding to localtime.

def localtime(timer: Ptr[Long]): Ptr[tm] = { 
  val address: jdk.incubator.foreign.MemoryAddress = io.gitlab.mhammons.polymorphics.MethodHandleHandler.call1(io.gitlab.mhammons.slinc.components.UniversalNativeCache.addMethodHandle(8, io.gitlab.mhammons.slinc.components.Linker.linker.downcallHandle(io.gitlab.mhammons.slinc.components.SymbolLookup.given_SymbolLookup.lookup("localtime"), java.lang.invoke.MethodType.methodType(io.gitlab.mhammons.slinc.components.LayoutOf.given_LayoutOf_Ptr[StdlibSuite.this.tm].carrierType, io.gitlab.mhammons.slinc.components.LayoutOf.given_LayoutOf_Ptr[scala.Long].carrierType, ), jdk.incubator.foreign.FunctionDescriptor.of(io.gitlab.mhammons.slinc.components.LayoutOf.given_LayoutOf_Ptr[StdlibSuite.this.tm].layout, io.gitlab.mhammons.slinc.components.LayoutOf.given_LayoutOf_Ptr[scala.Long].layout))), timer.asMemoryAddress).asInstanceOf[jdk.incubator.foreign.MemoryAddress]
  new io.gitlab.mhammons.slinc.Ptr[StdlibSuite.this.tm](address.asSegment(StdlibSuite.this.tm.derived$Struct.layout.byteSize(), address.scope()), 0L, scala.Predef.Map.empty[java.lang.String, scala.Any])
}

Todo

There is still a lot left to do on SLinC. I must test it with all sorts of functions and libraries, and I must implement support for function pointers, padding, union types, varargs, and more. I will hopefully tackle these one-by-one in the coming months. I believe once I have a more solid subset of C features implemented I will release a v0.0.1 version of SLinC for others to make use of.

You can find the current version of SLinC at Gitlab and Github