HDTenEightyP/NetNews huggingface dataset:
From: waugh@probitas.cs.utas.edu.au (Sam Waugh)
Subject: Help required with PreludeText (Haskell)
Keywords: Questions, simple
Organization: University of Tasmania, Australia.
Date: Tue, 10 Nov 1992 04:49:06 GMT

Sorry to be posting a simple question to the net, but I can't find the
answer anywhere.

The function readsPrec is defined within the Text class.
- What does the "Prec" bit stand for; and
- why does readsPrec require an Int value (I can't see why this is used).
	[the type being readsPrec :: Int -> ReadS a]

I've been looking for answers in the Haskell Report (v1.1) and every place
that readsPrec is used the Int value is thrown away.  Why not use reads
within the class?

Thanks very much for any help.

Sam Waugh
email: waugh@cs.utas.edu.au
From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Newsgroups: comp.lang.functional
Subject: Re: Is efficient backtracking feasible in functional languages?
Date: 13 Nov 92 17:31:52
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)
Reply-To: tmb@idiap.ch
NNTP-Posting-Host: arolla.idiap.ch
In-reply-to: jones-mark@CS.YALE.EDU's message of Thu, 12 Nov 1992 16:27:25 GMT

In article <1992Nov12.162725.25836@cs.yale.edu> jones-mark@CS.YALE.EDU (Mark P. Jones) writes:

   |  In general, in a lazy language, you are often at the mercy of the
   |  compiler to prove things about your code in order to obtain decent
   |  performance.

   But in a lazy language, you don't need to do a lot of the standard
   optimisations like tail recursion elimination, moving constants outside
   loops etc.  Laziness gets you those things for free! [...]

   |  Fortunately, in SML, you have better control over
   |  resources than in a lazy language,

   Unfortunately, you will often have to write extra code to control
   those resources...

   Yes, it is true that reasoning about the resources used by a program
   in a lazy language is more difficult than reasoning about a program in
   a strict language like SML.  But sometimes it's nice to be able to write
   code using a list without wondering whether I ought to write it with an
   explicit loop, or whether I should use a stream library instead, or ...
   I'm not criticising SML.  But Haskell (and lazy languages in general)
   have their nice points too.

I completely agree that a lot of the mess in writing programs comes
from orchestrating what gets computed when, and that it would be nice
to leave all that to the compiler. However, resource constraints mean
that I need more control than lazy languages currently give me, and,
as I mentioned before, I somehow remain doubtful that
compilers/runtime systems be able to make the right tradeoffs between
space and time in the near future.

I'd rather see a little more support added to eager languages for
lazyness and caching. In SML, you can already define many lazy
constructs like streams, thunks, and caches. Some improvements that
I would like to see are:

	* eliminate those weak type variables that come from
          the underlying imperative implementations

	* provide versions that use structural equality, hashing,
	  and comparisons (SML has polymorphic "=", but for some
	  obscure reason does not provide polymorphic "<" and
	  polymorphic "hash" to go with it)

	* make the syntax a little nicer; maybe I could declare
	  individual function arguments to be "lazy":

	  fun f(x: 'a lazy) = [x]
	  f(3+4) --> [thunk] : int lazy list

	* provide "dynamic contexts" for caching:

	  fun f(x) = ...

	  fun g() =
	      let
		  (* any call to "f" within this dynamic scope
	          is cached; the cache gets destroyed when this
		  dynamic context exits *)

                  dynamically_cache(f)
                  ...
	      in
		  ...
	      end

Anyway, just some suggestions (actually, you can experiment with such
constructs relatively nicely in CommonLisp or in Scheme with macros).

					Thomas.
Newsgroups: comp.lang.functional
From: aet@mullian.ee.mu.OZ.AU (bert thompson)
Subject: functional LR parsing
Organization: Computer Science, University of Melbourne, Australia
Date: Mon, 9 Nov 1992 00:41:17 GMT


The book ``LR Parsing: Theory And Practice'' by Nigel Chapman has a little 
bit on LR parsing in SASL. It talks about SASL-YACC by S P Jones.

Does anyone else know anything about non-LL parsing techniques?
Just curious: Has anyone implemented Early's algorithm or some other 
general technique?

	Bert.

--------------------------------------------------------------------------------
bert thompson	aet@munagin.ee.mu.oz.au.
SITEE		school of information technology and electrical engineering
		university of melbourne
--------------------------------------------------------------------------------
Newsgroups: comp.lang.functional
From: weberwu@inf.fu-berlin.de (Debora Weber-Wulff)
Subject: Re: Functional Parsers
Keywords: parsers
Reply-To: dww@inf.fu-berlin.de
Organization: Free University of Berlin
Date: Thu, 12 Nov 1992 13:34:48 GMT

ptb@eng.cam.ac.uk (P.T. Breuer) writes:
>>
>>I don't mind admitting that I don't know what a non-LL language looks like.


>Thanks to Debora Weber-Wulff for offering a test case.
>The language { a^n b^n | n>=0 } apparently definitely has no LL grammar
>(but does have a LR(0) one) and is specifiable in pre-cc. But not all

No, Peter, the language I gave you was
{a^n b^n | n >=1} \cup [that's the LaTeX union operator] {a^n c^n | n >=1}
This is not LL because you have to get all the way down to the b's or
c's before you can decide which way you needed to go. In LR parsing,
we are constructing the reverse of a right-derivation, we shift a's
onto the stack until we see a b or a c, and they we *know* which
set of productions to use. 


>it's the basis of my claim that LR(0) languages are expressible.
How about a proof including the time and space complexities of
your system? I so enjoyed the strangesucc function, which has proved
to me that, yes, it is nice to express things with backtracking and no,
I do not want my systems to use it, because I prefer termination to
stack overflow.

-- 
Debora Weber-Wulff                       dww@inf.fu-berlin.de
Institut fuer Informatik                 +49 30 89691 124
Nestorstr. 8-9                           (INCLUDE "standard.disclaimer")
D-W-1000 Berlin 31                       (PRINTN (WITTY-MESSAGE TODAY))
Newsgroups: comp.lang.functional
From: ulrich@mips.complang.tuwien.ac.at (Ulrich Neumerkel E185/1 +43158801/4477)
Subject: Is efficient backtracking feasible in functional languages?
Keywords: lazy evaluation, comprehensions, backtracking
Reply-To: ulrich@mips.complang.tuwien.ac.at
Organization: Technische Universitaet Wien, Institut fuer Computersprachen
Date: Tue, 10 Nov 1992 16:44:56 GMT


In many textbooks and papers about functional languages it is suggested
that lazy evaluation allows to implement backtracking by representing
the sequence of solutions by an appropriate datastructure which is
generated in a lazy manner. Is seems however, that such an encoding,
although conceptually elegant, requires space proportional to the
number of choices already considered.

Below is such a backtracking program `strangesucc' that computes the
successor of a number by searching through all natural numbers and
selecting the first solution found. This program here is a little
overkill. It serves only as an example for the problems I
encountered in more complex backtracking programs. Take a more
complex condition and the program does make sense.

strangesucc n =	hd [x|x<-[0..];x>n];

This program should run in constant space and linear time [1].
However, for the implementations I tried, it turns out that the program
seems to run in linear space! For a small n as 10000 the program aborts
due to memory problems. Also a rewriting of the program to encode list comprehensions explicitly did not yield the desired result.

Is there ANY implementation of a lazy functional language to execute
the program above in an efficient manner (i.e. in constant space)?

Thank You, Ulrich

[1] more precicely in log n space and n log n time, if we consider
numbers of arbitrary magnitude.

PS: Note that backtracking as implemented in Prolog does not have
such problems.
-- 
Ulrich Neumerkel, ulrich@dec4.wu-wien.ac.at ulrich@mips.complang.tuwien.ac.at
TU-Wien, Vienna University of Technology, +431 58801 4477 fax +431 5057838
Institut fuer Computersprachen E185/1 Argentinierstr.8/4, A-1040 Wien Austria
From: kh@dcs.glasgow.ac.uk (Kevin Hammond)
Newsgroups: comp.lang.functional
Subject: Re: Is efficient backtracking feasible in functional languages?
Keywords: lazy backtracking Gofer
Date: 12 Nov 92 18:14:49 GMT
Organization: Computing Sci, Glasgow Univ, Scotland

In article <1992Nov12.162725.25836@cs.yale.edu> jones-mark@CS.YALE.EDU (Mark P. Jones) writes:
>Commenting on the implementation of a strange successor function, the fact
>that it appears to run in space proportional to n, the fact that actually
>it only uses constant space in an implementation of SML and the fact that
>one implementation of Haskell seems to have problems with this, Thomas M.
>Breuel says:
>
>|  Let's nip this rumor in the bud:
>
>Yes indeed.  Lazy languages do not have a problem with this either.

>[...]

>But the garbage collector algorithm has nothing to do with the
>strangesucc algorithm that you're looking at.  I'd be very suprised if
>the Haskell B. version doesn't actually run in constant space.
> The backend of Gofer is based on the same G-machine technology that was  
>introduced in the implementation of LML and then Haskell B.

The Haskell B. (and LML) implementations have (or had) some
interesting space leaks (as Dave Wakeling's profiler pointed out).
One of these was due to not "black-holing" closures when they were
entered (so retaining space if arguments to the original closure
became dead before the closure was fully evaluated).  It sounds as if
this may be the problem reported with the Haskell B implementation.
The most recent implementation has compiler flags to fix the problems
which Dave Wakeling reported, but I think they're disabled by default
(black-holing costs time, for instance, which you may not want to
spend).

Most functional language implementations that I know in detail (strict
or non-strict) have, or have had, significant space-leak problems.
I'm sure the same is true of Lisp systems (though they may be
sufficiently mature that they've solved most of the problems), and
I've had space leaks in C (though that was generally my fault).  If
you have dynamically allocated memory (stack or heap), then you need
to control it carefully to avoid leaks.  If the memory is managed
implicitly, then the compiler has to take care never to retain space
unnecessarily.  At the moment we still seem to be discovering ways in
which space can be lost, perhaps because they're not all written down,
and they're not all obvious.

To reiterate the point, this is an *implementation* issue, NOT a
language issue.  For what it's worth, the new Glasgow Haskell compiler
has no problem with strangesucc 10000000.  It always "black-holes"
entered closures, and should never retain dead values on the stack.

Kevin
-- 
Dept. of Computing Science, Glasgow University.    E-mail: kh@dcs.glasgow.ac.uk

This Signature Intentionally segmentation fault
From: graham@cs.chalmers.se (Graham Hutton)
Newsgroups: comp.lang.functional
Subject: Parsers
Date: 5 Nov 92 14:29:02 GMT
Organization: Dept. of CS, Chalmers, Sweden

There have been a few people posting to this group
about building parsers in functional languages.  A
while ago I wrote a tutorial article about functional
parsers; it is soon to appear in the Journal of
Functional Programming.  It can be obtained by ftp from

        animal.cs.chalmers.se   (129.16.225.66)

Use "anonymous" as the login, and your email address
as the password.  The file is "pub/papers/parsing.dvi".

Graham Hutton
(graham@cs.chalmers.se)
From: staffan@chivas.Eng.Sun.COM (Staffan Liljegren)
Newsgroups: comp.lang.functional
Subject: Re: Is efficient backtracking feasible in functional languages?
Date: 11 Nov 1992 21:53:37 GMT
Organization: Sun Microsystems
Distribution: world
Reply-To: staffan@chivas.Eng.Sun.COM
NNTP-Posting-Host: chivas

In article 18783@eua.ericsson.se, joe@erix.ericsson.se (Joe Armstrong) writes:
>
>|> 
>|>    strangesucc n =	hd [x|x<-[0..];x>n];
>|> 
>	....
>|> 
>|>   - Stream.head(Stream.filter(fn x => x > 1000000,Stream.iota()));
>|>   
>|>   [Major collection... 21% used (3397260/15733684), 1920 msec]
>|>   
>|>   [Major collection... 21% used (3397288/15730836), 1910 msec]
>|>   
>|>   [Major collection... 21% used (3397288/15730948), 1920 msec]
>|>   
>|>   [Major collection... 21% used (3397288/15730888), 1920 msec]
>|>   
>|>   [Major collection... 21% used (3397288/15730888), 1910 msec]
>|>   val it = 1000001 : int
>|>   -
>
>	Wonderfull  !!
>
>	This is the kind of stuff that gives FP a bad name :-)
>
>	Is their a transformation system which can prove that
>
>	strangesucc x == x + 1 ?
>
>	Joe

I thought I should try this in Haskell, so I started Haskell B (the Chalmers implementation)
and I had no problem with 

	strangesucc 10000

Although it garbed three times it wasn't that slow. So ahead with some more courageus:

	strangesucc 100000

What happened ? Well:

	GC Stack Overflow !

So it's not only SML that has these problems. So what are some better mechanisms for 
representing backtracking OR how can You circumvent this problem ?

/Staffan Liljegren
From: tmb@arolla.idiap.ch (Thomas M. Breuel)
Newsgroups: comp.lang.functional
Subject: Re: Is efficient backtracking feasible in functional languages?
Date: 11 Nov 92 10:41:19
Organization: IDIAP (Institut Dalle Molle d'Intelligence Artificielle
	Perceptive)
Reply-To: tmb@idiap.ch
NNTP-Posting-Host: arolla.idiap.ch
In-reply-to: ulrich@mips.complang.tuwien.ac.at's message of Tue, 10 Nov 1992 16:44:56 GMT

In article <1992Nov10.164456.18062@email.tuwien.ac.at> ulrich@mips.complang.tuwien.ac.at (Ulrich Neumerkel E185/1 +43158801/4477) writes:

   In many textbooks and papers about functional languages it is suggested
   that lazy evaluation allows to implement backtracking by representing
   the sequence of solutions by an appropriate datastructure which is
   generated in a lazy manner. Is seems however, that such an encoding,
   although conceptually elegant, requires space proportional to the
   number of choices already considered.

   [...]

   strangesucc n =	hd [x|x<-[0..];x>n];

   This program should run in constant space and linear time [1].
   However, for the implementations I tried, it turns out that the program
   seems to run in linear space! For a small n as 10000 the program aborts
   due to memory problems. Also a rewriting of the program to encode list
   comprehensions explicitly did not yield the desired result.

   Is there ANY implementation of a lazy functional language to execute
   the program above in an efficient manner (i.e. in constant space)?

There should be no problem with that in principle. For example, the
following program, using a lazy streams library in SML, only requires
constant space (3397288 bytes). Of course, it garbage collects a
lot...

  - Stream.head(Stream.filter(fn x => x > 1000000,Stream.iota()));
  
  [Major collection... 21% used (3397260/15733684), 1920 msec]
  
  [Major collection... 21% used (3397288/15730836), 1910 msec]
  
  [Major collection... 21% used (3397288/15730948), 1920 msec]
  
  [Major collection... 21% used (3397288/15730888), 1920 msec]
  
  [Major collection... 21% used (3397288/15730888), 1910 msec]
  val it = 1000001 : int
  -

In general, I think that backtracking is better expressed using
callcc; is there some equivalent to callcc in lazy languages?

					Thomas.
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.lang.functional
Subject: Re: Functional Parsers
Date: 7 Nov 92 10:55:50 GMT
	<1992Nov3.160104.5305@odin.diku.dk>
	<1992Nov4.153220.8174@eng.cam.ac.uk> <Bx923M.K82@dcs.glasgow.ac.uk>
Organization: Department of Computer Science, University of Manchester
In-reply-to: jl@dcs.glasgow.ac.uk's message of 5 Nov 92 15:38:09 GMT

In article <Bx923M.K82@dcs.glasgow.ac.uk> jl@dcs.glasgow.ac.uk (John Launchbury) writes:
   I am amazed that after more than half a dozen articles on functional
   parsers that no-one has referred to the literature.

I think the literature is, on the whole, covered in the references of
the papers that have been mentioned in the articles.  For example, I
reference Burge in my (incomplete) paper since it mentions the use of
continuations (which IMHO is the interesting part :-) and if I ever
finish the paper, I'll also include a reference to Lloyd Allison's
paper.  If and when I cover building the AST and/or dealing with
ambiguous grammars, the following will also be referenced :-

@inproceedings
{ Koster75
, author=    {C. H. A. Koster}
, title=     {A technique for parsing ambiguous grammars}
, booktitle= {Jahrestagung}
, year=      {1975}
, editor=    {D. Siefkes}
, pages=     {233--246}
, publisher= SpringerVerlag
, note=      {LNCS 26}
}

which covers much of the work (under in the form of affix grammars)
which has been subsequently rediscovered in the functional language
area.  If one wishes to push further back, higher order functional
parsers bear a striking similarity with van Wijngaarden grammars; just
replace the higher order combining forms (seq, alt ... etc.) with
meta-rules in a van Wijngaarden grammar.  This fact has not be lost
on others, and one went so far as to get a Ph.D on the subject.
(actually the thesis goes the other way, it replaces meta-rules with
HOF ... etc.)

@phdthesis
{ Edupuganty87
, author= {Balanjaninath Edupuganty}
, title=  {Two Level Grammars: An implementable metalanguage for
           consistent and complementary language specifications} 
, school= {University of Alabama in Birmingham}
, year=   {1987}
}

So to sum up: functional parsing is a simple idea, it has been
independently invented many times and will probably be re-invented
many times in the future.

bevan
From: urban@daimi.aau.dk (Urban Engberg)
Subject: Including files from ml-lex and -yacc
Keywords: ml-lex ml-yacc sml
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
Date: Tue, 10 Nov 92 14:28:21 GMT

In the language of a parser I am writing I want to use the parser
directive %Include <filename> meaning that the file <filename> is to
be included in the parsed file just as if its contents were actually
put there.  I would like to do this inside ml-lex and/or -yacc, which
means that I have to do some operations on the streams that are
generated in the lexer and passed on to the parser.  Has anyone done
this?  How?

This is how I construct the parser:

structure PreParser : PREPARSER =
  struct
    val parse = fn s =>
      let val dev    = open_in s
          val stream = PreParserParser.makeLexer (fn i => input(dev, i))
          val _      = PreParserLex.UserDeclarations.pos := (1, 0)
          val error  = fn (e, (oldline:int, oldchar:int),
			      (newline:int, newchar:int)) => 
            		  output(std_out, "...")
      in PreParserParser.parse(30, stream, error, ()) before close_in dev
      end
  end


--
Urban Engberg					Computer Science Department
urban@daimi.aau.dk				Aarhus University
Phn: +45 86 20 27 11 - 50 91			Ny Munkegade
Fax: +45 86 13 57 25				DK-8000 Aarhus C  --  DENMARK
From: lloyd@cs.monash.edu.au (lloyd allison)
Newsgroups: comp.lang.functional
Subject: Re: Functional Parsers
Keywords: parsers
Date: 5 Nov 92 05:49:46 GMT
Article-I.D.: bruce.lloyd.720942586
Organization: Computer Science, Monash University, Australia

Let me add this ref' of mine:

L. Allison
Some applications of continuations.
Computer Journal 31(1) 9-11 1988
From: wand@dec5120z.ccs.northeastern.edu (Mitchell Wand)
Newsgroups: comp.lang.functional
Subject: Re: Functional Parsers
Date: 10 Nov 92 18:52:23 GMT
	<1992Nov4.153220.8174@eng.cam.ac.uk>
	<1992Nov10.170123.107@eng.cam.ac.uk>
Organization: College of Computer Science, Northeastern University

In article <1992Nov10.170123.107@eng.cam.ac.uk> ptb@eng.cam.ac.uk (P.T.
Breuer) writes:


   Thanks to Debora Weber-Wulff for offering a test case.
   The language { a^n b^n | n>=0 } apparently definitely has no LL grammar
   (but does have a LR(0) one) and is specifiable in pre-cc. But not all
   LR(0) grammars are acceptable for precc, because LR(0) presentations can be
   left recursive. 

a^n b^n not LL ?  Here's a grammar:

S -> A -|   (endmarker)
A -> a A b
A -> e

You can tell which of the two productions for to use for A: if it's an "a",
you use the first, if it's "b" or the endmarker you use the second. (In other
words, the FIRST sets of the 2 A-productions are disjoint, as needed for
LL(1)-ness).  Am I missing something here?

   I think all LR(0) languages are expressible, though,
   if you choose the right grammar presentation.

There's a theorem that says that any deterministic context-free language (ie
acceptable by some deterministic PDA) is expressible by some LR(0) grammar.
However, the grammar may be pretty ugly.

--Mitch 
--
Mitchell Wand
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN, Boston, MA 02115     Phone: (617) 437 2072
Internet: wand@flora.ccs.northeastern.edu          Fax:   (617) 437 5121
From: jl@dcs.glasgow.ac.uk (John Launchbury)
Newsgroups: comp.lang.functional
Subject: Re: Functional Parsers
Keywords: parsers
Date: 5 Nov 92 15:38:09 GMT
Organization: Glasgow University Computing Science Dept.

I am amazed that after more than half a dozen articles on functional
parsers that no-one has referred to the literature. The standard
technique goes back to Landin and Burge and is described in Burge's
old book 'Recursive Programming Techniques'. Phil Wadler explored
it in the setting of a more modern functional language in 'How
to Replace Failure with a List of Successes' (FPCA 85, LNCS 201, S-V).
An application of the technique to parsing natural language occurs
in a joint paper by Frost and Launchbury, 'Constructing Natural
Language Interpreters in a Lazy Functional Language' (Computer
Journal - special issue on Lazy Evaluation ed. P.Wadler, Vol 3
No. 2, 1989). The technique has continued to be developed and
used by many people, and I believe the Journal of Functional
Programming is about to publish something by Hutton.

John.
Newsgroups: comp.lang.functional
From: ronny@cs.kun.nl (Ron Wichers Schreur)
Subject: Incorrect IP address in Clean 0.8 announcement
Keywords: Clean
Organization: University of Nijmegen, The Netherlands
Date: Wed, 11 Nov 1992 15:02:23 GMT

Hello,

An annoying error sneaked into the recent announcement for Clean 0.8.
The IP address for our ftp site was wrong. The correct ftp address is:

        ftp.cs.kun.nl (131.174.33.1)

Apologies for any inconvenience.

Cheers,

Ronny Wichers Schreur
ronny@cs.kun.nl
Newsgroups: comp.lang.functional