I am reading Hudak's paper Modular Domain Specific Languages and Tools [1] and am confused by his use of the term `Partial Evaluation'. I understand it to mean supplying some but not all arguments to a function, e.g. (+3) but it seems to mean something else too. This is in the context of optimising performance: "We have used existing partial evaluation techniques to do this...Unfortunately, there does not currently exist a suitable, easy-to-use partial evaluator for Haskell. Our approach was to convert the Haskell program to Scheme, partially evaluate the Scheme program, and then translate back into Haskell." What does P.E, mean here? Thanks, [1] Available http://wiki.ittc.ku.edu/lambda/Image:Hudak-Modular_Domain_Specific_Languages...
Hello, Partial evaluation in this context (programming languages research) usually refers to "compile time" optimization techniques such as statically evaluating as much of a function as possible (e.g. going into the function body and evaluating as much as possible that doesn't depend on the function arguments) and various syntactic transformations to improve run-time efficiency. You can find lots of information about this topic at: http://partial-eval.org. -Jeff haskell-cafe-bounces@haskell.org wrote on 03/21/2007 02:47:28 PM:
I am reading Hudak's paper Modular Domain Specific Languages and Tools [1] and am confused by his use of the term `Partial Evaluation'. I understand it to mean supplying some but not all arguments to a function, e.g. (+3) but it seems to mean something else too. This is in the context of optimising performance:
"We have used existing partial evaluation techniques to do this...Unfortunately, there does not currently exist a suitable, easy-to-use partial evaluator for Haskell. Our approach was to convert the Haskell program to Scheme, partially evaluate the Scheme program, and then translate back into Haskell."
What does P.E, mean here?
Thanks,
[1] Available http://wiki.ittc.ku.edu/lambda/Image:Hudak- Modular_Domain_Specific_Languages_and_Tools.pdf
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
--- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.
jim burton wrote:
I am reading Hudak's paper Modular Domain Specific Languages and Tools [1] and am confused by his use of the term `Partial Evaluation'. I understand it to mean supplying some but not all arguments to a function, e.g. (+3) but it seems to mean something else too.
That's partial application you're thinking of. In the context of inline
operators, this is referred to as a section.
Partial evaluation actually executes some of a partially applied
function, generating a new function that is specialised to the given
arguments.
Here's a silly, contrived example to illustrate the difference.
Consider this function:
sumPlus :: Num a => [a] -> a -> a
sumPlus xs y = sum xs + y
Here's a partially applied version of the function:
sumPlus ([3,2] :: [Int])
Its type is
Int -> Int
If you partially evaluate this function, you're evaluating as much of
the function as possible at "compile time" (usually in a separate
partial evaluation tool that generates a whole new source file for the
real compiler), and getting a new specialised function:
sumPlus32 :: Int -> Int
sumPlus32 y = 5 + y
You could expect a decent compiler to apply this kind of transformation
under limited circumstances, but partial evaluation is much more
ambitious. The canonical example is partially evaluating a language
interpreter by giving it a chunk of source as the input to specialise
on. This produces a new interpreter that is specialised to interpret
exactly that source (aka the first Futamura projection), and which you
might hope would do so more efficiently than the fully general interpreter.
I think you are confusing "partial application" and "partial evaluation". Though they are conceptually related. The former is what happens when you apply a function of arity N to M arguments, where M < N. In Haskell the partially applied function is suspended, pending the rest of its arguments. The latter is a way of taking a program and _some_ of its inputs and transforming/compiling/specialising it into a residual program, by "evaluating" as much as possible, given the inputs you have available. An interesting example of partial evaluation is to take an interpreter for a language and a sample source program, and partially evaluate the interpreter with respect to the program. The result is a version of the interpreter which acts effectively as a compiled version of the source program. In Hudak's paper(s), if I remember correctly, they have an interpreter for a functional language (in continuation passing style), which is parameterised by a monitor function. I think they are trying to argue that you can make the system more efficient if you partially evaluate the interpreter with respect to a particular monitor. It is better than running the interpreter directly. The problem is that I think it is hard to scale to a language like Haskell, though there might have been advances that I am not familiar with. Wikipedia has an entry on partial evaluation which is somewhat useful, though you should probably follow the references at the bottom. Cheers, Bernie.
-----Original Message----- From: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe- bounces@haskell.org] On Behalf Of jim burton Sent: 21 March 2007 18:47 To: haskell-cafe@haskell.org Subject: [Haskell-cafe] Partial Evaluation
I am reading Hudak's paper Modular Domain Specific Languages and Tools [1] and am confused by his use of the term `Partial Evaluation'. I understand it to mean supplying some but not all arguments to a function, e.g. (+3) but it seems to mean something else too. This is in the context of optimising performance:
"We have used existing partial evaluation techniques to do this...Unfortunately, there does not currently exist a suitable, easy-to-use partial evaluator for Haskell. Our approach was to convert the Haskell program to Scheme, partially evaluate the Scheme program, and then translate back into Haskell."
What does P.E, mean here?
Thanks,
[1] Available http://wiki.ittc.ku.edu/lambda/Image:Hudak- Modular_Domain_Specific_Languages_and_Tools.pdf
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
participants (4)
-
Bernie Pope -
Bryan O'Sullivan -
Jeff Polakow -
jim burton