Show HN: Lisp in C#
github.com
github.com
I'm afraid I've been out of the C# loop too long to know what's fast and what isn't these days.
Now that maybe I have the attention of some serious C# nerds, any assistance in making this thing run faster would be much appreciated.
It's not terrible atm, given a managed host language, but I'm sure there are plenty of knobs left to turn.
See the benchmarks section in the README for more info, and the same benchmarks ported to Python in python/fib.py.
Oh, and there's some undocumented yet potentially useful stuff in /Libs; strings, terminal control and IO mainly.
Was: 686 98 1195
Now: 226 79 293 (with net9.0 preview: 201 70 269, another release another free >10%)
The reason for such a significant difference is that `ArrayStack<(int, int)>` only implements `IEnumerable<T>`, which prevented the Enumerable.Last(stack) call from seeing that the type has an indexer which can be used to quickly access the last element instead of traversing it in its entirety.
Now, it still requires JIT (or, in this case, compiler back-end and ILC) to reason about the actual type of ArrayStack to optimize away type tests, inline Last() call and devirtualize indexer access, but the better option is simply replacing it with just [^1] which does the same on any indexable type.
Generally speaking, it's recommended to use out of box collections whenever appropriate like Stack, List, etc. which already implement all the necessary interfaces which the standard library takes advantage of unless there's a specific need to do otherwise.
Also, it is always nice to have .net's aot emit "canonical" native binaries, so it took me about 45s to find the bottleneck by bumping up the numbers in benchmarks.sl and clicking "Sample" in macOS's Activity Monitor.
All in all, the code in the project is terse and thanks for showcasing it!
I'll have a look later, the only part I didn't get was [^1], could you elaborate?
About the ArrayStack, I wanted a stack backed by a fixed array, because my suspicion was using a fixed array for fundamental collections would be faster. Hence the VM.Config object to set the max sizes.
There is also a DynamicArrayStack that supports reallocation, which is currently used by OrderedMap.
The plan is to eventually benchmark the alternatives, but start with the simplest thing that could possibly work.
Internally, `.Last()` will try to optimize for the common cases where a type implements `IList<T>` and uses an indexer to simply get the last element. However, because ArrayStack<T> does not implement IList<T>, .Last() does not know that this is possible, therefore costs O(n) as noted above.
Instead, we can simply use an index operator `[^1]` which gets the first element from end, which is short-hand for `[stack.Count - 1]`.
Other than that, it’s a good idea to lean towards out-of-box tools to avoid investing effort into reinventing another language within C# and use spans for slicing data types - you almost never need to call methods like Array.ConstrainedCopy - this is something quite ancient. The idiomatic way of copying a portion of array today is `source.AsSpan(start, length).CopyTo(dest)`, slicing destination as well if you need so. The prime slice types in .NET are Span<T> and ReadOnlySpan<T>, and can wrap memory of any origin.
I'm not well versed on this topic.
For large amounts of trash in project you would need to look for other languages, like JS ecosystem or certain Java-related projects :)
Ah, someone should just come up with a huge file so we can ignore every possible combination at this point :)
> like JS ecosystem
Heh, JS is probably the language that generates the least trash by default as it's just a index.html file + your single JavaScript file, nothing else required or generated at all, and now you have a interactive website :)
(This is what is used to populate the templates if you ask GitHub to include a gitignore when creating a new repo, or if you add a new file to a Repo and name it .gitignore and get the template selector to show up.)
I believe `dotnet new gitignore` basically shares the same template, even, as this file: https://github.com/github/gitignore/blob/main/VisualStudio.g...
Like why is there a `.DS_Store` (which is specific to macOS) in the `core.gitignore` file? That belongs in the global `.gitignore` macOS users should have in their home directory, rather than including it in project specific .gitignore.
But I digress, not exactly a huge problem and I won't lose any sleep over it :)
We just roughly doubled the speed by changing one line of code, that means there's plenty more fun before it gets really tricky.
My issue isn't really profiling, its not knowing enough about the platform to do anything constructive with the hot spots.
(and /lisp/ has an index if you want to see the other random lisp-related stuff I've collected copies of so I can find it again later)
Have you considered making it compile to IL? Or if not that, using the Roslyn API to compile it to C# which is then automatically faster as a result of being compiled. Then getting AOT (ahead-of-time compilation) at build time gives you improved perf basically for free.
I see neon has contributed a perf change, I know that he's an expert at using https://github.com/dotnet/BenchmarkDotNet so hopefully you'll be able to do some scientific tests soon.
I would love to see another language here for the *Common* Language Runtime (CLR, the core of .NET).
And AOT isn't a lot of free perf; it's mostly equivalent to JIT, the big advantage is faster and smaller startup.
(I have used the Roslyn compile API; it's pretty cool but you do have to do more setup. e.g. https://joshvarty.com/2016/01/16/learn-roslyn-now-part-16-th... )
Parsing is a one time thing though.
Yes, different levels of compiling to C# are definitely on the table as options; for performance, but also to hopefully be able to generate self contained executables.
Even just generating my own bytecode for faster startup.
I tried to compare some script languages implemented in C# with Roslyn script compilation. Same code to sum up 1M doubles. Roslyn takes almost 100ms to compile the code.
This may become especially painful when source code changes on every execution and reusing compilation result is not possible for some reason, e.g. user input or parametrized string template.
I don't much like the odds of Lisp vs. Nintendo hardware kickstarters.
Curious though, I'm pretty sure it emits MSIL rather than its own bytecode like sharpl? So that would be one difference, in most cases an advantage because of performance.
The other obvious difference is I'm not aiming for any standards, quite the contrary; this is about being so fed up with the alternatives (including Scheme) that spending the rest of my life getting it just right looks like a reasonable deal.
I wrote a lisp in C# based on that, it was only a 100+ ish lines of code. It was a great way to get into Lisp.
I started out designing Forth interpreters, actually calculators and template engines, but Forth was a natural progression.
My design differs a lot from idiomatic Lisp implementations (likewise Forth), and I do sometimes wonder what it would look like if you started in that end and worked your way towards supporting all the features of sharpl.
The initial expansion is often pretty sloppy.
I don't do many source transformations, everything is designed to emit pretty optimal byte code on the first pass.
I just went through it over 2-3 days, great practice IMHO to do once in your life from start to finish: https://github.com/metaleap/go-lisp
I like to call that the emit phase, as in emitting byte code.
The interesting thing is that it only happens once, before the code is evaluated.
The general idea is to use both languages together, as complements; not calling one from the other.
https://github.com/codr7/sharpl/blob/main/src/Sharpl/Libs/Co...
Sure thing, VM.Eval("your code") returns a value if one is produced.
if (vm.Eval("1:2") is Value v and v.Type == Libs.Core.Pair) {
Console.WriteLine("Pair: " + v.Cast(Libs.Core.Pair));
}
So far there has been no shortage of more important features at the scale of programs it's currently viable for.
(reduce + (range 1 3) 0)
(^upto (n) (range 1 (- n 1)))
This concern brought to you by e.g. the great pain induced by the difference between
for x in "foo":
for x in "foo",:
It may turn out in practice that a lispy language and/or programmers who make different mistakes to me will make it not an issue ... but were it -my- project I'd probably comment out the iterator implementation for int and see if its absence annoyed me enough to decide it was worth bringing back.
(when perpetrating language myself I often find that some of my favourite bits of clever don't pass the 'annoyed me enough' test and end up as documentation examples or similar in the end instead ... hopefully you have better luck ;)
Some way of forming ranges is planned anyways.
My current thing in progress has basically all of its temptation points already spent because I decided I was going to make it fexpr based, but I'm very definitely having fun with that so far - "no special forms required" makes for some interesting possibilities.
(kernel-lisp and kernel-thesis in /lisp/ are worth looking at if fexprs sound interesting, though I'm on the pragmatics side of things and will not pretend I came anywhere close to understanding the $vau calculus part)
Yep, I've been on a ride down the fexpr implementation hole previously; which is another reason I've been delaying user macros; still processing the experience.
Writing perl as a programming language is, I find, a very different dialect, and perhaps amusingly one in which I rely on function composition, closures and block scoping heavily due to also loving lisp - javascript's 'let' behaves very similarly to perl's 'my' and I find it ... difficult ... to deal with python or ruby for any length of time since their scoping is "stuff randomly pops into existence at function scope" and, just, aaaaa.
Perl of course can't really have macros, but it does have the ability to define custom (also block scoped :) keywords which can allow one to achieve similar results - see e.g. https://p3rl.org/Keyword::Declare for a demonstration built on top of that functionality (there's also a code rewriter called Babble but I got distracted so while it works, it's woefully underdocumented, keep forgetting to get back to that).
I've always had a fondness for the "building the language up towards the problem" style of programming (I wrote the first ever proof of concept for custom perl keywords, though that code has happily long since been obsoleted by people who knew what they were doing) which has led me to 'fexprs for making DSLs' since those are usually building up a config structure or similar which makes fexprs' being tricky to optimise less of an obstacle.
(also with fexprs I don't have to limit myself to 'block in front' ala perl or 'block at the end' ala ruby/elixir (though it's amazing how much mileage elixir gets out of its macros, Kernel.ex is well worth a read if you're so inclined))
1> [mapcar list '(a b c) 10]
((a 10) (b 11) (c 12))
Or fixed it, depending on which way you lean.
It's also less inefficient, because the value has to be converted to an iterator object that knows about the range, and keeps track of the state.
In TXR Lisp, certain objects are self-iterable, like characters, numbers and good old conses.
1> (iter-begin "abc")
#<seq-iter: a031a10>
2> (iter-begin 3)
3
3> (iter-begin '(a b c))
(a b c)
4> (iter-more 3)
t
5> (iter-item 3)
3
6> (iter-step 3)
4
7> (iter-more '(a b c))
t
8> (iter-item '(a b c))
a
9> (iter-step '(a b c))
(b c)
10> (iter-more *1)
t
11> (iter-item *1)
#\a
12> (iter-step *1)
#<seq-iter: a031a10>
13> (iter-item *1)
#\b
You can see how for a list, iter-more is equivalent to (not (null ...)), iter-item is just car, and iter-step is just cdr.
There is also lazy processing in TXR Lisp. E.g. lazy mapcar which is mapcar*. The following will only read the first few lines of the syslog, returning instantly:
14> (take 3 [mapcar* cons 1 (file-get-lines "/var/log/syslog")])
((1 . "Jul 23 00:09:54 sun-go systemd[1]: openvpn@client.service: Service hold-off time over, scheduling restart.")
(2 . "Jul 23 00:09:54 sun-go systemd[1]: openvpn@client.service: Scheduled restart job, restart counter is at 1044619.")
(3 . "Jul 23 00:09:54 sun-go systemd[1]: Stopped OpenVPN connection to client."))But like I said, I'm not so sure there is a right way to interpret it any more.
In Lisps, we program syntax with different semantics regularly, so the plurality is part of the daily existence. (defclass a (b c)) and (list a (b c)) have the same shape, but are completely different things.
10 is a piece of syntax, but how do we assign its semantics when it is an argument to a parameter that expects a sequence? That is up in the air the same way. Is it an error, like in most Lisp-like languages? does it count up to 10 from 1? Below 10 from zero? From 10 ad infinitum?)
The choice becomes a paradigm in the language that everyone has to understand.
What is undesirable is inconsistencies. If certain functions counted up to the number, but others from the number, arbitrarily, that would be objectively worse than consistently doing one or the other.
[mapcar list '(a b c) [count-from 10]]
[mapcar list '(a b c) x]
OTOH if you've got the entire codebase in your head that isn't really an issue; it's coming back to tweak something a few months later where I usually find such features give me an unexpectedly ventilated foot :)
```lisp
(+ 1 2)
```
It's unfortunately enough of a bad fit for me to prefer no highlighting; my own fault, the price you pay for adding syntax.
Polyglot projects have been sort of a thing lately, because micro services made them doable I guess; but I feel the combination of a capable and portable host language and a scripting language implemented in that language captures the best of both worlds while adding nice super powers on top.
But it's not a circle, it's a spiral; we learn something new every time.
Evolution is messy, every combination has to be tried, every minor detail thoroughly investigated from all angles.