From: Jack Waugh [mailto:waugh@...]
>The group blurb says, among other things, "In short, concatenativeYou'll have to read up on functional languages... This group is a little
>languages behave in a way [that] looks imperative (like C or Perl),
>but can be reasoned about in a functional manner (like ML or
>Haskell).".
>What is one characteric of Joy, ML, and Haskell that makes it
>possible to reason about them in a way that isn't possible with, say,
>C?
more specialised.
>C is based on function composition, denoted by the ";" operator.Yes, you can work that way in theory; however, the behavior of the
>Each C "statement" denotes a function in one parameter to produce one
>result. In all cases, the type of the parameter and that of the
>result is "execution state". An execution state includes a stack, an
>indexed memory space, open files, the system clock, the mental states
>of the users, the phase of the moon, etc. Since the result of a
>function has the same type as the parameter and this type is the same
>for all functions in the language, we can readily construct
>compositions of any of the functions. . . .
'functions' in this model is VERY hard to anticipate and model. It just
doesn't work in practice.
In addition, C has MANY constructs which look like 'functions' to this
model, but aren't. (Declarations, for example.)
You wind up with a vague, general rule, with a billion exceptions and
special cases.
-Billy
--- In http://groups.yahoo.com/group/concatenative/message/684, Billy
Tanksley <wtanksley@b...> wrote:
> You'll have to read up on functional languages... This group isThis group struck me as staking out a viewpoint that might shed light
> a little more specialised.
on what the functional-language people (and more broadly the
declarative-language people) are saying about what it is about
programming notations that makes programs in them easy or difficult
to reason about. Perhaps this group plots a point on a slippery
slope leading between functional programming and imperative
programming.
> >C is based on function composition, denoted by the ";" operator.By contrast, how is the behavior of the functions in a concatenative
> Yes, you can work that way in theory; however, the behavior of the
> 'functions' in this model is VERY hard to anticipate and model.
> It just doesn't work in practice.
language easier to anticipate and model, and how does it work better
in practice with them? Just cite an example or two.
> In addition, C has MANY constructs which look like 'functions'OK, declarations by themselves don't denote functions (at least, not
> to this model, but aren't. (Declarations, for example.)
to be applied at runtime). Please just think of them as part of the
syntax for specifying the meaning of the utterances that mention the
variables declared. Also, they bear on the data type of all
arguments, by affecting the size of the indexed memory.
> You wind up with a vague, general rule, with a billion exceptionsI see no need for vagueness.
> and special cases.
My point is, if Joy is functional on the grounds that we can analyse
it as applying the composition of functions to an argument whose data
type is as big as all outdoors (and seems to be linear), what
language isn't functional? Cite an example of an imperative
language. All programming languages are functional. Perhaps being
functional is a matter of degree; some languages are more functional
than others. Perhaps more-functional languages are easier to reason
about than less-functional languages. Please help me articulate how
this is so, if it is.
Indeed, to capture a semantics for C in the terms I suggested would
require a lot of words, and you might count them as a "billion
exceptions and special cases". But that's just because C is messy,
not because C is imperative. You could recast all my questions about
C substituting a simpler imperative langauge. APL might make a
fairly good example. Or some simple dialect of Forth without an
assembler. That's an even better example because it will be closer
to Joy. One difference between that language and Joy would be that
Joy provides lists and list operations and, significantly,
combinators that can execute lists as code. But this can't be
contributing to making Joy easier to reason about because the
programmer doesn't have to use those features. The other difference
between our simple dialect of Forth and Joy would be that the Forth
would provide operations involving "variables". The data type of all
arguments would include, multiplied by the stack data type, a data
type of mappings from "locations" to values (such as can populate the
stack) and mappings from words to locations.
On Mon, 18 Jun 2001, Jack Waugh wrote:
> This group struck me as staking out a viewpoint that might shed lightThink about this progression (I hope also that it is progress):
> on what the functional-language people (and more broadly the
> declarative-language people) are saying about what it is about
> programming notations that makes programs in them easy or difficult
> to reason about.
imperative Ls ==>
purely functional "applicative" Ls ==>
purely functional "concatenative" Ls (Joy)
> My point is, if Joy is functional on the grounds that we can analyseOK, perhaps one should always say "purely functional".
> it as applying the composition of functions to an argument whose data
> type is as big as all outdoors (and seems to be linear), what
> language isn't functional?
A language is purely funnctional if and only if it has no
imperative/procedural features. The most important such
feature is the assignment statement, here in Pascal and in C:
x := y + z
x = y + z
The lambda calculus language Lisp started off as a purely functional
language, at that time it was like its theoretically cleaner sibling,
Landin's (1965 or thereabouts) ISWIM. But then assignment was added,
and both are present in Common Lisp and in Scheme. The same
happened in ML which (if I understand the theory behind it correctly)
is based on the typed lambda calculus. Nevertheless, it is
often useful to speak of the purely functional subsets of
Lisp, Scheme, and ML. The only widely known purely
functional languages around these days are Miranda
Haskell and, I believe, Clean. But there may be others.
> Cite an example of an imperativeFortran, Cobol, Algol60, Algol68, Snobol, Basic, Pascal, C, C++,
> language.
Ada, Perl, sh, csh, bash, and those languages that have a
very useful purely functional fragment: Lisp, Scheme, ML.
> All programming languages are functional.Well OK, most have functions, and you can write useful stuff
just using that. But they are not purely functional, and most
programs written in them use the imperative features a lot.
> Perhaps beingNo, for the languages it is not a matter of degree. Either
> functional is a matter of degree; some languages are more functional
> than others.
they have assignment or they do not.
> Perhaps more-functional languages are easier to reasonOne might speak of degrees when it comes to the programs
> about than less-functional languages. Please help me articulate how
> this is so, if it is.
written in the language. Some programs use assignment a lot,
and some use it very little.
> between our simple dialect of Forth and Joy would be that the ForthIf the language has locations and assignable variables then the
> would provide operations involving "variables". The data type of all
> arguments would include, multiplied by the stack data type, a data
> type of mappings from "locations" to values (such as can populate the
> stack) and mappings from words to locations.
language is not purely functional.
I hope all this helps.
- Manfred
I'm playing devil's advocte here. I _feel_ that the concept of pure
functional language as easier to reason about than imperative
language has a great deal of validity. But not being able to
articulate why, or even what a functional language is, I take the
devil's position that there is no such distinction.
Now you say a language with assignment is not purely functional. You
say the assignment changes the value of a variable. I say I can
interpret the situation without admitting that there is a change in
the value of a variable.
x := y + z
is a pure function that takes one argument and produces one result.
The argument and result belong to the same type, so the ":=" command,
woops, I mean function, could belong to a concatenative language (if
I understand the meaning this group assigns to that term) (assuming
you can quote code, and that concatenating quoted passages results in
the composition of the functions they represent). Of course the
argument type and result type I have in mind admits of instances,
like your dictionary, that associate names to values. For example,
the argument to the above function might contain an association "x" --
> 3, and perhaps the result looks similar except that the "x"assocation in it leads to 4 instead of 3. The value of x has not
changed. It is still 3 in the argument and 4 in the result. So, no
change in the values of any variables, therefore no imperative
language.
On Tue, 19 Jun 2001, Jack Waugh wrote:
> I'm playing devil's advocte here. I _feel_ that the concept of pureFirstly "functional languages" are more a cluster of features than a
> functional language as easier to reason about than imperative
> language has a great deal of validity. But not being able to
> articulate why, or even what a functional language is, I take the
> devil's position that there is no such distinction.
defined object. (A syndrome rather than a disease? ;-)) So lets take some
of the "functional" features and highlight them.
Speaking C to be neutral...
Reason about...
int y = 2;
int f( int x)
{
return g(x)+x+y;
}
Does g modify x? If x is modified, does the modification occur before or
after the "+x"? Does g modify y? When? Will g(x) have the same value next
time you call f?
Without a specification for g, you cannot answer those
questions and you cannot reason further about the behaviour of f.
In a Functional Language in which side effects within expressions have
been banned, you can reason quite a lot.
You know x is not modified by g, and you don't care when!
You know y was not modified by g.
In a pure "recursive" language without any lexical scoping, you can also
say g does not depend on y, and hence the only dependency of f on y is
"+y". You know g(x) will be the same every time f is called with the same
value of x.
In a "functional language" with delayed evaluation you needn't care
whether or not the parameters are computable until you actually reference
them. eg.....
void this_func()
{
int array[10];
int i = 10000;
myfunc(i, a[i]);
}
void myfunc( int i, int b)
{
if( i < 10)
dosomething_with( b);
else
error();
}
In C, this code is wrong and will probably segfault, you're referencing
a[10000] when you call myfunc, but with delayed evaluation its fine.
Weird? No, this is standard C....
return i < 10 && a[i];
If i >=10, the second term not evaluated due to short circuit evaluation
of &&.
In a functional language a function is a first order object, you can
manipulate them and combine them in interesting ways. C pointer to
functions takes you some of the way.
I wrote a fairly major program in R, a lovely statistics scripting
language with Scheme-like semantics. The curious thing was it didn't have
a single looping construct. It didn't need one!
Once I had my head wrapped around the idea that the functions move, not
the data, it was much clearer than the procedural version.
Now consider functional composition in infix (C like) languages....
f( g( x, y), z) or in prefix (lisp like) langauges....
(f (g x y) z) or in postfix Joy like languages....
z y x g f
Which is simpler to reason about? Which is simpler to write rewrite rules
for? Answer: the one that maps string concatenation (the domain of
rewriting) to function composition (the domain of semantics).
No, stop that postscript / forth like mental image. You are thinking of
this aren't you....
"z y x g f" means put z on the stack, put y on the stack,
put x on the stack, pop x, pop y evaluate g push result on the stack,
pop g(x,y), pop z evaluate f, push result.
Wrong! Think of it rather as f( g( x( y( z( stack))))), no even better
think of it as z o y o x o g o f (stack) where o denotes functional
composition.
If you can reduce any substring to id, you can remove that substring!
Lovely! If any substring is equivalent to something else, you can replace
that substring by that something else. Lovely!
Read Manfred's paper on the rewrite rules for Joy. My explosive out loud
comment on reading that paper was "This language _is_ a Joy!"
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@...
New Zealand