How can I rewrite the function APPLY without using APPLY?

Discussion of Common Lisp
smithzv
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

How can I rewrite the function APPLY without using APPLY?

Post by smithzv » Fri Oct 24, 2008 10:23 am

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

kroger
Posts: 12
Joined: Mon Jul 28, 2008 2:38 am

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

Post by kroger » Fri Oct 24, 2008 10:57 am

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

smithzv
Posts: 94
Joined: Wed Jul 23, 2008 11:36 am

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

Post by smithzv » Fri Oct 24, 2008 8:58 pm

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?

qbg
Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

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

Post by qbg » Fri Oct 24, 2008 9:15 pm

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.

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

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

Post by dmitry_vk » Fri Oct 24, 2008 9:20 pm

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

Exolon
Posts: 49
Joined: Sat Jun 28, 2008 12:53 pm
Location: Ireland
Contact:

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

Post by Exolon » Sat Oct 25, 2008 4:29 am

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.

kroger
Posts: 12
Joined: Mon Jul 28, 2008 2:38 am

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

Post by kroger » Sat Oct 25, 2008 4:49 am

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

kroger
Posts: 12
Joined: Mon Jul 28, 2008 2:38 am

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

Post by kroger » Sat Oct 25, 2008 4:54 am

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

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

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

Post by dmitry_vk » Sat Oct 25, 2008 8:14 am

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.

Exolon
Posts: 49
Joined: Sat Jun 28, 2008 12:53 pm
Location: Ireland
Contact:

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

Post by Exolon » Sat Oct 25, 2008 8:23 am

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

Post Reply