Please help my head get around 'deftype'

Hi all,

In general, I'm comfortable with the dynamic typing of CL 'except' in a case where I want to lock down interfaces to a package. That is, beyond exporting only the functions I want exported from the package, I want to specify the types of their arguments in the most precise way possible to make the code explicit for users of the package.

It looks like deftype can be used to build up type abstractions but I'm really having a heck of a time with it. The Graham book only briefly touches the topic. There are two main things I'm trying to define.

1. A type 'somthing-list' that represents a simple list where all elements of that list are of type something.

2. A way to define a function signature type. For instance, a type that represents the class of all functions that take two number arguments.

Are either of these even possible using deftype? Maybe there's an entirely different, more Lispy, way of achieving the same sort of package encapsulation effect? Any examples or suggestions would be greatly appreciated.

Thanks in advance!

I'm afraid this is an area where CL is really weak. I don't believe there's a way to define the types you want -- and I don't know what CL would do with them if you did. You certainly can describe them in your interface documentation; after that, your best bet is to check the supplied arguments at runtime, perhaps with CHECK-TYPE. But you won't be able to check that a supplied function takes two numbers, or even that it takes two arguments; you'll just have to call it and take your chances. It's the Lisp way: don't worry, be happy

You can do #1 with a SATISFIES type. You create a predicate function, say something-list-p, then the type would be (satisfies something-list-p).

Unfortunately, it probably wouldn't help the compiler and it has to run the function each time you want to check an object for that type...

Maybe I'm not following you, but why do you care about typing? From your original posting, it sounds like you just need it for documentation purposes, to communicate with users of your API. If that's true, then I'd suggest that you just use well-written doc strings and be done with it. Typically, typing is used in Lisp to try to make things really easy on the compiler such that it can generate better code, not for documentation purposes. If you aren't trying to make a particular bit of code go faster, I'd just concentrate on doc strings and not on types. If you are trying to make things go faster, then DEFTYPE might help you reduce the number of characters you have to type (no pun intended) when you write our your type declarations. But those should really only be necessary around inner loops, etc. And as people have already said, there are limitations to what can be expressed with the Lisp type system, though those limits are at least as large as what you can do with many other statically typed languages (e.g. C). For instance, developing a type like "all numbers between 17 and 32" or "all fixnums" or "a string or a character" are pretty easy. Things like "all prime numbers less than 4 billion" would be hard.

Summary: try to figure out whether you really need to do that. If not, then don't. If you still do, then look at declarations and DEFTYPE.

findinglisp wrote:Maybe I'm not following you, but why do you care about typing? From your original posting, it sounds like you just need it for documentation purposes, to communicate with users of your API. If that's true, then I'd suggest that you just use well-written doc strings and be done with it.

It is true that this serves as a sort of documentation. However, it goes beyond that because documentation isn't part of the runtime system. A person may or may not read the documentation. Even if they do, they may still pass something unintended into the package that doesn't generate problems immediately but rather down the road during runtime at some point, making it difficult for them to determine a root cause. The motivation for typing interface points between packages is so that you can make some solid statement, enforced by the system, regarding what you define as valid input. If the interfaces are open to any input then you've effectively created a situation where you must anticipate any possible input a user of your package may provide. By typing your interfaces, you're not letting them pass in things that you don't anticipate and hence increase your code's robustness. Granted, this doesn't always matter but it does sometimes.

As a little background, I come from mainly a C++/COM environment building large applications. So some of my ideas I'm sure carry over from that. However, for the past year I've worked mainly with Lua, an interactive scripting language with functional features and dynamic typing (I've been learning Lisp in hopes that I could get the best of both worlds, and then some). A significant percentage of defects we've encountered in this code base arises from developers calling interface points, where the arguments are of dynamic type, with an unpredicted 'type' of argument. There are plenty of cases where the documentation is read but not well understood.

Anyway, I really hope I don't spawn a type system war (pointless) as that isn't my intention at all. There's a place for many different kinds of type systems. I just wish they'd bend to my will

Hi, have you looked at Qi? It has a static typing system (and has some nice features like pattern matching).

Exolon wrote:Hi, have you looked at Qi? It has a static typing system (and has some nice features like pattern matching).

A bit. Qi was mentioned in another thread. Having just got my head around Lisp fundamentals, I'm a bit reluctant to stack another language on top but it may very well be the way to go. Thanks all!

I'm in the exact same boat, and am going to put off even investigating Qi properly until I've done a few mini-projects in common-or-garden CL first

tlareywi wrote:It is true that this serves as a sort of documentation. However, it goes beyond that because documentation isn't part of the runtime system. A person may or may not read the documentation. Even if they do, they may still pass something unintended into the package that doesn't generate problems immediately but rather down the road during runtime at some point, making it difficult for them to determine a root cause. The motivation for typing interface points between packages is so that you can make some solid statement, enforced by the system, regarding what you define as valid input. If the interfaces are open to any input then you've effectively created a situation where you must anticipate any possible input a user of your package may provide. By typing your interfaces, you're not letting them pass in things that you don't anticipate and hence increase your code's robustness. Granted, this doesn't always matter but it does sometimes.

So, I'm still not sure what you are after, exactly:

• Documentation
• API enforcement
• Performance optimization

If you want the first, then doc strings are fine. And doc strings are available in the runtime system. This is a big difference from other static languages or things like Javadoc that use special comment formats. Lisp doc strings are stored with the functions and variables that they document. Type "(DESCRIBE 'SYMBOL)" in a typical Lisp where SYMBOL is one of your symbols with a known doc string and notice the output. At least with SBCL, it's quite robust. Note that often the base CL API is compiled with doc strings removed to save space. We don't need the CLHS repeated online. The point is, doc strings work quite well to document APIs. There are even a few packages out there to automatically generate other forms of API documentation (e.g. HTML) from doc strings.

If you're interested in doing the second option, you can always check types with your own code. You don't need to declare anything to do so. In other words, you can write something like:

(defun foo (bar)
  (unless (integerp bar)
    (error "BAR must be an integer"))
  ...)

Finally, if you want performance optimization, that's when it really benefits you to declare types.

As a little background, I come from mainly a C++/COM environment building large applications. So some of my ideas I'm sure carry over from that. However, for the past year I've worked mainly with Lua, an interactive scripting language with functional features and dynamic typing (I've been learning Lisp in hopes that I could get the best of both worlds, and then some). A significant percentage of defects we've encountered in this code base arises from developers calling interface points, where the arguments are of dynamic type, with an unpredicted 'type' of argument. There are plenty of cases where the documentation is read but not well understood.

So I still don't see the benefit. In a C++/COM world, type mismatches cause big problems because operations are not type-checked. In Lisp, you can't accidentally add a string and an integer. When you try, you'll generate a condition and be dropped into the debugger. At that point you typically have a full stack trace and can quickly identify where things went wrong. If the same thing happens in C++/COM, you just get a mysterious crash and if you're lucky a core file to debug after the fact. If you're really up tight, you could type check every parameter in an API right at the first entry to the API, but I'm really not sure that's too useful in practice. If it was such a big problem, you'd see it being done in Lisp code all over the place, and that just isn't the case.

Anyway, I really hope I don't spawn a type system war (pointless) as that isn't my intention at all. There's a place for many different kinds of type systems. I just wish they'd bend to my will

I'm not hung up on type systems, so you aren't offending me at all. I'd simply suggest that if you really want to learn Lisp, that you try to not impose your C++/COM background on it. Instead, read lots of well-written Lisp code (I'd recommend Paradigms of Artificial Intelligence Programming as a good start) and see what good Lisp programmers do. Programmers have been using Lisp for nearly a half-century and there isn't much that they haven't tried during that time, I would surmise. I have been constantly amazed that when I start thinking Lisp needs such and such, I quickly realize that either it already has it, buried in some corner of the CLHS, or I don't really need it.

Put another way, whenever you learn to speak another language, whether human or programming language, you know you have arrived when you master idioms. Idioms from one human language rarely translate well to another human language. Indeed, whenever you use an idiom from a foreign language, you typically speak it in the foreign language. I submit that's true of programming languages, too. So, rather than trying to translate C++/COM idioms into Lisp, try learning Lisp's idioms first.

findinglisp wrote: So, I'm still not sure what you are after, exactly:

• Documentation
• API enforcement
• Performance optimization

API enforcement is what I'm after in this case.

So I still don't see the benefit. In a C++/COM world, type mismatches cause big problems because operations are not type-checked. In Lisp, you can't accidentally add a string and an integer. When you try, you'll generate a condition and be dropped into the debugger. At that point you typically have a full stack trace and can quickly identify where things went wrong.

Consider a case where the thing being passed into the API is a function and the function is stored off in a slot. As long as you give lisp some function, no error condition will arise immediately. Instead, assuming the function provided does not accept the expected arguments, you wont get an error until the function is actually invoked from somewhere. This could be immediately, much later, never, etc. If your code, the API client, is not the one doing the invocation, this could be quite surprising and confusing.

If it was such a big problem, you'd see it being done in Lisp code all over the place, and that just isn't the case.

As I mentioned earlier, I don't believe it is a pervasive problem. I don't think explicit type checking needs to be littered throughout most code. I'm focusing on module level entry points...APIs if you like.

I'm not hung up on type systems, so you aren't offending me at all. I'd simply suggest that if you really want to learn Lisp, that you try to not impose your C++/COM background on it.

I'm trying I'm not a fan of COM in general, but I think the general concept of componentization is valuable for any language that aims to implement large systems. I'd be interested to hear from folks that have worked on mid to large Lisp programs, say 100k+ lines of code, and how they tackled API/interface sorts issues between code modules owned by different devs, etc.

tlareywi wrote: As I mentioned earlier, I don't believe it is a pervasive problem. I don't think explicit type checking needs to be littered throughout most code. I'm focusing on module level entry points...APIs if you like.

Gotcha. That's not unreasonable in a few strategic locations. TYPEDEF can help you build up more complex types and the associated predicates for checking them. You said that Graham didn't go far enough. Have you read through the appropriate sections of CLHS and CLtL2?

http://www.lispworks.com/documentation/ ... /index.htm
http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/clm.html

From a quick reading (don't take my word for it, I might have missed it), CLtL2 seems to imply that you can't check functional arguments. That is, you can determine if FOO is a function with FUNCTIONP, but not whether FOO is a function taking an integer and a list. See the description of "(FUNCTION ...)" here http://www.cs.cmu.edu/Groups/AI/html/cl ... ode49.html . It says you can use the function specifier to declare the types of arguments (optimization) but not check them.

I quickly looked through CLHS and I can't seem to find any language one way or another. You can always try it with TYPEP in your implementation and see what it does. CLtL2 says it will signal an error.

tlareywi wrote: I'd be interested to hear from folks that have worked on mid to large Lisp programs, say 100k+ lines of code, and how they tackled API/interface sorts issues between code modules owned by different devs, etc.

It's not CL, but emacshas over on million lines of Elisp, in one namespace...

TheGZeus wrote:...emacshas over on million lines of Elisp, in one namespace...

Proving that even dumb ideas are workable if you try hard enough.

Seriously, while it is a quite amazing feat if you think about it, I'm not sure anybody would argue that it's the right way to build a large system. What happens is that all emacs symbols end up getting prefixed with the name of the "package" they are associated with. For instance, everything in SLIME has a "slime-" prefix. Essentially, it's the equivalent of typing "package:symbol" all the time, except it's "package-symbol" instead.

findinglisp wrote:

tlareywi wrote: As I mentioned earlier, I don't believe it is a pervasive problem. I don't think explicit type checking needs to be littered throughout most code. I'm focusing on module level entry points...APIs if you like.

Gotcha. That's not unreasonable in a few strategic locations.

You can always roll your own function signature tester. This is Lisp, after all.

findinglisp wrote:

TheGZeus wrote:...emacshas over on million lines of Elisp, in one namespace...

Proving that even dumb ideas are workable if you try hard enough.

Seriously, while it is a quite amazing feat if you think about it, I'm not sure anybody would argue that it's the right way to build a large system. What happens is that all emacs symbols end up getting prefixed with the name of the "package" they are associated with. For instance, everything in SLIME has a "slime-" prefix. Essentially, it's the equivalent of typing "package:symbol" all the time, except it's "package-symbol" instead.

It's fine until you want to merge in third-party components.

chucks wrote:You can always roll your own function signature tester. This is Lisp, after all.

Ah, I was wondering if something like that was doable. Can you briefly describe how this would be accomplished? I assume this would involve getting the AST representation for the function from the symbol referencing the function and then 'car'ing the argument list out, or something along those lines?

Thanks for all the responses thus far. I did take a look at the CLHS docs for deftype and I agree with the consensus that it can not directly express a function signature type. The ability to roll my own checkers would work fine though for the time being. I'm just unclear on how to get that level of introspection.

Cheers!

tlareywi wrote:

chucks wrote:You can always roll your own function signature tester. This is Lisp, after all.

Ah, I was wondering if something like that was doable. Can you briefly describe how this would be accomplished? I assume this would involve getting the AST representation for the function from the symbol referencing the function and then 'car'ing the argument list out, or something along those lines?

It strongly depends on what you need. You mentioned stuffing an API function into a slot and wanting to know at stuff-time rather than at call-time whether a call would break.

But we don't yet know if you're concerned with blessing call exprs or with blessing the function's API signature (e.g., as compared to some declarative doc that you have available). If it's the former, you'll need to entype the call exprs and do some unification against the function's as-built signature. That'll be some significant work. If it's the latter, you'll use Equal and be done with it.

A third possibility is that you're also the function package's author. In that case, you could make the API functions, themselves, test arguments via a sample-call mechanism. And there might be more possibilities for doing what you want that haven't surfaced as yet (I'm just guessing as best I can with a couple minutes thought). Sounds like a bit of fun, though.

tlareywi wrote:

findinglisp wrote: So, I'm still not sure what you are after, exactly:

• Documentation
• API enforcement
• Performance optimization

API enforcement is what I'm after in this case.

So I still don't see the benefit. In a C++/COM world, type mismatches cause big problems because operations are not type-checked. In Lisp, you can't accidentally add a string and an integer. When you try, you'll generate a condition and be dropped into the debugger. At that point you typically have a full stack trace and can quickly identify where things went wrong.

Consider a case where the thing being passed into the API is a function and the function is stored off in a slot. As long as you give lisp some function, no error condition will arise immediately. Instead, assuming the function provided does not accept the expected arguments, you wont get an error until the function is actually invoked from somewhere. This could be immediately, much later, never, etc. If your code, the API client, is not the one doing the invocation, this could be quite surprising and confusing.

the thing i've marked in bold in your text is the key point; how is this "thing" being defined/created?

* you are providing an api in form of something that accepts objects/functions(#1) of a certain kind
* but, at the same time, you are not providing an api for creating (these) objects/functions of that specific certain kind

(defmacro mk-3d-callback ((x-sym y-sym z-sym) &body body)
  `(lambda (,x-sym ,y-sym ,z-sym)
     ,@body))
(export 'mk-3d-callback) ;; Export this to your users; screw the ones who do not use it.


(defun user-api (3d-callback)
  "3D-CALLBACK is a function created by MK-3D-CALLBACK."
  (let ((inner-x 1) (inner-y 2) (inner-z 3)) ;; You want to combine this internal data with behaviour+data from the outside.
    (funcall 3d-callback inner-x inner-y inner-z)))
(export 'user-api)



(defun the-dumb-users-code ()
  (let ((x 3) (y 2) (z 1))                              ;; This is data "from the outside"..
    (user-api (mk-3d-callback (inner-x inner-y inner-z) ;; We use the INNER- prefix to avoid name-clashes(#2).
                (values (+ inner-x x)                   ;; ..and here is the behaviour+data passed in.
                        (+ inner-y y)
                        (+ inner-z z))))))

(the-dumb-users-code)
=> 4, 4, 4

..this was typed in a hurry.. ..maybe someone has pointed something like this out already .. or maybe i've missed something

edit: ..note that you can control or enforce "form of" return data (from the outside, to the internals) in a similar way! (or in many ways really)

#1: functions really are objects you can pass around like anything else in lisp ..
#2: if you don't want to always type the argument-names: (defmacro mk-3d-callback ((&key (x-sym 'x) (y-sym 'y) (z-sym 'z)) &body body) ...) .. but this is something one usually only do when really needed

For functions you could do something like this:

(defmacro defun* (name limited-lambda-list &body body)
  "Like defun, but saves type information.
   Special lambda lists (&optional, &key, etc.) not supported
   Lambda list treated like that of defmethod; ((integer a) b (integer c)) would
    yield variable a, b, and c where a&c are integers and b is of type T"
  (let ((ll (mapcar (lambda (itm) (if (consp itm) (cadr itm) itm)) limited-lambda-list))
        (types (mapcar (lambda (itm) (if (consp itm) (car itm) t)) limited-lambda-list))
        (args (gensym))
        (docstring (if (stringp (car body)) (car body)))
        (body (if (stringp (car body)) (cdr body) body)))
    `(defun ,name (&rest ,args)
       (declare (special *inspect-function-type*))
       ,docstring
       (cond
	((and (boundp '*inspect-function-type*) *inspect-function-type*)
         ',types)
        (t
         (destructuring-bind ,ll ,args
           ,@body))))))

(defun check-function (function &rest types)
  "Checks that a given function (defined with defun*) is of the correct type"
  (let ((ftypes (let ((*inspect-function-type* t))
                 (declare (special *inspect-function-type*))
                 (funcall function))))
    (when (or (/= (length ftypes) (length types))
              (notevery #'subtypep types ftypes))
      (error "Function ~a is typed ~a; expected ~a" function ftypes types))))

Downsides:
1) check-function will only work correctly when the given function behaves like a function that defun* would define.
2) The lambda-list for the function defun* creates isn't helpful
3) As mentioned in the code, you (currently) don't get &option, &rest, &aux, &key, etc.
4) The functions created currently don't check to see that the arguments they are given match their declared types

Side note: Having functions bound to a symbol and knowing the symbol would fix problems 1&2 as you could store the information in the symbol's plist then.

My advice: Trusting the programmers who are going to be using your functions is probably the better option.

The above strategy makes sense to me and seems quite robust. That's basically what I'm after. Thanks for all the responses!

I was thinking today, and came up with a better implementation for defun*:

(defparameter *%function-types* (make-hash-table :test #'eq))

(defmacro defun* (name limited-lambda-list &body body)
  "Like defun, but saves type information.
   Special lambda lists (&optional, &key, etc.) not supported
   Lambda list treated like that of defmethod; ((integer a) b (integer c)) would
    yield variable a, b, and c where a&c are integers and b is of type T"
  (let ((ll (mapcar (lambda (itm) (if (consp itm) (cadr itm) itm)) limited-lambda-list))
	(types (mapcar (lambda (itm) (if (consp itm) (car itm) t)) limited-lambda-list))
        (docstring (if (stringp (car body)) (car body)))
        (body (if (stringp (car body)) (cdr body) body)))
    `(progn
       (if (fboundp ',name)
	   (remhash (symbol-function ',name) *%function-types*))
       (defun ,name ,ll
	 ,docstring
	 ,@(loop for var in ll for type in types collect `(check-type ,var ,type))
	 ,@body)
       (setf (gethash (symbol-function ',name) *%function-types*)
	     ',types)
       ',name)))

(defun check-function (function &rest types)
  "Checks that a given function (defined with defun*) is of the correct type"
  (let ((ftypes (gethash function *%function-types*)))
    (when (or (/= (length ftypes) (length types))
              (notevery #'subtypep types ftypes))
      (error "Function ~a is typed ~a, expected ~a" function ftypes types))))

(defun unregister-function (function)
  (remhash function *%function-types*))

1) check-function is safe to use on untyped functions.
2) check-function can be trivially improved to reject all untyped functions
3) The lambda list for the function defun* creates is helpful, though still limited.
4) It automatically checks to make sure the function was given the right types.

I'm thinking of making a simple prototype-based object system based on the above technique.

about body, declarations and doc-strings .. Alexandria has a parse-body which might be useful .. it can be used like, say, this:

(defmacro mk-on-cnt-add-fn ((new-children-sym container-sym &key
                                              (on-cnt-add-fn-sym 'on-cnt-add-fn on-cnt-add-fn-sym-supplied-p)
                                              once-only-p)
                            &body body)
  (multiple-value-bind (body declarations) (parse-body body)
    (unless on-cnt-add-fn-sym-supplied-p
      (push `(declare (ignorable ,on-cnt-add-fn-sym)) declarations))
    `(lambda (,new-children-sym ,container-sym ,on-cnt-add-fn-sym)
       ,@declarations
       (when ,once-only-p (remove-cb ,container-sym :cnt-add ,on-cnt-add-fn-sym))
       ,@body)))

..parse-body actually returns 3 values .. the 3rd one being the doc-string, but i don't use this here

tlareywi wrote: [...] 2. A way to define a function signature type. For instance, a type that represents the class of all functions that take two number arguments. [...]

(deftype functions-that-take-two-number-arguments () (quote (function (number number) t)))

examples:

CL-USER> (deftype functions-that-take-two-arguments () (quote (function (* *) t)))
FUNCTIONS-THAT-TAKE-TWO-ARGUMENTS

CL-USER> (declaim (ftype functions-that-take-two-arguments test-2 test-3))
; No value

CL-USER> (defun test-2 (a b) (values a b))
TEST-2

CL-USER> (defun test-3 (a b c) (values a b c))
; in: LAMBDA NIL
;     (SB-INT:NAMED-LAMBDA TEST-3 (A B C) (BLOCK TEST-3 (VALUES A B C)))
; ==>
;   #'(SB-INT:NAMED-LAMBDA TEST-3 (A B C) (BLOCK TEST-3 (VALUES A B C)))
; 
; caught STYLE-WARNING:
;   The definition has three args, but the proclamation has two.
; 
; compilation unit finished
;   caught 1 STYLE-WARNING condition
TEST-3

new type:

CL-USER> (deftype fun-args (&rest args)
           `(function ,(if (and (integerp (car args)) (endp (cdr args)))
                           (make-list (car args) :initial-element (quote *))
                           args)
                      t))
FUN-ARGS

first example -- declaim function(s) with fixed number of arguments:

CL-USER> (declaim (ftype (fun-args 2) test-fun-2-args test-fun-3-args))
; No value

CL-USER> (defun test-fun-2-args (a b) (values a b))
TEST-FUN-2-ARGS

CL-USER> (defun test-fun-3-args (a b c) (values a b c))
; [...]
; caught STYLE-WARNING:
;   The definition has three args, but the proclamation has two.
; [...]
TEST-FUN-3-ARGS

second example -- declaim function with fixed number of args and specified (input) types --
1: number
2: symbol
3: array of element type integer which contains 3 elements

CL-USER> (declaim (ftype (fun-args number symbol (array integer (3))) fun-test))
; No value

CL-USER> (defun fun-test (a b c) (values a b c))
FUN-TEST

CL-USER> (fun-test 3.14 'foo #(1 2 3))
3.14
FOO
#(1 2 3)

CL-USER> (ignore-errors (fun-test 0 0 0))
NIL
#<TYPE-ERROR {AC8F3C1}>

CL-USER> (ignore-errors (fun-test 3.14 'foo #(1 2)))
NIL
#<TYPE-ERROR {AD85601}>

...