[HN Gopher] Show HN: Lisp with GC in 436 Bytes
___________________________________________________________________
Show HN: Lisp with GC in 436 Bytes
Author : jart
Score : 110 points
Date : 2021-12-20 21:06 UTC (1 hours ago)
(HTM) web link (justine.lol)
(TXT) w3m dump (justine.lol)
| MaxBarraclough wrote:
| Very impressive.
|
| > SectorLISP uses what we call an ABC garbage collector and it
| took only 40 bytes of assembly.
|
| > [...]
|
| > Fast immediate garbage collection with zero memory overhead and
| perfect heap defragmentation is as easy as ABC when your language
| guarantees data structures are acyclic.
|
| Neat, but my understanding was that even pure functional
| languages can't generally make this guarantee, because things
| like _letrec_ complicate matters. If SectorLISP can take this
| approach, why doesn 't Haskell? (Or does it?)
| supergarfield wrote:
| Letrec requires either laziness (which implies some sort of
| internal mutability, as thunks get replaced by values at some
| point), or "internal" mutability that may not be visible to the
| programmer (like in OCaml, where in a `let rec` some variables
| will initially be null pointers, and get updated once other
| definitions have run).
|
| In languages with no mutability at all (not even internal
| mutability like with these two features), you can't create
| cycles and refcounting becomes possible, but I'm not aware of
| non-academic general purpose languages that actually fall in
| this category.
|
| Esoteric functional languages like Unlambda do make that
| guarantee, and implementations can use a ref counter as their
| GC.
|
| I've written more about this here:
| https://terbium.io/2019/09/cyclic-immutable/
| aidenn0 wrote:
| I mean even a doubly-linked list is a cyclic data structure...
| IsTom wrote:
| Strict purely functional languages will sometimes provably
| introduce log n slowdown that can't be amortized away. This is
| certainly a trade-off.
|
| This doesn't happen when you've got mutation or laziness.
|
| One language that I'm aware which makes this tradeoff is
| Erlang.
| __s wrote:
| Haskell does, https://wiki.haskell.org/GHC/Memory_Management
| WJW wrote:
| I'm pretty sure that Haskell supports cyclic data structures
| and that GHC garbage collection is more complicated than
| that. See for example the presentation by Ben Gamari over
| here: https://www.youtube.com/watch?v=EQqBpVRA3wU. Haskell GC
| is a generational copying design. Optionally you can enable
| the low-latency GC in newer runtimes, which is still
| generational and copying for the youngest generation but uses
| a parallel mark-and-sweep algorithm for the later
| generations.
| ridiculous_fish wrote:
| I believe Erlang makes this guarantee and exploits it in the
| GC:
|
| _...the terms are immutable and thus there can be no pointers
| modified on the old heap to point to the young heap_
|
| so old objects cannot refer to young objects. This means it
| doesn't have to deal with write barriers, etc.
| commandlinefan wrote:
| > BrainF#*k not a true language
|
| Curious why that might be, and TFA doesn't expound. What makes it
| not a "true" language?
| casion wrote:
| My "not so gracious" interpretation: "It would invalidate the
| claim that we wish to make, so... no true scotsman"
| roywiggins wrote:
| It's almost the opposite of a language, in that it's probably
| harder to do anything with than just using whatever the native
| assembly instructions of the machine are. It's explicitly
| designed to be annoying, an example of a Turing tarpit:
|
| https://en.wikipedia.org/wiki/Turing_tarpit
| jart wrote:
| Author here. You know it when you see it. LISP is a tool that
| people want to use. People write production software using it.
| For example, this website (Hacker News) was written in LISP.
| Languages like BrainFuck are usually only called programming
| languages if the word "esoteric" is attached. There's a real
| consensus of opinion around this this being a generally held
| view.
|
| There should ideally be a more compelling explanation of why
| Brainfuck is an esoteric toy and LISP isn't, than me simply
| saying "but that's what people believe". I considered going
| into more depth on this subject. I found a C to Brainfuck
| compiler written in OCaml and used it to compile a Brainfuck
| metacircular evaluator into Brainfuck. It ended up being 88,439
| bytes of code, and it sadly didn't work, because the compiler
| isn't very polished.
|
| Let's compare ratios. Brainfuck is 99 bytes, whereas Brainfuck
| written in Brainfuck is 88439 bytes. That's 893x larger. On the
| other hand, LISP is 436 bytes of systems code and LISP written
| in LISP is 1370 bytes of LISP. That's 3.14x larger. It's cool
| that the ratio between layers of simulation with LISP is pretty
| close to pi. It helps explain why LISP is viewed by human
| beings as being such a powerful tool, since it lets you
| accomplish more impact with less effort, without having the
| castles you build turn into a leaning tower of pisa. Since
| after all, the purpose of tools since prometheus has been to
| give people more power.
| tromp wrote:
| Would you consider binary lambda calculus [1] [2] a real
| language? The 650 byte interpreter written in obfuscated C
| also sports garbage collection and might fit in a bootsector
| when translated to x86 code. Its metacircular interpreter is
| only 29 bytes (232 bits), and looks somewhat readable with
| some syntactic sugar [4] (analogous to how x86 looks more
| readable as assembler source).
|
| [1] https://www.ioccc.org/2012/tromp/hint.html
|
| [2] https://tromp.github.io/cl/Binary_lambda_calculus.html
|
| [3] https://github.com/tromp/AIT/blob/master/int.lam
| shatteredgate wrote:
| To me it's missing the point to describe that as Brainfuck
| versus Lisp. It just turns out that lambda functions and
| linked lists are higher level abstractions than arrays and
| pointers. I'd like to see some more variations on that
| concept and what the size is if using another esolang that
| has lambda functions.
| redler wrote:
| As someone who is not a language expert, I find this a
| fascinating way to objectively (albeit without nuance)
| describe the relative expressiveness of different languages.
| shadowofneptune wrote:
| I would have to assume because it's neither a high-level
| language, nor a practical low-level one. True in the sense of a
| language being a labor-saving device.
| titzer wrote:
| This is such an awesome project! Writing interpreters in assembly
| is something of a lost art. That's part of the reason I wrote a
| Wasm interpreter in asm. I hope this does not _stay_ a lost art.
| Waterluvian wrote:
| This inspires me to craft a language just for fun.
|
| I absolutely LOVE projects that immediately build on themselves.
| I wrote a GameBoy emulator from scratch and without any
| prerequisite knowledge and it felt amazing because of how
| incremental it is: you can break it into thousands of sensibly
| sized pieces.
|
| I'm looking for the next project that's like that. At the moment
| it's an ECS video game.
|
| I think work is what makes me seek projects with really good
| feedback loops.
| Shared404 wrote:
| It is submissions like this that keep me coming back to HN.
|
| Even though I understand little of the OP, I understand more than
| last time, and have the hope to be able understand more in the
| future.
|
| Thanks for the inspiration OP!
| jjtheblunt wrote:
| this is awesome exposition (from someone who has implemented a
| small version of Scheme himself decades ago)
| dang wrote:
| Past related thread:
|
| _Show HN: SectorLISP now fits in one sector_ -
| https://news.ycombinator.com/item?id=29047584 - Oct 2021 (75
| comments)
___________________________________________________________________
(page generated 2021-12-20 23:00 UTC)