Chez Scheme: Lisp with native code speed
yakihonne.com
yakihonne.com
https://ecraven.github.io/r7rs-benchmarks/
A few years ago Racket switched to using Chez for its implementation. The lead for Racket (Matthew Flatt) seems pretty happy with the new Chez base: he and the team were able to reduce the total amount of code while at the same time improving performance. Here's the experience report from a few years ago:
https://en.m.wikipedia.org/wiki/Larceny_(Scheme_implementati...
Are you trying to make a (crime) racket/larceny pun? From what I've heard, they named it Racket because a racket is an organized group of schemers.
Anyway, would have been nice for the article to link to Chez Scheme's project page, which seems to be this one:
https://github.com/cisco/ChezScheme
Also not clear why should folks use Chez? The article barely covered the why or what successful apps have been written in Chez.
YakiHonne is a Nostr-based decentralized content media protocol, which supports free curation, creation, publishing, and reporting by various media.
https://yakihonne.com/article/naddr1qq2njnfcdpsngu3sdev4wjn3...
I was hoping to find that information on the site itself, I was looking for an about page or similar. Couldn't find it. Hence why it was confusing for a first time user. Or maybe I just missed it.
Apparently Racket Chez will merge into Cisco Chez and all will be well.
[0] https://sbcl.org
It's a cultural oddity how strongly people seem to associate them with interpreted code.
If you want native code from Scheme, using Gambit.
User didn't want to talk about Common Lisp.
Other user pointed out that the title of the article says "lisp".
My comment points out that the article also says "scheme".
Scheme is a Lisp. Not all Lisps are Scheme.
Hope that clarifies.
Chez Scheme has a few interesting features that most compilers do not have, for any language:
"A source file can also be precompiled into a stored binary form and automatically recompiled when its dependencies change. Whether compiling on the fly or precompiling, the compiler produces optimized machine code, with some optimization across separately compiled library boundaries. The compiler can also be directed to perform whole-program compilation, which does full cross-library optimization and also reduces a program and the libraries upon which it depends to a single binary."[0]: https://cons.io
It compiles to C, and from that to binary program
Minor Gerbil version as an example. (export main)
(def (fib n) (if (fx<= n 1) n (+ (fib (fx- n 1)) (fib (fx- n 2)))))
(def (main) (display (fib 47)) (newline))
Compiled with gxc -O -exe -o gerbil.fib
Similar results on x86_64
Of course if you want something really fast you let a genius who knows the target system inside and out write some hand-optimized assembly, but for a program that only needs to run once (or that has no direct or indirect connection to an end user) Chez is roughly fast enough.
Meh, my genius works at electro magnetic level. His mum works at the quantum level but she is outside our budget
On carefully-written programs on some domains with full optimization, both Chez and Gambit have been observed to produce object programs that run at speeds comparable to those of their C equivalents. This isn't new. I think it was Guy Steele who observed circa 1970 that some Maclisp programs ran faster than Fortran equivalents.
1) Clojure is secretly a compiled language. A lot of routine errors in Clojure dev are compiler errors.
2) Clojure aims for super-native performance. Immutability in practice gives weird benefits. The obvious example is copying a large object but making a small change. As a native operation in C that is very expensive. In Clojure, the cost is roughly equivalent to the cost of making the small change, because the structure of the big object can be safely reused (everything is immutable, why not?). It enables completely different styles of coding, it is a very practical benefit of Clojure.
Most operations on clojure persistent data structures are an order of magnitude less efficient than they are on the mutable equivalents, excepting a full copy which free due to it being unnecessary.
It's not really clear what you mean by "order of magnitude" here. The notation you're using suggests that you're thinking in terms of asymptotic algorithmic resource requirements, which are most often characterized by polynomial degree; an order of magnitude ("factor of 10") is invisible in those terms.
But a factor of log n, while not invisible, is nearly so. If you're thinking in terms of polynomial degree, a factor of log n is literally an infinitesimal value - it's more than 0, but less than all positive real numbers.
But this doesn't apply to hashset because hashmaps are sparse, and stored as pairs, meaning that they're effectively base 16. Also the clojure implementation of sets is just hashmaps where the key is the same as the value.
Technically true, but only because a change to a vector of under 32 elements is O(1) by definition (as long as the algorithm is deterministic) and O(n) includes O(1). It's equally true that a change to a vector of under 32 elements is O(n!).
The notation you're using is not meaningful in the context of bounded input. Big-O notation is not concerned with any behavior except the behavior at infinity.
Also, the point about logarithmic time is that it grows much more slowly than even linear time: log2(128) is only 7, and log2(1024) is only 10.
That isn't good usage, but there was enough context in your comment to guess that that was what you meant.
The main problem I was pointing out is that the difference between O(log n) and O(1) is much, much, much, much, much, much smaller than the difference between O(log n) and O(n), so it doesn't make sense to describe those two differences the same way.
Mostly we worry about algorithms that can run in polynomial time. It's easy to show that when m < n, xᵐ = o(xⁿ), and that when a polynomial's degree is n, the whole polynomial is O(xⁿ), and this leads us to divide up the polynomial-runtime space according to the degree of a representative polynomial. It's very normal to talk about "linear" time requirements -- meaning ϴ(x¹), "constant" requirements [ϴ(x⁰)], "quadratic" requirements [ϴ(x²)], "cubic" requirements [ϴ(x³)], etc. (OK, it's less common to talk about higher degrees, but the concept stays relevant there.)
So once you're thinking that way, you can ask where the function f(x) = log x belongs. It isn't a polynomial, but it is asymptotically limited by polynomials and so it's present within the polynomial-runtime space. If you represented the growth rate of the function f(x) = log x by a polynomial approximation, F(x) = xᵏ, what would the value of k be?
The answer is that k must be a positive value that is greater than zero but less than all positive real numbers, an infinitesimal. If you're calibrated against polynomials, a logarithmic time requirement is "not constant, but so close to being constant that it's impossible to see the difference".
(Note that if k is not an integer this isn't really a polynomial.)
Also, if you care about that then you can use transients (if no one knows you mutated the data structure then it still counts as immutable) or mutable structures - both of which are pretty simple.