XXIIVV

A cons cell is a data structure which holds both data and the address to the following cell.

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.

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 into 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 JSR2
	;cat ;cons JSR2
		;dog ;cons JSR2
			;owl ;cons JSR2
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 JSR ;nil

@cons ( list* fn* -- list* )

	( car ) ,alloc JSR STH2k STA2
	( cdr ) STH2kr INC2 INC2 STA2
	STH2r

JMP2r

Duplicate/Remove

We can build new primitives to duplicate, remove and swap cells from the list:

@pop ( list* -- list* )

	INC2 INC2 LDA2

JMP2r

@dup ( list* -- list* )

	LDA2k ,cons JSR

JMP2r

@swap ( list* -- list* )

	LDA2k STH2 ,pop JSR LDA2k STH2 ,pop JSR
	SWP2r
	STH2r ,cons JSR STH2r ,cons JSR

JMP2r

Nesting two lists

You can make a list of lists, or nested lists, using the @cons routine with two cons cells from different lists.

( list1 )
;nil JSR2
	;cat ;cons JSR2
		;dog ;cons JSR2
			;owl ;cons JSR2
( list2 )
;nil JSR2
	;ant ;cons JSR2
		;bat ;cons JSR2
			;cow ;cons JSR2
( list3 list1 list2 )
;nil JSR2
	SWP2 ;cons JSR2
		SWP2 ;cons JSR2
;echo JSR2
	

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* -- list* )

	&w INC2 INC2 LDA2 LDA2k ;nil NEQ2 ,&w JCN #0004 ADD2

JMP2r

@join ( list-a* list-b* -- list-b* )

	STH2k ,last JSR STA2 STH2r

JMP2r

@unwrap ( list* -- list* )

	INC2k INC2 LDA2 SWP2 LDA2 STH2k ,last JSR 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 JCN
	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 ,&fn JCN
			( list )
			LDA2k ;echo JSR2 ,&resume JMP
			&fn
			LDA2k LDA2 ,print JSR #2018 DEO
		&resume
		INC2 INC2 LDA2 LDA2k ;nil NEQ2 ,&w JCN
	POP2
	#2918 DEO #2018 DEO

JMP2r

@print ( short* -- )

	SWP ,&byte JSR
	&byte ( byte -- ) DUP #04 SFT ,&char JSR
	&char ( char -- ) #0f AND DUP #09 GTH #27 MUL ADD #30 ADD #18 DEO

JMP2r