How can I rewrite the function APPLY without using APPLY?

Discussion of Common Lisp
Kompottkin
Posts: 94
Joined: Mon Jul 21, 2008 7:26 am
Location: München, Germany
Contact:

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

Post by Kompottkin » Sun Oct 26, 2008 1:06 am

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.

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

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

Post by findinglisp » Sun Oct 26, 2008 9:18 am

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 :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.
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.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

metageek
Posts: 10
Joined: Fri Jul 25, 2008 8:01 am

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

Post by metageek » Mon Oct 27, 2008 5:42 am

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.

Post Reply