Functional Programming Languages with Lazy Evaluation 
Author Message
 Functional Programming Languages with Lazy Evaluation

Has anyone out there considered implementing a functional language
with lazy evaluation, such as Miranda or Haskell, in Poplog ?

I am completely ignorant of what might be involved but am thinking of
setting a 3rd  year undergraduate onto the subject as a final year
project and would like to know if anyone has already thought seriously
about the matter. I understand that the evaluation strategy in these
languages (graph reduction) is somehow radically different from most
programming languages. My worry is that it may prove somehow
fundamentally unfeasible to implement Haskell using the Pop Virtual
Machine.

Any comments gratefully appreciated.

Rob Gaizauskas

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

Dr. Robert Gaizauskas
Department of Computer Science
University of Sheffield
211 Portobello Street
Regent Court
Sheffield S1 4DP
U.K.


phone:  +44 (0)742 825572
fax:    +44 (0)742 780972



Mon, 28 Oct 1996 06:47:38 GMT  
 Functional Programming Languages with Lazy Evaluation

Quote:
> Has anyone out there considered implementing a functional language
> with lazy evaluation, such as Miranda or Haskell, in Poplog ?

> I am completely ignorant of what might be involved but am thinking of
> setting a 3rd  year undergraduate onto the subject as a final year
> project and would like to know if anyone has already thought seriously
> about the matter.

Robin Popplestone has gone a long way in this direction, I understand.
It would probably be far too big a job for an undergraduate project,
but if Robin were willing to make available some of what he has done,
then perhaps your student could build on it.

I am copying this to him at Umass in case he doesn't notice your query
on comp.lang.pop

Aaron



Mon, 28 Oct 1996 14:30:23 GMT  
 Functional Programming Languages with Lazy Evaluation

Quote:
> Has anyone out there considered implementing a functional language
> with lazy evaluation, such as Miranda or Haskell, in Poplog ?

Yes, I've been through this loop a couple of times.  An implementation
of a "full" language such as the two mentioned is a fair amount of
work.  I suggest structuring the work as follows:-

Tokeniser: assume the Pop11 tokeniser.  This isn't correct, of course,
    but I think a student would be wasting their time doing a custom
    tokeniser.  (I think a LEX equivalent would be a good 3rd year project in
    itself.)

Parser: use the new define_parser syntax.  Again, unlikely to be
    perfect and the same comments apply.  The important thing is to
    get the student working from the parse-tree from day 1.

Type-checker: leave as optional.  If there is enough time this can
    be tackled as second part.  Of course, this means that a few elegant
    optimisations will be impossible (e.g. the elimination of store
    allocation for constructions in singleton datatype declarations such
    as    datatype Foo = Foo of int; )  

    This implies that you should choose a language such as KRC or Miranda,
    which either have dynamic type-checking or still make sense with
    dynamic type-checking.  Haskell and type-checking are too closely
    linked.

Code generation: this is the core of the work.  For a fully lazy language
    there are a number of well-understood strategies.  In the past I have
    done this by implementing a special type of "delay" object and inserting
    "forces" at appropriate points.  This is simple -- but the efficiency
    depends on the quality of strictness analysis.  Graph reduction is
    great fun, too.  It is radically different in concept, but if you
    generate supercombinators then you can implement them as procedures
    (and one nice challenge is to avoiding generating superfluous copies of
    common supercombinators.)

Analysis for optimisation: again, an optional phase, probably best considered
    as lower priority than writing a type-checker.  But great fun.

So, with this structure, I think it would be a reasonable (though moderately
difficult) project for a good student.

Steve



Mon, 28 Oct 1996 18:59:35 GMT  
 Functional Programming Languages with Lazy Evaluation

I actually have an unfinished implementation of Haskell that I did in
Glasgow. Essentially the POPLOG VM can be made to correspond quite well
with the STG machine that is one of the -modern- ways to implement
functional languages. The main mismatch is that the STG machine is very
dense in its creation of closures, so that the balance between the cost of
creation of a closure and the cost of using the closure is rather crucial.
Poplog closures are cheap to use (being real code) but rather expensive in
store and cycles to create. Also STG stands for Spineless TAGLESS
G-machine. And Poplog is not of course tagless. However for mixed language
working the tagging would be essential.

Explicit graph reduction is vieux chapeau.

Robin.



Mon, 28 Oct 1996 23:11:54 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Partial Evaluation for Lazy Functional Languages

2. Lazy-evaluation functional language for MS DOS

3. Parial Evaluation & Lazy Functional Language

4. Time complexity of lazy programs. profiling functional languages

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

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

7. Information about lazy evaluation in imperative languages

8. multiplatform GUI design with parallelized lazy functional language

9. Lazy and Strict Functional languages

10. Benchmarking Lazy Functional Languages

11. Monitoring (Lazy) Functional Languages

12. Profiling Lazy Functional Languages

 

 
Powered by phpBB® Forum Software