libera/#commonlisp - IRC Chatlog
Search
5:22:16
hayley
minion: memo for pve: For your amusement, Clouseau inspecting objects in a Smalltalk-ish language: <https://social.applied-langua.ge/media/cc8fba53-74a0-4a5a-9a1c-a4f0967de6b4/parser-test-in-clouseau.png>
7:34:17
bitblit1
Oh yeahhhh I remember. Stupid question but does it work with normal common lisp or just inspects CLIM code?
7:39:21
bitblit1
One basic thing I forgot about common lisp; If variables don't have types but objects do, what goes in the heap and what goes in the stack?
7:39:57
White_Flame
there are usually tag bits in the machine word that says what the value's type is
7:41:16
beach
bitblit1: If you can't tell the difference, then the implementation is allowed to (and usually will) optimize.
7:41:28
hayley
A cheeky implementor might choose to put objects on the stack. Or in regions. Or maybe the disk. Or wherever they feel like, in general.
7:42:07
White_Flame
consider a 64-bit system. 64 bits = 8 bytes. So objects are at a multiple of 8 bytes apart in memory organization,m eaning the bottom 3 bits of hte address are always zero
7:42:28
White_Flame
or it could allocate on a doubleword resolution meaning 16 bit stride in memory, thus the bottom 4 bits are always zero
7:42:42
beach
bitblit1: For example, most implementations will encode a fixnum in the pointer itself, rather than allocating memory for it.
7:43:09
White_Flame
because that's where the tags go, whie still being able to point ot everything in address space
7:43:37
hayley
beach: I wrote an ACCEPT method for reading forms (since I don't quite use Common Lisp syntax), added an eval-in-frame command, and now I can pretend I made an IDE.
7:44:14
hayley
Suppose you have 8 byte alignment, then you can assume that the three lowest bits of any pointer to an object in the heap are all zeroes.
7:45:46
beach
bitblit1: If your processor uses byte addresses, and every pointer points to a word that is aligned to 8 bytes, then the three lower bits will be 0.
7:45:49
White_Flame
the other tags will say "the rest of the word is a pointer to an object of this class"
7:46:04
hayley
Because the allocator lets you assume that, and makes sure that objects are aligned to eight bytes.
7:46:42
bitblit1
beach: Ohhhhhhhhhhhhh, so a word is four bytes that leaves the bottom 4? no so it is 7... wait?
7:48:05
White_Flame
an implementation can literally store things however it feels like. but there's certain things that are advantageous on common processor designs
7:48:51
White_Flame
tag for "this is a pointer to a cons cell", "this is a pointer to a string", etc
7:50:23
White_Flame
if it knows that it's a cons cell, it can dereference it with a -7 offset to directly hit the cons cell storage without having to mask off the tag bits
7:50:59
bitblit1
White_Flame: Wait, so by this you mean that the value pointing to it would be stored AT 0x1007??
7:52:33
White_Flame
the value at 0x1008 as the cdr could contain the raw machine value 0x1017, which references the next cons cell at 0x1010
7:53:08
White_Flame
or it coud be 0x001f, which let's say 0xf is the tag fro a fixnum, and that's the value 1
7:53:56
bitblit1
White_Flame: Wait, so when you say references AT, you mean it points to right? Not like it is STORED AT?
7:56:02
White_Flame
so we read 0x1000, which is the raw value 0x001f, which is the literal value 1 (fixnum tag 0xf)
7:56:56
White_Flame
so those 4 bytes represent (1 2), and any slot holding the raw machine word 0x1007 is a reference to that list
7:59:10
aeth
in CL, the type tag is basically just achieved with ASH to shift in both directions. One direction removes the tag and gets the data (which is why in SBCL if you disassemble a function with the constant value 1 it shows up as 2, and with 2 it shows up as 4, etc.)
8:01:05
aeth
I'm just guessing that one of the directions would be something like (using the 7 tag) this: (format t "#x~X" (logior (ash 1000 1) #x7)) => #x7D7
8:02:42
beach
An object can be allocated on the stack if that turns out to be safe to do, and slots in objects allocated on the heap will contain tagged pointers.
8:07:31
aeth
but e.g. (format t "#x~X" (logior (ash 1000 8) #x7)) and then reverse it with (format t "~D" (ash #x3e807 -8)) to get 1000 back.
8:07:56
aeth
you can make a list contiguous with CDR coding but modern implementations don't think that it's a worthwhile optimization https://en.wikipedia.org/wiki/CDR_coding
8:08:21
White_Flame
garbage collectors probably also end up reordering lists in car cdr car cdr car cdr order
8:09:58
bitblit1
Wait at the beginning? Why is it O(n)? itn't it like the first object pointed by memory
8:10:58
bitblit1
but a chain of cons cells where each cell consists of 2 words where 1 word is the car and value and the 2nd word is the pointer to the next cell or nil.
8:11:45
beach
bitblit1: You might get some help here: http://metamodular.com/Common-Lisp/Tutorial/semantics.html
8:12:28
aeth
(if foo x y) is probably (if (eql foo nil) y x) at the low level. At least, that's the most obvious way if NIL isn't 0 in the lowest level representation
8:13:53
White_Flame
remember, NIL is a symbol and obeys the cons cell interface, eg (car nil) => nil, (cdr nil) => nil
8:14:56
bitblit1
so a boolean tag would be just a bit but takes but the rest of the three bits (I still don't get why it's not 4) and so it's just a bit where 0x0 = NIL and 0x1 = T
8:18:39
White_Flame
if you only have 3 or 4 bits of tag, then one bit that's a massive percentage of that limited space
8:24:19
beach
bitblit1: In chapter 16 of http://metamodular.com/SICL/sicl-specification.pdf you can see how we do it in SICL.