13 ms·
Show HN: Lisp with GC in 436 Bytes
- mlatu 5y agoI love it, but i think the video from "the oldskool pc" is a bit inprecise in claiming it brings everything necessary to implement features like reading off the disk: now maybe I have overlooked something but how are you going to put something into eax and then do int 80h? the only interupts in the codebase are 10 and 16, so i assume it is a challenge for the reader to implement anything that has to do with hardware, though a universal api to do interrupts would be nice in the core language
- jart 5y agoI think the Oldskool PC channel did a good job covering the topic. He started writing his own boot sector operating systems from scratch to make that video. When you do that, you start seeing something like SectorLISP more as a kit that lets you take these beautiful universal equations that John McCarthy discovered, and then you fill in the blanks yourself in terms of systems implementation details. SectorLISP isn't intended to be a shrink-wrapped solution (and The Oldskool PC channel has excellent videos about shrink-wrap too!) So I do think the video is accurate and I'm very pleased with how it turned out.
- mlatu 5y agoas i said i love it, its just, when he said everything was ready, i thought the function to trigger whichever interrupt you want was included in the 436 bytes, at least there is plenty room to implement something, again: i love it edit: there is always mr brown to help us out : http://ctyme.com/rbrown.htm http://ctyme.com/rbrown.htm
- jhallenworld 5y agoOverlapping functions... (saves 14 bytes...) Crazy, DNA uses this trick! "-Os" should search for possibilities here.. I'm wondering if such code breaks any CPUs. I could imagine that it could confuse the code translation that modern x86s do. I mean I bet they don't test this particular corner case...
- jart 5y agoThat's cool. I didn't know. It's nice how having fun hacking on boot sectors can help us discover things mother nature figured out a long time ago. Do you have links you could share where I could learn more about dna coding hacks? For example, I've been reading some of the stuff written by Bert Hubert (known for his work on PowerDNS) who got into biology recently and wrote blog posts like this https://berthub.eu/articles/posts/amazing-dna/ https://berthub.eu/articles/posts/amazing-dna/ > These comments are fascinating in their own right. Like C comments they have a start marker, like /*, and a stop marker, like */. But they have some more structure. Remember that DNA is like a tape - the comments need to be snipped out physically! The start of a comment is almost always indicated by the letters ‘GT’, which thus corresponds to /*, the end is signaled by ‘AG’, which is then like */. I don't know a whole lot about biology, but learning cool facts like that makes me wonder what would happen if those comment markers were used as parenthesis.
- MaxBarraclough 5y agoVery 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?)
- aidenn0 5y agoI mean even a doubly-linked list is a cyclic data structure...
- MaxBarraclough 5y agoSure, but presumably they can't be expressed in SectorLISP.
- __s 5y agoHaskell does, https://wiki.haskell.org/GHC/Memory_Management https://wiki.haskell.org/GHC/Memory_Management
- WJW 5y agoI'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 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.
- __s 5y agoPotentially cyclic values are statically known But yes, GCs have evolved in the past decade, so these things are subject to change
- commandlinefan 5y ago> BrainF#*k not a true language Curious why that might be, and TFA doesn't expound. What makes it not a "true" language?
- casion 5y agoMy "not so gracious" interpretation: "It would invalidate the claim that we wish to make, so... no true scotsman"
- not2b 5y agoLisp is a language that people actually use to get work done; Brainfuck isn't.
- casion 5y agoI suppose the humor was lost in my message.
- commandlinefan 5y agoWell… I believe it was James Gosling who said that there are two types of computer languages: “ones people complain about and ones nobody uses”. So if you’re complaining about Brainfuck then it must be a language people use by process of elimination ; )
- yellowapple 5y agoThis presumes that "ones people complain about" and "ones nobody uses" are mutually exclusive - and I'm reasonably sure that Brainfuck is clear evidence against such mutual exclusivity ;)
- gmfawcett 5y agoStroustrup, not Gosling. And I like your logic. :)
- klyrs 5y agoUnless your "work" is proving that a language is Turing complete. That is, to my knowledge, the only serious use of brainfuck.
- dang 5y agoPast related thread: Show HN: SectorLISP now fits in one sector - https://news.ycombinator.com/item?id=29047584 https://news.ycombinator.com/item?id=29047584 - Oct 2021 (75 comments)
- Shared404 5y agoIt 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!
- jart 5y agoAuthor here. I tend to learn best by doing, so I'd say the same thing. Each time I write one of these blog posts I feel like I understand LISP a bit more and it's my pleasure to share that knowledge. Thanks for your words of support!
- deleted 5y ago[deleted]
- psyc 5y agoIt’s submissions like this that keep me coming back to HN 3 times per day, in order to see such a submission 3 times per quarter.
- jjtheblunt 5y agothis is awesome exposition (from someone who has implemented a small version of Scheme himself decades ago)
- titzer 5y agoThis 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.
- ngcc_hk 5y agoConvert his into a wasm lisp perhaps? Just a suggestion. Both these attempts are crazily great.
- Waterluvian 5y agoThis 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.
- jokoon 5y agoI wonder if there are botnet/rootkits circulating that use such compact programming.
- userbinator 5y agoVintage computer viruses are definitely in this category of size optimisation. Not so much "modern" malware.
- jazzyjackson 5y agoI’m ignorant to such optimizations—-is the idea just to be small enough that your presence isn’t noticed stuffed into a exe/pdf file or are there other reasons a virus designer would want to create such small executables?
- userbinator 5y agoYes, that's correct. Being able to infect without increasing the length of infected files is an important point. https://en.wikipedia.org/wiki/Code_cave https://en.wikipedia.org/wiki/Code_cave
- jandrese 5y agoSome had to fit in a 512 byte bootsector. Size optimization was always a concern when dealing with floppy disks.
- jjice 5y agoEverytime I see this domain I know I'm in for a treat. I assume the Dev's name is Justine, and they're one hell of a programmer. Pretty sure Actually Portable Executables are from this dev as well, which are also incredibly interesting.
- jart 5y agoAuthor here. Thanks! The other projects I'm known for here on HN are: https://news.ycombinator.com/item?id=26271117 https://news.ycombinator.com/item?id=26271117 Redbean (2011) is a single file distributable web server. Here's a video of me giving a talk about it https://youtu.be/1ZTRb-2DZGs https://youtu.be/1ZTRb-2DZGs https://news.ycombinator.com/item?id=24256883 https://news.ycombinator.com/item?id=24256883 αcτµαlly pδrταblε εxεcµταblε (2020) lets you build c/c++/fortran/etc. code so that it runs on seven operating systems https://news.ycombinator.com/item?id=13769727 https://news.ycombinator.com/item?id=13769727 Operation Rosehub (2017) where I helped save a lot of people from an Apache security bug similar to Log4j issue today I like doing these projects because they all fit together so well into a consistent story. For example, a lot of these past projects were what helped to make SectorLISP better. Thanks to APE you now have a 20kb quickly deployable and embeddable LISP interpreter. Thanks to Redbean we're going to have an online pastebin service that'll let you publish SectorLISP gists in a few days, for example: https://lisp.pub/1 https://lisp.pub/1 Thank you Hacker News community for being so supportive and encouraging.
- Ericson2314 5y agoHow do I get you interested in the Nix ecosystem? It's a great sandbox for all sorts of portability and bootstrapping experiments.
- MonkeyClub 5y agoAwesome work, and very enjoyable to read, kudos! > αcτµαlly pδrταblε εxεcµταblε You mean ακτυαλλγ πορταβλε εχεκυταβλε?
- haakonhr 5y ago
- chubot 5y agoWow, when did the C-JavaScript polyglot thing happen? I don't recall that, and looking back on the October article, it doesn't mention that. What's the motivation for it? https://news.ycombinator.com/item?id=29047584 https://news.ycombinator.com/item?id=29047584 I would expect that to add a constraint that makes the code bigger, not smaller? Or I'm probably misunderstanding how the different variants of the interpreter work.
- jart 5y agoSectorLISP has always had a C implementation for explainability. It started off as ugly C because it was actually used to generate the assembly code for the first ~900 byte version. See https://github.com/jart/sectorlisp/blob/a561e031aec03270459f85e9038f7951798f7fd3/lisp.c https://github.com/jart/sectorlisp/blob/a561e031aec03270459f... and https://github.com/jart/sectorlisp/blob/a561e031aec03270459f85e9038f7951798f7fd3/lisp.h https://github.com/jart/sectorlisp/blob/a561e031aec03270459f... Once we reached 512 bytes I started deleting a lot of the C code since things like assembly macros weren't needed anymore, since the assembly was now being written by hand. https://github.com/jart/sectorlisp/blob/main/lisp.c https://github.com/jart/sectorlisp/blob/main/lisp.c Once I cleaned up the C code, I noticed that the entire program didn't use pointers at all! (Except of course to interop with Bestline, but that could be replaced with fgetwc() instead). That's when the idea occurred to me that, since it didn't use pointers, it was also technically valid JavaScript too. So I asked around on Twitter to see if anyone's done a C / JS polyglot before. I got some helpful tips from a code golfer in Estonia who experimented with the idea and he told me about the paragraph separator trick. https://twitter.com/angealbertini/status/1463755612345540611 https://twitter.com/angealbertini/status/1463755612345540611 So I updated the C code to hybridize the two: https://justine.lol/sectorlisp2/lisp.js https://justine.lol/sectorlisp2/lisp.js It's a shell script and a C program and it runs in the browser unaltered without needing to be compiled.
- machawinka 5y agoThis blew my mind.
- int_19h 5y ago
- dschulz 5y agoImpressive. Yet another disappointing reminder that, as a programmer, I'm not worth the salt of the food I eat daily.
- adamnemecek 5y agoDude, this thing is a toy of sorts and the author spent quite a bit of time on this. No reason to knock yourself down.
- glouwbug 5y agoAs someone who’s spent their career gluing react libraries together, something like this does make me wonder how good some people really are with computers. It’s all the same assembly instructions in the end
- jart 5y agoSometimes that kind of work has a lot of impact. For example, people at Google used to joke around about how they hire PhDs to write HTML, but it was important HTML. Just like I'm sure the React libraries you're gluing together are being used for important things. The work I'm doing right now is flashier, but I had to make a lot of personal sacrifices in order to be able to do it.
- quickthrower2 5y agoI think thats the rub these days. With such an impressive mountain of free and indeed proprietary software, the money is going to be mostly in how you glue it together to solve a problem for a business. Getting something in a low number of bytes is not rewarded when gigabytes of storage are so cheap. To create something that doesn’t fir this mould has to be more like a “recurse centre” project - a labour of love you have to finance yourself.
- Bost 5y ago> storage is cheap Sometimes. Sometimes not. The physical HW, i.e. RAM and HDD storage is cheap but price you pay for accidental complexity is high. E.g. when your non-tail-call recursive calculation eats away all available memory. And you need to persistently store the intermediary results - just a handful of long integers in a dbase. And that dbase must be set up and maintained. That means dealing with access rights, usernames, passwords, replication, backups etc. In every environment: prod, tests, on every development branch (separately!), etc. In another dimension, read / write operations mean yet more side effects to deal with. And on top of that, dealing with intermediary results means yet more accidental complexity in the source code. So no, the workaround for "the memory limitation problem" can be in fact the most expensive part of a project. And now imagine, the data grows day by day...
- anyfoo 5y ago>It left plenty of room to add a 40 byte garbage collector. Oh yeah. Who wouldn't splurge if you have a massive 40 bytes left. Beautiful.
- rackjack 5y agoCan't you define FORTH (or a subset of it) for some architectures purely in assembly, then use those functions like normal? I remember some file floating around on GitHub that showed how to do that. Anyway, amazing work as always!
- thechao 5y agoYes; this Lisp is entirely in machine code and smaller than SectorForth.
- int_19h 5y agoThat's how Forth is normally implemented (and what makes it so handy on a new platform that doesn't have any dev tools yet). Although there's a further difference between implementations that rely on an existing assembler to implement the native bits, and those that roll their own in a way that allows them to cross-compile themselves. As for the file, I suspect that you're referring to JonesForth, which is a heavily commented implementation of the first variety: https://github.com/nornagon/jonesforth/blob/master/jonesforth.S https://github.com/nornagon/jonesforth/blob/master/jonesfort...
- LennyHenrysNuts 5y ago
- jxy 5y agoOne biggest downfall of lisp is that people just call anything with parenthesized prefix notation "lisp".
- cmrdporcupine 5y agoDid you not read far enough to see that it runs a program (proof assistant) written for LISP 1.5 (1961)?
- bitcharmer 5y agoSerious question: who uses Lisp these days? Been in software dev industry for over 20 years. Never encountered a single project employing the language. There must be some reason Lisp is so popular on HN.
- stjohnswarts 5y agoI've seen some self reported “lisp pros” working every day on lisp projects, but they are pretty rare compared to c++/javascript/python/c# programmers. It usually sounds like they are senior people who get their choice of languages and/or consultants who write and maintain very custom stuff with long-term, loyal customers.
- Scaless 5y agoThe scripting language for Halo 1/2/3/ODST/Reach were based on Lisp. Halo 4 kept a similar syntax but got rid of the parentheses to be more BASIC-like. Halo 5 and now Infinite moved on completely to Lua. Halo 1 reference: https://andrew.gg/scripts/00reference.html https://andrew.gg/scripts/00reference.html Decompiled campaign scripts: https://github.com/Nibre/blamscript/blob/master/blamscript/halo_reach_xex/scenarios/m10/scripts/m10.hsc https://github.com/Nibre/blamscript/blob/master/blamscript/h...
- deleted 5y ago[deleted]
- karanbhangui 5y agoClojure is fairly popular on the JVM and the site you are on uses a lisp dialect named Arc. Though not popular as an industrial language, ideas from lisp have spread into javascript and front end dev
- retrac 5y agoGrammarly uses it for many of their services.: https://www.grammarly.com/blog/engineering/running-lisp-in-production/ https://www.grammarly.com/blog/engineering/running-lisp-in-p... Pathway Tools is a genetic database search/comparison tool (I think, it's a bit over my head) and powers the https://biocyc.org/ https://biocyc.org/ website. Both are pretty typical use cases. Back-end services dealing with heavy symbolic manipulations. I think the most common use of Lisp is to implement Lisp though. ;)
- rurban 5y agoThe short eval is standard amongst small lisps (see eg SICP), but the immutability which leads to the nice ABC GC (no RPLACD, no cycles, immutable strings) is practical. All other lisp liked one or our autolisp features: the very same immutability. Such a GC really is trivial and fast. Lot of temporary garbage, but only for a single op.
- deleted 5y ago[deleted]
- jart 5y agoAuthor here. Yes, but you have to use the extended 509 byte "friendly branch" version, in order to get error messages on undefined behavior. For example, if I mistype a variable name as "FUDGE" then it'll longjmp() out of the evaluator and print "?FUDGE": https://justine.lol/sectorlisp2/debugging.png https://justine.lol/sectorlisp2/debugging.png If we were to do that in the main branch, it'd get caught in an infinite loop. You can always define a higher-level LISP evaluator on top of it which has undefined variable reporting. So that doesn't make it a toy. Doing nothing on undefined behavior may be hostile and dangerous, but it's legal as far as optimizations are concerned. If what you said were true, then Clang and GCC would be toys, since they'll often exploit undefined behaviors to gain an edge in benchmarks, by generating code so that the world might end if an integer overflows. So one way you could think of it is the 436 byte version is your release branch and the 509 byte version is your dev branch. Both of which fit inside the 512 byte boot sector!
- LargoLasskhyfv 5y agoMind blown. I feel blind and mown.
- timonoko 5y agoMy great invention was that you dont have to collect all the garbage, only most of it. So I was assuming all the numbers on the CPU-stack were pointers to live cells. Never run out of memory because of this heresy. > (ncompile '(cons 1 (cons 2 3))) $09CB:$7163: MOV AX,$04 ; S-object 1 $09CB:$7166: PUSH AX $09CB:$7167: MOV AX,$05 ; S-object 2 $09CB:$716A: PUSH AX $09CB:$716B: MOV AX,$06 ; S-object 3 $09CB:$716E: MOV BX,AX $09CB:$7170: POP AX $09CB:$7171: CALL $05AE ; cons $09CB:$7174: MOV BX,AX $09CB:$7176: POP AX $09CB:$7177: CALL $05AE ; cons $09CB:$717A: JMP $1DA7 (subru: eval=$7163, compile=$3B6F)
- jart 5y agoOne thing you can do is `push $05` which only needs 2 bytes. The idea of using the x86 stack instructions to construct cons cells is potentially brilliant. I experimented with it a little bit. Couldn't make it work. For example, here's how it changes certain aspects of the implementation: Cons: xchg %sp,%cx # Cons(m:di,a:ax):ax push %di push %ax xchg %sp,%cx mov %cx,%di xchg %di,%ax ret Apply: ... xchg %cx,%sp Pairlis:test %di,%di # Pairlis(X:di,Y:si,a:dx):ax jz 1f # for x,y in zip(X,Y) push (%bx,%di) # (- . y) push (%bx,%si) # (x . y) push %sp # ((x . y)) push %dx # ((x . y) . a) mov %sp,%dx # a = ((x . y) . a) mov (%si),%si mov (%di),%di jmp Pairlis 1: xchg %cx,%sp ...
- timonoko 5y agoMy "compiler" was totally context-free and made in assembler. Which means that it compiles every instruction in complete vacuum and assumes stuff comes in AX and BX registers (with rest-pointer in CX, I think). And result in AX. But this proved not to be a bad start at all. Once you understand the limitations of the "compiler", you can modify the macros accordingly. One of the feature of the compiler was that it assigned absolute memory places for variables, so you could stop wasting stack and do early assignments to temporary variables. Unfortunately the source is quite incomprehensible now because of insane use of nested macros: https://github.com/timonoko/nokolisp https://github.com/timonoko/nokolisp But the example given above works, no doubt about it: > (setq test (ncompile '(cons 1 (cons 2 3)))) > (test) (1 2 . 3)
- andi999 5y agoWhen is a Lisp a Lisp? I mean what functionality needs to be provided to call it such?
- fsloth 5y agoPaul Graham's Roots of Lisp is a pretty good introduction to the fundamentals http://www.paulgraham.com/rootsoflisp.html http://www.paulgraham.com/rootsoflisp.html (The actual document is a .ps at the bottom of the page)
- andi999 5y agoThanks. I need some time to parse this. So this 436 bytes lisp implemented the 7 commands, so one can write the eval function?
- fsloth 5y agoMore or less. Read-eval-apply loop is the core concept of running a Lisp program. Structure And Interpretation Of Computer Programs is an excellent reference on the detail on how to put together such a system and how to use it.
- posterboy 5y ago> It's compatible with all PC models dating back to 1981 which have at least 64kb of RAM So, is it compatible with C51 8080? The differentiation function sounds really nifty, too!