Scm2Cpp

Japanese (README.ja.md) · 中文 (README.zh.md)

Scm2Cpp translates a subset of Scheme into C++ that a person can read and edit, and scikit-learn's machine-learning algorithms, written in it plainly, come out fast. The translator derives the fast form of an algorithm from the naive one (the Gram matrix hoisted out of a coordinate descent, a loop-invariant product formed once), hands the products to BLAS or cuBLAS, and turns parallel loops into CUDA kernels. The estimators ship on PyPI as scm2cpp-learn (scm2cpp-lasso up to 0.17.0; that name still installs it), with compiled wheels for Linux, macOS and Windows (no compiler, no Racket).

Machine-learning algorithms it speeds up

Each is scikit-learn's own algorithm written in the subset, checked against scikit-learn's iterations and results. Times against scikit-learn on one core (i9-10900X, an RTX 4090 for the device rows, scikit-learn 1.9); the conditions are in the section named on the right.

algorithm, n x p	scm2cpp_learn class	against scikit-learn	how	section
Lasso, 4,096 penalties each from zero, 1,800 x 200	CovLasso (fit_path_batch)	16x on one core, 340x on the GPU (tolerance 1e-8 against its 1e-4)	the descent over the Gram matrix	Example: a fast lasso
Lasso path, 20 penalties, 100,000 x 500	DerivedLasso (fit_path)	6.7x	derived from the naive descent (--derive --cublas)	First example: the lasso
RFE(LinearRegression), 20,000 x 500	GramRFE(0.0, ..)	1,047x	the Gram, its Cholesky factor downdated per drop	Feature selection by F statistics and RFE
f_regression, 100 targets, 20,000 x 1,000	f_regression	49x	one product on the device	Feature selection by F statistics and RFE
RidgeCV, 50 alphas, 20,000 x 500	GramRidgeCV	29x	one eigenproblem, every alpha's leave-one-out errors in two products	RidgeCV from one eigenproblem
KernelPCA(rbf), 5 components, 6,000 x 20	GramKernelPCA	3.5x	subspace iteration by dgemm, where scikit-learn takes ARPACK	KernelPCA by subspace iteration
LinearDiscriminantAnalysis, 200,000 x 100, 5 classes	GramLDA	52x	the svd solver's n x p SVD as a p x p eigenproblem of the Gram	LDA from the Gram matrix
TruncatedSVD, 10 components, 200,000 x 100	GramTruncatedSVD	5.4x (20x against arpack)	the exact SVD from X'X, where scikit-learn's default approximates	TruncatedSVD from the Gram matrix
CCA / PLSRegression, 50,000 x 500 -> 10	GramCCA / GramPLSRegression	109x / 61x	NIPALS on X'X, X'Y, Y'Y: the rows read once	PLS and CCA over the cross products
FactorAnalysis, 200,000 x 100, 10 factors	GramFactorAnalysis	62x (286x against lapack)	each iteration's n x p SVD as a p x p eigenproblem of the covariance	FactorAnalysis over the covariance
LinearRegression, 500,000 x 100	GramLinearRegression	19x	the normal equations by Cholesky, guarded by the condition estimate	LinearRegression from the Gram matrix
QuantileRegressor, 20,000 x 100	FrischNewtonQuantileRegressor	515x (62x against highs-ipm)	an interior point method (a weighted Gram and a Cholesky per iteration), then the vertex	QuantileRegressor by an interior point method
TruncatedSVD, sparse 200,000 x 200, 5% nonzero	GramTruncatedSVD	8.1x (15x against arpack)	X'X from each row's outer product (csr-gram)	Sparse X through the Gram matrix
GraphicalLasso, p = 50	CDGraphicalLasso	45x	--blas	GraphicalLasso, KMeans and RANSAC
HuberRegressor / LogisticRegression / PoissonRegressor, 200,000 x 100	LBFGSHuberRegressor / LBFGSLogisticRegression / LBFGSPoissonRegressor	22x / 15x / 10x	L-BFGS-B, --cuda	GPU kernels from the translator
LassoLarsIC, 200,000 x 100	GramLassoLarsIC	20x	the criterion from the Gram	Perceptron, passive-aggressive, ARD, LassoLarsIC
FastICA / GaussianMixture, 200,000 x 20	ParallelFastICA / EMGaussianMixture	6.7x / 3.1x	--cuda	GPU kernels from the translator
LogisticRegressionCV, 2,000 x 20 / LarsCV, 2,000 x 50	LBFGSLogisticRegressionCV / GramLarsCV	6.6x / 6.6x	the folds over one Gram, warm starts	GLMs, the cross-validated estimators
ARDRegression, 20,000 x 100	CovARDRegression	3.1x	X'X formed once (--derive derives it)	Loop-invariant products, derived
LinearSVC, 100,000 x 200	LinearSVM	1.9x	liblinear's solver in the subset	The SVM
NMF (cd), 20,000 x 1,000, 30	CDNMF	1.8x	derived (--derive --cublas)	NMF, derived

Using one in place of scikit-learn's

Most classes take the scikit-learn estimator's parameters under the same names (a subset of them) and have its fit / predict / transform, coef_, n_iter_ and so on, so an import is the change:

from scm2cpp_learn import LBFGSLogisticRegression as LogisticRegression

clf = LogisticRegression(C=1.0).fit(X, y)   # scikit-learn's iterations and coefficients

The ones that differ: CovLasso, CovRidge and DerivedLasso take the data in the constructor and solve a whole grid of penalties at once (fit_path / fit_path_batch, where scikit-learn loops Lasso(alpha=a).fit with fit_intercept=False); GramRFE takes the ridge penalty instead of an estimator (GramRFE(1.0, n_features_to_select=20) for RFE(Ridge(alpha=1.0), n_features_to_select=20), alpha=0 for LinearRegression). The package README's table of every estimator gives each class with its scikit-learn counterpart.

scikit-learn compatibility. From 0.14.0 the estimators derive from scikit-learn's BaseEstimator and mixins (scikit-learn itself stays optional), so clone, GridSearchCV, Pipeline and cross_val_score take them, and all 44 with a fit(X, y) pass check_estimator; each class that takes its data in the constructor has a fit(X, y) form beside it (GramLasso for CovLasso, DesignLasso for DerivedLasso, and so on). The cost is the input checks, from about 10 us per call to one pass over X; the package README's compatibility section has the measurements.

Inside another library. The same holds one level up: darts' LinearRegressionModel(likelihood="quantile") takes FrischNewtonQuantileRegressor in the place of scikit-learn's QuantileRegressor by one assignment (its fit 23x to 334x faster, the same coefficients), and examples/kernel-only/dtw.scm put under darts' dynamic time warping fills the same cost matrix 57x to 648x faster: Inside darts.

Installing

$ pip install scm2cpp-learn

platform	what pip installs
Linux x86_64 (glibc 2.28 or later)	a wheel, OpenBLAS inside
macOS 15 or later, Apple silicon	a wheel, OpenBLAS inside
Windows x86_64	a wheel, without BLAS (the loop variants: same answers, slower products)
anything else (Linux aarch64, Intel Macs, musl)	the sdist, built on install: needs a C++17 compiler

One wheel serves every Python 3.8 or later (the libraries are loaded through ctypes); each wheel is tested on install with Python 3.12, and the Linux one with 3.13 and 3.14 too. The wheels carry no GPU code: for the CUDA builds install from the sdist where nvcc is on the path (pip install --no-binary scm2cpp-learn scm2cpp-learn). Building the translator itself is docs/translator.md.

Against Intel's sklearnex

sklearnex (scikit-learn-intelex) accelerates some of the same estimators. On one core the package is ahead of it on every one compared but Ridge (LogisticRegression, PCA, SVC, SVR, RFE(Ridge): 1.4x to 106x; Ridge 0.8x). Given 20 cores each, with the package's loops under OpenMP and its products in MKL, it is ahead on Ridge (2.3x), PCA (1.4x to 1.6x), the device build of logistic regression (1.8x) and RFE (116x), level on logistic regression on the CPU, and behind on the SVMs (0.4x to 0.5x: SMO is one step after another). sklearnex is not scikit-learn's arithmetic (12 L-BFGS iterations to scikit-learn's 6, coefficients 6e-3 apart); this package's are. It has no lasso. The table and the conditions are in the package README.

To reproduce the comparison on Colab's machines in one click, open notebooks/compare-sklearn.ipynb with the badge at the top (a CPU runtime installs the wheel; a GPU runtime builds the CUDA paths too).

Not every case is faster: PCA at 50,000 x 500 and KMeans at large n run at or below scikit-learn's speed, and their sections say so.

First example: the lasso

pip install scm2cpp-learn and DerivedLasso(X, y).fit_path(lambdas) runs a lasso whose C++ the translator derived: the source is the naive residual-form coordinate descent (examples/kernel-only/lasso-design.scm, flat loops over X as numpy holds it, no Gram matrix anywhere), --derive turns it into the covariance form with the Gram matrix hoisted in front of the penalty path, and --blas / --cublas hand its three products to BLAS or cuBLAS. Nothing of it is written at the Gram level by hand, and nothing is prepared in numpy. On an RTX 4090 the cuBLAS build solves a 20-penalty path in 0.024 / 0.052 / 0.11 s at 5,000 x 1,000 / 100,000 x 200 / 100,000 x 500, against 0.100 / 0.236 / 0.759 s for scikit-learn's lasso_path(precompute=True) at its default tolerance on one core -- 4.2x, 4.5x, 6.7x; 2.2x, 4.5x, 4.0x when scikit-learn gets all 20 BLAS threads, since only its Gram product scales -- and the CPU build times the same as the hand-written CovLasso beside it. The table, the conditions and the differences against a tight reference are in python/scm2cpp-learn/README.md. Every rule of the derivation, in the order it fires, with links into the code, is in DERIVATION.md.

What the translation looks like

Unlike conventional Scheme compilers, which emit C intended only for a machine, Scm2Cpp gives Scheme values no runtime representation: an integer becomes a std::int64_t (an element of an integer array an int), a vector becomes a std::array<double,1025>, and (car x) becomes car(x). Types come from whole-program inference; what inference cannot pin down becomes a C++ template parameter.

(define (square x) (* x x))
(define (average x y) (/ (+ x y) 2.0))
(define (improve guess x) (average guess (/ x guess)))

becomes

double square( double x )                 { return (x*x) ; }
double average( double x, double y )      { return ((x+y)/2.0) ; }
double improve( double guess, double x )  { return average(guess,double((x/guess))) ; }

Documentation

• docs/lasso.md - the lasso in detail: the kernels, every lasso pip can install, cross-validation, the GPU batch, memory, calling it from Python
• docs/benchmarks.md - each estimator family against scikit-learn: the algorithm, the protocol, the full tables
• docs/translator.md - the translator itself: installing it, the command line and its options, the Scheme subset, the test suite, the Typed Racket cross-check, the runtime header
• python/scm2cpp-learn/README.md - the Python package: every estimator, the sklearnex comparison
• FILES.md - every source file's role in a line or two and the require graph between the Racket modules, grouped by pipeline stage; where a change goes (FILES.ja.md in Japanese)
• DERIVATION.md - how DerivedLasso is derived: each rule on the --derive --blas log line for lasso-design.scm, in firing order, with links into the code (DERIVATION.ja.md in Japanese)
• CHANGES.ja.md - a record of the modifications made to the historical code base, with the reason for each
• scribblings/scm2cpp.scrbl - the manual of the Racket interface (read-source-forms, scm2cpp-match-list, ...). Its examples are evaluated when it is built, so it is also a test: raco scribble --dest /tmp/scm2cpp-doc scribblings/scm2cpp.scrbl (with PLTCOLLECTS=$PWD/vendor: or rkanren linked) writes scm2cpp.html, and run-tests.sh builds it as doc-unit
• ideal/stream-ideal-new.cpp - the intended shape of the generated code for delayed streams, written by hand

Contributing

See CONTRIBUTING.md.

License

MIT License; see LICENSE, which carries the MIT terms and nothing else.

Several files derive from Aubrey Jaffer's Schlep and SLIB, and from utilities published in Paul Graham's On Lisp; vendor/rkanren is a bundled third-party library. These remain under their own permissive terms, which are reproduced in full at the head of each file. Those conditions are additional to the MIT terms and are recorded in NOTICE, together with the provenance and the measured extent of each derivation -- not in LICENSE, so that the licence file stays identifiable as plain MIT. Redistributors must honour them in addition to the MIT terms.

Citing

A paper describing the design is in preparation and is not in this repository yet. Until it appears, cite the repository and the commit you used; machine-readable metadata is in CITATION.cff.

The temporal feature selection behind the tfs- kernels (the moving-average designs, scm2cpp-tfs) is described in H. Niitsuma, An Extension of Temporal Feature Selection, Zenodo, 2026, doi:10.5281/zenodo.18909363.