home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / Misc / CLISP-1.LHA / CLISP960530-sr.lha / doc / extend.txt < prev    next >
Encoding:
Text File  |  1996-04-15  |  16.5 KB  |  408 lines
  1.                         Extending CLISP
  2.                         ===============
  3.  
  4. Since CLISP is provided with source, you can add features you want yourself.
  5.  
  6. Additions in Lisp are accomplished by writing a Lisp module and adding a
  7. LOAD form for it at the end of init.lsp. Please conditionalize with #+ and #-
  8. if you use features that are not present in all platforms supported by CLISP.
  9.  
  10. Additions in C or assembly language are also possible, as well as interfacing
  11. code written in other languages.
  12.  
  13. As general rules for extensions to CLISP:
  14.  
  15. 1. Add what you want in Lisp. This is both more portable and easier to
  16.    maintain.
  17.  
  18. If that is not possible, you may choose to write it in C.
  19.  
  20. 2. If it makes up a separate module, then write it as a stand-alone program,
  21.    with the usual argv/argc interface, and call it from Lisp using
  22.    (SHELL "your-program argument ...") or
  23.    (EXECUTE "your-program" "argument" ...)
  24.  
  25. Otherwise you'll indeed have to extend CLISP.
  26.  
  27. For now, CLISP has no foreign function call facility with automatic type
  28. conversion between Lisp and C types and dynamic loading of C object modules.
  29. Thus you will create your own version of CLISP, which will have .mem files
  30. incompatible with what I distribute. (.fas files remain valid, you needn't
  31. recompile everything.)
  32.  
  33. Split your project into three parts:
  34. A. The high-level things that may be implemented in Lisp. Do them in Lisp.
  35. B. C code that is already present or doesn't need access to Lisp data
  36.    structures.
  37. C. C code that makes up the interface between CLISP and part B. You may use
  38.    CLISP's dynamic memory management here for the purposes of part B.
  39.  
  40. Part A code.
  41.  
  42. Make the names of the .lsp files known to your makefile. This is done by
  43. modifying the lines CODE=... in makemake.in.
  44. Make them also contained in lispinit.mem. This is done by adding LOAD forms
  45. at the end of init.lsp.
  46.  
  47. Part B and C code.
  48.  
  49. Code in modules that begin with a  #include "lispbibl.c"  are considered
  50. internal to CLISP, code in other modules or libraries is considered external.
  51. Important: Calls from internal to external code must be protected by a pair
  52. of  begin_call();  and  end_call();  statements. Calls from external to
  53. internal code must either be avoided altogether, or the called code must
  54. begin with  begin_callback();  and end with  end_callback();  .
  55.  
  56. Part C code is usually (although not absolutely necessary) written in a
  57. modified or enhanced C, which has been created to overcome the limitations
  58. of some C compilers. Such code is contained in .d files, which are
  59. preprocessed to .c files. The modifications against C are the following:
  60. - # and space introduce comments up to the end of the line.
  61. - Preprocessor directives may be preceded by spaces, so that they nest
  62.   properly with the rest of the program.
  63. - Function declarations and definitions have the "storage class" `global'
  64.   or `local'. `global' implies global visibility, `local' corresponds to
  65.   `static'.
  66. - Function declarations are written with full parameter types, as in ANSI C.
  67. - Function definitions are written as in traditional C, with only the
  68.   parameter names listed within the parentheses, and with full parameter
  69.   declarations afterwards, one declaration for each parameter.
  70. - #if defined(...), #elif, #error may be used as in ANSI C.
  71. - Adjacent strings are merged after preprocessing, as in ANSI C.
  72. - Variable declarations within functions are usually introduced by `var'
  73.   (for readability), They may receive the storage class `reg1' ... `reg10'
  74.   which stand for `register' or nothing, depending on the CPU's number of
  75.   registers. `reg1' is to be used for variables of highest priority, `reg10'
  76.   for rarely used variables which may as well be `auto'.
  77. This allows you to use the same source for both traditional (= deficient) and
  78. ANSI C compilers.
  79.  
  80. Part C code may use the macros and functions listed in lispbibl.d.
  81.  
  82. Make the names of the .d files known to your makefile. This is done by
  83. modifying the lines MODULES=... in makemake.in.
  84. The other modules (.o object files and .a libraries) should be added to the
  85. lines LIBS=... in makemake.in.
  86.  
  87. When building an interface to CLISP, you must of course work with Lisp objects,
  88. at least with the arguments and the value to be returned.
  89. There are some rules that govern working with Lisp objects. The C type of a
  90. Lisp object is always `object'.
  91. 1. C variables may hold Lisp objects only as long as no garbage collection may
  92.    be invoked. Those routines that may invoke a garbage collection are marked
  93.    in lispbibl.d as "kann GC auslösen"; they include allocate_cons(), funcall()
  94.    and eval() and even equalp(). Only low level routines and macros such as
  95.    type tests, eq() and accessing the slots of Lisp data types can't invoke
  96.    a garbage collection.
  97. 2. The regular place for Lisp objects is on a special stack called the STACK.
  98.    The top element is STACK_0, the next-to-top element is STACK_1 etc. There
  99.    are macros pushSTACK() to push an object onto the stack and popSTACK() to
  100.    remove the top element.
  101. 3. Arguments to functions are passed on the stack. In the simplest case, a
  102.    function with n required arguments receives the first argument in
  103.    STACK_(n-1) and the last argument in STACK_0. When the function has done
  104.    its work, it must remove its arguments from the STACK - n times popSTACK()
  105.    or, equivalently, skipSTACK(n) - and put its return value in the variable
  106.    value1, as well as the number of return values (1 in most cases) in the
  107.    variable mv_count. (Note that value1 is not GC-safe in the sense of
  108.    paragraph 1!) You may enforce a check that the STACK has been set correctly
  109.    by defining STACKCHECKS and STACKCHECKC as TRUE in lispbibl.d.
  110. 4. Intermediate values of type `object' should be saved on the STACK when
  111.    needed. Of course, optimizations are possible: Assuming that foo(), foo1()
  112.    and foo2() return objects and may invoke GC, you may well write
  113.        var object temp = foo1(foo(x)); # don't use the contents of x afterwards!
  114.    but not
  115.        var object temp = foo2(foo(x),foo(y));
  116.    Be careful! If you are not sure what is allowed and what not, you can let
  117.    me <haible@ma2s2.mathematik.uni-karlsruhe.de> proof-read your code.
  118. 5. If you need a global variable of type `object', add it at the end of
  119.    constobj.d like this:
  120.    LISPOBJ(foo,"initial value, to be read in at initialisation time")
  121.    You can then refer to the variable as O(foo).
  122.    Of course, you will have a reentrancy problem when using global variables.
  123.  
  124. Lisp functions with n required arguments are declared like this:
  125. LISPFUNN(foo_bar,n) { /* ... function body ... */ }
  126. Also add a line
  127. LISPFUNN(foo_bar,n)
  128. at the end of subr.d.
  129.  
  130. With every Lisp function is associated its name, a symbol. To declare a
  131. symbol known at compile-time, add a line
  132. LISPSYM(foo_bar,"FOO-BAR",pack)
  133. at the end of constsym.d. The string is the symbol's print name, and pack
  134. is either `lisp', `system', `keyword' or any package name defined in
  135. constpack.d. Be careful when choosing pack=lisp: you may produce package
  136. conflicts with applications.
  137. You can then refer to the symbol as S(foo_bar).
  138. NIL is nothing more than S(nil).
  139.  
  140.  
  141.                               An example
  142.                               ----------
  143.  
  144. As an example, consider the 8-queens problem. The brute-force search may
  145. gain speed when written in assembly language or in C.
  146.  
  147. We may generate queens.o either from
  148.  
  149. ================================= queens.c =====================================
  150. /* Compute the number of solutions to the n-queens problem on a nxn
  151.    checkboard. */
  152.  
  153. /* dynamic data structures not needed for such a simple problem */
  154. #define nmax 100
  155.  
  156. int queens (n)                /* function definition in traditional C style */
  157.   int n;
  158. { /* Compute the solutions of the n-queens problem. Assume n>0, n<=nmax.
  159.      We look for a function D:{1,...,n} -> {1,...,n} such that
  160.      D, D+id, D-id are injective. We use backtracking on D(1),...,D(n).
  161.      We use three arrays which contain information about which values
  162.      are still available for D(i) resp. D(i)+i resp. D(i)-i. */
  163.   int dtab[nmax]; /* values D(1),...D(n) */
  164.   int freetab1[nmax+1]; /* contains 0 if available for D(i) in {1,...,n} */
  165.   int freetab2[2*nmax+1]; /* contains 0 if available for D(i)+i in {2,...,2n} */
  166.   int freetab3a[2*nmax-1]; /* contains 0 if available for D(i)-i in {-(n-1),...,n-1} */
  167. #define freetab3 (&freetab3a[nmax-1])
  168.   /* clear tables */
  169.   { int i; for (i=1; i<=n; i++) { freetab1[i] = 0; } }
  170.   { int i; for (i=2; i<=2*n; i++) { freetab2[i] = 0; } }
  171.   { int i; for (i=-(n-1); i<n; i++) { freetab3[i] = 0; } }
  172.  {int counter = 0;
  173.   int i = 0; /* recursion depth */
  174.   int* Dptr = &dtab[0]; /* points to next free D(i) */
  175.   entry: /* enter recursion */
  176.     i++;
  177.     if (i > n)
  178.       { counter++; }
  179.       else
  180.       { int try;
  181.         for (try = 1; try <= n; try++)
  182.           { if (freetab1[try]==0 && freetab2[try+i]==0 && freetab3[try-i]==0)
  183.               { freetab1[try]=1; freetab2[try+i]=1; freetab3[try-i]=1;
  184.                 *Dptr++ = try;
  185.                 goto entry;
  186.                 comeback:
  187.                 try = *--Dptr;
  188.                 freetab1[try]=0; freetab2[try+i]=0; freetab3[try-i]=0;
  189.       }   }   }
  190.     i--;
  191.     if (i>0) goto comeback;
  192.   return counter;
  193. }}
  194. ================================================================================
  195.  
  196. or
  197.  
  198. ================================= queens.d =====================================
  199. # Compute the number of solutions to the n-queens problem on a nxn checkboard.
  200.  
  201. #include "lispbibl.c"
  202.  
  203. # dynamic data structures not needed for such a simple problem
  204. #define nmax 100
  205.  
  206. global uintL queens (n)        # function definition in traditional C style
  207.   var reg4 uintC n;            # use `var' and `register', n needs only 16 bit
  208. { # Compute the solutions of the n-queens problem. Assume n>0, n<=nmax.
  209.   # We look for a function D:{1,...,n} -> {1,...,n} such that
  210.   # D, D+id, D-id are injective. We use backtracking on D(1),...,D(n).
  211.   # We use three arrays which contain information about which values
  212.   # are still available for D(i) resp. D(i)+i resp. D(i)-i.
  213.   var uintC dtab[nmax]; # values D(1),...D(n)
  214.   var uintB freetab1[nmax+1]; # contains 0 if available for D(i) in {1,...,n}
  215.   var uintB freetab2[2*nmax+1]; # contains 0 if available for D(i)+i in {2,...,2n}
  216.   var uintB freetab3a[2*nmax-1]; # contains 0 if available for D(i)-i in {-(n-1),...,n-1}
  217.   #define freetab3 (&freetab3a[nmax-1])  # indent this correctly
  218.   # clear tables
  219.   { var reg2 uintC count;
  220.     var reg1 uintB* ptr = &freetab1[1];
  221.     dotimespC(count,n, { *ptr++ = 0; } ); # clear n>0 array elements
  222.   }
  223.   { var reg2 uintC count;
  224.     var reg1 uintB* ptr = &freetab2[2];
  225.     dotimespC(count,2*n-1, { *ptr++ = 0; } ); # clear 2n-1>0 array elements
  226.   }
  227.   { var reg2 uintC count;
  228.     var reg1 uintB* ptr = &freetab3[-(n-1)];
  229.     dotimespC(count,2*n-1, { *ptr++ = 0; } ); # clear 2n-1>0 array elements
  230.   }
  231.  {var reg5 uintL counter = 0; # may need 32 bits for the counter
  232.   var reg2 uintC i = 0; # recursion depth
  233.   var reg3 uintC* Dptr = &dtab[0]; # points to next free D(i)
  234.   entry: # enter recursion
  235.     i++;
  236.     if (i > n)
  237.       { counter++; }
  238.       else
  239.       { var reg1 uintC try;
  240.         for (try = 1; try <= n; try++)
  241.           { if (freetab1[try]==0 && freetab2[try+i]==0 && freetab3[try-i]==0)
  242.               { freetab1[try]=1; freetab2[try+i]=1; freetab3[try-i]=1;
  243.                 *Dptr++ = try;
  244.                 goto entry;
  245.                 comeback:
  246.                 try = *--Dptr;
  247.                 freetab1[try]=0; freetab2[try+i]=0; freetab3[try-i]=0;
  248.       }   }   }
  249.     i--;
  250.     if (i>0) goto comeback;
  251.   return counter;
  252. }}
  253. ================================================================================
  254.  
  255. or on 68000 based Unix machines:
  256.  
  257. ================================= queens.S =====================================
  258. ! Processor: 680x0
  259. ! Parameter passing: on the stack sp@(4), sp@(8), ...
  260. ! Return value: in d0
  261. ! Registers a0-a1,d0-d1 may be used freely.
  262. ! Registers a2-a4,d2-d7 must be saved when used.
  263.  
  264. #define nmax 100
  265.  
  266.            .text
  267.            .globl _queens
  268. _queens:   moveml a2-a3/d2-d6,sp@-   ! save registers
  269.            movel sp@(28+4),d6        ! n
  270.            subw #7*nmax+2,sp         ! make space in the stack: 7*nmax+1 bytes
  271.            leal sp@(2*nmax),a1       ! freetab1
  272.            leal a1@(nmax+1),a2       ! freetab2
  273.            leal a2@(3*nmax),a3       ! freetab3
  274.            ! clear tables:
  275.            leal a1(1),a0             ! &freetab1[1]
  276.            movew d6,d0
  277.            bras q12
  278. q11:         clrb a0@+
  279. q12:         dbra d0,q11
  280.            leal a2(1),a0             ! &freetab2[1]
  281.            movew d6,d0
  282.            bras q22
  283. q21:         clrb a0@+
  284.              clrb a0@+
  285. q22:         dbra d0,q21
  286.            movel a3,a0
  287.            movew d6,d0
  288.            subqw #1,d0
  289.            subw d0,a0                ! &freetab3[-(n-1)]
  290.            addw d6,d0
  291.            bras q32
  292. q31:         clrb a0@+
  293. q32:         dbra d0,q31
  294.            clrl d7                   ! counter := 0
  295.            clrw d5                   ! i := 0
  296.            leal sp@(0),a0            ! dptr := dtab
  297. entry:     ! enter recursion
  298.            addqw #1,d5               ! i++
  299.            cmpw d6,d5
  300.            bhis count                ! i > n ?
  301.            moveq #1,d1               ! try := 1
  302. tryup:       movew d1,d2
  303.              movew d1,d3
  304.              addw d5,d2              ! try + i
  305.              subw d5,d3              ! try - i
  306.              moveb a1@(d1.w),d0
  307.              orb a2@(d2.w),d0
  308.              orb a3@(d3.w),d0
  309.              bnes skip
  310.              st a1@(d1.w)
  311.              st a2@(d2.w)
  312.              st a3@(d3.w)
  313.              movew d1,a0@+
  314.              bras entry
  315. comeback:    movew a0@-,d1
  316.              movew d1,d2
  317.              movew d1,d3
  318.              addw d5,d2              ! try + i
  319.              subw d5,d3              ! try - i
  320.              clrb a1@(d1.w)
  321.              clrb a2@(d2.w)
  322.              clrb a3@(d3.w)
  323. skip:        addqw #1,d1             ! try++
  324.              cmpw d6,d1
  325.              blss tryup              ! try <= n ?
  326. return:    subqw #1,d5
  327.            bnes comeback
  328.            movel d4,d0               ! return counter;
  329.            addw #7*nmax+2,sp
  330.            moveml sp@+,a2-a3/d2-d6   ! restore registers
  331.            rts
  332. count:     addql #1,d4               ! counter++
  333.            bras return
  334. ================================================================================
  335.  
  336. We furthermore need an interface:
  337.  
  338. ============================== callqueens.d ====================================
  339. # Interface to the queens() function
  340.  
  341. #include "lispbibl.c"
  342.  
  343. # Conditionalize, such that we don't lose the ability to build CLISP without
  344. # the QUEENS function. The flag -DQUEENS must be given to the C compiler.
  345.  
  346. #ifdef QUEENS
  347.  
  348. #define nmax 100
  349.  
  350. # extern declaration
  351. extern int queens (int n); # use this one if using queens.c above
  352. extern uintL queens (uintC n); # use this one if using queens.d above
  353. extern uintL queens (uintL n); # use this one if using queens.S above
  354.  
  355. # (LISP:QUEENS n) returns the number of solutions to the n-queens problem.
  356. # n ought to be an integer > 0, <= nmax. Otherwise it returns NIL.
  357. LISPFUNN(queens,1)
  358. { # No garbage collection is a problem. So we get the argument from the
  359.   # STACK immediately.
  360.  
  361.   var reg1 object arg = popSTACK(); # clean up STACK at the same time
  362.   # If arg is an integer > 0, <= 100, ist must be a nonnegative fixnum.
  363.   # We do the argument check in two steps: 1. check whether arg is a
  364.   # nonnegative fixnum. 2. Extract its value. 3. Check its value.
  365.   if (!posfixnump(arg)) goto bad_arg;
  366.  {var reg2 uintL n = posfixnum_to_L(arg);
  367.   if (!(n>0 && n<=nmax)) goto bad_arg;
  368.  
  369.   # Arguments are checked. Do our job:
  370.   { var reg3 uintL result;
  371.     begin_call(); # not needed when using queens.d above
  372.     result = queens(n); # call external function
  373.     end_call(); # not needed when using queens.d above
  374.     # Assume result is >=0 and <2^32 (which is guaranteed by the type
  375.     # of problem we have and the amount of time queens() may have run).
  376.     # So an uintL is enough, and the following call is appropriate.
  377.     value1 = UL_to_I(result); # convert result to nonnegative integer
  378.     mv_count=1; # no "multiple" values
  379.   }
  380.   return;
  381.  }
  382.  
  383.   bad_arg:
  384.     # We could issue an error. We prefer to return NIL here.
  385.     value1 = NIL; mv_count=1; return;
  386. }
  387.  
  388. #endif # QUEENS
  389. ================================================================================
  390.  
  391. To subr.d we add the lines
  392.  
  393. # ---------- CALLQUEENS ----------
  394. #ifdef QUEENS
  395. LISPFUNN(queens,1)
  396. #endif
  397.  
  398. To constsym.d we add the lines
  399.  
  400. # ---------- CALLQUEENS ----------
  401. #ifdef QUEENS
  402. LISPSYM(queens,"QUEENS",lisp) # put it into the LISP package (quick and dirty)
  403.                               # such that it will be visible in the USER package
  404. #endif
  405.  
  406. That's all. After having built a new CLISP you will be able to call (QUEENS 8).
  407.  
  408.