클래스의 캡처 검사

클래스의 캡처 검사 (Capture Checking of Classes)

소개

클로저에 대한 캡처 검사 원칙은 클래스에도 적용돼요. 예를 들어 다음을 생각해볼게요.

출처: Scala 3 Reference

본문

import language.experimental.captureChecking
import caps.*
class FileSystem extends SharedCapability
class Logger(using fs: FileSystem):
  def log(s: String): Unit =
    val _ = summon[FileSystem]
    ()

def test(xfs: FileSystem): Logger^{xfs} =
  Logger(using xfs)

여기서 클래스 Logger는 역량 fs를 (private) 필드로 보존해요. 따라서 test의 결과는 Logger^{xfs} 타입이에요.

때로는 추적되는 역량이 클래스의 생성자에서만 쓰이고, 필드로 보존되지는 않도록 의도할 때가 있어요. 이 사실은 파라미터를 @constructorOnly로 선언하면 캡처 검사기에 알릴 수 있어요. 예시:

import language.experimental.captureChecking
import caps.*
class FileSystem extends SharedCapability
import scala.annotation.constructorOnly

class NullLogger(using @constructorOnly fs: FileSystem):
  summon[FileSystem] match
    case _ => ()
def test2(using fs: FileSystem): NullLogger = NullLogger() // OK

클래스의 캡처된 참조에는 지역 역량(local capabilities)과 인자 역량(argument capabilities)이 포함돼요. 지역 역량은 클래스 밖에서 정의되고 클래스 본문에서 참조되는 역량이에요. 인자 역량은 클래스의 일차 생성자에 파라미터로 전달돼요. 지역 역량은 상속돼요: 슈퍼클래스의 지역 역량은 그 서브클래스의 지역 역량이기도 해요. 예시:

import language.experimental.captureChecking
import caps.*
class Cap extends caps.SharedCapability

def test(a: Cap, b: Cap, c: Cap): Object^{a, b, c} =
  class Super(y: Cap):
    def f = a
  class Sub(x: Cap) extends Super(x):
    def g = b
  Sub(c)

여기서 클래스 Super는 지역 역량 a를 갖는데, 이는 클래스 Sub에 상속되어 Sub 자신의 지역 역량 b와 합쳐져요. 클래스 Sub는 또한 파라미터 x에 대응하는 인자 역량을 가져요. 이 역량은 마지막 생성자 호출 Sub(c)에서 c로 인스턴스화돼요. 따라서 그 호출의 캡처 집합은 {a, b, c}예요.

This의 캡처 집합

클래스의 this 타입의 캡처 집합은 다음 같은 self-type 어노테이션으로 타입이 명시적으로 선언되지 않는 한 캡처 검사기가 추론해요.

class C:
  self: D^{a, b} => ...

그 추론은 다음 제약들을 관찰해요.

• 클래스 C의 this 타입은 C의 모든 캡처된 참조를 포함해요.
• 클래스 C의 this 타입은 C의 각 부모 클래스의 this 타입의 하위 타입이에요.
• this 타입은 this가 사용되는 모든 제약을 관찰해야 해요.

예를 들어 다음에서

import language.experimental.captureChecking
import caps.*
class Cap extends caps.SharedCapability
def test(c: Cap) =
  class A:
    val x: A = this
    def f = println(c)  // error

this가 타입 A를 가진 val의 오른쪽이므로 this의 타입이 순수해야 한다는 것을 알 수 있어요. 하지만 마지막 줄에서 클래스의 캡처 집합이, 그리고 그것과 함께 this의 캡처 집합이 c를 포함하게 될 것임을 발견해요. 이것은 모순으로 이어지고, 따라서 검사 오류가 생겨요.

   |    def f = println(c)  // error
   |                    ^
   |              Reference `c` is not included in the allowed capture set 's1
   |              of the enclosing class A.

트레이트와 오픈 클래스

self-type 추론은 클래스의 모든 서브클래스가 알려져 있는지에 따라 다르게 동작해요. 일반(오픈도 추상도 아닌) 클래스의 경우 모든 서브클래스가 컴파일 타임에 알려지므로, 캡처 검사기가 self-type을 정확히 추론할 수 있어요.¹ 그러나 트레이트, 추상 클래스, open 클래스의 경우 임의의 서브클래스가 존재할 수 있으므로, 캡처 검사기는 this가 임의의 역량을 캡처할 수 있다고 보수적으로 가정해요(즉 보편 캡처 집합 any를 추론해요).

¹여기서는 오픈이 아닌 클래스가 다른 컴파일 단위에 서브클래스를 가질 가능성(예: 테스트)을 무시하고, 그런 서브클래스들이 추론된 self-type을 바꾸지 않는다고 가정해요.

예를 들어(모든 정의가 같은 파일에 있다고 가정):

import language.experimental.captureChecking
import caps.*
class A:
  def fn: A = this   // ok

trait B:
  def fn: B = this   // error
  def fn2: B^ = this // ok

abstract class C:
  def fn: C = this   // error
  def fn2: C^ = this // ok

sealed abstract class D:
  def fn: D = this   // ok

object D0 extends D

open class E:
  def fn: E = this   // error
  def fn2: E^ = this // ok

상속

클래스나 트레이트의 this 캡처 집합은 확장 클래스들의 가능한 캡처 집합들의 상한으로도 기능해요.

import language.experimental.captureChecking
import caps.*
class CapA extends SharedCapability
class CapB extends SharedCapability
class IO extends SharedCapability

val a: CapA^ = CapA()
val b: CapB^ = CapB()
val io: IO^ = new IO()
abstract class Root:
  this: Root^ => // the default, can capture anything

abstract class Sub extends Root:
  this: Sub^{a, b} => // ok, refinement {a, b} <: {any}

class SubGood extends Sub:
  val fld: AnyRef^{a} = a // ok, {a} included in {a, b}

class SubBad extends Sub: // error, inherited self type does not admit {io}
  val fld: IO^{io} = io

class SubBad2 extends Sub: // error, self type SubBad2^{io} does not conform to Sub^{a, b}
  this: SubBad2^{io} =>

일반적으로 클래스 계층을 올라갈수록 클래스의 this 캡처 집합은 더 허용적/불순해지고(계층을 내려가면 더 제한적/순수해지고), 그래요. 예를 들어 Scala 3의 최상위 참조 타입 AnyRef/Object는 개념적으로 보편 역량을 가져요.

class AnyRef:
  this: AnyRef^ =>
  // ...

마찬가지로 순수한 Iterator는 불순한 것의 하위 타입이에요.

캡처 터널링 (Capture Tunneling)

Pair 클래스의 다음 간단한 정의를 생각해볼게요.

import language.experimental.captureChecking
import caps.*
class Pair[+A, +B](x: A, y: B):
  def fst: A = x
  def snd: B = y

Pair가 이렇게 인스턴스화되면 어떻게 될까요 (ct와 fs가 스코프에 있는 두 역량이라고 가정)?

def x: Int ->{ct} String
def y: Logger^{fs}
def p = Pair(x, y)

마지막 줄은 다음과 같이 타입이 붙어요.

import language.experimental.captureChecking
import caps.*
class Pair[+A, +B](x: A, y: B):
  def fst: A = x
  def snd: B = y
import language.experimental.captureChecking
import caps.*
class FileSystem extends SharedCapability
class Ct extends SharedCapability

class Logger(using fs: FileSystem):
  def log(s: String): Unit =
    val _ = summon[FileSystem]

val ct: Ct = Ct()
val fs: FileSystem = FileSystem()
def x: Int ->{ct} String = _.toString
def y: Logger^{fs} = Logger(using fs)
def p: Pair[Int ->{ct} String, Logger^{fs}] = Pair(x, y)

이것은 놀랍게 보일 수 있어요. Pair(x, y) 값은 확실히 역량 ct와 fs를 캡처하는데, 왜 그것들이 바깥에서 타입에 드러나지 않을까요?

답은 캡처 터널링(capture tunneling)이에요. 타입 변수가 캡처 타입으로 인스턴스화되면, 그 지점을 넘어 캡처가 전파되지 않아요. 반면 타입 변수가 접근 시 다시 인스턴스화되면 캡처 정보가 "다시 튀어나와요". 예를 들어 p가 캡처 집합이 비어 있어 기술적으로 순수하더라도, p.fst를 쓰면 캡처된 역량 ct에 대한 참조가 기록돼요. 그래서 이 접근이 클로저에 들어가면 그 역량은 다시 외부 캡처 집합의 일부가 돼요. 예:

import language.experimental.captureChecking
import caps.*
class Pair[+A, +B](x: A, y: B):
  def fst: A = x
  def snd: B = y
import language.experimental.captureChecking
import caps.*
class FileSystem extends SharedCapability
class Ct extends SharedCapability

class Logger(using fs: FileSystem):
  def log(s: String): Unit =
    val _ = summon[FileSystem]

val ct: Ct = Ct()
val fs: FileSystem = FileSystem()
def x: Int ->{ct} String = _.toString
def y: Logger^{fs} = Logger(using fs)
def p: Pair[Int ->{ct} String, Logger^{fs}] = Pair(x, y)
val f: () ->{ct} Int ->{ct} String = () => p.fst

다시 말해 역량에 대한 참조는 생성에서 접근까지 제네릭 인스턴스화를 "터널로 통과"해요. 그것들은 감싸는 제네릭 데이터 생성자 적용의 캡처 집합에는 영향을 주지 않아요. 이 원칙은 캡처 검사를 간결하고 실용적으로 만드는 데 중요한 역할을 해요.

new의 캡처

환경에 역량 io, async, out이 있다고 가정하고 다음 클래스를 생각해볼게요.

import language.experimental.captureChecking
import caps.*
object io extends SharedCapability
object out extends SharedCapability:
  def println(s: String): Unit = ()

class File:
  def write(s: String): Unit = ()
object File:
  def apply(): File^{io} = new File
def test(): Unit = {
class C(x: () => Unit):
  val f: File^{io} = File()
  def g() =
    out.println("one")
    f.write("two")
    x()
  class Async extends SharedCapability
  val async: Async^ = Async()
  val y: () ->{async} Unit = () => ()
  val _ = C(y)
  ()
}

y가 타입 () ->{async} Unit을 가진다고 가정할 때, 클래스 생성 표현식 C(y)의 캡처 집합은 무엇일까요? 이 캡처 집합은 지역 요소와 외부 요소로부터 계산돼요. 지역 요소는 다음과 같아요.

• 파라미터로 전달된 모든 역량——이 경우 값이면 y 또는 그 기저 역량인 async——그리고
• 클래스 필드 타입의 모든 역량——이 경우 f의 타입에서 오는 io.

외부 요소는 클래스의 메서드가 참조하는 클래스 밖의 모든 역량이에요. 이 경우 외부 요소는 out과 io예요. out은 메서드 g에서 직접 접근돼요. io는 필드 f를 통해 간접적으로 접근돼요.

클래스 캡처 집합의 외부 요소는 uses 절로 명시적으로 선언할 수 있어요.

import language.experimental.captureChecking
import caps.*
object io extends SharedCapability
object out extends SharedCapability:
  def println(s: String): Unit = ()

class File:
  def write(s: String): Unit = ()
object File:
  def apply(): File^{io} = new File
class C(x: () => Unit) uses out, io:
  val f: File^{io} = File()
  def g() =
    out.println("one")
    f.write("two")
    x()
def test(): Unit =
  class Async extends SharedCapability
  val async: Async^ = Async()
  val y: () ->{async} Unit = () => ()
  val _ = C(y)
  ()

다른 컴파일 단위에서 보이는 클래스가 외부 역량을 캡처한다면 uses 절을 반드시 줘야 해요. 이것은 C의 내부를 분석하지 않고 C(...)의 캡처 집합을 알아야 하는 분리 컴파일(separate compilation)을 지원하기 위함이에요.

C가 Capability를 상속하면 new C의 캡처 집합에 항상 any를 추가해요.

import language.experimental.captureChecking
import caps.*
def test() = {
class C extends SharedCapability
val c = C() // `c` has type `C^`
}

any를 캡처하는 필드를 클래스가 가진다면 any도 추가돼요.

import language.experimental.captureChecking
import caps.*
class D extends SharedCapability
def test() = {
class C:
  val x: D^ = D()
val c = C() // `c` has type `C^`
}

any를 캡처하는 필드를 가진 클래스 C가 다른 컴파일 단위에서 보인다면, Capability를 상속해야 해요. 이것은 필드를 스캔할 필요 없이 분리 컴파일에서 new C에 올바른 캡처 집합을 추가하도록 보장해요.

클래스 초기화로 인한 캡처

이전 절은 클래스 인스턴스 생성 표현식의 값이 어떤 역량을 캡처하는지 설명했어요. 하지만 이것이 new와 연결된 유일한 관련 캡처 집합은 아니에요. 클래스가 초기화될 때 어떤 역량이 접근되는지 아는 것도 중요해요.

예를 들어 다음을 생각해볼게요.

import language.experimental.captureChecking
import caps.*
object io extends SharedCapability
object out extends SharedCapability:
  def println(s: String): Unit = ()

class File:
  def write(s: String): Unit = ()
object File:
  def apply(): File^{io} = new File
class D():
  val str: String =
    out.println("str was initialized")
    "abc"
def test(): Unit =
  val _: () ->{out} D = () => D()
  ()

여기서 D의 초기화는 역량 out에 접근해요. 따라서 함수 값 () => D()는 타입 () ->{out} D를 가져요.

클래스 초기화 동안 접근되는 역량은 uses 절에서 각 접근 역량 뒤에 initially를 붙여 선언할 수 있어요.

import language.experimental.captureChecking
import caps.*
object io extends SharedCapability
object out extends SharedCapability:
  def println(s: String): Unit = ()

class File:
  def write(s: String): Unit = ()
object File:
  def apply(): File^{io} = new File
class D() uses out initially:
  val str: String =
    out.println("str was initialized")
    "abc"
def test(): Unit =
  val _: () ->{out} D = () => D()
  ()

클래스가 생성자에서 역량을 초기에 사용하고, 생성된 인스턴스에서 추가로 사용하기 위해 그것도 보존한다면, 그 역량은 uses 절에 두 번 나타나는데, 한 번은 initially와 함께, 한 번은 없이 나타나요.

import language.experimental.captureChecking
import caps.*
object io extends SharedCapability
object out extends SharedCapability:
  def println(s: String): Unit = ()

class File:
  def write(s: String): Unit = ()
object File:
  def apply(): File^{io} = new File
class D() uses out initially, out:
  val str: String =
    out.println("str was initialized")
    "abc"
  def print() = out.println(str)
def test(): Unit =
  val _: () ->{out} D^{out} = () => D()
  ()

다른 컴파일 단위에서 보이는 클래스가 초기화 동안 역량에 접근한다면 uses 절을 반드시 줘야 해요. 일반 uses 절과 마찬가지로, 이것은 클래스의 내부를 분석하지 않고 클래스 인스턴스 생성의 사용 집합을 알아야 하는 분리 컴파일을 지원하기 위함이에요.

Syntax

uses 절은 extends와 derives 절 다음에 온다.

InheritClauses    ::=  [‘extends’ ConstrApps]
                       [‘derives’ QualId {‘,’ QualId}]
                       [‘uses’ UseRef {‘,’ UseRef}]
UseRef            ::=  CaptureRef [‘initially’]

더 큰 예시

더 큰 예시로, 지연 리스트의 구현과 몇 가지 사용 사례를 제시할게요. 단순함을 위해 우리의 리스트는 꼬리 부분에서만 지연돼요. 이것은 Scala-2 타입 Stream이 했던 것과 대응되지만, Scala 3의 LazyList 타입은 첫 번째 인자에서도 지연되므로 엄밀하게는 덜 계산해요.

지연 리스트 버전을 위한 기저 트레이트 LzyList는 다음과 같아요.

import language.experimental.captureChecking
import caps.*
trait LzyList[+A]:
  def isEmpty: Boolean
  def head: A
  def tail: LzyList[A]^{this}

tail이 캡처 어노테이션을 지닌다는 점을 주목하세요. 그것은 지연 리스트의 꼬리가 지연 리스트 전체와 같은 참조들을 캡처할 수 있음을 말해요.

LzyList의 빈 경우(empty case)는 평소처럼 쓰여요.

import language.experimental.captureChecking
import caps.*
trait LzyList[+A]:
  def isEmpty: Boolean
  def head: A
  def tail: LzyList[A]^{this}
object LzyNil extends LzyList[Nothing]:
  def isEmpty = true
  def head = ???
  def tail = ???

지연 cons 노드를 위한 클래스의 공식화는 다음과 같아요.

import language.experimental.captureChecking
import caps.*
trait LzyList[+A]:
  def isEmpty: Boolean
  def head: A
  def tail: LzyList[A]^{this}
object LzyNil extends LzyList[Nothing]:
  def isEmpty = true
  def head = ???
  def tail = ???
import scala.compiletime.uninitialized

final class LzyCons[+A](hd: A, tl: () => LzyList[A]^) extends LzyList[A]:
  private var forced = false
  private var cache: LzyList[A]^{this} = uninitialized
  private def force =
    if !forced then { cache = tl(); forced = true }
    cache

  def isEmpty = false
  def head = hd
  def tail: LzyList[A]^{this} = force
end LzyCons

LzyCons 클래스는 두 파라미터를 받아요: head hd와 LzyList를 돌려주는 함수인 tail tl. 함수와 그 결과 모두 임의의 역량을 캡처할 수 있어요. 함수를 적용한 결과는 private 변경 가능 필드 cache에서 tail을 처음 참조한 뒤 메모이즈돼요. 할당 cache = tl()의 타이핑은 {this} 캡처 집합에 대한 단조성 규칙에 의존한다는 점을 주목하세요.

지연 리스트를 위한 infix cons 연산자 #:를 정의하는 확장 메서드는 다음과 같아요. ::와 유사하지만 엄밀한 리스트 대신 오른쪽 피연산자를 평가하지 않고 지연 리스트를 만들어요.

import language.experimental.captureChecking
import caps.*
trait LzyList[+A]:
  def isEmpty: Boolean
  def head: A
  def tail: LzyList[A]^{this}
object LzyNil extends LzyList[Nothing]:
  def isEmpty = true
  def head = ???
  def tail = ???
import scala.compiletime.uninitialized

final class LzyCons[+A](hd: A, tl: () => LzyList[A]^) extends LzyList[A]:
  private var forced = false
  private var cache: LzyList[A]^{this} = uninitialized
  private def force =
    if !forced then { cache = tl(); forced = true }
    cache

  def isEmpty = false
  def head = hd
  def tail: LzyList[A]^{this} = force
end LzyCons
extension [A](x: A)
  def #:(xs1: => LzyList[A]^): LzyList[A]^{xs1} =
    LzyCons(x, () => xs1)

#:가 오른쪽 인자로 불순한 call-by-name 파라미터 xs1을 받는 점을 주목하세요. #:의 결과는 그 인자를 캡처하는 지연 리스트예요.

#:의 사용 예시로, 주어진 길이의 지연 리스트를 생성자 함수 gen으로 만드는 메서드 tabulate가 있어요. 생성자 함수는 부작용을 가질 수 있어요.

import language.experimental.captureChecking
import caps.*
trait LzyList[+A]:
  def isEmpty: Boolean
  def head: A
  def tail: LzyList[A]^{this}
object LzyNil extends LzyList[Nothing]:
  def isEmpty = true
  def head = ???
  def tail = ???
import scala.compiletime.uninitialized

final class LzyCons[+A](hd: A, tl: () => LzyList[A]^) extends LzyList[A]:
  private var forced = false
  private var cache: LzyList[A]^{this} = uninitialized
  private def force =
    if !forced then { cache = tl(); forced = true }
    cache

  def isEmpty = false
  def head = hd
  def tail: LzyList[A]^{this} = force
end LzyCons
extension [A](x: A)
  def #:(xs1: => LzyList[A]^): LzyList[A]^{xs1} =
    LzyCons(x, () => xs1)
def tabulate[A](n: Int)(gen: Int => A): LzyList[A]^{gen} =
  def recur(i: Int): LzyList[A]^{gen} =
    if i == n then LzyNil
    else gen(i) #: recur(i + 1)
  recur(0)

tabulate의 사용 예시는 다음과 같아요.

import language.experimental.captureChecking
import caps.*
trait LzyList[+A]:
  def isEmpty: Boolean
  def head: A
  def tail: LzyList[A]^{this}
object LzyNil extends LzyList[Nothing]:
  def isEmpty = true
  def head = ???
  def tail = ???
import scala.compiletime.uninitialized

final class LzyCons[+A](hd: A, tl: () => LzyList[A]^) extends LzyList[A]:
  private var forced = false
  private var cache: LzyList[A]^{this} = uninitialized
  private def force =
    if !forced then { cache = tl(); forced = true }
    cache

  def isEmpty = false
  def head = hd
  def tail: LzyList[A]^{this} = force
end LzyCons
extension [A](x: A)
  def #:(xs1: => LzyList[A]^): LzyList[A]^{xs1} =
    LzyCons(x, () => xs1)
def tabulate[A](n: Int)(gen: Int => A): LzyList[A]^{gen} =
  def recur(i: Int): LzyList[A]^{gen} =
    if i == n then LzyNil
    else gen(i) #: recur(i + 1)
  recur(0)
class LimitExceeded extends Exception
def squares(n: Int)(using ct: CanThrow[LimitExceeded]): LzyList[Int]^{ct} =
  tabulate(10): i =>
    if i > 9 then throw LimitExceeded()
    i * i

추론된 squares의 결과 타입은 LzyList[Int]^{ct}예요. 즉 tail을 한 번 이상 호출해 구체화(elaborated)될 때 LimitExceeded 예외를 던질 수 있는 Int들의 지연 리스트예요.

지연 리스트를 매핑, 필터링, 연결하기 위한 몇 가지 추가 확장 메서드는 다음과 같아요.

import language.experimental.captureChecking
import caps.*
trait LzyList[+A]:
  def isEmpty: Boolean
  def head: A
  def tail: LzyList[A]^{this}
object LzyNil extends LzyList[Nothing]:
  def isEmpty = true
  def head = ???
  def tail = ???
import scala.compiletime.uninitialized

final class LzyCons[+A](hd: A, tl: () => LzyList[A]^) extends LzyList[A]:
  private var forced = false
  private var cache: LzyList[A]^{this} = uninitialized
  private def force =
    if !forced then { cache = tl(); forced = true }
    cache

  def isEmpty = false
  def head = hd
  def tail: LzyList[A]^{this} = force
end LzyCons
extension [A](x: A)
  def #:(xs1: => LzyList[A]^): LzyList[A]^{xs1} =
    LzyCons(x, () => xs1)
def tabulate[A](n: Int)(gen: Int => A): LzyList[A]^{gen} =
  def recur(i: Int): LzyList[A]^{gen} =
    if i == n then LzyNil
    else gen(i) #: recur(i + 1)
  recur(0)
class LimitExceeded extends Exception
def squares(n: Int)(using ct: CanThrow[LimitExceeded]): LzyList[Int]^{ct} =
  tabulate(10): i =>
    if i > 9 then throw LimitExceeded()
    i * i
extension [A](xs: LzyList[A]^)
  def map[B](f: A => B): LzyList[B]^{xs, f} =
    if xs.isEmpty then LzyNil
    else f(xs.head) #: xs.tail.map(f)

  def filter(p: A => Boolean): LzyList[A]^{xs, p} =
    if xs.isEmpty then LzyNil
    else if p(xs.head) then xs.head #: xs.tail.filter(p)
    else xs.tail.filter(p)

  def concat(ys: LzyList[A]^): LzyList[A]^{xs, ys} =
    if xs.isEmpty then ys
    else xs.head #: xs.tail.concat(ys)

  def drop(n: Int): LzyList[A]^{xs} =
    if n == 0 then xs else xs.tail.drop(n - 1)

그들의 캡처 어노테이션은 모두 예상대로예요.

• 지연 리스트를 매핑하면 원래 리스트와 (아마 불순한) 매핑 함수를 캡처하는 지연 리스트가 생겨요.
• 지연 리스트를 필터링하면 원래 리스트와 (아마 불순한) 필터링 술어를 캡처하는 지연 리스트가 생겨요.
• 두 지연 리스트를 연결하면 두 인자를 모두 캡처하는 지연 리스트가 생겨요.
• 지연 리스트에서 원소를 버리면 결과에 원래 리스트가 캡처되는 안전한 근사가 돼요. 사실 런타임에서 유지되는 것은 리스트의 일부 suffix뿐이지만, 우리의 모델링은 지연 리스트와 그 suffix를 동일시하므로 이 추가 지식은 유용하지 않아요.

물론 map이나 filter에 전달되는 함수가 순수할 수도 있어요. 어쨌든 A -> B는 A => B와 같은 (A -> B)^{any}의 하위 타입이거든요. 그 경우 순수 함수 인자는 map이나 filter의 결과 타입에 나타나지 않아요. 예를 들어:

import language.experimental.captureChecking
import caps.*
trait LzyList[+A]:
  def isEmpty: Boolean
  def head: A
  def tail: LzyList[A]^{this}
object LzyNil extends LzyList[Nothing]:
  def isEmpty = true
  def head = ???
  def tail = ???
import scala.compiletime.uninitialized

final class LzyCons[+A](hd: A, tl: () => LzyList[A]^) extends LzyList[A]:
  private var forced = false
  private var cache: LzyList[A]^{this} = uninitialized
  private def force =
    if !forced then { cache = tl(); forced = true }
    cache

  def isEmpty = false
  def head = hd
  def tail: LzyList[A]^{this} = force
end LzyCons
extension [A](x: A)
  def #:(xs1: => LzyList[A]^): LzyList[A]^{xs1} =
    LzyCons(x, () => xs1)
def tabulate[A](n: Int)(gen: Int => A): LzyList[A]^{gen} =
  def recur(i: Int): LzyList[A]^{gen} =
    if i == n then LzyNil
    else gen(i) #: recur(i + 1)
  recur(0)
class LimitExceeded extends Exception
def squares(n: Int)(using ct: CanThrow[LimitExceeded]): LzyList[Int]^{ct} =
  tabulate(10): i =>
    if i > 9 then throw LimitExceeded()
    i * i
extension [A](xs: LzyList[A]^)
  def map[B](f: A => B): LzyList[B]^{xs, f} =
    if xs.isEmpty then LzyNil
    else f(xs.head) #: xs.tail.map(f)

  def filter(p: A => Boolean): LzyList[A]^{xs, p} =
    if xs.isEmpty then LzyNil
    else if p(xs.head) then xs.head #: xs.tail.filter(p)
    else xs.tail.filter(p)

  def concat(ys: LzyList[A]^): LzyList[A]^{xs, ys} =
    if xs.isEmpty then ys
    else xs.head #: xs.tail.concat(ys)

  def drop(n: Int): LzyList[A]^{xs} =
    if n == 0 then xs else xs.tail.drop(n - 1)
def test(using ct: CanThrow[LimitExceeded]^): Unit = {
val xs = squares(10)
val ys: LzyList[Int]^{xs} = xs.map(_ + 1)
}

매핑된 리스트 ys의 타입은 캡처 집합에 xs만 가져요. 실제 함수 인자는 순수하므로 나타나지 않아요. 마찬가지로 지연 리스트 xs가 순수했다면, 그 어떤 메서드 결과에도 나타나지 않았을 거예요. 이것은 캡처 검사를 가진 역량 기반 효과 시스템이 자연스럽게 효과-다형적(effect polymorphic)임을 보여줘요.

이것으로 예시를 마칠게요. 표준적이고 엄밀한 리스트를 정의하고 사용하는 동등한 프로그램은 캡처 어노테이션을 전혀 요구하지 않는다는 점을 언급할 가치가 있어요. 그것은 현재 표준 Scala 3에서 그대로 컴파일되면서도 캡처 검사를 공짜로 얻어요. 본질적으로 =>는 이미 "무엇이든 캡처할 수 있다"를 뜻하고, 엄밀한 리스트에서는 부작용 연산이 결과에 보존되지 않으므로 기록할 추가 캡처가 없어요. 물론 엄밀한 리스트는 그 원소에서 부작용을 일으키는 클로저를 캡처할 수 있지만, 그 원소들은 타입 변수로 표현되므로 터널링이 적용돼요. 이는 거기서도 아무것도 어노테이션할 필요가 없음을 뜻해요.

또 다른 가능성은 map, filter 및 그와 유사한 연산에 전달되는 모든 함수가 순수하도록 요구하는 지연 리스트 변형이에요. 예를 들어 그런 리스트의 map은 이렇게 정의될 거예요.

extension [A](xs: LzyList[A])
  def map[B](f: A -> B): LzyList[B] = ...

그 변형도 어떤 캡처 어노테이션도 요구하지 않을 거예요.

요약하면 데이터 구조 설계에는 두 개의 "스위트 스팟"이 있어요: 부작용을 일으키거나 리소스를 인지하는 코드의 엄밀한 리스트와 순수 함수형 코드의 지연 리스트. 둘 다 명시적인 어노테이션 없이 이미 올바르게 캡처-타입이 붙어 있어요. 캡처 어노테이션은 불순한 지연 리스트나 엄밀한 리스트 위의 부작용 반복자처럼 지연된 효과를 다루게 되어 의미가 더 복잡해지는 곳에서만 등장해요. 이 속성은 아마 더 시끄러운 경향이 있는 이전 기법들과 비교했을 때, 우리의 캡처 검사 접근이 가진 가장 큰 장점 중 하나일 거예요.