Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!newstop!exodus!rbbb.Eng.Sun.COM!chased
From: chased@rbbb.Eng.Sun.COM (David Chase)
Newsgroups: comp.lang.misc
Subject: Re: On whether C has first-class composable functions
Message-ID: <6800@exodus.Eng.Sun.COM>
Date: 29 Jan 91 02:15:07 GMT
References: <3576:Jan2622:55:2991@kramden.acf.nyu.edu> <1991Jan27.035619.24981@spool.cs.wisc.edu> <21245@yunexus.YorkU.CA> <9606:Jan2806:52:1991@kramden.acf.nyu.edu>
Sender: news@exodus.Eng.Sun.COM
Organization: Sun Microsystems, Mt. View, Ca.
Lines: 70

brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>In article <21245@yunexus.YorkU.CA> oz@yunexus.yorku.ca (Ozan Yigit) writes:
>> Yes, you were able to write an interpreter that contained said
>> functionality, minus the scoping details.
>> Amazing.
>'Twas hardly amazing. What amazes me is that there are *still* people
>posting to this newsgroup asking questions like ``Ya know, I haven't
>seen any portable first-class composable function implementations that
>don't have arbitrary limits.  Is this because they are impossible, or is
>there some sneaky way?'' ...

Dan, you obviously missed the point.  Most of the questioners assumed
that you weren't going to write an interpreter.  Of course it works if
you write an interpreter.  Nobody is surprised, or thinks it is
particularly interesting, if you solve the problem by writing an
interpreter.  By that standard, C has first-class functions, closures,
partial application, garbage collection, and threads -- I'll just
write an interpreter.

No doubt you'll claim that your answer is different, because the text
of your program is input to a C compiler, not an interpreter.  Bogus
distinction, that -- consider the innards of the emacs lisp
interpreter, or the innards of the x-lisp interpreter.  One just makes
calls from C to manipulate the appropriate data structures, and away
you go.  Your code might look something like:

    DEFUN ("directory-files", Fdirectory_files,
           Sdirectory_files, 1, 3, 0,
      "Return a list of names of files ...")
      (dirname, full, match)
         Lisp_Object dirname, full, match;
    {
      DIR *d;
      char slashfilename[MAXNAMLEN+2];
      char *filename = slashfilename;
      int length;
      Lisp_Object list, name;
    ...

(above was an excerpt from GNU Emacs)

OR, perhaps

    /* xread - read an expression */
    NODE *xread(args)
      NODE *args;
    {
        NODE ***oldstk,*fptr,*eof,*rflag,*val;
        /* create a new stack frame */
        oldstk = xlsave(&fptr,&eof,(NODE **)NULL);
        ...
        /* restore the previous stack frame */
        xlstack = oldstk;
        /* return the expression */
        return (val);
    }

(above was an excerpt from Xlisp)

See?  "Functions" in these interpreters work because they obey some
protocol (just like your "functions"), and as long as that protocol is
obeyed, the "functions" have all the power of "functions" in the
language being interpreted.  That's why your answer is boring; it's
obvious.

By the way Dan, how is it that growing arrays by reallocation has
quadratic cost?  I must have missed your answer.

David Chase
Sun