lazamar

Glean - Evaluating recursive queries

This document describes a proposed design for implementing support for recursive queries in Glean.

Semantics

With recursion comes the question of whether the query evaluation will ever finish and given the existence of negation we need to consider whether the result could be ambiguous. These questions are addressed in the sections on Termination and Negation.

Formally, Glean will calculate the well-founded partial model of a query, schema and database combination by calculating the least fixed point of such query. We require that schemas be stratified to guarantee that the well-founded partial model generated be two-valued and the only stable model for the program [1,2,4]. It can then be computed one stratum at a time, each stratum as the least fixed point of its rules given the strata below it.

lazamar

Marcelo Lazaroni

lazaroni.marcelo@gmail.com · github.com/lazamar · linkedin.com/in/lazaroni · Porto, Portugal

---

I work on compilers and database internals. I was one of the two people maintaining the core of Glean, Meta's graph database of facts about code; its query language compiler in Haskell and its runtime in C++. I have since led engineering at an event-sourcing infrastructure startup.

I like problems of correctness at scale, where it takes good abstractions to make systems both fast and safe.

lazamar

FROM debian:trixie-slim

ENV HOME="/root"
ENV LOCAL_BIN="$HOME/.local/bin"
ENV PATH="$PATH:$LOCAL_BIN:$HOME/.hsthrift/bin:$HOME/.ghcup/bin"
ENV LD_LIBRARY_PATH="$HOME/.hsthrift/lib"
ENV PKG_CONFIG_PATH="$HOME/.hsthrift/lib/pkgconfig"
ENV CABAL_CONFIG_FLAGS="-f-bundled-folly -fclang -f-hack-tests -f-rust-tests -f-python-tests"
ENV CLANG_VER="19"

lazamar

import weaviate, { WeaviateClient, Collection, vectors, generative } from 'weaviate-client';

// Best practice: store your credentials in environment variables
const weaviateUrl = process.env.WEAVIATE_URL as string;
const weaviateApiKey = process.env.WEAVIATE_API_KEY as string;

async function importData(collection: Collection) {
  const data : { sentence: string }[] = [
    // Nationalities
    "British",

lazamar

module Database.MySQL
  ( Connected
  , withConnection
  , connected
  ) where

import Control.Concurrent (MVar, newMVar, newEmptyMVar, putMVar, takeMVar, tryPutMVar, modifyMVar_)
import Control.Concurrent.Async (withAsyncBound, withAsync, wait, waitEither)
import Control.Exception (SomeException, SomeAsyncException, fromException, bracket, throwIO, tryJust, tryJust)
import Control.Monad (unless, forever)

lazamar

  Wed Jul  3 12:04 2024 Time and Allocation Profiling Report  (Final)

     main +RTS -p -RTS test ghcup

  total time  =       56.65 secs   (56648 ticks @ 1000 us, 1 processor)
  total alloc = 338,254,238,432 bytes  (excludes profiling overheads)

COST CENTRE            MODULE SRC                       %time %alloc

serialize.write        Main   Main.hs:(99,3)-(107,53)    27.6   27.7

lazamar

// run with `node index.js`

function bubbleSort(list) {
  for (let limit = 1; limit < list.length; limit++) {
    for (let i = 0; i < list.length - limit; i++) {
      let left = list[i];
      let right = list[i + 1];
      if (left > right) {
        list[i] = right;
        list[i+1] = left;

lazamar

{- Unnecessarily knot tying solution to https://github.com/josevalim/nested-map-reduce-traversal

   You can run it with:
    $ ghc Main.hs && ./Main

   Which outputs:
    Numbered 0 ("One",[Numbered 0 "A",Numbered 1 "B"])
    Numbered 1 ("Two",[Numbered 2 "C",Numbered 3 "D",Numbered 4 "E"])
    Numbered 2 ("Three",[Numbered 0 "F",Numbered 1 "G"])
    Numbered 3 ("Four",[])

lazamar

{- This is a solution to https://github.com/josevalim/nested-map-reduce-traversal
   without using explicit accumulators.
   
   You can run it with:
   $ ghc Main.hs && ./Main
   
   Which outputs:
    Numbered 0 ("One",[Numbered 0 "A",Numbered 1 "B"])
    Numbered 1 ("Two",[Numbered 2 "C",Numbered 3 "D",Numbered 4 "E"])
    Numbered 2 ("Three",[Numbered 0 "F",Numbered 1 "G"])

lazamar

#!/bin/bash
set -e
rm -f tags
find . -name "*.hs*" | fast-tags -
# ag respects .github
ag -l | ctags --optlib-dir=/home/lazamar/ --excmd=number --links=no -L-  # This must be universal-ctags