Kilo LISP(t3x.org)

221 pointsby geocarvor 7 Jahren48 comments

http://t3x.org/klisp/index.html

49 comments

I saw that Kilo Lisp claimed "constant space garbage collection." I understand why a project like Kilo Lisp might like this, but I was curious about how that was accomplished, so I looked through the code.

The actual GC cycle code is pretty small, and looks like a classic mark-and-sweep over a fixed heap:

    int gc(void) {
        int i, k;

        k = 0;
        for (i=0; Root[i]; i++) mark(Root[i][0]);
        Freelist = NIL;
        for (i=0; i<NNODES; i++) {
                if (0 == (Tag[i] & MARK)) {
                        setcdr(i, Freelist);
                        Freelist = i;
                        k = k+1;
                }
                else {
                        Tag[i] &= ~MARK;
                }
        }
        /* ... */
        return k;

}

Cutting out the verbose GC stuff, there is a finite number of nodes and a free list. Exactly what one might expect. Even sorta feels like hardware.

The function mark is a classic algorithm, the Schorr-Waite algorithm [1], which traverses a directed graph and reverses the pointers, which modifies the heap graph as it traverses it to keep track of how much the graph has.

This is an interesting choice, and gave me pause because in a traditional large heap this would be a fantastically bad decision. But it's pretty interesting that the entire memory image of KiloLisp can exist in side the L2 cache of a raspberry pi and and in some circumstances half the memory can be hot and still reside in L1.

So actually, this is pretty clever. I suspect it's a good case of mechanical sympathy in recognizing that filling L2 will probably remove any gains that a "fancier" algorithm or a non-constant algorithm would bring. Very cool.

[1]: https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec... is a good reference for this. The original article is annoying to get and hard to read.

rain1vor 7 Jahren

This is good, I had been searching for a decent little lisp like this for a while but most of the ones I found had garbage collector bugs (extremely difficult to locate and fix) or didn't properly implement tail calls. I ended up writing my own https://github.com/rain-1/single_cream but now there's a few solid ones!

Kilo lisp is just over 1000 lines of code, pretty impressive given what it does. It uses the parallel rails memory representation for pairs as taught in sicp. It even seems to be able to load and save "images"!

I'm not totally sure how the evaluator works. It uses these kinds of opcodes? enum { MHALT = 0, MEXPR, MLIST, MBETA, MRETN, MAPPL, MPRED, MNOTP, MSETQ, MPROG }; do they represent the control stack or something?

nils-m-holmvor 7 Jahren

Nice to see Kilo LISP pop up here! :)

Yes, it does use images. (SUSPEND 'NAME) creates an image file and KL NAME at the shell prompt will load the image.

The evaluator is basically multiple functions in one, where the variable "m" ("mode") controls which function to apply next. The codes (MHALT, MEXPR, etc) denote the functions. MEXPR means "evaluate any expression", MLIST evaluates the next element of a list, MBETA starts function application, MRETN finishes it, etc. Yes, they implement states on the control stack (mstack).

TYvor 7 Jahren

Good to see you back online, Nils. Your books are amazing - thank you.

nils-m-holmvor 7 Jahren

Thank you!

garganzolvor 7 Jahren

Impressive. This the tiniest Lisp implementation I ever saw. Having two strides of storage for pairs is an elegant solution. It even provides macro support by building atop of lambda which is impressive too.

This small kernal bootstraps itself with 'klsrc' file, and then it's able to provide 'cond', 'or', 'and' and other keywords for a conventional Lisp syntax.

I am eager to characterize the performance of this implementation. Tiny tends to mean fast but not always.

rain1vor 7 Jahren

in language implementation the speed you get generally follows this path:

    AST interpreter < bytecode interpreter < native code compiler

and it's an AST interrpeter so it's (likely to be) on the lower end of the speed scale.

nathellvor 7 Jahren

It's the first Lisp I've seen in which numbers don't evaluate to themselves. In fact, it doesn't even have a number type. A number-like symbol is just a symbol.

I now wonder whether this was the case with McCarthy's Lisps as well.

phoe-krkvor 7 Jahren

No, McCarthy's original Lisp didn't have numbers. See chapter 5 and the linked footnote 4 of [1].

I guess that the Lisp described by Graham does not describe any mathematical operations, since they aren't really required to construct a metacircular evaluator, which is the selling point of the whole article. You don't need numbers for purely symbolic processing; if absolutely required, you can emulate them using Church encoding. Or you could try and make your Lisp dialect practically useful, and extend it with numeric types and operations.

[1] http://lib.store.yahoo.net/lib/paulgraham/jmc.ps via http://www.paulgraham.com/rootsoflisp.html

nils-m-holmvor 7 Jahren

Church encoding is not the only option, since you already have pairs. So you can use base-1 list encoding, which is what lots of Kilo LISP programs do. Or you can implement natural numbers using lists of digits, which is still inefficient, but probably much faster than Church numerals.

Try this in kilo LISP:

  (load 'src//nmath)
  (times '(1 2 3) '(4))

int_19hvor 7 Jahren

I wonder if there's any benefit in representing numbers as pairs forming a ring, with some pair arbitrarily designated as 0. This would only work for very small numbers due to being memory wasteful (although the implementation could try to optimize); but on the other hand, CAR/CDR become increment and decrement, and you get wraparound for free.

vesinisavor 7 Jahren

    * (load 'src//nmath)
    ? undefined: null

You have to first load klsrc which defines objects required by src/nmath:

    * (load 'klsrc)
    t
    * (load 'src//nmath)
    t
    * (times '(1 2 3) '(4))
    (4 9 2)

nils-m-holmvor 7 Jahren

If you build Kilo LISP using the Makefile, it will load "klsrc" and create the "klisp" image file from it. Without the image file the interpreter is not very useful!

Edit: If you cannot/will not use MAKE, just do

  (load 'klsrc)
  (suspend 'klisp)

After that you do not have to load klsrc any longer.

vesinisavor 7 Jahren

Right, I just compiled the C file with gcc -o kl kl.c and it seemed to work fine.

weebervor 7 Jahren

What does the times function?

cryptonectorvor 7 Jahren

Multiply.

weebervor 7 Jahren

ok, but why 2 * 4 produces a 9?

yellowapplevor 7 Jahren

The list is a list of digits, which combine into a single number (that is: '(1 2 3) == #123). 123 × 4 = 492, so (times #123 #4)) unsurprisingly evaluates to #492 (a.k.a. '(4 9 2)).

A bit funky if you're coming from a Lisp that actually does have numbers that evaluate to themselves, but when it hits you it hits you :)

nils-m-holmvor 7 Jahren

Good to see Kilo LISP here!

Note: LISP, not Lisp -- I refuse to get the memo! :)

dangvor 7 Jahren

Ok, we'll give you LISP in the title above. Nobody else gets that :)

nils-m-holmvor 7 Jahren

You really didn't have to do this, but I'm glad you did! Thank you! :)

matthewwiesevor 7 Jahren

Just wanted to say that I always enjoy seeing a t3x.org link pop up on the front page of HN. Your site is one of the few "regulars" that I always enjoy seeing a new update from; your projects are always interesting and I can usually learn something new just by perusing the manual and looking at the code to discern how a feature was implemented.

nils-m-holmvor 7 Jahren

Wow, this is great to hear! Thank you! :)

yellowapplevor 7 Jahren

Fantastic work! It was understandable enough that I was able to hack in support for a (quit) form in, like, 5 minutes of glossing through the code and seeing how you defined special forms (kinda useless since you can always press C-d, but it was a fun and quick first-step exercise in figuring out how I might go about extending it for use in various "real-world" projects).

eggyvor 7 Jahren

TurboC compilation is 13KB and GCC is over 512KB. Very interesting Lisp-1. I am going to look at the C code. Should be good for embedding as a scripting language.

UncleEntityvor 7 Jahren

> ...and GCC is over 512KB.

Just using make out of the box shows 44k so not sure where the 512k is coming from?

Using my "standard" little gcc flags:

  -Os -s -Wall -Wl,-z,norelro

it comes out to 19k on gcc 8.2.1 on x86-64.

nils-m-holmvor 7 Jahren

Try -static, because that is what Turbo C and SubC do!

ninjinvor 7 Jahren

The “wackiest” Lisp embedding I have seen is of femtolisp [1] into Julia [2] to drive the language parser [3]. In hindsight, this is a fairly sensible design decision, but it did blow my mind when I first spotted it.

    # julia --lisp
    ;  _
    ; |_ _ _ |_ _ |  . _ _
    ; | (-||||_(_)|__|_)|_)
    ;-------------------|----------------------------------------------------------

    > (apply cons '(1 2))
    (1 . 2)

[1]: https://github.com/JeffBezanson/femtolisp

[2]: https://julialang.org/

[3]: https://github.com/JuliaLang/julia/blob/d76a30a7178dd1e9b744...

nickpsecurityvor 7 Jahren

A lot of people liked Lisp concepts but couldn't stand the syntax. One thing I keep telling people to try is wrap it in a better syntax hiding the ugly parts. Seeing Lisp in Julia, a language mainstream developers might embrace, brought a big smile to my face. Need more attempts. :)

Another language that tried this with a syntax change was Dylan. People interested in that can try OpenDylan.

drmeistervor 7 Jahren

Lisp without s-expressions is like bathwater without a baby.

S-expressions enable homo-iconic macros and make compile-time computing super easy! I spent 35 years programming in C and C-like languages and then developed my own Common Lisp implementation (http://github.com/clasp-developers/clasp.git) - the only Common Lisp that interoperates with C++ and uses llvm as the backend. When I started with lisp I wrestled with the syntax and sweet-expressions and just decided to let it go. Now I've found language love all over again!

In a world that runs on Javascript, nobody should be able to complain about a few measly parentheses.

Obligatory relevant XKCD comic: https://xkcd.com/297/

zemvor 7 Jahren

you get all the good properties of lisp with a syntax that leaves some parentheses implicit but unambiguous (meaning that a preprocessor can add them back as the first step).

Syzygiesvor 7 Jahren

I've been coding for years using a preprocessor that eliminates most parentheses: Indentation implies parentheses. A pipe "|" opens a parenthesis that auto-closes at the end of that line or at the next ")". A dollar "$" opens a parenthesis that auto-closes when the indentation recovers. The result has a lighter, more poetic look than any language I know, and the parentheses that are left actually matter, so I pay attention to them.

I've seen other proposals online, but they felt untested to me. Leave out either "|" or "$" and the above system gets clumsy. I check for the equivalent of "$" in other proposals exactly as I check for marrow in a stew recipe: Did they really think this through?

One can't change existing habits. An idea that appeals to me: Write a Lisp preprocessor for Rust, and happen to use this syntax.

saulrhvor 7 Jahren

Can you post a link to an example? This sounds like something I could use for my all-too-common convenience hacks, but I can't quite envision it just from the description.

naaskingvor 7 Jahren

Why not o-expressions? http://breuleux.net/blog/oexprs.html

Syzygiesvor 7 Jahren

Core: APPLY IF IFNOT LAMBDA PROG QUOTE SETQ Derived: LET LABELS COND AND OR QQUOTE LOOP

I was curious how quickly I could change the source to lowercase symbols. It turns out that all Lisp symbols are already lowercase in the C source, and all Lisp source is lowercase. The only uppercase is in the documentation. A nod to us "thawed out of glaciers" elders who actually remember old Lisps?

nils-m-holmvor 7 Jahren

A nod, a habit, and pragmatism. Many LISP books and manuals I have read reproduced code in upper case. Then, upper case is a simple way to make keywords stick out in prose.

Syzygiesvor 7 Jahren

Yes, but to some not yet seduced by Lisp, it reads like Bernie Saunders just texted "GET OFF MY LAWN!"

pjmlpvor 7 Jahren

Not when one is used to Wirth languages, which used caps to differentiate keywords on teletypes that only had one font type.

Caps for keywords was the first use of syntax "highlighting". :)

sitkackvor 7 Jahren

I want to believe that Bernie Sanders uses LISP.

asimjalisvor 7 Jahren

Would be neat if this supported Clojure syntax.

[deleted]vor 7 Jahren

ashton314vor 7 Jahren

Now, can I get this to run on my HP 50g...

benj111vor 7 Jahren

"Kilo LISP A Kilo Byte-Sized LISP System"

But it's 25k of code, the executables and memory requirements are both greater than 1k.

Did it start off as 1k in size, and since expanded?

aaronhardervor 7 Jahren

I suspect it's called Kilo Lisp because all those sizes are in the of "kilobyte" order of magnitude, rather than "megabyte." But not because any aspect of it is exactly 1k in size.

Fun name either way.

nils-m-holmvor 7 Jahren

Aaronharder is right, it is called Kilo LISP, because it's code size is measured in kilo bytes. In fact the code contracted a bit since the first version.

That being said, I like S4M's explanation, too!

benj111vor 7 Jahren

Thanks. Wasn't sure if it started as a 1k thing.

Sloccount on kl.c gives 1056, so either lose 56 lines, or 32 lines and put up with pedants.

Edit: Making specialp() return a single line, excluding 1 branch of the #ifdef and all the #defines gets you below 1024. So maybe you could argue the case?

nils-m-holmvor 7 Jahren

Sounds like a solid argument, but I think I will stick to the "kilo byte order of magnitude" narrative! :)

S4Mvor 7 Jahren

I think they named it like that because it's 1k lines of code.

ngcc_hkvor 7 Jahren

I still think if it is nit lisp-2 it is not lisp but scheme.