higher-order programming language

higher-order programming language

Post by Marlene Mi » Tue, 07 Nov 2006 15:07:32


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)
(eval (caddar e)
(append (pair (cadar e)
(evlis (cdr e) a)) a)))))
 
 
 

higher-order programming language

Post by Pascal Cos » Wed, 08 Nov 2006 01:26:39


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

Post by Marlene Mi » Wed, 08 Nov 2006 16:29:00


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

Post by Pascal Bou » Wed, 08 Nov 2006 23:25:03

"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

Post by Pascal Cos » Thu, 09 Nov 2006 00:20:02


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/