# RE: [stack] Reasoning about Programming Languages in a Functional Manner

## Billy Tanksley — 2001-05-31 18:25:27

    From: Jack Waugh [mailto:waugh@...]

     >The group blurb says, among other things, "In short, concatenative

    >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?

     You'll have to read up on functional languages... This group is a little

    more specialised.

     >C is based on function composition, denoted by the ";" operator.

    >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. . . .

     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.

    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

## Jack Waugh — 2001-06-18 13:48:54

    --- 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 is

    > a little more specialised.

     This group struck me as staking out a viewpoint that might shed light

    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.

    > 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.

     By contrast, how is the behavior of the functions in a concatenative

    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'

    > to this model, but aren't.  (Declarations, for example.)

     OK, declarations by themselves don't denote functions (at least, not

    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 exceptions

    > and special cases.

     I see no need for vagueness.

    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.

## Manfred von Thun — 2001-06-19 04:56:23

    On Mon, 18 Jun 2001, Jack Waugh wrote:

     > This group struck me as staking out a viewpoint that might shed light

    > 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.

     Think about this progression (I hope also that it is progress):

    imperative Ls  ==>

    purely functional "applicative" Ls ==>

    purely functional "concatenative" Ls (Joy)

     > 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?

     OK, perhaps one should always say "purely 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 imperative

    > language.

     Fortran, Cobol, Algol60, Algol68, Snobol, Basic, Pascal, C, C++,

    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 being

    > functional is a matter of degree; some languages are more functional

    > than others.

     No, for the languages it is not a matter of degree. Either

    they have assignment or they do not.

     > Perhaps more-functional languages are easier to reason

    > about than less-functional languages.  Please help me articulate how

    > this is so, if it is.

     One might speak of degrees when it comes to the programs

    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 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.

     If the language has locations and assignable variables then the

    language is not purely functional.

    I hope all this helps.

      - Manfred

## Jack Waugh — 2001-06-19 09:19:38

    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.

## John Carter — 2001-06-19 23:14:14

    On Tue, 19 Jun 2001, Jack Waugh wrote:

     > 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.

     Firstly "functional languages" are more a cluster of features than a

    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