Added patch by Siddharth Heroor

[Klink.git] / README.org

* README
** Headers
*** Purpose

Top-level user documentation for Klink, the Kernel interpreter

*** History

Begun Tue Nov  2 17:50:37 2010

Right now this documentation is in a very tenous state.  Don't expect
too much.

*** Associated files

None

** What it is

Klink is an interpreter for the Kernel programming language.  It was
adapted from Tinyscheme.

Now (12 Mar 2011) Klink basically runs.  The major missing
features are get-module and neat printing - it prints stuff that it
can't yet read back.

** Where to get it

http://repo.or.cz/w/Klink.git

** Installing it

You need:
 * A C compiler
   * GNU gcc 4.3.2 works
 * Make
   * GNU make 3.81 works
 * The Boehm garbage collector library, [[http://www.hpl.hp.com/personal/Hans_Boehm/gc/][here]]
   * Alternatively, I'm told that [[http://tinygc.sourceforge.net/][Tinygc]] is API compatible and
     smaller, but I haven't tested it myself.

Before you start:
 * Edit the makefile by hand for your system.

Run:
 * make

Don't run:

 * ./configure, there isn't any.
 * make install, there isn't any

It will have built:
 * klink
 * libklink.a
   * Same comments.
 * libklink.so
   * Same comments.

*** Configuration

None at this point.

** Running it

The file "klink" is an executable, call it as
 : ./klink

** Extensions

 * Combiners
   * get-module-from-port
     * Like get-module, but takes a port
   * listtype
     * For now, used only with type?
   * destructure-list
     * For now, used only with do-destructure
   * list-neighbors-linear
   * get-char
     * Kernel does not yet define operations on ports
   * compare-neighbors
   * for-each-while-true (Not yet)
   * every?
     * For now it's only provided as every?/2-xary
   * some?
     * (Not provided yet)
 * Printing
   * Objects known to the ground environment are printed as #,known-symbol
   * Some constructed or accessed objects are printed as ,(ctor args).
     * For now, this is only done for `unwrap'.

** Hacking
*** General action of Klink

Klink's main loop is _klink_cycle.  That repeatedly pops the dynmaic
stack and evaluates what it popped, until the stack is empty.
Evaluation mostly consists of calling C functions that are boxed as
Kernel objects.

There are 3 ways that C functions deal with scheduling for
_klink_cycle:
 * The simplest way is to do nothing special.  Your C function just
   computes a value and returns it, and *does*not* call any C function
   that will schedule future operations for _klink_cycle, *unless*
   it's the last thing it does.  If your function calls such a C
   function any other time, things that appear (in C) to be done after
   the call returns will in fact be done sometime in the middle of the
   (Kernel) call.  Even if you could make that work, it's messy and
   introduces dependencies.  It's not intended to work.

 * Another way is to arrange for _klink_cycle to call one or more
   Kernel functions in the future, and then return the value that the
   first of them should be called with.  Arranging to call is done by
   means of the CONTIN_* macros.

 * The third way is to call invoke_continuation, which jumps back to
   _klink_cycle, erasing any intervening C calls, and arranges to
   continue Kernel execution from that continuation.  It's basically
   for raising errors.


*** The types of built-in operatives

 * T_CFUNC :: A C function plus data how to turn the value that Kernel
              passes into the arguments the C function accepts.
 * T_CURRIED :: A curried combiner.  It consists of another combiner,
                a value, and a decurrier that converts that value plus
                the value that Kernel passes into the value to call
                the combiner with.
 * T_TYPE :: A trivial predicate to check a T_ type.  Not exposed in
             `ground' but exposed in `simple', which should not be
             directly used.
 * T_TYPECHECK :: (Not yet) A predicate that checks a list for
                  being the right type, element by element.
 * T_DESTRUCTURE :: (Not yet) Like T_TYPECHECK, but in addition to
                  checking the list, it (will) create a vector of its
                  elements.  It is currently used to destructure
                  argobjects for T_CFUNC calls.

*** How to define C functions                                       :hackdoc:

C functions that the interpreter can be made aware of are defined by
the macro family KERNEL_DEFUN_*.  See [[id:d072eec0-4a2c-4c2f-8e57-971010dc54ff][Naming conventions for function
types]].  Use one of these in place of the C declaration.  Eg, instead
of:

 : pointer foo(klink *sc, pointer a, pointer b)
 : { stuff; }

write:

 : KERNEL_DEFUN(ps00a2,"foo",foo)
 : { 
 :   pointer a = arg1; 
 :   pointer b = arg2; 
 :   stuff;
 : }

Note that for some variants the arguments have special names (Again
see [[id:d072eec0-4a2c-4c2f-8e57-971010dc54ff][Naming conventions for function types]])

Their signatures can be forward declared in two ways:
 * To forward declare the C function, use a KERNEL_FUNCSIG_* macro, eg
   : KERNEL_FUNCSIG_ps00a2(foo);
 * To forward declare the data that allows Kernel to know about the
   function, use the KERNEL_FFDATA_DECL macro, eg:
   : KERNEL_FFDATA_DECL(foo);

If the C function will be anonymous in Kernel (ie it's only used by
other C functions, never by Kernel code) the first argument to
KERNEL_DEFUN_* can be 0.

*** Naming conventions for function types                           :hackdoc:
    :PROPERTIES:
    :ID:       d072eec0-4a2c-4c2f-8e57-971010dc54ff
    :END:

Each member of a macro family is distinguished by a suffix which
encodes the function type's argument types and return value.  The
suffix is composed of letters.  

 * There should be one letter from each group in the chart below.  Use
   0 as a placeholder where some group is not given.
 * Letters are used in the same order that groups are given in.
 * Corresponding arguments are passed to the function in the same
   order that groups are given in.
 * Please keep them in alphabetical order in fftype and in the macro
   definitions in "klink.h".



| Letter  | arg name  | What the argument or return type is          |
|---------+-----------+----------------------------------------------|
| P       | N/A       | returns a pointer                            |
| B       | N/A       | returns a boolean as an int                  |
|---------+-----------+----------------------------------------------|
| S       | sc        | the interpreter                              |
|---------+-----------+----------------------------------------------|
| E       | env       | the current environment                      |
|---------+-----------+----------------------------------------------|
| AN      | args      | The remaining Kernel arguments as one object |
| A1      | arg1      | the car of the Kernel argument list          |
| A2      | arg1,arg2 | the car and cadr of the Kernel argument list |
| A3, etc | similar   | similar for 3 (etc) Kernel arguments         |
|---------+-----------+----------------------------------------------|

Only functions with E will make pure operatives, others will make
applicatives.

I suggest that when using A1, A2 etc, the programmer begin by renaming
the arguments, like:
     
 : pointer proc = arg1;
 : pointer form = arg2;
*** How to define C function types                                  :hackdoc:
 * Figure out the right suffix.  That suffix will be used to identify
   a family of typedefs, macros, fields and enums. Use the naming
   conventions in [[id:d072eec0-4a2c-4c2f-8e57-971010dc54ff][Naming conventions for function types]].  

   Let's pretend it's "Your_Suffix"

 * In "fftypes.inc", 
   * Add FFTYPE(Your_Suffix,N) where N is the number of normal
     arguments the function type takes, or 0 for unchecked.  It will
     be the same as the number after "a", or 0 for "an".
 * In "klink.h", 
   * Write a new KERNEL_FUN_SIG_Your_Suffix macro It should take 1
     argument and build a function signature with that name.

     See the existing cases.
   * There were other steps that used to be needed, but they no longer
     need manual action.
 * In "klink.c"
   * Add a case in a handler for it:
     * Normally, add a case in kernel_call for
       kernel_enum_f_Your_Suffix

   * If the function takes env (has E in the name), alter
     ff_wrap_p to return 0 for that type.
   * There were other steps but they no longer need manual action.
 * You're done!

*** About calling patterns
**** Obsolete

Calling patterns were a sort of poor-man's currying.  When I added
support for real currying (under the hood for C, that is), it became
unneccessary.  

*** About T_CURRIED and decurriers

**** Why

Because very early in development, I noticed that this often happened:
What I wanted to do would be *almost* supported by an existing C
function.  But the argument list wasn't quite in order.  For instance,
I'd want to cons the returned value onto the car of the stored
argument.

At first I wrote little functions to rearrange the arguments.  But it
quickly became clear that this was going to be an ongoing thing.

So I created calling patterns, which encode how to arrange arguments.
Then I could call existing C functions for Kernel without writing
extra code (either Kernel or C).

But it was slightly odd to always have a calling pattern in every
instruction.  About half the time, they weren't used.  They also
overlapped somewhat with the T_FF_W_DATA type, and I kept wanting to
control the bundled data better.

So I replaced calling patterns and T_FF_W_DATA with actual lightweight
instructions to the Eval_Cycle.  These are the T_CURRIED object type.



**** Naming conventions for decurriers

Decurrier names encode the instruction for building the argument
list.  They have the following pattern:
 * "dcrry_"
 * A digit
 * A sequence of 3-letter groups

Table of 3-letter groups:

 * VLL :: The value passed (returned) to this continuation.
   * This could be extended as V1 etc, but hasn't been yet.
 * ALL :: The entire stored argument list
 * A01 :: The car of the stored argument list (Which must be a pair)
 * A02 :: The cadr of the stored argument list, etc
 * AX1 :: The cdr of the stored argument list
 * AX2 :: The cddr of the stored argument list, etc
 * C :: A cons of the next 2 arguments.  Can be repeated to make a
        list.  No "_" after it because it's not a real piece.
   * It's anomalous because it is not 3 letters.
 * dot :: The rest of the list is considered dotted.  Often followed
          by ALL.

It's possible that this will be extended in the future.

*** C to C calling sequence

Can proceed in two main ways:
 * If it's a tail call, code can just call the next C function
 * Otherwise:
   * The original C function schedules a continuation, using one of
     the CONTIN_* macros.
   * That macro specifies a calling-pattern.
     * Except for CONTIN_0 because its target takes no argument.
   * The eval loop eventually reaches that continuation (maybe, and
     maybe more than once).
   * kernel_call_by_pattern, using that pattern, gathers an arglist
     from several sources:
     * The value itself
     * Stored arguments
     * Possibly from constants as well.
   * kernel_call calls the C function itself.
     * Sometimes it also passes the dynamic environment
     * Sometimes it also passes the interpreter object.
     * In the future, some common cases of calling-pattern and
       function-type may be dispatched directly in kernel_call_by_pattern.

*** RGSTR and registerables

When the number of C objects exported to Kernel reached a few dozen, I
knew I couldn't keep manually writing them into the ground environment
registerables array.  I needed an automatic way of exporting them.
That's what RGSTR is.

The RGSTR macro doesn't make any output during normal compilation.
But during a special preprocessor pass, it emits data for declaring a
Kernel object.  This output is processed and winds up in a file in the
registerables subdirectory, and that file is included in an
appropriate array.

The arguments to the RGSTR macro are:
 * The target environment.
 * The Kernel name, as a string.
 * A C reference to the object.  Use REF_APPL, REF_OPER, or REF_OBJ as
   appropriate.

The target environment is usually `ground', but can also be:
   * unsafe :: for objects used only by the prolog.  They may behave
               bizarrely if used incautiously.
   * simple :: For simpler versions of Kernel functionality which are
               overridden by fuller versions built on them (or
               eventually will be).  For instance, map1.





*** Functions in `simple'

Combiners that are put in `simple' instead of `ground' are usually
combiners that resemble a ground combiner but are limited in some way.
The ground combiner is usually constructed from it in the prolog.

Some cases:
 * A unary or binary combiner, where the ground version is nary.
   * eg >?/2
   * Naming convention: Basename "/" Number-of-args
 * A combiner with argument type restrictions.
   * eg equal?/2-num-num
   * Naming convention: As above, then follow the "/N" with a list of
     the types, separated by hyphens.
 * A combiner that accepts a different combiner argument
   * Eg, every?-xary.1
     * Rename: every?/2-xary
   * Naming convention: As above.  "Xary" is a type name.  Trailing
     "any" types can be omitted.
 * A combiner that accepts only combiners that do not use the Kernel
   eval loop.
   * Eg, typecheck-raw
     * Rename this listtype/N-trivpred
   * Naming convention: As above: "trivpred" is a type name

Type names:
 * unary :: A combiner taking 1 arg
 * binary :: A combiner taking 2 args
 * nary :: A combiner taking any number of args
 * xary :: A combiner taking a non-list argobject
 * num :: any number
 * any :: no restriction
 * trivpred :: xary operative which returns boolean and does not use
               the Kernel eval loop.