Using cons cells and linked lists in Uxntal.
In functional programming languages, a list is the most versatile data type that can be used to store a collection of similar data items. Uxn uses singular opcodes operating on words of equal length, one might come across a problem that is better addressed with routines that operate on ordered lists of items and nested stacks. This 300 bytes implementation of cons cells gives your project that power.
A cons cell is data structure which holds both data and an address to the next cell.
The data slot is known as the CAR, and the address slot is known as the CDR. The purpose is so that ordered lists can be traversed by going from one cell to the next, it also allows one to change the order of cells without manually moving any of the cells' data.
Let us consider the following cons list:
(list cat dog owl)
Also equivalent to the expression:
(cons owl (cons dog (cons cat nil)))
A translation to uxntal assembly would be something like the following, in which POP2 is to get rid of the dangling pointer. This can obviously be made prettier with macros, but we'll keep things straightforward.
nil ;cat cons ;dog cons ;owl cons POP2
Creating a new list
The @alloc routine needs a @memory label to an address with enough space to host the lists, it returns the address of the newly created cell. A list begins with a cons cell whose CAR is a pointer to the cell's data and whose CDR is the next cell. A nil list begins with the nil function pointer.
The @cons routine creates a new cons cell, making the fn its CAR, and the next cell its CDR. It returns the address of the newly created cons cell. @cons is often used to add a single element to the front of a list. This is called consing the element onto the list.
@alloc ( -- cell* ) [ LIT2 &next :memory ] DUP2 #0004 ADD2 ,&next STR2 JMP2r @nil ( -- list* ) alloc ;nil @cons ( list* fn* -- list* ) ( car ) alloc STH2k STA2 ( cdr ) STH2kr INC2 INC2 STA2 STH2r JMP2r ( values ) [ @cat =dict/cat :nil @dog =dict/dog :nil @bat =dict/bat :nil @ant =dict/ant :nil @owl =dict/owl :nil @cow =dict/cow :nil ] @dict [ &cat "cat $1 &dog "dog $1 &bat "bat $1 &ant "ant $1 &owl "owl $1 &cow "cow $1 ] @memory $4000
Nesting two lists
You can make a list of lists, or nested lists, using the @cons routine with two cons cells from different lists.
nil ;cat cons ;dog cons ;owl cons nil ;ant cons ;bat cons ;cow cons nil SWP2 cons SWP2 cons echo ( ( owl dog cat ) ( cow bat ant ) )
Joining two lists
Two lists of cons cells can be joined together into one by modifying the last pointer of the second list, and pointing it to the first one.
@last ( list* -- cell* ) &w INC2 INC2 LDA2 LDA2k ;nil NEQ2 ?&w INC2 INC2 JMP2r @join ( list-a* list-b* -- list-b* ) STH2k last INC2 INC2 STA2 STH2r JMP2r
Finding the length
This routine will run through a list and return its length.
@length ( list* -- length* ) LIT2r 0000 &w INC2 INC2 INC2r LDA2 LDA2k ;nil NEQ2 ?&w POP2 STH2r JMP2r
Printing a list
Running through a list and its nested lists is a matter of itterating through each cell's CDR until a ;nil pointer is found. The following routine will run recursively. If the list is a series of function pointers, you can modify this into an evaluation routine.
@echo ( list* -- ) #2818 DEO #2018 DEO &w LDA2k INC2 INC2 LDA2 ;nil EQU2 ?&value ( list ) LDA2k echo !&resume &value LDA2k LDA2 pstr #2018 DEO &resume INC2 INC2 LDA2 LDA2k ;nil NEQ2 ?&w POP2 #2918 DEO #2018 DEO JMP2r @pstr ( str* -- ) &w LDAk #18 DEO INC2 LDAk ?&w POP2 JMP2r