{"id":34517,"date":"2021-12-21T14:55:42","date_gmt":"2021-12-21T19:55:42","guid":{"rendered":"https:\/\/mjtsai.com\/blog\/?p=34517"},"modified":"2021-12-21T14:55:42","modified_gmt":"2021-12-21T19:55:42","slug":"sectorlisp-lisp-with-gc-in-436-bytes","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2021\/12\/21\/sectorlisp-lisp-with-gc-in-436-bytes\/","title":{"rendered":"SectorLISP: Lisp With GC in 436 Bytes"},"content":{"rendered":"

Justine Tunney<\/a> (Hacker News<\/a>):<\/p>\n

The SectorLISP<\/a>\n project has achieved its goal of creating a LISP that’s tiny enough to\n fit in the master boot sector of a floppy disk. To the best of our\n knowledge, this is the tiniest LISP to date. Since a master boot\n record is only 512 bytes, that means LISP is now tied\n with FORTH<\/a> to\n be the most lightweight high-level programming language in the world.<\/p>\n

[…]<\/p>\n

\n One of the most important code size saving techniques has been to\n avoid the temptation of defining data structures in such a way\n that NIL<\/code> is encoded as zero. For example, if the lowest\n bit of a word is a flag bit for telling atoms apart from cons, then\n that bit must be 1 for cons cells since NIL is an atom. In that case,\n all words representing cons cells effectively become a misaligned\n pointer and extra code needs to be written so the 1 bit can be cleared\n before addressing memory. Avoiding those address calculation woes by\n defining atoms as oddly-numbered words is far more profitable than\n avoiding explicit NIL<\/code> compares.\n<\/p><\/blockquote>\n\n

Justine Tunney<\/a> (tweet<\/a>, Hacker News<\/a>):<\/p>\n

There’s been many changes over the past few months that made it possible to shave away another hundred bytes from the i8086 assembly implementation. It left plenty of room to add a 40 byte garbage collector.<\/p>

[…]<\/p>

It works by saving the position of the cons stack\nbefore and after evaluation. Those values are called A and B. It then\ndecreases the cx cons stack pointer further by recursively copying the\nEval<\/code> result. The new stack position is called C. The memory\nbetween B and C is then copied up to A. Once that happens, the new cons\nstack position becomes A - B + C. The purpose of this operation is to\ndiscard all the cons cells that got created which aren’t part of the\nresult, because we know for certain they can’t be accessed anymore\n(assuming functions aren’t added which mutate cells).<\/p>

[…]<\/p>

Similar to how a Chess game may unfold very differently if a piece is moved to an unintended adjacent square, an x86 program can take on an entirely different meaning if the instruction pointer becomes off by one. We were able to use this to our advantage, since that lets us code functions in such a way that they overlap with one another.<\/p><\/blockquote>","protected":false},"excerpt":{"rendered":"

Justine Tunney (Hacker News): The SectorLISP project has achieved its goal of creating a LISP that’s tiny enough to fit in the master boot sector of a floppy disk. To the best of our knowledge, this is the tiniest LISP to date. Since a master boot record is only 512 bytes, that means LISP is […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"2021-12-21T19:55:44Z","apple_news_api_id":"e4ddfa52-37e4-4687-b8e6-9756ac9da1b8","apple_news_api_modified_at":"2021-12-21T19:55:44Z","apple_news_api_revision":"AAAAAAAAAAD\/\/\/\/\/\/\/\/\/\/w==","apple_news_api_share_url":"https:\/\/apple.news\/A5N36UjfkRoe45pdWrJ2huA","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[770,45,263,288,70,74,138,71],"class_list":["post-34517","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-assembly-language","tag-c","tag-theory","tag-garbargecollection","tag-lisp","tag-opensource","tag-optimization","tag-programming"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/34517","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=34517"}],"version-history":[{"count":1,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/34517\/revisions"}],"predecessor-version":[{"id":34518,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/34517\/revisions\/34518"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=34517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=34517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=34517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}