The way you implement apply is directly tied to how you implement function calls. If you compile your code, you have a protocol at runtime where you know how values are exchanged between function calls, and apply can emit code that satisfy to this protocol. We could do the same in a quick and dirty interpreter. Let's define a package:
(defpackage :interpreter (:use :cl))
(in-package :interpreter)
We define a function object, which has an optional name, a list of parameters, the code as well as a set of bindings being closed-over:
(defstruct fn name parameters code closed)
We also define a frame, which has a set of bindings and an optional parent frame:
(defstruct frame bindings parent)
Here we have a simple interpreter, and we put the current frame within the evaluation environment:
(defstruct env frame)
Bindings are either objects of type FN, or cons pairs. We write generic functions to manipulate them with a uniform API. Functions and variables share the same namespace:
(defgeneric name (object)
(:method ((fn fn)) (fn-name fn))
(:method ((pair cons)) (car pair)))
(defgeneric value (object)
(:method ((c cons)) (cdr c))
(:method ((fn fn)) fn))
We define two functions, my-apply and my-eval
(declaim (ftype function my-apply my-eval))
There is a global environment, which is simply:
(defparameter *global-frame*
(make-frame
:bindings (list (make-fn :name '+
:parameters '(x y)
;; built-in
:code (lambda (x y) (+ x y)))
(make-fn :name 'addition
:parameters '(x y)
:code '(+ x y)))
:parent nil))
The empty environment implicitly holds to the global frame:
(defgeneric frame (env)
(:method ((empty null)) *global-frame*)
(:method ((env env)) (env-frame env)))
Resolving a binding involves visiting parent frames:
(defun resolve (name frame &optional (on-error :error))
(labels ((recurse (frame)
(cond
(frame (or (find name (frame-bindings frame) :key #'name)
(recurse (frame-parent frame))))
((eql :error on-error) (error "Unknown: ~a" name)))))
(recurse frame)))
The evaluation function is the following one:
(defun my-eval (code env &aux (frame (frame env)))
(flet ((ev (exp) (my-eval exp env)))
(typecase code
(symbol (value (resolve code frame)))
(atom code)
(cons
(destructuring-bind (head . tail) code
(case head
(list (mapcar #'ev tail))
(let (destructuring-bind ((var val) expr) tail
(my-eval expr
(make-env :frame (make-frame :bindings `((,var . ,(ev val)))
:parent frame)))))
(thunk (make-fn :name nil
:parameters nil
:code (first tail)
:closed (frame-bindings frame)))
(apply (my-apply (ev (first tail))
(ev (second tail))
env))
(t (my-apply (resolve head (frame env))
(mapcar #'ev tail)
env))))))))
The evaluation functions accept the following terms:
(list <...>) builds a list containing the result of evaluation of its arguments(apply <fn-expr> <arg-expr>), evaluate all arguments and call the my-apply primitive.(let (<var> <val>) <expr>), local binding(thunk <expr>) closes over current environment and produce an anonymous closure with no parameters which returns the value of <expr> (<f> . <args>) function call- symbols are resolved for values, and other values are returned as-is.
The built-in my-apply knows how to bind parameters to values dynamically:
(defun my-apply (fn arguments env)
(assert (= (length arguments)
(length (fn-parameters fn)))
()
"Length mismatch when calling ~S with argsuments ~S"
fn
arguments)
(let ((code (fn-code fn)))
(typecase code
(function (apply code arguments))
(t (my-eval code
(make-env :frame
(make-frame :bindings (append (fn-closed fn)
(mapcar #'cons
(fn-parameters fn)
arguments))
:parent (frame env))))))))
For example:
(my-eval '(let (f (let (x 10) (thunk (addition x 5))))
(let (x 20) (apply f (list)))) nil)
=> 15
In the above example, f is a function that closes over the binding of x to 10, and calls addition. The binding that is made later is not seen by the closure. The call to apply resolves f and builds an empty list. The call to addition resolves to (+ 10 5), which itself eventually calls the CL function +. You can (trace my-eval) to see how things are evaluated. The above code is a bit messy.
applycalls theIFn.applyTo()method of the function, so it's actually implemented in Java. – Taylor Woodapplyis generally one of the most primitive ways to call functions, everything else is defined in terms of it. – Barmarapplyis quite involved. I don't think the answers so far are good at explaining it. It'd need a lot of effort to explain it fully. Probably worth a blog post. The complications are: Variadic functions + Lazy sequences. If you didn't have them the impl would be straight forward. – ClojureMostly