OlivierBlanvillain

Revisiting Tagless Final Interpreters

Tageless Final interpreters are an alternative to the traditional Algebraic Data Type (and generalized ADT) based implementation of the interpreter pattern. This document presents the Tageless Final approach with Scala, and shows how Dotty with it's recently added implicits functions makes the approach even more appealing. All examples are direct translations of their Haskell version presented in the Typed Tagless Final Interpreters: Lecture Notes (section 2).

The interpreter pattern has recently received a lot of attention in the Scala community. A lot of efforts have been invested in trying to address the biggest shortcomings of ADT/GADT based solutions: extensibility. One can first look at cats' Inject typeclass for an implementation of [Data Type à la Carte](http://www.cs.ru.nl/~W.Swierstra/Publications/DataTypesA

djspiewak

assume: () -> a

True -> a
not True \/ a
False \/ a
a \/ False
not a -> False
(a -> False) -> False

True = ()

djspiewak

Consider a value of the following type:

type Thunk[A] = () => A

This value represents a thunk of A. Any general effect type, F[_], in Scala must define a function of the following type:

val suspend: (() => A) => F[A]

thbkrkr

com.sun.management:type=DiagnosticCommand
com.sun.management:type=HotSpotDiagnostic
java.lang:name=CodeCacheManager,type=MemoryManager
java.lang:name=Code Cache,type=MemoryPool
java.lang:name=Compressed Class Space,type=MemoryPool
java.lang:name=G1 Eden Space,type=MemoryPool
java.lang:name=G1 Old Generation,type=GarbageCollector
java.lang:name=G1 Old Gen,type=MemoryPool
java.lang:name=G1 Survivor Space,type=MemoryPool
java.lang:name=G1 Young Generation,type=GarbageCollector

djspiewak

Coherence Domains in Scala

Miles probably already thought of this idea and found some problem with it, but I'm going to go ahead and propose it anyway so that he has an easy way of telling me it's a bad idea. :-)

In order to solve the problem of typeclass coherence in a system which supports local instances (Scala), I propose that we introduce a tagging type – which I call a coherence domain – on all implicit values, regardless of their declaration scope. This tagging type could be encoded as a type member on the type of the implicit value itself, but that is awkward, exposes some details of the machinery in user-facing APIs, and also requires a macro to fully implement. This proposal requires a small, backwards-compatible change to the type system, an unambiguous and consistent change to the syntax (also backwards-compatible), and a minor revision to the implicit resolution rules.

Domains

Declaration

jdegoes

case class IO[A](unsafePerformIO: () => A) { self =>
  def map[B](ab: A => B): IO[B] =
    IO(() => ab(unsafePerformIO()))
  def flatMap[B](afb: A => IO[B]): IO[B] =
    IO(() => afb(unsafePerformIO()).unsafePerformIO())
  def attempt: IO[Either[Throwable, A]] =
    IO(() => try { Right(unsafePerformIO()) } catch { case t : Throwable => Left(t) })
  def forkIO: Task[A] = Task(f => IO(unsafePerformIO = () => {
    new java.lang.Thread {
      override def run: Unit = {

djspiewak

Getting Started in Scala

This is my attempt to give Scala newcomers a quick-and-easy rundown to the prerequisite steps they need to a) try Scala, and b) get a standard project up and running on their machine. I'm not going to talk about the language at all; there are plenty of better resources a google search away. This is just focused on the prerequisite tooling and machine setup. I will not be assuming you have any background in JVM languages. So if you're coming from Python, Ruby, JavaScript, Haskell, or anywhere…  I hope to present the information you need without assuming anything.

Disclaimer It has been over a decade since I was new to Scala, and when I was new to Scala, I was coming from a Java and Ruby background. This has probably caused me to unknowingly make some assumptions. Please feel free to call me out in comments/tweets!

One assumption I'm knowingly making is that you're on a Unix-like platform. Sorry, Windows users.

Getting the JVM

lihaoyi

package test
package grepgit.core

import scala.collection.mutable
import scala.reflect.ClassTag

/**
  * A Generator of elements of type [[A]].
  *
  * [[Generator]] is basically the inverse of

jdegoes

Applied Functional Programming with Scala - Notes

Copyright © 2016-2018 Fantasyland Institute of Learning. All rights reserved.

1. Mastering Functions

A function is a mapping from one set, called a domain, to another set, called the codomain. A function associates every element in the domain with exactly one element in the codomain. In Scala, both domain and codomain are types.

val square : Int => Int = x => x * x

djspiewak

type checking requires testing the equivalence of runtime expressions

Quick prerequisite here: testing the equivalence of runtime expressions is, in general, undecidable for languages with straightforward recursion. (see: eq(PDA)) Thus, for Scala to be a dependently-typed language, we must clarify an ambiguity in this definition:

type checking requires testing the pessimistic equivalence of runtime expressions

Which is to say, the type checker will attempt to check the equivalence of runtime expressions, and in the cases where it fails, it will assume not-equal. In order to prevent this definition from being completely vacuous, let's further assume that there must exist at least one case (perhaps trivial) where the compiler is able to perform this runtime equivalence checking, and thus its equality check produces True.

Scala's rules in this area are more pessimistic than perhaps they could be, but they do still apply. Specifically, the following two rules are in play: