Lazy functional/logic programming 
Author Message
 Lazy functional/logic programming

Though Babel is _described_ as a lazy functional-logic language
(Moreno-Navarro and Rodriguez-Artalejo), the implementation described
by Andy Mueck ("CAMEL:  An Extension of the CAM to Compile Functional/Logic
Programs), and the implementation described by Kuchen, Loogen and
Moreno-Navarro (Graph-based Implementation of a Functional Logic Language)
are both strict.  What has been published wrt implementing _lazy_
functional-logic programming?  (By `lazy' I am not necessarily restricting
the topic to graph reduction, but any implementation that has the semantics
of normal-order evaluation).

I know that Uday Reddy discussed lazy narrowing in 1985,
and Darlington, in his paper on Absolute Set Abstraction + Hope,
suggested that lazy evaluation could be compatible with his idea,
But I am interested in implementations, not just theory.

A fairly recent paper by Hans, Loogen and Winkler, "On the Interaction
of Lazy Evaluation and Backtracking" (anybody know where this was
published -- my copy doesn't say), states that a lazy strategy
may lead to nontermination in combination with backtracking,
where an innermost strategy will determine a solution.
(e.g. where an argument has an infinite number of narrowings,
each of which will cause the function's first program clause to fail,
but which might succeed if the second program clause were tried).
They then describe a compromise strategy that avoids the problem
for many programs, but state that it is impossible to find a strategy
that is safe and avoids the nontermination problems of lazy narrowing
plus backtracking, in general.

I'm surprised that such a problem had not revealed itself earlier.
Is this indeed the first paper to seriously study the implementation
of lazy narrowing and/or lazy functional/logic programming?

I know that Tetsuo Ida and Satoshi Okui at University of Tsukuba, Japan,
have been doing experiments with lazy narrowing.  Is there any other
work I should be aware of?

------------------------------------------

Tulane University       New Orleans, Louisiana  USA



Wed, 28 Feb 1996 04:14:54 GMT  
 Lazy functional/logic programming

Quote:
Silbermann) writes:
>    [ A discussion on BABEL and lazy narrowing and a paper by Hans,
>      Loogen and Winkler omitted ]

>    Is this indeed the first paper to seriously study the implementation
>    of lazy narrowing and/or lazy functional/logic programming?

A paper with several references to the problem can be obtained
by anonymous ftp from potemkin.cs.pdx.edu, [131.252.20.145].
Look for the files with name "nns" and extension tex, dvi or ps.
The paper is about a narrowing strategy that performs only
narrowing step that are unavoidable (the essense of laziness,
I believe).

Sergio Antoy
Dept. of Computer Science
Portland State University
P.O.Box 751
Portland, OR 97207
voice +1 (503) 725-3009
fax   +1 (503) 725-3211



Thu, 29 Feb 1996 04:28:12 GMT  
 Lazy functional/logic programming

Quote:

>Is there any other work I should be aware of?

The following paper describes an extension of NU-Prolog with {lazy} function
definitions (which are transformed into Prolog).  There are other
similar proposals around.  There is a need for a good survey paper on
this topic....

        author =        {Lee Naish},
        title  =        {Adding equations to {NU-Prolog}},
        journal =       {Proceedings of The Third International
                        Symposium on
                        Programming Language Implementation and Logic
                        Programming},
        address =       {Passau, Germany},
        publisher =     {Springer-Verlag},
        series =        {Lecture notes in computer science},
        number =        {528},
        year   =        {August, 1991},
        pages  =        {15--26},
        comment   =     {Technical Report 91/2, Department of Computer
                        Science, University of Melbourne}

Quote:
}

        lee


Fri, 01 Mar 1996 14:30:24 GMT  
 Lazy functional/logic programming
|> ...
|> A fairly recent paper by Hans, Loogen and Winkler, "On the Interaction
|> of Lazy Evaluation and Backtracking" (anybody know where this was
|> published -- my copy doesn't say), ...
It is published as

        CROSSREF = {PLILP1992},
        AUTHOR = {Werner Hans and Rita Loogen and Stefan Winkler},
        TITLE = {On the Interaction of Lazy Evaluation and Backtracking},
        YEAR = 1992,
        PAGES = {355-369}
Quote:
}


        TITLE = {Programming Lanugage Implementation and Logic Programming},
        YEAR = 1992,
        BOOKTITLE = {Proc. PLILP '92},
        EDITOR = {M. Bruynooghe and M. Wirsing},
        PUBLISHER = {Springer},
        ADDRESS = {Leuven, Belgium},
        MONTH = aug,
        NOTE = {LNCS 631}

Quote:
}

|> ------------------------------------------

|> Tulane University New Orleans, Louisiana  USA

--
Peter Thiemann, Wilhelm-Schickard-Institut,           | Phone: x49 7071 29 5467
Sand 13, D-72076 Tuebingen, Germany                   | Fax:   x49 7071 29 5958



Fri, 01 Mar 1996 20:59:30 GMT  
 Lazy functional/logic programming
A first text on the implementation of lazy Babel is "Lazy Narrowing in a Graph
Machine" [1]. This paper also addresses the nontermination problem and
proposes a transformation scheme to a normal form -Uniform Babel programs. The
authors identify the source of the non-termination problem ---there is only a
finite number of rules matching a redex but a (possibly) infinite number of
outcomes--- and propose a program transformation that implements backtracking
in the proper order: try different reductions of arguments first, then try the
different rules for each reduction. There is a _implementation_ of the lazy
abstract machine (lBAM). You can contact us for more details.

This partially solved the nontermination problem but made some other more
evident. Subsequent research in the Babel project was aimed at dealing with
the interaction between laziness and backtracking. Note that normal order
reduction is just a "forward evaluation" concept. The paper "On the
Interaction of Lazy Evaluation and Backtracking" [2] can be found in the
proceedings of PLILP'92. Another intrinsic problem with the interaction of
laziness and nondeterminism is reevaluation -delayed computations may be
carried out several times. This was first discussed in a Compulog meeting in
Pisa, April 1992, I think. The re-evaluation problem suggests evaluating the
arguments of a function call as soon as possible. Of course, this should be
done without affecting (much) the lazy nature of the language.  For these
reasons, in [3,4] a new approach is taken: to use static analysis to detect
necessary reductions so that they be performed earlier, i.e. to safely control
the degree of operational laziness. This is called demandedness analysis
and can be seen as a broad generalization of the classical strictness analysis
for FP. The evaluation strategy in [3] is again a mixed one, not fully lazy.
This gets a little better in [4] which also includes a compilation scheme. The
overhead introduced by this scheme is overcome with the techniques in [5]. A
further extension to demandedness analysis will appear in [6].
--
                        ----------------------------------
                        Julio MARI~NO

                        LSIIS Dept/Facultad de Informatica
                        Universidad Politecnica de Madrid
                        28660-Boadilla del Monte (SPAIN)
                        PHO +34-1-336-7449(7464) Off(Lab)
                        FAX +34-1-336-7412
                        ----------------------------------


        author =        {J.J.~Moreno-Navarro and H.~Kuchen and R.~Loogen and
                            M.~Rodr\'{\i}guez-Artalejo},
        title  =        {Lazy Narrowing in a Graph Machine},
        journal =       {Proceedings of the 2nd International Conference on
                            Algebraic and Logic Programming},
        address =       {Nancy, France},
        publisher =     {Springer-Verlag},
        series =        {Lecture notes in computer science},
        number =        {463},
        year   =        1990,
        pages  =        {298--317},
        comment=        {RWTH-Aachen TR-90/11}

Quote:
}


        author =        {R.~Loogen and W.~Hans and S.~Winkler},
        title  =        {On the Interaction of Lazy Evaluation and
                            Backtracking},
        journal =       {Proceedings of the 4th International Symposium on
                            Programming Language Implementation and
                            Logic Programming},
        address =       {Leuven, Belgium},
        publisher =     {Springer-Verlag},
        series =        {Lecture notes in computer science},
        number =        {631},
        year   =        1992,
        pages  =        {355--369},

Quote:
}


        author =        {J.A.~Jim\'{e}nez-Mart\'{\i}n and J.~Mari\~{n}o and
                            J.J.~Moreno-Navarro},
        title  =        {Some Techniques for the Efficient Compilation of
                            Lazy Narrowing into Prolog},
        journal =       {Proceedings of LOPSTR'92},
        address =       {Manchester, UK},
        publisher =     {Springer-Verlag},
        series =        {Workshops in computer science},
        year   =        1993,

Quote:
}


        author =        {J.J.~Moreno-Navarro and H.~Kuchen and J.~Mari\~{n}o
                            and W.~Hans and S.~Winkler},
        title  =        {Efficient Lazy Narrowing using Demandedness
                            Information},
        journal =       {Proceedings of the fifth International Symposium on
                            Programming Language Implementation and
                            Logic Programming},
        address =       {Tallinn, Estonia},
        publisher =     {Springer-Verlag},
        series =        {Lecture notes in computer science},
        number =        {714},
        year   =        1993,
        pages  =        {167--183}

Quote:
}


        Author =        {Angel {Herranz Nieva}and Julio {Mari\~{n}o Carballo}},
        Title =         {Specialized Compilation of Lazy Functional Logic
                            Programs},
        Booktitle =     {Segundo Congreso Nacional de Programaci\'{o}n
                            Declarativa PRODE'93},
        Year =          1993,
        Address =       {Blanes, Girona},
        Note =          {Spanish Conference on Declarative Programming,
                            to appear},

Quote:
}


        author =        {Julio {Mari\~{n}o Carballo} and Angel {Herranz Nieva}
                            and J.J. {Moreno Navarro}},
        title =         {Demandedness Analysis with Dependence Information for
                            Functional Logic Languages},
        booktitle =     {International Logic Programming Symposium},
        year =          1993,
        address =       {Vancouver, Canada},
        comment =       {Workshop on Global Compilation. To appear}
Quote:
}



Fri, 01 Mar 1996 21:06:43 GMT  
 Lazy functional/logic programming


Quote:
Julio Mari~no Carballo writes:
>    A first text on the implementation of lazy Babel is
>    "Lazy Narrowing in a Graph Machine" [1].  This paper
>    also addresses the nontermination problem and proposes
>    a transformation scheme to a normal form -Uniform Babel programs.
>    The authors identify the source of the non-termination problem
>    ---there is only a finite number of rules matching a redex
>    but a (possibly) infinite number of outcomes--- and propose
>    a program transformation that implements backtracking in the
>    proper order: try different reductions of arguments first,
>    then try the different rules for each reduction.

Would the trying of different ways to reduce the arguments
be interleaved with the trying of the different rules?
I.e. would you:

        1. look for a way to reduce the arguments that hasn't yet been tried,
        2. if found, then try all the rules with this reduction
        3. go to 1.

Is this what you mean?

Quote:
>    This partially solved the nontermination problem but made
>    some others more evident.

Which sort of nontermination problems were made worse by this scheme?

By the way, how did other lazy functional logic languages (e.g. KLEAF)
face these problems?

------------------------------------------

Tulane University       New Orleans, Louisiana  USA



Sat, 02 Mar 1996 07:15:01 GMT  
 Lazy functional/logic programming
Yes, that's the idea. The problem now is that different rules may need
different degrees of evaluation for their arguments. The solution proposed was
transforming the rules in such a way that all the heads had a similar shape in
homologous positions. The problems I referred to in my last posting where with
this translation aggravating reevaluation. As you will see in the paper, this
would move some computations deeper in the evaluation tree, thus increasing
the risk of reevaluations and delaying the detection of failures.

For instance, the program

    f 0 X 0 1 := 0.  will transform to:     f 0 X Y 1 := f1 Y.
    f 1 1 Y 1 := 1.                         f 1 X Y 1 := f2 X.
                                            f1 0 := 0.
                                            f2 1 := 1.

We considered that, for practical programs, this kind of change could mislead
the programmer's intuition on the behaviour of his/her program. Besides, that
turned our attention to the more general problem of reevaluations caused by
laziness itself.

Julio
--
                        ----------------------------------
                        Julio MARI~NO

                        LSIIS Dept/Facultad de Informatica
                        Universidad Politecnica de Madrid
                        28660-Boadilla del Monte (SPAIN)
                        PHO +34-1-336-7449(7464) Off(Lab)
                        FAX +34-1-336-7412
                        ----------------------------------



Sun, 03 Mar 1996 22:51:38 GMT  
 Lazy functional/logic programming

Quote:

> What has been published wrt implementing _lazy_
> functional-logic programming?  (By `lazy' I am not necessarily restricting
> the topic to graph reduction, but any implementation that has the semantics
> of normal-order evaluation).

> Tulane University  New Orleans, Louisiana  USA


Cyprus)

Regarding the recent discussion on integrating lazy functional languages
with logic ones, I did some time ago some similar work in extending GHC
(flat or full) with some functional features including lazy evaluation,
infinite (even cyclic) data structures and sharing of common
subexpressions.

The work was done in the framework of term graph rewriting and, indeed, its
implementation was a mapping of GHC/F programs onto Dactl (a graph
rewriting language) rewrite rules. The resulting mapping wasn't that bad
bearing in mind the extra machinery needed to handle the interaction
between the logic and the functional component (read next paragraph), but
it would probably be a challenging job to design an extended WAM. In many
ways GHC/F was a reincarnation of Parlog'83.

The interaction of the "eager" concurrent logic component with the lazy
functional subcomponent introduced deadlock, as expected. For instance, a
logic variable may be an input argument to some predicate which suspends
waiting for it to be instantiated by some producer. Now if the producer
happens to be a lazy function we have deadlock.

The solution I adopted extends basically the presentation of a variable
with a pointer to its defining function, through which the predicate can
fire the function and cause the instantiation of the variable. There are
some issues now on how, for instance, variable-to-variable unification is
handled but have been worked out and are handled by an extended unification
procedure defined also as sets of Dactl rewrite rules.

Interestingly, these resulting GHC/F to Dactl programs can be transformed
into the Monstr subset (due to Richard Banach, University of Manchester)
which has been shown to be implementable with reasonable efficiency onto
graph rewriting architectures such as Flagship (Developed by ICL,
Manchester, Imperial College, and UEA as part of the UK Alvey Programme).

There is one paper coauthored with John Glauert (UEA) that presents the
language and some programming techniques you can pull in it which can be
obtained by either author. Another one explaining the underlying
implementation machinery will be submitted soon.

George
Nicosia

[This message forwarded since George does not have easy access to News.

appears in his PhD Thesis "Parallel Implementation of Concurrent Logic
Languages using Graph Rewriting Techniques", University of East Anglia,
Norwich, UK (1989).]



Mon, 18 Mar 1996 18:04:14 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. flaw in lazy functional logic programming?

2. flaw in lazy functional logic programming?

3. Lazy functional/logic programming

4. Lisp: program=data (Was: A functional/imperative lazy curious guy )

5. Lazy functional programming on stock hardware

6. REq: Lazy functional programming on stock hardware

7. Time complexity of lazy programs. profiling functional languages

8. Functional Programming Languages with Lazy Evaluation

9. game programming + functional/logic languages

10. CFP: Fuji Workshop on Functional and Logic Programming

11. Workshop on Functional and Logic Programming (2nd call)

 

 
Powered by phpBB® Forum Software