Partial Evaluation for Lazy Functional Languages 
Author Message
 Partial Evaluation for Lazy Functional Languages

I hear someone managed to write mix for a lazy higher order language
with strong typing. Does anyone know anything about this? Maybe an ftp
site where I could get a paper or some source? or at least a reference?

Thanx, John Heron
*** I don't speak for Network General



Sun, 27 Jul 1997 06:32:07 GMT  
 Partial Evaluation for Lazy Functional Languages
   I hear someone managed to write mix for a lazy higher order language
   with strong typing. Does anyone know anything about this? Maybe an ftp
   site where I could get a paper or some source? or at least a reference?

{ Launchbury:phd:1989
, author=   "J. Launchbury"
, title=    "Projection Factorisation in Partial Evaluation"
, school=   "Department of Computer Science, Glasgow University"
, month=    nov
, year=     1989
, reffrom=  Launchbury:fplca:1991
, reffrom=  Consel:Danvy:fplca:1991
, reffrom=  Bondorf:acm:lfp:1992

Quote:
}


{ Launchbury:fplca:1991
, author=   "John Launchbury"

, title=    "A Strongly-Typed Self-Applicable Partial Evaluator"
, crossref= "fplca:1991"
, pages=    "145--164"
, refs=     23
, checked=  19940809
, source=   "Main library"
, abstract= "When attempting self-application of a partial evaluator
written in and for a strongly-typed language several problems arise
that do not seem to occur in the untyped world.  These problems have
hindered the production of a self-applicable partial evaluator in such
languages for a number of years.  In this paper we report on what is,
to the best of our knowledge, the first successful attempt to produce
such a partial evaluator and, in the process, we discuss some
theoretical aspects of partial evaluation raised by strong-typing."

Quote:
}

You might also be interested in :-

{ Birkedal:Welinder:msc:1993
, author=   "Lars Birkedal and Morten Welinder"
, title=    "Partial evaluation of Standard ML"
, school=   "Computer Science Department, University of Copenhagen"
, month=    aug
, year=     1993
, reffrom=  Lawall:Danvy:acm:lfp:1994
Quote:
}



Sat, 02 Aug 1997 17:23:49 GMT  
 Partial Evaluation for Lazy Functional Languages

Quote:

>   I hear someone managed to write mix for a lazy higher order language
>   with strong typing. Does anyone know anything about this? Maybe an ftp
>   site where I could get a paper or some source? or at least a reference?

[references deleted]

All of these references deal with strict languages. Laziness gives
further problems for partial evaluation, unless you use a simple
strategy without memoization, like lambda-mix [1]. The usual strategy
in partial evaluation is to specialize a function with respect to its
known (static) arguments. Thus, the specialized function is identified
by a pair of the original function name and the values of the static
parameters. When a function call is processed, the partial evaluator
tests to see if it already has specialized an occurence of that
function with these static arguments. This, however, requires
comparison of the static arguments, which my not terminate in a lazy
language.

You can, of course, use the same strategies as for strict languages,
but as soon as you have a static infinite list, you get
non-termination.

Carsten Kehler Holst and John Hughes [2] have tried to attack the
problem by first solving a simpler one: making an interpreter for a
lazy language, which will detect that a loop has occurred, that is if
the same function is called with the same arguments. I believe Carsten
has worked further on this problem in his PhD thesis, which he is
writing on at this time.



  author =      "C.K. Gomard and N.D. Jones",
  title =       "A Partial Evaluator for the Untyped Lambda-Calculus",
  journal =     "Journal of Functional Programming",
  year =        "1991",
  volume =      "1",
  number =      "1",
  pages =       "21-69",
  month =       "January",
  OPTnote =     ""}


  author =      "C.K. Holst and J. Hughes",
  title =       "A Loop-Detecting Interpreter for Lazy Programs",
  booktitle =   "Draft Proceedings, Fourth Annual Glasgow Workshop on
                 Functional Programming, Skye, Scotland",
  year =        "1991",
  OPTeditor =   "",
  pages =       "199-209",
  organization = "Glasgow University",
  OPTnote =     ""}



Tue, 05 Aug 1997 19:07:36 GMT  
 Partial Evaluation for Lazy Functional Languages

|>    I hear someone managed to write mix for a lazy higher order language
|>    with strong typing. Does anyone know anything about this? Maybe an ftp
|>    site where I could get a paper or some source? or at least a reference?
|>

|> { Launchbury:phd:1989
|> , author=   "J. Launchbury"
|> , title=    "Projection Factorisation in Partial Evaluation"
|> , school=   "Department of Computer Science, Glasgow University"
|> , month=    nov
|> , year=     1989
|> , reffrom=  Launchbury:fplca:1991
|> , reffrom=  Consel:Danvy:fplca:1991
|> , reffrom=  Bondorf:acm:lfp:1992
|> }
|>
|>

|> { Launchbury:fplca:1991
|> , author=   "John Launchbury"

|> , title=    "A Strongly-Typed Self-Applicable Partial Evaluator"
|> , crossref= "fplca:1991"
|> , pages=    "145--164"
|> , refs=     23
|> , checked=  19940809
|> , source=   "Main library"
|> , abstract= "When attempting self-application of a partial evaluator
|> written in and for a strongly-typed language several problems arise
|> that do not seem to occur in the untyped world.  These problems have
|> hindered the production of a self-applicable partial evaluator in such
|> languages for a number of years.  In this paper we report on what is,
|> to the best of our knowledge, the first successful attempt to produce
|> such a partial evaluator and, in the process, we discuss some
|> theoretical aspects of partial evaluation raised by strong-typing."
|> }
|>
|>
|> You might also be interested in :-
|>

|> { Birkedal:Welinder:msc:1993
|> , author=   "Lars Birkedal and Morten Welinder"
|> , title=    "Partial evaluation of Standard ML"
|> , school=   "Computer Science Department, University of Copenhagen"
|> , month=    aug
|> , year=     1993
|> , reffrom=  Lawall:Danvy:acm:lfp:1994
|> }

Note that none of the above papers really treat the issue of laziness in
partial evaluation. Launchbury only implements his mix on top of
a lazy languages, but this doesn't say anything about partial evaluation
for lazy languages. The closest you can get to the issue of partial evaluation
and laziness is Gomard and Holst's PEPM'91 paper:

  author =      "C.K. Holst and C.K. Gomard",
  title =       "Partial Evaluation is Fuller Laziness",
  booktitle =   PEPM,
  year =        "1991",
  pages =       "223-233",
  publisher =   ACM,
  OPTnote =     ""}

Regards,

-- Dirk



Tue, 05 Aug 1997 20:30:53 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Lazy-evaluation functional language for MS DOS

2. Functional Programming Languages with Lazy Evaluation

3. Parial Evaluation & Lazy Functional Language

4. Partial Evaluation & Lazy functionallanguage

5. Speed of FP languages, prospects (was Re: Benchmarking Lazy Functional Languages)

6. Special issue of J. Functional Programming on Partial Evaluation

7. Special issue of J. Functional Programming on Partial Evaluation

8. Special issue of J. Functional Programming on Partial Evaluation

9. Special issue of J. Functional Programming on Partial Evaluation

10. Special issue of J. Functional Programming on Partial Evaluation

11. lazy.dylan 0.1 -- add ML/Scheme-style lazy evaluation to Dylan

12. Information about lazy evaluation in imperative languages

 

 
Powered by phpBB® Forum Software