From Newsgroup: comp.lang.scheme
Hello comp.lang.scheme,
I have released Scm2Cpp, a translator from a subset of Scheme into C++
that a person can read and edit. It is written in Racket and is under
the MIT license.
https://github.com/niitsuma/scm2cpp
Conventional Scheme compilers (Stalin, Gambit, Chicken, Bigloo and
others) use C as a portable assembler and emit C with continuation
passing and tagged values, not meant to be read. Scm2Cpp goes the other
way: Scheme values get no runtime representation. An integer becomes
an int, a vector a std::array or a std::vector. Types come from
whole-program Hindley-Milner inference; whatever inference cannot pin
down becomes a C++ template parameter.
(define (square x) (* x x))
(define (average x y) (/ (+ x y) 2.0))
becomes
double square( double x ) { return (x*x) ; }
double average( double x, double y ) { return ((x+y)/2.0) ; }
The price is that only a subset translates. There are no union types
("a vector or #f"), arrays are flat vectors with explicit index
arithmetic, and loops are written with do or a named let.
For the past few months I have worked on deriving fast forms from
naive numerical Scheme. When a function declares its array shapes with with-arrays, --derive does the following:
- raises the loops to an array algebra;
- finite-differences the residual update of a coordinate descent
into a memo maintained by a Gram matrix hoisted out of the loop;
- turns products of arrays the loop never writes (and of gathers
from them by an index) into lookups in a table formed once, and
memoises pure calls that no contraction can express;
- folds the products into einsum-style contractions, which --blas /
--cublas lower to BLAS / cuBLAS calls.
Each derived program is checked against a Racket oracle to print the
same output as the original (the test data is dyadic, so both sides
print the same digits). With --cuda, loops that the dependence
analysis finds parallel are emitted as CUDA kernels.
With it I have written scikit-learn's estimators (lasso, ARD, LARS,
L-BFGS logistic regression, Gaussian mixtures, FastICA and others)
naively in Scheme, and the translated C++ is on PyPI
(pip install scm2cpp-lasso; no Racket needed where it is installed).
For example, on a lasso penalty path the cuBLAS build derived from the
naive residual form runs 4-7 times as fast as scikit-learn (RTX 4090; scikit-learn on one core).
I would be glad to hear comments on the design of the subset or on the
type inference. In particular, if there are shapes of code you find
hard to write in a subset without union types, please tell me.
Hirotaka Niitsuma
--- Synchronet 3.22a-Linux NewsLink 1.2