We are currently in the process of converting the website to the new design. Some pages, like this one, are still broken. We appreciate your patience.
Handmade Network»Fishbowls»Lessons from the Lisp Jam

Lessons from the Lisp Jam

In the summer of 2020 we held a Lisp jam, where many community members made exploratory Lisp-inspired projects. We held this fishbowl as a recap, as a time for the participants to share what they learned and explore how those lessons relate to our day-to-day programming.

This is a fishbowl: a panel conversation held on the Handmade Network Discord where a select few participants discuss a topic in depth. We host them on a regular basis, so if you want to catch the next one, join the Discord!
bvisness Aug 05, 2020 08:00 AM
here we go again
Topic: Lessons from the Lisp Jam
So yeah, we did a Lisp jam several weeks ago, and it's about time we all reconvened and discussed what we learned from it. (If you're interested in reading conversations that happened during the jam, start here: https://discord.com/channels/239737791225790464/485261036308660244/729636584093384724) (edited)
As a recap, we had several really interesting projects, including:
@nakst 's flip, a 16-bit Lisp-based OS (demo here: https://discordapp.com/channels/239737791225790464/485261036308660244/731467698352947260) (edited)
@rxi 's cel7, a tiny game framework built around his fe language: https://rxi.itch.io/cel7 (edited)
@accidentalrebel 's Emacs game engine: https://github.com/accidentalrebel/emacs-game-engine
@Allen4th 's Splink!, a Lisp IDE: https://github.com/4th-dimention/splink
@inso 's peril, a "C in Lisp" toy language: https://github.com/baines/peril
@Luis Reyes 's puyo puyo game, made using rxi's cel7 (a jam project built on someone else's jam project!): https://gist.github.com/no-difference/36745227bfb4257b762009d30392ec5d
and my Dream-th (Dreams, with a Lisp!) - a Lispy interpreter made in Dreams for PS4 https://youtu.be/KcPKZmQve_c (edited)
(sorry if I missed anyone's project!)
You can see more of these projects and some early discussion about "homoiconicity" in the #accountability channel if you scroll back a bit. (I hope we can talk a bit more about homoiconicity today!) But the purpose of this fishbowl is for us to actually discuss what we all learned as a result of producing all these projects.
ryanfleury Aug 05, 2020 08:33 AM
Something I was thinking about while researching Lisp and doing my tiny jam project was meaning being imposed upon a uniform structure in Lisp (and the implications this has for Dion specifically)--I'm sure Allen can speak a lot to this also. This architecture seems to lift semantic language meaning out of the tree structure, and instead adds to it as metadata. The interesting thing here is that you can start imposing custom things on top of a uniform thing.
bvisness Aug 05, 2020 08:34 AM
one message into this fishbowl and I already need more coffee
ryanfleury Aug 05, 2020 08:34 AM
Hahaha, fair :P
This also gets into something I've been playing with for awhile now, which is a concept of trying to form "legos", where you have a uniform building block you use to piece together many different things, much in the same way that Lisp does. Interestingly enough I've been trying to use this in entity systems, as well as UI systems. The results seem to be fairly fruitful (edited)
bvisness Aug 05, 2020 08:38 AM
Say more about that; this ties a little bit into the discussion of "homoiconic" languages we had before
Lisp's building blocks are obviously very small and simple (basically just linked lists in the common case?) but I know Dion is more complex than that.
ryanfleury Aug 05, 2020 08:42 AM
So I am still not 100% sure what "homoiconic" means; from what I've heard it is a term that has been used to mean a number of things, but I think the term is getting at the same picture that I am trying to get at, which is just trying to describe a system with a uniform structure at the bottom, but with meaning imposed on top of that with metadata. Dion has been like this for a while, but over time what we've found is that we're constantly driving to a simpler building block; very recently we've moved to a very uniform structure that is slightly more structured than Lisp, where we effectively have lists-of-lists like Lisp does, except we also have AST nodes that are used to make certain grammatical enforcements, which are formed by the definition for some kind of node type. We call those nodes "specs", so what we find is that we have an alternating pattern: sets-of-specs-of-sets
Interestingly the UI stuff for Dion--which is a completely different system (though it is related to the constraints of the code, e.g. recursiveness, because it was meant to be used for things that need to exist alongside code)--is similar in this way. At first I started with a kind of sprawling megastruct of stuff, but overtime as I started collapsing/simplifying functionality, I was finding that my building block was becoming more and more uniform. These UI nodes form a list-of-lists-style tree, just like Lisp. (edited)
bvisness Aug 05, 2020 08:46 AM
I look forward to when @Allen4th can be online to discuss Splink, because it seems like that might be exploring similar ideas. Do you know if Allen's work on Splink influenced your design work on Dion?
ryanfleury Aug 05, 2020 08:47 AM
Definitely. In fact Allen had more insight than I did because his project was sort of like a mini "compute engine" (the term we are using for Dion) for a textual Lisp, so I'm sure he can speak to a lot of this in greater detail
I think the course of design has been a gigantic expansion, followed by a compression to something much tighter and simpler; Allen is way better than I am at the second stage of that, so naturally he was thinking about this kind of thing harder during the jam. 😄 (edited)
bvisness Aug 05, 2020 08:50 AM
It's interesting that you're still managing to preserve C-like semantics on top of that; clearly the execution models are very different between Dion and Lisp
at least by default, maybe
by the way I know this discussion got really deep really fast, but as people who participated in the jam are available, I'd love if you just hopped in to share your overall thoughts and what you learned
ryanfleury Aug 05, 2020 08:51 AM
Well really there isn't an assumed execution model, which is interesting; it is basically a uniform tree, plus some metadata, which is used to render, type-check, and eventually compile to real instructions on a computer. In other words, a C-like AST is just a more specific version--with more metadata over the nodes--of a Lisp AST (edited)
bvisness Aug 05, 2020 08:51 AM
even if it interrupts the flow a bit
ryanfleury Aug 05, 2020 08:51 AM
Yes absolutely, don't let me infect every conversation with Dion, that was just my takeaway that was very useful for me :)
bvisness Aug 05, 2020 08:52 AM
it's interesting to me that you mentioned your megastruct thing for UI, since I just yesterday watched your talk with Randall (at Randall?) about that stuff
What does that simplifying process look like there? What are some examples of ways that your UI entity design became more uniform?
ryanfleury Aug 05, 2020 08:58 AM
Yeah so my talk with Randall (@randy) was very much related to this. Entities in a game world are a little different because there isn't necessarily some kind of tree structure imposed on them (though often times, there is), but my approach that I was trying to get at in that video was very much the same: Drive to a uniform building block. Initially I started with a megastruct, where I just started dumping stuff for any possible UI widget, with some flags:
struct UI_Widget { UI_Widget *next, *prev, *parent, *children_list, *children_list_tail; u64 properties[UI_WidgetProperty_Max/64+1]; // etc. b32 *clicked; f32 *drag_f32_value; v4 *color_picker_value; // etc. etc. etc. };
And that's all fine, but you'll notice that there's an explosion happening: The "widget response data"
What I ended up wanting was a "canvas widget", which basically allows for any custom interception of rendering or updating
And that eventually added these to the widget struct:
void *custom_user_data; UI_CustomUpdate *CustomUpdate; UI_CustomUpdate *CustomRender;
NOTE: custom_user_data is allocated on double-buffered per-frame arenas, so it can be used to store persistent data per-widget, because you can always persistently access last frame's state, and allocate current frame's state, and map between the two. I then noticed that these--paired with some built-in properties that are a fast-path for implementing very common UI paradigms, like clicking--could be used to represent almost any simple widget I already had. (edited)
(You could implement clicking with a CustomUpdate, but I have a fast-path for it where you just flick on a property and it does the logic) (edited)
And then I realized I had moved the definition of very specific UI widgets out of the internals of the UI system, and into a sort of "third user" of the API, who is tasked with forming widgets
In other words, the building of widget types became a third face to the API, and therefore became user code, allowing for very specific widgets (e.g. file explorer buttons that display super specific stuff), formed by usage code:
On the other side, the structure of the widgets is 100% uniform and can be used as such, for example with keyboard navigation.
So there's a real magic to being able to adjust the "structuredness" you're dealing with at different places in the API, and ultimately I think that's what Lisp provides, and I think this was just a slice of that in the UI sphere. In one spot, you can consider things as a generic uniform tree, in another spot, you can write the most specific code possible to specify the exact information you want. But there isn't any weird inheritance or casting pointers or anything like that, the two structures are actually just the same thing, you're just talking about their contents differently. (edited)
Another interesting property of the UI stuff is that it allows for composability very easily. So I can turn on the "clickable" property, and I can feed in a custom update/render, which allows me to do things like make those file explorer buttons. But that is a sort of different rabbit hole not immediately related to the Lisp-like uniform building block (though the two play very nicely with each other). (edited)
bvisness Aug 05, 2020 09:11 AM
So maybe this doesn't really get to the heart of it, but do you think something like Dion or Lisp would allow you to do this stuff more easily or naturally?
ryanfleury Aug 05, 2020 09:12 AM
I think with something like UI structures, not really, but with code itself, definitely
The fact that--if we want to treat our C code as data--we need to parse it, already puts us a mile away from what we want, but even after that point, you're still talking about a very specific tree, when in many cases you want a generic, Lisp-like one (edited)
Someone could always write a C compiler that parses out to a Lisp tree, maybe! (edited)
bvisness Aug 05, 2020 09:16 AM
I know we've had the discussion about "parsing" Lisp before at some point, but it's pretty much a non-issue because parsing Lisp is hardly any more difficult than deserializing some binary representation of the same thing
it's still directly representing the final structure
ryanfleury Aug 05, 2020 09:16 AM
Right, actually what Allen and I have been discussing recently is that parsing is mostly a problem when it's not local
Localized parsing is not very problematic
It is for this reason that we've moved to a list of "expression tokens" (even though those "tokens" are just full subtrees, not textual tokens) for our expressions in Dion. They are still formally a tree, but we don't actually have the + with two children, like we did before (edited)
Parsing starts to get nasty when you've got important information scattered throughout 100 files, it's not clear how they are supposed to connect, it's impossible to tell what things are until you've figured that out, and finally, add a little bit of textual preprocessor as the cherry on top
In other words, when you're parsing something like that, it's very difficult to tell "where you are"
bvisness Aug 05, 2020 09:23 AM
I mean something like Lisp still has bindings in the environment and whatnot; no sophisticated program can do stuff entirely locally
but I suppose in Dion that's just a direct pointer to another node?
ryanfleury Aug 05, 2020 09:28 AM
Right, not quite a pointer, but a "node handle", which keeps track of a generation number
All "close" relationships in the tree are formed by "pointers" (they aren't even pointers anymore for practical architectural reasons having to do with very large codebases, they're just indices--also helps us keep the size of nodes down), but "far" relationships are formed by handles, which have more information packed into them (edited)
And that's specifically so that, say, deleting a type that someone is referencing doesn't crash the program or result in massively broken code or something (edited)
bvisness Aug 05, 2020 09:33 AM
makes sense
mind if I deviate a bit and just say a few of the things I learned from my project?
ryanfleury Aug 05, 2020 09:33 AM
Not at all, I'd prefer that--I've gone on long enough :P
bvisness Aug 05, 2020 09:35 AM
so I went into the jam really not knowing Lisp at all - I kind of understood the basics but couldn't even tell you what the list structure actually looked like, much less how you would do anything interesting in it
I had to play around with Racket a bit and I implemented minilisp just to try and learn it
but in the process of creating the thing in Dreams, I really had to grapple a lot with what Lisp actually is
and I've mentioned before in other channels, but it weirdly felt like implementing Lisp in Smalltalk or something. Dreams feels very object-oriented in a pure sort of way.
I had to question, for example, if I actually needed memory allocations to make things behave like Lisp (I did)
or nuances like when you evaluate a list as a function vs. just looking at the list data (in some sense, what's the runtime and what's the actual program?)
for example, your primitive functions have to be able to access their arguments somehow, which implies working down the list and evaluating each argument (which means possibly calling more functions)
In order to achieve that, I had to implement some list-walking stuff in my runtime that I don't think could be done just with more Lisp code - I think at some level, something in the runtime needs to actually know how to walk a list
I think I might have actually learned more about object-oriented programming through this project than I did about Lisp. There are parts of Dream-th that feel very natural, like how the cons cells can talk to each other by proximity, just seeing what's snapped on to their value slot. Having each cons cell be an "agent" that you could send messages to felt really natural there. ("What's in your cdr slot?", "Can you ask your car thing to evaluate itself and then tell me what it said?")
On the other hand, just implementing an addition function was a nightmare of IDs, and I needed three different objects all talking to each other to make that happen. (One to walk the list nodes, another to evaluate the things at those list nodes, and another to grab the return values.) In retrospect, one of those may have been unnecessary if I had smarter messages in my runtime, and obviously some of that is just Dreams being weird. But I really felt the pain at some points of not knowing where to put the state or behavior, which is inherent to object-oriented programming.
Also naming. Naming sucks. Everything in Dream-th is some riff on "evaler".
It's possible that if I put more work into abstraction, I could maybe make the objects small enough that the system is easier to understand. But if you watch the latter half of my code walkthrough video, you'll see that a simple addition function is almost too complex to explain. (edited)
ryanfleury Aug 05, 2020 09:51 AM
That is pretty interesting. It sounds like the concept of classical object-orientation--message passing between agents, basically--works much better in Dreams than most other places, because there are actual "real world objects" that are directly equivalent to the "code objects", but maybe this addition "circuit" is an example of where that breaks down?
bvisness Aug 05, 2020 09:51 AM
(It occurs to me that I to a large extent had to implement not just a programming language, but a computer. Following memory references is a lot of work since you have to find the physical location of the thing in space, and then actually travel there, which is several steps.)
Yeah the problem is that the addition logic was quite a crazy sequence of actions, and ping-ponged back and forth between the different objects involved in the operation.
let me see if I can give you a sense of those steps...
- START: receive eval message with ID of cons cell containing the first argument - tell list walker to go there - list walker calls to global registry to get physical location of cons cell, and performs several steps to travel there - list walker sends message to cons cell asking what is in its car slot - list walker tells evaler to go to the car slot (this is what could be elided with better messages) - evaler goes to the car object via the global registry and travel thing - evaler sends eval message to car thing - eval happens, a result is spawned and the ID is sent back to the evaler - evaler tells value grabber to go grab the value - value grabber goes to result via the same multi-step process - value grabber sends result back to the primitive (via wires, mercifully) - primitive sends message to list walker saying it's done with the value - list walker asks cons cell what's in its cdr slot - list walker either moves on and repeats most of this, or sends stop messages to evaler and value grabber - list walker sends done message to primitive - primitive sends message to spawner with a result - spawner produces a value and send the ID back to the primitive - primitive returns the ID of the spawned value back to the thing that evaled it
😱 1
this is, to put it mildly, insane.
There are echoes of concurrent programming in this too, because each object is an independent actor and must be explicitly sequenced with the others via messages.
(It's very CSP-like.)
Now as I said, part of that is the "computer". The "look up a location by ID and then travel there" is basically fetching from RAM.
And that part could likely be standardized in some way so that each thing didn't implement it itself.
I think there are several things in here that could be better abstracted and simplified so that it more concisely describes the actual logic of the system.
ryanfleury Aug 05, 2020 10:01 AM
That's kind of fascinating, definitely seems like it is more complicated than an addition circuit or something :P
bvisness Aug 05, 2020 10:01 AM
I've never actually used Smalltalk, but I really hope that modeling problems isn't as challenging as it is here.
bvisness Aug 05, 2020 10:03 AM
for reference, here's minilisp's plus primitive
static Obj *prim_plus(Obj *env, Obj *list) { int sum = 0; for (Obj *args = eval_list(env, list); args != Nil; args = args->cdr) { if (args->car->type != TINT) error("+ takes only numbers"); sum += args->car->value; } return make_int(sum); }
Allen4th Aug 05, 2020 10:03 AM
My entire understanding of Dreams and Dream-th comes from the first few minutes of your video @bvisness but based on my vague understanding of all of it, it seems like it highlights how important organization is for a "computation system"
Allen4th Aug 05, 2020 10:04 AM
As in - even if Smalltalk did require very similar signals and objects as Dreams, the quality of the model would also be improved by the basic fact that you could probably find an easier way to organize it that isn't available in Dreams.
bvisness Aug 05, 2020 10:05 AM
Interesting, I think you're right
a large part of the complexity in the Dreams version is that since many messages are sent based on physical proximity, objects can really only follow one pointer at a time
which is why I needed separate list walkers, evalers, and value grabbers
if I need to get messages from two things at the same time, I need two objects or I guess I need to travel back and forth and save state along the way
this is obviously a limitation of Dreams and not of other OO models
but; I suppose it's analogous to a limited memory bus or something
Allen4th Aug 05, 2020 10:09 AM
Yeah or the "tape" of the classical Turing Machine definition.
It definitely seems like you had to simultaneously mine out the turing complete part of Dreams and then make a Lisp work on top of it.
bvisness Aug 05, 2020 10:12 AM
this has me wanting to go back in and made a couple simplifications
I think for example I could make a "memory bus" that is a pair of objects wired together - one that goes to visit the memory address, and one that goes to visit the requester, and that effectively creates a temporary "wire" between them to facilitate messages
it would be fine for there to be only one because execution is sequential
Allen4th Aug 05, 2020 10:14 AM
Ahh interesting.
It seems like the "machine" you have right now is literally a lisp machine. Like it has to implement some features that are not usually a part of implementing a Lisp because the underlying layer doesn't even have them (Dreams doesn't give you RAM).
But it's still a machine whose execution and instructions are just defined to be Lisp.
bvisness Aug 05, 2020 10:15 AM
Allen4th Aug 05, 2020 10:16 AM
So if that's the case, one thing I would be curious about is the comparison between the complexity of taking a sum on Dreams that way vs building a machine in Dreams with a different architecture.
Does a stack based machine or a register based machine with a "bytecode" interpretation model take more or less complexity to get up and running?
Did Lisp simplify or complicate the design of a machine in Dreams?
bvisness Aug 05, 2020 10:17 AM
I'm not sure if Dreams can take two levels of computers 😛
brain 1
that's a good question
Allen4th Aug 05, 2020 10:18 AM
Haha yeah I don't mean a Lisp macine on a register machine, just the side-by-side 😄
bvisness Aug 05, 2020 10:18 AM
I'm not sure to what extent Dreams itself can do sophisticated computations. I haven't really tried, to be honest. For example, I'm not sure how you would implement any kind of recursive function.
You don't have a stack, really.
ryanfleury Aug 05, 2020 10:19 AM
Couldn't you do the y-combinator thing?
bvisness Aug 05, 2020 10:19 AM
googles furiously
I think this is it...
From my understanding--it has been awhile--this allows you to effectively do a recursive function purely from non-recursive functions, as long as you can treat functions as values
Allen4th Aug 05, 2020 10:22 AM
I have tried to understand the fixed-point combinator and I feel like just conceptually - without even trying to describe the computation of it to an actual machine - it is more complicated than the actual implementation details of Dream-th!
ryanfleury Aug 05, 2020 10:23 AM
Haha, yeah, that is totally true :P
bvisness Aug 05, 2020 10:23 AM
someday I really do need to learn some lambda calculus
so @Allen4th , what would you say are a few takeaways from your work on Splink?
Allen4th Aug 05, 2020 10:28 AM
That's a lot to unpack.
I sort of struck research gold - not in the sense that Splink is particularly great for anything - but I just happened to find a path where I got to try a lot of really wild stuff.
I think the thing which almost anyone could learn from is the ideas about evaluation order, and functional vs stateful computations.
So something I wanted to try in Splink which you can see if you look at the screenshots of it is that each little block is one Lisp expression, and then the evaluation of that Lisp expression is shown at all times right on the block.
And since Splink is a "compute engine" not just a programming language + editor, those blocks are actually each separate little units in the compute system. They don't have any concept of global ordering.
What that means is it doesn't really make sense to think of a global environment where first block A effects the environment and then block B effects the environment etc.
There is still a global environment, but it has to be defined in such a way that order won't matter.
The way I did this is to say that all eval just happens in two steps. First each of those blocks gets added to the environment as a "deferred" evaluation, and then when you actually go to evaluate one, if it depends on another block that just means you need to eval that other block. It doesn't matter if A depends on B or B depends on A, they will both see the each other in the environment.
Then if A depends on B, you will find this out while trying to evaluate A. If B is still in the "deferred" state, you can just try to evaluate B before you evaluate A. This also made it super easy to detect cycles because you can just have A marked as "in-progress" and then if some block tries to eval A again before it finishes you know you hit a cycle.
Putting all that together once I had a basic understanding of Lisp was surprisingly painless, but the takeaway is that I never really found a way to make it extremely useful as a model of computation.
Because this forces you to do everything in very strictly functional style ways. I ended up hacking in some ideas to make state work without breaking the assumption that each block has only one possible evaluation, and so I was able to do some RNG stuff with it, but it's still really far from something I could do something useful with. (edited)
The standard idea of Lisp with a read-eval-print loop is actually easier to use than this for most purposes. Having the immediate eval for multiple different expressions was really neat - but I suppose (repeating my biggest take away) I am not sure it's practical to make that the core of the compute system. (edited)
ryanfleury Aug 05, 2020 10:42 AM
That is super interesting. I wonder how much of that can fit into a computing environment that allows for state... Like maybe it is still preferable to have something like the functional real-time evaluation thing for cases where it can be determined that something is an immutable functional computation or something.
Like it might seem useful to have that model of computation--see Excel--but maybe it isn't a hard problem to support both, and just take what you can get in both stateful computations and functional ones?
Allen4th Aug 05, 2020 10:46 AM
Right. There are a lot of neat ideas that I could think of to try "next" if I actually wanted to make Splink useful.
So one idea is that you just have these "units" or "blocks" that are already in Splink, and the eval of a unit only changes when you change it or a unit it depended on.
But then you extend that with a new sort of "unit" maybe called a "program" that explicitly does not have the ability to eval at all times.
I also have ideas about trying to make a "global environment" a more explicit thing.
Like if a unit could say "I require that there be a global variable A and B that I can read and modify" then you could "type check" these environments.
ryanfleury Aug 05, 2020 10:51 AM
Ahhhh interesting...
Allen4th Aug 05, 2020 10:51 AM
That unit couldn't depend on another unit unless it could pass along knowledge of the global variables - and it could only be called by someone who also had knowledge of those particular variables.
Then you could say "Here's a program with all it's global variables requirements" "Here's an initial value for those global variables" and then that is something you can treat as purely functional again. (edited)
One of the cool things you get if you do have purely functional expressions is that you sort of get a testing system that falls out of the compute system "for free"
👍 1
You just have some units that form tests, set up the expression however you want and then check if the evaluation is what you expect.
Which is why I bothered exploring this in the first place.
Or "one reason why" I should say.
But, yeah, I just don't know how to make it practical.
ryanfleury Aug 05, 2020 10:56 AM
Yeah definitely makes sense. I am just imagining a C editor or something where you hover over things, and you get two possible results: 1. The value of the functional value, computed in real-time 2. "Indeterminate"
And maybe that allows for the functional tool that tests assertions on pure functions that should always be true, and allows for mutable state.
Allen4th Aug 05, 2020 10:59 AM
So a C-like that always includes in it's type information of functions the rules about visibility of globals in the function is a very interesting idea.
Then a pure-functional function would just be one with no global visibility.
But still you need another step which is the expressions that form the tests. Basically a "test" at least in this sense is a pure-functional function and inputs.
Another cool thing about explicit global visibility in the type information, when you also imagine putting it into a compute engine instead of a textual language, would be very easy transition paths from global variables to context pointers.
Transitioning from:
gl_buffer : GLBuffer; // ... proc render_rect(rect : Rect, color : Color) globals[gl_buffer : GLBuffer]{ // ... }
RenderCtx :: struct{ gl_buffer : GLBuffer; }; // ... proc render_rect(ctx : In-Out RenderCtx, rect : Rect, color : Color){ // ... }
But anyway - that's fairly far off the topic of things I actually got a chance to try with Splink 😄
bvisness Aug 05, 2020 11:05 AM
not at all, that's the point of this fishbowl
bvisness Aug 05, 2020 11:18 AM
I just can't wait for @nakst to be online and tell us about flip
nakst Aug 05, 2020 11:34 AM
oh yeah I'm here
what do you want to know about @bvisness ?
bvisness Aug 05, 2020 11:35 AM
Whatever you found interesting about the project!
Certainly I think it's already amazing that we had an OS entered into our jam
I'm curious how long it took just to get something off the ground
but also I'm curious what you liked and disliked about the result, any surprising new discoveries, whatever
nakst Aug 05, 2020 11:37 AM
So ... it's not actually that hard to make a single tasking 16-bit OS for x86, since the BIOS can do most of the heavy lifting for you (disk/floppy access, graphics, keyboard input)
I had got a working environment to start write the lisp interpreter within only a few hours.
From there, it took a few days to write the base interpreter. I was mostly using the design of rxi's fe, with some small changes.
One thing that I thought worked out quite nicely was memory management. All objects are stored in a 64KB block on memory, and all string segments are stored in another 64KB block. So I could set 2 segment registers (fs/gs) at the start of the program to access objects and strings respectively. Therefore a pointer to an object can fit in 2 bytes, and you don't have to add an offset to it, just use the correct segment register
On the lisp side of things, I knew that adding string manipulation builtins was going to be difficult. In the rxi-fe design, strings exist as a linked list of small sections of the string (in flip, each section is 8 bytes: a 2 byte next pointer (qword aligned, so 3 bits spare for misc flags), and 6 ascii chars). So it's not very easy to do things like take a substring, or index individual characters. What I decided to do was use a Unix pipes inspired approach ...
For example, when you read a file, [read "my file.txt"] then the contents of the file is written to the terminal. If you want to store the contents of the file in a string, then you can use the capture builtin, which "captures" whatever is being output to the terminal, e.g. [capture [read "my file.txt"]] returns a string with the contents of the file. This extends to being able to capture anything, e.g. [capture [print [+ 30 50]] will create a string with "80" written in ASCII
writing to a file does something similar, it will "capture" anything that's printed, and write it to the file. so to copy a file, you do [write "file 2.txt" [read "file 1.txt"]]. the read builtin streams out all the data in the file (in buffered chunks), and the write builtin captures it, and writes it to the second file
this is really nice because it requires basically no memory (other than some small buffers), to be able to do fairly complex string operations
concatenating strings is just printing them both, and capture in a single string: [capture [print string1] [print string2]]
to upper case string, there is a special capture command that upper-cases anything passed in: [capture-upper [print "hello"]] makes string object containing "HELLO". similar for lower case. I wanted to upper case a "pipe" function, so instead you'd do [capture [to-upper [print "hello"]]], where to-upper converts what's being sent through the stream to upper case, without having to store it in a string. that makes it more composable, so if you just wanted to print a string in upper case, you'd do [to-upper [print "hello"]], rather than having to store it in an intermediate strings... however I ran out of time before I could implement this
to make a substring, there is a just a special command to print a substring [print-substr "hello world" 3 5] prints "lo wo" (although I can't remember the exact order of the arguments)
All these streaming functions were really easy to implement, actually! for example, here is the capture builtin code (simplified slightly)
do_builtin_capture: ; Push the old stream callback and its data onto the stack. push word [print_callback] push word [print_data] ; Set our callback. mov word [print_callback],capture_string ; ... create empty string object ... ; (omitted) ; Store string as our callback data. mov [print_data],dx ; ... evaluate next argument ... ; (omitted) ; Restore previous stream callback. pop word [print_data] pop word [print_callback] ret capture_string: ; The callback! ; Read each character.. lodsb or al,al jz .done ; And append it to the string. mov bx,[print_data] push si call string_append_character pop si mov [print_data],bx jmp capture_string .done: ret
all that you have to do to receive data, is save the old callback, update the callback to your callback, and then restore the previous one once your builtin finishes
the builtins that write data to the stream just use the standard printing functions
that's all I really have to report, I think. Unless people have questions?
bvisness Aug 05, 2020 12:04 PM
I really like the idea of lisp functions that operate on streams
nakst Aug 05, 2020 12:04 PM
rough breakdown of lines count (~5700) 30% interpreter core 15% OS stuff, error handling 30% builtins 20% IO, filesystems 5% actual lisp code (the included programs)
@bvisness yeah, it worked out really nice, even though it was just initially a hack to get file IO working without proper traditional string manipulation (edited)
bvisness Aug 05, 2020 12:05 PM
that already looks like a far more pleasant shell than any I've ever used
I wonder what it would take to apply that shell design to an existing operating system
nakst Aug 05, 2020 12:07 PM
also, my favourite feature in the shell :) (edited)
bvisness Aug 05, 2020 12:11 PM
man, for the rest of the week now I'm gonna be frustrated with my shell for not being lisp
nakst Aug 05, 2020 12:12 PM
it sure would be nice to have a shell where i actually knew how to evaluate arithmetic expression 😆
i have given up on linux, and just started using firefox as a calculator...
bvisness Aug 05, 2020 12:18 PM
well bash is the only programming environment I've ever used where I have to look up the syntax of if statements literally every time
it's a syntactic nightmare
☝️ 1
Allen4th Aug 05, 2020 01:05 PM
Pitch: Lispish language, compiles to shell and batch, maybe a virtual machine debugger too
If I was going to make more progress on Splink, I think I would experiment with a lisp debugger, as I think you could do some pretty useful stuff there given that it is specialized to a Lisp interpretation machine.
And having a cross OS shell script and better shell script debugging is something I think would be super useful.
bvisness Aug 05, 2020 01:23 PM
shell scripts are such important glue in so many areas, and yet they are always done in just the worst programming languages
I would love to see a richer shell environment that way
and, if you allow people to omit parentheses on the outermost thing, the basic experience probably wouldn't be that different
(I dunno if it's a bad idea to allow people to omit parentheses.)
So one thing I'm curious about is if the work people did on these projects changed their opinion of Lisp at all, given that we certainly don't see much of it around here. (edited)
I went from not understanding it and thinking it was hard to read, to seeing a lot of new value in it (but also that is hard to read)
I wouldn't really say that my opinion changed, but I certainly learned a lot about it.
Allen4th Aug 05, 2020 01:41 PM
So I spent the last few days of my work on Splink more focused on trying to use it to see if it was any good and I definitely came away from it seeing the some real issues with Lisp.
I think the basic concept that your built ins are just special types of "nodes" that have built in apply rules is cool, and the idea of a macro as just an apply form that doesn't eval it's arguments etc. is cool too.
It has the flexibility/power to define all sorts of things, but it's also important to examine how difficult it is to actually define anything with it.
So like, the super powerful version of a macro lets you say something like "read this variable, do some math, then store a new value for this variable that is visible in my environment not just yours"
To actually do this a macro in Splink (and I think in most Lisps? Not sure) has to return a Lisp AST that then gets evaluated in the caller's context.
But that makes it really hard to correctly write the body of a macro because the thing you actually have to construct looks so different from the code you would have to write in-line to achieve the same effect.
(:= x (+ x 1)) becomes (and this is probably wrong but it's something like this) (list := arg (list + arg 1))
And then if you want your macro to have rules like, "please eval this argument but not this" or, "put this define in the caller's context but not this one" it's super confusing and would take me hours of tinkering with recursion, and lists, and quotes, just to finally get to the pattern I wanted.
Point is I think it is a system that stands out for the depth to which it can modify itself. But it fails in the important criteria of making things which seem like they should be trivial, actually be trivial. (edited)
bvisness Aug 05, 2020 01:50 PM
So how might you choose to fix some of those issues? Or do I need to wait for Handmade Seattle 😛
Allen4th Aug 05, 2020 01:51 PM
Haha well I am not sure exactly, but to put it simply I think doing everything as sort of fixed expression functional style stuff makes it harder than it needs to be.
A typed procedural thing might be more verbose, but it'd be easier to see that a particular macro is saying "here's the root of my tree" "here's where I evaluate and save the result for the first argument" "here's where I ..." you get the point.
At least for me, just being able to think about my lists and trees in a typed procedural language would have been a lot more effective. (edited)
bvisness Aug 05, 2020 01:52 PM
did working with Splink change your thinking at all on the "homoiconicity" thing? (which I will define as heavy use of simple, uniform building blocks) (edited)
Allen4th Aug 05, 2020 01:54 PM
Yes and no.
Given your definition, I was already a huge fan of that pattern going into Splink.
But I also don't necessarily think that's exactly a useful definition of homoiconicity.
But certainly I came out of it with an even deeper appreciation of how far you can go with a few basic building blocks.
bvisness Aug 05, 2020 01:55 PM
I didn't want to define it as "everything uses exactly one form" because I think we disputed whether that was even true of Lisp during the jam
Allen4th Aug 05, 2020 01:57 PM
For instance, I now am fairly convinced that something like Splink would be a really useful way to construct a "typer" for a C-Like that has to simultaneously figure out the sizes/offsets of type members, resolve the constant expressions of arrays, and check the types of everything along the way. I realized that doing that is quite similar to what Splink has to do, and that maybe building the typer out of a single "lego brick" rather than a specialized piece for each thing would make a lot of sense.
Right, my take away on the word homoiconicity is more or less that I don't know what it means, but it vaguely means "those things that are special about Lisp" (edited)
bvisness Aug 05, 2020 01:58 PM
therefore lisp is the most homoiconic possible language 😛
ryanfleury Aug 05, 2020 04:05 PM
I think that'll probably do it for this Fishbowl discussion. Thanks everyone for participating, it was a really interesting discussion! End of Fishbowl Day 3, thanks everyone for participating! (check pinned messages for conversation start)