Quicklinks | Readinglist | Computing | Picolisp | The Picolisp Reference | ASM | Pil Tutorials |

# The Picolisp Machine

One of the key features of the picolisp language is that high-level constructs of the language directly map to the underlying machinery, making the whole system both understandable and predictable.

Also please note that there are still a number of possible errors in this Document, it is under active development

#### Data Types

These are the fundamental datatypes in Picolisp:
```
cell
|
+-----------+-----------+
|           |           |
Number       Symbol       Pair
S010 S100      1000        0000
(cnt | big)      |
|
+--------+----- --------+-----------+
|        |              |           |
NIL   Internal       Transient    External
\           /            |
0010 Short name        1010 Short name
0100 Long name         1000 Properties
0000 Properties

```

#### The Cell

The most fundamental datatype is the cell which is the building block for all other data types.
```
+-----+-----+
| CAR | CDR |
+-----+-----+

```
Consider memory as an array of bytes growing downwards.
```
each x, c, i is a bit (0 or 1)
x means "address  bit, unimportant if it is 0 or 1"
i mean  "special  bit for the Interpreter"
c means "contents bit"
S means "Sign bit, 1 means negative, 0 positive"

Them Address are 64 bits in Length                                          the lowest 4 bits are used by the interpreter
to figure out which type the value is
|
B8       B7       B6       B5       B4       B3       B2       B1   |          ContentsV
--------------------------------------------------------------------------------------------------------
ADDRESS: xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 0000, BYTE  0: cccc iiii  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 0001, BYTE  1: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 0010, BYTE  2: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 0011, BYTE  3: cccc cccc  |__ CAR (8 Bytes long, 64 bits)
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 0100, BYTE  4: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 0101, BYTE  5: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 0110, BYTE  6: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 0111, BYTE  7: cccc cccc  |
--------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------
ADDRESS: xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 1000, BYTE  8: cccc iiii  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 1001, BYTE  9: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 1010, BYTE 10: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 1011, BYTE 11: cccc cccc  |__ CDR (8 Bytes long, 64 bits)
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 1100, BYTE 12: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 1101, BYTE 13: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 1110, BYTE 14: cccc cccc  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx 1111, BYTE 15: cccc cccc  |
--------------------------------------------------------------------------------------------------------__ Beginning of Next Cell
ADDRESS: xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxx1 0000, BYTE 16: cccc iiii  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxx1 0001, BYTE 17: cccc cccc  |
V

```
The Same Contents can be written linearly like:
```          BYTE 7   BYTE 6   BYTE 5   BYTE 4   BYTE 3   BYTE 2   BYTE 1   BYTE 0

pair  cccccccc cccccccc cccccccc cccccccc cccccccc cccccccc cccccccc cccc 0000

cnt   cccccccc cccccccc cccccccc cccccccc cccccccc cccccccc cccccccc cccc S010

big   cccccccc cccccccc cccccccc cccccccc cccccccc cccccccc cccccccc cccc S100

sym   cccccccc cccccccc cccccccc cccccccc cccccccc cccccccc cccccccc cccc 1000

```

The lowest bit (M) of a cell is set for garbage collection.
```
[bit0]
|
B8       B7       B6       B5       B4       B3       B2       B1  |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx000M
|
v
[Mark for garbage collection]

```

#### Numbers

Internally, numeric values of up to 60 bits are stored in "short" numbers or count (CNT)
```
[bit1 set]
|
B8       B7       B6       B5       B4       B3       B2       B1 |
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxS010  - 10 = 2 in Binary
|
v
[sign-bit]

```
```
BYTE 1: xxxxS010
BYTE 2: xxxxxxxx
BYTE 3: xxxxxxxx
BYTE 4: xxxxxxxx
BYTE 5: xxxxxxxx
BYTE 6: xxxxxxxx
BYTE 7: xxxxxxxx
BYTE 8: xxxxxxxx

```
i.e. the value is directly represented in the pointer, and doesn't take any heap space.

Numbers larger than 60 bits are called "big nums" and are stored like this:
```

Bignum
|
V
+-----+-----+
| DIG |  |  |
+-----+--+--+
|
V
+-----+-----+
| DIG |  |  |
+-----+--+--+
|
V
+-----+-----+
| DIG | CNT |
+-----+-----+

```
```
[bit2 set]
|
B8       B7       B6       B5       B4       B3       B2       B1|
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxS100    - 100 = 4 in binary
|
v
[sign-bit]

```

#### Symbols

```
Symbol
|
V
+-----+-----+
|  /  | VAL |  Getting the Value of a symbol is super efficient as the
+-----+-----+  pointer points directly to it.
_____
|     |
V     V
+-----+-----+
| CAR | CDR |
+-----+-----+
|
V
'tail' is kept in the CAR

```
```
[bit3 set]
|
B8       B7       B6       B5       B4       B3       B2      B1|
xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxx1000  - 1000 = 8 in binary
|
v
Notice the Symbol always
points to the 8th Byte

```
##### Property Lists and Symbol Names
• A property is a key-value pair, represented by a cons pair in the symbol's tail.
• This is called a "property list".
• The property list may be terminated by a number representing the symbol's name.
• Each property in a symbol's tail is either a symbol or a cons pair with the property key in its CDR and the property value in its CAR.
• if it is a symbol, then it represents the boolean value T and the key is is the CAR
• The name of a symbol is stored as a number at the end of the tail.
• It contains the characters of the name in UTF-8 encoding, using between one and seven bytes in a short number, or eight bytes in a bignum cell.
• The first byte of the first character, for example, is stored in the lowest 8 bits of the number.
• ###### Sample Symbols
```

Symbol
|
V
+-----+-----+                                +----------+---------+
|  |  | VAL |                                |'hgfedcba'|'onmlkji'|
+--+--+-----+                                +----------+---------+
tail                                          ^
|                                            |
|                                            |
|                                            |
V                                          name
+-----+-----+     +-----+-----+     +-----+--+--+
|  |  |  ---+---> | KEY |  ---+---> |  |  |  |  |
+--+--+-----+     +-----+-----+     +--+--+-----+
|                                   |
V                                   V
+-----+-----+                       +-----+-----+
| VAL | KEY |                       | VAL | KEY |
+-----+-----+                       +-----+-----+

```
###### Bit Representations in Symbol Tails
```   Symbol tail
Internal/Transient
0010 Short name
0100 Long name
0000 Properties

External
1010 Short name
1000 Properties
^
|

Name final short
Internals, Transients
0000.xxxxxxx.xxxxxxx.xxxxxxx.xxxxxxx.xxxxxxx.xxxxxxx.xxxxxxx0010
60      52      44      36      28      20      12       4

```

###### The Symbol NIL
```

NIL:  /
|
V
+-----+-----+-----+-----+
|'LIN'|  /  |  /  |  /  |
+-----+--+--+-----+-----+

```

#### Pairs & Lists

A list is a sequence of one or more cells (cons pairs), holding numbers, symbols, or cons pairs.
```

|
V
+-----+-----+
| any |  |  |
+-----+--+--+
|
V
+-----+-----+
| any |  |  |
+-----+--+--+
|
V
...

```

#### Internal Symbols

Internal symbols are all those "normal" symbols, as they are used for function definitions and variable names. T hey are "interned" into an index structure, so that it is possible to find an internal symbol by searching for its name.

There cannot be two different symbols with the same name in the same namespace.

Initially, a new internal symbol's VAL is NIL.

#### Transient Symbols

Transient symbols are only interned into an index structure for a certain time (e.g. while reading the current source file), and are released after that. That means, a transient symbol cannot be accessed then by its name, and there may be several transient symbols in the system having the same name.

Transient symbols are used
• as text strings
• as identifiers with a limited access scope (like, for example, static identifiers in the C language family)
• as anonymous, dynamically created objects (without a name)
Initially, a new transient symbol's VAL is that symbol itself.

A transient symbol without a name can be created with the box or new functions.

#### External Symbols

The interpreter recognizes external symbols internally by an additional tag bit in the tail structure.

External symbol names are surrounded by braces { and }

The characters of the symbol's name itself identify the physical location of the external object.
• in the 64-bit version: The number of the database file minus 1 in "hax" notation
• ```(i.e. hexadecimal/alpha notation, where '@' is zero, 'A' is 1 and 'O' is 15 (from
"alpha" to "omega")),

immediately followed (without a hyphen) the starting block in octal ('0' through '7').
```
In both cases, the database file (and possibly the hyphen) are omitted for the first (default) file.