# Factor internals documentation

## Slava Pestov — 2004-12-16 04:26:21

    Hi everybody,

    I have written up a brief document explaining the inner workings of the

    Factor runtime written in C.

    I hope it sheds some light onto the workings of Factor. While you don't

    have to read it to be able to program in Factor, reading it will give a

    better understanding of what's actually going on.

    ------->8--------

    FACTOR INTERNALS GUIDE

    This guide focuses on portion of Factor that is written in C. The

    sources can be found in the native/ subdirectory.

    Factor defines a few new integer types; they will be mentioned without

    further explanation:

    - CELL: unsigned word-size field.

    - FIXNUM: signed word-size field.

    The 'CELLS' constant is defined as sizeof(CELL). The idea is to be able

    to write expressions like 4*CELLS.

    * The memory manager

    Factor's memory manager is concentrated in the files memory.c and gc.c.

    A guard page is allocated above the memory heap, and an out of memory

    condition is raised if an attempt is made to write to the guard page.

    Out of memory errors are fatal -- the garbage collector must be

    triggered before this happends.

    The alloc_guarded(CELL size) function allocates a block of memory with

    guard pages above and below.

    There are two memory zones of identical size; only one is in use at any

    one time -- this is denoted as the 'active' zone. The other is the

    'prior' zone. Each zone is identified with a ZONE struct stored in a

    global variable named after the zone's role.

    Memory is allocated in the zone using the allot(CELL a) function. This

    function takes the size of a memory block to allocate. Memory blocks are

    aligned on 8 byte boundaries, due to tagged representation of pointers.

    If a non-8-byte-aligned block is passed in, allot() will round up the

    size accordingly. Memory is allocated in a linear fashion, simply by

    incrementing the 'here' field of the 'active' ZONE struct.

    Note that allot() cannot be used in an arbitrary fashion, since doing so

    will confuse the garbage collector. See the section on object

    representation below.

    * Tagged pointer representation

    A ``tagged value'' is a CELL whose three least significant bits are a

    ``type tag''. The type tags are defined in types.h:

    #define FIXNUM_TYPE 0

    #define WORD_TYPE 1

    #define CONS_TYPE 2

    #define OBJECT_TYPE 3

    #define RATIO_TYPE 4

    #define COMPLEX_TYPE 5

    #define HEADER_TYPE 6

    #define GC_COLLECTED 7

    If the tag is OBJECT_TYPE and the remaining bits of the cell are zero --

    that is, if the tagged cell has integer value 3 -- it is taken to be the

    canonical falsity value, and also the empty list. There is a convinient

    macro:

    #define F RETAG(0,OBJECT_TYPE)

    If the tag is FIXNUM_TYPE, the most significant 29 bits of the cell are

    taken to be a literal integer value. To decode the integer value, the

    cell must be shifted to the right by three bits.

    The role of the header tag is described below.

    Any other tag signifies that the cell is a pointer to a 8-byte-aligned

    block of memory; the address of the block is obtained by masking off the

    least significant three bits of the tag.

    Some macros for working with tagged cells are provided:

    - TAG(cell) -- the tag of the cell

    - UNTAG(cell) -- mask off the tag, turning it into a pointer

    - RETAG(cell,tag) -- set the tag of a cell

    - untag_fixnum_fast(cell) -- shift the cell to the left by three bits,

    without actually checking that the tag is FIXNUM_TYPE. If it is not

    FIXNUM_TYPE, a meaningless value is returned.

    * Built-in data types

    In Factor, all data types are defined as part of the runtime. There are

    no user-defined types.

    For some cells, the type of the object they point to is encoded entirely

    in the tagged cell. This is true for the following types:

    #define FIXNUM_TYPE 0

    #define WORD_TYPE 1

    #define CONS_TYPE 2

    #define RATIO_TYPE 4

    #define COMPLEX_TYPE 5

    All other data types are pointed to by cells with a tag of OBJECT_TYPE,

    and the first cell of the object must then be a tagged cell with tag

    HEADER_TYPE, and the remaining bits must be one of the following values:

    #define T_TYPE 7

    #define ARRAY_TYPE 8

    #define BIGNUM_TYPE 9

    #define FLOAT_TYPE 10

    #define VECTOR_TYPE 11

    #define STRING_TYPE 12

    #define SBUF_TYPE 13

    #define PORT_TYPE 14

    #define DLL_TYPE 15

    #define ALIEN_TYPE 16

    There are three fundamental functions for working with types:

    - type_of(CELL tagged) -- return one of the above values. Never returns

    OBJECT_TYPE or HEADER_TYPE.

    - typep(CELL type, CELL tagged) -- return a boolean value. Behaves

    identically to: type_of(tagged) == type.

    - type_check(CELL type, CELL tagged) -- raise an error if the tagged

    cell does not point to an object of the given type.

    * Object representation

    Object representation details can be found in types.[ch].

    There is a fundamental principle guiding object representation in

    Factor: When given a tagged cell, one must be able to determine the size

    of the object it points to, and what other objects this object points

    to.

    There are two primary classes of objects:

    - Conslikes. The type of a conslike is encoded in the tag. Conslikes are

    represented 'naked' in the heap, with no header. These are exactly

    objects of type CONS_TYPE, RATIO_TYPE, and COMPLEX_TYPE. Note that

    WORD_TYPE also has its own tag, however words do have a header.

    Since conslikes lack a header, the garbage collector and relocator

    cannot distinglish between them while doing a linear scan of the heap.

    This has an important consequence: the fields of conslikes must all be

    tagged cells.

    - Large objects. So called because the have a header and are larger than

    conslikes. Unlike conslikes, an object with a header permits the garbage

    collector and relocator to behave accordingly. For example, because

    strings have a header, the relocator can skip over the characters of a

    string, instead of treating them as tagged cells and crashing.

    Tagged cells pointing to headed objects all have a tag OBJECT_TYPE,

    except for pointers to words which have a tag WORD_TYPE.

    * Conses and related types

    Conslikes are found in the files cons.[ch], ratio.[ch] and complex.[ch].

    Conslikes are one of the most important data types in Factor. They use

    exactly two words of storage in the heap. This may seem surprising --

    however, since all pointers to conslikes are tagged as being such, no

    ambiguity results.

    The most important is the CONS_TYPE.

    Given a tagged cell pointing to a CONS_TYPE, one can call

    untag_cons(CELL cell) to obtain a pointer to a F_CONS. F_CONS is a

    struct defined as:

    typedef struct {

    	CELL car;

    	CELL cdr;

    } F_CONS;

    Given an untagged pointer to an F_CONS, one can obtain a tagged cell by

    calling tag_cons(F_CONS* cons).

    There are corresponding taggers and untaggers for the other two

    conslikes:

    untag_ratio(), tag_ratio(), untag_complex(), tag_complex().

    * Image format

    Image loading and saving is performed by image.[ch] and relocate.[ch].

    On startup Factor loads an image file. The image file format depends on

    the CPU word size and byte order, since it is directly loaded into

    memory.

    The image begins with two constants that must exactly equal:

    - CELL magic -- 0x0f0e0d0c

    - CELL version -- 0

    The next value is used to relocate the image:

    - CELL relocation_base

    The following two are tagged pointers for user space:

    - CELL boot -- quotation to interpret on startup.

    - CELL global -- global namespace.

    The last value is the image size, for verification purposes:

    - CELL size.

    * Image relocation

    After the image has been loaded into the heap, a relocation procedure is

    performed. The idea behind relocation is as follows: in memory, the

    image contains absolute addresses to other parts of the image. However,

    it is desirable to be able to load the image into another offset of

    memory; depending on absolute memory mapping is unportable and

    troublesome.

    When saving the image, Factor stores the start address of the heap into

    the header field relocation_base.

    When loading the image, each address must be manipulated like so:

    void fixup(CELL* cell)

    {

    	if(TAG(*cell) != FIXNUM_TYPE && *cell != F)

    		*cell += (active.base - relocation_base);

    }

    Where 'active.base' is the heap start offset of the current instance,

    and 'relocation_base' is the value found in the image header.

    Relocation relies on total knowledge of object structure; it does this

    by inspecting type tags.

    Also the unportable 'xt' field of F_WORD structs is reset during

    relocation, by looking up the word's primitive number in a global table

    of primitives.

    * Garbage collection

    The garbage collector is defined in gc.c.

    Factor's garbage collector is a standard two-space copying collector,

    using Cheney's algorithm. Much has been said about this algorithm in the

    literature, and this information will not be duplicated here.

    Garbage collection is manually triggered by calling

    maybe_garbage_collection(). This function checks if free memory is below

    a certain threshold, and if so, commences a garbage collection.

    *Beware!* Any local variables in the C stack are not visible to the

    garbage collector, and are not taken as roots. Therefore, the only place

    it is safe to call maybe_garbage_collection() is from inside a primitive

    that was called directly from run(), before any values are stored in

    locals.

    For example, consider the following is a safe call to

    maybe_garbage_collection():

    void primitive_cons(void)

    {

    	CELL car, cdr;

    	maybe_garbage_collection();

    	cdr = dpop();

    	car = dpop();

    	dpush(cons(car,cdr));

    }

    The function primitive_cons() is only ever called from run() or

    primitive_execute(). In both these cases, the C stack does not store any

    heap-allocated values in local variables.

    However, the following would not be safe, and would result in a runtime

    crash sooner or later:

    void primitive_cons(void)

    {

    	CELL cdr = dpop();

    	CELL car = dpop();

    	maybe_garbage_collection();

    	dpush(cons(car,cdr));

    }

    The garbage collector would not update the car and cdr local variables

    to point to their new locations; so after it returned, the primitive

    might have allocated pushed a cons cell that refers to oldspace. A crash

    would follow soon after.

    * The stacks

    The stacks are defined in run.h.

    The runtime maintains exactly two stacks -- the data stack and the

    return stack. (The name stack and catch stack are purely library

    phenomena.) Both the data and return stacks are allocated using

    alloc_guarded(), so stack over/underflow checks are done in hardware

    with no runtime overhead.

    Both stacks hold tagged cells, and grow down -- that is, pushing

    increments the pointer.

    The data and return stacks are scoped by two global variables each:

    - CELL ds_bot/cs_bot -- a pointer to the bottom of the data/return

    stack; this is the first value you can write to, right above the guard

    page.

    - CELL ds/cs -- a pointer to the value at the top of the data/return

    stack.

    A set of inline functions are provided for pushing and popping the

    stacks:

    - dpop()/cpop() -- pop a value off the data/return stack.

    - dpush()/cpush() -- push a value on the data/return stack.

    - dpeek() -- return the top value on the data stack without popping.

    - drepl() -- replace the top of the stack with a given value.

    You can acess other values using the get() and set() inline functions.

    For example, to get the value on the data stack under the top value,

    without popping:

    get(ds - CELLS);

    * The inner interpreter

    The inner interpreter is defined in the run() function of run.c.

    The inner interpreter is a loop. It does not call itself recursively;

    rather, it pushes and pops the Factor return stack to maintain recursive

    state for interpreted definitions.

    The currently executing quotation is stored in the global variable 'cf'.

    This is a tagged cell that must point to a CONS_TYPE; otherwise a type

    error is raised. This quotation will be called the ``call frame''.

    If the end of the call frame quotation is reached -- that is, if it

    becomes identically equal to F -- the return stack is popped, and the

    popped value becomes the new call frame.

    Each step of the interpreter takes the car of the call frame, referred

    to as ``next'', and advances execution state by setting the call frame

    to its cdr.

    The type tag of next is inspected. If it is anything but WORD_TYPE, it

    is pushed on the stack using dpush(). Otherwise, the word is executed as

    described below.

    When a word is executed by the inner interpreter, first the global

    variable 'executing' is set to an untagged pointer to the F_WORD struct.

    Next, the interpreter calls the C function whose address is stored in

    the 'xt' field of the word using the EXECUTE macro:

    #define EXECUTE(w) ((XT)(w->xt))()

    An 'xt' is just a function that takes no arguments:

    typedef void (*XT)(void);

    As soon as the function returns, the inner interpreter loop continues

    iterating down the call frame, pushing literals, and executing words,

    then finally it reaches the end of the call frame, pops the return

    stack, and the whole cycle repeats again.

    The run() function never returns. The only way to exit the inner

    interpreter is by calling the exit* primitive, defined in the function

    primitive_exit() in misc.c

    * Primitives

    Primitives are exported to user space via numbers -- each F_WORD struct

    has a 'primitive' field. During relocation, the 'xt' field of the F_WORD

    is set to the corresponding C function pointer by looking up the

    primitive number in a table.

    Six fundamental primitives are:

    - #0: undefined() -- undefined words have this primitive/XT. It simply

    raises an error.

    - #1: docol() -- compound definitions have this primitive/XT. Recall

    that the inner interpreter sets the 'executing' global variable to the

    word object before calling its XT. The docol() function accesses the

    quotation stored in the 'parameter' field of the executing word, and

    calls it. What exactly is meant by 'calls' is described below.

    - #2: dosym() -- symbol definitions have this primitive/XT. It simply

    pushes the executing word on the data stack, thus making it behave like

    a literal.

    - #3: primitive_execute() -- defined in user space as 'execute' in the

    'words' vocabulary. Pops a word off the datastack, stores it in the

    'executing' global variable, and calls its XT.

    - #4: primitive_call() -- defined in user space as 'call' in the

    'kernel' vocabulary. Pops a cons cell off the datastack, and calls it.

    What exactly is meant by 'calls' is described below.

    - #5: primitive_ifte() -- defined in user space as 'ifte' in the

    'kernel' vocabulary. Executes one of two quotations on the stack,

    depending on a boolean value stored below.

    A 'boolean value' is of course 'false' if it is identically equal to F,

    and 'true' otherwise.

    * Quotations

    Notice that docol(), primitive_call() and primitive_ifte() all take a

    quotation from some source, and 'call' it. They do this using the inline

    function call():

    INLINE void call(CELL quot)

    {

    	/* tail call optimization */

    	if(callframe != F)

    	{

    		cpush(tag_word(executing));

    		cpush(callframe);

    	}

    	callframe = quot;

    }

    Indeed, this function does not actually call the quotation itself. It

    merely changes inner interpreter state in such a way that the next

    iteration of the interpreter loop will begin executing this quotation;

    then when it is done, the previous quotation is popped off the return

    stack.

    Two final points should be said about call(). It also pushes the

    currently executing word for the profiler's sake; the inner interpreter

    itself does not use the word that was pushed on the return stack.

    Finally, call() performs tail call optimization. If the current call

    frame is F -- in other words, if the occurrence of docol(),

    primitive_call() or primitive_ifte() was the last in a quotation -- the

    call frame is not pushed on the return stack, since there is nothing to

    return to. If F was pushed on the return stack, it would simply be

    popped again at a later time.

    * User environment

    At startup, the last thing done by the C code is setting the call frame

    to point to the boot quotation (as defined in the image header). Then,

    it calls run() and execution of the boot quotation begins.

    User space makes use of a 'user environment' to store state that does

    not belong on the data stack. The user environment is roughly like

    global variables, however their number is fixed.

    The user environment consists of 16 numbered slots, each slot holding

    one tagged cell. User environment slots are accessed using the getenv (

    slot -- value ) and setenv ( value slot -- ) primitives. The slots have

    the following assignment:

    #define STDIN_ENV      0

    #define STDOUT_ENV     1

    #define STDERR_ENV     2

    #define NAMESTACK_ENV  3

    #define GLOBAL_ENV     4

    #define BREAK_ENV      5

    #define CATCHSTACK_ENV 6

    #define CPU_ENV        7

    #define BOOT_ENV       8

    #define RUNQUEUE_ENV   9

    #define ARGS_ENV       10

    #define OS_ENV         11

    #define RESERVED_ENV_1 12

    #define RESERVED_ENV_2 13

    #define RESERVED_ENV_3 14

    #define RESERVED_ENV_4 15

    STDIN_ENV and STDOUT_ENV are set by the I/O code to point to F_PORTs for

    the appropriate system streams. STDERR_ENV is unused.

    NAMESTACK_ENV is not used by the runtime; it is for user space use only.

    GLOBAL_ENV is set by the runtime on startup to the same value as the

    'global' field of the image header. User space makes use of

    NAMESTACK_ENV and GLOBAL_ENV to implement named variables and nested

    namespaces. Both values are initialized in 'init-namespaces' of the

    'namespaces' vocabulary.

    BREAK_ENV is a quotation, set by user space. This quotation is called

    when the runtime raises an error. CATCHSTACK_ENV is not set or read by

    the runtime, it is for user space use only. Both are initialized in

    'init-errors' of the 'errors' vocabulary.

    CPU_ENV is set by the runtime to one of the two strings "x86" or

    "unknown". It is not intended to be written. The 'cpu' word of the

    'kernel' vocabulary is defined for reading it.

    BOOT_ENV is set by the runtime to the same value as the 'boot' field of

    the image header -- that is, the boot quotation. If it is set to a

    different value and then an image is saved, the new image will have this

    boot quotation. This can be used to make 'turnkey' images that start a

    custom app, instead of the listener loop.

    RUNQUEUE_ENV is used exclusively by user space, for threading. See the

    'threads' vocabulary.

    ARGS_ENV is set by the runtime to a linked list of strings,

    corresponding to command line arguments given to the Factor runtime

    executable. The first of these arguments will always be an image name.

    OS_ENV is set by the runtime to one of the two strings "unix" or

    "win32". It is not intended to be written. The 'os' word of the 'kernel'

    vocabulary is defined for reading it.

    The remaining four user environment slots must not be read or written by

    user space code.

    * Error handling

    Error handling goes on inside the error.c file, as well as run.c.

    When the inner interpreter loop begins, setjmp is called to save the

    current C stack in the global variable 'toplevel'.

    When an error is raised inside the runtime, one of two things happen:

    - BREAK_ENV is not yet set, so the interpreter prints an error message

    and immediately exits. This is the case during bootstrapping.

    - BREAK_ENV is set, in which case the error is stored in the

    'thrown_error' global variable, and the error handler long-jumps to the

    top level. Execution then resumes at the inner interpreter loop, which

    then checks if there was a thrown error, and if so, it pushes the error

    on the data stack, and calls the quotation stored in BREAK_ENV.

    User space takes over from here. The BREAK_ENV is defined as follows in

    the 'init-error-handler' word of debugger.factor:

    [ dup save-error rethrow ] 5 setenv

    The 'save-error' word snapshots the current stacks -- this is how :s,

    :r, :n and :c work. 'rethrow' then pops a continuation from the catch

    stack and calls it, which results in a certain 'catch' block being

    executed.

## carsten_eckelmann — 2004-12-16 10:57:12

    Hmmm, very nice, but as a newbie to concatenative languages and a

    not-so-hot C programmer I don't get as much satisfaction out of this

    as out of the Factor Developers Handbook.

    From what I've seen so far, I really like Factor and I will stay tuned

    to all the nice things that will hopefully happen to it in the future.

    But in the mean-time I am trying to read up on this very special

    universe that you are all so happily familiar with.

    So my reading schedule is as follows:

    To get into Forth, the father of concatenative languages:

    1. Thinking Forth, Leo Brodie

    2. Starting Forth, Leo Brodie

    But I don't really want to get into Forth, I want to get into Factor! So..

    To get into Lisp/Scheme:

    1. The little Schemer, Daniel P. Friedman and Matthias

    Felleisen

    2. On Lisp, Paul Graham

    But I don't really want to get into Lisp/Scheme, I want to get into

    Factor! So..

    To get into Joy I will have to find my way through the maze that is

    the Joy website.

    And maybe at that point I will be in a state of mind, where I can dig

    into Factor and make the most of it.

    Any suggestions to this curriculum?

    Some day, I hope there will be "Thinking in Factor", so people can

    take some shortcuts.

    Cheers,

    Carsten.

## phimvt@lurac.latrobe.edu.au — 2004-12-17 04:37:09

    Well done, Slava.

    I have always felt that I should write something like this

    for the Joy implementation, to help anybody who is game

    enough to work on the innards. One day, perhaps ...

    I am watching your progress with interest.

      - Manfred

    Manfred von Thun

    Philosophy Department, La Trobe University

     http://www.latrobe.edu.au/philosophy/phimvt/s00bok.html

      ( SYMBOLIC PROCESSING IN PASCAL - many programs at different levels )

     http://www.latrobe.edu.au/philosophy/phimvt/joy.html

      ( JOY - a programming language based on function composition )

     On Wed, 15 Dec 2004, Slava Pestov wrote:

    >

    > Hi everybody,

    >

    > I have written up a brief document explaining the inner workings of the

    > Factor runtime written in C.

    >

    > I hope it sheds some light onto the workings of Factor. While you don't

    > have to read it to be able to program in Factor, reading it will give a

    > better understanding of what's actually going on.

    >

    > ------->8--------

    >

    > FACTOR INTERNALS GUIDE

    >

    > This guide focuses on portion of Factor that is written in C. The

    > sources can be found in the native/ subdirectory.

    >

    > Factor defines a few new integer types; they will be mentioned without

    > further explanation:

    >

    > - CELL: unsigned word-size field.

    > - FIXNUM: signed word-size field.

    >

    > The 'CELLS' constant is defined as sizeof(CELL). The idea is to be able

    > to write expressions like 4*CELLS.

    >

    > * The memory manager

    >

    > Factor's memory manager is concentrated in the files memory.c and gc.c.

    >

    > A guard page is allocated above the memory heap, and an out of memory

    > condition is raised if an attempt is made to write to the guard page.

    > Out of memory errors are fatal -- the garbage collector must be

    > triggered before this happends.

    >

    > The alloc_guarded(CELL size) function allocates a block of memory with

    > guard pages above and below.

    >

    > There are two memory zones of identical size; only one is in use at any

    > one time -- this is denoted as the 'active' zone. The other is the

    > 'prior' zone. Each zone is identified with a ZONE struct stored in a

    > global variable named after the zone's role.

    >

    > Memory is allocated in the zone using the allot(CELL a) function. This

    > function takes the size of a memory block to allocate. Memory blocks are

    > aligned on 8 byte boundaries, due to tagged representation of pointers.

    > If a non-8-byte-aligned block is passed in, allot() will round up the

    > size accordingly. Memory is allocated in a linear fashion, simply by

    > incrementing the 'here' field of the 'active' ZONE struct.

    >

    > Note that allot() cannot be used in an arbitrary fashion, since doing so

    > will confuse the garbage collector. See the section on object

    > representation below.

    >

    > * Tagged pointer representation

    >

    > A ``tagged value'' is a CELL whose three least significant bits are a

    > ``type tag''. The type tags are defined in types.h:

    >

    > #define FIXNUM_TYPE 0

    > #define WORD_TYPE 1

    > #define CONS_TYPE 2

    > #define OBJECT_TYPE 3

    > #define RATIO_TYPE 4

    > #define COMPLEX_TYPE 5

    > #define HEADER_TYPE 6

    > #define GC_COLLECTED 7

    >

    > If the tag is OBJECT_TYPE and the remaining bits of the cell are zero --

    > that is, if the tagged cell has integer value 3 -- it is taken to be the

    > canonical falsity value, and also the empty list. There is a convinient

    > macro:

    >

    > #define F RETAG(0,OBJECT_TYPE)

    >

    > If the tag is FIXNUM_TYPE, the most significant 29 bits of the cell are

    > taken to be a literal integer value. To decode the integer value, the

    > cell must be shifted to the right by three bits.

    >

    > The role of the header tag is described below.

    >

    > Any other tag signifies that the cell is a pointer to a 8-byte-aligned

    > block of memory; the address of the block is obtained by masking off the

    > least significant three bits of the tag.

    >

    > Some macros for working with tagged cells are provided:

    >

    > - TAG(cell) -- the tag of the cell

    >

    > - UNTAG(cell) -- mask off the tag, turning it into a pointer

    >

    > - RETAG(cell,tag) -- set the tag of a cell

    >

    > - untag_fixnum_fast(cell) -- shift the cell to the left by three bits,

    > without actually checking that the tag is FIXNUM_TYPE. If it is not

    > FIXNUM_TYPE, a meaningless value is returned.

    >

    > * Built-in data types

    >

    > In Factor, all data types are defined as part of the runtime. There are

    > no user-defined types.

    >

    > For some cells, the type of the object they point to is encoded entirely

    > in the tagged cell. This is true for the following types:

    >

    > #define FIXNUM_TYPE 0

    > #define WORD_TYPE 1

    > #define CONS_TYPE 2

    > #define RATIO_TYPE 4

    > #define COMPLEX_TYPE 5

    >

    > All other data types are pointed to by cells with a tag of OBJECT_TYPE,

    > and the first cell of the object must then be a tagged cell with tag

    > HEADER_TYPE, and the remaining bits must be one of the following values:

    >

    > #define T_TYPE 7

    > #define ARRAY_TYPE 8

    > #define BIGNUM_TYPE 9

    > #define FLOAT_TYPE 10

    > #define VECTOR_TYPE 11

    > #define STRING_TYPE 12

    > #define SBUF_TYPE 13

    > #define PORT_TYPE 14

    > #define DLL_TYPE 15

    > #define ALIEN_TYPE 16

    >

    > There are three fundamental functions for working with types:

    >

    > - type_of(CELL tagged) -- return one of the above values. Never returns

    > OBJECT_TYPE or HEADER_TYPE.

    >

    > - typep(CELL type, CELL tagged) -- return a boolean value. Behaves

    > identically to: type_of(tagged) == type.

    >

    > - type_check(CELL type, CELL tagged) -- raise an error if the tagged

    > cell does not point to an object of the given type.

    >

    > * Object representation

    >

    > Object representation details can be found in types.[ch].

    >

    > There is a fundamental principle guiding object representation in

    > Factor: When given a tagged cell, one must be able to determine the size

    > of the object it points to, and what other objects this object points

    > to.

    >

    > There are two primary classes of objects:

    >

    > - Conslikes. The type of a conslike is encoded in the tag. Conslikes are

    > represented 'naked' in the heap, with no header. These are exactly

    > objects of type CONS_TYPE, RATIO_TYPE, and COMPLEX_TYPE. Note that

    > WORD_TYPE also has its own tag, however words do have a header.

    >

    > Since conslikes lack a header, the garbage collector and relocator

    > cannot distinglish between them while doing a linear scan of the heap.

    > This has an important consequence: the fields of conslikes must all be

    > tagged cells.

    >

    > - Large objects. So called because the have a header and are larger than

    > conslikes. Unlike conslikes, an object with a header permits the garbage

    > collector and relocator to behave accordingly. For example, because

    > strings have a header, the relocator can skip over the characters of a

    > string, instead of treating them as tagged cells and crashing.

    >

    > Tagged cells pointing to headed objects all have a tag OBJECT_TYPE,

    > except for pointers to words which have a tag WORD_TYPE.

    >

    > * Conses and related types

    >

    > Conslikes are found in the files cons.[ch], ratio.[ch] and complex.[ch].

    >

    > Conslikes are one of the most important data types in Factor. They use

    > exactly two words of storage in the heap. This may seem surprising --

    > however, since all pointers to conslikes are tagged as being such, no

    > ambiguity results.

    >

    > The most important is the CONS_TYPE.

    >

    > Given a tagged cell pointing to a CONS_TYPE, one can call

    > untag_cons(CELL cell) to obtain a pointer to a F_CONS. F_CONS is a

    > struct defined as:

    >

    > typedef struct {

    > 	CELL car;

    > 	CELL cdr;

    > } F_CONS;

    >

    > Given an untagged pointer to an F_CONS, one can obtain a tagged cell by

    > calling tag_cons(F_CONS* cons).

    >

    > There are corresponding taggers and untaggers for the other two

    > conslikes:

    >

    > untag_ratio(), tag_ratio(), untag_complex(), tag_complex().

    >

    > * Image format

    >

    > Image loading and saving is performed by image.[ch] and relocate.[ch].

    >

    > On startup Factor loads an image file. The image file format depends on

    > the CPU word size and byte order, since it is directly loaded into

    > memory.

    >

    > The image begins with two constants that must exactly equal:

    >

    > - CELL magic -- 0x0f0e0d0c

    > - CELL version -- 0

    >

    > The next value is used to relocate the image:

    >

    > - CELL relocation_base

    >

    > The following two are tagged pointers for user space:

    >

    > - CELL boot -- quotation to interpret on startup.

    > - CELL global -- global namespace.

    >

    > The last value is the image size, for verification purposes:

    >

    > - CELL size.

    >

    > * Image relocation

    >

    > After the image has been loaded into the heap, a relocation procedure is

    > performed. The idea behind relocation is as follows: in memory, the

    > image contains absolute addresses to other parts of the image. However,

    > it is desirable to be able to load the image into another offset of

    > memory; depending on absolute memory mapping is unportable and

    > troublesome.

    >

    > When saving the image, Factor stores the start address of the heap into

    > the header field relocation_base.

    >

    > When loading the image, each address must be manipulated like so:

    >

    > void fixup(CELL* cell)

    > {

    > 	if(TAG(*cell) != FIXNUM_TYPE && *cell != F)

    > 		*cell += (active.base - relocation_base);

    > }

    >

    > Where 'active.base' is the heap start offset of the current instance,

    > and 'relocation_base' is the value found in the image header.

    >

    > Relocation relies on total knowledge of object structure; it does this

    > by inspecting type tags.

    >

    > Also the unportable 'xt' field of F_WORD structs is reset during

    > relocation, by looking up the word's primitive number in a global table

    > of primitives.

    >

    > * Garbage collection

    >

    > The garbage collector is defined in gc.c.

    >

    > Factor's garbage collector is a standard two-space copying collector,

    > using Cheney's algorithm. Much has been said about this algorithm in the

    > literature, and this information will not be duplicated here.

    >

    > Garbage collection is manually triggered by calling

    > maybe_garbage_collection(). This function checks if free memory is below

    > a certain threshold, and if so, commences a garbage collection.

    >

    > *Beware!* Any local variables in the C stack are not visible to the

    > garbage collector, and are not taken as roots. Therefore, the only place

    > it is safe to call maybe_garbage_collection() is from inside a primitive

    > that was called directly from run(), before any values are stored in

    > locals.

    >

    > For example, consider the following is a safe call to

    > maybe_garbage_collection():

    >

    > void primitive_cons(void)

    > {

    > 	CELL car, cdr;

    > 	maybe_garbage_collection();

    > 	cdr = dpop();

    > 	car = dpop();

    > 	dpush(cons(car,cdr));

    > }

    >

    > The function primitive_cons() is only ever called from run() or

    > primitive_execute(). In both these cases, the C stack does not store any

    > heap-allocated values in local variables.

    >

    > However, the following would not be safe, and would result in a runtime

    > crash sooner or later:

    >

    > void primitive_cons(void)

    > {

    > 	CELL cdr = dpop();

    > 	CELL car = dpop();

    > 	maybe_garbage_collection();

    > 	dpush(cons(car,cdr));

    > }

    >

    > The garbage collector would not update the car and cdr local variables

    > to point to their new locations; so after it returned, the primitive

    > might have allocated pushed a cons cell that refers to oldspace. A crash

    > would follow soon after.

    >

    > * The stacks

    >

    > The stacks are defined in run.h.

    >

    > The runtime maintains exactly two stacks -- the data stack and the

    > return stack. (The name stack and catch stack are purely library

    > phenomena.) Both the data and return stacks are allocated using

    > alloc_guarded(), so stack over/underflow checks are done in hardware

    > with no runtime overhead.

    >

    > Both stacks hold tagged cells, and grow down -- that is, pushing

    > increments the pointer.

    >

    > The data and return stacks are scoped by two global variables each:

    >

    > - CELL ds_bot/cs_bot -- a pointer to the bottom of the data/return

    > stack; this is the first value you can write to, right above the guard

    > page.

    >

    > - CELL ds/cs -- a pointer to the value at the top of the data/return

    > stack.

    >

    > A set of inline functions are provided for pushing and popping the

    > stacks:

    >

    > - dpop()/cpop() -- pop a value off the data/return stack.

    >

    > - dpush()/cpush() -- push a value on the data/return stack.

    >

    > - dpeek() -- return the top value on the data stack without popping.

    >

    > - drepl() -- replace the top of the stack with a given value.

    >

    > You can acess other values using the get() and set() inline functions.

    > For example, to get the value on the data stack under the top value,

    > without popping:

    >

    > get(ds - CELLS);

    >

    > * The inner interpreter

    >

    > The inner interpreter is defined in the run() function of run.c.

    >

    > The inner interpreter is a loop. It does not call itself recursively;

    > rather, it pushes and pops the Factor return stack to maintain recursive

    > state for interpreted definitions.

    >

    > The currently executing quotation is stored in the global variable 'cf'.

    > This is a tagged cell that must point to a CONS_TYPE; otherwise a type

    > error is raised. This quotation will be called the ``call frame''.

    >

    > If the end of the call frame quotation is reached -- that is, if it

    > becomes identically equal to F -- the return stack is popped, and the

    > popped value becomes the new call frame.

    >

    > Each step of the interpreter takes the car of the call frame, referred

    > to as ``next'', and advances execution state by setting the call frame

    > to its cdr.

    >

    > The type tag of next is inspected. If it is anything but WORD_TYPE, it

    > is pushed on the stack using dpush(). Otherwise, the word is executed as

    > described below.

    >

    > When a word is executed by the inner interpreter, first the global

    > variable 'executing' is set to an untagged pointer to the F_WORD struct.

    >

    > Next, the interpreter calls the C function whose address is stored in

    > the 'xt' field of the word using the EXECUTE macro:

    >

    > #define EXECUTE(w) ((XT)(w->xt))()

    >

    > An 'xt' is just a function that takes no arguments:

    >

    > typedef void (*XT)(void);

    >

    > As soon as the function returns, the inner interpreter loop continues

    > iterating down the call frame, pushing literals, and executing words,

    > then finally it reaches the end of the call frame, pops the return

    > stack, and the whole cycle repeats again.

    >

    > The run() function never returns. The only way to exit the inner

    > interpreter is by calling the exit* primitive, defined in the function

    > primitive_exit() in misc.c

    >

    > * Primitives

    >

    > Primitives are exported to user space via numbers -- each F_WORD struct

    > has a 'primitive' field. During relocation, the 'xt' field of the F_WORD

    > is set to the corresponding C function pointer by looking up the

    > primitive number in a table.

    >

    > Six fundamental primitives are:

    >

    > - #0: undefined() -- undefined words have this primitive/XT. It simply

    > raises an error.

    >

    > - #1: docol() -- compound definitions have this primitive/XT. Recall

    > that the inner interpreter sets the 'executing' global variable to the

    > word object before calling its XT. The docol() function accesses the

    > quotation stored in the 'parameter' field of the executing word, and

    > calls it. What exactly is meant by 'calls' is described below.

    >

    > - #2: dosym() -- symbol definitions have this primitive/XT. It simply

    > pushes the executing word on the data stack, thus making it behave like

    > a literal.

    >

    > - #3: primitive_execute() -- defined in user space as 'execute' in the

    > 'words' vocabulary. Pops a word off the datastack, stores it in the

    > 'executing' global variable, and calls its XT.

    >

    > - #4: primitive_call() -- defined in user space as 'call' in the

    > 'kernel' vocabulary. Pops a cons cell off the datastack, and calls it.

    > What exactly is meant by 'calls' is described below.

    >

    > - #5: primitive_ifte() -- defined in user space as 'ifte' in the

    > 'kernel' vocabulary. Executes one of two quotations on the stack,

    > depending on a boolean value stored below.

    >

    > A 'boolean value' is of course 'false' if it is identically equal to F,

    > and 'true' otherwise.

    > * Quotations

    >

    > Notice that docol(), primitive_call() and primitive_ifte() all take a

    > quotation from some source, and 'call' it. They do this using the inline

    > function call():

    >

    > INLINE void call(CELL quot)

    > {

    > 	/* tail call optimization */

    > 	if(callframe != F)

    > 	{

    > 		cpush(tag_word(executing));

    > 		cpush(callframe);

    > 	}

    > 	callframe = quot;

    > }

    >

    > Indeed, this function does not actually call the quotation itself. It

    > merely changes inner interpreter state in such a way that the next

    > iteration of the interpreter loop will begin executing this quotation;

    > then when it is done, the previous quotation is popped off the return

    > stack.

    >

    > Two final points should be said about call(). It also pushes the

    > currently executing word for the profiler's sake; the inner interpreter

    > itself does not use the word that was pushed on the return stack.

    >

    > Finally, call() performs tail call optimization. If the current call

    > frame is F -- in other words, if the occurrence of docol(),

    > primitive_call() or primitive_ifte() was the last in a quotation -- the

    > call frame is not pushed on the return stack, since there is nothing to

    > return to. If F was pushed on the return stack, it would simply be

    > popped again at a later time.

    >

    > * User environment

    >

    > At startup, the last thing done by the C code is setting the call frame

    > to point to the boot quotation (as defined in the image header). Then,

    > it calls run() and execution of the boot quotation begins.

    >

    > User space makes use of a 'user environment' to store state that does

    > not belong on the data stack. The user environment is roughly like

    > global variables, however their number is fixed.

    >

    > The user environment consists of 16 numbered slots, each slot holding

    > one tagged cell. User environment slots are accessed using the getenv (

    > slot -- value ) and setenv ( value slot -- ) primitives. The slots have

    > the following assignment:

    >

    > #define STDIN_ENV      0

    > #define STDOUT_ENV     1

    > #define STDERR_ENV     2

    > #define NAMESTACK_ENV  3

    > #define GLOBAL_ENV     4

    > #define BREAK_ENV      5

    > #define CATCHSTACK_ENV 6

    > #define CPU_ENV        7

    > #define BOOT_ENV       8

    > #define RUNQUEUE_ENV   9

    > #define ARGS_ENV       10

    > #define OS_ENV         11

    > #define RESERVED_ENV_1 12

    > #define RESERVED_ENV_2 13

    > #define RESERVED_ENV_3 14

    > #define RESERVED_ENV_4 15

    >

    > STDIN_ENV and STDOUT_ENV are set by the I/O code to point to F_PORTs for

    > the appropriate system streams. STDERR_ENV is unused.

    >

    > NAMESTACK_ENV is not used by the runtime; it is for user space use only.

    > GLOBAL_ENV is set by the runtime on startup to the same value as the

    > 'global' field of the image header. User space makes use of

    > NAMESTACK_ENV and GLOBAL_ENV to implement named variables and nested

    > namespaces. Both values are initialized in 'init-namespaces' of the

    > 'namespaces' vocabulary.

    >

    > BREAK_ENV is a quotation, set by user space. This quotation is called

    > when the runtime raises an error. CATCHSTACK_ENV is not set or read by

    > the runtime, it is for user space use only. Both are initialized in

    > 'init-errors' of the 'errors' vocabulary.

    >

    > CPU_ENV is set by the runtime to one of the two strings "x86" or

    > "unknown". It is not intended to be written. The 'cpu' word of the

    > 'kernel' vocabulary is defined for reading it.

    >

    > BOOT_ENV is set by the runtime to the same value as the 'boot' field of

    > the image header -- that is, the boot quotation. If it is set to a

    > different value and then an image is saved, the new image will have this

    > boot quotation. This can be used to make 'turnkey' images that start a

    > custom app, instead of the listener loop.

    >

    > RUNQUEUE_ENV is used exclusively by user space, for threading. See the

    > 'threads' vocabulary.

    >

    > ARGS_ENV is set by the runtime to a linked list of strings,

    > corresponding to command line arguments given to the Factor runtime

    > executable. The first of these arguments will always be an image name.

    >

    > OS_ENV is set by the runtime to one of the two strings "unix" or

    > "win32". It is not intended to be written. The 'os' word of the 'kernel'

    > vocabulary is defined for reading it.

    >

    > The remaining four user environment slots must not be read or written by

    > user space code.

    >

    > * Error handling

    >

    > Error handling goes on inside the error.c file, as well as run.c.

    >

    > When the inner interpreter loop begins, setjmp is called to save the

    > current C stack in the global variable 'toplevel'.

    >

    > When an error is raised inside the runtime, one of two things happen:

    >

    > - BREAK_ENV is not yet set, so the interpreter prints an error message

    > and immediately exits. This is the case during bootstrapping.

    >

    > - BREAK_ENV is set, in which case the error is stored in the

    > 'thrown_error' global variable, and the error handler long-jumps to the

    > top level. Execution then resumes at the inner interpreter loop, which

    > then checks if there was a thrown error, and if so, it pushes the error

    > on the data stack, and calls the quotation stored in BREAK_ENV.

    >

    > User space takes over from here. The BREAK_ENV is defined as follows in

    > the 'init-error-handler' word of debugger.factor:

    >

    > [ dup save-error rethrow ] 5 setenv

    >

    > The 'save-error' word snapshots the current stacks -- this is how :s,

    > :r, :n and :c work. 'rethrow' then pops a continuation from the catch

    > stack and calls it, which results in a certain 'catch' block being

    > executed.

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

    >