[HN Gopher] Crunch - a Scheme compiler with a minimal runtime
___________________________________________________________________
Crunch - a Scheme compiler with a minimal runtime
Author : sjamaan
Score : 154 points
Date : 2024-12-17 12:18 UTC (10 hours ago)
(HTM) web link (www.more-magic.net)
(TXT) w3m dump (www.more-magic.net)
| nudpiedo wrote:
| so if I understand this right, it could be a way to run scheme on
| esp32 and similar microcontrollers, isn't it?
|
| Also its small size would make it a perfect target to compile to
| typescript/deno/wasm without rejecting the s-exp power and
| runtime possibilities in its full chicken code at the backend...
| f1shy wrote:
| Not in the way I would like: you cannot have a REPL running.
| Seems only a transpiler for R7 Small.
| davexunit wrote:
| It's compiling a subset of Scheme that can be statically
| typed. It's not for full-blown live-hackable Scheme programs.
| You'd use Crunch or PreScheme to implement things that you
| can't implement in Scheme, like a garbage collector. I don't
| know if Crunch has this feature, but with PreScheme you can
| run your PreScheme programs at the Scheme REPL so you can
| have your comfy REPL-driven dev environment and then create a
| static executable when you're ready.
| soegaard wrote:
| There are specialized Scheme implementations that aim to be
| small.
|
| A recent paper (see also the presentation on YouTube):
|
| Leonard Oest O'Leary, Mathis Laroche, and Marc Feeley A R4RS
| Compliant REPL in 7 KB
|
| For systems with a C compiler:
|
| Vincent St-Amour and Marc Feeley. PICOBIT: A Compact Scheme
| System for Microcontrollers. (This one got a best paper award).
|
| Finally, there is also PICBIT available for PIC
| microcontrollers:
|
| PICBIT: A Scheme System for the PIC Microcontroller
| cardanome wrote:
| Not a scheme, but for running a lisp on microcontrollers uLisp
| is pretty amazing. http://www.ulisp.com/
|
| You even get a REPL and everything WHILE running on the
| hardware. Super easy to set up and get going. Though as it is
| interpreted so you will of course not have native performance.
| Still very useful for prototyping and hobbyist projects.
| retrac wrote:
| As a rule, interpreted code has a smaller memory footprint
| than natively compiled programs.
|
| Even interpreted on a several hundred MHz classic RISC
| microcontroller, Lisp will chew through a million cons cells
| a second or more - an order of magnitude or so faster than
| the old Lisp machines in the 80s were and they used to run
| giant CAD systems on those to design aircraft and stuff.
| (Albeit slowly...)
| int_19h wrote:
| OTOH if you want something that gives you a REPL and
| everything directly on the hardware but is also not as slow
| as your typical interpreter, look at Forth.
| davexunit wrote:
| I'm glad to see more projects exploring the statically compiled
| Scheme space. One difference from PreScheme listed is R7RS
| conformance, but the PreScheme restoration project is also
| targeting R7RS so that the compiler is portable to many Scheme
| implementations. The biggest difference I can see is manual
| memory management vs. reference counting. Though, one of the TODO
| items for the PreScheme restoration is to revisit memory
| management. Maybe PreScheme will end up with reference counting,
| as well.
| fouric wrote:
| For Common Lispers such as myself, who are vaguely aware of
| developments in the Scheme space: the most important difference
| between CRUNCH and Chicken appears to be that, while both compile
| down to C/object code, CRUNCH is additionally targeting a
| _statically-typed_ subset of Scheme.
|
| Opinion: this is great. The aversion of Lispers to static types
| is historical rather than intrinsic and reflects the relative
| difference in expressiveness between program semantics and type
| semantics (and runtime vs tooling) for much of computing. Now
| that types and tools are advancing, static Lisps are feasible,
| and I love that.
| diggan wrote:
| > Now that types and tools are advancing, static Lisps are
| feasible, and I love that.
|
| Haven't that been feasible for a pretty long time already?
| Judging by how well-received (or not) they've been, it seems
| there isn't much demand for it. Things like clojure.spec and
| alike (compile-time + run-time typing) seems much more popular,
| but isn't static.
| nesarkvechnep wrote:
| There isn't much demand for Lisps in general.
| stolen_biscuit wrote:
| I think given the sheer amount of them that is demonstrably
| false
| cjaybo wrote:
| Many have been created, but how many have significant
| usage?
| jnxx wrote:
| What are the main differences between OcamML and a statically
| typed Lisp?
| packetlost wrote:
| Type inference is probably the biggest thing. You would need
| explicit "phases" to expand macros, disallow macro expansion
| at runtime, and implement bi-directional type inference HM-
| style to get even close to what OCaml has.
|
| To be honest, I'd kill for a Lisp that had the same type
| system as OCaml, but I suspect the closes we'll get is
| basically Rust (whose macro system is quite good).
| shawn_w wrote:
| Racket has Typed Racket, which while not Hindley-Miller can
| do some type inference.
|
| There's also the plait language which says its type system
| is similar to ML: https://docs.racket-
| lang.org/plait/index.html
|
| And Hackett, inspired by Haskell: https://lexi-
| lambda.github.io/hackett/
|
| And Common Lisp has coalton: https://coalton-
| lang.github.io/
| packetlost wrote:
| Most of those aren't really ready for production use
| except maybe Typed Racket, which I consider to be too
| "weak" and took a route with annotations that I'm not a
| fan of. Coalton is very interesting, I've been following
| it for a bit. Carp [0] is another one that I've been
| following.
|
| [0]: https://github.com/carp-lang/Carp
| reikonomusha wrote:
| Coalton is used in production for quantum computing
| systems and soft real-time control system automation.
| There are also (a small number of) Coalton jobs.
| packetlost wrote:
| Quantum computing control systems is _exactly_ the domain
| I 've spent about half a decade doing, it's really not
| the production-like environment you think it is. Speed of
| iteration and flexibility to allow for changes to
| hardware is tantamount to success. It's also a lot easier
| to accept risk to breakages in the language when the
| author works at your company too.
| PittleyDunkin wrote:
| It's also pretty straightforward to use multiple coding
| styles in the lisps in question, regardless of the typing
| being static or not.
| norir wrote:
| There is a simpler solution than type inference to removing
| type annotations while retaining types: remove the
| distinction between variable and type names. The way that
| you handle multiple instances of a type is to define an
| alias for the type. In pseudocode it might look like:
| type Divisor Number def divide(Number, Divisor) =
| Number / Divisor
|
| As compared to: def divide(number: Number,
| divisor: Number) = number / Divisor
|
| I have implemented a compiler for a language that does this
| with different (less familiar) syntax. It's a bit more
| complicated than described above to handle local variables
| but it works very well for me.
| wbl wrote:
| The module and functor system. Also macros are much more a
| Lisp family thing.
| dokyun wrote:
| I don't believe it's not intrinsic. A lot of the reason why
| Lispers may be averse to static types is because of the
| perceived inflexibility it can induce into the system. Lisp
| programmers don't want to be told what to do, especially by the
| compiler. Some CLs like SBCL have allowed some form of
| inference through the standard type declarations in the
| language. This leads me to believe that the 'right thing' in
| the case of Lisp is a combination of dynamicity and some
| stronger typing features that can be applied during the
| optimization stage. The dynamic nature and ease of use of Lisp
| relative to its performance is one of its greatest assets: it
| would be nearsighted to try and sacrifice that--a good Lisp
| programmer can optimize the important parts of his programs
| such that they're comparable to or even outperform their
| equivalents in other more ``high-performance'' languages. With
| that being said, these developments might bring us closer to a
| ``sufficiently smart compiler'' that could make that latter
| stage mostly unnecessary.
| Imustaskforhelp wrote:
| Interesting since this can compile down to C code , I was
| thinking maybe we can convert this to cosmopolitan c code as
| well?
| Imustaskforhelp wrote:
| that is to make it so that a single executable can on
| everything
| kristjansson wrote:
| You would just need to (configure this tool to) compile the
| resulting C with cosmocc, no?
| VyseofArcadia wrote:
| I believe the domain name is a reference to this anecdote
| https://www.catb.org/jargon/html/magic-story.html
| JonChesterfield wrote:
| The make && make install doesn't create the chicken-crunch
| executable which is used in the examples, nor do I see 'crunch'
| in any of the build scripts. Any guesses?
| dieggsy wrote:
| The installation bit mentions doing:
|
| > <install location>/bin/chicken-install -test crunch
|
| Edit: That's because this is an "egg", which is an external
| library/package not part of the core chicken install
| JonChesterfield wrote:
| Ah yes, the test runner leaves the new binary under bin.
| Thanks
| jxy wrote:
| > No support for first class continuations
|
| I'm not sure about how people would feel about this. I have mixed
| feelings. It feels like a loss of many things. What are the gains
| from ditching continuations?
| mst wrote:
| Given the intent to have relatively straightforward C code and
| a tiny runtime, you pretty much _have_ to ditch them or you 're
| not going to get anywhere at all.
|
| Plus honestly most of the uses of continuations that would make
| sense in the sort of relatively low level code this is aimed at
| can be built out of a few special purpose macros (and possibly
| a small amount of crying) - scheme code tends to lean on first
| class continuations for a lot of things that don't really need
| them, Because It Can.
|
| e.g. Paul Graham's On Lisp shows how to build (a subset of)
| continuations out of macros, and getting something like
| clojure's 'recur' out of that would probably give you simpler
| macros than pg's code uses.
| soegaard wrote:
| From the article:
|
| > What is needed is a small, portable compiler that generates
| more or less "natural" C code with minimal dependencies and
| runtime system that supports at least the basic constructs of
| the language and that puts an emphasis on producing efficient
| code, even if some of the more powerful features of Scheme are
| not available.
|
| Since C doesn't support continuations, it is not possible to
| have continuations and at the same time generate "natural" C
| code.
|
| Consider how you would implement first class continuations.
| It's not possible to do CPS transformation (given the goal of
| natural code generation) - since that's a whole program
| transformation.
| sctb wrote:
| > Since C doesn't support continuations, it is not possible
| to have continuations and at the same time generate "natural"
| C code.
|
| Since CHICKEN actually does this, I'll add the proviso of
| "without a GC or costly runtime".
| soegaard wrote:
| I would call the code CHICKEN generates for "direct style"
| not "natural". (I know - it is a cop-out to use "natural"
| in quotes)
|
| Regardless of what we call the style, it isn't _simple_ any
| more.
|
| For people interested in the internals of Chicken Scheme (I
| suspect sctb already knows):
|
| https://www.more-magic.net/posts/internals-gc.html
| davexunit wrote:
| It's fine because this is a static subset of Scheme that you
| could use to, say, implement a runtime for a full Scheme. As a
| Scheme programmer, it feels nice to be able to implement your
| Scheme in something very close to Scheme instead of having to
| use C.
| neonscribe wrote:
| First-class continuations remains the hardest nut to crack to
| implement any full specification of Scheme, especially if
| performance and/or compactness and/or simplicity of
| implementation and/or integration with other languages (C, C++,
| Java, etc.) is a priority. Scheme--, a subset with only
| downward continuations, i.e. continuations that could be
| implemented using only C setjmp and longjmp or equivalent,
| would still be an extremely useful language, but it is much
| harder to gather a community for such a project.
| rollcat wrote:
| The interesting part is how few trade-offs had to be made to make
| GC-less (ref-counting) Scheme-to-C compilation attainable, and
| how closely CRUNCH adheres to R7RS.
|
| Notable is the lack of call/cc, but in my "armchair expert"
| opinion, it's the ugliest part of the language. Yes,
| continuations as a first-class object are elegant and succinct,
| but in order to do anything _actually useful_ with them (like
| implementing exceptions), you need library code, which makes them
| much less composable.
|
| I think there's a much more pleasant and practical language
| lurking somewhere between R6RS "big" and traditional "small"
| Scheme, but I feel it would take a BDFL to flesh it out.
|
| (Meanwhile, back to fixing my init.el.)
| wbl wrote:
| Delineated continuations might help
| michaelsbradley wrote:
| delimited
| ta8645 wrote:
| The very first rudimentary standalone example:
| (define (main) (display "Hello world\n"))
|
| Doesn't compile, but instead gives error:
| Error: main: global variable `scheme#display' has unknown type
| JonChesterfield wrote:
| The popcount example does compile, if you drop the "assume"
| form, (import (chicken bitwise) (chicken
| fixnum)) (define (popcount32 x) ; From "Hacker's
| Delight"
| ; (assume
| (let ((x (fx- x (bitwise-and (arithmetic-shift x -1)
| #x55555555)))) (let ((x (fx+ (bitwise-and x
| #x33333333) (bitwise-and
| (arithmetic-shift x -2) #x33333333)))) (let ((x
| (bitwise-and (fx+ x (arithmetic-shift x -4)) #x0F0F0F0F)))
| (let ((x (fx+ x (arithmetic-shift x -8))))
| (let ((x (fx+ x (arithmetic-shift x -16))))
| (bitwise-and x #x0000003F)))))))
|
| Turns into somewhat redundant C, looks much like transliterated
| bytecode, e.g. long v17 = 0; // ...
| // popcnt.scm:7
| v17 = 0; // ... // popcnt.scm:7
| v17 = (t37 & 252645135); // popcount32
| // popcnt.scm:8
| t40 = crunch_arithmetic_shift(v17, -8);
|
| Interesting find in the (small) crunch.h is
| #ifdef CRUNCH_FREESTANDING #include <inttypes.h>
| #include <stdarg.h> #include <complex.h>
| #include "crunch-environment.h" #else // loads
| of stuff
|
| though I haven't found crunch-environment.h in the source yet
| tines wrote:
| The nice thing is that you can emit pretty sloppy C and the C
| compiler will optimize it pretty well.
| soegaard wrote:
| The documentation for Crunch is here:
|
| https://wiki.call-cc.org/eggref/6/crunch
| iainctduncan wrote:
| This just made my day. I'm the author of Scheme for Max, an
| extension to the Max music programming environment that puts the
| s7 Scheme interpreter in it for scripting note-event level code
| (not dsp). It would be fantastic to also be able to use a subset
| of Scheme for generating DSP level code, where speed would be
| more important than dynamic typing or continuations/tco/etc.
|
| I will be watching this closely!
| jnxx wrote:
| what do you think about pre-scheme?
| iainctduncan wrote:
| I haven't tried it, but I'm curious and interested!
| JonChesterfield wrote:
| > Other targets are possible, like GPUs. I don't know anything
| about that, so if you are interested and think you can
| contribute, please don't hesitate to contact me.
|
| The freestanding macro suggests most of the heavy lifting is
| done. Stuff the GPU targets will struggle with in no particular
| order:
|
| - setjmp / longjmp
|
| - signals (if used?)
|
| - threads
|
| - fast alloc/free
|
| - stack will be smaller than chicken expects
|
| I don't know how to do signals. The rest are merely difficult.
| outworlder wrote:
| > - setjmp / longjmp
|
| Isn't that mostly needed by call/cc, which is not supported by
| Crunch?
| JonChesterfield wrote:
| I thought chicken used it to treat the C stack as an arena
| for the GC, with longjmp acting as part of garbage
| collection. I don't see how it would help for call/cc, that
| needs a reified stack to handle repeat invocations.
| hassleblad23 wrote:
| This looks useful for sure.
___________________________________________________________________
(page generated 2024-12-17 23:00 UTC)