Implementing "function literals" in an ANSI C -like programming language 
Author Message
 Implementing "function literals" in an ANSI C -like programming language

I have thought of how to include "function literals" in a C-like
language. Below is what I have written so far. If you have any questions
or comments, feel free to reply.

Thursday 15th February 2001

                IMPLEMENTING FUNCTION LITERALS IN A ANSI C -LIKE
                PROGRAMMING LANGUAGE
                ------------------------------------------------
                an informal specification

A common C program is composed of functions, like this:

    #include <stdio.h>
    void message(void)
    {
        printf("Hello, world!\n");
    }
    int main(void)
    {
        message();
        return 0;
    }

Functions can be freely called from within other functions, but their contents
(ie. definitions) stay the same. Often the need to have the same function call
perform various functions arises, one way around this is to use function
pointers:

    #include <stdio.h>
    void (*function)(void);
    void message(void)
    {
        printf("Hello, world!\n");
    }
    void another(void)
    {
        printf("Hello again, world!\n");
    }
    int main(void)
    {
        function=message;
        function();
        function=another;
        function();
        return 0;
    }

This works, but has two constraints: First, the syntaxes for a static function
and a function pointer differ from each other. Second, every function called
(either statically or via a pointer) must actually be implemented in a named
function at file scope. This makes standard C functions "low order".

I propose a new scheme of making functions of a bit "higher order", while still
keeping the language ANSI C -like. In my proposition, function definitions at
file scope are replaced by "function literals", which can be defined anywhere.
A function literal looks like a standard C function definition, without the
function name. Here is an example of a function literal.

    void(void)
    {
        printf("Hello, world!\n");
    }

Function literals, like any other literals, can be assigned to variables. The
variables must be declared to match the type of the function literal. Here is
an example.

    void function(void);
    function=
        void(void)
        {
            printf("Hello, world!\n");
        };

Of course, declararation and initialisation can be combined:

    void function(void)=
        void(void)
        {
            printf("Hello, world!\n");
        };

Function literals can be called either via pointers or directly. When calling a
function literal directly, the parantheses () are written directly after the
closing curly brace of a function literal. Here is an example program that
demonstrates both cases.

    #include <stdio.h>
    void function(void)=
        void(void)
        {
            printf("Hello, world!\n");
        };
    int main(void)=
        int(void)
        {
            function();
            void(void)
            {
                printf("Hello again, world!\n");
            }();
            return 0;
        }

Note that main is now also a function variable instead of an actual function.
The party executing the program is assumed to implicitly call main via a
suitable method.

Passing parameters to function literals is a bit tricky, because parameter
names might change when the function literal is assigned to another function
variable, and when called directly, parameter names are undefined. To get
around this, I have decided to put the parameter names in the definition of
the actual literal - not the variable. The variable declaration can have
parameter names, but they are ignored.
For example:

    #include <stdio.h>
    int a=0;
    void foo(int b)=
        void(int c)
        {
            printf("a=%d, c=%d\n", a, c);
        };
    void bar(int a);
    int main(void)=
        int(void)
        {
            foo(1);
            bar=foo;
            bar(2);
            return 0;
        }

This prints "a=0, c=1" and "a=0, c=2". Note that in the call to bar(2), the
parameter name a in void bar(int a) does not override the global variable a.
Function literals are strongly typed according to their parameters. An
assignment between two incompatible function types is erroneous. For example,
void foo(int a)=void(int b, int c){printf("%d %d\n", b, c);}; will fail.

Like any other literals, function literals also have a value, and they can be
used in expressions. When used with any other operators than assignment or
function call, a function literal's value is the address where its code is
stored. For example, this code:

    #include <stdio.h>
    int main(void)=
        int(void)
        {
            printf("%p\n", main);
            return 0;
        }

might print "0x12345678" or "0x9ABCDEF0" or something similar depending on
where the code generated from main's value is stored.
Function literals also implement "pointer arithmetic", but it usually does
not make any sense. For example, if the variable function is assigned a value of
void(void){printf("Hello, world!\n");} and the value takes 64 bytes of memory,
then function+1 will point to 64 bytes after the start of this code, function+2
will point to 128 bytes after the start, and so on. These addresses generally
don't contain anything sensible.

Programs in "C with function literals" could be converted into ANSI C programs
by replacing every function variable with a function pointer variable, and every
function literal (every appearance of any literal, not just every distinct
literal) with normal functions with suitable machine-generated names.
For example, this program:

    #include <stdio.h>
    void message(void);
    int main(void)=
        {
            message=
                void(void)
                {
                    printf("Hello, world!\n");
                };
            message();
            return 0;
        }

could be converted to:

    #include <stdio.h>
    void (*message)(void);
    void FUNCTION_LITERAL_AA(void)
    {
        printf("Hello, world!\n");
    }
    int main(void)
    {
        message=FUNCTION_LITERAL_AA;
        message();
        return 0;
    }

This eliminates the need of assigning function literals to variables before
calling them, because the literal's body will always be converted into a
callable function. For example, this program:

    #include <stdio.h>
    int main(void)=
        int(void)
        {
            void(void)
            {
                printf("Hello, world!\n");
            }();
            return 0;
        }

could be converted into this program:

    #include <stdio.h>
    void FUNCTION_LITERAL_AA(void)
    {
        printf("Hello, world!\n");
    }
    int main(void)
    {
        FUNCTION_LITERAL_AA();
        return 0;
    }

--

| Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
| http://www.*-*-*.com/ ~palaste       W++ B OP+                     |
\----------------------------------------- Finland rules! ------------/

"We sorcerers don't like to eat our words, so to say."
   - Sparrowhawk



Tue, 05 Aug 2003 03:49:02 GMT  
 Implementing "function literals" in an ANSI C -like programming language
Hmmm.  Looks like Algol 68 routine texts, save that you have to write
the prototype twice for the usual function definition.  Would you allow

        printf("%f\n", traprule(double(double x){return x * x;},
                0.0, 5.0));

?

It does look like something it would be straightforward to preprocess
into C, but I don't know how advantageous people will find it.

        James Jones

Opinions herein are those of the author, and not necessarily those
of any organization.



Tue, 05 Aug 2003 04:59:13 GMT  
 Implementing "function literals" in an ANSI C -like programming language
Followup-To: comp.lang.misc


Quote:
> I propose a new scheme of making functions of a bit "higher order",
> while still keeping the language ANSI C -like. In my proposition,
> function definitions at file scope are replaced by "function
> literals", which can be defined anywhere.

Can a locally defined function refer to local variables of the function
it is defined in?

If no, then it does not provide anything new to C except an alternative
syntax.

But if yes, then I assume a function pointer holds a reference to
the environment in which the function was created (otherwise you
can't know where to find these local variables). What happens when
the function in which our function was defined returns, and you use
the function pointer after that?

If the program crashes, then you reinvented downward function closures,
as they were in Pascal I believe (standard Pascal, not Turbo Pascal).
You can pass local functions to other functions, but you can't return
them in any useful way. This provides a little more freedom than C,
e.g. you can pass functions which depend on local data as arguments to
qsort, and various libraries no longer need to bundle function pointers
with void* values to be passed to these functions as parameters (this
simulates function closures as long as memory can be managed). At
the cost of making function pointers less efficient than in plain C.

gcc manages to have downward function closures as an extension,
without changing the traditional C representation of function pointers.
But this is very tricky, requires building machine code on the stack
at runtime. Unfortunately there are no common C extensions which
would allow bundling data with function pointers in more useful ways,
which implies that an implementation of another language which wants
to allow programmers to interface to C and express their functions
as C function pointers - must do similar nonportable tricks itself,
usually building machine code on the heap.

But if returning locally defined functions is supposed to work,
such that local variables of the outer function are forced to live
as long as some locally defined function is alive, then things become
interesting. This requires garbage collection, which is not compatible
with the goal of being C-like.

Almost all languages have garbage collection. About half of them have
full function closures, i.e. you can easily define functions locally
and pass them as data objects. There is a continuous spectrum of how
naturally and easily they can be used. In many languages it could
be added without technical problems, but language designers haven't
thought about doing it well.

To summarize, it's nothing new, but not in C. You could add a little
to C in this direction, but C and C++ will never allow convenient
functional programming without radical changes to the core of the
language (beginning with memory management, then the type system,
then syntax).

--

 \__/
  ^^                      SYGNATURA ZASTPCZA
QRCZAK



Tue, 05 Aug 2003 05:05:34 GMT  
 Implementing "function literals" in an ANSI C -like programming language

Quote:
> Followup-To: comp.lang.misc

Sorry, but I'm reading only c.l.c
Quote:


> > I propose a new scheme of making functions of a bit "higher order",
> > while still keeping the language ANSI C -like. In my proposition,
> > function definitions at file scope are replaced by "function
> > literals", which can be defined anywhere.

> Can a locally defined function refer to local variables of the function
> it is defined in?

> If no, then it does not provide anything new to C except an alternative
> syntax.

And (optionally) anonymity.

Quote:
> But if yes, then I assume a function pointer holds a reference to
> the environment in which the function was created (otherwise you

f> can't know where to find these local variables). What happens when

Quote:
> the function in which our function was defined returns, and you use
> the function pointer after that?

> If the program crashes, then you reinvented downward function closures,
> as they were in Pascal I believe (standard Pascal, not Turbo Pascal).

And PL/1, and as already noted algol, and Ada,
and (it almost goes without saying) LISP.
COBOL (-85) does have nested procedures,
but (last I looked) not procedure pointers
(though it does have call by dynamic name!).

(Good discussion about implementation issues,
and upward closures, snipped.)

--
- David.Thompson 1 now at worldnet.att.net



Mon, 18 Aug 2003 13:43:42 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. "Implementing Prolog Programs Free from Unification"

2. Underscore ("_") in numeric literals

3. "Formal CS"

4. string.join(["Tk 4.2p2", "Python 1.4", "Win32", "free"], "for")

5. "ANSI Common Lisp" an excellent book

6. Function names and "filter" function

7. Implementing "Bookmark" menu

8. Implementing "Apply" button

9. How to implement "DefaultFill" for List

10. Implementing the "other" rexec

11. implementing "in"

12. Has anyone implemented "Spin widget"?

 

 
Powered by phpBB® Forum Software