• ok, sorry, I was a little clickbaity

Masataro Asai

<note: “n” / “p” key to move forward / backward >

Me

• Automated Planning / Heuristic Graph Search (aka symbolic AI)
• Creating the future AI with Neural-Symbolic hybrid at IBM
• A somewhat competent Common Lisper

spng:ranking

About the Talk : Assortment of Tiny Little Ideas

• Goal: (blatantly) talk about the current limitation of the language

  and propose some prototypes

  • without sounding ignorant

    (i.e. try to avoid topics that are well known)

  • macro, package, namespace, type system, misc.

Part 1 : “Lisp macros are awesome!”

True, but it feels something is missing

The case of local macros in Iterate

Iterate: the lispier alternative to loop

• Has various local macros

  (iter (for i below 5)   ; <- local macro
        (for j = (1+ i))  ; <- local macro
        (print i))
      

• They cannot be implemented by macrolet/defmacro

  → because the iterate macro must detect =for= beforehand

Iterate as macrolet ?

Suppose a simplified version that supports only for

What iterate must do for for?

(iter (for i below 5)   ; <- detect these
      (for j = (1+ i))  ; <- detect these 
      (print j))

Can we implement for with a macrolet?

(defmacro iter (&body body)
  `(macrolet ((for (...) ...))
     ,@body))

• No: for in body are expanded after expanding iter

  → iter cannot receive information (e.g. loop variables)

  → The case of inter-macro communications

Current solution: Code walker

Iterate walks across the code body

• Standard macros are expanded (exposing the local macro inside)

  (defmacro for2 (&rest args) `(for ,@args))
  
  (iter (for2 i below 5)
        (print i))        ; works
      

• Surrounding macrolet’s are also expanded

  (macrolet ((for2 (&rest args) `(for ,@args)))
    (iter (for2 i below 5)
          (print i)))        ; works
      

  by passing &environment variable to macroexpand.

However, inner macrolet’s cause problems

(iter (macrolet ((for2 (&rest args) `(for ,@args)))
        (for2 i below 5))
      (print i))

WARNING: Iterate:
Iterate does not know how to handle the special form (MACROLET ...)

  The function FOR2 is undefined.
     [Condition of type UNDEFINED-FUNCTION]

• This cannot be done in ANSI CL

  → Requires CLtL2 augment-environement to shadow the outer binding

  → iterate does not use it – it has its own walker.

Sketch

(defun walk (form env)
  (let ((form (macroexpand form env)))
    (case (car form)
      ('tagbody ...)
      ...
      ('macrolet
       (destructuring-bind (bindings . body) (rest form)
         (walk `(progn ,@body) (sb-cltl2:augment-environment env :macro binding))))
      ...)))

(defmacro for (&rest args)
  (cerror 'for-found :args args)
  '(progn))

(defmacro iter (&body body &environment e)
  (let (metadata)
    (handler-bind ((for-found
                     (lambda (c)
                        (push-metadata c metadata) ; (1)
                        (continue c))))
       (let ((body (walk `(progn ,@body) e)))
         (wrap metadata body)))))                  ; (2)

But writing a code walker is dumb

• Every inter-macro communication requires its own code walker?
• hu.dwim.walker is not a solution (returns a CLOS object tree)
• Can be replaced by macroexpand-all

MACROEXPAND-ALL Sketch

(ql:quickload :trivial-macroexpand-all)
(use-package :trivial-macroexpand-all)

(defmacro for (&rest args)
  (cerror "ignore" 'for-found :args args)
  '(progn))

(defmacro iter (&body body &environment e)
  (let (metadata)
    (handler-bind ((for-found
                     (lambda (c)
                        (push c metadata)          ; (1)
                        (continue c))))
       (let ((body (macroexpand-all `(progn ,@body) e)))
         (wrap metadata body)))))                  ; (2)

• Can we generalize this intention further?

(Partially) Chainging the Macro Expansion Order

Whats the common pattern?
→ Nondeterministic expansion

(defmacro iter ( ... )
  (loop <expand further>
        (if <fail>
            <fix and retry>
            <return>)))

We propose compile-time continuation

(defmacro iter ( &body body &cont c )
  (loop (funcall c `(progn ,@body)) ; expand inner first
        (if <fail>
            <fix and retry>
            <return>)))

This can encupsulate the unspecified &environment structure

c is merely a closure

> https://github.com/guicho271828/recursive-macroexpansion

Normal order evaluation vs Applicative order evaluation

;; Assume + and * are primitives (normal form)
(defun 1+     (x) (+ 1 x))
(defun square (x) (* x x))

Part 2: package system, symbols and namespace

• Not about its complexity
• Not about package-inferred systems
• but about namespaces

The issue of the package system in CL:
→ cannot import the “feature” of each symbol

(in-package :numeric)
(defun square (x) (* x x))

(in-package :gui)
(defclass square (rectangle) ...)

(defpackage :library3 (:use :numeric :gui)) ; conflict!!

Their features never overwrap → no need for a conflict (but they do in CL)

The case of Trivia’s fail/next macro

trivia pattern matching library

(match (list 1 2)
  ((list x y)
   (if (= y (* 2 x))
       (print :success!)
       (trivia.fail:fail))) ; <- separated

  ...next clauses...)

to avoid frequent conflicts:

(defpackage test (:use :cl :trivia :fiveam))
(test mytest
  (fail "reason"))

The case of Trivia’s next macro

trivia pattern matching library has a next macro

(match arg
  ((list x y)
   (if (= y (* 2 x))
       (print :success!)
       (trivia.next:next))) ; <- separated

  ((list x y)
   (print :something-else)))

to avoid frequent conflicts with iterate:

(iter (initially (setq i 0))
      (for i next (if (> i 10) (terminate) (incf i))
      (print i))

Their features never overwrap → no need for a conflict (but they do in CL)

• What are “features”? → The key notion missing here is namespace

Background : Namespace
(it is orthogonal to packages)

Common Lisp is Lisp 2 : variable and function namespaces. … Is it?

(defun fn (list)
  (list list list list))

• No, CL is Lisp-N : same symbol can mean more than 2 things

  (defun fn (x) x)
  (defclass fn () ())
  (defvar fn)
  (cffi:define-foreign-library fn ...)
  (trivia:defpattern fn ...)
  (clack:defroute fn ...)
  (asdf:defsystem fn ...)
      

Background : Namespace (cont.)

Every namespace has accessors, conditions, boundp(, binder)

namespace	accessor	unbound condition	boundp	binding
class	find-class	SIMPLE-ERROR	n/a	n/a
function	symbol-function	UNDEFINED-FUNCTION	fboundp	flet,labels
value	symbol-value	UNBOUND-VARIABLE	boundp	let

Some namespaces in CL can be said to overlap with each other:

• class — with type, condition and struct

  function — with macro-function and generic-function

  value — with symbol-macro

Background : Macro DEFINE-NAMESPACE

https://github.com/guicho271828/lisp-namespace

(define-namespace name &optional (expected-type t) (binding t) (documentation ""))

For a namespace X, it defines:

• #'symbol-x, #'(setf symbol-x), #'x-boundp, UNBOUND-X

  Implementation: Simple hash table.

  Namespaces have its own namespace named namespace.

• Integrated into cl:documentation interface (and appears on C-c C-d)

  (setf (documentation 'mysym 'x) "doc for mysym")
      

  i.e. CL already has the notion of (non-extensible) namespace

Proposed package system:

Symbol itself is global (hashtable from a string to a symbol object)

Import/export/conflict : performed per each namespace

Shadowing : per namespace (or for all namespaces, for convenience)

(export 'square 'numeric 'function)
(export 'square 'gui     'class)
(defpackage mypackage (:use :cl :numeric :gui))
(make-instance 'square) ; -> #<STANDARD-CLASS SQUARE>
(square 5.0)            ; -> 25.0
(eq 'mypackage:square 'numeric:square) ; -> T
(eq 'mypackage:square 'gui:square)     ; -> T

namespace accessor has additional package arguments

(make-instance 'square) vs (make-instance 'pkg2:square)
                        ↓
(make-instance 'square) vs (make-instance (find-class 'square 'pkg2))

→ compensation, but is required less often

The case of Trivia’s next macro

trivia’s next macro and iterate’s next (keyword used in its macro) are orthogonal

Then iterate’s next

(match arg
  ((list x y)
   (if (= y (* 2 x))
       (print :success!)
       (trivia.next:next))) ; <- separated

  ((list x y)
   (print :something-else)))

to avoid frequent conflicts with iterate:

(iter (initially (setq i 0))
      (for i next (if (> i 10) (terminate) (incf i))
      (print i))

Part 3: Type System

(I think probably the time has run out)

I really want a parameteric type in CL

The case of matrix GEMM

(defun gemm (a b c)
  (declare ((array ?t (?d1 ?d2)) a))
  (declare ((array ?t (?d2 ?d3)) b))
  (declare ((array ?t (?d1 ?d3)) c))
  ...)

I want it to signal a compile-time/run-time error when

• a, b, c are of different upgraded-array-element-types
• dimensions do not match

This and recursive type is an orthogonal issue

(it can happen without recursive type)

So I made one

https://github.com/numcl/gtype

(defun gemm (a b c)
  (resolve  ; <--------- ugly!
    (declare (gtype (array ?t (?n1 ?n2)) a)
             (gtype (array ?t (?n2 ?n3)) b)
             (gtype (array ?t (?n1 ?n3)) c))
    (dotimes (i ?n1)
      (dotimes (j ?n2)
        (dotimes (k ?n3)
          (setf (aref c i k) (* (aref a i j) (aref b j k))))))))

Implemented through cltl2:declaration-information

Hack: Does not perform compile-time checking

→ Impossible inside CL, needs a framework to extend the compiler

→ I wish to develop a lisp that does this natively

The choice of aesthetics:

Historic prolog style : (array ?t (?n1 ?n2))

C++ style : (array <T> (<n1> <n2>))

Which do you like?

Part 4: Equality functions

(eq "string" "string") ; -> NIL
(eql "string" "string") ; -> NIL
(equal "string" "string") ; -> T
(equalp "string" "string") ; -> T
(string= "string" "string") ; -> T
(string-equal "string" "string") ; -> T

LIL (as I understand)

(defgeneric eq (<interface> a b))
(defmethod eq ((<interface> <case-insensitive-string>) (a string) (b string)))

but the resulting code requires an explicit mention to the interface

(defun myfunc (<i> a b c d e)
  (and (eq      <i> a b)
       (less    <i> b c)
       (greater <i> c d)
       (!=      <i> d e)))

Proposed alternative: role declaration

(declare (type string a b))
(declare (role case-insensitive-string a b))
(= a b)

• Orthogonal to a casting (like C++ does); Not this:

  (= (coerce a 'case-insensitive-string)
     (coerce b 'case-insensitive-string))
      

• Operation is defined by the role lexically assigned to variables

  (declare (type string a b c d))
  (declare (role case-insensitive-string a b c d))
  (and (= a b) (/= b c) (or (= b d) (= b d)))
      

Proposed alternative: role declaration

Can also be dynamically altered; similar to LIL

(defun equal-with-runtime-role (a b role)
  (with-role ((a role) (b role))
    (= a b)))

However, most usage will have the compiler support

(in combination with types)

Closing remarks

Personally I feel like moving away from Common Lisp

– but NOT to non-lisp! The Time is right for me:

• I have a (virtual) freedom of research
• The dawn of neural-symbolic AI is approaching
• We need a language that has a large enough feature set for helping it
• Not python: lacks low-level speed and optional type checks (~ SBCL)
• Not CL: hard to modify the core of its compiler

Personal opinion: Lisp must address more acadmic needs

• symbolic optimization solvers (SAT, CSP, Prolog, MILP) as stdlib

  type checking / compiler built on these standardized frameworks

  https://github.com/guicho271828/cl-maxsat, cl-sat, cl-prolog2, cl-smt

• connectionist optimization solvers (NN, tensors) as stdlib

  https://github.com/numcl/numcl , gtype, specialized-function (Julia-like dispatch for CL)

Conclusion

Showcased tiny ideas that could be useful for implementing non-CL lisp

• compile-time continuation
• namespace
• type-based constraints
• role declarations
• Argued that we need something new