curried function calling
Alan Baljeu
h = g 4
The first line takes +, attaches a 3 as the first argument, and assigns the
result to g.
The second line takes g, attaches 4 as the next argument to +, calls +, and
assigns the result to h.
There appears to be two things happening under one syntax: attaching
parameters, and calling functions. What would happen if these were
segregated?
E.g., suppose # were the cause-evaluation operator. Suppose we had to do:
g = (+) 3
h = g 4
i = #h
(Of course you could write #(+ 3 4) (or #((+ 3) 4), and we could come up
with some sugarizing rules so you don't need the # in direct application.)
Would the resulting language be less capable in any substantial way, or are
there simple program transformations to convert one language to the other?
Alan
gr...@cs.uwa.edu.au
: g = (+) 3
: h = g 4
: The first line takes +, attaches a 3 as the first argument, and assigns the
: result to g.
: The second line takes g, attaches 4 as the next argument to +, calls +, and
: assigns the result to h.
These lines don't _do_ anything. They are just rules that the interpreter
will follow if the interpreter (or runtime system) wants to do something.
: There appears to be two things happening under one syntax: attaching
: parameters, and calling functions.
The second line does not call +, so it is no different to the first
line - it attaches the argument and assigns the result to the name.
The interpreter reads the rules and binds the names, but it will only
evaluate h if and when it needs to, not as soon as it reads the rule.
: E.g., suppose # were the cause-evaluation operator.
Haskell's cause-evaluation operator is called `seq`.
: Suppose we had to do:
: g = (+) 3
: h = g 4
: i = #h
Do you mean # to indicate that the value should be computed at compile
instead of deferred to runtime? An interesting proposal: It seems like
a handy thing to have, since the compiler can't evaulate all constants
at compile-time, (lest they turn out to be infinite, or just too large
to put in the binary when we don't know if they will really be needed)
but there are certainly examples of programs where start-up time might
be reduced by evaluating some things beforehand. I'm not aware of such
a mechanism, but it seems so useful that it should exist, and probably
ought to be part of the standard, rather than being compiler-specific.
-Greg
William Lovas
> g = (+) 3
> h = g 4
>
> The first line takes +, attaches a 3 as the first argument, and assigns the
> result to g.
> The second line takes g, attaches 4 as the next argument to +, calls +, and
> assigns the result to h.
>
> There appears to be two things happening under one syntax: attaching
> parameters, and calling functions. What would happen if these were
> segregated?
Actually, only one thing is happening -- expressions are being evaluated.
In the first line, the expression happens to evaluate to a function, which
is the essence of curried functions: instead of taking 2 arguments, (+)
takes one argument and returns a function that takes one argument and
returns a value. A plausible type signature (in no particular syntax)
might be:
(+) : integer -> integer -> integer
which parses as:
(+) : integer -> (integer -> integer)
After applying (+) to 3, g has type `integer -> integer', and after
applying this resulting value to 4 you get an `integer'. Make sense?
The real difference between the two lines is the type of the returned
value.
> Would the resulting language be less capable in any substantial way, or are
> there simple program transformations to convert one language to the other?
The resulting language would be conceptually more complex -- it would have
both regular expressions and strange "partially evaluated" expressions, or
"functions with some arguments attached". You would be sacrificing the
mathematical beauty that curried function application buys you. There's no
apparent reason to take such a leap -- it doesn't result in any more power,
but it complicates the implementation and makes the semantics more obscure.
Hope this helps,
William
Tim Sweeney
The way you're describing this code reflects the LISP view of
programming, where there is such a thing as a "function with a
parameter attached to it", and that "evaluating the function with the
parameter attached to it" produces the resulting value.
That concept doesn't exist in most languages. For example, in
Haskell,
g = (+) 3
applies the function (+) to the argument 3, and binds the result to
"g". The function (+) takes a number parameter A, and returns a new
function that takes a different number parameter B and returns A+B.
Thus "g" is bound to a function that takes a number B and returns B+3.
In this view, functions can return functions, and functions take take
functions as parameters. So there is no such thing as "binding a
parameter to a function" here, just calling a function with a
parameter, which produces a result.
To get a better understanding of the differences in view, it's useful
to look at a simple implementation of a lambda expression evaluator in
Haskell, where you'll see that the primitive pieces of code are
functions (lambdas), constants, and function calls -- there isn't any
such thing as a "function with a parameter attached". Then compare to
LISP evaluators where quoted lists are literally considered to be
"functions with parameters attached", which can later be evaluated to
produce results.
Alan Baljeu
news:9ef8dc7.03040...@posting.google.com...
> Alan,
>
> The way you're describing this code reflects the LISP view of
> programming, where there is such a thing as a "function with a
> parameter attached to it", and that "evaluating the function with the
> parameter attached to it" produces the resulting value.
To you and all the other responses, thanks for replying.
You are correct that I'm presenting a view of programming
akin to LISP. I also understand lambda calculus, lazy-evaluation,
beta reduction, etc., and have no questions about how it works or
what you can do with it.
I guess I want to compare the semantics of a "normal, pure,
eager, curried" system with that of a system doesn't do real
currying, but instead collects parameters until an explicit
function call (e.g., using #) is made.
My question is, whether there any real, practical loss of
functionality?
For example
map : ((A->B), [A]) -> [B]
map f [] = []
map f [a|aa] = [#(f a) | #(map f aa)]
In this system, f must be a function of one parameter, which
when evaluated can return a value of any type, including a
function. However, since function calling must be explicit,
you couldn't write:
let x = #(map + [1,3,5]) in #(head x 3)
because head has type ([A])->A. Instead you would need to write:
let x = #(map + [1,3,5]) in #(#(head x) 3)
This is more work, but is it only more work, or does this restriction
limit the kinds of higher-order functions you could construct? Are
there practical examples of such functions?
<aside>
I suppose the type signature of # would be # : (() -> A) -> A except
it's really a special operator, and not a function according to this
system.
</aside>
This is ugly, I know. I only ask because I'm interested in language
features and I'm just thinking about different ways to construct
functions, and this idea came up.
Tim Sweeney
are isomorphic to functions of the form (a,b)->c. In other words, you
can trivially translate functions and calls from one form to the other
and back without losing any information or changing the semantics.
So the only practical question is, which form is more convenient for a
given situation?
- Map tends to be more convenient in curried form because often you're
looking for a function [a]->[b], and can conveniently obtain the right
one with map(f). Whereas, in uncurried form, you would need to
express this as lambda(x::[a])->map(f,x) which is more verbose.
- For functions like addition, you almost always call it with two both
arguments present, so add(a,b) may be more convenient than add(a)(b).
Some languages bring additional benefits to uncurried form. For
example, with support for variable-length arrays, you could just as
easily define "add" to take an array of numbers and have
add(a,b,c,d)=a+b+c+d, add(a,b)=a, add(a)=a, and add()=0 which are
often convenient.
> <aside>
> I suppose the type signature of # would be # : (() -> A) -> A except
> it's really a special operator, and not a function according to this
> system.
> </aside>
In LISP, that kind of operator is useful because you can first-class
write code (in your language itself, not just in the compiler) that
traverses these "unevaluated expressions" and transforms them in
interesting ways. This is so powerful in LISP because it's done in an
untyped way: you can traverse an expression and turn it into anything
imaginable, and if there are any type violations, they only show up at
runtime. Thus compile-time typechecking doesn't impose any
limitations on how you can traverse stuff.
In a strongly-typed and simply-typed language like Haskell, your #
operator can be implemented directly in the language as "call ::
lambda(f::t->u)->lambda(x::t)->f(x)", which obeys the rule
"call(f)(x)=f(x)" and therefore "call(f)=f" -- so it turns out to just
be the identity function. So, it doesn't add any expressive power to
the language. The type system restricts you to only writing code
that's well-typed, so the neat expression-traversal features of LISP
go away.
Overall, I think the conclusion is that the "#" operator brings your
language new capabilities if and only if your language is untyped.
> This is ugly, I know. I only ask because I'm interested in language
> features and I'm just thinking about different ways to construct
> functions, and this idea came up.
LISP from the 1970's pretty much represents the apex of untyped
languages. It does all of the interesting things that are doable and
does them very simply, leaving most of the further debate to
subjective issues like syntax.
The really interesting and hard problems outstanding in language
design are in extending the power of strongly-typed languages. Here
are some cool papers I recommend checking out, covering language
features that do add significant new expressive power:
http://www.cs.caltech.edu/~jyh/papers/fool3/default.html
http://www.autoreason.com/ontic-spec.ps
Lauri Alanko
> I guess I want to compare the semantics of a "normal, pure,
> eager, curried" system with that of a system doesn't do real
> currying, but instead collects parameters until an explicit
> function call (e.g., using #) is made.
>
> My question is, whether there any real, practical loss of
> functionality?
There is a performance issue:
matchStr :: String -> String -> Maybe [String]
matchStr = \re ->
let rx = mkRegex re in \str -> matchRegex rx str
Now a partially applied (matchStr re) has already done the regexp
compilation, and each application to a string can use the precompiled
regexp. In contrast:
matchStr2 :: (String,String) -> Maybe [String]
matchStr2 (re, str) = matchRegex (mkRegex re) str
If the arguments to this function are merely being "collected" by some
kind of a partial application, then each final application will compile
the regular expression again and again.
This is the theory, anyway. In practice, compiler optimizations may do
hoisting, inlining and eta expansion and the result may be
unpredictable...
Lauri Alanko
l...@iki.fi
Joachim Durchholz
> "Alan Baljeu" <aba...@sympatico.deleteme.ca> quoth:
>>My question is, whether there any real, practical loss of
>>functionality?
>
> compilation, and each application to a string can use the precompiled
> regexp.
This depends on what "collecting a parameter" means.
If it means "evaluate the parameter and keep the result around", there
should be no difference.
If it means "keep the unevaluated parameter", then there is indeed a
difference.
In practice, I don't think that anybody in his right mind would choose
the second semantics. It's both slower and more difficult to implement.
Just my 2c.
Regards,
Jo
--
Currently looking for a new job.
Benjamin Ylvisaker
t...@epicgames.com (Tim Sweeney) wrote:
> The really interesting and hard problems outstanding in language
> design are in extending the power of strongly-typed languages. Here
> are some cool papers I recommend checking out, covering language
> features that do add significant new expressive power:
>
> http://www.cs.caltech.edu/~jyh/papers/fool3/default.html
> http://www.autoreason.com/ontic-spec.ps
And some more:
http://www-2.cs.cmu.edu/afs/cs/user/aleks/www/papers.html
The paper on meta-programming contradicts your assertion that one can
only do meta-programming in untyped languages.
Benjamin
Alan Baljeu
> In any ordinary programming situation, functions of the form a->b->c
> are isomorphic to functions of the form (a,b)->c. In other words, you
> can trivially translate functions and calls from one form to the other
> and back without losing any information or changing the semantics.
That's what I was looking for. Thanks.
> > <aside>
> > I suppose the type signature of # would be # : (() -> A) -> A except
> > it's really a special operator, and not a function according to this
> > system.
> > </aside>
>
> In LISP, that kind of operator is useful because you can first-class
> write code (in your language itself, not just in the compiler) that
> traverses these "unevaluated expressions" and transforms them in
> interesting ways. This is so powerful in LISP because it's done in an
> untyped way: you can traverse an expression and turn it into anything
> imaginable, and if there are any type violations, they only show up at
> runtime. Thus compile-time typechecking doesn't impose any
> limitations on how you can traverse stuff.
I believe it is actually the presence of eval/compile/defmacro that provide
this capability, and not call. In this hypothetical language with a #
operator, whether checked or not, no additional capability appears, unless
methods can analyze the structure of its parameters. If there's more there,
I'm not seeing it. It seems like nothing more than you could do by
constructing and passing around partially applied functions.
Ketil Malde
> Lauri Alanko wrote:
>> Now a partially applied (matchStr re) has already done the regexp
>> compilation, and each application to a string can use the precompiled
>> regexp.
> This depends on what "collecting a parameter" means. If it means
> "evaluate the parameter and keep the result around", there should be
> no difference.
Eh, I'm not sure I follow you here. If you have:
matchStr re str = let cr = compileRe re in applyCr cr str
Wouldn't compileRe be evaluated every time you apply (matchStr re) to
a new string? A partially applied function could have the 'cr'
already evaluated, and only perform the 'applyCr' part to each
pattern.
-kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Dirk Thierbach
> I guess I want to compare the semantics of a "normal, pure,
> eager, curried" system with that of a system doesn't do real
> currying, but instead collects parameters until an explicit
> function call (e.g., using #) is made.
> you couldn't write:
>
> let x = #(map + [1,3,5]) in #(head x 3)
>
> because head has type ([A])->A. Instead you would need to write:
>
> let x = #(map + [1,3,5]) in #(#(head x) 3)
This means that every application of an argument has to be prefixed
with a function evaulation.
> My question is, whether there any real, practical loss of
> functionality?
Obviosly not, because there is a straight-forward translation from
every lambda term to your system (by inserting the # in every application).
I more interesting question is, what would you gain from that? The way
you propose wouldn't allow you to write terms that are really
different from lambda terms.
If you relax the above condition and allow a function to "collect"
several arguments before the "function call", e.g. #(f x y) instead of
#( #(f x) y), you gain some expressiveness. You could use such
constructs to control the evaluation strategy (lazy vs. eager: for
lazy, the # appears only on ground types in case statements; for eager,
the # appears again in every application). You could maybe also use
something similar for some sort of "staged computation" (i.e., some sort of
macros: Control over which expressions get reduced already at "compile
time" (stage 1) and which at "runtime" (stage 0), with possibly more
"stages").
Frank Pfenning and others did some research about this topic, google
or citeseer should be able to find it.
> <aside>
> I suppose the type signature of # would be # : (() -> A) -> A except
> it's really a special operator, and not a function according to this
> system.
> </aside>
Another idea for a fitting type system is to introduce a new type
operator. This is usually written as a box, though as ASCII
representation # is probably also acceptable. So you can have a
function of type
f :: A -> B -> #C
which must be evaluated as #(f x y), while a function of type
f :: A -> #(B -> #C) must be evaluated as #( #(f x) y).
Variants are of course possible.
It is well known that the simple lambda type system corresponds to
the implication fragment of the "usual" logic, and what happens here is
that you switch to a modal logic (of which there are several flavours,
choose the one that suits you best).
> This is ugly, I know. I only ask because I'm interested in language
> features and I'm just thinking about different ways to construct
> functions, and this idea came up.
So maybe the above remarks are interesting to you.
- Dirk
Joachim Durchholz
> Joachim Durchholz <joac...@gmx.de> writes:
>
>>Lauri Alanko wrote:
>>>Now a partially applied (matchStr re) has already done the regexp
>>>compilation, and each application to a string can use the precompiled
>>>regexp.
>
>>This depends on what "collecting a parameter" means. If it means
>>"evaluate the parameter and keep the result around", there should be
>>no difference.
>
> Eh, I'm not sure I follow you here. If you have:
>
> matchStr re str = let cr = compileRe re in applyCr cr str
>
> Wouldn't compileRe be evaluated every time you apply (matchStr re) to
> a new string? A partially applied function could have the 'cr'
> already evaluated, and only perform the 'applyCr' part to each
> pattern.
This depends entirely on whether the compiler is smart enough to detect
that cr always evaluates to the same value. (Which should be trivial
unless compileRe calls out to C.)