A quick-n-dirty guide to function programming concepts in Uxntal.
Functions are the only primitive data types in untyped lambda calculus. It is nevertheless possible to represent numerals, booleans, lists, sets, characters and strings as higher order functions in untyped lambda calculus using Church encoding.
To familiarize yourself with Combinatory Logic, begin with the primer.
Church Booleans
In Uxntal, to apply an operation from a value on the stack, we use the Identity macro, which pops a byte from the stack and writes it in front of the Program Counter. It is possible to put the literal values of opcodes on the stack, operate the stack and apply them at a later time, this is done with the #00 STR 00 pattern.
%I { #00 STR 00 }
%True { LIT POP }
%False { LIT NIP }
%And { DUP I }
%Not { False True ROT I }
%Or { DUP Not I }
%Nand { And Not }
Booleans can be represented as operations that expect two values on the stack, returning the first argument if True, or POP, and the second if False, or NIP.
False True AndFalse True NotFalse True False OrTrue
Currying
Currying is the technique of converting a routine that takes multiple arguments into a sequence of routines that each takes a single argument. Functions are curried when we partially apply their arguments, both invocations returned functions into which the partially applied values are baked.
INCRABC ( a b c -- res ) ROT INC ROT INC ROT INC JMP2r
Running routines over an array
You might want to run a routine over an array of data, in the style of:
array.each(incr)
You can create a each routine that way, but remember that this is not immutable.
|0100 ;array ;incr ,each JSR ;send ,each JSR POP2 BRK @each ( arr* fn* -- arr* ) ,&fn STR2 DUP2 LDAk #00 SWP ADD2k NIP2 SWP2 &l INC2 [ LIT2 &fn $2 ] JSR2 GTH2k ,&l JCN POP2 POP2 JMP2r @incr ( addr* -- addr* ) STH2k LDA INC STH2kr STA STH2r JMP2r @send ( addr* -- addr* ) LDAk #18 DEO JMP2r @array 06 &body "abcdef
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