Scala with Cats学習メモ：Monoids and Semigroups

Scala with Cats を読んだので学習した内容のメモを残します。
2章のMonoids and Semigroupsです。

はじめに

Monoidは二項演算と単位元を持つ代数的構造であり、Catsでは型クラスが提供されている。

Monoidの定義

CatsでのMonoidの定義を簡略化したものが以下。

trait Monoid[A] {
  def combine(x: A, y: A): A
  def empty: A
}

• combine(二項演算): A型の2つの値を結合させて1つのA型の値を返す
• empty(単位元): A型の空要素を返す

という2つの操作がMonoidには定義されている。

combineとemptyの操作に加えて、Monoidはいくつかの法則に従う必要がある。

def associativeLaw[A](x: A, y: A, z: A)(implicit m: Monoid[A]): Boolean = {
  m.combine(x, m.combine(y, z)) == 
    m.combine(m.combine(x, y), z)
}
def identityLaw[A](x: A)(implicit m: Monoid[A]): Boolean = {
  (m.combine(x, m.empty) == x) && 
    (m.combine(m.empty, x) == x)
}

例えば整数の足し算、整数の掛け算、文字列の連結はこれらの法則に従うが、整数の引き算は従わない。

Semigroupの定義

SemigroupはMonoidのcombineの部分であり、emptyは含まない。

trait Semigroup[A] {
  def combine(x: A, y: A): A
}
trait Monoid[A] extends Semigroup[A] {
  def empty: A
}

CatsにおけるMonoid

Monoid型クラスは cats.kernel.Monoid で、cats.Monoid としてエイリアスされている。

catsパッケージから型クラスをimportする

import cats.Monoid
import cats.Semigroup

instance

import cats.Monoid
import cats.instances.string._ // for Monoid
Monoid[String].combine("Hi ", "there")
// res0: String = "Hi there"
Monoid[String].empty
// res1: String = ""

個々のinstanceをimportする理由がなければ全てをimportすればいい。

import cats._
import cats.implicits._

syntax
Catsは、|+| 演算子の形でcombineメソッドの構文を提供している。

Monoidの活用例

(1)ビッグデータ
SparkやHdoopのようなアプリケーションで複数マシンでの計算結果を組み合わせる

(2)分散システム
2つのデータをマージする際、この操作はMonoidであることに依存している

まとめ

Semigroupは加算や組み合わせの演算を表し、MonoidはSemigroupに恒等要素や ゼロ 要素を追加して拡張したもの

Scala with Cats学習メモ：Introduction

MicroAd Advent Calendar 2023 の21日目の記事です。

Scala with Cats を読んだので学習した内容のメモを残します。
1章のIntroductionです。

はじめに

Catsには様々な関数型プログラミングのツールが含まれているが、それらの大半は既存のScalaの型に適用できる型クラスで提供される。
型クラスはHaskellで使われ始めたプログラミングパターンで、これによって継承を用いずに既存のコードの機能拡張が行える。

用語

※ クラスやインスタンスはオブジェクト指向で聞き慣れた言葉だが、意味が異なるので注意

型クラス

実装したい機能を表現するインタフェースやAPIのこと
Scalaでは1つ以上の型パラメータを持つtraitで表される

trait Show[A] {
  def show(value: A): Unit
}

例えば上記で定義したShowはコンソール出力を生成するメカニズムを提供する型クラスで、型パラメータAを持つ

型クラスのインスタンス

型クラスの実装を提供する
Scalaではimplicit valueでインスタンスを定義する

implicit val showIntInstance: Show[Int] = new Show[Int] {
  def show(value: Int): Unit = println(value.toString)
}

既存のクラスにShowの機能がほしい場合も継承ではなく、型クラスのインスタンスを作成し拡張できる

case class Person(name: String, age: Int)

implicit val showPersonInstance: Show[Person] = new Show[Person] {
  def show(value: Person): Unit = println(s"name=${value.name}, age=${value.age}")
}

型クラスの使用

型クラスの使用は動作するために型クラスのインスタンスを必要とする機能のこと
Scalaでは型クラスのインスタンスをimplicitパラメータとして受け取るメソッドで定義
2つの方法がある

方法1: Interface Objects

シングルトンオブジェクトにメソッドを置く方法

object ShowObject {
  def showValue[A](value: A)(implicit show: Show[A]): Unit = show.show(value)
}

実行する場合には型クラスのインスタンスが必要になる

import ShowObject._

showValue(1) // showIntInstance
showValue(Person("a", 1))  // showPersonInstance
// showValue(100L) // 対応するインスタンスがないためコンパイルエラー

方法2: Interface Syntax

implicit classで実装する方法
Catsではシンタックスと呼ばれる

object ShowSyntax {
  implicit class ShowOps[A](value: A) {
    def showValue(implicit show: Show[A]): Unit = show.show(value)
  }
}

必要なインスタンスをインポートして実行する

import ShowSyntax._

1.showValue // showIntInstance
Person("Bob", 30).showValue // showPersonInstance
// 100L.showValue // 対応するインスタンスがないためコンパイルエラー

Catsのパッケージ構成

型クラス

Catsの型クラスはcatsパッケージで定義されている

import cats.Show

インスタンス

cats.instancesパッケージにインスタンスが定義されている

import cats.instances.int
import cats.instances.string
import cats.instances.list
...

シンタックス

cats.syntaxパッケージからシンタックスをインポートできる

import cats.syntax.show._

全部

実は個別にインポートしなくても

import cats._
import cats.implicits._

で標準的なインスタンスとシンタックスを一気にインポートできる

変位

変位指定は複合型の間の継承関係とそれらの型パラメータ間の継承関係の相関です。

変位指定 | Scala Documentation

trait Foo[A]  // Invariance(非変)
trait Bar[+A] // Covariance(共変)
trait Baz[-A] // Contravariance(反変)

Covariance(共変)

BがAのサブタイプであるとき、型F[B]がF[A]のサブタイプである

covariance

+記号を使って共変を表す

trait F[+A]

ScalaではListやOptionが共変で定義されている

trait List[+A]
trait Option[+A]

共変を使えば、ある型のコレクションをそのサブタイプのコレクションで代用することができる

seald trait Animal
case class Dog(name: String) extends Animal

val dogs: List[Dog] =  List(Dog("A"), Dog("B"))
val animals: List[Animal] = dogs

一般的には共変は出力、つまりメソッドの戻り値などに使われる。

Contravariance(反変)

AがBのサブタイプであるとき、型F[B]がF[A]のサブタイプである

contravariance

-記号を使って反変を表す

trait F[-A]

反変は型クラスJsonWriterのように、入力を表す型をモデリングする

trait JsonWriter[-A] {
  def write(value: A): Json
}


val shape: Shape = ???
val circle: Circle = ???

val shapeWriter: JsonWriter[Shape] = ???
val circleWriter: JsonWriter[Circle] = ???

def format[A](value: A, writer: JsonWriter[A]): Json = 
  writer.write(value)

どの値とどのJsonWriterの組み合わせをformat関数に渡すことができるか?
全てのCircleはShapeなので、CircleはJsonWriter[Shape]とJsonWriter[Circle]のどちらを使ってもwriteが可能
一方、全てのShapeがCircleではないので、JsonWriter[Circle]でShapeをwriteできない

format(shape, shapeWriter)
// format(shape, circleWriter) // compile error
format(circle, shapeWriter)
format(circle, circleWriter)

Invariance(非変)

共変でも反変でもない。Scalaでは標準で非変になる。

trait F[A]

インスタンスの選択

型クラスを扱う際に、インスタンスの選択を行ううえで2つの問題がある

• A: スーパータイプに定義されたインスタンスが利用可能な場合、そのインスタンスは選択されるのか？
• B: サブタイプのインスタンスはスーパータイプのインスタンスよりも優先して選択されるのか？

これらの質問に対する回答は変位ごとに異なる

型クラスの変位	質問A	質問B
非変	No	No
共変	No	Yes
反変	Yes	No

さいごに

2章以降では1章で紹介されたShowやEqなどよりもさらに抽象度が高い型クラスである Semigroup、Monoid、Functor、Monad、Semigroupal、Applicative、Traverseなどが説明されています。そのあたりも学習した内容をまとめていきたいです（余裕があれば）。

FLEDGEにおけるWebAssemblyの利用

この記事は MicroAd Advent Calendar 2022 の22日目の記事です。

qiita.com

これまでリターゲティング*1は、3rd Party Cookie*2を利用し、サイトアクセス情報をアドテクのサーバで保存することで実現していました。
しかしChromeで2024年に3rd Party Cookieの廃止が予定されているため、今の仕組みは使えなくなります。 そこでFLEDGEの登場です。

FLEDGEとは

FLEDGEはPrivacy Sandbox*3で提案される、クロスサイトトラッキング技術に依存せずにリターゲティングを実現する仕組みです。
K匿名性やブラウザ上でのオークションなどの技術を利用することにより、ユーザのプライバシーは保護された上で広告配信が行われます。
FLEDGEではざっくりと以下のような流れで処理が行われます。

1. ユーザが広告主サイトにアクセスした時、buyer(広告主またはDSP)が設置したタグがインタレストグループの情報をブラウザに保存する。
2. 同じユーザ(ブラウザ)がパブリッシャーサイトにアクセスした時、seller(パブリッシャーまたはSSP)の設置したタグがブラウザ上のオークションを実行し表示する広告を選ぶ。この時、ブラウザに保存されたインタレストグループの情報を利用する。
3. 広告がFenced Frame(特殊なiframeのようなもの)の中で表示される。

ブラウザ上のオークション処理は入札ワークレットと呼ばれる特別な環境で実行され、通信ができないなどの制限があるため注意が必要です。

FLEDGEの仕組み

もう少し詳しくFLEDGEの仕組みを説明します。
以下で示すコードの例を動かすには、現時点(2022年12月22日)ではChromeで以下のフラグを有効化する必要があります。

• chrome://flags/#privacy-sandbox-ads-apis
• chrome://flags/#enable-fenced-frames

インタレストグループ登録

インタレストグループは共通の興味を持つユーザのグループを表し、広告や入札処理に関連する情報が含まれます。
以下はインタレストグループのデータをブラウザに保存するコードの例です。
navigator.joinAdInterestGroupはFLEDGE特有のAPIなのでフラグを有効化している必要があります。

const interestGroup = {
  "owner": "https://example-buyer.com",  // インタレストグループのオーナー
  "name": "item1", // インタレストグループの名前。ownerとペアでインタレストグループは一意になる。
  "biddingLogicUrl": "https://example-buyer/biddingLogic.js", // 入札額計算を行う時に使用する関数を定義したファイルのURL
  "ads": [, // 表示する広告のURLとメタデータ
    {"renderUrl": "https://ads.advertiser-a.com/ads/item1-ad1.html", "metadata": "item1-ad1"},
    {"renderUrl": "https://ads.advertiser-a.com/ads/item1-ad2.html", "metadata": "item1-ad2"}
  ]
}

const kSecPerDay = 30 * 24 * 60 * 60; // インタレストグループの有効期間

navigator.joinAdInterestGroup(interestGroup, kSecPerday)

※ 上記の interestGroupには最低限の値しか設定していません。他にも入札時に使用可能なシグナルなどを設定可能です。

ブラウザ上でのオークション

FLEDGEでは広告のオークション処理がブラウザ上で実行されます。
以下はブラウザ上のオークションを実行するコードの例です。
navigator.runAdAuctionはFLEDGE特有のAPIなのでフラグを有効化している必要があります。

const auctionConfig = {
  "seller": "https://example-seller.com",
  "decisionLogicUrl": "https://example-seller.com/decisionLogic.js",
  "interestGroupBuyers": ["https://example-buyer.com", ...]
};

const opaqeuAds = await navigator.runAdAuction(auctionConfig);

※ 上記のauctionConfigには他にもさまざまな値が設定可能です。

navigator.runAdAuctionが実行されると、ブラウザ内部ではbuyerの定義したgenerateBidとsellerの定義したscoreAdが実行されます。

generateBid

インタレストグループごとに実行され、入札する広告を選択します。
入札処理を行う場合には広告のメタデータや、その他シグナルと呼ばれる情報を用いることが可能です。

generateBid(interestGroup, auctionSignals, perBuyerSignals, trustedBiddingSignals, browserSignals, directFromSellerSignals) {
  ...
  return {'ad': adObject,
          'bid': bidValue,
          'render': renderUrl,
          'adComponents': [adComponent1, adComponent2, ...],
          'allowComponentAuction': false};
}

scoreAd

generateBidで入札された広告ごとに、入札額を調整するような処理をseller側で定義したコードで実行します。

scoreAd(adMetadata, bid, auctionConfig, trustedScoringSignals, browserSignals, directFromSellerSignals) {
  ...
  return {desirability: desirabilityScoreForThisAd,
          allowComponentAuction: componentAuctionsAllowed};
}

WebAssembly

WebAssemblyを利用することで実行速度の問題を解決可能な場合があります(WebAssemblyではJavaScriptエンジンによる呼び出しではなく、機械語レベルでの呼び出しを用いる)。
WebAssemblyのユースケースとしては以下が参考になります。
Use Cases - WebAssembly

C/C++やRustなどのコードをWebAssemblyバイナリにコンパイルし、ブラウザがWebAssemblyバイナリを機械語のコードにコンパイルします。
C/C++ではEmscripten、Rustではwasm-bindgenを利用することでWebAssemblyバイナリを生成できます。

Main — Emscripten 3.1.26-git (dev) documentation

Introduction - The `wasm-bindgen` Guide

FLEDGEにおけるWebAssemblyの利用

WebAssemblyがFLEDGEにどう関わってくるのでしょうか。
入札額計算が実行される入札ワークレットで複雑な計算を行うと、パフォーマンスが大幅に低下しタイムアウト制限を超えてしまう問題がありました。
詳細は以下のissueで議論されています。

Bidding worklet performance limitations · Issue #215 · WICG/turtledove · GitHub

generateBidでのタイムアウトを回避するためにWebAssemblyを使用することが可能です。
インタレストグループに登録するデータとして biddingWasmHelperUrl という項目が指定可能で、ブラウザでの入札額計算実行前に指定したURLからWebAssemblyバイナリを取得し、入札関数に引数としてWebAssemblyモジュールを渡してくれます。

インタレストグループでのbiddingWasmHelperUrl登録例

const interestGroup = {
  "owner": "https://example-buyer.com", 
  "name": "item1", 
  "biddingLogicUrl": "https://example-buyer/biddingLogic.js",
  "biddingWasmHelperUrl": "https://example-buyer.com/wasm",  // WebAssemblyバイナリを取得するURL
  "ads": [,
    {"renderUrl": "https://ads.advertiser-a.com/ads/item1-ad1.html", "metadata": "item1-ad1"},
    {"renderUrl": "https://ads.advertiser-a.com/ads/item1-ad2.html", "metadata": "item1-ad2"}
  ]
}

入札額計算実行前に指定したURLからWebAssemblyモジュールを取得し、generateBid関数のbrowserSignalsから取得可能です。

function generateBid(interestGroup, auctionSignals, perBuyerSignals, trustedBiddingSignals, browserSignals, directFromSellerSignals) {
  ...
  const wasmInstance = (new WebAssembly.Instance(browserSignals.wasmHelper)).exports;
  const bid = wasmInstance.bid(interestGroup.ads); // bidは入札額計算を行う関数とする
  ...
}

これを利用することで複雑な計算処理を高速化することが可能になり、ブラウザ上でのオークションでも精度の高い入札が行えることが期待できます。

さいごに

FLEDGEの仕組みとWebAssemblyがどう利用されているのかを簡単に紹介しました。
まだまだ仕様変更が入ることが考えられるため、今後も動向を追っていきたいです。

参考

turtledove/FLEDGE.md at main · WICG/turtledove · GitHub

FLEDGE API - Chrome Developers

FLEDGE RTB origin trial  |  Real-time Bidding  |  Google Developers

*1:サイトにアクセスしたユーザに対してそのサイトの広告を配信するターゲティング

*2:アクセスしたサイトのドメインとは別のドメインが発行するCookieのこと。

*3:3rd Party Cookieやその他のトラッキング技術を用いずにクロスサイトのユースケースを満たす一連の提案。