Listh Language News - Pros and cons of list storage versus heap storage.

Listh Language News
 by Alone Coder

I weighed for a long time whether additional
data structures other than lists, which seemed
wasteful of memory. I decided to write down the pros and cons
List storage vs heap storage:

- an entry in the heap can be indexed (there will be an array), and a list
impossible.
? first fit heap (very slow) is filled to 85%, that is
for strings it is 3.4 times more profitable (but we can in the list
store 16-bit strings), and for programs 1.7 times than
list. The buddy heap (medium-slow) is filled to 75%, that is
for rows it is 3 times more profitable (but we can in the list
store 16-bit strings), and for programs 1.5 times than
list. but these numbers are for blocks of 10-100 bytes, and the heap loses a lot
memory on small records (it needs an extra 8bytes per write).
4 elements in a row (16 bytes in the heap, 16 bytes in the list) or string
of 3 letters (12 bytes in the heap, 12 bytes in the list, because not needed)
It is more profitable to store in a list!
+ list allocates and frees memory in O(1), practically
instantly.
+ the list has no restrictions on the length of the selected fragment, it
will always be allocated if there is free memory. you can even 100
kilobytes in one list.
+ implementing the list on the heap will give a loss of 3 times (12 bytes per
element versus 4).
+ implementation of a binary tree on the heap: 12 bytes per node
(using NIL), on list: 4 bytes per node (using NIL) -
we believe that the sheets are stored separately, we only point to them
otherwise depends on the sheet size.
+ the list can be increased and decreased, but the heap element cannot.

That is, not everything is so bad, the only real problem is how
implement an array on lists.

a) enumerating the list - O(i). 
b) make a list of even elements on top of the list, on top of that 
too, etc. - O(log(n)). 
c) add allocated blocks of 256 bytes as elements 
list? (store pointers to them and have operations 
indexing.) memory for lists can be made on these 
blocks, they can even be released back (if you have a counter in 
each). To do this, the free list can be made doubly connected, 
then it will be possible to turn off empty elements of the block and give 256 
byte. 
d) add a bunch more? how to divide memory between list and heap? 
d) simply work in memory through POKE and PEEK. 

I chose the last option, but I laid down the possibility in the future
use 256-byte blocks (for this you had to do
the list of free elements is doubly connected so that you can
discard elements in a 256-byte block when it
will be released).

Last time I did not write all the interpreter code and
handlers, moreover, undebugged. Generally minimal environment
execution includes:

- interpreter
- arithmetic (T,NIL, +, -...)
- working with lists (VALUE, NEXT, FORM...)
- work with the stack (DUP, DUP2 (repeat 2 elements), DROP, SWAP,
OVER(repeat 2nd element), ROT(remove 3rd element)...)
- working with memory (NEW, DEL...)
- working with variables (NEWVAR, FINDVAR, =>, DEF, DEFUN,
EVAL...)
- work with the terminal (ttypeek, ttyget (initially works from
memory, then the patch will work to switch to the keyboard),
ttyput...)
- decoding and execution of lispotekst from the terminal.

The rest can be written on Listh itself or gradually added
assembly processors.
You can write the editor (decryption and execution of commands) in
Listh itself. At first I did just that, planning to type these
Listh functions directly in the assembly text (in the form
sequence dw:dw), but for this you need to immediately implementprogram structures (IF, WHILE...). So I just manually
compiled the necessary procedures into assembler, and as
Whenever necessary, I wrote new ones directly in assembler.

All lists (entered command, VarList, Prog) are made
outputable. To do this, they have the LispList address at the beginning, in
in the middle there are pointers to content terms, and at the end there is a pointer to
term EndLisp. Terms are also lists; their first element has an address
handler, in the second the value, and then the name one character at a time
(this also applies to numbers - after all, they can be written in different ways, and
must be shown exactly as entered). Print function
list of lists ttyputlist recursively displays all terms for which
the first element contains the address of the LispList (it is not displayed, just like
last element). This function can also print a separate term
(its first element is different from LispList). Naked lists
This function cannot print numbers, you can write a separate one
function for this.

During the implementation process, the following milestones were passed:

+ work with memory (NEW, DEL), check with trace
+ print the number ttyputnum, check by calling from ASMA
+ print the ttyputstr line, check by calling from ASMA
+ reading a nested list (from known elements),check the operation of strcmp with asmov inserts, check how it fits
memory (READTERM (READTERM) READTERM)
+ print the nested list, check that it matches
entered (READTERM (VarList () readlist) READTERM)
+ interpretation of the list (VarList ttyputlist) - printing the list
variables, check it
+ interpretation of the list list (T T + T ttyputnum ttyputnum)
+ interpretation of nested list list (T - (T + T) DUP
ttyputnum NOT ttyputnum)
+ reading numbers (with automatic creation of a constant, if one
not yet), check for (13 + 13 ttyputnum VarList ttyputlist)
+ reading lines (with automatic creation of a constant, if such
not yet), check for ("abc" ttyputstr VarList ttyputlist)
+ display of free memory (FreeMem ttyputnum)=1AChC ("abc"
ttyputstr VarList ttyputlist FreeMem ttyputnum)=1984
+ clear a found word or an erroneous word when entering (to
do not fill memory) (FreeMem ttyputnum)=1A44 ("abc" ttyputstr
VarList ttyputlist FreeMem ttyputnum)=19E4
+ variable definition command (with entry into the source code, in
initial value in parentheses) (DEF "newvar" (15) VarList
ttyputlist) or (DEF "newvar" (15 + 11) VarList ttyputlist)
+ print source (list of entered definition commands - in
the order in which they were entered) (DEF "newvar" (15) VarList ttyputlist Prog
ttyputlist)
+ execution of several entered lines (DEF "newvar" (15)
VarList ttyputlist Prog ttyputlist FreeMemttyputnum)(newvar
ttyputnum)
+ function definition command (with entry into the source) (DEF
"newvar" (15) DEFUN "newfun" (VarList ttyputlist Prog
ttyputlist) FreeMem ttyputnum)(newvar ttyputnum newfun)
+ command QUOTE (QUOTE (VarList ttyputlist Prog ttyputlist) DUP
ttyputlist EVAL FreeMem ttyputnum)
+ when redefining a function, put a link to it not at the beginning,
and at the end of the source, so that it is always later than the announcement
variables used in it
+ list copy command (QUOTE (VarList ttyputlist) FreeMem
ttyputnum copylist FreeMem ttyputnum DUP ttyputlist dellist
FreeMem ttyputnum)
+ tree deletion command (i.e. LispList with incoming LispList):
(QUOTE (VarList (13) ttyputlist) FreeMem ttyputnum DUP
ttyputlist deltree FreeMem ttyputnum)
+ tree copy command (i.e. LispList with incoming
LispList): (QUOTE (VarList (13) ttyputlist) FreeMem ttyputnum
copytree FreeMem ttyputnum DUP ttyputlist deltree FreeMem
ttyputnum)
+ manual input (only in brackets, enter after the closing bracket
Enter), with echo, when entering an unknown identifier immediately
an error is written, and NIL is included in the list
+ print free memory before input, after input and after
command execution
+ reading characters (with automatic creation of a constant if
there is no such thing yet, a space or a quote is not allowed), check for ('A'
ttyputnum VarList ttyputlist)
+ negative numeric constants
+ clearing the entered command (preliminarily all new words from
the entered command is copied to VarList, and with DEF/DEFUN
definitions are copied to Prog)

Plans:

- command to remove a variable/constant/function from Prog and
VarList (with usage check?)
- command to output the source to a file (without external brackets, so
you will get a set of relatively short commands)
- command for entering sources from a file
- command THEN (...) ELSE (...)
- command REPEAT (...) //UNTIL T
- comments, word input must support spaces in
comments
- escape codes in string constants