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 And False
True Not False
True False Or True
```

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

@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
```