I'm getting my feet wet with defpackage
in Lisp and got off to an ignominious start, namely a bug I can't begin to understand.
The code below is an attempt to create a sublanguage to perform infix operations on vectors. I'd like to use this for a project involving some linear algebra.
The 'meat' of my code is parse-infix
. This function finds the operator with the highest priority, calls apply-op
to replace said operator and its operands with operator (operand, operand)
and thus shrink the list, and iterates until the list contains only the result. Supported operators are the four rules, equality (which binds a result to a Lisp symbol), and vector concatenation.
Here's the code, warts and all:
(defpackage :infix
(:use :common-lisp)
(:export operator-list
operators
parse-infix
infix))
(in-package :infix)
(defun parse-input (a)
"Turns symbols into numbers as necessary while reading an expression"
(if (symbolp a) (symbol-value a) a))
;; Definition of structure containing data for one operator
(defmacro mapf (op type)
""
`(lambda (a b)
(map ,type #'(lambda (x y)
(funcall ,op x y)) (parse-input a) (parse-input b))))
(defstruct (operator
(:conc-name op-)
(:constructor op (sym &key (func (mapf sym 'vector)) priority associativity n-operands)))
sym ; Operator symbol
func ; Function to be applied to operands
priority ; Other operators attributes
(associativity 'left-to-right) ; Evaluation order for operators
; that appear more than once in a row
(n-operands 2)) ; Number of operands (NOT IMPLEMENTED)
(defmacro operator-list (&body ops)
"Produces an operator list from a list of operator structs."
`(mapcar #'(lambda (y) (apply #'op
(mapcar #'(lambda (x) (if (listp x) (eval x) x)) y))) ',ops))
(defparameter operators
(operator-list
(+ :priority 4)
(- :priority 4)
(* :priority 3)
(/ :priority 3)
(^ :priority 2 :func expt :associativity right-to-left)
(& :priority 2 :func (lambda (x y) (concatenate 'vector x y)))
(= :priority 10 :func (lambda (x y) (set (intern (string x)) y))))
"Default set of operators, which perform arithmetic operations on
vectors lengthwise. If one vector is shorter than the other, the result
is truncated.")
(defun apply-op (b)
"Reads a segment of a list of the format operand/operator/operand (in 3 consecutive
cells) and leaves operator (operand, operand) in a single cell."
(setf (car b) (funcall (op-func (caadr b))
(car b)
(caddr b))
(cdr b) (cdddr b)))
(defun parse-infix (b &key (operator-list operators))
"Parses an infix expression by calling apply-op repeatedly until the entire
expression is processed."
(let ((expr (mapcar #'(lambda (x)
(case (type-of x)
(symbol (or (member x operator-list :key #'op-sym) x))
(cons (parse-infix x))
(otherwise x))) b)))
(loop while (cdr expr) do
(apply-op (reduce #'(lambda (x y &aux (op1 (caadr x)) (op2 (caadr y)))
(if (or (< (op-priority op2) (op-priority op1))
(and (= (op-priority op1) (op-priority op2))
(eq (op-associativity op1) 'right-to-left))) y x))
(remove-if #'listp (mapcon #'list expr) :key #'caddr)))
finally (return (car expr)))))
(defmacro infix (&rest b)
"Wrapper to create lists for parse-infix"
`(parse-infix ',b))
And here's the snag. The functions seems to be working...
? (infix (#(2 3) + #(4 5)) * #(2 2))
#(12 16)
? (infix (#(100) & (#(2 3) + #(4 5)) * #(2 2))) ; '& is concatenation
#(200 12)
? (infix A = #(5 5) + #(10 10))
#(15 15)
? A
#(15 15)
... but when I leave the package, the concatenation (&) operator suddenly 'dies':
? (in-package :cl-user)
#<Package "COMMON-LISP-USER">
? (infix:infix A = #(5 5) + #(10 10))
#(15 15)
? (infix:infix (#(2 3) + #(4 5)) * #(2 2))
#(12 16)
? (infix:infix (#(100) & (#(2 3) + #(4 5)) * #(2 2)))
> Error: The value & is not of the expected type LIST.
> While executing: (:INTERNAL INFIX:PARSE-INFIX), in process listener(1).
> Type :POP to abort, :R for a list of available restarts.
> Type :? for other options.
1 >
I tried to trace the package's functions and noticed that, for whatever reason, '& ceases to be recognized as an operator when I leave the infix
package. I don't have the foggiest idea why this is the case. Any input is appreciated.
PS. As many probably noticed, all this is in Clozure Common Lisp.
&
is an internal symbol in your package.
You need to export it to fix the problem.
The same goes for ^
:
(defpackage :infix
(:use :common-lisp)
(:export #:operator-list
#:operators
#:parse-infix
#:infix
#:&
#:^))
When you type
(infix:infix (#(100) & (#(2 3) + #(4 5)) * #(2 2)))
while in the cl-user
package,
the symbols &
, +
, and *
are read as cl-user::&
,
cl:+
and cl:*
.
Note that the latter two are exported from the
common-lisp
package and thus
are also available in your infix
package:
(eq 'infix::+ 'cl-user::+)
==> T
(eq 'infix::+ 'cl-user::+)
==> T
However, the first one is different:
(eq 'infix::& 'cl-user::&)
==> NIL
find-all-symbols
is your
friend:
(find-all-symbols "+")
==> (+)
(find-all-symbols "*")
==> (*)
(find-all-symbols "&")
==> (INFIX::& CL-USER::&)
Note that I use uninterned symbols as the :export
arguments
in defpackage
-
so that they are not interned into CL-USER
by read
.