Higher-order function application
In Haskell, only a single notion of "function application" exists, where a function f::t-u is passed a parameter of type t, returning a result of type u. Example function calls are: 1+2 sin 3.14 map sin [1:2:3] However, a higher-order notion of function application seems sensible in many cases. For example, consider the following expressions, which Haskell rejects, despite an "obvious" programmer intent: cos+sin-- intent: \x-((cos x)+(sin x)) cos(sin) -- intent: \x-cos(sin(x)) (cos,sin)(1,2) -- intent: cos(1),sin(2) (+)(1,2) -- intent: (+)(1)(2) cos [1:2:3]-- intent: map cos [1:2:3] From this intuition, let's postulate that it's possible for a compiler to automatically accept such expressions by translating them to the more verbose "intent" listed above, using rules such as: 1. Operator calls like (+) over functions translate to lambda abstractions as in the "cos+sin" example. 2. A pair of functions f::t-u, g::v-w acts as a single function from pairs to pairs, (f,g)::(t,u)-(v,w). 3. Translating function calling into function composition, like "cos(sin)". 4. Automatic currying when a pair is passed to a curried function. 5. Automatic uncurrying when a function expecting a parameter of type (t,u) is passed a single value of type t. 6. Applying a function f:t-u to a list x::[t] translates to "map f x". I wonder, are these rules self-consistent? Are they unambiguous in all cases? Are there other rules we can safely add? It also seems that every statement above is simply a new axiom at the type checker's disposal. For example, to describe the general notion of "cos+sin" meaning "\x-(cos(x)+sin(x))", we say: for all types t,u,v, for all functions f,g :: t-u, for all functions h ::u-u-v, h (f,g) = \x-h(f(x),g(x)). Is this "higher order function application" a useful notion, and does any research exist on the topic? -Tim
Re: Higher-order function application
Hi Tim, Tim 6. Applying a function f:t-u to a list x::[t] translates to Tim "map f x". the problem is that we loose much of the strength the Haskell type system provides and a lot of programming errors will remain undetected. What you can do is write a preprocessor that provides a nicer syntax for you. Cheers -- Christoph Herrmann E-mail: [EMAIL PROTECTED] WWW: http://brahms.fmi.uni-passau.de/cl/staff/herrmann.html
Re: Higher-order function application
Tim Sweeney:
Is this "higher order function application" a useful notion, and does any
research exist on the topic?
The answer to the first question is "yes, when it matches the intuition of
the programmer". Your two first examples:
cos+sin-- intent: \x-((cos x)+(sin x))
cos(sin) -- intent: \x-cos(sin(x))
have equivalents in Fortran 90 and HPF, although with arrays rather than
functions. For instance, one can write "A+B" to mean an array with value
A(I)+B(I) for all indices I, and A(B) for the array with elements A(B(I))
(provided B is an integer array whose elements all are valid indices for
A). This feature is widely used in array languages, where it is seen as an
intuitive and convenient notation to express array operations. I definitely
believe it could be useful also for operations over other data structures.
The answer to the second question is "surprisingly little". There is, for
instance, no formal description to be found of the Fortran 90 array
operations and how they type. But it is quite straightforward to define
type systems and type checking algorithms for this, when the language is
explicitly typed. One example is
@InProceedings{Thatte-ScalingA,
author = {Satish Thatte},
title ={Type Inference and Implicit Scaling},
booktitle ={ESOP'90 -- 3rd European Symposium on Programming},
editor = {G. Goos and J. Hartmanis},
number = 432,
series = {Lecture Notes in Computer Science},
year = 1990,
publisher ={Springer-Verlag},
address = {Copenhagen, Denmark},
month =may,
pages ={406--420}
}
where a type system for an APL-inspired overloading in an FP-like language
is described. This approach is based on subtyping.
A student of mine is pursuing another, more direct approach, where a
coercive type system is used to resolve the overloading at compile time
through a combined rewrite and type check. He did this for an explicitly
typed variant of Core ML, and this is reported in his Licentiate thesis
("file://ftp.it.kth.se/Reports/paradis/claest-licthesis.ps.gz"):
@PHDTHESIS{claest-lic,
AUTHOR = {Claes Thornberg},
TITLE = {Towards Polymorphic Type Inference with Elemental Function
Overloading},
SCHOOL = it,
ADDRESS = {Stockholm},
YEAR = {1999},
TYPE = {Licentiate thesis},
MONTH = may,
NOTE = {Research Report } # rep-id # {99:03}
}
@STRING{it = "Dept.\ of Teleinformatics, KTH"}
@STRING{rep-id = "TRITA-IT R "}
When the type system is implicit (inference rather than checking), however,
less is known. You can do some tricks with the Haskell class system (for
instance, defining functions between instances of Num to be instances of
Num themselves, which then lets you overload numerical operations like "+")
but this solution has some restrictions and is also likely to lead to
run-time overheads. We would like to have something better.
Finally, there is an interesting discussion of this overloading business,
for array- and data parallel languages, in
@ARTICLE{Sip-Blel-Coll-Lang,
AUTHOR = {Jay M. Sipelstein and Guy E. Blelloch},
TITLE = {Collection-Oriented Languages},
JOURNAL = {Proc.\ {IEEE}},
YEAR = {1991},
VOLUME = {79},
NUMBER = {4},
PAGES = {504--523},
MONTH = apr
}
For instance, they bring up the possible conflicts which may occur when
trying to resolve this overloading for operations over nested data
structures. (A witness is length l, where l :: [[a]]: should it be just
length l, or resolved into map length l?)
Björn Lisper
RE: code generation for other languages
For doinjg this sort of thing I have used asdl before
which I find really useful.
-Original Message-
From: Manuel M. T. Chakravarty [mailto:[EMAIL PROTECTED]]
Sent: 23 August 2000 14:09
To: [EMAIL PROTECTED]
Cc: [EMAIL PROTECTED]
Subject: Re: code generation for other languages
Jeffrey Straszhiem [EMAIL PROTECTED] wrote,
On Wed, Aug 23, 2000 at 12:26:38PM +1000, Timothy Docker wrote:
I'm writing a haskell program that generates C++ code based upon
some haskell data structures. At the moment, the code is somewhat
ugly with lots of stuff like
mutatorDef structName (name,vtype) =
"inline void\n" ++
structName ++ "::" ++ (mutatorName name) ++
"( " ++ (cppParamType vtype) ++ " v ) {\n" ++
"" ++ (storageName name) ++ " = v;\n" ++
"}\n\n"
All those ++ operators working on raw strings bug me, and manually
getting the indentation correct is a pain. Is there a more
functional approach to generating source code? I thought
this could
be a common enough task that there could be a library,
but a perusal
of haskell.org didn't seem to show anything relevant.
To make matters worse, you're likely getting lousy
efficiency with all
of the ++ operators. Look through the code for showS in the Prelude
for better ways to hook strings together. Paul Hudak talks
about the
efficient use of the show functions at:
http://www.haskell.org/tutorial/stdclasses.html
Now, with regard to the code being ugly, my suggestion would be to
check out some of the pretty printer libraries out there,
and to look
through them. They basically solve a similar problem, except they
first parse a normal program into a tree, then flatten the tree in a
standard way. In your case you'll likely build the tree directly,
then call the final stages of the pretty printer. There is no
shortage of pretty printer libraries for Haskell, or for FP in
general.
The canonical approach is to define an internal data
structure that represents C++ code, then let your mutator
functions generate values of that data type (instead of
strings), and finally pretty print values of this C++ data
structure. That's cleaner and more flexible than the ++
cascades (or the show equivalent).
Depending on how restricted and/or idiomatic the generate
C++ code is, it makes sense to not have a data structure
that can represent arbitrary C++ programs, but only a subset
that is relevant for the code generation task at hand. So,
you might want functions like
mutatorDef :: ... - AbstractCPlusPlus
prettyPrintACPP :: AbstractCPlusPlus - String
Cheers,
Manuel
Job openings at INRIA
[Apologies for multiple copies] Job openings in formal methods for smartcards at INRIA == INRIA is opening up several doctoral and post-doctoral positions at Rocquencourt (projet Coq), Rennes (projet Lande) and Sophia-Antipolis (projets Lemme and Oasis). All positions are related to projects aimed at applying formal methods to the verification of the JavaCard platform and of JavaCard applications. Most projects are carried out in collaboration with leading industrial companies in the field (Bull, Gemplus, Schlumberger) and offer a unique opportunity to address scientifically challenging and industrially relevant problems. We seek candidates with a strong background in any of the following fields: - theorem-provers - model-checkers - program analysis and transformation and a strong interest in smartcard and mobile code security. To apply (or for further details) please send an email to: Gilles Barthe ([EMAIL PROTECTED]) http://www-sop.inria.fr/oasis/personnel/Gilles.Barthe/index.html Yves Bertot ([EMAIL PROTECTED]) http://www-sop.inria.fr/lemme/Yves.Bertot/index.html Thomas Jensen ([EMAIL PROTECTED]) http://www.irisa.fr/lande/jensen/index.html Christine Paulin ([EMAIL PROTECTED]) http://www.lri.fr/~paulin Your email application should include a CV, names and addresses of three referees, and, if available, pointers to on-line articles (please do *not* include the articles in your mails). You should also indicate your geographical preferences, if any. Applications will be evaluated from now on until the positions are filled.
REMINDER: ICFP Programming Contest - Task to be posted this Saturday 17:00 EST
[Please note that the task for the ICFP Programming Contest will be posted this Saturday, August 26, at 17:00 EST (5 pm).] We are pleased to announce: The Third Annual ICFP PROGRAMMING CONTEST August 26-29, 2000 http://www.cs.cornell.edu/icfp/ Convinced your favorite programming language provides unbeatable productivity? Do functional languages lead to better and faster programs? Perhaps it's just the case that functional programming languages attract better programmers than other languages...and you and your friends are the best of the best. If so, we're providing you the opportunity to prove it! We are pleased to announce the Third Annual ICFP Programming Contest to be held in conjunction with the 2000 International Conference on Functional Programming (ICFP'00). All programmers are invited to enter the contest, either individually or in teams; we especially encourage students to enter. You may use any programming language (or combination of languages) to show your skill. On Saturday, August 26 at 5pm EST, we will publish a challenge task to registered participants. Teams will have until Tuesday, August 29 at 5pm EST (72 hours) to implement a program to perform this task and submit it to the contest judges. We've designed the contest for direct, head-to-head comparison of language technology and programming skill. We have a range of prizes for the winners: cash awards, famous texts on functional languages donated and autographed by the authors, special student prizes, and, of course, unlimited bragging rights. For more information about the contest, prizes, and registration, point your browser to: http://www.cs.cornell.edu/icfp. For more information about ICFP 2000, see: http://diwww.epfl.ch/~odersky/icfp2000
REMINDER: PLI 2000 Early Registration Deadline this Friday, August 25th
PLI 2000 Principles, Logics, and Implementations of high-level programming languages Montréal, Canada September 17-22, 2000 http://www.cs.yorku.ca/pli00 This is a reminder that the early registration deadline for PLI 2000 is August 25th. You need to reserve by the end of this week in order to get the cheaper registration rates and hotel bookings. The colloquium on Principles, Logics, and Implementations of high-level programming languages is a collection of conferences and workshops aimed at the advancement of high-level programming languages. PLI 2000 comprises the following conferences and workshops: ICFPInternational Conference on Functional Programming PPDPPrinciples and Practice of Declarative Programming Haskell Workshop on Haskell HLCLHigh-Level Concurrent Languages HOOTS Higher Order Operational Techniques in Semantics RULERule-Based Programming Scheme Workshop on Scheme and Functional Programming SAIGSemantics, Applications and Implementation of Program Generation TIC Types in Compilation For further information and registration forms, see http://www.cs.yorku.ca/pli00
Re: code generation for other languages
Manuel M. T. Chakravarty writes: The canonical approach is to define an internal data structure that represents C++ code, then let your mutator functions generate values of that data type (instead of strings), and finally pretty print values of this C++ data structure. That's cleaner and more flexible than the ++ cascades (or the show equivalent). Depending on how restricted and/or idiomatic the generate C++ code is, it makes sense to not have a data structure that can represent arbitrary C++ programs, but only a subset that is relevant for the code generation task at hand. So, you might want functions like mutatorDef :: ... - AbstractCPlusPlus prettyPrintACPP :: AbstractCPlusPlus - String Thanks for the clear description (and to Julian Seward who also suggested such an approach). Alfter playing with the code a little more, I had actually already started down this approach. The tricky bit will be, as you say, defining a data structure that is "just" general enough. Tim
Re: Higher-order function application
Bjorn Lisper [EMAIL PROTECTED] writes: cos+sin-- intent: \x-((cos x)+(sin x)) cos(sin) -- intent: \x-cos(sin(x)) have equivalents in Fortran 90 and HPF, although with arrays rather than functions. For instance, one can write "A+B" to mean an array with value But I'd look at this differently: Essentially it means to have a typeclass Addable which is a superclass of Num and making vectors instances of Addable. (If Fortran9x also allows multiplication, we need no Addable and use Num directly.) OTOH, something like this is used in Xlisp-stat, and I hate it :-) (it does make programming harder, since I always have to think (or even worse, to experiment) whether some function will map itself over lists or not. (Xlisp-stat is even harder, since it uses lists as well as vectors. As a result of this "niceness", I have to write all my functions which might be passed as arguments to HOFs with a typecheck in order to find out whether the system's functions (like minimizers etc.) called them with a vector, a list, or a number). If one really needs to add functions argumentwise in a programm, one should IMHO use something like data (Num b) = NumFunction a b = NumFunction (a-b) instance (Num b) = Eq (NumFunction a b) where (NumFunction f) == (NumFunction g) = error "cannot eq funcs" instance (Num b) = Show (NumFunction a b) where show (NumFunction f) = error "cannot show funcs" -- one should use something smarter here instance (Num b) = Num (NumFunction a b) where (NumFunction f)+(NumFunction g) = NumFunction (\x-(f x)+(g x)) (NumFunction f)*(NumFunction g) = NumFunction (\x-(f x)*(g x)) (NumFunction f)-(NumFunction g) = NumFunction (\x-(f x)-(g x)) negate (NumFunction f) = NumFunction (negate . f) abs (NumFunction f) = NumFunction (abs . f) signum (NumFunction f) = NumFunction (signum . f) fromInteger x = NumFunction (\_ - fromInteger x) fromInt x = NumFunction (\_ - fromInt x) useFunc :: (Num b) = (NumFunction a b) - a - b useFunc (NumFunction f) = f -- example h::NumFunction Double Double h = (NumFunction cos) + (NumFunction sin) -- useFunc h 0.7 gives 1.40905987 -- usefunc 3 4 gives 3 -- useFunc (1+h*3) 0.01 gives 4.0298495 Ralf
