xacid

https://infoscience.epfl.ch/record/264990/files/Staged%20Tagless%20Interpreters%20in%20Dotty.pdf

Staging allows us to do execution-time optimization while tagless eliminates tagging overhead. Jacques Carette, Oleg Kiselyov and Chung-chieh Shan wrote staged tagless interpreters in OCaml and Haskell [1].

The goal of this work is to port the ideas of embedding domain-specific languages using tagless interpreters in Scala. Before, it was not possible to implement these types of interpreters in vanilla Scala since the necessary staging capabilities arrived with Dotty.

https://github.com/lampepfl/dotty/blob/master/tests/run/polymorphic-functions.scala

  type F0 = [T] => List[T] => Option[T]
  type F1 = [F[_], G[_], T] => (F[T], F[T] => G[T]) => G[T]
  type F11 = [F[_[_]], G[_[_]], T[_]] => (F[T], [U[_]] => F[U] => G[U]) => G[T]
  type F2 = [T, U] => (T, U) => Either[T, U]

  val t0 = [T] => (ts: List[T]) => ts.headOption
  val t0a: F0 = t0
  assert(t0(List(1, 2, 3)) == Some(1))

  val t1 = [F[_], G[_], T] => (ft: F[T], f: F[T] => G[T]) => f(ft)
  val t1a: F1 = t1
  assert(t1(List(1, 2, 3), (ts: List[Int]) => ts.headOption) == Some(1))

  val t11 = [F[_[_]], G[_[_]], T[_]] => (fl: F[T], f: [U[_]] => F[U] => G[U]) => f(fl)
  val t11a: F11 = t11
  case class C11[F[_]](is: F[Int])
  case class D11[F[_]](is: F[Int])
  assert(t11[F = C11](C11(List(1, 2, 3)), [U[_]] => (c: C11[U]) => D11(c.is)) == D11(List(1, 2, 3)))

import scala.util.control.TailCalls._

inline def[A, B, C] (f: A => B) >>> (g: B => C): A => C = f andThen g

type ->>[A, B] = A => TailRec[B]

inline def[A, B, C] (f: A ->> B) >>> (g: B ->> C): A ->> C = f (_) flatMap g

type Cont[A, S, R] = (A ->> S) ->> R

inline def[A, S, R] (c: Cont[A, S, R] ) $: (A ->> S) ->> R =
  k => tailcall (c (a => tailcall (k (a) ) ) )

inline def pure[A, R] (a: A): Cont[A, R, R] = _ (a)

inline def[A, S, R, B] (c: Cont[A, S, R] ) map (f: A => B): Cont[B, S, R] =
  c flatMap (f >>> (pure (_) ) )

inline def[A, S, R, B, S1] (c: Cont[A, S, R] ) flatMap (f: A => Cont[B, S1, S] ): Cont[B, S1, R] =
  k => c $ (f (_) (k) )

@inline def shift0[A, S, R]: (A ->> S) ->> R => Cont[A, S, R] = identity

inline def reset0[A, R] (k: Cont[A, A, R] ): R = k (done) result

def example (n: Int) = 1 + reset0 (for x <- shift0 (
  (k: Int ->> Int) => (k >>> k) (n) ) yield x + 10)

@main def test = (example >>> println) (100) // 121

https://www.slideshare.net/SanshiroYoshida/extensible-effects-in-dotty

https://dotty.epfl.ch/docs/reference/new-types/match-types.html

Match types have similarities with closed type families in Haskell. Some differences are:

Subtyping instead of type equalities.
Match type reduction does not tighten the underlying constraint, whereas type family reduction does unify. This difference in approach mirrors the difference between local type inference in Scala and global type inference in Haskell.
No a-priori requirement that cases are non-overlapping. Uses parallel reduction instead of always chosing a unique branch.

по мотивам https://xacid.dreamwidth.org/70479.html где я недоумевал по поводу отсутсвия в дотти синт-сахара для полиморфных лямбд и вобще функций первого класса - кажется до них таки это доперло

https://github.com/lampepfl/dotty/pull/4672

теперь в дотти будут (уже замержили в мастер) такие полиморфные лямбды

// Polymorphic idenity
val pid = [T] => (t: T) => t

// Function with poly function argument
val mf = (f: [U] => U => U, t: Int) => f(t)
val mf0 = mf(pid, 23)

https://infoscience.epfl.ch/record/229878/files/simplicitly_1.pdf

includes examples for final tagless & free monads

https://gist.github.com/OlivierBlanvillain/48bb5c66dbb0557da50465809564ee80

Поиграл немного с недавней 0.2.0-RC1 dotty и кроме того что там еще всё сыро (это конечно ожидаемо) обнаружил еще один для меня лично достаточно неприятный факт который можно проиллюстрировать вот этой ссылкой

https://github.com/lampepfl/dotty/issues/2500

Проблема заключается в том что несмотря на то что в дотти уже реализованно частичное применение типов и даже на первый взгляд вроде бы нормальные лямбды на уровне типов (в дотти это одно и то же, кстати Одерский на эту тему написал целый пейпер) , практическое применение этой привлекательной и потенциально полезной возможности остается по большей части не ясным по причине все еще отсутствия в дотти нормальных же полиморфных значений с квантификатором forAll, а при попытке какого либо использования частично примененного типа или его лямбды компилятор начинает либо требовать полного применения типа либо просто жалуется что не найден параметр типа. Выше ссылка на предложение таки добавить логичное forAll чтобы это начало нормально работать однако не заметно чтобы это предложение нашло поддержку со стороны Одерского и судя по всему нет уверенности что таки это както решится (хотя конечно хочется в это верить). А жаль :(

С другой стороны конечно я возможно чего нибудь пока не понимаю в этом вопросе :)

S	M	T	W	T	F	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Entries tagged with dotty

Staged Tagless Interpreters in Dotty

Dotty first class polymorphic functions

Dotty cps tc

Extensible Effects in Dotty

Dotty match types (closed type families)

Лёд тронулся

Implicit types (dotty)

Dotty / Scala 3.0 forAll

Profile

April 2021

Syndicate

Most Popular Tags

Page Summary

Style Credit

Expand Cut Tags