uLisp – Lisp for the Arduino | Hacker News Reader

uLisp – Lisp for the Arduino

ulisp.com

104 pointsweeber33 comments

This looks really neat! There was a story about Lisp at JPL that got me dreaming about embedded REPLs:

> The Remote Agent software, running on a custom port of Harlequin Common Lisp, flew aboard Deep Space 1 (DS1), the first mission of NASA's New Millennium program. Remote Agent controlled DS1 for two days in May of 1999. During that time we were able to debug and fix a race condition that had not shown up during ground testing. (Debugging a program running on a $100M piece of hardware that is 100 million miles away is an interesting experience. Having a read-eval-print loop running on the spacecraft proved invaluable in finding and fixing the problem.) http://www.flownet.com/gat/jpl-lisp.html

So often in embedded development I resort to things that make printf-style debugging look downright virtuous. ("If you reach some complicated runtime state, blink the LED thrice.") Having a REPL would let you poke around without the compile-flash-test cycle and have an actual conversation with the hardware.

I have TinyScheme running on a STM32F415.

https://sc4.us/hsm/

I love TinyScheme. I love NaCl. This is wonderful!

Thanks. I have a few left from a limited production run that I'm selling for $55. Send me an email if you want one. I'm also going to be doing a kickstarter to raise money for a real production run.

Any BSD kernel drivers for this?

It's just a USB serial device, so if BSD supports those (and I can't imagine that it doesn't) then it will work. But I don't run BSD so I haven't tried it.

Though uLisp has tail-call optimization, if the C compiler doesn't, then the garbage collector needs stack in proportion to list length:

  void markobject (object *obj) {
    if (obj == NULL) return;
  
    object* arg = car(obj);
    if (marked(obj)) return;

    int type = obj->type;
    mark(obj);
  
    if (type != SYMBOL && type != NUMBER) { // cons
      markobject(arg);
      markobject(cdr(obj));   // <--- TAIL CALL!
    }
  }

It's simple enough to obj = cdr(obj) and wrap a loop around this.

Good suggestion!

By the way, you can't eliminate the need for a stack when traversing the cell graph (unless you give them parent pointers, thereby hiding the stack in the data).

That's why I wrote "in proportion to list length", not "tree structure depth" in general.

Above, we still have recursion when marking the arg = car(obj) value. However, Lisp lists tend to be greatly unbalanced in favor of growing in the cdr direction; that is why it helps to iterate on the cdr.

The AVR cpu at the core of the Arduino uses a (modified) Harvard architecture., which separates code from data memory. A key feature of lisp of that code IS data. How does uLisp bridge the contradiction?

It provides a Lisp interpreter written in C.

You can read the implementation... code:

http://www.ulisp.com/list?1BWZ

> A key feature of lisp of that code IS data.

I think this is an oversimplification. "Code is data" means several things:

1. Both use the same ASCII representation to humans (homoiconity)

2. Lisp Macros operate using data traversal functions

3. You can load and eval code on the fly

Really only #3 is invalidated under Arduino constraints. #1 is the source at rest and #2 is compile-time.

ulisp can load and evaluate Lisp code on the fly on the arduino.

3. is not invalidated under Arduino in a general sense. The split into "code memory" and "data memory" is only relevant to the meaning of "code" and "data" assigned by uC-level assembly. There's nothing stopping your code to reinterpret data as code. Consider: that's how interpreters and VMs are made :).

Moreover, 1-3 together are more than sum of its parts. The idea that "in Lisp code = data" doesn't mean that elsewhere it doesn't; code = data is a fundamental truth about the nature of information (that many other languages and their ecosystems did quite a lot of work to obscure). Lisp only makes exploiting that truth much easier than other languages.

Also, a nitpick. #2 is not "compile-time". Macros can and are expanded at what you'd call "run-time" as well. Generally, Lisp systems don't have "compile-time" and "run-time" you know from other languages; the split is usually read- / load- / compile- / run-time, with some other "times" sprinkled in (e.g. "macroexpansion-time"), and this split is not necessarily sequential - you can read/load/compile stuff in what would usually be called "runtime", and read/load/compile phases have full access to features of the running Lisp image, including changes you made previously - so, for example, code you're just compiling can, during its read-time, refer to variables you previously created at run-time and run computations on them.

Code IS data, that's a fundamental fact of reality, and not something mere chip architecture can invalidate. Separating "code memory from "data memory" only means you can't have bits from "data memory" flowing directly into the chip to be run. It doesn't prevent you from having some code in "code memory" that would translate the data into code, by e.g. means of flow control.

> It's also an ideal language for expressing complex ideas, such as [...] finding the shortest route on a map

So, I googled "Dijkstra's Algorithm in Lisp" and got this: http://richardsherriff.com/?p=233

Now, I'm no lisp expert, so I can't judge whether the author of this code actually knows what they're doing, but I know for sure that in an imperative language the implementation of the algorithm is much more concise and understandable.

I have concluded from my observations that claims of Lisp being "easier", "ideal for learning fundamental programming concepts" and "more expressive" are exaggerated.

Congratulations, you have found the most ugly Lisp code ever.

> so I can't judge whether the author of this code actually knows what they're doing

Not really. He can't even format the code.

For example from that blog post:

    (defun return_highers_helper (list element result)

    (cond

    ((null list) result)

    ((equalp (first element) (first (first list)))

    (cond

    ((< (rest element) (rest(car list))) (return_highers_helper (cdr list) element (cons (car list) result)))

    (t (return_highers_helper (cdr list) element result))

    ))

    (t (return_highers_helper (cdr list) element result))

    ))

This would be written usually as:

    (defun %return-highers (element list)
      (remove-if-not (lambda (item)
                       (and (equalp (car element) (car item))
                            (<      (cdr element) (cdr item))))
                     list))

There are better comparisons here. The Lisp version is pretty nice compared to most of the imperative versions:

http://rosettacode.org/wiki/Dijkstra%27s_algorithm

>in an imperative language

Lisp is capable of imperative programming.

I would say multi-paradigm instead.

You might want to look at something like:

https://github.com/gwkkwg/cl-graph/blob/master/dev/graph-alg...

or perhaps: https://planet.racket-lang.org/package-source/jaymccarthy/di...

I was a little surprised to not find any direct graph algorithms at rosetta code[1], but for showing off somewhat similar code, this might be of interest:

http://rosettacode.org/wiki/Longest_common_subsequence#Commo...

I don't really think common lisp is a great beginning language, compared to, say, python or ruby - although Racket Scheme is pretty nice. I did for example come across this introduction to A * that uses Python for the code examples:

http://www.redblobgames.com/pathfinding/a-star/introduction....

As for introduction to new programmers, Racket's tutorial is kind of nice, jumping right in to do some simple graphics with an embedded DSL:

https://docs.racket-lang.org/quick/

[1] WillPostForFood obviously out-searched me here, finding: http://rosettacode.org/wiki/Dijkstra%27s_algorithm Not sure how I managed to not find it - perhaps trusting search rather than trying to use the site-index would've helped...

1. Find bad possibly code written in a language (by possibly a starting student).

2. Use it to invalidate any arbitrary claim X about the language.

3. Profit?

uLisp includes a mark and sweep garbage collector. Garbage collection takes under 1 msec on an Arduino Uno or under 3 msec on an Arduino Mega 2560.

I wonder how predictable and controllable that is. Adding GC to what is likely to be a real-time device seems like a potential showstopper. But if the numbers can be a bit more firm, or if the application can receive alerts on pause / resume, that might not be such a big deal.

As I said in another thread recently, garbage collectors don't have to be of the stop-the-world, non-deterministic kind. It's perfectly possible to have real-time garbage collection [1], and the language I commonly work with supports soft real-time use with the default GC [2]. I'm no expert on garbage collection techniques, but what I have picked up is that most of the challenge lies in timing of the collections (when to run the GC) and how to deal with things like cycles.

[1] http://michaelrbernste.in/2013/06/03/real-time-garbage-colle...

[2] http://nim-lang.org/docs/gc.html

Yes, but the language chosen implied to me that it's using a stop-the-world approach.

I've confirmed this by looking at the (surprisingly readable and small) code: http://www.ulisp.com/list?1BWZ

Also, it looks like the algorithm is mostly deterministic, so that's good from a real-time standpoint. And it only runs if memory is about to be exhausted, so if the application ensured that it stayed within the Arduino's memory budget, it's essentially a no-op.

In a real-time application that has to run on constrained hardware, the most interesting use of a GC language is as part of a compilation/configuration process for the actual runtime code or assets.

This is the approach of e.g. Naughty Dog's old GOAL language: it isn't doing Lispy things in the engine code, so much as using Lisp as a very powerful macroassembler. This approach is potentially advantageous over having a batch process to compile and upload to the device since it presents some important groundwork for doing "live editing". The performance of the shipped application is effectively unlimited, since the user code has so much control over the resulting output.

The main downside is that the resulting app isn't designed for portability, being so oriented towards the machine code rather than an abstract layer: Getting the portability and the live-editing functionality and the performance is a considerably harder problem to visualize, but production C++ game engines are doing it now.

Lisp for Arduino sounds great. The C programming barrier has kept me from tinkering with Arduino. Does this give you access to arduino shields/expansion boards (wifi/gps/screens), or will that be dependent on device drivers?

Check out esp8266/nodemcu. They can be programmed in lua or micropython (or arduino ide). Not as much of an ecosystem/community, but growing. Includes wifi on-chip, and dirt cheap.

There's also a Lisp for ESP8266 under development :). See:

https://github.com/yesco/esp-lisp

Nice! This reminds me of my tiny Lisp Machine project: https://aaron-fischer.net/tdn https://translate.google.com/translate?hl=en&sl=de&tl=en&u=h...

This reminds me of muLISP [0].

[0]: https://de.wikipedia.org/wiki/MuLISP

muLISP is much larger and needs a much more capable system. 16bit muLISP officially requires 512 kbyte RAM.

ulisp runs with 2 kbyte RAM.

Clojure is my favorite language, and I'd probably like scheme just as well if it had the easy to use (yet advanced) Data structures of clojure. I just can't seem to get my brain to mesh with Common Lisp yet, but I periodically dip my toes to test the water.

That said, I just don't get statements like:

"It's also an ideal language for expressing complex ideas, such as teaching a robot to solve mazes or finding the shortest route on a map." More ideal than C, sure. But I don't see the huge advantage over other high level languages.

Reply on news.ycombinator.com