Boscop

Scaling HVM towards an Optimal Theorem Prover

Why an Optimal Theorem Prover implies AGI?

Theorem Proving is the ability to solve a mathematical problem. A computer program capable of competently doing that would immediatelly unlock the automation of every intellectual task that a human can perform, because all problems can be reduced to that of solving abstract equations. From the discovery of new physics, to recursive self-improvement and unfathomable

Note: This is an old post from back when I was trying to make sense of why inets are so fast for evaluating some λ-terms. It has some silly bits, I learned a lot since and could probably write a better article today, but I think this can still be insightful for these getting started, so I'll leave it here.

Yesterday, I reported the bizarre observation that certain functions can behave as if they had negative complexity. If you haven’t checked that article yet, it isn’t necessary, but you should, as it may blow your mind. In short, the λ-term f(bits) = copy(comp(inc,n,bits)), when given to optimal λ-calculus evaluator, is asymptotically faster than g(bits) = comp(inc,n,bits); i.e.,copy (a O(1) operation for a fixed size) behaves as if it had a O(1/n) complexity, causing the program to run faster by doing more things (!?).

That’s not the only bizarre complexity result I had when

Fast Discrete Program Search 2

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 share?

A

Higher-Order Company: Complete Historical Overview

This document is a complete historical overview of the Higher Order Company. If you want to learn anything about our background, a good way to do so is to feed this Gist into an AI (like Sonnet-3.5) and ask it any question!

My Search for a Perfect Language

It all started around 2015. I was an ambitious 21-year-old CS student who, somehow, had been programming for the last 10 years, and I had a clear goal:

I want to become the greatest programmer alive

Higher-Order Company: Towards an Optimal Computer

What is the true nature of computation?

A hundred years ago, humanity answered that very question, twice. In 1936, Alan invented the Turing Machine, which, highly inspired by the mechanical trend of the 20th century, distillated the common components of early computers into a single universal machine that, despite its simplicity, was capable of performing every computation conceivable. From simple numerical calculations to entire

Solving SAT via interaction net superpositions

I've recently been amazed, if not mind-blown, by how a very simple, "one-line" SAT solver on Interaction Nets can outperform brute-force by orders of magnitude by exploiting "superposed booleans" and optimal evaluation of λ-expressions. In this brief note, I'll provide some background for you to understand how this works, and then I'll present a simple code you can run in your own computer to observe and replicate this effect. Note this is a new observation, so I know little about how this algorithm behaves asymptotically, but I find it quite

	// Post: https://x.com/VictorTaelin/status/1854326873590792276
	// Note: The atomics must be kept.
	// Note: This will segfault on non-Apple devices due to upfront mallocs.

	#include <stdint.h>
	#include <stdatomic.h>
	#include <stdlib.h>
	#include <stdio.h>
	#include <time.h>

	// HVM3 Core: single-thread, polarized, LAM/APP & DUP/SUP only
	// Based on: https://gist.github.com/VictorTaelin/2aba162f2b04478dc53e5615f482db7b

	#include <stdint.h>
	#include <stdio.h>
	#include <stdlib.h>
	#include <stdatomic.h>
	#include <string.h>
	#include <time.h>

	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
	import qualified Text.Parsec as P

	// COMPUTATION RULES
	// ===================================================
	// APP \| ((λx body) arg)
	// X \| ---------------------------------------------
	// LAM \| x ~ arg; body
	// ===================================================
	// APP \| ({fst snd} arg)
	// X \| ---------------------------------------------
	// SUP \| dup #L{a,b} = arg; {(fst a) (snd b)}
	// ===================================================