5-q.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "14101481-e6ec-4bcc-95d5-44916ab4edea",
   "metadata": {},
   "source": [
    "# Embedding the `q` array programming language"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70698684-1f12-4595-b16f-60478cab5e66",
   "metadata": {},
   "source": [
    "## Syntax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3837b901-f1c8-4b90-89bf-c89972023a18",
   "metadata": {},
   "outputs": [],
   "source": [
    "trait Q[R]:\n",
    "    extension (i: Int)\n",
    "        def int: R\n",
    "\n",
    "    extension (f: R => R)\n",
    "        def lam: R\n",
    "\n",
    "    extension (f: (R, R) => R)\n",
    "        def lam: R\n",
    "\n",
    "    extension (q1: R)\n",
    "        def til: R\n",
    "        def +(q2: R): R\n",
    "        def *(q2: R): R\n",
    "        def apply(q2: R): R \n",
    "        def apply(q21: R, q22: R): R \n",
    "        def ++(q2: R): R\n",
    "        def cross(q2: R): R\n",
    "        def `#`(l: R): R\n",
    "        def count: R\n",
    "        def reverse: R\n",
    "        def |>(f: R => R): R\n",
    "        def drop(i: R): R\n",
    "\n",
    "    def min: R \n",
    "    def `*`: R\n",
    "\n",
    "    extension (f: (R, R) => R)\n",
    "        def each: R = \n",
    "            ((p: R) => f(p(0.int), p(1.int))).lam.each\n",
    "\n",
    "    extension (f: R)\n",
    "        def each: R\n",
    "        def over: R\n",
    "\n",
    "object Q: \n",
    "    def apply[R](using Q: Q[R]) = Q\n",
    "\n",
    "    object syntax: \n",
    "        def `*`[R](using Q: Q[R]): R = Q.`*`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a3168e0-87cb-4b6c-9dcc-be83eae260ff",
   "metadata": {},
   "source": [
    "## Programs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a7c7039e-7a7a-43e2-8b48-a10b40481674",
   "metadata": {},
   "outputs": [],
   "source": [
    "// {(*/)1+til x}\n",
    "import Q.syntax._\n",
    "\n",
    "def factorial[R: Q] = \n",
    "    {(x: R) => `*`.over(1.int + x.til)}.lam"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f619c9e-1f28-43a0-af19-921264266cfb",
   "metadata": {},
   "outputs": [],
   "source": [
    "// {(min'')(2#count w)#w cross w:v,1_reverse v:1+til x}\n",
    "\n",
    "def pyramid[R: Q] = \n",
    "    {(x: R) =>\n",
    "        (1.int + x.til) |> { v => \n",
    "            (v ++ v.reverse.drop(1.int)) |> { w => \n",
    "                 Q[R].min.each.each(2.int `#` w.count `#` (w cross w))\n",
    "            }\n",
    "        }\n",
    "    }.lam"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f71e02be-d1c1-4fc9-9b43-dda659172c76",
   "metadata": {},
   "source": [
    "## Q serialization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "87f655e9-c205-421e-a5d5-1750a8796c00",
   "metadata": {},
   "outputs": [],
   "source": [
    "import $ivy.`org.typelevel::cats-core:2.10.0`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c6516af5-aab4-447b-bf9f-2d6c3f3c7db5",
   "metadata": {},
   "outputs": [],
   "source": [
    "import cats._, cats.data._, cats.syntax.all._, cats.implicits._"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c14c824b-9602-499d-8931-1d1a45a42412",
   "metadata": {},
   "outputs": [],
   "source": [
    "case class S(i: Int, b: Boolean, m: Map[Int, String])\n",
    "\n",
    "object S: \n",
    "    type QSerA[A] = State[S, A]\n",
    "    type QSer = State[S, String]\n",
    "\n",
    "    def paren(s: String)(b: Boolean): String = \n",
    "        if (b) s\"($s)\"\n",
    "        else s\n",
    "\n",
    "    def getParen: QSerA[Boolean] = \n",
    "        State.inspect:\n",
    "            case S(i, b, s) => b\n",
    "\n",
    "    def getVar: QSerA[Int] = \n",
    "        State.inspect:\n",
    "            case S(i, b, s) => i\n",
    "\n",
    "    def getVarValue(i: Int): QSer = \n",
    "        State.inspect:\n",
    "            case S(_, _, s) => s(i)\n",
    "\n",
    "    def incVar: QSerA[Unit] = \n",
    "        State.modify:\n",
    "            case S(i, b, m) => S(i+1, b, m)\n",
    "\n",
    "    def modifyMap(f: Map[Int, String] => Map[Int, String]): QSerA[Unit] = \n",
    "        State.modify:\n",
    "            case S(i, b, m) => S(i, b, f(m))\n",
    "\n",
    "    def setValue(i: Int, s: String): QSerA[Unit] = \n",
    "        modifyMap(_ + (i -> s))\n",
    "\n",
    "    def getValue(i: Int): QSer = \n",
    "        for\n",
    "            v <- getVarValue(i)\n",
    "            _ <- setValue(i, s\"x$i\")\n",
    "        yield v\n",
    "\n",
    "    extension (q: QSer)\n",
    "        def withParen(b: Boolean): QSer =\n",
    "            State.modify[S]{ case S(i, _, s) => S(i, b, s) } *> q \n",
    "\n",
    "        def serialize: String = \n",
    "            q.runA(S(0, false, Map())).value\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e0ef65f6-6150-4b3a-914b-c6875b3bc6b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import S._\n",
    "\n",
    "object QSer extends Q[QSer]:\n",
    "\n",
    "    extension (i: Int)\n",
    "        def int: QSer = State.pure(i.toString)\n",
    "\n",
    "    extension (f: QSer => QSer)\n",
    "        def lam: QSer = for\n",
    "            i1 <- f(State.pure(s\"x\")).withParen(false)\n",
    "        yield s\"{$i1}\"\n",
    "\n",
    "    extension (f: (QSer, QSer) => QSer)\n",
    "        def lam: QSer = for\n",
    "            i1 <- f(State.pure(\"x\"), State.pure(\"y\")).withParen(false)\n",
    "        yield s\"{$i1}\"\n",
    "\n",
    "    extension (q1: QSer)\n",
    "\n",
    "        def op2(op: String, sp: String)(q2: QSer): QSer = for\n",
    "            b <- getParen\n",
    "            i2 <- q2.withParen(false)\n",
    "            i1 <- q1.withParen(true)\n",
    "        yield paren(s\"$i1$sp$op$sp$i2\")(b)\n",
    "\n",
    "        def op1(op: String): QSer = for\n",
    "            b <- getParen\n",
    "            i1 <- q1.withParen(false)\n",
    "        yield paren(s\"$op $i1\")(b)\n",
    "                 \n",
    "        def op1post(op: String): QSer = for\n",
    "            b <- getParen\n",
    "            i1 <- q1.withParen(false)\n",
    "        yield paren(s\"$i1$op\")(b)\n",
    "                 \n",
    "        def til: QSer = q1.op1(\"til\")\n",
    "\n",
    "        def +(q2: QSer): QSer = q1.op2(\"+\", \"\")(q2)\n",
    "\n",
    "        def *(q2: QSer): QSer = q1.op2(\"*\", \"\")(q2)\n",
    "\n",
    "        def apply(q2: QSer): QSer  = for\n",
    "            b <- getParen\n",
    "            i1 <- q1.withParen(true)\n",
    "            i2 <- q2.withParen(false)\n",
    "        yield paren(s\"$i1$i2\")(b)\n",
    "\n",
    "        def apply(q21: QSer, q22: QSer): QSer = for\n",
    "            b <- getParen\n",
    "            i1 <- q1.withParen(true)\n",
    "            i21 <- q21.withParen(true)\n",
    "            i22 <- q22.withParen(false)\n",
    "        yield paren(s\"$i1[$i21,$i22]\")(b)\n",
    "\n",
    "        def ++(q2: QSer): QSer = q1.op2(\",\", \"\")(q2)\n",
    "\n",
    "        def cross(q2: QSer): QSer = q1.op2(\"cross\", \" \")(q2)\n",
    "\n",
    "        def `#`(q2: QSer): QSer = q1.op2(\"#\", \"\")(q2)\n",
    "\n",
    "        def count: QSer = q1.op1(\"count\")\n",
    "\n",
    "        def reverse: QSer = q1.op1(\"reverse\")\n",
    "\n",
    "        def |>(f: QSer => QSer): QSer = for\n",
    "            b <- getParen\n",
    "            i <- getVar\n",
    "            i1 <- q1.withParen(false)\n",
    "            _ <- setValue(i, s\"x$i:$i1\")\n",
    "            _ <- incVar\n",
    "            i2 <- f(getValue(i)).withParen(false)\n",
    "        yield paren(i2)(b)\n",
    "\n",
    "        def drop(q2: QSer): QSer = q2.op2(\" _ \", \"\")(q1)\n",
    "\n",
    "    def min: QSer  = State.pure(\"min\")\n",
    "    def `*`: QSer  = State.pure(\"*\")\n",
    "\n",
    "    extension (q1: QSer)\n",
    "        def each: QSer = q1.op1post(\"'\")\n",
    "        def over: QSer = q1.op1post(\"/\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6d836187-7591-4584-be64-ded4a72e1a81",
   "metadata": {},
   "outputs": [],
   "source": [
    "factorial(using QSer).serialize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f300a5ed-dde6-41b0-820d-7d27bb222967",
   "metadata": {},
   "outputs": [],
   "source": [
    "def p1[R: Q]: R = \n",
    "    3.int.til + 1.int + 5.int"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "33313e6d-7b91-45d0-acc7-4d319b7b827b",
   "metadata": {},
   "outputs": [],
   "source": [
    "p1(using QSer).serialize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6dd1f65e-90c4-429f-9af2-b30a9ae63058",
   "metadata": {},
   "outputs": [],
   "source": [
    "// {(min'')(2#count w)#w cross w:v,1_reverse v:1+til x}\n",
    "\n",
    "pyramid(using QSer).serialize"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "177ddcec-fd52-49f1-b2c0-0a27d7489487",
   "metadata": {},
   "source": [
    "# References"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b9e10907-4835-4e25-959a-ae891c1477ee",
   "metadata": {},
   "source": [
    "* kdb+/q: https://kx.com/developers/"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala 3.3.0",
   "language": "scala",
   "name": "scala3"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".sc",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.13.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}