How can I rewrite the function APPLY without using APPLY?

So, I have often wondered about this. APPLY is not a special operator, but I cannot seem to figure out how it is written without usage of the APPLY function. If it is not a special operator, doesn't that mean that it should be representable in terms of special operators?

Put another way, how could someone write an APPLY-TO-VECTOR function? This would work something like this:

(apply-to-vector #'+ (vector 1 2 3 4))
 ==> 10

Would you have to cons up a new list that holds a vectors contents, then use APPLY? Or could you do something that uses the vector directly.

I'll leave it at that, but has anyone else thought about this? Anyone know if/how this can be done?

Zach

smithzv wrote: Put another way, how could someone write an APPLY-TO-VECTOR function? This would work something like this:

(apply-to-vector #'+ (vector 1 2 3 4))
 ==> 10

Well it depends on you *really* want. If you just want to do stuff like your example, reduce works with sequences (including vectors):

(reduce #'+ #(1 2 3 4))

I can't see when you'd like to apply a function to itens in a vector, but then you can use coerce:

(apply #'expt (coerce #(2 3) 'list))

Pedro

I can't see when you'd like to apply a function to itens in a vector

Thanks for the reply. Perhaps this is too academic for the part of the CL community represented here?

Well it depends on you *really* want.

I wanted to know if APPLY is some kind of black box function/language primitive. I was under the impression that the only language primitives are special operators/forms (perhaps from the first few chapters I got to read of Lisp in Small Pieces). I think maybe this is just plain false. If someone cannot write APPLY within CL, what functions are like APPLY? Is there a defined (or definable) set of "primitive" functions?

If you have ever watched the SICP video lectures, then you might remember the scene where Sussman labels the two hands drawing each other EVAL and APPLY, so apply is a rather basic function. You could write your own apply, but at that point you would probably end up writing a lot of a lisp implementation.

smithzv wrote: I wanted to know if APPLY is some kind of black box function/language primitive. I was under the impression that the only language primitives are special operators/forms (perhaps from the first few chapters I got to read of Lisp in Small Pieces). I think maybe this is just plain false. If someone cannot write APPLY within CL, what functions are like APPLY? Is there a defined (or definable) set of "primitive" functions?

Only the compiler knows how to call the function (because function is usually compiled to byte code or machine code), so it is not possible to write apply in CL.
If the body of all functions is available then it is possible to write the interpreter (which uses only special forms) (see http://en.wikipedia.org/wiki/Metacircular_interpreter).

dmitry_vk wrote:Only the compiler knows how to call the function (because function is usually compiled to byte code or machine code), so it is not possible to write apply in CL.

I had a quick look at the SBCL source and found apply in eval.lisp, line 279 - search for "defun apply".
Note however the comment just beforehand:

276 ;;; miscellaneous full function definitions of things which are
  277 ;;; ordinarily handled magically by the compiler
  278 
  279 (defun apply (function arg &rest arguments)
  280   #!+sb-doc
  281   "Apply FUNCTION to a list of arguments produced by evaluating ARGUMENTS in
  282   the manner of LIST*. That is, a list is made of the values of all but the
  283   last argument, appended to the value of the last argument, which must be a
  284   list."
  285   (cond ((atom arguments)
  286          (apply function arg))
  287         ((atom (cdr arguments))
  288          (apply function (cons arg (car arguments))))
  289         (t (do* ((a1 arguments a2)
  290                  (a2 (cdr arguments) (cdr a2)))
  291                 ((atom (cdr a2))
  292                  (rplacd a1 (car a2))
  293                  (apply function (cons arg arguments)))))))

HTH!

[edit]
Although I don't understand how it can terminate It seems to recurse in every case?

[edit2]
Or perhaps it's the "((atom (cdr a2)) (rplacd a1 (car a2))" end test.

Exolon wrote: I had a quick look at the SBCL source and found apply in eval.lisp, line 279 - search for "defun apply".

Although I don't understand how it can terminate It seems to recurse in every case?

that's the apply from my version of sbcl (version 1.0.21.11), the part after the t terminates the recursion:

(defun apply (function arg &rest arguments)
  #!+sb-doc
  "Apply FUNCTION to a list of arguments produced by evaluating ARGUMENTS in
  the manner of LIST*. That is, a list is made of the values of all but the
  last argument, appended to the value of the last argument, which must be a
  list."
  (cond ((atom arguments)
         (apply function arg))
        ((atom (cdr arguments))
         (apply function (cons arg (car arguments))))
        (t (do* ((a1 arguments a2)
                 (a2 (cdr arguments) (cdr a2)))
                ((atom (cdr a2))
                 (rplacd a1 (car a2))
                 (apply function (cons arg arguments)))))))

smithzv wrote: Thanks for the reply. Perhaps this is too academic for the part of the CL community represented here?

I don't think it was too academic. it was not clear to me if you want to understand how apply is defined, to reduce the items in a vector or something else.

I wanted to know if APPLY is some kind of black box function/language primitive. I was under the impression that the only language primitives are special operators/forms (perhaps from the first few chapters I got to read of Lisp in Small Pieces). I think maybe this is just plain false. If someone cannot write APPLY within CL, what functions are like APPLY? Is there a defined (or definable) set of "primitive" functions?

of course you can define apply using CL. you discovered the source code in SBCL yourself.

Have you checked chapter 4 of SICP?

http://mitpress.mit.edu/sicp/full-text/ ... l#%_chap_4

Pedro

Exolon wrote: I had a quick look at the SBCL source and found apply in eval.lisp, line 279 - search for "defun apply".

Although I don't understand how it can terminate It seems to recurse in every case?

AFAIU, the apply inside a defun is an apply from compiler environment. So, (defun apply ...) defines an apply function in a program's image which calls apply function from the compiler image (from the image of the compiler that compiled the compiler). So, it's not recursive
The real apply in SBCL is defined somewhere else. AFAIK, it should be defined in sb-imp package.
I'm not familiar with sbcl internals, so I might be wrong.

dmitry_vk wrote:The real apply in SBCL is defined somewhere else. AFAIK, it should be defined in sb-imp package.
I'm not familiar with sbcl internals, so I might be wrong.

I had a look for all definitions of apply, but haven't found another one yet (there's a %apply and interpreted-apply or something, but they seem similar).

[edit]
Another possible one in compiler/srctran.lisp:

;;; We convert APPLY into MULTIPLE-VALUE-CALL so that the compiler
;;; only needs to understand one kind of variable-argument call. It is
;;; more efficient to convert APPLY to MV-CALL than MV-CALL to APPLY.
(define-source-transform apply (fun arg &rest more-args)
  (let ((args (cons arg more-args)))
    `(multiple-value-call ,fun
       ,@(mapcar (lambda (x)
                   `(values ,x))
                 (butlast args))
       (values-list ,(car (last args))))))

smithzv wrote:I wanted to know if APPLY is some kind of black box function/language primitive. I was under the impression that the only language primitives are special operators/forms (perhaps from the first few chapters I got to read of Lisp in Small Pieces). I think maybe this is just plain false.

It's not like APPLY can't be implemented on top of other primitives, but in general, you can't reimplement your Lisp implementation's version of APPLY portably. The situation is the same as for everything else that deals with some kind of data structure.

How do you replace CAR with a function of your own? Well, you can't; the only thing you can do is redefine what a cons cell is (using closures, for example) and then rip out everything that deals with cons cells and reimplement it in terms of your newly defined data structure. In this sense, CAR is a primitive operation. You can't replace it without reimplementing most of Common Lisp because cons cells are defined in terms of CONS, CAR, CDR, RPLACA, and RPLACD.

Functions, likewise, are defined in terms of LAMBDA and APPLY (and maybe some more). If you want to reimplement APPLY, you'll have to redefine what a function is and rewrite LAMBDA, DEFUN, FUNCTION, et cetera accordingly (which would likely affect almost every component in the system including the loader, so I imagine you'd effectively have to replace all of Common Lisp in this case).

If you're the implementor of a Common Lisp system, there is some merit in only implementing a few primitives and defining everything in terms of these, and you can probably do so, but as a user of someone else's system, you don't retain quite the same power.

dmitry_vk wrote:

Exolon wrote: I had a quick look at the SBCL source and found apply in eval.lisp, line 279 - search for "defun apply".

Although I don't understand how it can terminate It seems to recurse in every case?

AFAIU, the apply inside a defun is an apply from compiler environment. So, (defun apply ...) defines an apply function in a program's image which calls apply function from the compiler image (from the image of the compiler that compiled the compiler). So, it's not recursive
The real apply in SBCL is defined somewhere else. AFAIK, it should be defined in sb-imp package.
I'm not familiar with sbcl internals, so I might be wrong.

I'm not well-versed in SBCL internals, but I think apply doesn't really exist as such most of the time since SBCL compiles everything (it has no interpreter, though somebody was working on grafting one back in, I thought). When interpreting, apply is used at the point of every function call. As such, it's as recursive as your code call depth is deep. It simply keeps evaluating arguments and applying functions to them all the way down the call stack.

In SBCL, since it's compiled, not interpreted, many (most) function calls are directly dispatched right from the call site and don't go through a central apply function. The same basic operations are being done, but they're distributed throughout the code rather than centralized. You still need a central apply function for those cases where the user code actually calls it directly (#'APPLY has to refer to something), but then you can rapidly switch back to direct calls as you enter the code that the user is APPLYing.

smithzv wrote:If it is not a special operator, doesn't that mean that it should be representable in terms of special operators?

No. There's nothing that says that builtins have to be special forms. Being a special form just means it doesn't use the default evaluation rule.