[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
Re: [Haskell-cafe] Partial Evaluation
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 [EMAIL PROTECTED] 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.___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Partial Evaluation
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. b ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Partial Evaluation
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: [EMAIL PROTECTED] [mailto:haskell-cafe- [EMAIL PROTECTED] 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
