Page 1 of 2

How can I rewrite the function APPLY without using APPLY?

Posted: Fri Oct 24, 2008 10:23 am
by smithzv
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:

Code: Select all

(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

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Fri Oct 24, 2008 10:57 am
by kroger
smithzv wrote: Put another way, how could someone write an APPLY-TO-VECTOR function? This would work something like this:

Code: Select all

(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):

Code: Select all

(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:

Code: Select all

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

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Fri Oct 24, 2008 8:58 pm
by smithzv
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?

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Fri Oct 24, 2008 9:15 pm
by qbg
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.

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Fri Oct 24, 2008 9:20 pm
by dmitry_vk
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).

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Sat Oct 25, 2008 4:29 am
by Exolon
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:

Code: Select all

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 :D It seems to recurse in every case?

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

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Sat Oct 25, 2008 4:49 am
by kroger
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 :D 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:

Code: Select all

(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)))))))

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Sat Oct 25, 2008 4:54 am
by kroger
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

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Sat Oct 25, 2008 8:14 am
by dmitry_vk
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 :D 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.

Re: How can I rewrite the function APPLY without using APPLY?

Posted: Sat Oct 25, 2008 8:23 am
by Exolon
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:

Code: Select all

;;; 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))))))