HDTenEightyP/NetNews huggingface dataset:
From: fjh@munta.cs.mu.OZ.AU (Fergus James HENDERSON)
Subject: Re: Completely functional program in C
Organization: Computer Science, University of Melbourne, Australia
Date: Fri, 25 Dec 1992 18:02:01 GMT

goodrich@lynx.larc.nasa.gov (Mike Goodrich) writes:

>Greetings,
>	The following is an example of a functional program in C I wrote after
>reading MaClannan's book on FP. I would like to invite comments from the FP
>community.

I would not describe this program as particularly "functional".
It does have a lot of tail recursion, but there is not much else that
could be called functional.

[...]
>main(argc, argv)
>	int             argc;
>	char          **argv;
>{
>	unsigned char   buff[REC_SIZE];
>
>	if (argc < 2) {
>		printf("\nUsage: hexdmp <filename>\n");
>		exit(0);
>	}
>	DumpFile(fopen(argv[1], "rb"), buff);
>}

- exit(0) is not very functional
- failing to return a value from main() is not very functional
  (not to mention that it's not very good C either ;-)
- passing uninitialized parameters (buff) is not very functional

>void
>PutTextLine(NumRead, buff)
>	short           NumRead;
>	unsigned char  *buff;
>{
>	switch (NumRead) {
>	case 0:
>		return;
>	default:
>		if (*buff < ' ' || *buff > '~') {	/* printable ? */
>			printf(".");
>		} else {
>			printf("%c", *buff);
>		}
>		PutTextLine(NumRead - 1, buff + 1);
>	}
>}

Why the switch statements? What's wrong with using if statements?

Also, purely functional programs should have declarative I/O.
Since this is impossible, the next best thing is to confine all your
I/O to the very top-level of your program, or alternately to pass
pretend state-of-the-world arguments to and from a library of declarative
I/O functions (OK, admittedly that's a bit silly in this context, but
then it's a pretty silly context ;-)

>
>void
>PutHexLine(NumRead, buff)
>	short           NumRead;
>	unsigned char  *buff;
>{
>	switch (NumRead) {
>	case 0:
>		printf("\t");
>		return;
>	default:
>		printf("%02x ", *buff);
>		PutHexLine(NumRead - 1, buff + 1);
>	}
>}
>
>void
>DoLine(NumRead, buff, count, fp)
>	short           NumRead, count;
>	unsigned char  *buff;
>	FILE           *fp;
>{
>	switch (NumRead) {
>	case 0:
>		return;
>	default:
>		printf("\n<%d>\t", count * REC_SIZE);
>		PutHexLine(NumRead, buff);
>		PutTextLine(NumRead, buff);
>		DoLine(fread(buff, 1, REC_SIZE, fp), buff, count + 1, fp);
>	}
>}
>
>void 
>DumpFile(fp, buff)
>	FILE *fp;
>	unsigned char  *buff;
>{
>	if (fp == NULL) {
>		printf("Error: cannot open input file\n");
>		exit(-1);
>	}
>	DoLine(fread(buff, 1, REC_SIZE, fp), buff, 0, fp);
>}

fread() is not a very functional function, since the buff array is 
effectively passed by reference rather than by value.

-- 
Fergus Henderson             fjh@munta.cs.mu.OZ.AU      
This .signature virus is a self-referential statement that is true - but 
you will only be able to consistently believe it if you copy it to your own
.signature file!
From: sfk@otter.hpl.hp.com (Steve Knight)
Date: Fri, 1 Jan 1993 17:35:54 GMT
Subject: Re: Dynamic List Implementation
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Newsgroups: comp.lang.pop

Thanks to Aaron Sloman for for the historical review of dynamic lists.
It is always insightful to see how a language flows from equal 
measures of design and experiment!

Aaron writes:
> One problem with having a different record type for dynamic lists is
> that if you expand a dynamic list you would then have to change the
> type of the record, since lots of things can be pointing to that
> list.

This isn't strictly necessary.  The DPAIR could be implemented exactly
the way dynamic PAIRs are currently implemented.  In other words, they
could have a procedure for their back if they were dynamic and false
if they were an expanded null.

Aaron makes another point concerning the optimisation
    unless null( x ) then ... destpair( x ) ... endunless
to 
    unless null( x ) then ... fast_destpair( x ) ... endunless
and this point is preserved using the implementation suggested above.


John Gibson's point, that the current implementation of dynamic
pairs only costs another memory access is plainly true.  However,
the performance different is measurable -- I wrote a note on this
a while back I think.  

There can't be many programs that would be broken if we were to
change the representation of dynamic lists.  (In fact, such programs
are already broken by my way of thinking.)  The only examples I can
think of are list operators such as expandlist which plainly have
to change when one changes the representation.

Steve
From: axs@cs.bham.ac.uk (Aaron Sloman)
Newsgroups: comp.lang.pop
Subject: Re: Dynamic List Implementation
Date: 23 Dec 92 16:49:05 GMT
Organization: School of Computer Science, University of Birmingham, UK

Following on from my previous comment on Steve Knight's message.

> sfk@otter.hpl.hp.com (Steve Knight)
> Date: 22 Dec 92 14:55:12 GMT
> Organization: Hewlett-Packard Laboratories, Bristol, UK

Steve considered a change to use a special data-type for dynamic
lists, saying

> Now the common case is significantly quicker -- only inspecting the key
> of -x- to return a result.
>
> As far as I can tell, the same analysis follows through for all the
> list operators.  The dynamic list operations are slightly worsened in
> performance, it is true, but looking at the statistics there it is
> a very small amount indeed.
>
> Is there some subtle detail about dynamic lists that I am overlooking?
> I would be grateful for any facts or insights into this aspect of
> POP.  What motivates me is that I love having dynamic lists around
> but I hate having to pay -any- performance penalty for them if there is
> no necessity for it.  So my question boils down to, where is the
> necessity?

I asked John Gibson about the possible advantage of using a new kind
of link and he commented:
| Checking whether the back is a procedure is merely 1 memory access
| slower than checking the key of the pair (ie, utterly insignificant).
| Once you know it's dynamic, checking the front for true/false is
| insignificant compared to the time taken the run the dynamic procedure,
| etc.

So maybe the efficiency issue is not worth worrying about, given
that you can already use front and back (or the fast_versions) for
speed when you know you are not using dynamic lists.

But I have not done any tests to check the difference it would make
to procedures like hd, tl, null, etc. on non-dynamic lists, if there
were a special datatype for dynamic lists.

aaron
-- 
Aaron Sloman, School of Computer Science,
The University of Birmingham, B15 2TT, England
EMAIL   A.Sloman@cs.bham.ac.uk  OR A.Sloman@bham.ac.uk
Phone: +44-(0)21-414-3711       Fax:   +44-(0)21-414-4281
From: sfk@otter.hpl.hp.com (Steve Knight)
Date: Fri, 1 Jan 1993 17:00:15 GMT
Subject: Re: Syntax Misdesign
Organization: Hewlett-Packard Laboratories, Bristol, UK.
From: pop@cs.umass.edu ( Robin Popplestone )
Newsgroups: comp.lang.pop
Subject: When the (Gibson) cat's away across the atlantic....
Keywords: vision, butchering-of-vectors danger
Date: 23 Dec 92 14:10:39 GMT
Organization: University of Massachusetts, Amherst
Originator: pop@roo.cs.umass.edu

Needing to crunch a quarter of a million pixels in a hurry I have been
reduced to writing 600 lines of C. How, I wondered to let C report its
answers back to POP - these had to be line-segment records as well  as
an 512*512 array  (something like the  Ramsay and Barrett  line-finder
souped up) Now the array  was no problem - POP  knows how big it  will
be, and just gives  C the array vector.  Line segments, the number  of
which cannot be predicted, presented  a harder problem. I didn't  want
to use a call-back to the POPLOG allocator, for various reasons.  So I
made POP  hand C  a large  vector, which  C then  carves into  segment
records (using a segment-key handed in as an argument) and a left-over
vector. This is safe (once I got the bugs out), provided the C program
can't be interrupted by a signal (since C is left with no compromising
pointers), but is clearly in danger of being upstaged by any change in
POPLOG. It  is  also mostly  satisfactory,  in the  sense  that  store
doesn't get fragmented, and the implementation is efficient.

I suppose my question is - might some conventions and .h files etc. be
provided to allow one to do this kind of thing in a way that would  be
proof against version change. [One of the main pains in this  exercise
is that C  doesn't let  offset pointers  into structures  the way  POP
does, so that there is  no neat solution to  being able to access  all
the fields (including  the key)  while maintaining  the C  size =  the
actual size of the POP record.].

Robin
From: sfk@otter.hpl.hp.com (Steve Knight)
Date: Tue, 22 Dec 1992 14:55:12 GMT
Subject: Dynamic List Implementation
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Newsgroups: comp.lang.pop

I've always been puzzled why POPLOG implements dynamic lists using
pairs rather than a separate dpair key.  In fact, a dynamic list
is represented using a pair whose back is a procedure and whose
front is true.

Because POPLOG uses this representation, many simple operators go
slower in the common case of non-dynamic lists.  For example, the
operator -null-, which is almost always applied to non-dynamic pairs, 
determines the speed of -for- loops.  But it has to be coded like 
this

    define null( x ); lvars x;
        if ispair( x ) then
            isprocedure( fast_back( x ) ) and 
            dnull( x )    ;;; you can imagine the code for this.
        else
            x == [] or mishap( 'LIST NEEDED', [^x] )
        endif
    enddefine;

 
In the common case, this version of null is obliged not only to inspect
the key of -x- but also the fast_back(x) for being a procedure.  If we
compare with the version which uses dpairs to indicate dynamic pairs.

    define null( x ); lvars x;
        not( ispair( x ) ) and
        (    
            x == [] or
            isdpair( x ) and dnull( x )
        )
    endefine;

Now the common case is significantly quicker -- only inspecting the key
of -x- to return a result.

As far as I can tell, the same analysis follows through for all the 
list operators.  The dynamic list operations are slightly worsened in
performance, it is true, but looking at the statistics there it is
a very small amount indeed.  

Is there some subtle detail about dynamic lists that I am overlooking?
I would be grateful for any facts or insights into this aspect of
POP.  What motivates me is that I love having dynamic lists around
but I hate having to pay -any- performance penalty for them if there is
no necessity for it.  So my question boils down to, where is the 
necessity?

Steve
From: sfk@otter.hpl.hp.com (Steve Knight)
Date: Tue, 22 Dec 1992 14:13:51 GMT
Subject: Re: POP syntax
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Newsgroups: comp.lang.pop

Continuing Ian Rogers transliteration from C-syntax to POP-syntax ...

Robin Popplestone's original, with correction and standard whitespace and
indentation :-

    maplist( x, f ) { 
        null( x ) ? [] : f( hd( x ) ) :: maplist( tl( x ), f )
    }

And here's Ian Rogers POP version, modified to use -null- (because that's
an error in Robin's code) _but_ using the dot notation for elegance.

    define maplist( x, f ); 
        x.null and [] or x.hd.f :: maplist( x.tl, f ) 
    enddefine;

Not surprisingly, when we lay out the code correctly, we find that the
POP code is more concise and visually simpler.  This situation is 
reversed when we add in the obligatory "lvars" declarations, alas.
Here's the kicker ...

    define maplist( x, f ); 
        lvars x, f;                                   ;;; pointless.
        x.null and [] or x.hd.f :: maplist( x.tl, f )
    enddefine;

These extra declarations are pointless clutter forced upon the reader
by historical changes within POP-11.  Unfortunately, the reader _must_
read these declarations and understand their meaning, since any
change leads to a massive change in semantics.  (In fact, the first two
versions of maplist given here are completely wrong because of the 
omitted declarations.  The arguments default to "vars" and therefore
wrongly mask other top-level declarations of -x- and -f- during the
invocations of the procedure -f-.)

To my mind, Ian has produced a nice little demonstration -- by comparison
with another programming language -- why obligatory declarations are 
harmful to POPs syntax.  The obvious solution that has been suggested to
me very frequently (as Pop9x coordinator) is to make the default
declaration "lvars".  And I see this as very sensible.  

Steve
Newsgroups: comp.lang.pop

Here's a question that Chris and I have whiled away the odd lunchtime
over.  Given that POPLOG has got a 2-bit tag on each full-cell but
only uses three of the tag, what should the 4th tag be used for?

My favourite two suggestions are as follows.  (1) The 4th tag code should
be used to denote other "simple" quantities such as characters (UNICODE)
and enumerated types constructed by the user.  (2) The 4th tag code
should be used to denote "delayed" expressions.  These are arbitrary 
expressions that get "forced" on demand but otherwise are not executed.
The garbage collector would be sensitive to them and elide references
to them if they have been evaluated.

I especially like suggestion (2) -- even though it has a small performance
cost.  If there are delayed expressions floating around, it is necessary
for all recognisers to check for that 4th tag code.  This is probably
acceptable, but it is a cost.  But then again, just imagine having the
ability to write lazy programs rather than just dynamic lists!

Any other suggestions?

Steve
Newsgroups: comp.lang.pop

To answer a couple of specific points made about quotation in POP-11
and Pepper, here's a short note.

In the context of the POP-11 syntax "'any chars'", Aaron Sloman writes:
> I've just realised that this facility could be screwed up by the
> suggestion from Steve Knight and Chris Dollin to allow multiple
> quoted words by using
>     "the cat on the mat"
> to put five words on the stack.

Yes, this is an issue.  However, it is dealt with via the obligatory
force-quotation mechanism '\'.  So where you would write
    "'f(x)'"  in POP-11
you write
    "\'f(x)'" in Pepper

This is rather neater than the POP-11 syntax because it works in
any context.  For example one has to write
    [A funny atom % "'f(x)'" %] in POP-11
to get the same effect as
    "[A funny atom \'f(x)']"    in Pepper


> Taking account of all requirements when designing a general purpose
> language is HARD!

I couldn't agree more.  Illustrating this, the recent evolution of 
POP-11 has left a number of awkward features.  One of the aims in 
designing Pepper was to explore the possibility of a rational 
reconstruction of some parts of POP-11.  In the case of quotation, 
list and vector syntax I am satisfied that Pepper is a clean and 
thorough solution.

And we certainly found designing the details of the solution exceedingly
tricky!  POP-11 is one of the best designed languages in existence
and even its weak points are hard to definitely improve on.  Although
we had a strong vision of the core of the solution, designing a system
that coped with all the corner cases was difficult.

Steve
From: pop@cs.umass.edu ( Robin Popplestone )
Newsgroups: comp.lang.pop
Subject: Dynamic lists
Date: 23 Dec 92 18:46:18 GMT
Organization: University of Massachusetts, Amherst
Originator: pop@roo.cs.umass.edu

[I must get our news machine mounted, so that I can use the POP reader...]

Steve K. [it  was I  think] suggested  a more  efficient implementation  of
dynamic lists could  be obtained by  having a separate  record to hold  the
generating function. That would seem to be a good idea, since dynamic lists
should be  used  abstractly.  The  only occasion  recently  when  I  recall
actually looking  at  the structure  of  a dynamic  list  is in  the  error
reporting mechanism of parse_gen. Error  reporting is of course always  the
trouble spot where abstractions  break down etc.  What the error  reporting
mechanism needs to do is to potter along the expanded dynamic list until it
finds the unexpanded part,  which is where the  parser must have failed  to
find a parse. However, the  code I have written  would actually work OK  if
the suggestion  of  a  separate  terminating  record  were  adopted.  But a
predicate to recognise whether you  are looking at a completely  unexpanded
dynamic list would be a help.


As to why in the  first place we used a  list cell for the termination  - I
don't recall any alternative being discussed, and indeed we might not  even
have implemented general records at the time the problem came up. I seem to
recall that we tried to do something to respond to noises that Peter Landin
was making in 1967  about streams needing to  be respectable things  with a
stable denotation, and came  up with dynamic lists.  I wasn't aware at  the
time of any perceived need for a general laziness.

Re. Steve's suggestion of using the 'extra' tag combination (1 out of 8  in
the original POP-2 implementation, 1 out of 4 in POPLOG) This would seem to
be  a  good  idea,  apart  from  the  apparently  unavoidable  inefficiency
introduced into recognisers (which he pointed out). I can't  think of any
way  out of this -  zoos are bad news  I think. If  there is  to be any
spatial separation,  modern consensus is towards separating generations
rather than types.


One hack that has been tried  in the persistent language community (and  as
Steve observes, one might regard persistence as a delayed read from backing
store) has  been  to  force a  page-fault  when  such a  delayed  beast  is
encountered. However, with current  operating systems, this probably  works
better for persistence  (where you  are going to  have wait  quite a  while
anyway) than for general laziness.

Robin.
From: axs@cs.bham.ac.uk (Aaron Sloman)
Newsgroups: comp.lang.pop
Subject: Re: Dynamic List Implementation
Date: 23 Dec 92 09:06:15 GMT
Organization: School of Computer Science, University of Birmingham, UK

sfk@otter.hpl.hp.com (Steve Knight) writes:

> Date: 22 Dec 92 14:55:12 GMT
> Organization: Hewlett-Packard Laboratories, Bristol, UK.
>
> I've always been puzzled why POPLOG implements dynamic lists using
> pairs rather than a separate dpair key.  In fact, a dynamic list
> is represented using a pair whose back is a procedure and whose
> front is true.

I absolutely agree that this is wrong and wish we had changed it in
Pop-11 instead of following Pop2, just as we introduced a new
data-type for undefs and for booleans. (In Pop2, 0 was false, alas.)

I cannot see any reason for the way things are except that the
original Pop2 was implemented on a tiny machine and a new record
type would have required an unacceptable amount of additional space
in the system.

One problem with having a different record type for dynamic lists is
that if you expand a dynamic list you would then have to change the
type of the record, since lots of things can be pointing to that
list. Your message did not point out that one of the consequences of
applying "null" to a list is that if it is dynamic and non-null it
gets "solidified" by one step, so that if null(list) returns false
you can then optimise and apply "front", or even "fast_front" to
list.

I suspect we would then need three record types

    dlist = unexpanded dynamic list
    dnull = empty dynamic list
    pair  = static list, or link for expanded part of dynamic
            list.

This is currently handled in Pop11, following Pop2, by changing the
*contents* of the record holding the dynamic list. Changing the
type, by changing the key pointer, would be better, allowing faster
checking.

Aaron
-- 
Aaron Sloman, School of Computer Science,
The University of Birmingham, B15 2TT, England
EMAIL   A.Sloman@cs.bham.ac.uk  OR A.Sloman@bham.ac.uk
Phone: +44-(0)21-414-3711       Fax:   +44-(0)21-414-4281
From: sfk@otter.hpl.hp.com (Steve Knight)
Date: Fri, 1 Jan 1993 17:46:32 GMT
Subject: Re: When the (Gibson) cat's away across the atlantic....
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Newsgroups: comp.lang.pop

Robin Popplestone writes:
> Needing to crunch a quarter of a million pixels in a hurry I have been
> reduced to writing 600 lines of C. How, I wondered to let C report its
> answers back to POP - these had to be line-segment records as well  as
> an 512*512 array  (something like the  Ramsay and Barrett  line-finder
> souped up) Now the array  was no problem - POP  knows how big it  will
> be, and just gives  C the array vector.  Line segments, the number  of
> which cannot be predicted, presented  a harder problem. I didn't  want
> to use a call-back to the POPLOG allocator, for various reasons.  So I
> made POP  hand C  a large  vector, which  C then  carves into  segment
> records (using a segment-key handed in as an argument) and a left-over
> vector.

While supporting Robin's request for suitable .h files to make this
kind of programming safer, I am puzzled by the need for it here.

Why not pre-allocate all the line-segment records and stick them
into a vector (null-terminated)?  This vector can then be passed to
C with impunity.  It is admittedly slightly more space consuming 
and likely to take more slightly time to preallocate.  But this
seems like quite an acceptable cost to me.

Steve
From: tmr@cs.bham.ac.uk (Tim Read)
Newsgroups: comp.lang.pop
Subject: The Joys of X !!
Date: 28 Dec 92 14:44:20 GMT
Distribution: comp.lang.pop
Organization: School of Computer Science, University of Birmingham, UK

I am still `on the case' of trying to get X thingies (bitmaps, widgets etc)
into a window created by the rc_graphic library. To my knowledge there are a
couple of ways to import X bitmaps, but in each case I am missing some part
of the jigsaw puzzle, so am unable to complete the process. Watch this
space.

Another problem I wish to solve is how to create and obtain a handle for an
X widget for use within the same rc_graphic window. This does not appear to
be an easy task. I don't like to criticise rc_graphic too much, as it does
make life much easier in the majority of cases. However one problem with it
is that the types of things that can be created and drawn within the X
window are very limited.

For anyone trying to display an environment with many different objects,
things get very frustrating. You are basically limited to lines and
alphanumeric characters. You can build moderately complex objects using a
function that puts together a few lines etc, but that gets very slow when
you come to display things. I am also using colour and sound of course, but
that limits the numbers of machines I can run my code on. I don't require
the widget to have any functionality, like a button might have, just to be
displayable.

Well considering it is (was) xmas recently, if I ask nicely enough perhaps
Santa will supply me with pointers to the knowledge as to how to create such
widgets, and a corresponding set of functions to display and manipulate
them.

I don't want to have to use any `big' existing libraries that were designed
for other purposes, as the key thing here is speed, or efficiency if you
like (that's got Steve's attention!). I have tried wading through the help
and ref files but find them somewhat indigestible, after all the turkey...

Has anyone done anything like this?, or have any code fragments that I could
browse to understand how best to go about such code? 

Thanks in advace,

Tim
--
    --------------------------------------------------------------------
    Tim Read, Email: tmr@cs.bham.ac.uk, The Attention and Affect Project
    Room LG23, School of Computer Science, The University of Birmingham,
    B15 2TT, England, Phone: +44-(0)21-414-4766, Fax: +44-(0)21-414-4281
    --------------------------------------------------------------------