Extending uLisp with Common Lisp functions


#1

Inevitably due to size limitations there are many useful functions in Common Lisp that are not provided in uLisp. If one of your favourite functions is missing, this page shows how to write the most popular ones in uLisp.

You can make sure that the functions you want are always available in your copy of uLisp using the Lisp Library feature.

Note that in many cases these aren’t as fully featured as the full Common Lisp versions. For example:

  • The sequence functions only support lists.
  • Keyword arguments such as :key and :test aren’t supported.
  • There’s reduced error checking.

I’d welcome suggestions for additions, or improvements to these.

count

Counts the number of items eq to x in lst.

(defun count (x lst)
  (if (null lst) 0
    (+ (if (eq x (car lst)) 1 0) (count x (cdr lst)))))

count-if

Counts the number of items in lst for which tst is true.

(defun count-if (tst lst)
  (if (null lst) 0
    (+ (if (funcall tst (car lst)) 1 0) (count-if tst (cdr lst)))))

count-if-not

Counts the number of items in lst for which tst is false.

(defun count-if-not (tst lst)
  (if (null lst) 0
    (+ (if (funcall tst (car lst)) 0 1) (count-if-not tst (cdr lst)))))

eql

In uLisp eq and eql are equivalent.

(defvar eql eq)

equal

Tests whether two objects or strings are equal, or have the same list structure.

(defun equal (x y)
  (cond
   ((and (stringp x) (stringp y)) (string= x y))
   ((and (consp x) (consp y)) (and (equal (car x) (car y)) (equal (cdr x) (cdr y))))
   (t (eq x y))))

every

Returns t if tst is true for every item in lst, or returns nil on the first false item.

(defun every (tst lst)
  (if (null lst) t
    (and (funcall tst (car lst)) (every tst (cdr lst)))))

find

Returns x if x is in lst, or nil otherwise.

(defun find (x lst) (car (member x lst)))

find-if

Returns the first item for which tst is true in lst, or nil otherwise.

(defun find-if (tst lst)
  (cond
   ((null lst) nil)
   ((funcall tst (car lst)) (car lst))
   (t (find-if tst (cdr lst)))))

find-if-not

Returns the first item for which tst is false in lst, or nil otherwise.

(defun find-if-not (tst lst)
  (cond
   ((null lst) nil)
   ((not (funcall tst (car lst))) (car lst))
   (t (find-if-not tst (cdr lst)))))

fourth

Returns the fourth item in a list.

(defun fourth (lst) (car (cdddr lst)))

identity

Simply returns its argument.

(defun identity (x) x)

last

Returns the last cdr of lst.

(defun last (lst)
 (if (null (cdr lst)) lst
   (last (cdr lst))))

mapl

Applies fn to successive cdrs of lst, and returns lst.

(defun mapl (fn lst)
  (mapl2 fn lst)
  lst)

(defun mapl2 (fn lst)
  (cond
   ((null lst) nil)
   (t (funcall fn lst)
      (mapl2 fn (cdr lst)))))

maplist

Applies fn to successive cdrs of lst, and returns a list of the results.

(defun maplist (fn lst)
  (if (null lst) nil
   (cons (funcall fn lst) (maplist fn (cdr lst)))))

nconc

Destructively appends its arguments together, which must be lists.

(defun nconc (&rest ls)
  (mapcan #'(lambda (x) x) ls))

nthcdr

Returns the nth cdr of lst.

(defun nthcdr (n lst)
  (if (zerop n) lst
    (nthcdr (1- n) (cdr lst))))

position

Returns the position of the first x in lst, or nil if it’s not found.

(defun position (x lst &optional (n 0))
  (cond
   ((null lst) nil)
   ((eq x (car lst)) n)
   (t (position x (cdr lst) (1+ n)))))

position-if

Returns the position of the first item in lst for which tst is true, or nil if none is found.

(defun position-if (tst lst &optional (n 0))
  (cond
   ((null lst) nil)
   ((funcall tst (car lst)) n)
   (t (position-if tst (cdr lst) (1+ n)))))

position-if-not

Returns the position of the first item in lst for which tst is false, or nil if none is found.

(defun position-if-not (tst lst &optional (n 0))
  (cond
   ((null lst) nil)
   ((not (funcall tst (car lst))) n)
   (t (position-if-not tst (cdr lst) (1+ n)))))

reduce

Returns the result of applying fn to successive pairs of items from lst.

(defun reduce (fn lst)
  (if (null (cdr lst)) (car lst)
    (funcall fn (car lst) (reduce fn (cdr lst)))))

remove

Removes all occurrences of x from lst.

(defun remove (x lst)
  (mapcan #'(lambda (y) (unless (eq x y) (list y))) lst))

remove-if

Removes all items from lst for which tst is true.

(defun remove-if (tst lst)
  (mapcan #'(lambda (x) (unless (funcall tst x) (list x))) lst))

remove-if-not

Removes all items from lst for which tst is false.

(defun remove-if-not (tst lst)
  (mapcan #'(lambda (x) (when (funcall tst x) (list x))) lst))

subseq (for lists)

Returns the subsequence of lst from item n to item m-1.

(defun subseq* (lst n m)
  (cond
   ((> n 0) (subseq* (cdr lst) (1- n) (1- m)))
   ((zerop m) nil)
   (t (cons (car lst) (subseq* (cdr lst) 0 (1- m))))))

third

Returns the third item in a list.

(defvar third caddr)

Thanks to Max-Gerd Retzlaff for inspiring me to provide this.


#2

It is for this reason that I actually LIKE uLisp… It still has the elegance of Scheme. And everybody has usually his own “bag of functions” he carries from project to project. (E.g. I have something like “take-first n lis” to take the first n elements of a list, etc.)


#3

This is true.

However, I wonder if perhaps they shouldn’t be.

Specifically, uLisp’s eq implements the semantics of Common Lisp’s eql. In Common Lisp, eq is not required to be true of numbers of equal value. In SBCL, (eq 5/4 5/4) returns NIL. So does (eq (1+ most-positive-fixnum) (1+ most-positive-fixnum)). The language specification even specifically notes that (eq 3 3) may be either true or false.

Moreover, the only reason symbols are generally eq is because the reader automatically interns them - and although the mechanism isn’t the same, so does uLisp’s reader. It is not possible, from inside the uLisp runtime, to force the creation of two symbols that aren’t the same object in memory.

In that context, the Common Lisp eq provides a low-level capability that could be valuable if it ever becomes possible to implement more of uLisp in itself.


#4

Personally, I would have preferred Scheme but that’s what I “grew up on” wrt LISP.

As for the CL functions… I think I would have written them iteratively (er… tail recursively)
instead of recursively but, lately, that’s how I’ve been writing things. Yeah, that can be tougher
to do and a bit more “obfuscative” though.


#5

If it becomes useful in the future we can add separate eql and eq to uLisp.


#6

For convenience, here’s a file containing all these extensions to uLisp in a format suitable for adding as a Lisp Library:

LispLibrary.h

Since the Lisp Library is stored in program memory, adding it has no impact on the workspace or performance of uLisp until you load the definitions you want, as described below.

To add this to your copy of uLisp

  • Save this file as LispLibrary.h.

  • Put this in the same Arduino project folder as the uLisp source file.

  • Comment out the definition of LispLibrary[] at the start of the uLisp source:

    // Lisp Library
    // const char LispLibrary[] PROGMEM = "";
    
  • Add a reference to the LispLibrary.h file in the main uLisp source file by uncommenting the line:

    #include "LispLibrary.h"
    
  • Compile and upload uLisp to your board.

To list the symbols in the Lisp Library:

Give the command:

(list-library)

To load a single definition

You can load definitions only when you need them, to minimise the amount of workspace used, by giving a command such as:

(require 'count)

To load all the definitions

You can load all the functions and variables defined in the Lisp Library at startup by uncommenting the #define:

#define lisplibrary

Now you can see that all the definitions have been added to your workspace by doing:

(pprintall)

uLisp RISC 3.5 assembler crash
#7

Can you “overwrite” the definitions? That is, can you, after having loaded them with require, again “unload” them by e.g. re-defining them?

If indeed yes, it could be used to implement a sort of “overlay-like” solution, where you program only loads that what it needs “right now” at runtime, “emptying” again the definitions after usage and reloading the functions as needed again, etc.


#8

Yes. You can also just makunbound them.