🚀 go-pugleaf

clin@eng.umd.edu (Charles Lin) writes:


>   Well, a while back, I asked people why functional languages were useful,
>interesting, etc.   I have two followup questions, and unfortunately
>I was a little lazy and didn't type the correct sunject heading, which
>should have been "Why are you interested in functional languages?".

>   So, I'm interested in why you wanted to do work in this area, and
>also what you think the important kinds of questions or work will
>be done in the area, either now, or in the future.

My primary interest in functional languages is not ease of programming
from a human viewpoint (after all, adding imperative features to a
pure FL will not make programming in it harder), but the ease of
manipulating programs.

The high degree of referential transparency in functional laguages
makes many transformations possible, which would not always be valid
in the presence of side-effects, and thus requires a global test of
interference before it can be applied in an imperative language. A
simpe example of this is common subexpression elimination. If you
write "f(x)+f(x)" you would like to transform it into something like
"y+y where y=f(x)" which you couldn't in an imperative language as the
two calls might yield different results, or even modify x. An analysis
of the behaviour of f in an imperative setting could check that it
behaves functionally, but that is both difficult (in most imperative
languages) and costly.

Note that I'm not against side effects as an algorithmic tool (far
from it), only the effects they have on the validity of
transformations. If a language provided a mostly functional framework,
but allowed limited side effects with clear indication (e.g. in the
type system) of what each given function depends on or can modify,
then the transformation rules can use this information to check the
validity of each given transformation. SML goes some way towards this
with the special types for side-effects, but the information is not
exactly what I need.

Even in basically imperative languages, there are degrees of
"badness". In C you have enourmous aliasing problems, as pointers can
refer to local variables, so updating what a pointer refers to can
essentially modify anything. In Pascal, pointers can only refer to
heap objects, so it is easier to determine the potential effects. You
have, off course, aliasing in Pascal too (by var parameters), but it
is less severe than in C.

As you might have guessed, C is my pet hate language. Even so, I
program mostly in C (when i'm not using functional languages, that
is), but I would not try to do automatic transformation of C programs.

The important future works in pure functional languages are:

1) Make it easy to describe functionally algorithms that are
   traditionally written in imperative style with arrays and pointer
   updating. The "standard trick" of adding the state as extra
   parameters/results of functions is notationally burdensome.

2) Make such algorithms run efficiently. The abovementioned trick adds
   a lot of overhead. Also, operations on arrays can be costly if
   implemented in the obvious ways.

3) Make good parallel implementations of functional languages, getting
   good processor utilisation without requiring programs to be written
   specifically for a given architecture.

Much work is already done in these areas, but there is still room for
improvement.

	Torben Mogensen (torbenm@diku.dk)

tmb@arolla.idiap.ch (Thomas M. Breuel) writes:


>I think in order to fulfill their promise in this area, functional
>programming languages should probably go back to Lisp notation.

(I
  (Don (' (t
	     (think
		   (so)))))) (!).
-- 
Annius Victor Groenink      Universiteit Utrecht      PTT Research Leidschendam
Mathematics/Comp. Sc.        avgroeni@cs.ruu.nl       +31 70 3325445 (weekdays)
Atari ST/Music          A.V.Groenink@research.ptt.nl  +31 70 3464732 (evenings)
_____________My opinions are my opinions____________  +31 5700 29396 (weekends)

tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

>   My primary interest in functional languages is not ease of programming
>   from a human viewpoint (after all, adding imperative features to a
>   pure FL will not make programming in it harder), but the ease of
>   manipulating programs.
>
>Too bad that languages like SML (and, moreso, Haskell) have adopted
>such a comparatively complex syntax. Writing programs to manipulate
>programs is much easier in Lisp, due to the obvious correspondence
>between external and internal representation and a standard interface
>to the compiler/type facilities (in the form of macros and type
>predicates).

All you need is a parser which translates the concrete syntax to the abstract
syntax (i.e., Lisp-like notation), and an "unparser" to translate back.  This
way the user gets the benefit of being able to write readable code and the
rewrite engine doesn't have to parse anything.  This approach works very well
for the transformation system on which I'm working (Uday Reddy's Focus system).

Rob

   My primary interest in functional languages is not ease of programming
   from a human viewpoint (after all, adding imperative features to a
   pure FL will not make programming in it harder), but the ease of
   manipulating programs.

Too bad that languages like SML (and, moreso, Haskell) have adopted
such a comparatively complex syntax. Writing programs to manipulate
programs is much easier in Lisp, due to the obvious correspondence
between external and internal representation and a standard interface
to the compiler/type facilities (in the form of macros and type
predicates).

I think in order to fulfill their promise in this area, functional
programming languages should probably go back to Lisp notation.
Furthermore, some standardization work on interfaces still needs to be
done. Hopefully, the result would be cleaner than what Lisp has to
offer right now.

					Thomas.

PS: What statically typed functional languages with Lisp-like notation
are available? I believe MIT has something; can that be FTP'ed?

In article <annius.717696151@freyr> annius@sif.research.ptt.nl (Annius Groenink) writes:

   tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

   >I think in order to fulfill their promise in this area, functional
   >programming languages should probably go back to Lisp notation.

   (I
     (Don (' (t
		(think
		      (so)))))) (!).

Well, in SML, that would be:

   I(
     Don( Q( t(
		think(
		      so()))))) (bang).

That doesn't look any prettier to me.

Seriously, I somehow doubt that the "gain in readability" from putting
your parens after your function names, not having to put parens around
"let" and "if", and using infix for the occasional numerical operation
(NB, I write a lot of numerical code myself), is really worth it
compared to the difficulties such irregularities in syntax cause for
tools, tool writers, and simple-minded human readers like me. But, all
these things are a matter of taste, and I don't want to start a flame
war.

Incidentally, what SML modes for Emacs are out there? I have Lars'
mode, but it seems to get confused on occasion, and I can't get it to
give me the simple, no-frills layout that I want.

					Thomas.

It is certainly nice to be able to manipulate programs in terms of a
straightfoward structural representation.  However, this doesn't mean
that one has to be content with a primitive concrete syntax such as
Lisp's.  It suffices to have a parser that translates one's concrete
syntax into a more convenient representation for manipulation by
programs.  For instance, the next release of SML of NJ will provide
a syntax tree datatype, currently called ast (but this name may change
before the release) which is fairly close to the concrete syntax.
Of course, parentheses have nothing to do with the representation of
of programs in terms of a syntactic datatype.  [Note also that Lisp
S-expressions are not equivalent to an abstract syntax representation
for Lisp -- most S-expressions do not correspond to well formed Lisp
programs or expressions.]

Anyone who prefers Lisp style concrete syntax is free to define such
a syntax for, say, Standard ML.  They could then write a parser that
would translate their syntax into a type like ast for processing by
the rest of the compiler.  The ast representation mentioned above is
"pre-elaboration", meaning static analysis and type checking take
place after the construction of the ast representation of a program.
This makes the parser's task fairly simple.

Actually, I would prefer to move further away from Lisp style syntax.
One of the unfortunate aspects of SML syntax is the overloading and
consequent over-use of parentheses.  Parentheses play three main
roles:

 (1) grouping (this is the most fundamental role)

 (2) bracketing tuples as in (1, true, "abc")

 (3) bracketing sequence expressions, as in (print "a"; print "b")

I would prefer to use different notations for (2) and (3).  Angle
brackets would be appropriate for (2), but are unfortunately not
available in ascii (maybe it's time to move on to the ISO Latin 8 bit
character set?).  For (3) the traditional Algol "begin ... end"
notation would probably be fine.

Dave MacQueen
macqueen@research.att.com
Room 2A-431, AT&T Bell Labs, 600 Mountain Ave, Murray Hill, NJ 07974
--
Dave MacQueen
macqueen@research.att.com
Room 2A-431, AT&T Bell Labs, 600 Mountain Ave, Murray Hill, NJ 07974

tmb@arolla.idiap.ch (Thomas M. Breuel) writes:

>Well, in SML, that would be:

>   I(
>     Don( Q( t(
>		think(
>		      so()))))) (bang).

>That doesn't look any prettier to me.

Sorry, I didn't mean to actually merge into the discussion. I'm
more in favour of more friendly languages such as the Haskell-
family. In fact, the only thing I know about Lisp is that is uses
lots of )))))))):)

-- 
Annius Victor Groenink      Universiteit Utrecht      PTT Research Leidschendam
Mathematics/Comp. Sc.        avgroeni@cs.ruu.nl       +31 70 3325445 (weekdays)
Atari ST/Music          A.V.Groenink@research.ptt.nl  +31 70 3464732 (evenings)
_____________My opinions are my opinions____________  +31 5700 29396 (weekends)

In article <DBM.92Sep28220940@ai.allegra.att.com> dbm@allegra.att.com (Dave MacQueen) writes:

   It is certainly nice to be able to manipulate programs in terms of a
   straightfoward structural representation.  However, this doesn't mean
   that one has to be content with a primitive concrete syntax such as
   Lisp's.  It suffices to have a parser that translates one's concrete
   syntax into a more convenient representation for manipulation by
   programs.

I agree, it doesn't mean that, but it makes it somewhat easier since
then both the reader and the machine have a better idea of what the
other is "talking about". In my case it's not a question of "being
content with a primitive concrete syntax", but actually preferring it.
But there are lots of people with either kind of taste, and it is
pointless to argue which is "better".

Still, I have yet to see tools that can indent SML code properly and
consistently; their lack already is an indication to me that there is
_some_ problem with the syntax as it is. I'd like to be proven wrong
in this perception...

I will admit, though, that I don't see how Lisp syntax goes in a
straightforward way with the way SML handles arguments, since one of
the things I like about SML syntax is the seamless way in which tuples
double as "first-class argument lists". Fortunately, thanks to the
availability of ast's in the next release of NJ/SML that you just
announced, we all will have ample opportunity to experiment.

   Actually, I would prefer to move further away from Lisp style syntax.
   One of the unfortunate aspects of SML syntax is the overloading and
   consequent over-use of parentheses.  Parentheses play three main
   roles:

    (1) grouping (this is the most fundamental role)

    (2) bracketing tuples as in (1, true, "abc")

    (3) bracketing sequence expressions, as in (print "a"; print "b")

   I would prefer to use different notations for (2) and (3).  Angle
   brackets would be appropriate for (2), but are unfortunately not
   available in ascii (maybe it's time to move on to the ISO Latin 8 bit
   character set?).  For (3) the traditional Algol "begin ... end"
   notation would probably be fine.

Well, I'm not so sure I agree. I think (3) should not matter, since
imperative programming is the exception, not the rule in SML (right?).
And I don't see much of a conflict between (1) and (2); in particular,
I like the fact that function calls with tupled arguments look
"normal" ("f(x,y,z)") right now.

Incidentally, instead of "begin ... end", you can use "let in ... end".

Also, ironically, if you use currying frequently, your expressions will
end up looking like Lisp expressions anyway:

	map (compose (invert f) (invert g))
            (sublist l (position l x) (3 + position l x))

"Asymptotically", the number of parens is the same...

					Thomas.

In article <1992Sep28.183322.29254@m.cs.uiuc.edu>, hasker@m.cs.uiuc.edu (Rob Hasker) writes:
|> All you need is a parser which translates the concrete syntax to the abstract
|> syntax (i.e., Lisp-like notation), and an "unparser" to translate back.  This
|> way the user gets the benefit of being able to write readable code and the
|> rewrite engine doesn't have to parse anything.  This approach works very well
|> for the transformation system on which I'm working (Uday Reddy's Focus system).
|> 
|> Rob

We do something similar in SISAL (Streams and Iteration in a Single
Assignment Langauge for the curious).  We maintain a functional
intermediate language (IF1) below the programmer source level.  We can
actually do code optimizations and other code re-writes and then
``uncompile'' the result back to SISAL!

Again, we get the advantages of human readible, functional code
without losing the advantages of a fully functional backend.

-- 
Pat Miller                            I have many opinions, but they
patmiller@llnl.gov                      generally aren't humble ones

In <1992Sep26.212935.26809@eng.umd.edu> clin@eng.umd.edu (Charles Lin) writes:
>   So, I'm interested in why you wanted to do work in this area, and
>also what you think the important kinds of questions or work will
>be done in the area, either now, or in the future.

  I think functional language compiler writers will be addressing a question
which is very important for compiler writers for all languages:

  Why does that other compiler produce better code than mine, and how can I
  change mine to do the same thing?

For functional language compiler dudes, they are a heck of a long way away
from a C compiler, but on the other hand they have referential transparency
to help them along.

John

In article <TMB.92Sep29100759@arolla.idiap.ch>, tmb@arolla.idiap.ch (Thomas M. Breuel) writes:
|> In article <DBM.92Sep28220940@ai.allegra.att.com> dbm@allegra.att.com (Dave MacQueen) writes:
|> 
|>    Actually, I would prefer to move further away from Lisp style syntax.
|>    One of the unfortunate aspects of SML syntax is the overloading and
|>    consequent over-use of parentheses.  Parentheses play three main
|>    roles:
|> 
|>     (1) grouping (this is the most fundamental role)
|> 
|>     (2) bracketing tuples as in (1, true, "abc")
|> 
|>     (3) bracketing sequence expressions, as in (print "a"; print "b")
|> 
|> 
|> Well, I'm not so sure I agree. I think (3) should not matter, since
|> imperative programming is the exception, not the rule in SML (right?).

well, what about the example given, namely printing (and more generally
using input/output streams)?  this is even more true in concurrent ml,
in which communication between threads is done on channels.  

|> And I don't see much of a conflict between (1) and (2); in particular,
|> I like the fact that function calls with tupled arguments look
|> "normal" ("f(x,y,z)") right now.

i guess i might be missing the point here.  by (1), i thought this 
referred to expressions like f(g(h(k x))) having tons of parens, vs.
f g h k x, which has none.  i don't see how this relates to your
comments.

- thomas

In article <farrell.717828892@coral>, farrell@coral.cs.jcu.edu.au (John Farrell) writes:
|> For functional language compiler dudes, they are a heck of a long way away
|> from a C compiler, but on the other hand they have referential transparency
|> to help them along.

This isn't necessarily true.   Functional language compilers can
``rediscover'' the imperative structure underneath the function structure
of the source code  -- this makes an efficient mapping possible if
you can eliminate copying and other memory problems.  This has been
done for SISAL (see CACM, Aug. 92 --- Retire FORTRAN: A Debate Rekindled by
Dave Cann).

-- 
Pat Miller                            I have many opinions, but they
patmiller@llnl.gov                      generally aren't humble ones

In article <1992Sep30.175841.19500@cs.cornell.edu> tyan@cs.cornell.edu (Thomas Yan) writes:

   In article <TMB.92Sep29100759@arolla.idiap.ch>, tmb@arolla.idiap.ch (Thomas M. Breuel) writes:
   |> In article <DBM.92Sep28220940@ai.allegra.att.com> dbm@allegra.att.com (Dave MacQueen) writes:
   |> 
   |>    Actually, I would prefer to move further away from Lisp style syntax.
   |>    One of the unfortunate aspects of SML syntax is the overloading and
   |>    consequent over-use of parentheses.  Parentheses play three main
   |>    roles:
   |> 
   |>     (1) grouping (this is the most fundamental role)
   |> 
   |>     (2) bracketing tuples as in (1, true, "abc")
   |> 
   |>     (3) bracketing sequence expressions, as in (print "a"; print "b")
   |>
   |> And I don't see much of a conflict between (1) and (2); in particular,
   |> I like the fact that function calls with tupled arguments look
   |> "normal" ("f(x,y,z)") right now.

   i guess i might be missing the point here.  by (1), i thought this 
   referred to expressions like f(g(h(k x))) having tons of parens, vs.
   f g h k x, which has none.  i don't see how this relates to your
   comments.

McQueen was suggesting using different syntax for constructing tuples.
I very much object to that, since the current syntax makes tupled
function calls (the most common case of function call, unless you
happen to curry everything) look "normal":

	f(x,y,z)

looks much nicer to me than something like

	f[< x, y, z >]

					Thomas.

tmb@arolla.idiap.ch (Thomas M. Breuel) wrote:

> Too bad that languages like SML (and, moreso, Haskell) have adopted
> such a comparatively complex syntax. Writing programs to manipulate
> programs is much easier in Lisp, due to the obvious correspondence
> between external and internal representation and a standard
> interface to the compiler/type facilities (in the form of macros and
> type predicates).

I'm not sure that languages should encourage such a reflective
approach.  Surely it is better to maintain a clear division between
the `levels' of a compiler system in order to retain semantic
simplicity.  As I see it, it's the semantic simplicity and strong type
enforcement that make developing in a functional programming language
so much more productive.

On a practical note: Introducing reflection of the sort you mention
makes it impossible (or at least difficult) to deliver applications
separate from the compiler.  When your compiler is as complex as a
truly standard ML compiler must be, this is a serious problem.

I agree, however, that the syntax of Standard ML is too complicated.
In fact, it requires infinite lookahead to parse Standard ML (New
Jersey and Poly/ML don't implement it).  This is a shame after so much
effort has gone into the semantics.
---
Richard Brooksby <richard@harlqn.co.uk>
ML Project / Symbolic Processing Division / Harlequin
+44 223 872522