I can't comment on ml, but there are times when I wish certain functions
in Lisp were curried rather than tupled. The reason is that I would like
the functions to be partially applied, and that the compiler would take
advantage of constant propagation for the partially applied arguments.
Yes, this can all be done by a clever compiler, but if the _usual_ usage
of a function nearly always wants to be partially applied, then perhaps
the primitive functions are not properly organized.
For example, two functions that come to mind are 'sort' and 'search'.
Sorting usually involves passing a comparison function, but very often
the comparison function is constant and large efficiency gains can be
made by specializing the sort function. Wouldn't it be much better to
write sort like this:
Scheme: ((sort <) list)
Common Lisp: (funcall (sort #'<) list)
rather than having the compiler try to figure all of this out?
Ditto for search. The pattern to be searched for is often constant,
and major gains in efficiency can be obtained by preprocessing (compiling)
the pattern.
Scheme: ((search "abc") string)
Common Lisp: (funcall (search "abc") string)
Notice that by explicitly currying, the compiler no longer needs painful
analyses to figure out when preprocessing is ok -- it is now _always_ ok.
It also is much better for the programmer who can then rest easy knowing
that the correct optimization will be done, without his having to come
up with a myriad of specialized search functions on his own.
However, unless substantial gains of this sort are to be expected from
such partial evaluation, the more traditional tupling approach is to
be preferred for strict languages with side-effects.
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
as a side tidbit, Dybvig's C-Scheme [1] implemented complete currying
of its function definitions and applications. this probably made some
parts easier to implement. [perhaps Kent may comment?]
oz
---
[1] Kent Dybvig
C-Scheme Reference Manual
Computer Science Department Technical Report #149
Indiana University, 1983
--
humpty-dumpty was pushed. | electric: ··@nexus.yorku.ca
- anonymous | or ··@sni.ca [416] 449 9449
······@netcom.com (Henry Baker) writes:
>I can't comment on ml, but there are times when I wish certain functions
>in Lisp were curried rather than tupled. The reason is that I would like
>the functions to be partially applied, and that the compiler would take
>advantage of constant propagation for the partially applied arguments.
Would it be a valid extension for a Scheme system to treat a
procedure called with `insufficient' number of arguments as an
indication to return a curried procedure?
·····@netcom.com (Bakul Shah) writes:
>Would it be a valid extension for a Scheme system to treat a
>procedure called with `insufficient' number of arguments as an
>indication to return a curried procedure?
I don't think so, but I think the following is standard scheme:
(define (curry f a) (lambda l (apply f (cons a l))))
(define (curryn f l) (lambda l2 (apply f (append l l2))))
(define (rcurry f a) (lambda l (apply f (append (list a) l))))
(define (rcurryn f l) (lambda l2 (apply f (append l2 l))))
Note that this is actually _more_ expressive than leaving out parameters:
how would you express (rcurry / 2) without writing rcurry?
Since Scheme has no type system, errors resulting from absent parameters
could be extremely difficult to detect. On the other hand, you can express
the Y combinator in Scheme, so typed isn't necessarily what it's cracked
up to be.
As a Scheme programmer who has used Gofer fairly extensively, these four
procedures are in my personal standard library.
Now for a real _Scheme_ question: Does anyone know a more efficient way
of coding any of them?
-- Scot
In article <···············@netcom.com>, ·····@netcom.com (Bakul Shah) wrote:
> Would it be a valid extension for a Scheme system to treat a
> procedure called with `insufficient' number of arguments as an
> indication to return a curried procedure?
I wouldn't care for that because you're being deprived of error trapping
when you have too few arguments because you goofed rather than intending
to curry!
;;;;;;;;;;;;;;;;;;;; Andre van Meulebrouck ;;;;;;;;;;;;;;;;;;;;;
;; e-mail: ········@acm.org finger: ········@netcom.com ;;
;;;;; URL: ftp://ftp.netcom.com/pub/va/vanmeule/home.html ;;;;;
In article <·······················@192.0.2.1> ······@netcom.com (Henry Baker) writes:
>Sorting usually involves passing a comparison function, but very often
>the comparison function is constant and large efficiency gains can be
>made by specializing the sort function. Wouldn't it be much better to
>write sort like this:
>
>Scheme: ((sort <) list)
>Common Lisp: (funcall (sort #'<) list)
>
>rather than having the compiler try to figure all of this out?
The compiler optimization techniques required to recognize that this can be
optimized are not much simpler than those required to recognize
(sort #'< list)
Many compilers already have recognizers for common patterns like this. And
Common Lisp even makes such optimization techniques available to the user,
with the DEFINE-COMPILER-MACRO feature.
--
Barry Margolin
BBN Planet Corporation, Cambridge, MA
······@near.net
In article <··········@tools.near.net>, ······@nic.near.net (Barry
Margolin) wrote:
> In article <·······················@192.0.2.1> ······@netcom.com (Henry
Baker) writes:
> >Sorting usually involves passing a comparison function, but very often
> >the comparison function is constant and large efficiency gains can be
> >made by specializing the sort function. Wouldn't it be much better to
> >write sort like this:
> >
> >Scheme: ((sort <) list)
> >Common Lisp: (funcall (sort #'<) list)
> >
> >rather than having the compiler try to figure all of this out?
>
> The compiler optimization techniques required to recognize that this can be
> optimized are not much simpler than those required to recognize
>
> (sort #'< list)
I disagree. I'm interested in 100% accurate analysis and optimizations.
The Lisp 'optimizers' I have seen are usually syntactically based, and
it is usually very easy to trick them into making serious errors, because
they do not have a deep understanding of the code they are trying to optimize.
They make lots of assumptions -- e.g., that cons cells won't be destroyed
by the program as it is running -- that are _usually_ true, but not always
true. This means that higher levels of optimization are often attended by
system crashes that are difficult to find the source of.
> Many compilers already have recognizers for common patterns like this. And
> Common Lisp even makes such optimization techniques available to the user,
> with the DEFINE-COMPILER-MACRO feature.
Ditto.
----
There is a place for 'heuristic' optimization -- particularly when the
underlying language is not well designed for an application, and the programmer
is going to apply an optimization only to _his_ program, which he presumably
understands very well. However, such ad hoc optimizations are not useful
as _generic_ optimizations in a wide-spectrum system language, because the
optimization then has to work in _every_ case.
The whole point of currying the search function is a way of the
programmer telling the compiler that preprocessing a (constant) pattern
is ok in _every_ case -- there are _no_ exceptions.
--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
Hi,
I am trying to set up a list environment (compiler, interpreter.. whatever)
in my company. I have myself used acl (allegro) and scl (sun's )
Could someone let me know if i can ftp source for building common lisp.
if so from where?
please email to me.
appreciate it
Deepa
·····@imatron.com
In article <·······················@192.0.2.1>, ······@netcom.com (Henry
Baker) wrote:
> I can't comment on ml, but there are times when I wish certain functions
> in Lisp were curried rather than tupled.
I agree entirely. This whole area of partial evaluation and currying
needs to be re-examined.
Due to tunnel vision, people that see conventional languages first, then
LISP; find LISP quite strange (at least at first).
Due to similar tunnel vision we find that concepts from lambda calculus
seem strange to LISPers.
For instance, when first introduced to currying there is a temptation to
think that it's a hassle born of the thriftiness of lambda calculus and
that it's just a slower, less efficient way of dealing with parameters
than passing as many as you like to a function straightaway.
But then you start to see the brilliance of currying and that you can
express any non-curried function as a curried function BUT NOT THE
REVERSE!!!
Truly it is a very powerful technique that views parameters as like the
talons of a cat: they are tucked away until needed (so they don't get in
the way).
Another use of currying (beyond your examples) is in roll-your-own objects
a la Abelson and Sussman.
Currying gives a much more uniform way of having messages that have
varying numbers of arguments.
You break the message out from the arguments so you can have uniformity:
(lambda (message)
(cond
((eq? message 'foo)
(lambda (arg1 arg2) ...))
((eq? message 'fido)
(lambda (arg1) ...)
etc..
then call them:
((object 'foo) arg1 arg2)
((object 'fido) arg1)
Imagine trying to do this without currying. How inelegant. Of course you
could use the variable arity stuff in Scheme, but then if you pass these
objects around a lot you have to futs with them (inefficient and
confusing). I.e.:
(lambda (message . args)
would mean you'd have to do something inelegant to get around the list
structuring of the arguments using apply: (apply message args). This
would mean less uniformity in calling conventions for "resident" objects
vs. those that got passed around.
;;;;;;;;;;;;;;;;;;;; Andre van Meulebrouck ;;;;;;;;;;;;;;;;;;;;;
;; e-mail: ········@acm.org finger: ········@netcom.com ;;
;;;;; URL: ftp://ftp.netcom.com/pub/va/vanmeule/home.html ;;;;;
I don't particularly have any opinion on the curried vs. tupled
debate, but if you do want to go the curried route, isn't Scheme a bit
limited by the fact that it is awkward to efficiently partially apply
a function and get two or more functions back?
For example, consider the example of a simple binary tree with create,
insert, and lookup operations :-
(define (make-tree) ...)
(define (tree-insert key value < tree) ...)
(define (tree-lookup key < tree) ...)
If you prefer to factor out the ordering, the insert and lookup could
be written as to :-
(define (tree-insert <) (lambda (key value tree) ...))
(define (tree-lookup <) (lambda (key tree) ...))
However, the ordering is still defined separately for both insert and
lookup. This is a) tedious (especially given that in a real tree code
there is likely to be >> 2 functions) and b) makes it possible,
though perhaps not likely, that different ordering functions are
passed to insert and lookup.
I'd be interested in any solutions the above.
·····@cs.man.ac.uk (Stephen J Bevan) writes:
| (define (tree-insert <) (lambda (key value tree) ...))
| (define (tree-lookup <) (lambda (key tree) ...))
|
|However, the ordering is still defined separately for both insert and
|lookup. This is a) tedious (especially given that in a real tree code
|there is likely to be >> 2 functions) and b) makes it possible,
|though perhaps not likely, that different ordering functions are
|passed to insert and lookup.
(define (make-tree-type <)
(lambda (message)
(cond ((eq? message 'insert) (lambda (key value tree) ...))
((eq? message 'lookup) (lambda (key tree) ...))
...)))
[ I've directed followups to comp.lang.scheme - bevan ]
In article <··········@agate.berkeley.edu> ··@anarres.CS.Berkeley.EDU (Brian Harvey) writes:
·····@cs.man.ac.uk (Stephen J Bevan) writes:
| (define (tree-insert <) (lambda (key value tree) ...))
| (define (tree-lookup <) (lambda (key tree) ...))
|
|However, the ordering is still defined separately for both insert and
|lookup. This is a) tedious (especially given that in a real tree code
|there is likely to be >> 2 functions) and b) makes it possible,
|though perhaps not likely, that different ordering functions are
|passed to insert and lookup.
(define (make-tree-type <)
(lambda (message)
(cond ((eq? message 'insert) (lambda (key value tree) ...))
((eq? message 'lookup) (lambda (key tree) ...))
...)))
Unless the system optimises out the lookup (when possible) this
approach is significantly slower than where a direct function call is
made. Does anyone know of an available Scheme system that does
optimise the above type of code into direct calls? If not, then I'd
appreciate hearing about other solutions.