Repository: effekt-lang/effekt
Pull request #199 (2022-11-30 17:06:53)

Polymorphism in machine-based backends (through boxing)
*[EDIT: Old (outdated) version below)]*

This adds a phase `PolymorphismBoxing`, replacing primitive types `T` by `BoxedT` in type arguments and inserting coercions where necessary. `BoxedT` should be defined in the standard library for each type `T`.



#### Old version:
This is WIP to bring polymorphism to machine-based backends.
It currently works using an additional pass over lifted, auto-boxing and unboxing values.

It also is more of a proof-of-concept/prototype in it's current stage.

Basic polymorphism works, but not with block parameters (e.g. a function `Int => Int` as argument for a parameter of type `A => B`) - This will give a readable error message, however.

marzipankaiser: Some remarks/things I would do differently:
1. Wait for #132 if possible. Since auto-boxing/-unboxing is basically implicit conversion, we need types all the time and in some places they're not easily available. (e.g. type of `BlockLit`s)
     - Using a BlockLit of type `Int => Int` as `A => B` needs wrapping and for this we need the type of the `BlockLit`.
2. Maybe do the transformation earlier (e.g. in Core?, so we do not need to consider Evidence parameters)
3. Parameters are somewhat inconsistent between type and term level: `FunctionType` has different kinds of parameters separated, `BlockLit` just has one List. this makes it harder to find the corresponding ones.
marzipankaiser: Adding the new Phase crashes with alll backends tried, known bugs so far:
- for all machine backends: ...App(BlockLit(...)...) is not supported in machine. This was easiest to generate, maybe we could support this? (alternatively: inline it)
- for all lift backends: LiftInference does not work correctly (always passes here to the wrapped function instead of forwarding the evidence)

The generated core looks fine for me, though (on simple examples).
b-studios: Wow cool, so machine-based backends get boxing "for free" if they implement (polymorphic) datatypes?
marzipankaiser: It should also be possible to make specialized versions of this phase that box only some, or more types (or use different boxes) when used polymorphically, by overriding the partial function `box: ValueType -> Boxer`.
marzipankaiser: I started adding tests using #205 now, will continue doing so as I find the time.
marzipankaiser: Rebased onto current master and cleaned up the commit history slightly in the process (moving bugfix commits to the point where the bug was introduced, mostly).
marzipankaiser: With something like #213, this could be changed to generate a `BoxedT` exactly for each `extern type T`, allowing this to be backend-specific without explicitly exchanging/passing parameters to this Phase.

Patch:
diff --git a/effekt/shared/src/main/scala/effekt/Compiler.scala b/effekt/shared/src/main/scala/effekt/Compiler.scala
index 98c88753..08307c77 100644
--- a/effekt/shared/src/main/scala/effekt/Compiler.scala
+++ b/effekt/shared/src/main/scala/effekt/Compiler.scala
@@ -231,15 +231,27 @@ trait Compiler {
    * It does **not** generate files and write them using `saveOutput`!
    * This is achieved by `compileWhole`.
    */
-  def compileSeparate(source: Source)(using Context): Option[(CoreTransformed, Document)] =
-    (Frontend andThen Middleend andThen CoreDependencies andThen Backend.separate).apply(source)
+  def compileSeparate(source: Source)(using C: Context): Option[(CoreTransformed, Document)] = C.config.backend() match {
+    case "llvm" =>
+      (Frontend andThen Middleend andThen core.PolymorphismBoxing andThen CoreDependencies andThen Backend.separate).apply(source)
+    case _ =>
+      (Frontend andThen Middleend andThen CoreDependencies andThen Backend.separate).apply(source)
+  }
 
   /**
    * Used by [[Driver]] and by [[Repl]] to compile a file
    */
-  def compileWhole(source: Source)(using Context): Option[Compiled] =
-    (Frontend andThen Middleend andThen CoreDependencies andThen Aggregate andThen Backend.whole).apply(source)
+  def compileWhole(source: Source)(using C: Context): Option[Compiled] = C.config.backend() match {
+    case "llvm" =>
+      (Frontend andThen Middleend andThen CoreDependencies andThen Aggregate andThen core.PolymorphismBoxing andThen Backend.whole).apply(source)
+    case _ =>
+      (Frontend andThen Middleend andThen CoreDependencies andThen Aggregate andThen Backend.whole).apply(source)
+  }
 
-  def compileAll(source: Source)(using Context): Option[CoreTransformed] =
-    (Frontend andThen Middleend andThen CoreDependencies andThen Aggregate).apply(source)
+  def compileAll(source: Source)(using C: Context): Option[CoreTransformed] = C.config.backend() match {
+    case "llvm" =>
+      (Frontend andThen Middleend andThen CoreDependencies andThen Aggregate andThen core.PolymorphismBoxing).apply (source)
+    case _ =>
+      (Frontend andThen Middleend andThen CoreDependencies andThen Aggregate).apply(source)
+  }
 }
diff --git a/effekt/shared/src/main/scala/effekt/core/Parser.scala b/effekt/shared/src/main/scala/effekt/core/Parser.scala
index 3c6760ef..d265c5fb 100644
--- a/effekt/shared/src/main/scala/effekt/core/Parser.scala
+++ b/effekt/shared/src/main/scala/effekt/core/Parser.scala
@@ -137,11 +137,17 @@ class CoreParsers(positions: Positions, names: Names) extends EffektLexers(posit
   // Pure Expressions
   // ----------------
   lazy val pure: P[Pure] =
+    pureNonAccess ~ many((`.` ~> id) ~ (`:` ~> valueType)) ^^ {
+      case firstTarget ~ accesses => accesses.foldLeft(firstTarget){
+        case (target, field ~ tpe) => Pure.Select(target, field, tpe)
+      }
+    }
+
+  lazy val pureNonAccess: P[Pure] =
     ( literal
     | id ~ (`:` ~> valueType) ^^ Pure.ValueVar.apply
     | `box` ~> captures ~ block ^^ { case capt ~ block => Pure.Box(block, capt) }
     | block ~ maybeTypeArgs ~ valueArgs ^^ Pure.PureApp.apply
-    | pure ~ (`.` ~> id) ~ (`:` ~> valueType) ^^ Pure.Select.apply
     | failure("Expected a pure expression.")
     )
 
@@ -169,12 +175,20 @@ class CoreParsers(positions: Positions, names: Names) extends EffektLexers(posit
   // Blocks
   // ------
   lazy val block: P[Block] =
+    ( blockNonMember ~ many((`.` ~> id) ~ (`:` ~> blockType)) ^^ {
+          case firstReceiver ~ fields => fields.foldLeft(firstReceiver) {
+          case (receiver, field ~ tpe) => Block.Member(receiver, field, tpe)
+        }
+      }
+    | blockNonMember
+    )
+
+  lazy val blockNonMember: P[Block] =
     ( id ~ (`:` ~> blockType) ~ (`@` ~> captures) ^^ Block.BlockVar.apply
     | `unbox` ~> pure ^^ Block.Unbox.apply
     | `new` ~> implementation ^^ Block.New.apply
     | blockLit
     // TODO check left associative nesting (also for select)
-    | block ~ (`.` ~> id) ~ (`:` ~> blockType) ^^ Block.Member.apply
     | `(` ~> block <~ `)`
     )
 
diff --git a/effekt/shared/src/main/scala/effekt/core/PolymorphismBoxing.scala b/effekt/shared/src/main/scala/effekt/core/PolymorphismBoxing.scala
new file mode 100644
index 00000000..5390dce8
--- /dev/null
+++ b/effekt/shared/src/main/scala/effekt/core/PolymorphismBoxing.scala
@@ -0,0 +1,371 @@
+package effekt.core
+
+import effekt.PhaseResult.CoreTransformed
+import effekt.context.Context
+import effekt.symbols
+import effekt.symbols.{TmpBlock, TmpValue}
+import effekt.{CoreTransformed, Phase}
+
+import scala.annotation.targetName
+
+/**
+ * [[Phase]] on [[CoreTransformed]] to automatically box values when used polymorphically
+ * (i.e., their types are type parameters).
+ *
+ * By default, it will box all primitive types (i.e. all types of the form [[ValueType.Data]]`(T,List())`
+ * with `T` in [[symbols.builtins.rootTypes]]) using the data type `BoxedT` found in the prelude
+ * (see [[symbols.Module.findPrelude]]).
+ * This behavior can be changed by overriding [[box]].
+ */
+object PolymorphismBoxing extends Phase[CoreTransformed, CoreTransformed] {
+
+  override val phaseName: String = "polymorphism boxing"
+
+  /**
+   * Describes how to box/unbox values
+   * @param tpe The type of the values to be boxed
+   * @param constructor The constructor to box the values with
+   * @param field The field to access for unboxing
+   */
+  case class Boxer(tpe: ValueType, constructor: Id, field: Id)
+
+  /**
+   * Partial function to describe which values to box and how.
+   * Is defined iff values of the given type should be boxed.
+   *
+   * @param tpe The [[ValueType]] of the value
+   * @return a [[Boxer]] that describes how to box values of that type
+   */
+  def box(using PContext): PartialFunction[ValueType, Boxer] = {
+    case ValueType.Data(name, List()) if symbols.builtins.rootTypes.values.exists(_ == name) =>
+      if(!Context.module.findPrelude.types.contains("Boxed" + name)) {
+        Context.abort(s"Primitive ${name} is used as type parameter but Boxed${name} is not defined.")
+      }
+      Context.module.findPrelude.types("Boxed" + name) match {
+        case tpeCns @ symbols.TypeConstructor.Record(_, List(), cns @ symbols.Constructor(_, List(), List(field), _)) =>
+          Boxer(ValueType.Data(tpeCns,List()), cns, field)
+        case tpeCns @ symbols.TypeConstructor.DataType(_, List(), List(cns @ symbols.Constructor(_, List(), List(field), _))) =>
+          Boxer(ValueType.Data(tpeCns,List()), cns, field)
+        case _ =>
+          Context.abort(s"No appropriate Boxed${name} type, but ${name} used as type parameter.")
+      }
+  }
+
+  class PContext(val declarations: List[Declaration])(using val context: Context){
+    def findDeclarations(id: Id): List[Declaration] = {
+      declarations.filter(_.id == id)
+    }
+    def getDataLikeDeclaration(id: Id): Declaration.Data = {
+      val decls: List[Declaration.Data] = declarations.flatMap{
+        case d : Declaration.Data if d.id == id =>
+          Some(d)
+        case _ => None
+      }
+      if (decls.length != 1) {
+        context.abort(s"No unique declaration for ${id}. Options: \n" +
+          (decls.map(d => PrettyPrinter.pretty(PrettyPrinter.indent(PrettyPrinter.toDoc(d)), 60).layout)).mkString("\n\n"))
+      } else {
+        decls.head
+      }
+    }
+  }
+  def PContext(using ctx: PContext): PContext = ctx
+  implicit def Context(using ctx: PContext): Context = ctx.context
+
+  override def run(input: CoreTransformed)(using Context): Option[CoreTransformed] = input match {
+    case CoreTransformed(source, tree, mod, core) => {
+      implicit val pctx: PContext = new PContext(core.declarations)
+      Context.module = mod
+      val transformed = transform(core)
+      Some(CoreTransformed(source, tree, mod, transformed))
+    }
+  }
+
+  def transform(decl: ModuleDecl)(using PContext): ModuleDecl = decl match {
+    case ModuleDecl(path, imports, declarations, externs, definitions, exports) =>
+      ModuleDecl(path, imports, declarations map transform, externs map transform, definitions map transform, exports)
+  }
+
+  def transform(declaration: Declaration)(using PContext): Declaration = declaration match {
+    case Declaration.Data(id, tparams, constructors) =>
+      Declaration.Data(id, tparams, constructors map transform)
+    case Declaration.Interface(id, tparams, properties) =>
+      Declaration.Interface(id, tparams, properties map transform)
+  }
+
+  def transform(constructor: Constructor)(using PContext): Constructor = constructor match {
+    case Constructor(id, fields) => Constructor(id, fields map transform)
+  }
+
+  def transform(property: Property)(using PContext): Property = property match {
+    case Property(id, tpe) => Property(id, transform(tpe))
+  }
+
+  def transform(field: Field)(using PContext): Field = field match {
+    case Field(id, tpe) => Field(id, transform(tpe))
+  }
+
+  def transform(extern: Extern)(using PContext): Extern = extern match {
+    case Extern.Def(id, tparams, cparams, vparams, bparams, ret, annotatedCapture, body) =>
+      Extern.Def(id, tparams, cparams, vparams map transform, bparams map transform, transform(ret),
+        annotatedCapture, body)
+    case Extern.Include(contents) => Extern.Include(contents)
+  }
+
+  def transform(valueParam: Param.ValueParam)(using PContext): Param.ValueParam = valueParam match {
+    case Param.ValueParam(id, tpe) => Param.ValueParam(id, transform(tpe))
+  }
+  def transform(blockParam: Param.BlockParam)(using PContext): Param.BlockParam = blockParam match {
+    case Param.BlockParam(id, tpe) => Param.BlockParam(id, transform(tpe))
+  }
+
+  def transform(definition: Definition)(using PContext): Definition = definition match {
+    case Definition.Def(id, block) => Definition.Def(id, transform(block))
+    case Definition.Let(id, binding) => Definition.Let(id, transform(binding))
+  }
+
+  def transform(block: Block.BlockLit)(using PContext): Block.BlockLit = block match {
+    case Block.BlockLit(tparams, cparams, vparams, bparams, body) =>
+      Block.BlockLit(tparams, cparams, vparams map transform, bparams map transform,
+        transform(body))
+  }
+  def transform(block: Block)(using PContext): Block = block match {
+    case Block.BlockVar(id, annotatedTpe, annotatedCapt) =>
+      Block.BlockVar(id, transform(annotatedTpe), annotatedCapt)
+    case b: Block.BlockLit => transform(b)
+    case Block.Member(block, field, annotatedTpe) =>
+      Block.Member(transform(block), field, transform(annotatedTpe))
+    case Block.Unbox(pure) =>
+      Block.Unbox(transform(pure))
+    case Block.New(impl) =>
+      Block.New(transform(impl))
+  }
+
+  def transform(implementation: Implementation)(using PContext): Implementation = implementation match {
+    case Implementation(BlockType.Interface(symbol, targs), operations) =>
+      Implementation(BlockType.Interface(symbol, targs map transform), operations map transform(targs))
+
+  }
+
+  def transform(targs: List[ValueType])(operation: Operation)(using PContext): Operation = operation match {
+    case Operation(name, tparams, cparams, vparams, bparams, resume, body) =>
+      val blockTpe = BlockType.Function(tparams, cparams, vparams.map(_.tpe), bparams.map(_.tpe), body.tpe)
+      val implBlock: Block.BlockLit = Block.BlockLit(tparams, cparams, vparams, bparams, body)
+      val transformed: Block.BlockLit = coercer(implBlock.tpe, blockTpe)(implBlock)
+      Operation(name, transformed.tparams, transformed.cparams, transformed.vparams, transformed.bparams,
+        resume map transform,
+        transformed.body)
+  }
+
+  def transform(stmt: Stmt)(using PContext): Stmt = stmt match {
+    case Stmt.Scope(definitions, body) =>
+      Stmt.Scope(definitions map transform, transform(body))
+    case Stmt.Return(expr) => Stmt.Return(transform(expr))
+    case Stmt.Val(id, binding, body) => Stmt.Val(id, transform(binding), transform(body))
+    case Stmt.App(callee, targs, vargs, bargs) =>
+      instantiate(callee, targs).call(callee, vargs map transform, bargs map transform)
+    case Stmt.If(cond, thn, els) =>
+      Stmt.If(transform(cond), transform(thn), transform(els))
+    case Stmt.Match(scrutinee, clauses, default) =>
+      scrutinee.tpe match {
+        case ValueType.Data(symbol, targs) =>
+          val Declaration.Data(tpeId, tparams, constructors) = PContext.getDataLikeDeclaration(symbol)
+          Stmt.Match(transform(scrutinee), clauses.map {
+            case (id, clause: Block.BlockLit) =>
+              val constructor = constructors.find(_.id == id).get
+              val casetpe: BlockType.Function = BlockType.Function(tparams, List(),
+                constructor.fields.map(_.tpe), List(), Type.inferType(clause.body)
+              )
+              (id, coercer(clause.tpe, Type.instantiate(casetpe, targs map transformArg, List()))(transform(clause)))
+          }, default map transform)
+        case t => Context.abort(s"Match on value of type ${PrettyPrinter.format(t)}")
+      }
+    case Stmt.State(id, init, region, body) =>
+      Stmt.State(id, transform(init), region, transform(body))
+    case Stmt.Try(body, handlers) =>
+      Stmt.Try(transform(body), handlers map transform)
+    case Stmt.Region(body) => Stmt.Region(transform(body))
+    case Stmt.Hole() => Stmt.Hole()
+  }
+
+  def transform(expr: Expr)(using PContext): Expr = expr match {
+    case DirectApp(b, targs, vargs, bargs) =>
+      instantiate(b, targs).callDirect(b, vargs map transform, bargs map transform)
+    case Run(s) => Run(transform(s))
+    case pure: Pure => transform(pure)
+  }
+
+  def transform(pure: Pure)(using PContext): Pure = pure match {
+    case Pure.ValueVar(id, annotatedType) => Pure.ValueVar(id, transform(annotatedType))
+    case Pure.Literal(value, annotatedType) => Pure.Literal(value, transform(annotatedType))
+    case Pure.PureApp(b, targs, vargs) =>
+      instantiate(b, targs).callPure(b, vargs map transform)
+    case Pure.Select(target, field, annotatedType) => {
+      val (symbol, targs) = target.tpe match {
+        case ValueType.Data(symbol, targs) => (symbol, targs)
+        case t => Context.abort(s"Select on value of type ${PrettyPrinter.format(t)} is not supported.")
+      }
+      PContext.getDataLikeDeclaration(symbol) match {
+        case Declaration.Data(id, tparams, List(Constructor(cns, fields))) =>
+          val f = fields.find(_.id == field).getOrElse{
+            Context.abort(s"${id} has no field ${field}.")
+          }
+          coercer(f.tpe, Type.substitute(f.tpe, (tparams zip targs).toMap, Map()))(Pure.Select(target, field, transform(annotatedType)))
+        case t => Context.abort(s"Select on data type ${t.id} is not supported.")
+      }
+    }
+    case Pure.Box(b, annotatedCapture) =>
+      Pure.Box(transform(b), annotatedCapture)
+  }
+
+  def transform(valueType: ValueType)(using PContext): ValueType = valueType match {
+    case ValueType.Var(name) => ValueType.Var(name)
+    case ValueType.Data(symbol, targs) => ValueType.Data(symbol, targs map transformArg)
+    case ValueType.Boxed(tpe, capt) => ValueType.Boxed(transform(tpe), capt)
+  }
+
+  def transform(blockType: BlockType)(using PContext): BlockType = blockType match {
+    case BlockType.Function(tparams, cparams, vparams, bparams, result) =>
+      BlockType.Function(tparams, cparams, vparams map transform, bparams map transform, transform(result))
+    case BlockType.Interface(symbol, targs) => BlockType.Interface(symbol, targs map transformArg)
+  }
+
+  def transformArg(valueType: ValueType)(using PContext): ValueType = valueType match {
+    case ValueType.Var(name) => ValueType.Var(name) // assume vars are always OK
+    case t if box.isDefinedAt(t) => box(t).tpe
+    case ValueType.Data(symbol, targs) => ValueType.Data(symbol, targs map transformArg)
+    case ValueType.Boxed(tpe, capt) => ValueType.Boxed(transform(tpe), capt)
+  }
+
+  def instantiate[B >: BlockLit <: Block](block: B, targs: List[ValueType])(using PContext): FunctionCoercer[BlockType, B] = {
+    block.tpe match {
+      case tpe: BlockType.Function =>
+        coercer(tpe, Type.instantiate(tpe, targs, tpe.cparams.map(Set(_))), targs)
+      case tpe: BlockType.Interface =>
+        Context.abort(s"Using interface of type ${tpe} in function position.")
+    }
+  }
+
+  trait Coercer[Ty <: Type, Te <: Tree] {
+    def from: Ty
+    def to: Ty
+
+    @targetName("applyType")
+    def apply(tpe: Ty): Ty = if tpe == from then to else tpe
+    def apply(t: Te): Te
+    def isIdentity: Boolean = false
+  }
+  class IdentityCoercer[Ty <: Type, Te <: Tree](
+      override val from: Ty,
+      override val to: Ty) extends Coercer[Ty, Te] {
+    override def apply(t: Te): Te = t
+    override def isIdentity: Boolean = true
+  }
+  case class BoxCoercer(valueType: ValueType)(using PContext) extends Coercer[ValueType, Pure] {
+    override def from = valueType
+    override def to = box(valueType).tpe
+
+    override def apply(t: Pure): Pure = {
+      val boxer = box(valueType)
+      val blockTpe = BlockType.Function(List(), List(), List(from), List(), to)
+      Pure.PureApp(Block.BlockVar(boxer.constructor, blockTpe, Set()), List(), List(t))
+    }
+  }
+  case class UnboxCoercer(valueType: ValueType)(using PContext) extends Coercer[ValueType, Pure] {
+    override def from = box(valueType).tpe
+    override def to = valueType
+
+    override def apply(t: Pure): Pure = {
+      val boxer = box(valueType)
+      Pure.Select(t, boxer.field, to)
+    }
+  }
+
+  def coercer(from: ValueType, to: ValueType)(using PContext): Coercer[ValueType, Pure] = (from, to) match {
+    case (f,t) if f==t => new IdentityCoercer(f,t)
+    case (_: ValueType.Var, _: ValueType.Var) => new IdentityCoercer(from, to) // are always boxed
+    case (unboxed, boxed) if box.isDefinedAt(unboxed) && box(unboxed).tpe == boxed => BoxCoercer(unboxed)
+    case (unboxed, _: ValueType.Var) if box.isDefinedAt(unboxed) => BoxCoercer(unboxed)
+    case (boxed, unboxed) if box.isDefinedAt(unboxed) && box(unboxed).tpe == boxed => UnboxCoercer(unboxed)
+    case (_: ValueType.Var, unboxed) if box.isDefinedAt(unboxed) => UnboxCoercer(unboxed)
+    case _ =>
+      //Context.warning(s"Coercing ${PrettyPrinter.format(from)} to ${PrettyPrinter.format(to)}")
+      new IdentityCoercer(from, to)
+  }
+
+  trait FunctionCoercer[Ty <: BlockType, Te <: Block] extends Coercer[Ty, Te] {
+    def callPure(block: Te, vargs: List[Pure])(using PContext): Pure
+    def callDirect(block: Te, vargs: List[Pure], bargs: List[Block])(using PContext): Expr
+    def call(block: Te, vargs: List[Pure], bargs: List[Block])(using PContext): Stmt
+  }
+  class FunctionIdentityCoercer[Ty <: BlockType, Te <: Block](
+      from: Ty, to: Ty, targs: List[ValueType]) extends IdentityCoercer[Ty, Te](from, to) with FunctionCoercer[Ty, Te] {
+    override def call(block: Te, vargs: List[Pure], bargs: List[Block])(using PContext): Stmt =
+      Stmt.App(block, targs map transformArg, vargs.map(transform(_)), bargs map transform)
+    override def callPure(block: Te, vargs: List[Pure])(using PContext): Pure =
+      Pure.PureApp(block, targs map transformArg, vargs map transform)
+    override def callDirect(block: Te, vargs: List[Pure], bargs: List[Block])(using PContext): Expr =
+      DirectApp(block, targs map transformArg, vargs map transform, bargs map transform)
+  }
+  def coercer[B >: Block.BlockLit <: Block](fromtpe: BlockType, totpe: BlockType, targs: List[ValueType] = List())(using PContext): FunctionCoercer[BlockType, B] =
+    (fromtpe, totpe) match {
+    case (f,t) if f == t => new FunctionIdentityCoercer(fromtpe, totpe, targs)
+    case (BlockType.Function(ftparams, fcparams, fvparams, fbparams, fresult),
+          BlockType.Function(ttparams, tcparams, tvparams, tbparams, tresult)) =>
+
+      val vcoercers = (fvparams zip tvparams).map {
+        case (t,f) => // note: Order inversed as contravariant in arguments
+          coercer(f,t)
+      }
+      val bcoercers: List[Coercer[BlockType, Block]] = (fbparams zip tbparams).map {
+        case (t,f) => // note: Order inversed as contravariant in arguments
+          coercer(f,t)
+      }
+      val rcoercer = coercer(fresult, tresult)
+
+      if((rcoercer +: (vcoercers ++ bcoercers)).forall(_.isIdentity)) {
+        return new FunctionIdentityCoercer(fromtpe, totpe, targs) // nothing to do here
+      }
+
+      new FunctionCoercer[BlockType, B] {
+        override def from = fromtpe
+        override def to = totpe
+
+        override def apply(block: B): B = {
+          val vparams: List[Param.ValueParam] = vcoercers.map { c => Param.ValueParam(TmpValue(), transform(c.from)) }
+          val bparams: List[Param.BlockParam] = bcoercers.map { c => Param.BlockParam(TmpBlock(), transform(c.from)) }
+          val result = TmpValue()
+          val inner = TmpBlock()
+          val vargs = (vcoercers zip vparams).map { case (c, p) => c(Pure.ValueVar(p.id, p.tpe)) }
+          val bargs = (bcoercers zip bparams).map { case (c, p) => c(Block.BlockVar(p.id, p.tpe, Set.empty)) }
+          Block.BlockLit(ftparams, bparams.map(_.id), vparams, bparams,
+            Def(inner, block,
+              Stmt.Val(result, Stmt.App(Block.BlockVar(inner, block.tpe, block.capt), targs map transformArg, vargs, bargs),
+                Stmt.Return(rcoercer(Pure.ValueVar(result, rcoercer.from))))))
+        }
+
+        override def callPure(block: B, vargs: List[Pure])(using PContext): Pure = {
+          rcoercer(Pure.PureApp(block, targs map transformArg, (vcoercers zip vargs).map {case (c,v)=> c(v)}))
+        }
+
+        override def callDirect(block: B, vargs: List[Pure], bargs: List[Block])(using PContext): Expr = {
+          val result = TmpValue()
+          Run(Let(result, DirectApp(block, targs map transformArg,
+            (vcoercers zip vargs).map {case (c,v) => c(v)},
+            (bcoercers zip bargs).map {case (c,b) => c(b)}),
+            Return(rcoercer(Pure.ValueVar(result, rcoercer.from)))))
+        }
+
+        override def call(block: B, vargs: List[Pure], bargs: List[Block])(using PContext): Stmt = {
+          val result = TmpValue()
+          Stmt.Val(result, Stmt.App(block, targs map transformArg,
+            (vcoercers zip vargs).map {case (c,v) => c(v)},
+            (bcoercers zip bargs).map {case (c,b) => c(b)}),
+            Return(rcoercer(Pure.ValueVar(result, rcoercer.from))))
+        }
+
+      }
+    case _ => Context.abort(s"Unsupported coercion from ${PrettyPrinter.format(fromtpe)} to ${PrettyPrinter.format(totpe)}")
+  }
+
+}
diff --git a/effekt/shared/src/main/scala/effekt/core/PrettyPrinter.scala b/effekt/shared/src/main/scala/effekt/core/PrettyPrinter.scala
index e1a91067..83d9cc2c 100644
--- a/effekt/shared/src/main/scala/effekt/core/PrettyPrinter.scala
+++ b/effekt/shared/src/main/scala/effekt/core/PrettyPrinter.scala
@@ -21,6 +21,15 @@ object PrettyPrinter extends ParenPrettyPrinter {
   def format(s: Stmt): String =
     pretty(toDoc(s), 60).layout
 
+  def format(t: ValueType): String =
+    pretty(toDoc(t), 60).layout
+
+  def format(t: BlockType): String =
+    pretty(toDoc(t), 60).layout
+
+  def format(t: Block): String =
+    pretty(toDoc(t), 60).layout
+
   val emptyline: Doc = line <> line
 
   def toDoc(m: ModuleDecl): Doc = {
diff --git a/effekt/shared/src/main/scala/effekt/core/Tree.scala b/effekt/shared/src/main/scala/effekt/core/Tree.scala
index 8efdacd4..fbf61dc1 100644
--- a/effekt/shared/src/main/scala/effekt/core/Tree.scala
+++ b/effekt/shared/src/main/scala/effekt/core/Tree.scala
@@ -313,14 +313,16 @@ object Tree {
   }
 
   class Rewrite extends Structural {
+    def id: PartialFunction[Id, Id] = PartialFunction.empty
     def pure: PartialFunction[Pure, Pure] = PartialFunction.empty
     def expr: PartialFunction[Expr, Expr] = PartialFunction.empty
     def stmt: PartialFunction[Stmt, Stmt] = PartialFunction.empty
     def defn: PartialFunction[Definition, Definition] = PartialFunction.empty
     def block: PartialFunction[Block, Block] = PartialFunction.empty
-
     def handler: PartialFunction[Implementation, Implementation] = PartialFunction.empty
+    def param: PartialFunction[Param, Param] = PartialFunction.empty
 
+    def rewrite(x: Id): Id = if id.isDefinedAt(x) then id(x) else x
     def rewrite(p: Pure): Pure = rewriteStructurally(p, pure)
     def rewrite(e: Expr): Expr = rewriteStructurally(e, expr)
     def rewrite(s: Stmt): Stmt = rewriteStructurally(s, stmt)
@@ -328,6 +330,9 @@ object Tree {
     def rewrite(d: Definition): Definition = rewriteStructurally(d, defn)
     def rewrite(e: Implementation): Implementation = rewriteStructurally(e, handler)
     def rewrite(o: Operation): Operation = rewriteStructurally(o)
+    def rewrite(p: Param): Param = rewriteStructurally(p, param)
+    def rewrite(p: Param.ValueParam): Param.ValueParam = rewrite(p: Param).asInstanceOf[Param.ValueParam]
+    def rewrite(p: Param.BlockParam): Param.BlockParam = rewrite(p: Param).asInstanceOf[Param.BlockParam]
 
     def rewrite(matchClause: (Id, BlockLit)): (Id, BlockLit) = matchClause match {
       case (p, b) => (p, rewrite(b).asInstanceOf[BlockLit])
diff --git a/effekt/shared/src/main/scala/effekt/generator/llvm/Transformer.scala b/effekt/shared/src/main/scala/effekt/generator/llvm/Transformer.scala
index 8518be26..48038c63 100644
--- a/effekt/shared/src/main/scala/effekt/generator/llvm/Transformer.scala
+++ b/effekt/shared/src/main/scala/effekt/generator/llvm/Transformer.scala
@@ -1,6 +1,5 @@
 package effekt.llvm
 
-import scala.collection.mutable
 import effekt.llvm.Operand.LocalReference
 import effekt.machine
 import effekt.machine.analysis.*
@@ -421,24 +420,6 @@ object Transformer {
     }
   }
 
-  def getEraser(environment: machine.Environment)(using C: ModuleContext): Operand = {
-    val types = environment.map{ _.tpe };
-    val freshEnvironment = environment.map{
-      case machine.Variable(name, tpe) => machine.Variable(freshName(name), tpe)
-    };
-    val eraser = ConstantGlobal(eraserType, freshName("eraser"));
-
-    C.erasers.getOrElseUpdate(types, {
-      defineFunction(eraser.name, List(Parameter(envType, "env"))) {
-        // TODO avoid unnecessary loads
-        loadEnvironmentAt(LocalReference(envType, "env"), freshEnvironment);
-        eraseValues(freshEnvironment, Set());
-        RetVoid()
-      };
-      eraser
-    });
-  }
-
   def produceObject(environment: machine.Environment, freeInBody: Set[machine.Variable])(using ModuleContext, FunctionContext, BlockContext): Operand = {
     if (environment.isEmpty) {
       ConstantNull(objType)
@@ -446,7 +427,15 @@ object Transformer {
       val obj = LocalReference(objType, freshName("obj"));
       val env = LocalReference(envType, freshName("env"));
       val size = ConstantInt(environmentSize(environment));
-      val eraser = getEraser(environment)
+      val eraser = ConstantGlobal(eraserType, freshName("eraser"));
+
+      //TODO cache eraser based on environment
+      defineFunction(eraser.name, List(Parameter(envType, "env"))) {
+        // TODO avoid unnecessary loads
+        loadEnvironmentAt(LocalReference(envType, "env"), environment);
+        eraseValues(environment, Set());
+        RetVoid()
+      }
 
       emit(Call(obj.name, objType, newObject, List(eraser, size)));
       emit(Call(env.name, envType, objectEnvironment, List(obj)));
@@ -664,7 +653,6 @@ object Transformer {
   class ModuleContext() {
     var counter = 0;
     var definitions: List[Definition] = List();
-    val erasers = mutable.HashMap[List[machine.Type], Operand]();
   }
 
   def emit(definition: Definition)(using C: ModuleContext) =
diff --git a/effekt/shared/src/main/scala/effekt/machine/Transformer.scala b/effekt/shared/src/main/scala/effekt/machine/Transformer.scala
index ad3227de..a1573bd7 100644
--- a/effekt/shared/src/main/scala/effekt/machine/Transformer.scala
+++ b/effekt/shared/src/main/scala/effekt/machine/Transformer.scala
@@ -123,7 +123,8 @@ object Transformer {
           Clause(List(transform(lifted.ValueParam(id, tpe))), transform(rest)),
             transform(bind)
         )
-      case lifted.App(lifted.BlockVar(id, tpe), List(), args) =>
+      case lifted.App(lifted.BlockVar(id, tpe), targs, args) =>
+        if(targs.exists(requiresBoxing)){ ErrorReporter.abort(s"Types ${targs} are used as type parameters but would require boxing.") }
         // TODO deal with BlockLit
         id match {
           case symbols.UserFunction(_, _, _, _, _, _, _)  | symbols.TmpBlock() =>
@@ -149,7 +150,8 @@ object Transformer {
             ErrorReporter.abort(s"Unsupported blocksymbol: $id")
         }
 
-      case lifted.App(lifted.Member(lifted.BlockVar(id, tpe), op, annotatedTpe), List(), args) =>
+      case lifted.App(lifted.Member(lifted.BlockVar(id, tpe), op, annotatedTpe), targs, args) =>
+        if(targs.exists(requiresBoxing)){ ErrorReporter.abort(s"Types ${targs} are used as type parameters but would require boxing.") }
         val opTag = {
           tpe match
             case core.BlockType.Interface(ifceId, _) =>
@@ -299,7 +301,9 @@ object Transformer {
 
     // hardcoded translation for get and put.
     // TODO remove this when interfaces are correctly translated
-    case lifted.PureApp(lifted.Member(lifted.BlockVar(x, core.BlockType.Interface(_, List(stateType))), TState.get, annotatedTpe), List(), List()) =>
+    case lifted.PureApp(lifted.Member(lifted.BlockVar(x, core.BlockType.Interface(_, List(stateType))), TState.get, annotatedTpe), targs, List()) =>
+      if(targs.exists(requiresBoxing)){ ErrorReporter.abort(s"Types ${targs} are used as type parameters but would require boxing.") }
+
       val tpe = transform(stateType)
       val variable = Variable(freshName("x"), tpe)
       val stateVariable = Variable(transform(x) + "$State", Type.Reference(tpe))
@@ -307,7 +311,9 @@ object Transformer {
         Load(variable, stateVariable, k(variable))
       }
 
-    case lifted.PureApp(lifted.Member(lifted.BlockVar(x, core.BlockType.Interface(_, List(stateType))), TState.put, annotatedTpe), List(), List(arg)) =>
+    case lifted.PureApp(lifted.Member(lifted.BlockVar(x, core.BlockType.Interface(_, List(stateType))), TState.put, annotatedTpe), targs, List(arg)) =>
+      if(targs.exists(requiresBoxing)){ ErrorReporter.abort(s"Types ${targs} are used as type parameters but would require boxing.") }
+
       val tpe = transform(stateType)
       val variable = Variable(freshName("x"), Positive("Unit"));
       val stateVariable = Variable(transform(x) + "$State", Type.Reference(tpe))
@@ -318,7 +324,9 @@ object Transformer {
         }
       }
 
-    case lifted.PureApp(lifted.BlockVar(blockName: symbols.ExternFunction, tpe: core.BlockType.Function), List(), args) =>
+    case lifted.PureApp(lifted.BlockVar(blockName: symbols.ExternFunction, tpe: core.BlockType.Function), targs, args) =>
+      if(targs.exists(requiresBoxing)){ ErrorReporter.abort(s"Types ${targs} are used as type parameters but would require boxing.") }
+
       val variable = Variable(freshName("x"), transform(tpe.result))
       transform(args).flatMap { values =>
         Binding { k =>
@@ -326,8 +334,10 @@ object Transformer {
         }
       }
 
-    case lifted.PureApp(lifted.BlockVar(blockName, tpe: core.BlockType.Function), List(), args)
+    case lifted.PureApp(lifted.BlockVar(blockName, tpe: core.BlockType.Function), targs, args)
     if DeclarationContext.findConstructor(blockName).isDefined =>
+      if(targs.exists(requiresBoxing)){ ErrorReporter.abort(s"Types ${targs} are used as type parameters but would require boxing.") }
+
       val variable = Variable(freshName("x"), transform(tpe.result));
       val tag = DeclarationContext.getConstructorTag(blockName)
 
@@ -395,7 +405,7 @@ object Transformer {
     }
 
   def transform(tpe: core.ValueType)(using ErrorReporter): Type = tpe match {
-    case core.ValueType.Var(name) => ???
+    case core.ValueType.Var(name) => Positive(name.name.name) // assume all value parameters are data
     case core.ValueType.Boxed(tpe, capt) => ???
     case core.ValueType.Data(symbols.builtins.UnitSymbol, Nil) => builtins.UnitType
     case core.ValueType.Data(symbols.builtins.IntSymbol, Nil) => Type.Int()
@@ -414,6 +424,15 @@ object Transformer {
   def transform(id: Symbol): String =
     s"${id.name}_${id.id}"
 
+  def requiresBoxing(tpe: core.ValueType): Boolean = {
+    tpe match
+      case core.ValueType.Var(_) => false // assume by induction all type variables must be data
+      case core.ValueType.Data(_, args) => {
+        args.exists(requiresBoxing)
+      }
+      case _ => true
+  }
+
   def freshName(baseName: String): String = baseName + "_" + symbols.Symbol.fresh.next()
 
   def findToplevelBlocksParams(definitions: List[lifted.Definition])(using BlocksParamsContext, ErrorReporter): Unit =
diff --git a/effekt/shared/src/main/scala/effekt/symbols/symbols.scala b/effekt/shared/src/main/scala/effekt/symbols/symbols.scala
index fc69bd84..73adb2e2 100644
--- a/effekt/shared/src/main/scala/effekt/symbols/symbols.scala
+++ b/effekt/shared/src/main/scala/effekt/symbols/symbols.scala
@@ -58,6 +58,10 @@ case class Module(
     case e: Interface => e
   }
 
+  def findPrelude: Module = {
+    dependencies.find(_.name.name == "effekt").get
+  }
+
   /**
    * It is actually possible, that exports is invoked on a single module multiple times:
    * The dependencies of a module might change, which triggers frontend on the same module
diff --git a/examples/llvm/polymorphic_failtooption.check b/examples/llvm/polymorphic_failtooption.check
new file mode 100644
index 00000000..759a4ba9
--- /dev/null
+++ b/examples/llvm/polymorphic_failtooption.check
@@ -0,0 +1,2 @@
+2
+None
diff --git a/examples/llvm/polymorphic_failtooption.effekt b/examples/llvm/polymorphic_failtooption.effekt
new file mode 100644
index 00000000..d4e81018
--- /dev/null
+++ b/examples/llvm/polymorphic_failtooption.effekt
@@ -0,0 +1,32 @@
+effect Fail(): Unit
+
+type Option[A] {
+    None(); Some(value: A)
+}
+def println(oi: Option[Int]): Unit = {
+    oi match {
+        case None() => println("None")
+        case Some(i) => println(i)
+    }
+}
+
+def runFail[A]{ f : => A / Fail }: Option[A] = {
+    try {
+        Some(f())
+    } with Fail {
+        None()
+    }
+}
+
+def safeDiv(x: Int, y: Int): Int / Fail = {
+    if(y == 0){
+        do Fail(); 0
+    } else {
+        x/y
+    }
+}
+
+def main() = {
+    println(runFail { safeDiv(6,3) })
+    println(runFail { safeDiv(2,0) })
+}
\ No newline at end of file
diff --git a/examples/llvm/polymorphism_blockparams.check b/examples/llvm/polymorphism_blockparams.check
new file mode 100644
index 00000000..7c6ba0fe
--- /dev/null
+++ b/examples/llvm/polymorphism_blockparams.check
@@ -0,0 +1,1 @@
+55
\ No newline at end of file
diff --git a/examples/llvm/polymorphism_blockparams.effekt b/examples/llvm/polymorphism_blockparams.effekt
new file mode 100644
index 00000000..b869db7e
--- /dev/null
+++ b/examples/llvm/polymorphism_blockparams.effekt
@@ -0,0 +1,16 @@
+type List[A] {
+    Nil(); Cons(hd: A, tl: List[A])
+}
+
+def foldr[A,B](lst: List[A], init: B){ f: (A,B) => B }: B = {
+    lst match {
+        case Nil() => init
+        case Cons(hd, tl) => f(hd, foldr(tl, init){f})
+    }
+} 
+
+def main() = {
+    val l = [1,2,3,4,5,6,7,8,9,10]
+    val sum = foldr(l, 0){(x,y) => x + y}
+    println(sum)
+}
\ No newline at end of file
diff --git a/examples/llvm/polymorphism_data.check b/examples/llvm/polymorphism_data.check
new file mode 100644
index 00000000..dd7e60e3
--- /dev/null
+++ b/examples/llvm/polymorphism_data.check
@@ -0,0 +1,1 @@
+[12, 4]
diff --git a/examples/llvm/polymorphism_data.effekt b/examples/llvm/polymorphism_data.effekt
new file mode 100644
index 00000000..b88caf85
--- /dev/null
+++ b/examples/llvm/polymorphism_data.effekt
@@ -0,0 +1,65 @@
+type Integer {
+   InjInt(x: Int)
+}
+
+type List[A] {
+  Nil(); Cons(a: A, tail: List[A])
+}
+
+def map[A,B](l: List[A]){ f: A => B }: List[B] = {
+  l match {
+    case Nil() => Nil()
+    case Cons(hd, tl) => Cons(f(hd), map(tl){f})
+  }
+}
+
+def show(i: Int): String = {
+  def impl_digit(i: Int): String = {
+    if(i==0){"0"} else
+    if(i==1){"1"} else
+    if(i==2){"2"} else
+    if(i==3){"3"} else
+    if(i==4){"4"} else
+    if(i==5){"5"} else
+    if(i==6){"6"} else
+    if(i==7){"7"} else
+    if(i==8){"8"} else
+    if(i==9){"9"} else
+    "?"
+  }
+  def impl(i: Int): String = {
+    if(i<10){impl_digit(i)}else{
+      impl(i/10) + impl_digit(mod(i,10))
+    }
+  }
+  if(i==0) {
+    "0"
+  } else {
+    impl(i)
+  }
+}
+def show(i: Integer): String = {
+  i match {
+    case InjInt(j) => show(j)
+  }
+}
+
+def show(l: List[Integer]): String = {
+  def impl(t: List[Integer]): String = {
+    t match {
+      case Nil() => "]"
+      case Cons(hd, tl) => ", " + show(hd) + impl(tl)
+    }
+  }
+
+  l match {
+    case Nil() => "[]"
+    case Cons(hd,tl) => "[" + show(hd) +impl(tl)
+  }
+}
+
+def main(): Unit = {
+  val x = [InjInt(12), InjInt(4)]
+  val y = map(x){ x => x }
+  println(show(y))
+}
diff --git a/examples/llvm/polymorphism_int.check b/examples/llvm/polymorphism_int.check
new file mode 100644
index 00000000..d8263ee9
--- /dev/null
+++ b/examples/llvm/polymorphism_int.check
@@ -0,0 +1,1 @@
+2
\ No newline at end of file
diff --git a/examples/llvm/polymorphism_int.effekt b/examples/llvm/polymorphism_int.effekt
new file mode 100644
index 00000000..292f2257
--- /dev/null
+++ b/examples/llvm/polymorphism_int.effekt
@@ -0,0 +1,7 @@
+def id[A](a: A): A = a
+
+def main() = {
+    val x = 2
+    val y = id(x)
+    println(y)
+}
\ No newline at end of file
diff --git a/examples/llvm/polymorphism_map.check b/examples/llvm/polymorphism_map.check
new file mode 100644
index 00000000..335cf4a4
--- /dev/null
+++ b/examples/llvm/polymorphism_map.check
@@ -0,0 +1,5 @@
+1
+4
+9
+16
+25
diff --git a/examples/llvm/polymorphism_map.effekt b/examples/llvm/polymorphism_map.effekt
new file mode 100644
index 00000000..9505a923
--- /dev/null
+++ b/examples/llvm/polymorphism_map.effekt
@@ -0,0 +1,16 @@
+type List[A] {
+    Nil(); Cons(hd: A, tl: List[A])
+}
+
+def map[A,B](lst: List[A]){f: A => B}: List[B] = {
+    lst match {
+        case Nil() => Nil()
+        case Cons(hd, tl) => Cons(f(hd), map(tl){f})
+    }
+}
+
+def main() = {
+    val values = [1,2,3,4,5]
+    val squares = map(values){ n => n * n }
+    map(squares){ n => println(n) }
+}
\ No newline at end of file
diff --git a/libraries/llvm/effekt.effekt b/libraries/llvm/effekt.effekt
index 9836e233..3e16d44a 100644
--- a/libraries/llvm/effekt.effekt
+++ b/libraries/llvm/effekt.effekt
@@ -158,3 +158,9 @@ extern pure def infixAnd(adt_p: Boolean, adt_q: Boolean): Boolean = """
     %adt_r = insertvalue %Pos zeroinitializer, i64 %r, 0
     ret %Pos %adt_r
 """
+
+// For boxing polymorphic values
+record BoxedUnit(unboxUnit: Unit)
+record BoxedInt(unboxInt: Int)
+record BoxedDouble(unboxDouble: Double)
+record BoxedString(unboxString: String)


Test patch:
diff --git a/effekt/jvm/src/test/scala/effekt/LLVMTests.scala b/effekt/jvm/src/test/scala/effekt/LLVMTests.scala
index 66282d46..59dd41a7 100644
--- a/effekt/jvm/src/test/scala/effekt/LLVMTests.scala
+++ b/effekt/jvm/src/test/scala/effekt/LLVMTests.scala
@@ -21,24 +21,11 @@ class LLVMTests extends EffektTests {
     examplesDir / "pos" / "builtins.effekt",
     examplesDir / "pos" / "namespaces.effekt",
     examplesDir / "pos" / "triples.effekt",
+    examplesDir / "pos" / "either.effekt",
 
     // missing dealiasing of `def f = g`
     examplesDir / "pos" / "defdef.effekt",
 
-    // missing multiple operations (zero to be precise)
-    examplesDir / "pos" / "effectalias.effekt",
-
-    // type polymorphic data types
-    examplesDir / "pos" / "effectalias.effekt",
-    examplesDir / "pos" / "emptymatch.effekt",
-    examplesDir / "pos" / "either.effekt",
-    examplesDir / "pos" / "matching.effekt",
-
-    // type polymorphic functions
-    examplesDir / "pos" / "infer" / "infer_handler.effekt",
-    examplesDir / "pos" / "poly1.effekt",
-    examplesDir / "pos" / "imports.effekt",
-
     // option
     examplesDir / "pos" / "raytracer.effekt",
 
@@ -50,7 +37,6 @@ class LLVMTests extends EffektTests {
     examplesDir / "pos" / "overloading.effekt",
     examplesDir / "pos" / "matchblock.effekt",
     examplesDir / "pos" / "sideeffects.effekt",
-    examplesDir / "pos" / "lists.effekt",
 
     // arrays
     examplesDir / "pos" / "arrays.effekt",
@@ -68,17 +54,25 @@ class LLVMTests extends EffektTests {
 
     // holes
     examplesDir / "pos" / "infer" / "infer_blockvars.effekt",
+    examplesDir / "pos" / "emptymatch.effekt",
 
     // multi handlers
     examplesDir / "pos" / "multihandler.effekt",
     examplesDir / "pos" / "multieffects.effekt",
 
+    // multiple methods
+    examplesDir / "pos" / "effectalias.effekt",
+
     // toplevel def and let bindings
     examplesDir / "pos" / "toplevelval.effekt",
 
     // foreign functions with block arguments
     examplesDir / "pos" / "liftinference.effekt",
 
+    // probably issue 207
+    examplesDir / "pos" / "stream_push.effekt",
+    examplesDir / "pos" / "matching.effekt",
+
     // others
     examplesDir / "pos" / "issue108.effekt",
     examplesDir / "pos" / "propagators.effekt",
@@ -90,6 +84,9 @@ class LLVMTests extends EffektTests {
     examplesDir / "pos" / "mutualrecursion.effekt",
     examplesDir / "pos" / "multiline_extern_definition.effekt",
     examplesDir / "pos" / "maps.effekt",
+    examplesDir / "pos" / "state.effekt",
+    examplesDir / "pos" / "bug1.effekt",
+
 
     // whole folders
     examplesDir / "pos" / "bidirectional",
@@ -104,9 +101,8 @@ class LLVMTests extends EffektTests {
     // computes the wrong results
     examplesDir / "llvm" / "nested.effekt",
 
-    // polymorphic effect operations not supported, yet
-    examplesDir / "llvm" / "choice.effekt",
-    examplesDir / "llvm" / "triples.effekt",
+    // Issue #207
+    examplesDir / "llvm" / "polymorphism_blockparams.effekt",
   )
 
   def runTestFor(input: File, check: File, expected: String): Unit = {
diff --git a/effekt/jvm/src/test/scala/effekt/PolymorphismBoxingTests.scala b/effekt/jvm/src/test/scala/effekt/PolymorphismBoxingTests.scala
new file mode 100644
index 00000000..c8beb94f
--- /dev/null
+++ b/effekt/jvm/src/test/scala/effekt/PolymorphismBoxingTests.scala
@@ -0,0 +1,270 @@
+package effekt
+
+import java.io.File
+import effekt.core.{Block, Definition, DirectApp, PolymorphismBoxing, Pure, Run, Stmt}
+import effekt.context.Context
+import effekt.source.{IdDef, Import, ModuleDecl}
+import kiama.{parsing, util}
+import effekt.symbols.{Module, Name, TypeConstructor, TypeSymbol, ValueSymbol, ValueType}
+import effekt.source
+import effekt.util.messages
+import effekt.util.messages.DebugMessaging
+import kiama.parsing.{Failure, NoSuccess, Success}
+import kiama.util.Severities
+
+abstract class AbstractPolymorphismBoxingTests extends munit.FunSuite {
+
+  def boxDef(tpe: ValueType.ValueTypeApp): List[symbols.Symbol] = {
+    val tpeCns: symbols.TypeConstructor.Record =
+      symbols.TypeConstructor.Record(symbols.LocalName("Boxed" ++ tpe.constructor.name.name), List(), null)
+    tpeCns.constructor =
+      symbols.Constructor(symbols.LocalName("MkBoxed" ++ tpe.constructor.name.name), List(), null, tpeCns)
+    tpeCns.constructor.fields = List(
+      symbols.Field(symbols.LocalName("unbox" ++ tpe.constructor.name.name),
+        symbols.ValueParam(symbols.LocalName("value"), Some(tpe)), tpeCns.constructor))
+    List(tpeCns, tpeCns.constructor, tpeCns.constructor.fields.head)
+  }
+
+  val boxtpes = symbols.builtins.rootTypes.values.flatMap {
+    case t: TypeConstructor.ExternType => boxDef(ValueType.ValueTypeApp(t, List()))
+    case _ => Nil
+  }.map { c => (c.name.name, c) }.toMap
+
+  /** Mock context for Polymorphism boxing.
+   * Only implements what is actually used by [[core.PolymorphismBoxing]]
+   */
+  object context extends Context(new util.Positions()) {
+    this.module = new Module(ModuleDecl("test", List(Import("effekt")), List()), util.StringSource("", "test")) {
+      override def findPrelude: Module = new Module(ModuleDecl("effekt", List(), List()), util.StringSource("", "effekt")) {
+        override def types: Map[String, TypeSymbol] = boxtpes.collect[String, symbols.TypeSymbol]{
+          case (k,t: symbols.TypeSymbol) => (k,t)
+        }
+      }
+    }
+
+    object messaging extends DebugMessaging
+
+    def contentsOf(path: String): Option[String] = None
+
+    def findSource(path: String): Option[kiama.util.Source] = None
+  }
+
+  val names = new core.Names(boxtpes ++
+    symbols.builtins.rootTypes ++ Map(
+    // TODO maybe add used names
+  ))
+
+  class Renamer(names: core.Names, prefix: String = "l") extends core.Tree.Rewrite {
+    var bound: List[symbols.Symbol] = Nil
+    def withBindings[R](ids: List[symbols.Symbol])( f: => R ): R = {
+      val oldBound = bound
+      bound = ids ++ bound
+      val res = f
+      bound = oldBound
+      res
+    }
+    def withBinding[R](id: symbols.Symbol)( f: => R ): R = withBindings(List(id))(f)
+
+    override def id: PartialFunction[core.Id, core.Id] = { id =>
+      if (bound.contains(id)) {
+        names.idFor(prefix ++ (bound.length - bound.indexOf(id)).toString)
+      } else id
+    }
+
+    override def stmt: PartialFunction[Stmt, Stmt] = {
+      case core.Scope(definitions, rest) => withBindings(definitions.map{
+          case core.Definition.Def(id, _) => id
+          case core.Definition.Let(id, _) => id
+        }){
+        core.Scope(definitions map rewrite, rewrite(rest))
+      }
+      case core.Val(id, binding, body) => withBinding(id){
+        core.Val(rewrite(id), rewrite(binding), rewrite(body))
+      }
+      case core.State(id, init, reg, body) => withBinding(id){
+        core.State(rewrite(id), rewrite(init), rewrite(reg), rewrite(body))
+      }
+    }
+    override def block: PartialFunction[Block, Block] = {
+      case Block.BlockLit(tparams, cparams, vparams, bparams, body) =>
+        withBindings(cparams ++ vparams.map(_.id) ++ bparams.map(_.id)){
+          Block.BlockLit(tparams, cparams map rewrite, vparams map rewrite, bparams map rewrite,
+            rewrite(body))
+        }
+    }
+
+    def apply(m: core.ModuleDecl): core.ModuleDecl = m match {
+      case core.ModuleDecl(path, imports, declarations, externs, definitions, exports) =>
+        core.ModuleDecl(path, imports, declarations, externs, definitions map rewrite, exports)
+    }
+  }
+
+  def assertTransformsTo(input: String, expected: String): Unit = {
+    val pInput = core.CoreParsers.module(input, names) match {
+      case Success(result, next) => result
+      case nosuccess: NoSuccess => fail(nosuccess.toMessage)
+    }
+    val pExpected = core.CoreParsers.module(expected, names) match {
+      case Success(result, next) => result
+      case nosuccess: NoSuccess => fail(nosuccess.toMessage)
+    }
+    given core.PolymorphismBoxing.PContext = new PolymorphismBoxing.PContext(List())(using context)
+    val got = PolymorphismBoxing.transform(pInput)
+    val renamer: Renamer = Renamer(names)
+    assertEquals(renamer(got), renamer(pExpected))
+  }
+}
+class PolymorphismBoxingTests extends AbstractPolymorphismBoxingTests {
+
+  test("simple non-polymorphic code should stay the same"){
+    val code =
+      """module main
+        |
+        |extern {} def bar() {f@f: MyInterface}: Foo at {f} = "my decl"
+        |extern {} def bar() {g: MyInterface}: Foo at {g} = "my decl"
+        |
+        |def prim = { () => return 42 }
+        |def union = { () => if (true) (f: () => Int @ {f})() else (g: () => Unit @ {g})() }
+        |def main = { () => return () }
+        |
+        |export prim
+        |""".stripMargin
+    assertTransformsTo(code, code)
+  }
+
+  test("if only data types are used, code should stay the same"){
+    val code =
+      """module main
+        |
+        |type Foo { X() B() }
+        |
+        |def baz = { ['b](){ f@f: MyInterface } => (f: () => Unit @ {})() }
+        |def bar = { ['b](){ f@f: MyInterface } => return box {f} (f : MyInterface @ {f}) }
+        |def id = { ['A](a: 'A) => return a: 'A }
+        |
+        |def returnA = { () => return (id: ['A]('A) => 'A @ {})[Foo]((X: () => Foo @ {})()) }
+        |def pReturnA = { ['B](b: 'B) => return (id: ['A]('A) => 'A @ {})['A](b: 'B) }
+        |
+        |""".stripMargin
+    assertTransformsTo(code,code)
+  }
+
+  test("simple PureApp with int gets wrapped"){
+    val from =
+      """module main
+        |
+        |def id = { ['A](a: 'A) => return a: 'A }
+        |def idInt = { (x: Int) => return (id: ['A]('A) => 'A @ {})[Int](x: Int) }
+        |""".stripMargin
+    val to =
+      """module main
+        |
+        |def id = { ['A](a: 'A) => return a: 'A }
+        |def idInt = { (x: Int) => return (id: ['A]('A) => 'A @ {})[BoxedInt]((MkBoxedInt: (Int) => BoxedInt @ {})(x: Int)).unboxInt: Int }
+        |""".stripMargin
+    assertTransformsTo(from, to)
+  }
+
+  test("simple App with int gets wrapped"){
+    val from =
+      """module main
+        |
+        |def id = { ['A](a: 'A) => return a: 'A }
+        |def idInt = { (x: Int) => (id: ['A]('A) => 'A @ {})[Int](x: Int) }
+        |""".stripMargin
+    val to =
+      """module main
+        |
+        |def id = { ['A](a: 'A) => return a: 'A }
+        |def idInt = { (x: Int) => val tmp = (id: ['A]('A) => 'A @ {})[BoxedInt]((MkBoxedInt: (Int) => BoxedInt @ {})(x: Int)) ; return tmp:BoxedInt.unboxInt: Int }
+        |""".stripMargin
+    assertTransformsTo(from, to)
+  }
+
+  test("DirectApp with [Int] gets wrapped correctly"){
+    val from =
+      """module main
+        |
+        |def id = { ['A](a: 'A) => return a: 'A }
+        |def idInt = { (x: Int) =>
+        |    {
+        |        let res = !(id: ['A]('A) => 'A @ {})[Int](x: Int)
+        |        return res: Int
+        |    }
+        |}
+        |""".stripMargin
+    val to =
+      """module main
+        |
+        |def id = { ['A](a: 'A) => return a: 'A }
+        |def idInt = { (x: Int) =>
+        |    {
+        |        let res = run {
+        |            let boxedRes = !(id: ['A]('A) => 'A @ {})[BoxedInt]((MkBoxedInt: (Int) => BoxedInt @ {})(x: Int))
+        |            return boxedRes:BoxedInt.unboxInt: Int
+        |        }
+        |        return res: Int
+        |    }
+        |}
+        |""".stripMargin
+    assertTransformsTo(from,to)
+  }
+
+  test("block parameters get wrapped \"inversely\""){
+    val from =
+      """module main
+        |def test = { () =>
+        |    (hof: ['A](){ b : ('A) => 'A } => 'A @ {} )[Int](){ (x: Int) => return x: Int }
+        |}
+        |""".stripMargin
+    val to =
+      """module main
+        |def test = { () =>
+        |    val r = (hof: ['A](){ b : ('A) => 'A } => 'A @ {} )[BoxedInt](){ (boxedX: BoxedInt) =>
+        |      {
+        |         def originalFn = { (x: Int) => return x: Int }
+        |         val result = (originalFn: (Int) => Int @ {})(boxedX: BoxedInt.unboxInt: Int);
+        |         return (MkBoxedInt: (Int) => BoxedInt @ {})(result: Int)
+        |      }
+        |    };
+        |    return r:BoxedInt.unboxInt: Int
+        |}
+        |""".stripMargin
+    assertTransformsTo(from, to)
+  }
+
+  test("higher higher order functions get wrapped correctly"){
+    val from =
+      """module main
+        |
+        |def hhof_caller = { () =>
+        |    (hhof: ['A](){ b: (){ hhofarg: ('A) => 'A } => 'A } => 'A @ {})[Int](){
+        |        (){ hhofarg: (Int) => Int } => (hhofarg: (Int) => Int @ {})(5)
+        |    }
+        |}
+        |""".stripMargin
+    val to =
+      """module main
+        |
+        |def hhof_caller = { () =>
+        |    val result = (hhof: ['A](){ b: (){ hhofarg: ('A) => 'A } => 'A } => 'A @ {})[BoxedInt](){
+        |        (){ hhofargB: ('A) => 'A } =>
+        |          {
+        |              def originalFn = { (){ hhofarg: (Int) => Int } => (hhofarg: (Int) => Int @ {})(5) }
+        |              val res = (originalFn: (){ hhofarg: (Int) => Int } => Int @ {})(){
+        |                  (hhofargarg: Int) =>
+        |                      {
+        |                        def tmp = hhofargB: ('A) => 'A @ {}
+        |                        val rres = (tmp: ('A) => 'A @ {})((MkBoxedInt: (Int) => BoxedInt @ {})(hhofargarg: Int));
+        |                        return rres:BoxedInt.unboxInt: Int
+        |                      }
+        |              };
+        |              return (MkBoxedInt: (Int) => BoxedInt @ {})(res:Int)
+        |          }
+        |    };
+        |    return result:BoxedInt.unboxInt: Int
+        |}
+        |""".stripMargin
+    assertTransformsTo(from, to)
+  }
+}
\ No newline at end of file