ACNews #71 03 августа 2018

Listh language news - down pros and cons of lists vs. heap.

                      Listh language news
                        by Alone Coder

For a long time I guessed do we need extra data structures
except lists, that seemed memory bloat. So I wrote down pros and
cons of lists vs. heap:

- a record in a heap can be indexed (to make an array), a list
can not.
? "first fit" heap (very slow) is fulled up to 85%, so it keeps
3.4 times more strings than list (however, my lists allow 16-bit
strings), and 1.7 times more code. "Buddy" heap (of medium
speed) is filled up to 75%, so it keeps 3 times more strings
than list (however, my lists allow 16-bit strings), and 1.5
times more code. But these figures are for 10-100 byte records,
and heaps lose memory on small records ("first fit" heap needs 8
extra bytes for every record). 4 elements in a row (16 bytes in
heap, 16 bytes in list) or a 3-symbol string (12 bytes in heap,
12 bytes in list because it doesn't need '' terminator) are
better to keep in lists!
+ list reserves and frees memory at O(1) time, almost instantly.
+ list has no limitation on data length, it will be reserved
always if we have enough memory, even 100 KB as one list.
+ making a list in a heap is 3 times the size (12 bytes per
element vs. 4).
+ making a binary tree in a heap: 12 bytes per node (using NIL),
in lists: 4 bytes per node (using NIL) - leaves are thought to
be kept separately and pointed to.
+ lists can grow and shrink, but heap records can not.

So, everything is not so bad with lists, the only real trouble
is making arrays with them.

a) indexing the elements of a list - O(i). 
b) make a list of even elements of the list, make another over 
that, etc. recursively - O(log(n)). 
c) add 256 byte blocks and use them as list elements? (keep 
pointers to them and have indexing operators?.) Memory for lists 
can be based on these 256-byte blocks, we can even free them 
back (if we have a counter in every 256-byte block). For that, 
the list of free elements must be double-linked, then we could 
remove empty elements and release the 256 bytes block. 
d) add a heap? How to share memory between lists and the heap? 
e) just write and read memory using POKE and PEEK. 

I chose the last option, but for the future I reserved the
possibility to add 256-byte blocks (for that, I made
double-linked list of free elements, the backward link being in
"value" slot, to make possible freeing of elements in a 256-byte
block when it goes free).

In the previous publication, I wrote incomplete listing of the
interpreter and handlers, even undebugged. Overall, a minimum
working environment includes:

- interpreter
- math (T, NIL, +, -...)
- list handling (VALUE, NEXT, FORM...)
- pseudo-stack handling (DUP, DUP2(repeat 2 elements), DROP,
SWAP, OVER(repeat 2nd element), ROT(extract Зrd element)...)
- memory handling (NEW, DEL...)
- variables (NEWVAR, FINDVAR, =>, DEF, DEFUN, EVAL...)
- terminal (ttypeek, ttyget (initially works from memory, then a
patch is executed to use keyboard), ttyput...)
- decoding and running a Listh command from terminal.

The rest can be written in Listh itself of added as extra
handlers.
The editor (decoding and running) could also be written in
Listh. Initially I made it that way, planning to type in these
Listh functions in assembly text (as a sequence of dw:dw), but
that required program structures (IF, WHILE...). So I just
compiled the functions in asm by hand, and added others in asm
as well.

All the lisp-lists (user command, VarList, Prog) can be printed.
For that, they have in the first element the address LispList,
then contain the pointers to data terms, then finally the
pointer to term EndLisp. Terms are also lists (not lisp-lists),
in the first element they contain the address of the handler, in
the second element - the value, and finally the name, character
after character (even for numbers - as they can be written in
different ways but shown as they were written). The function for
printing lisp-lists - ttyputlist, in prints all the terms,
recursively, if their first element is LispList (it is not
shown, and the final element too). This function can also print
a stand-alone term (that has not LispList in its first element).
Pure number lists are not supported by this function, a separate
function must be written for that.

The following milestones were passed:

+ working with memory (NEW, DEL), tested with trace
+ printing a number - ttyputnum, tested from asm
+ printing a string - ttyputstr, tested from asm
+ reading a nested lisp-list (consisting of known elements),
strcmp is tested by asm, memory is tested with trace (READTERM
(READTERM) READTERM)
+ printing a nested lisp-list, check if it matches the inputted
one (READTERM (VarList () readlist) READTERM)
+ interpreting a lisp-list (VarList ttyputlist) - prints the
list of variables, check it
+ interpreting math (T T + T ttyputnum ttyputnum)
+ interpreting a nested lisp-list (T - (T + T) DUP ttyputnum NOT
ttyputnum)
+ reading numbers (with auto creation of a constant if it is
absent), test with (13 + 13 ttyputnum VarList ttyputlist)
+ reading strings (with auto creation of a constant if it is
absent), test with ("abc" ttyputstr VarList ttyputlist)
+ showing free memory (FreeMem ttyputnum)=1AЧC ("abc" ttyputstr
VarList ttyputlist FreeMem ttyputnum)=1984
+ clear the word that is found, or an erroneous word typed in
(to free memory) (FreeMem ttyputnum)=1A44 ("abc" ttyputstr
VarList ttyputlist FreeMem ttyputnum)=19E4
+ defining a variable (adding it in the Prog as a command, the
initial value is parenthesised) (DEF "newvar" (15) VarList
ttyputlist) ??? (DEF "newvar" (15 + 11) VarList ttyputlist)
+ printing the Prog (all DEF commands) (DEF "newvar" (15)
VarList ttyputlist Prog ttyputlist)
+ executing several commands (DEF "newvar" (15) VarList
ttyputlist Prog ttyputlist FreeMem ttyputnum)(newvar ttyputnum)
+ defining a function (adding it in the source) (DEF "newvar"
(15) DEFUN "newfun" (VarList ttyputlist Prog ttyputlist) FreeMem
ttyputnum)(newvar ttyputnum newfun)
+ QUOTE command to make a pointer (QUOTE (VarList ttyputlist
Prog ttyputlist) DUP ttyputlist EVAL FreeMem ttyputnum)
+ while defining a function, put it in the end of Prog, not the
beginning, to make it appear later than its variables
+ a command to copy a list (QUOTE (VarList ttyputlist) FreeMem
ttyputnum copylist FreeMem ttyputnum DUP ttyputlist dellist
FreeMem ttyputnum)
+ a command to copy a tree (i.e. LispList with inner LispLists):
(QUOTE (VarList (13) ttyputlist) FreeMem ttyputnum DUP
ttyputlist deltree FreeMem ttyputnum)
+ a command to delete a tree (i.e. LispList with inner
LispLists): (QUOTE (VarList (13) ttyputlist) FreeMem ttyputnum
copytree FreeMem ttyputnum DUP ttyputlist deltree FreeMem
ttyputnum)
+ keyboard input (parenthesised, press Enter after a command),
with echo, show error after unknown identifier, and NIL will be
kept instead
+ printing the free memory before input, after input, and after
command execution
+ reading symbol comstants (with auto creation of a constant if
it is absent, no space or quote), test with ('A' ttyputnum
VarList ttyputlist)
+ negative numeric constants
+ delete command after execution (before that, copy all the new
words from it to VarList, and DEF/DEFUN must copy definitions to
Prog)

Future plans:

- a command to delete variable/constant/function from Prog and
VarList (with checking whether it's used?)
- a command to output the Prog to file (without the outer
parentheses, so we will have a set of relatively short commands)
- a command to load the Prog from file
- THEN (...) ELSE (...)
- REPEAT (...) //UNTIL T
- comments, word input must support spaces in them
- escape codes in string constants