multithreaded uLisp

[dragoncoder047]

I had another idea that would require editing the uLisp source (i.e. not an extension): making the multithreading feature of the esp32's FreeRTOS available to uLisp. I wish it was also available on Teensy too but there aren't any good libraries for that. You could (ab)use setjmp()/longjmp() to switch contexts but I'm not sure how well that would work.

To be able to preserve the atomic nature of garbage collections, the garbage collector can't call yield() and must have some way to mark all the running threads.

The changes would look something like this

typedef struct {
  jmp_buf top_handler;
  jmp_buf* current_handler;
  uint16_t flags;
  object* code;
  object* env;
  object* send_queue;
  object** send_tail;
  object* recv_queue;
  object** recv_tail;
  TaskHandle_t handle;
  bool running;
} task_locals;

#define setflag(locals, flag) ((locals)->flags |= (1 << (flag)))
#define clrflag(locals, flag) ((locals)->flags &= ~(1 << (flag)))
#define tstflag(locals, flag) ((locals)->flags & (1 << (flag)))

// error() and error2() and related functions take first parameter task_locals* to get right jmp_buf

#define MAX_THREADS 64
task_locals uLisp_Tasks[MAX_THREADS];

typedef object* (*fn_ptr_type)(task_locals*, object*, object*);

void thread_fun (void* arg) {
  task_locals* task = (task_locals*)arg;
  eval(task->code, task->env);
  task->running = false;
  vTaskDelete(task->handle);
}

object* fn_spawn (task_locals* my_task, object* args, object* env) {
  int tid;
  for (tid = 0; tid < MAX_TASKS; tid++) {
    if (uLisp_Tasks[tid].running == false) break;
  }
  if (tid = MAX_TASKS) error2(my_task, PSTR("too many tasks"));
  task_locals* new_task = &uLisp_Tasks[tid];
  new_task->flags = my_task->flags;
  new_task->code = first(args);
  new_task->env = NULL;
  new_task->current_handler = &new_task->top_handler;
  new_task->env = NULL; // or env to inherit variables
  new_task->send_queue = NULL;
  new_task->send_tail = NULL;
  new_task->recv_queue = NULL;
  new_task->recv_tail = NULL;
  new_task->running = true;
  xTaskCreate(thread_fun, "uLisp-spawn", 10000, (void*)new_task, 1, &new_task->handle);
  return number(tid);
}

And then any of the functions that refer to global variables, could instead look in the

Then you could implement functions like (spawn), (send), (receive), and (kill) for threads to be started and stopped and for them to communicate between each other.

[technoblogy]

That sounds an exciting idea. Are you sure it will be possible to make uLisp multithreaded?

I'm not sure I would want to adopt this for the standard version of uLisp, because I don't want to start having features that are exclusive to one platform. However, as I said for your other suggestion, if you would like to do a FreeRTOS fork of uLisp I'd be very interested to try it out, and promote it on the forum.

[dragoncoder047]

I already did find that someone on the forum was able to run uLisp in its own freeRTOS task (http://forum.ulisp.com/t/ulisp-as-freertos-task/1126), but that was still only one task; the other tasks have to be done in C. TBH I think as long as you keep all of the uLisp tasks pinned to the same core (on 2-core ESPs), then because two tasks can't run at the same time on the same core, there won't be any garbage collector corruptions as long as it can mark all the tasks.

I do want to try out freeRTOS tasks, and honestly I think it would be a good exercise to implement a longjmp() based task scheduler, with only minor assembly edits, so it can be portable to most, if not all platforms, not just ESP.

Unfortunately it's AP test season, and I have two, so I won't be able to test this anytime soon.

[technoblogy]

OK, there's no urgency. I hope your AP tests go well!

[dragoncoder047]

I got to thinking about this a little more lately and I don't actually think that any C code changes would be necessary. The way it would work is that there would be a function/macro that would transform a standard lambda body into a coroutine by adding a parameter called yield, which would be the current continuation and everything would use continuation-passing style to yield between virtual threads.

I'm not well-versed on continuation-passing style, but from what I've read about it it seems like it is what is needed here. I assume that someone more-well-versed in Lisp would know about how this kind of stuff is actually pulled off or if it is even possible. Just an idea.

[technoblogy]

The problem is that the routines in uLisp aren't currently written to be reentrant. There are global variables, such as Context. If a second thread started executing eval() while the main thread was executing it, the values of Context would get muddled up. All the variables that are currently global would have to be rewritten to be on the stack, or passed as parameters.

Another problem is garbage collection. I'm not sure what would happen if one thread invoked a garbage collection while a second thread was executing, or worse, what would happen if two threads both invoked garbage collection at the same time!

[dragoncoder047]

Well, that would be the problem inherent with the multiple-FreeRTOS-threads approach. The continuation-passing approach still only uses one thread and AFAIK it can be done in pure Lisp, so it wouldn't need any sort of reentrant routines on the C API side. I'm not sure whether infinite-continuations would blow up the stack or not, but considering that continuation-passing is common practice in Scheme and both uLisp and all R5RS-compliant implementations of Scheme have tail-call optimization (meaning looping via infinite recursion is possible), so it may not affect much.

[technoblogy]

Hmmm... interesting. I'll need to think about that.

[dragoncoder047]

Wikipedia has some Scheme code that implements cooperative multitasking here. Once uLisp has macros I think that would make it a lot easier to port.

[dragoncoder047]

Wikipedia has some Scheme code that implements cooperative multitasking here.

On a second look, while macros would make it easier, it relies on (call/cc) to actually implement the task switching, so it would be just as difficult as using freeRTOS tasks (total rewrite of uLisp) to actually enable first-class continuations -- and Common Lisp doesn't have built-in continuations, anyway, it's a Scheme thing, so it would always be an extension to uLisp. And the only way for (call/cc) to be implemented using a single closure and not in C is if there is a continuation-passing-style transformer already there, which again ulisp does not, and probably never will have.

But to make it easier to make such extensions possible to causal hackers like me, I think adding a third void* parameter to all the functions to be used for some thing like this would help. E.g. this change + consequenses:

-typedef object *(*fn_ptr_type)(object *, object *);
+typedef object *(*fn_ptr_type)(object *, object *, void *);

In stock uLisp it would do absolutely nothing but be passed around to the other functions (and would mostly be NULL), but an extension could make use of it.

I'm busy applying to universities right now, but if I get a free moment here and there I'm going to try to add it into my fork of ulisp-builder.

[technoblogy]

Great! And good luck with the university applications.