Monday, June 17, 2013

Building a Lisp Interpreter from Scratch -- Part 11: This and that

(This is the final part of a series of posts on pLisp)

Well, it's time to wind up the series. It's been fun, spending time doing two of my favourite things (programming and writing; the only way this could have been topped is if I were to write about the coding involved in a Lisp-based first-player porn video game [just kidding]). I'll use this post to record stuff that doesn't really fit in any of the topics covered so far, and other random things.
  1. I have continued to work on the code since starting the series, and the posts are already somewhat out of sync with the code. One notable change is that WHILE is now a special form as opposed to a macro. There was nothing wrong with the macro (other than making your head hurt every time you looked at the definition), but since WHILE figures in the definitions of quite a few standard macros (DOLIST, DOTIMES, etc.), this makes sense from a performance perspective.

  2. I am in the process of adding a RETURN-FROM special form to handle non-local returns. This is pretty straightforward to implement using continuations, but things are still flaky -- it works fine for simple function calls, but barfs for functions that call macros internally.

  3. Performance-wise, pLisp has become slow as molasses. I probably need to do something about the implementation of arrays, and look at seriously optimizing the code, particularly memory management. Update: I replaced the custom binary search tree implementation with a red black tree, and the speedup has been phenomenal.

  4. The debug stacktrace at present, to put it politely, sucks big time. This is a direct consequence of moving to a compiler/VM architecture -- the execution trace at the VM level does not make sense for the application programmer; there needs to be a way to map (and display) source forms to the VM instructions, similar to how conventional debuggers manage things.

  5. The next major goal is the IDE -- something that approaches the power of a typical Smalltalk IDE with a system browser where we can browse all the symbols/packages, view/edit the code in a  pane, workspace and transcript windows to replace the command line top-level, a debugger UI, and so on. Man, I miss Smalltalk, especially after mucking around so much with Emacs, gcc and gdb.

  6. I realized that the NUATE instruction (used to invoke continuations) is not used at all, for the simple reason that the compiler never emits it. Just a simple matter of making the compiler inspect a symbol and see if it is bound to a continuation object (similar to how it handles macros now), will probably get around to implementing this soon.

  7. An object system is also in the works (not at the level of sophistication of CLOS or similar), but a functioning system nevertheless, with classes, inheritance, slots, and methods. 

Thursday, June 06, 2013

Building a Lisp Interpreter from Scratch -- Part 10: Foreign Functions

(This is Part 10 of a series of posts on pLisp)

The foreign functions interface in pLisp is the gateway to access and use external code. It is defined by two special forms, LOAD-FOREIGN-LIBRARY and CALL-FOREIGN-FUNCTION. The first form takes a string (literal or otherwise) that represents the name of the shared library to load, and does a dlopen() on it. The successfully created handle to the library is stored internally by pLisp, and is used to service requests through the second form. The second form is the actual invocation of the library's exported function.

We use libffi for implementing these special forms.

The data types supported are integer, float, character and string, and pointers to these data types.

To illustrate with an example, if we have a shared library called that exposes a function called fn_ret_float:

float fn_ret_float(int i, float f, char c, char *s)

  printf("%f\n", f + f);
  printf("exiting fn_ret_float\n");
  return f+f;

we invoke the function as:

$ ./plisp
Welcome to pLISP. Type 'quit' to exit.
USER> (load-foreign-library "")
USER> (call-foreign-function "fn_ret_float" 'float
                             '((10 integer)
                             (6.5 float)
                             (#\a character)
                             ("abc" character-pointer)))
exiting fn_ret_float

The first parameter to CALL-FOREIGN-FUNCTION is the name of the to-be-invoked function, expressed as a string; the next parameter is the return type of the function; this is followed by a list containing the actual parameters and their respective data types. Passing the data types too may seem redundant, since pLisp can figure out the types on its own, but we still need to differentiate between pointers and non-pointers, so we have to live with this redundancy.

Another example:

int fn_arg_int_ptr(int *i)
  printf("passed value is %d\n", *i);
  *i = 100;
  return 0;

USER> (define i 10)
USER> (call-foreign-function "fn_arg_int_ptr" 'integer
                             '((i integer-pointer)))
passed value is 10

This illustrates the above point about the redundancy -- if we do not mention the type of the argument (integer-pointer), pLisp will not know whether we need to pass the value of i or the address of i to the function.

A couple of points with respect to libffi:
  1. There seems to be some issues with using the ffi_arg struct for returning floats; I had to explicitly use a float variable for this.
  2. libffi is also used to implement the FORMAT special form. It handles the variable arguments requirement perfectly. More on FORMAT later.