## higher-order programming language

### higher-order programming language

I have been observing McCarthy's 1960 universal apply function. Examples 4
and 5 below do not work. Does that mean *this* LISP is not a higher-order
programming language?

1. Recursion.

(apply '(LAMBDA (NULL)
((LABEL MEMBER
(LAMBDA (X L)
(COND ((NULL L) (QUOTE ()))
((EQ X (CAR L)) (QUOTE T))
((QUOTE T)
(MEMBER X (CDR L))))))
(QUOTE A) (QUOTE (B A D))))
'((LAMBDA (X) (EQ X (QUOTE ())))))

;=> T

2. Passing functions. F is a free variable. Dynamic scoping.

(apply '(LAMBDA (F G) (G (QUOTE (L M N))))
'((LAMBDA (Y) (CAR X)) (LAMBDA (X) (F (QUOTE (A B C))))))
;=> L

3. Returning a function

(apply '(LAMBDA (F)
((LAMBDA (X) F) (QUOTE (A B C))))
'((LAMBDA (X) (CAR X))))

;=> (LAMBDA (X) (CAR X))

4. Cannot return a function and apply it.

(apply '(LAMBDA (X)
((LAMBDA (X) (LAMBDA (X) (CAR X))) (QUOTE (A B C))))
'((D E F)))

This cannot be evaluated: (LAMBDA (X) (CAR X))
with bindings ((X (A B C)) (X (D E F)))

5. Cannot return a function and apply it.

(apply '(LAMBDA (F)
(((LAMBDA (X) F) (QUOTE (A B C))) (QUOTE (D E G))))
'((LAMBDA (X) (CAR X))))

This cannot be evaluated:
(((LAMBDA (X) F) (QUOTE (A B C))) (QUOTE (D E G)))
with bindings ((F (LAMBDA (X) (CAR X))))

The reason is LAMBDA has to be (caar e).

(define (apply f args)
(eval (cons f (appq args)) '()))

(define (eval e a)
[...]
((eq (caar e) 'LAMBDA)
(evlis (cdr e) a)) a)))))

### higher-order programming language

It is higher-order, but it doesn't deal correctly with a number of
cases. You have basically rediscovered the "upward funarg problem."
Google for the paper "The Function of FUNCTION in LISP" by Joel Moses
for more details. A partial solution for these problems are dynamic
closures, as in Lisp 1.5 and some other early Lisp dialects, and
ultimately true lexical closures, as in Scheme, Common Lisp and most
later Lisp dialects.

Pascal

--
My website: http://www.yqcomputer.com/
Common Lisp Document Repository: http://www.yqcomputer.com/
Closer to MOP & ContextL: http://www.yqcomputer.com/

### higher-order programming language

4
higher-order

Thank you for the reference and comments.

I am disappointed those cases 4 and 5 do not work. I wanted to try

(((lambda (x)
(lambda (y) x)) 'a) 'b)

x is not a free variable. But the value of the variable reference x is not
the value bound to the parameter x.

### higher-order programming language

"Marlene Miller" < XXXX@XXXXX.COM > writes:

See point d. in:
http://www.yqcomputer.com/ #SECTION00040000000000000000

--
__Pascal Bourguignon__ http://www.yqcomputer.com/

"Specifications are for the weak and timid!"

### higher-order programming language

This link is probably correct wrt the history of the "environment
problem," but incorrect in that FUNCTION in Lisp 1.5 does not capture
the lexical enviroment, but the dynamic environment.

Pascal

--
My website: http://www.yqcomputer.com/
Common Lisp Document Repository: http://www.yqcomputer.com/
Closer to MOP & ContextL: http://www.yqcomputer.com/