? the platypus {aka David Formosa} <dform...@st.nepean.uws.edu.au> writes:

Well, in TRS-80 Level II BASIC, they had a DEF FN construct that
allowed one to define equations as functions. They were simple
expressions, there wasn't any logic allowed, and they were called
"functions" at the time.

I think it was something like:

10 DEF FNR(X)=INT(RND(0)*X)+1
20 R=FNR(6)+FNR(6)
30 IF R=7 OR R=11 THEN PRINT "YOU WIN!" ELSE PRINT "YOU LOSE"

I don't recall if you were allowed to put other variables in the
equations or not. If you were, then I imagine they were just globals
(like everything else).

I think you were able to create functions with both the numeric and
strings types.

Funny, I thought I had blotted most of this stuff out of my psyche.

--
Will Hartung - Rancho Santa Margarita. It's a dry heat. vfr...@netcom.com
1990 VFR750 - VFR=Very Red    "Ho, HaHa, Dodge, Parry, Spin, HA! THRUST!"
1993 Explorer - Cage? Hell, it's a prison.                    -D. Duck

* Marco Antoniotti
| If we want, we could discuss at length why some of the design choices
| of "destructive" operations in Common Lisp sometime have a
| non-intuitive behavior.

do they?  the question is one of which value one looks at, I think.  `sort'
on a list returns a sorted list, but the cons cells that used to be that
list have been reused.  if we look at the return value of `sort', we get
the sorted list.  if we look at a random cons cell that has been reused in
some unspecified way, who's to tell?  like `nreverse' in one implementation
swaps the `car' of cons cells, and in another the `cdr', we cannot know
what a cons cell that has been destructively modified would contain, unless
the operation is specified by the specification of the language, and it
isn't for `sort' or `nreverse'.

or, another way: after (sort <list> <predicate>), <list> is _history_.

#\Erik
--
there was some junk mail in my mailbox.  somebody wanted to sell me some
useless gizmo, and kindly supplied an ASCII drawing of it.  "actual size",
the caption read.  I selected smaller and smaller fonts until it vanished.

Sajid Ahmed the Peaceman <peace...@capital.net> writes:

This is an invalid argument.
To start with, C is _not_ close to the machine.
- most machines do not support C's auto-scaled pointer arithmetic directly
- *NONE* of the C89 integral types supported by the compilers on this
  machine (an UltraSPARC) match the machine's native register size (64 bits).
  [Yes, I know about long long, which is why I said _C89_ integral types.]
- C lets me specify a floating point type that does not exist on this
  machine.  On an older machine from the same manufacturer, NONE of C's
  floating point types were supported in hardware.
- There are some important differences between C functions and what you
  get in assembler.  In fact, on the immediate predecessor of this machine,
  it was actually useful that two C compilers had an option to use a
  calling convention that was _not_ the normal one on this machine.

But the machine flaw is the assumption that compilers are irredeemably
stupid.  What matters is not how close to the machine the *starting* point
is, but how close the compiler can get it.

For the record, I have frequently found Scheme code compiled by Stalin to
run _faster_ than the corresponding C code.

Another reason the argument is flawed is that, as the Fortran people are
fond of pointing out, C is hard to optimise.  Languages (such as Fortran 90)
where the compiler can know more about the program than any standard C
compiler can know about any standard C program, permit better optimisation.

In the examples where Scheme code ran faster than C, generally Fortran
code went even faster.  And nobody talks about Fortran being "close to
assembler".

This is meaningless.  _Which_ Lisp?  _Which_ C?  Which machine/OS?

You shot yourself in the foot there.
Lisp has *all* the control structures that C has.  ALL of them.
And then some.

Yes, several.

Obviously, you have not seen a quicksort in C.  One that came with a
version of UNIX takes (by actual measurement) 177 lines.  The rather
faster one I wrote myself takes 162 lines.  There's an important
optimisation in that without which the C version would be about 80 lines.
The "Engineered" quicksort by Bentley & McIlroy is about 112 lines of C.
Since the partition step itself takes about 6 lines of C, it would be
rather hard to get a readable version of Quicksort in "5 or 6 lines" of C.

--
Four policemen playing jazz on an up escalator in the railway station.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Note that there actually was a real commercial C system for the PC
where qsort() was implemented using Shell sort.

--
Four policemen playing jazz on an up escalator in the railway station.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Sajid Ahmed the Peaceman <peace...@capital.net> writes:

There is nothing in any BASIC standard to require this.
Traditionally, "GOSUB" and "RETURN" manipulated a control stack
just like you'd expect.  Multi-line functions in BASIC are, if
compiled, compiled just like functions in Pascal or C.

        Anyway, I'm sure there are some language designs that don't

Instead of repeating your assertion, PROVIDE SOME EVIDENCE FOR IT!

There have certainly been languages that didn't use *a* stack for
function calls, such as Simula 67, Interlisp, Burroughs Algol, &c.
That's because they supported multiple threads of control, so there
were multiple stacks, or cactus stacks, or spaghetti stacks.

The Algol 60 standard *described* all procedure calls using the "copy rule".
Every Algol 60 *implementation* I've ever heard of used a stack of
activation records, just like Pascal or C.

Even dBase III isn't defined to copy functions when they're called!
--
Four policemen playing jazz on an up escalator in the railway station.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

With a mighty <vfr750EDqHE1....@netcom.com>,
vfr...@netcom.com uttered these wise words...

That's the Basic that I'm thinking of.

Yes, from what I remember, the variables were dynamically scoped,
which is another way of saying that they were global. In your example,
variable X would shadow any already existing X, so that while FNR is
running, X would be 6, but when FNR returns, the old value would
become "visible" again.

As with many things in that Basic, and many other Basic of that
generation, functions were very limited. No wonder they were so rarely
used! Fortunately, these things change, and now it's not unusual for a
Basic to use lexical scoping and compile to native code. Not that this
stops some people from calling Basic "slow". People with long memories
and little recent experience of Basic, I guess.

Hmm. <looks at thread subject> Just like Lisp, really. Most Lisps that
I've used have compiled to native code, and yet some people can only
remember the interpreted lisps, like XLISP. That could be because of
the wide availabilty and age of XLISP, but it's no excuse for assuming
that this is the best or fastest Lisp to be found.

That's a lot like assuming that Small C is the most sophisticated C
compiler you can find, simply because it's the only one that you've
found and used. A little more effort should give you a much better C
compiler, like GNU C/C++.

On the other hand, you might have used a C interpreter...

That sounds familiar, so you could well be right.

Same here. I blame David Formosa. ;)
--
<URL:http://www.wildcard.demon.co.uk/> You can never browse enough
"An operating system is a collection of things that don't fit into a
 language. There shouldn't be one." Daniel Ingalls, Byte August 1981

Every garbage collector capable of working in constant space does this.
You should add "does not modify the original data structure while
traversing it" to your list of no-nos.  (Mark bits are usually shaved off
existing pointers, so they aren't really "explicitly allocated".)

IIRC, Knuth also describes an "elegant" technique somewhere in his AoCP
that involves encoded parent pointers without taking up additional space.
I remember an example involving double-linked lists, but I'm not sure if
this also works for trees.

Of course, the resulting code will be *much* uglier than a simple recursive
function.  But there are people who don't care for elegance, or even
maintainability.  I keep wondering why they feel a need for asserting the
perceived superiority of their favourite language here in comp.lang.lisp.
Perhaps to them, the mere existence of Lisp seems a threat.
And it may well be.

Greetings,

        Jens.
--
mailto:j...@acm.org                 phone:+49-7031-14-7698 (HP TELNET 778-7698)
                                     fax:+49-7031-14-7351
PGP:       06 04 1C 35 7B DC 1F 26 As the air to a bird, or the sea to a fish,
0x555DA8B5 BB A2 F0 66 77 75 E1 08 so is contempt to the contemptible. [Blake]

Henry Baker <hba...@netcom.com> wrote in article
<hbaker-2207970842150...@10.0.2.1>...

Actually, I don't think iteration is necessarily easier to understand than
recursion, but it is unfortunately true that most non-Lispers don't agree.
Also, many popular products for applications programming (like VB) don't know
anything about tail recursion, as witnessed by this dire warning from the VB5
help:

"Caution   Function procedures can be recursive; that is, they can call
themselves to perform a given task. However, recursion can lead to stack
overflow. The Static keyword usually isn't used with recursive Function
procedures."

And of course, the VC++ compiler is equally "broken", if we are to judge by the
standard of your excellent article. <g>

Therefore, I think that proper handling of tail-recursion, like lambda, is
yet-another-killer-Lisp technique that the masses are doomed to remain ignorant
of (unless there is a sudden resurgence of Lisp popularity). <sigh>

Bill House
--
http://www.housewebs.com
Note: my e-mail address has been altered to
confuse the enemy.

        A jump instruction, in assembly would translate
into the following:

        MOVE  IP, address

        which is iterative.

                                Peaceman

Richard O'Keefe may correct me on this, but I believe that the primary
reason for the addition of the SAVE statement to Fortran 77 was to allow
implementations to use stacks in a reliable manner. Technically I
believe Fortran 66 could be implemented using stacks, but entities
became undefined when they left their scope, so that local entites could
not be used in a standard conforming manner to retain state. However,
because most implementations did not use stacks, a significant body of
code was written that assumed that local entities always retained their
values, making it difficult, of course, for compilers to use stacks and
still satisfy their customers. It is true, however, that stacks were not
as useful in Fortran 77 as they were for languages with recursion or
block scoping, let alone more explicitly stack based languages such as
Forth or Pop.

As to recursion, I don't know anyone who wrote standard conforming
recursive Fortran 77 procedures, although I have met a few that thought
they had done so. In every case they were wrong. Some were using
compiler specific extensions, but most had code that worked untill new
standard conforming optimizations were implemented (such as the useage
of a stack). In some sense it is possible to emulate recursion in
Fortran 77, for example the following might be considered a form of
anonymous recursion

      FACTOR = 1
10    IF (M .EQ. 0) THEN
         FACTOR = 1 * FACTOR
      ELSE
         FACTOR = FACTOR * M
         M = M - 1
         GO TO 10
      ENDIF

but similar reasoning might consider iteration to be a way of emulating
recursion.

--

William B. Clodius              Phone: (505)-665-9370
Los Alamos Nat. Lab., NIS-2     FAX: (505)-667-3815
PO Box 1663, MS-C323            Group office: (505)-667-5776
Los Alamos, NM 87545            Email: wclod...@lanl.gov

With a mighty <5r4pom$...@isoit109.bbn.hp.com>,
je...@bbn.hp.com uttered these wise words...

This seems to be the only plausible explanation. It might also explain
many of the Java attacks, which use _identical_ arguments to attacks
on Lisp. They're all bizarre, wrong, and easily refuted.

Are there any archives for comp.lang.lisp, so that we could refer such
people to them? That way, they could simply read the efforts of the
past, and save everybody's time.

Watching hords of C++ programmers trying to convince us that Lisp
can't do what it _is_ doing (and has been doing, for some time) used
to remind me of seal culling. The C++ people were the baby seals,
while Lisp programmers would be the seal trappers, gently tapping the
heads of their prey with CS papers, Lisp software, and Lisp systems.
The result was the quick death of any anti-Lisp argument. Eventually,
the entire thread would die.

A few months would pass, and these events would repeat themselves,
only the words would be different. The arguments would be equally
clueless. Hence the image of baby seal culling. The difference between
C++ programmers and seals is that, well, seals don't write software.

Scary, isn't it?
--
<URL:http://www.wildcard.demon.co.uk/> You can never browse enough
    "My body falls on you like a dead horse" -- Portait Chinois
            Please note: my email address is gubbish

        You could certainly write recursive code, as long as the
number of times the function calls itself is set at compile time.

        There out there. New programming languages are created everyday.
That's what YACC is for.

        Most programming code out there (about 96%) is
nonrecursive. You've been programming is lisp too long.

                                Peaceman

? the platypus {aka David Formosa} wrote:

        To each their own. I find this style a lot easier to read than putting
all the end parenthesis on one line. Sure, it takes up more lines, but
it is a lot easier to group together the commands in the specified
level.

                                                Peaceman

        Igor, most people in the LISP newsgroup can't read your message
(which is MIME encoded). They probably use the EMACS Gnus newsreader,
which is a good newsreader, but doesn't support MIME encoded messages.

                                                Peaceman

In article <53wwmh9xa9....@pavel.physics.sunysb.edu>,

Note quite true.  Even though there's no stack, the parameters still have
to be filled in.  The difference is that this can be done by assigning to
fixed addresses rather than as an offset from the stack pointer.  On early
computers, the performance difference might have been noticeable, but it
would be in the noise these days.

Also, the return address has to be saved somewhere, since a subroutine or
function can be called from multiple places.  Again, the difference is that
there can be a fixed location for each procedure's return address
information, since procedures don't have to be reentrant.  Many early CPU's
had an instruction that would store the old PC in the target address and
then jump to the address following it (on the PDP-8 this was the "JMS
<address>" instruction); a return would be done by doing an indirect jump
through the procedure's starting address (on the PDP-8, "JMP I <address>").
As recursive programming languages and "pure" text pages gained popularity,
this technique lost its utility.

The main advantage of the Fortran-77 model is that the compiler could
determine the total memory requirements of the program.  With recursion
available, there's generally no way to determine the amount of memory that
will be needed for the stack.  Again, this was much more important in the
early days, when memory was extremely limited.

--
Barry Margolin, bar...@bbnplanet.com
BBN Corporation, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>

        How about this:
(defun faa (x)
   (cond
     ((numberp x) (+ x x))
     (t (list x))
   )
)

        It's the same as what you had, except the close paranthesis
are in the same line as the matching open parenthesis.

        I'm not the foremost expert in Emacs, but I do know that your
statement is not entirely true. Whether or not Emacs does the proper
indenting for you depends on whether or not Emacs is set to that mode.
One could set up a .emacs file to set the editor to always stay in
standard text mode, and not ever in c or lisp mode.

                                        Peaceman

Why should (+ 3 4) in Lisp be slower than 3 + 4 in C?

Many Lisp compilers too.

What is a *good* Lisp program versus a *good* C program.
Both language do allow recursive and iterative implementations
of algorithms.

Only if a C programmer would format the code.

--
http://www.lavielle.com/~joswig/

Sajid Ahmed the Peaceman wrote:

   I thought that Fortran77 didn't use the stack. I believe It also
doesn't allow recursion without some programming trickery.
Nick

Sajid Ahmed the Peaceman <peace...@capital.net> writes:

It does.

"Sajid Ahmed the Peaceman" wrote:

Perhaps it would help if you could say exactly what you mean by
"iterative" as opposed to "recursive".

In a piece of assembly language that looks like this (no, it's not
the assembly language of any specific processor known to me; no,
it isn't a usual assembly-language-ish syntax)

    func:   compare r1,=2
            branch-if-less skip:
            push-address after1:
            subtract r1,r1,=1
            jump func:             <---
    after1: push-register r0
            push-address after2:
            subtract r1,r1,=1
            jump func:             <---
    after2: pop-register r2
            add r0,r0,r2
            pop-program-counter
    skip:   move r0,r1
            pop-program-counter

it seems to me that the jumps I've labelled with <--- are *recursive*.

If you argue that they aren't recursive because at the level of
machine instructions there somehow isn't any concept of "function",
then I can equally argue that they aren't iterative either because
at the level of machine instructions there similarly isn't any
concept of "loop".

If you insist on ignoring the higher-level abstractions which
explain what a given piece of machine code means, then sure, you
can refuse to regard the code I give above as a recursive function;
it's just a load of instructions that push and pop things from a
stack and jump around. But then I can refuse to recognise

    loop:   store r1,[r0,r1]
            add r1,r1,=1
            compare r1,=1000
            branch-if-less loop:

as a loop, too: it's just a load of instructions that do arithmetic
and jump around.

In other words, your claim about what machine-level stuff does has
nothing whatever to do with the difference between iteration and
recursion.            

--
Gareth McCaughan       Dept. of Pure Mathematics & Mathematical Statistics,
gj...@dpmms.cam.ac.uk  Cambridge University, England.

In article <33D65B66.3CB8F...@interdyn.com> Nicholas Arthur Ambrose <ni...@interdyn.com> writes:

No it did not (and still does not :-) Once a friend of mine was given
an assignment to implement a recursive algorithm in Fortran, so he had
to emulate the stack using several arrays (remember -- Fortran does
not have structures, either!)

Besides the sipmlicity of the implementation, there was one more
reason for not using the stack: the speed. Indeed, when C or Lisp make
a function call, a lot of run-time job is being done on the
stack, while in Fortran, a function call gets translated into a single
'jump' instruction.

--
Keep talking!                                    /~~~~~~~~~~~~~~~
Dmitry Zinoviev                                 / /~~~~~~~~/    
                                               /  `~~~~~~~'    
_From the Other Side of the World ____________/  Long Island, NY

In article <33D64176....@capital.net> Sajid Ahmed the Peaceman

OK fine, but the question still stands, is it easier for you to see the
sections in

    (defun faa (x)
       (cond
         ((numberp x) (+ x x))
         (t (list x))
       )
    )

Than in

    (defun faa (x)
       (cond
         ((numberp x) (+ x x))
         (t (list x))))

?  This is your claim.

This statement doesn't support your argument much for two reasons.  One, you
want all of the leverage out of Emacs that you can get, so why would you
turn auto indenting off?  Emacs beginners sometimes do not know that they
can tailor the way Emacs does auto-indenting so that it auto indents exactly
the way they like it.  Two, language specific modes do a lot more than just
auto-indenting.  In C mode moving back and forth on conditionals and source
debugging code with a debugger like GDB are just two more examples.
--

William P. Vrotney - vrot...@netcom.com

I would phrase this differently.

The Fortran 66 specification was very carefully crafted to allow
overlays to work.  (Overlays were extremely important at the time.)
In particular, it was important that when a subroutine (which might
never be called again) exited, any data that had been brought into
memory for its use should be allowed to vanish.  So the rule was
that if there are no subprograms active that mention a particular
COMMON block, that COMMON block just plain doesn't exist, and if a
subprogram isn't active, it's local variables don't exist either
(so their values don't have to be written back to the disc when
the overlay containing that subprogram is dropped).

A consequence of this concern for overlays was that Fortran 66 could
be implemented using stacks throughout, and several Fortran 66 implementations
(notably the one from Burroughs for the B6700, a _very_ nice Fortran for its
day) did in fact do this.  This potential was particularly important for
multithreaded use of Fortran.  Burroughs Fortran was multithreaded back in
the '60s, and the PrimeOS operating system (or systems; did PrimeOS for the
P300 and PrimeOS for the 50 series have much in common) was actually written
in Fortran.

The _problem_ was that a lot of other Fortran 66 implementations didn't,
notably the ones for the IBM mainframes.  I have seen _really_ weird code
where you would call a subroutine passing 20 parameters, once, and then
repeatedly call an entry point of the subroutine, passing only one or two
parameters.  People were expecting the old parameters to retain the value
they had last time!  Many Fortran programmers never bothered to read (the
really rather clear and useful) Fortran standard, and were unaware that
their code rather flagrantly failed to conform in this area, just as many
Fortran programmers assumed that 'one-trip' loops were required by the
standard (which had carefully avoided saying anything about them).

So yes, SAVE was added so that old broken code could be repaired and made
to work in stack-oriented implementations.  (Like the UNIX Fortran compilers
I use from time to time.)

They couldn't.  A *program* that conforms to the Fortran 66 or Fortran 77
standards *must not* use recursion.  However, an *implementation* that
conforms to those standards is not required to diagnose it as an error and
may implement recursion.  Several Fortran 66 implementations did, and many
Fortran 77 implementations do.  (Like those UNIX Fortran compilers.)
Fortran 90 _requires_ support for recursion, and one level of block scope.

--
Four policemen playing jazz on an up escalator in the railway station.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

In article <33D63CC4.5...@capital.net> Sajid Ahmed the Peaceman <peace...@capital.net> writes:

   From: Sajid Ahmed the Peaceman <peace...@capital.net>
   Newsgroups: comp.lang.lisp,comp.programming,comp.lang.c++
   Date: Wed, 23 Jul 1997 13:17:56 -0400
   Organization: CADVision Development Corp.
   Reply-To: peace...@capital.net
   Lines: 27

   ? the platypus {aka David Formosa} wrote:
   >
   > >(defun high (x i h)                    ; select the high elts of x onto h.
   > >  (if
   > >    (null x) h
   > >    (if
   > >      (< (car x) i)
   > >        (high
   > >          (cdr x)
   > >          i
   > >          h
   > >        )
   > [...Rest of the code where each open bracket makes a new line...]
   >

           To each their own. I find this style a lot easier to read
   than putting  
   all the end parenthesis on one line. Sure, it takes up more lines, but
   it is a lot easier to group together the commands in the specified
   level.

I suppose you'd write the same in C as

int
high (int x[], int c, int i, int h)
{
        if
          (c == 0)
                if
                   (x[c] < i)
                        high(x,
                             c - 1,
                             i,
                             h)
        ...

Give me a break!
--
Marco Antoniotti
=========================================================================== ===
California Path Program - UC Berkeley
Richmond Field Station
tel. +1 - 510 - 231 9472

Have a look at anonymous functions in Pizza, a Java superset:
<http://www.cis.unisa.edu.au/~pizza/>.

Michael

--
Michael Schuerig                        Although condemned by moralist,
mailto:uzs...@uni-bonn.de           lying can have high survival-value.
http://www.uni-bonn.de/~uzs90z/                    -Richard L. Gregory