Show HN: Lisp with GC in 436 Bytes

by jart • 5 years ago

513 130 5 years ago

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?)

__s2• 5 years ago

Haskell does, https://wiki.haskell.org/GHC/Memory_Management

WJW• 5 years ago

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.

kmill• 5 years ago

That page is incorrect about GHC's memory management -- I verified this with a question to haskell-cafe around 2014, and I guess no one got around to updating it.

The linked paper at the bottom of the article explains how things work and have worked for a long time now. The source of cyclic references, and even references from old to new generations, comes from "thunks" (unevaluated lazy computations). Haskell guarantees that a thunk only ever gets evaluated once, and the way this is implemented is that the thunk is mutated with a pointer to the evaluation result.

So the garbage collector needs to deal with mutations, cyclic references, and references from old to new generations. (All that in a language with supposedly immutable data!)

aidenn0• 5 years ago

I mean even a doubly-linked list is a cyclic data structure...

MaxBarraclough3• 5 years ago

Sure, but presumably they can't be expressed in SectorLISP.

ridiculous_fish• 5 years ago

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.

supergarfield• 5 years ago

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/

macintux• 5 years ago

I'm not aware of non-academic general purpose languages that actually fall in this category.

Erlang?

isaacimagine• 5 years ago

If data is immutable and you tie the lifetime of data to a single stack frame, you only need a single bit for reference counting: whether the current frame owns the reference. Calling a function just requires setting this to bit low (some asterisks here), and all objects tied to a given frame can be collected when the frame returns.

IsTom2• 5 years ago

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.

foldr2• 5 years ago

Elm is also strict and purely functional.

mixedmath• 5 years ago

When you say log n slowdown, what is n here? The length of the program? Or something completely different?

tooltower• 5 years ago

If you are talking about Pippenger-Fischer theorem, then that's about Turing machines, not machines with RAM. Or is there another theorem I don't know about?

jart14• 5 years ago

Author here. Why would it? Let's have a look at Scheme letrec (or let* in Emacs Lisp) translated to pseudo-SectorLISP:

    (LETREC ((IS-ODD?  (QUOTE (LAMBDA (X) (CAR X))))
             (IS-EVEN? (QUOTE (LAMBDA (X) (NOT (IS-ODD X))))))
      (IS-EVEN? (QUOTE (NIL T NIL T))))

The oldskool LISP way of writing that is:

    ((LAMBDA (IS-ODD? IS-EVEN?)
       (IS-EVEN? (QUOTE (NIL T NIL T))))
     (QUOTE (LAMBDA (X) (CAR X)))
     (QUOTE (LAMBDA (X) (NOT (IS-ODD X)))))

As far as I can tell, letrec is just a nicer syntax for the same thing. So I don't know why it should require any mutability. It works probably because LISP is dynamically scoped. Most languages and modern LISP implementations prefer different scoping models to make the Assoc() equation faster. However that comes at a cost, since it can turn the difficulty of LISP up to 11. Next thing you know, you're discovering things like the Y combinator. So I have major respect for what languages like Haskell and Scheme are doing, because it's incredibly difficult. One of the reasons why I created SectorLISP is because I wanted to have a fun bastion of simplicity when I don't need the more mature tools.

SectorLISP doesn't have any kind of internal mutability last time I checked. But I have experimented with it. For example, the Peel() optimization described in the blog post is how we solve the "make Assoc() faster problem". As it's written in the blog post, it's 100% pure. But if you introduce a tiny bit of mutability, it can go even faster on benchmarks even though it doesn't change the complexity class. See https://justine.lol/sectorlisp2/fast.js

dan-robertson7• 5 years ago

I think you’ve a trivial error in your function definitions but I don’t think it’s relevant.

I think you’re right about avoiding cycles. I think the parent was talking about a let rec construction for data, e.g. in Haskell:

  let funky_list = 1:2:3:4:funky_list

(Note that : is the cons operator).

If this is allowed then you may have issues. I think the problem is perhaps that the GC won’t work if you have pointers in the opposite of the normal direction. The fix though is relatively simple: add forwarding pointers (somehow), then after copying from the ‘B’ region to the ‘C’ region you leave behind a forwarding pointer and, if you see it again in your copying, you don’t make a duplicate copy of the data. Then I think you can proceed as before. But representing forwarding pointers efficiently is hard, I suspect.

Actually I think I don’t understand the GC sufficiently. Do you end up with a lot of memory usage after this or a little?

  ((LAMBDA (D Z) (D Z))
   (QUOTE (LAMBDA (X)
     (COND
      (X ((LAMBDA (Y) (CONS Y Y)) (D (CDR X))))
      ((QUOTE T) (QUOTE T)))))
   (QUOTE (A A A A A A A A)))

This should get you a binary tree about 8 levels deep with T on every leaf, and I think it should use linear memory (in the depth of the tree) but I don’t understand how the GC avoids ending up with an exponential amount of memory being used?

nils-m-holm• 5 years ago

LETREC requires mutability in the presence of lexical scope. Otherwise it works fine in the way you describe it. Using lexical scope, IS-ODD and IS-EVEN would be bound in parallel and (LAMBDA (X) (NOT (IS-ODD X))) would close over IS-ODD before it is bound, so it would be undefined when applied inside of the outer LAMBDA.

Of course dynamic scoping will bite you earlier or later because of the upward and downward FUNARG problems. See my book (http://t3x.org/lfn/) for lots of entertaining details.

commandlinefan3• 5 years ago

BrainF#*k not a true language

Curious why that might be, and TFA doesn't expound. What makes it not a "true" language?

shadowofneptune• 5 years ago

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.

commandlinefan3• 5 years ago

Ok, that matches my understanding of it then - it is a language, just not one you'd actually want to do anything in. I was thinking that the author was saying it wasn't a programming language in the sense that HTML is not a programming language.

casion2• 5 years ago

My "not so gracious" interpretation: "It would invalidate the claim that we wish to make, so... no true scotsman"

not2b• 5 years ago

Lisp is a language that people actually use to get work done; Brainfuck isn't.

jart14• 5 years ago

Author here. We anticipated this as a possible criticism of our "we built the world's tiniest programming language" claim. That's why we wrote the Brainfuck interpreter too. As far as I know, the 99 byte Brainfuck interpreter that's included in this blog post is the tiniest one to date. So even if that invalidates our tiny LISP victory, it'd still be a victory for the team since we built the competition too.

jart14• 5 years ago

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• 5 years ago

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• 5 years ago

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.

robbedpeter• 5 years ago

Counter argument: ever seen the proof for simple addition in English? The verbosity and/or opacity of the definition of a system isn't a great proxy for value or ease of use. Principia Mathematica uses over 1000 pages to reach the proof that 1+1=2, formally defining and explaining everything needed along the way, establishing fundamentals and primitive types and so on.

Brainfuck isn't a great interpreter language. It is a great perspective language. If you can break your tasks down sufficiently that you can express your program in brainfuck, you can take that understanding back to a more performant and expressive language. Doing Rosetta code exercises in esoteric languages forces your brain to model programs with more nuance and detail. If raw machine level performance was the only thing that mattered, we'd be writing everything in assembly. Different languages can have different utility, though, and while brainfuck is less useful as software, it is an excellent tool, not just a toy.

vanderZwan• 5 years ago

Isn't the distinction as simple as "does the language let you define anything and use recursion?", where I'm going to be a bit handwavy with "define anything" but I think we all get what I mean.

You can't name functions in Brainfuck or recursively call them. You can do so in LISP and Forth. That is also the entire reason Brainfuck explodes in size: it lacks the "semiotic" capabilities required to compress source code (and therefore, structure and refactor code, which is what humans need).

roywiggins• 5 years ago

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

chubot4• 5 years ago

I had this argument once -- I also believe Brainfuck is more of a machine than a language. Whereas Lisp is a language.

The main reason is that Brainfuck lacks composition, so what happens in practice is that people GENERATE Brainfuck code rather than writing it. When you write code, you rely heavily on your programming language's mechanisms for composition in order to make something that works.

Someone pointed me to people who DO actually program by hand in Brainfuck. There are some pretty big programs that are hand-written, not generated. Still I'm not entirely convinced, as they seem to be have been constructed through mental feats, not compositional language.

It's a curious fact that human languages and programming languages compose in a way that can be leveraged to build very large things that "work". I guess there is some equivalence between building up a large body of knowledge through language and making a program that works. Brainfuck doesn't seem to have this property.

The demonstrations of arithmetic and calculus in the post are nice examples of this in Lisp, and from there you have the rest of the world as your disposal (which is well documented in many books). With Brainfuck you're left crawling on your hands and knees, occasionally finding something that works, so to speak.

moonchild• 5 years ago

Brainfuck, like assembly and forth, composes by concatenation.

harryposner• 5 years ago

From the beginning of SICP [0]:

A powerful programming language is more than just a means for instructing a computer to perform tasks. The language also serves as a framework within which we organize our ideas about processes. Thus, when we describe a language, we should pay particular attention to the means that the language provides for combining simple ideas to form more complex ideas. Every powerful language has three mechanisms for accomplishing this:
* primitive expressions, which represent the simplest entities the language is concerned with,
* means of combination, by which compound elements are built from simpler ones, and
* means of abstraction, by which compound elements can be named and manipulated as units.

Brainfuck is missing any sort of means of abstraction. The primitives are instructions, and the only means of combination is writing instructions in sequence, but there's no way in the language to refer to any sequence of instructions --- no functions, no subroutines, not even labels. This makes it utterly useless as a way to organize your thoughts on how to compute something.

[0] http://sarabander.github.io/sicp/html/1_002e1.xhtml#g_t1_002...

dang• 5 years ago

Past related thread:

Show HN: SectorLISP now fits in one sector - https://news.ycombinator.com/item?id=29047584 - Oct 2021 (75 comments)

Shared404• 5 years ago

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!

jart14• 5 years ago

Author 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!

psyc• 5 years ago

It’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• 5 years ago

this is awesome exposition (from someone who has implemented a small version of Scheme himself decades ago)

titzer• 5 years ago

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.

ngcc_hk• 5 years ago

Convert his into a wasm lisp perhaps? Just a suggestion. Both these attempts are crazily great.

Waterluvian• 5 years ago

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.

jokoon• 5 years ago

I wonder if there are botnet/rootkits circulating that use such compact programming.

userbinator2• 5 years ago

Vintage computer viruses are definitely in this category of size optimisation. Not so much "modern" malware.

jazzyjackson• 5 years ago

I’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?

jjice• 5 years ago

Everytime 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.

jart14• 5 years ago

Author here. Thanks! The other projects I'm known for here on HN are:

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://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 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

Thank you Hacker News community for being so supportive and encouraging.

MonkeyClub2• 5 years ago

Awesome work, and very enjoyable to read, kudos!

αcτµαlly pδrταblε εxεcµταblε

You mean ακτυαλλγ πορταβλε εχεκυταβλε?

Datagenerator• 5 years ago

Congratulations on all your progress especially creating the worlds tiniest programming language in the world with GC!

deknos• 5 years ago

Hey, i have a question regarding your projects! and before that, i am a huge fan of redbean, this is so cool! as long as the world has also people like you with that cool stuff in it, there's still some fun and hope in the world.

but for the question: for your projects, do you have like a stable buildplatform (like nixos, minimal debian stable or sth like that) for which you publish your build instructions for your project?

Ericson2314• 5 years ago

How do I get you interested in the Nix ecosystem? It's a great sandbox for all sorts of portability and bootstrapping experiments.

chubot4• 5 years ago

Wow, 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

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.

jart14• 5 years ago

SectorLISP 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/a561e031aec03270459f... and 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

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 So I updated the C code to hybridize the two: 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.

int_19h3• 5 years ago

For the sake of just-for-lulz purity, you could #define var auto instead, and then it wouldn't have any uses of int in the code at all.

machawinka• 5 years ago

This blew my mind.

dschulz• 5 years ago

Impressive. Yet another disappointing reminder that, as a programmer, I'm not worth the salt of the food I eat daily.

adamnemecek• 5 years ago

Dude, 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• 5 years ago

As 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

TurboHaskal• 5 years ago

I have sent this article to some folks and plenty of them had the same reaction. A bit like math envy, it is normal to have when you lack a formal education and all you did professionally was writing CRUD apps. It does _not_ mean your work is in any way less meaningful though.

And yeah it is indeed impressive and maybe the coolest thing I've seen this year.

anyfoo• 5 years 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• 5 years ago

Can'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• 5 years ago

Yes; this Lisp is entirely in machine code and smaller than SectorForth.

int_19h3• 5 years ago

That'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/jonesfort...

jxy• 5 years ago

One biggest downfall of lisp is that people just call anything with parenthesized prefix notation "lisp".

cmrdporcupine• 5 years ago

Did you not read far enough to see that it runs a program (proof assistant) written for LISP 1.5 (1961)?

bitcharmer• 5 years ago

Serious 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.

karanbhangui• 5 years ago

Clojure 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• 5 years ago

Grammarly uses it for many of their services.: 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/ 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. ;)

nyolfen• 5 years ago

There must be some reason Lisp is so popular on HN.

sicp is a really good book, but also: https://marktarver.com/bipolar.html

ksherlock• 5 years ago

You are, indirectly, by posting on hacker news...

chubot4• 5 years ago

The author of this site and the founder of YC wrote Lisp books, and then a bunch of influential essays about Lisp (starting ~20 years ago):

http://www.paulgraham.com/lisp.html

This site is written in Arc, his first Lisp: https://news.ycombinator.com/item?id=28155134

stjohnswarts2• 5 years ago

I'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.

kmstout• 5 years ago

- Professionally, much of my output is in Python--everyone else in the shop knows it--with a smattering of C when it's warranted. That said, I'm an Emacs user, and I do write libraries and custom modes in Elisp to do things I find useful. In the hopes that others will, too, I make them available to my colleagues.

- I use Common Lisp at home for personal projects when shell scripts no longer cut it. When the Python 3 storm hit my ~/bin, it occurred to me that one of CL's best features is that its specification has been stable for several years (even while the ecosystem has evolved considerably).

jhgb4• 5 years ago

its specification has been stable for several years

And by "several", you mean "at least fifteen at the time"? ;)

klyrs2• 5 years ago

This gets posted to HN every so often: https://common-lisp.net/lisp-companies

tsimionescu• 5 years ago

Just to add an example, there is a Portuguese company called SISCOG which produces planning software in (Common) Lisp, mainly for railway timetables, powering many European railway systems.

jhgb4• 5 years ago

Been in software dev industry for over 20 years. Never encountered a single project employing the language.

Are you saying you've never seen AutoCAD or Emacs in your life? While possible, I find it somewhat difficult to believe.

Scaless• 5 years ago

The 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

Decompiled campaign scripts: https://github.com/Nibre/blamscript/blob/master/blamscript/h...

rurban• 5 years ago

The 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.

LargoLasskhyfv• 5 years ago

Mind blown. I feel blind and mown.

timonoko2• 5 years ago

My 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)

jart14• 5 years ago

One 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
            ...

timonoko2• 5 years ago

My "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

But the example given above works, no doubt about it:

    > (setq test (ncompile '(cons 1 (cons 2 3))))
    > (test)
     
    (1 2 . 3)

andi9992• 5 years ago

When is a Lisp a Lisp? I mean what functionality needs to be provided to call it such?

fsloth2• 5 years ago

Paul Graham's Roots of Lisp is a pretty good introduction to the fundamentals http://www.paulgraham.com/rootsoflisp.html

(The actual document is a .ps at the bottom of the page)

andi9992• 5 years ago

Thanks. I need some time to parse this. So this 436 bytes lisp implemented the 7 commands, so one can write the eval function?

posterboy• 5 years 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!

mlatu2• 5 years ago

I 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

jart14• 5 years ago

I 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.

mlatu2• 5 years ago

as 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

jhallenworld• 5 years ago

Overlapping 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...

jart14• 5 years ago

That'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/

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.

Show HN: Lisp with GC in 436 Bytes

Related Stories