6 ms·
Show HN: Lisp in C#
- Olesya000 2y ago[dead]
- Zambyte 2y agoCool! I didn't get a chance to run it but I dug around the code a little bit. I noticed there is a Macro class, but no mention of macros in the README. Are macros working?
- codr7 2y agoWithin the host language for now, they more or less just need to be plugged in. So far there has been no shortage of more important features at the scale of programs it's currently viable for.
- codr7 2y agoAuthor here. 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.
- neonsunset 2y agohttps://github.com/codr7/sharpl/pull/1 https://github.com/codr7/sharpl/pull/1 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!
- codr7 2y agoNice work, thanks! 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.
- neonsunset 2y agoHere, calling `.Last()` on `ArrayStack<T>` traverses it from the start. `.Last()` is a static extension method defined on `System.Linq.Enumerable` class and has a signature `static T Last<T>(this IEnumerable<T> source)`. 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.
- codr7 2y agoJust the kind of information/expertise I was looking for, awesome!
- zebracanevra 2y agoAnd you can find that specilisation here: https://source.dot.net/#System.Linq/System/Linq/Last.cs,80 https://source.dot.net/#System.Linq/System/Linq/Last.cs,80
- codr7 2y agoBy all means, keep them coming people :) 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.
- mst 2y agoI don't know the platform and would -guess- that this won't actually help, but it's sufficiently fascinating I thought I'd share anyway: https://trout.me.uk/lisp/vlist.pdf https://trout.me.uk/lisp/vlist.pdf (roughly "stitching together efficient cons lists out of arrays") (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)
- codr7 2y agoInteresting, thanks.
- lloydatkinson 2y agoI haven't had chance to look over the code but I know that using Span for parsing might be a nice thing to try out. 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 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).
- pjc50 2y agoBit of a tradeoff there; so long as it's using its own bytecode, the sharpl executable itself can easily be AOT. Once you start trying to create your own assembly at runtime and run that, it's a LOT of work to get the host to still AOT (because you have to include the dotnet runtime anyway to run the inner assembly!) 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-the-emit-api/ https://joshvarty.com/2016/01/16/learn-roslyn-now-part-16-th... )
- codr7 2y agoSure thing, Span is one of the features I haven't had time to dig into yet. 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.
- WorldMaker 2y agoA fun middle ground to compiling to IL is using System.Linq.Expression<T> as a compiler. This was the middle ground that the "DLR" (Dynamic Language Runtime) used to great effect. System.Dynamic is still in the BCL and still useful, even though the dreams of IronPython and IronRuby and interop between them are sort of dead/dormant. System.Dynamic.DynamicMetaObject is still a fun thing to play with in how much power it gives you do some surprisingly optimized dynamic language things, all using System.Linq.Expression<T> as the higher level intermediate language than raw IL.
- keithnz 2y agoyears ago someone posted http://norvig.com/lispy.html http://norvig.com/lispy.html here on HN 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.
- codr7 2y agoYes, I am aware. 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.
- codr7 2y agoHaving thought a bit about it, one motivation for choosing the route I did; rather than the more idiomatic one; is that it relies on pipeline of source transformations to get to optimal code. 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.
- dualogy 2y agoThere's also Make-A-Lisp and, unlike most write-you-a-lisp/scheme-s out there, that one also covers TCO interpretation, quasiquotation/unquote for macros and their expansion, and goes up to self-hosting: https://github.com/kanaka/mal/ https://github.com/kanaka/mal/ 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 https://github.com/metaleap/go-lisp
- KineticLensman 2y agoConcur, although it took me two to three months, not days (was working full time is my excuse). Biggest grief point was getting macro expansion to work correctly; TCO worked almost first time, IIRC.
- codr7 2y agoIf only we could get a tiny Lisp loving push from the HN crew, wink, nudge. I don't much like the odds of Lisp vs. Nintendo hardware kickstarters.
- incanus77 2y agoI am here for it.
- davidelettieri 2y agoIt's worth mentioning https://github.com/IronScheme/IronScheme https://github.com/IronScheme/IronScheme
- codr7 2y agoRight, I recognize the name. 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.
- zczc 2y agoSo, it is a shortcut around the tenth rule: "Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp" [1] [1] https://en.wikipedia.org/wiki/Greenspun's_tenth_rule https://en.wikipedia.org/wiki/Greenspun's_tenth_rule
- codr7 2y agoObservant :) 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.
- pjmlp 2y agoYou mean rebranding distributed computing and OS IPC for newer generations?
- codr7 2y agoIt's the same old ideas, over and over again. But it's not a circle, it's a spiral; we learn something new every time.
- pjmlp 2y agoSometimes, and suddenly modular monoliths become a thing, as the microservices generation learns why we weren't doing SUN RPC, TOOL, DCOM and CORBA for every little piece of application functionality.
- codr7 2y agoWe could definitely do a better job of learning from those who came before, it would save a lot of time and effort. Evolution is messy, every combination has to be tried, every minor detail thoroughly investigated from all angles.
- healeycodes 2y agoYou can annotate the code blocks in the README to get generic lisp syntax highlighting. ```lisp (+ 1 2) ```
- codr7 2y agoThanks. It's unfortunately enough of a bad fit for me to prefer no highlighting; my own fault, the price you pay for adding syntax.
- mst 2y agoSeparate from anything else, I'm ... concerned ... at the idea of ints being iterable, because it seems like something I'd be much more likely to invoke accidentally than intentionally and then wonder wtf my program was doing. I'd prefer to have to write something like (reduce + (range 1 3) 0) and if you find yourself wanting the natural number iteration regularly maybe (^upto (n) (range 1 (- n 1))) as sugar. This concern brought to you by e.g. the great pain induced by the difference between for x in "foo": and for x in "foo",: in python, for example. 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 ;)
- codr7 2y agoNoted, I feel like I need more use cases and experience to say for sure. Some way of forming ranges is planned anyways.
- mst 2y agoYeah, 'int is iterable' triggered "oh that's cute!" immediately followed by "... and the exact sort of cute I often find irresistably tempting myself and then regret later." 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)
- codr7 2y agoA certain level of helpfulness is nice though, Ruby and to a somewhat lesser extent Perl get that part right. I guess Perl could be seen as a warning example of what happens if you go all in. 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.
- default-kramer 2y agoCool, thanks for showing. Are you planning for any sort of FFI/interop in either direction? I don't see it in your TODO, but I also don't understand why you would write it in C# unless you had this in mind.
- codr7 2y agoGiven how easy it is to expose functionality from the host language using existing facilities [0], and how complicated a reflection based FFI could get; I would rather not, at least not right now. It's also one of those decisions that will drastically limit my choices for future evolution of the implementation. 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/Core.cs https://github.com/codr7/sharpl/blob/main/src/Sharpl/Libs/Co...
- default-kramer 2y agoAh, this is actually what I had in mind by "interop". So from C# I can evaluate some Lisp code and then test that the result is `PairType` (for example)? Maybe this is so obvious it goes without saying, but I didn't see any examples of that.
- codr7 2y agoI understand. 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)); } Have a look in the main Program.cs to see how to get a VM up and running.
- coder94 2y agoThere's also Clojure CLR (lisp) https://github.com/clojure/clojure-clr https://github.com/clojure/clojure-clr
- codr7 2y agoYeah, I admire Rich Hickey a lot, it took a lot of guts; and I learned a lot from Clojure and his talks; but I unfortunately find the language a bit too opinionated and dogmatic.