Aug 23, 2022

Mlisp Scoping Rules for the Set Operator

From the start of developing Mlisp, I was never sure of how I should define the set operators. Common Lisp makes the most sense to me on the usage of the set operators in initializing variables, ie., the "defconstant", and "defparameter" operators. I stayed away from using "defvar" because this operator will initialize an already existing global variable which seems unneccesary to me. These operators are consistent with the notion of using dynamic or global variables at the top-level.

In Scheme, any variable is initialized with the operator "define". The operator "set!" is supposed to work on modifying an existing variable. Since Scheme is supposed to be lexically scoped, the notion a having a dynamic or global variable does not really exist. Yet, you can sort of define a global variable in Scheme by defining it at the top-level. You can change a variable defined at the top-level by using the "set!" operator at the top-level, or in the procedural level below top-level. (Also note Scheme's "make-parameter" which defines a variable at the top-level.)

The set operators in Common Lisp and Scheme are consistent if you don't try to mix these features from both languages. But after all these years of mixing features of Common Lisp and Scheme, I've come the conclusion that you cannot define consistent set operators in a simple way using the scoping rules of Mlisp.

After trying to use Chez Scheme a little more, I noticed that the "set!" operator can initialize a variable inside a "let" statement. For example,

    (let ()
      (set! x 1)     ; set closure inside a let
      (printl x))
works. Gauche and Guile Scheme tells you that x is an unbounded variable.

Mlisp uses the following set operators:

    set  (like define in Scheme, or setf in CL),
    set* (like defparameter in CL),
    set+ (like defconstant in CL).
    set! (like setq and setf for top-level global variables in CL),
    set% (like setq for local lexical variables in CL),

Mlisp set operators sort of work, but has not been perfected yet. Since I started programming using Common Lisp and then learned Scheme, I'm inclined (or prejudiced) to the Common Lisp usage of dynamic variables. In some ways, the Common Lisp's way of defining a variable, in general, is simpler, and maybe cleaner.

Jan 9, 2022

Continuations and the Unfolding of State

Continuations occur in program execution when the context for evaluation changes.

Dec 29, 2021

XLisp with Continuations was Truely Experimental

The way David Betz wrote Xscheme in 1988 was remarkable because of the simplicity and boldness of its implementation based on the concept of using full continuations. Given all the possible traps, Xscheme works remarkably well without seg-faulting.

Xscheme's scoping rules are those used in Common-lisp. So Scheme procedures or operators like define and set! do not work in the xscheme's (and hence mlisp's) let procedure. This is part of the evolutionary problems in mlisp's future.

The following is an article written by Duha and Felleisen in 1991 which is based on Alan Bawden's note that Scheme's letrec and define procedures are not "purely declarative facility". The authors of this article mention that Chez scheme implemented this as a fix which was a "non-RRRS" feature. Chez scheme is the Scheme I've decided to use in the future after I completed a review of the Scheme's I've used in the past which is descibed below.

Updated: Nov 26, 2021
Nov 21, 2021

Lisp with Threads

What impresses me about the results of benchmark below is that SBCL is fantastic at numerical processing. Chez is nice to program in also. Most of the compilers tested below get stuck in arithmetic crunching.

The other lisps I've tested which focused on running parallel applications using pthreads were: Clisp, Clozure, Chicken, Guile and Bigloo. Clisp and Chicken failed completely. The others above were hard to program and optimize for speed using native pthreads. You can e-mail me for more details on the evaluation.

ref: from the binarytree benchmarks in directory mlisp/tests/btree/Readme


This btree benchmark, which was derived from gcbench, is a good
general test of the lisp implementation's garbage collection.
The processor has 4 cores.  The routine btree.l has basically no
type optimizations.

                     chez     sbcl       ecl
btree.l  (21)         22s      25s      121s

         (21)                 9.4s**
         (21)         23s*    9.0s***    42s^**

(threaded versions)
**    - concurrent with option "--dynamic-space-size 16384"
***  - with option  "--dynamic-space-size 16384"
^**   - compile result is
      OPTIMIZE levels: Safety=2, Space=0, Speed=3, Debug=0
*   btree-chez-2.l   - chez native pthreads (must be optimized for
                       numerical use, otherwise it's fast)

Less numerically intensive version (better for testing just GC)

                          sbcl    chez    ecl         C (21)      1.9s    7.6s*   8.9s**     9s^

*   btree-chez-3.l    (time for btree-3.l(21) is 15s so using chez's
                       parallel threads speeds up performance by 2x
                       for this test)
^   plain gcc with -O2 option


btree.lua       (21)       46s
btree-lua-2.lua (21)     14.5s*

* concurrent

Oct 19, 2021

Replaced Mlisp-0.7u with Nlisp-0.4l

Depreciated the xlisp-3 version of MLisp using the simpler code based from Nlisp. There's only one version of Mlisp now. Changes to Mlisp in the future will be a change of the stack structure to use a segmented call stack (ref: Representing Control in the Presence of First-Class Continuations, by Hieb, Dybvig and Bruggeman, 1990). JIT development will continue on Mlisp.

Oct 14, 2021

Performance Benchmarks on Nlisp

So far, I've studied the tutorial on creating a toy interpreter using libgccjit, and the examples for gnu lightning and libjit. Libjit abstracts away the little details of assembly coding.

The Boyer and Btree (aka GCbench) benchmarks reveals nlisp spents up to 80% of its time in the garbage collector, GC, under heavy loads.

In the btree.l, "binarytrees:", test, (nlisp -L btree.l 16), the profiler shows nlisp spent about 25% of its time in the GC. For a larger tree traversals, (nlisp btree.l 17), the profiles shows nlisp spent greater than 80% of its time in the GC. This degradation of performance is due to the GC repeatedly trying to allocate more memory, and continually traversing long trees to mark each accessible cell. As each cell segment gets larger, it will take an exponentially longer time to complete a sweep of the unmarked cells. The compaction of vector segments did not impact performance too much as it took only 2% of the running time.

Sept 29, 2021

A Little Review on Implementing JIT for Mlisp

Now, I seem to be sliding backwards when trying to move forwards developing a design for Mlisp. What's becoming clear to me now is that I could not develop a JIT without a virtual machine. That's the reason I gave up on the old nlisp which had no byte code compiler. It would be hard to come up with a simple way to write advanced procedures without embedding sub-procedures or subroutines within higher level procedures. For example, recursion fits within an execution model using the virtual machine. The lambda function defines a way to build procedures up from the integration of smaller sub-procedures. It's almost as if a fuller lambda expansion necessarily required the dispatching function of a virtual machine.

And that's the machine. That's what all the little parenthesis, ie./eg., (*(!*(%(&^(&^%$(**)*&^).....)))) are about. Might seem obvious in retrospect, but is necessary maybe to think about now.

David Betz's stack oriented Xlisp and hence Mlisp have a lot in common with Maclisp. Maclisp had it's origin in Scott Fahlmann's Spice lisp which led to CMUCL and SBCL. I spent some time reading the old code in CMUCL this weekend. It's amazing software considering it was written in the early 1980's when the C-language was still not in wide spread use. CMUCL was designed for special computers with its own microcode. The more modern CMUCL's virtual machine was written in C with a design which is rather a standard way VM's for lisp are written today. What's incredible to me is that it uses an "implicit continuation representation" (in ref: Design of CMU Common Lisp) design in its compiler. There's a well written story on this in Gabriel and Steels's "Evolution of Lisp", section 2.8, Scheme: 1975-1980. Scheme's continuation model can actually simplify the construction of lisp compilers. My interpretation of this is that "context", especially temporal, time ordered context (or "aka" continuations) is a necessary requirement for a descriptive language. Continuations is analogous to an operating system's context switches.

CMUCL and SBCL uses the ideas for continuation in its compiler, but never implemented continuations in the language itself. This makes sense because in practical applications today, the use of continuations is still not as efficient relative to using coroutines or threads. The Ruby language implemented continuations, but now makes it available only as an installation option. Practical languages like Ocaml versus SML/NJ do not have continuations. This perfectly fits the usage of the language. But for writing languages with greater descriptive powers, parallel processing algorithms maybe required due to the associative capabilities required in a short temporal intervals characteristic of spoken languages.

In the next couple of days I'll probably continue reading "From Folklore to Fact: Comparing Implementations of Stack Continuations" and "Implementation Strategies for First-Class Continuations". This is "where the rubber meets the road" as they say. Moving forward on Mlisp's JIT would parallel work like using GNU-Lightning in speeding up Smalltalk. Trying to create a specific design plan for this has me really absorbed.

Sept 15, 2021

Selecting the JIT Tool

I've been thinking about a JIT tool for developing mlisp for about a month, and during the last couple of days it's become obvious to me that I should try GNU Lightning first. This is because Lightning was originally designed to speed up Smalltalk's context switching between objects. Smalltalk objects are the counterpart to Lisp procedures with respect to the language's internal virtual machine. Both objects and procedures require the same kind of contextual management of its arguments and values. And in many instances these kinds of language implementations uses stacks to track of objects or procedures.

Lightning explicitly refers to continuations in the section on setting up procedures (ie., trampolines, continuations and tail call optimization). This is at the core of what JIT for mlisp is about.

The challenge for me is to implement JIT efficiently so that mlisp will run the ctalk benchmark, for example, as fast as possible. Most scheme implementations don't consider fast execution of continuations critical. In my opinion, if you want to create a machine which understands language, with all the complexity of words in its context, then fast context switching with continuations is essential.

So I'm focusing my attention now on Lightning, and will focus to a lesser extend on libgccjit or luajit's dynasm for now. I don't seem to have the time to looking into the Smalltalk's implemention of Lightning, nor maybe Ruby's JIT. The horizon for languages using objects like Smalltalk and Ruby shines bright, but they're intrinsically inefficent because of their exaggerated requirement to explicitly depend on object linkages (in the form of inheritance). But as time passes, the evolution of programming languages will follow Smalltalk's original design concept, and that's the same for mlisp, in my opinion.

Sept 11, 2021

The Nbody Benchmark

                        (time in seconds)
 # of particles      chez      sbcl      luajit
  5000              0.15s      0.14s      0.01s
  500000            1.54s      0.22s	  0.16s
  5000000           14.6s      0.98s      1.44s
  50000000           188s      8.14s      14.5s

This is an extremely interesting computationally intensive benchmark.
SBCL and Luajit were notably robust at 50 million particles.

The Luajit language implementation is extremely efficient. Most notable is its small size, and simplicity. It's a model implementation of a programming language for mlisp to try to follow.

Sept 9, 2021

States or Values, Ordered Sequences, and Procedures

The intuitive model that I follow for thinking about context switching using continuations comes from temporal sequences describing physical processes. For me, a simple description of a computational processes requires keeping track of a procedure's calculation within an "environment" for the procedure which includes its arguments, and also all of the data or states which can be associated its arguments. The procedure can become enfolded in the global data environment which is the context in which all computation occurs.

It's worth reading formal descriptions of using continuations to get a perspective on how wide the applications of continuation is. For example, John Reynolds' article "Definitional Interpreters for Higher-order Programming Languages" (1998), is a concrete explanation on continuations. The article provides one a really good background on continuations. This article explains relationships between "embedding continuations in values", and how procedures can occur as values.

How procedures occur as values in a programming language is a key idea.

Sept 3, 2021


Conceptually, I like using first class or full continuations for asynchronous event handling. Using continuations is not hard if you can keep things simple. Modelling the real world events requires asynchronicity. Thus in a rather insane fashion I'm leveling anything that gets in the way of continuations. This includes exception handling with throw/catch and unwind-protect for now. This does mean I won't go back to using these special operators in some form in the future if there's a simple way to do so. (Ref: Kent Pitman's comments on unwind-protect versus continuations.)

August 25, 2021

Mlisp JIT - Now The Tedious Coding

Moving to add native compilation to Mlisp requires spending more time on the bytecode interpreter. So I'm archiving Nlisp-0.3 for now. The complexity of Mlisp-0.7's coupled continuation/gc code requires me to still strip away alot of the continuation dispatch structures. So I'm not going to develop jit for Mlisp-0.7. Instead I'm using the latest Mlisp-0.6 lisp which I'll call Nlisp-0.4 to develop jit on. This jumping between lisp versions might seem messy, but there's still too much bugs (and complexity) in the continuation/gc part of the current Mlisp-0.7 for me to develop jit on.

Currently, the opcode tracing in Nlisp-0.4 still has lots of problems. It may take a couple of weeks for me to get this working correctly. In the mean-time I've been trying to understand how libgccjit works in gccemacs. Since the jit is complex and does lots of optimizations this might be a good tool to look into. The performance gains using libgccjit on emacs is almost 4 times (not the 10x boost I was hoping for :-)).

  A good reference is the gccemacs wiki page.
     ___________                        _____________
    |_byte code_| --->  libgccjit ---> |_native code_|

August 16, 2021

The Plan for Mlisp JIT

Mlisp is currently a bytecode compiler. What we need to do is get Mlisp to translate the byte-code to machine-code, or "mcode" (versus "bcode"), on the fly. The Mlisp module make_code_string produces what is call a "byte code string" (it's also commonly referred to as a "code vector") for execution. It was called a code "string" because the Mlisp variable bcode was typed as a unsigned string, ("ucstr bcode;"), in Mlisp.

So in essence we want to change make_code_string to be a make_mcode_string. The final code object for execution would be a machine code string. This means we have to used the X86 assembler for our machine whcih runs the linux operating system. The assembler I'll use is gas. I don't know if all this will work yet because I've never done this before. But I'm laying out a plan to produce machine code vectors. I don't know how far I'll get.

August 13, 2021

JIT for Mlisp

The lisp implementations which are fast are SBCL, Clozure and Chez. I've never looked at the source code for these implementations yet because I don't have a background in JIT or just-in-time compilation. The Chicken Scheme implementation is also fast but does a static compilation from Scheme to C code. The source code for Scheme2c looked pretty messy to me, and JIT toolkits like libJIT seems as if it'll be too much work for me to try to use.

However, I feel that Mlisp might be able to run the CTAK benchmark in the speed range of Chez if it used a JIT to compile its functions or procedures. Mike Pall's luaJIT project was amazing since it boosted Lua's speed by an order of magnitude. I'm starting to feel that I should study or use the methodology of luaJIT to increase Mlisp's execution speed.

Mlisp is a compact bytecode implementation originally written by David Betz. The theoretical design philosoply is essentially very simple, but its implementation is complicated because its components parts like context execution (continuations), code evaluation and garbage collection are really tightly coupled together. But I feel there's essential beauty and capabilities in Mlisp which makes it deserve a JIT compiler for its procedures. So in the future months or years, I might be working towards this goal. I've not spent too much time on this project lately, but getting this done requires this. But I am interested in doing this.

August 5, 2021

I've hit a wall trying to work with the continuation dispatch table. So for now, I'm putting it aside. I'll probably not go back to using it; since for me, it's too complex in design. I'm continuing in the direction of using the "Context" data structure, and plain "Jmpbuf" to do the context switching.

July 22, 2021

mlisp-0.6q is depreciated and archived. nLisp (David Betz's xlisp-0.17 which did not have a bytecode compiler) uses the same basic structures as mLisp, however, is does not have continuations. The old mxLisp which grew out of xlisp-3 does a really remarkable job of implementing continuations. So the path ahead looks like I'll be trying to merge the execution context flavored of code from xlisp-2 with the continuations in xlisp-3. Currently, as has been in the past, I am sort of inspired by elegance of David Betz's implementation of continuations.

Maybe for the rest of this year, I'll be working on mlisp-0.7 which is a continuation of developing the old mxlisp.

  April 21, 2021

  mxlisp is being depreciated. I'm stopping work on mxLisp
  because I'm starting to understand its code better now. I can
  see the evolution of mLisp into mxLisp (David Betz's xscheme-0.28
  which evolved into xlisp-3.0) alot clearer now than I did a few
  years ago.

  Moreover, since I'm also seeing how nLisp (David Betz's xlisp-0.17
  which did not have a bytecode compiler) uses the same basic
  structures as mLisp, I've been able to understand better now
  how the bytecode compiler was constructed.

  I don't want to maintain 3 sets of lisps so I will focusing on
  nLisp which has a simpler code base, but still does not have
  continuations.  I think this is the best part and most challenging
  part of designing nLisp.  I hope this can happen soon, within the
  next year. "Stay tuned."