Victor Taelin VictorTaelin

Optimal Evaluation in 1 Minute (or 10 Minutes) (or 10 Years)

Short Version (1 minute)

A prerequisite to intelligence is the ability to find a program that explains a pattern. Programs are functions. To test a candidate program, we need to implement a "function evaluator". The problem is: all modern programming languages are sub-optimal "function evaluators", which, in the context of search, leads to massive slowdowns. To implement an optimal interpreter, we need to: 1. postpone the execution of expressions, to avoid wasted work, 2. cache the result of postponed expressions, to avoid duplicated work, 3. incrementally copy cached structures, to ensure 1 and 2 don't interfere. Haskell almost achieves this, but falls short on 3, because it is unable to incrementally copy lambdas. To solve this, we introduce the concept of a "superposition", which allows multiple versions of a term to exist simultaneously. This ensures that no work is ever wasted or duplicated, allowing us to optimally interpret (or com

Refactoring Kind's switch with ChatSH

(This is a readable version of my ChatSH session. For the full log, click here.)

Taelin: Hello. We're going to refactor an aspect of the implementation of the Kind language. Are you ready? Start by doing 'ls', then 'cat kind-lang.cabal' to get familiar with the repo.

ChatSH: Certainly! I'm ready to help you refactor an aspect of the Kind language implementation. Let's start by examining the repository structure and the contents of the Cabal file.

ls &amp;&amp; echo "---" &amp;&amp; cat kind-lang.cabal

Accelerating Discrete Program Search

I am investigating how to use Bend (a parallel language) to accelerate Symbolic AI; in special, Discrete Program Search. Basically, think of it as an alternative to LLMs, GPTs, NNs, that is also capable of generating code, but by entirely different means. This kind of approach was never scaled with mass compute before - it wasn't possible! - but Bend changes this. So, my idea was to do it, and see where it goes.

Now, while I was implementing some candidate algorithms on Bend, I realized that, rather than mass parallelism, I could use an entirely different mechanism to speed things up: SUP Nodes. Basically, it is a feature that Bend inherited from its underlying model ("Interaction Combinators") that, in simple terms, allows us to combine multiple functions into a single superposed one, and apply them all to an argument "at the same time". In short, it allows us to call N functions at a fraction of the expected cost. Or, in simple terms: why parallelize when we can sha

	Let an AB symbol be one of 4 possible variants:

	data AB : Set where
	A# : AB
	#A : AB
	B# : AB
	#B : AB

	Let an AB Term be a list of AB symbols:

	// Computes modular exponentiation by repeated ENUM rotation.
	//
	// To compute `a ^ b % M`, we:
	// - 1. Create a generic ENUM with M variants: enum T { v0, v1, v2, ... vM }
	// - 2. Create a generic ENUM rotator: v0 -> v1, v1 -> v2, ... v1 -> v0
	// - 3. Apply that rotator a^b times to v0; the result will be `a ^ b % M`!
	//
	// To test this, we compute `(123 ^ 10) % 257`.
	// This should require at least 792594609605189126649 function calls.
	// A Macbook M3 would take about 25,000 years to count to that number.

	<0>(HVM_MAIN_CALL)
	----------------
	<0>(HVM_MAIN_CALL)
	----------------
	<0>(Main)
	----------------
	<0>(Main)
	----------------
	<0>(Quote (APP (C2a) (C2b)) 0)
	----------------

	(Switch 0 z s) = z
	(Switch n z s) = (s (- n 1))

	// (λx(bod) arg)
	// ------------- APP-LAM
	// x <- arg
	// bod
	(APP (Lam bod) arg) =
	(bod arg)

	SYSTEM:
	You're a code completion assistant.

	PROMPT:
	-- Files for context:

	-- Kind-Lang parser in Rust:

	--
	use crate::{*};

	// tt.hs:

	import Control.Monad (forM_)
	import Data.Char (chr, ord)
	import Debug.Trace
	import Prelude hiding (LT, GT, EQ)
	import System.Environment (getArgs)
	import System.Exit (exitFailure)
	import Text.Parsec ((<\|>))
	import qualified Data.Map.Strict as M