Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1991 > unrolled thread

Re: Add nested-function support in a language the based on a stack-machine

Back to article view | Back to comp.compilers

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Add nested-function support in a language the based on a stack-machine Martin Ward <martin@gkc.org.uk> - 2018-03-12 16:17 +0000
    Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <157-073-9834@kylheku.com> - 2018-03-13 03:02 +0000
      Re: Add nested-function support in a language the based on a stack-machine Martin Ward <martin@gkc.org.uk> - 2018-03-19 11:04 +0000
        Re: Add nested-function support in a language the based on a stack-machine Gene Wirchenko <genew@telus.net> - 2018-03-19 12:50 -0700
          Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <157-073-9834@kylheku.com> - 2018-03-20 16:16 +0000
          Re: Add nested-function support in a language the based on a stack-machine Martin Ward <martin@gkc.org.uk> - 2018-03-23 10:44 +0000
            Re: algorithm performance, was Add nested-function support in a language the based on a stack-machine Andy Walker <anw@cuboid.co.uk> - 2018-03-23 18:47 +0000
              Re: algorithm performance, was Add nested-function support in a language the based on a stack-machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2018-03-24 14:06 +0000
                Re: algorithm performance, was Add nested-function support in a language the based on a stack-machine rpw3@rpw3.org (Rob Warnock) - 2018-03-25 07:02 +0000
                  Re: algorithm performance "Robin Vowels" <robin51@dodo.com.au> - 2018-03-27 01:22 +1100
            Re: sorting performance, Add nested-function support in a language the based on a stack-machine w.clodius@icloud.com (William Clodius) - 2018-03-24 23:25 -0600
        Re: Add nested-function support in a language the based on a stack-machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2018-03-20 09:06 +0000
          Re: Add nested-function support in a language the based on a stack-machine Bill Findlay <findlaybill@blueyonder.co.uk> - 2018-03-20 12:49 +0000
          Re: language design after Algol 60, was Add nested-function support Martin Ward <martin@gkc.org.uk> - 2018-03-27 14:46 +0100
            Re: language design after Algol 60, was Add nested-function support anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2018-03-30 14:20 +0000
            Re: language design after Algol 60, was Add nested-function support Martin Ward <martin@gkc.org.uk> - 2018-04-06 16:09 +0100
              Re: language design after Algol 60, was Add nested-function support "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2018-04-08 14:21 +0100
                Re: language design after Algol 60, was Add nested-function support George Neuner <gneuner2@comcast.net> - 2018-04-09 16:51 -0400
                  Re: language design after Algol 60, was Add nested-function support anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2018-04-10 05:48 +0000
                    Re: language design after Algol 60, was Add nested-function support George Neuner <gneuner2@comcast.net> - 2018-04-10 14:32 -0400
                      Re: language design after Algol 60, was Add nested-function support Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-04-12 01:09 +0200
                        Re: language design after Algol 60, was Add nested-function support bartc <bc@freeuk.com> - 2018-04-12 11:51 +0100
                          Re: language design after Algol 60, was Add nested-function support bartc <bc@freeuk.com> - 2018-04-12 19:40 +0100
                            Re: language design after Algol 60, was Add nested-function support Martin Ward <martin@gkc.org.uk> - 2018-04-13 14:10 +0100
                              Re: language design after Algol 60 "Robin Vowels" <robin51@dodo.com.au> - 2018-04-14 14:11 +1000
                                RE: language design after Algol 60 "Costello, Roger L." <costello@mitre.org> - 2018-04-16 12:56 +0000
                                  Re: language design after Algol 60 "Robin Vowels" <robin51@dodo.com.au> - 2018-04-17 19:08 +1000
                                    Re: Language design after Algol 60 "Robin Vowels" <robin51@dodo.com.au> - 2018-04-18 14:58 +1000
                                    Re: language design after Algol 60 Gene Wirchenko <genew@telus.net> - 2018-04-18 16:12 -0700
                                Re: language design after Algol 60 Martin Ward <martin@gkc.org.uk> - 2018-05-01 10:42 +0100
                            Re: language design after Algol 60 "Robin Vowels" <robin51@dodo.com.au> - 2018-04-14 14:19 +1000
                              Re: language design after Algol 60 bartc <bc@freeuk.com> - 2018-04-14 20:43 +0100
                              Re: language design after Algol 60 Andy Walker <anw@cuboid.co.uk> - 2018-04-15 00:04 +0100
                        Re: language design after Algol 60, was Add nested-function support rpw3@rpw3.org (Rob Warnock) - 2018-04-12 14:05 +0000
                        Re: language design after Algol 60, was Add nested-function support George Neuner <gneuner2@comcast.net> - 2018-04-12 20:51 -0400
                          Re: OOP language design after Algol 60, was Add nested-function support Kaz Kylheku <157-073-9834@kylheku.com> - 2018-04-13 03:22 +0000
                          Re: OOP language design after Algol 60, was Add nested-function support Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-04-13 10:22 +0200
                            Re: OOP language design after Algol 60, was Add nested-function support George Neuner <gneuner2@comcast.net> - 2018-04-14 13:40 -0400
                              Re: OOP language design after Algol 60, was Add nested-function support Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-04-15 00:12 +0200
                              Re: OOP language design after Algol 60, was Add nested-function support Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-04-15 00:23 +0200
                  Re: language design after Algol 60, was Add nested-function support "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2018-04-10 13:15 +0100
                    Re: language design after Algol 60, was Add nested-function support Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2018-04-11 13:27 +0200
                      Re: language design after Algol 60, was Add nested-function support "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2018-04-11 20:06 +0100
                  Re: language design after Algol 60, was Add nested-function support Kaz Kylheku <157-073-9834@kylheku.com> - 2018-04-10 18:32 +0000
                    Re: language design after Algol 60, was Add nested-function support George Neuner <gneuner2@comcast.net> - 2018-04-12 20:57 -0400
                      Re: OOP language design after Algol 60, was Add nested-function support Kaz Kylheku <157-073-9834@kylheku.com> - 2018-04-13 03:28 +0000
              Re: language design after Algol 60, was Add nested-function support albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2018-05-05 13:50 +0200
        Re: Add nested-function support in a language the based on a stack-machine mac <acolvin@efunct.com> - 2018-03-20 15:27 +0000
    Re: Add nested-function support in a language the based on a stack-machine w.clodius@icloud.com (William Clodius) - 2018-03-12 21:09 -0600
      Re: Add nested-function support in a language the based on a stack-machine Kartik Agaram <ak@akkartik.com> - 2018-03-13 13:27 -0700
        Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <157-073-9834@kylheku.com> - 2018-03-14 00:07 +0000
          Re: Add nested-function support in a language the based on a stack-machine Kartik Agaram <ak@akkartik.com> - 2018-03-13 22:31 -0700
            Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <157-073-9834@kylheku.com> - 2018-03-14 14:49 +0000
      Re: Add nested-function support in a language the based on a stack-machine Kaz Kylheku <157-073-9834@kylheku.com> - 2018-03-13 20:51 +0000
      Re: Add nested-function support in a language the based on a stack-machine Andy Walker <anw@cuboid.co.uk> - 2018-03-14 00:27 +0000
        Re: Add nested-function support in a language the based on a stack-machine Andy Walker <anw@cuboid.co.uk> - 2018-03-14 16:37 +0000
    Re: Add nested-function support in a language the based on a stack-machine anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2018-03-14 15:16 +0000

Page 1 of 3  [1] 2 3  Next page →

#1991 — Re: Add nested-function support in a language the based on a stack-machine

On 06/03/18 19:02, john wrote:
> Hypothetical question: Algol60 call by name was a mistake.  They
> intended an elegant definition of call by reference and didn't realize
> until Jensen's device what they'd done.  If they'd done what they
> intended and we didn't have to invent thunks, how would programming
> languages be different? -John

Lets go along with the theory that they intended call by reference
and did not realise that what they had was different until
Jenson's device was invented.  What happened next (hypothetically!)
was that the language designers realised two things:

(1) Call by name is mathematically, semantically, simpler
than call by reference

(2) Call by reference is much easier to implement than call by name.
Call by name requires significant effort to implement.

The designers decided to go with call by name because it produces
a mathematically simpler language, even at the expense of greater
effort to implement the compiler.

The result was an explosion of productive research and development
in compilers and language implementation.

Since that time, language designers have become very cautious and timid
in specifying powerful new language features and compiler research
has stagnated. An extreme example is the C language reference
which merely codifies the intersection of the behaviour of the major
C compilers, and leaves everything else "undefined".

So to answer your hypothetical question: how would programming language
be different if the designers of Algol 60 had decided to put
implementation convenience above mathematical simplicity
and expressive power in the language? Well, perhaps compiler
research would have stagnated from the beginning and we would not even
have some of the powerful language features we have now:
such as first order functions, closures, abstract data types and so on.

(In case you haven't noticed, I am trying to be provocative,
and hoping to be proved wrong: especially about the stagnation
in language design!)

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4
[It's not just a theory.  Alan Perlis told me so and
he was in a position to know.  But provoke away. -John]

[toc] | [next] | [standalone]

#1995

On 2018-03-12, Martin Ward <martin@gkc.org.uk> wrote:
> On 06/03/18 19:02, john wrote:
>> Hypothetical question: Algol60 call by name was a mistake.  They
>> intended an elegant definition of call by reference and didn't realize
>> until Jensen's device what they'd done.  If they'd done what they
>> intended and we didn't have to invent thunks, how would programming
>> languages be different? -John
>
> Lets go along with the theory that they intended call by reference
> and did not realise that what they had was different until
> Jenson's device was invented.  What happened next (hypothetically!)
> was that the language designers realised two things:
>
> (1) Call by name is mathematically, semantically, simpler
> than call by reference
>
> (2) Call by reference is much easier to implement than call by name.
> Call by name requires significant effort to implement.
>
> The designers decided to go with call by name because it produces
> a mathematically simpler language, even at the expense of greater
> effort to implement the compiler.

On the Roseta Code wiki site there is this programming task:

https://rosettacode.org/wiki/Man_or_boy_test

The aim of the task is "Imitate Knuth's example in Algol 60 in another
language, as far as possible".

I did this in my TXR Lisp dialect to a greater extent than the other
solutions, IMHO.

https://rosettacode.org/wiki/Man_or_boy_test#TXR

I implemented a "defun-cbn" macro which is like defun, but
creates a call-by-name function. I also implemented "labels-cbn"
macro for binding lexical functions, also with call-by-name
arguments.

The solution then looks like a nearly expression-for-expression
translation of the Algol:

  (defun-cbn A (k x1 x2 x3 x4 x5)
    (let ((k k))
      (labels-cbn (B ()
                    (dec k)
                    (set B (set A (A k (B) x1 x2 x3 x4))))
        (if (<= k 0)
          (set A (+ x4 x5))
          (B))))) ;; value of (B) correctly discarded here!

  (prinl (A 10 1 -1 -1 1 0))

The code for these macros is given there, and explained.
Thunks are just objects with lambdas for getting and setting
values. To pass an expression like (foo bar) by name,
which might denote a modifiablke place, it becomes.

Basically the thunk mechanism is simulated with objects that contain
getter/setter lambdas. The function calls are transformed such that their
argument expressions are wrapped in constructors of thunk objects, and then in
the bodies the references are transformed into accessors to these thunks.

There is a bit of a cheat. (defun-cbn foo (...) ...) in fact defines a macro
called foo, and not a function. It also defines a hidden function with a
machine-generated name. The macro transforms the arguments and then calls the
hidden function. This is a cheat because of course macros aren't functions;
they can't be indirected upon with apply, mapcar and so on.

> The result was an explosion of productive research and development
> in compilers and language implementation.
>
> Since that time, language designers have become very cautious and timid
> in specifying powerful new language features and compiler research
> has stagnated.

That's because machines have gotten faster and memories bigger!

Perversely, when memories get bigger, all the interesting stuff
gets a lot slower, because it has exponential complexity.

Approaches that could cut it for production use due to resource limtations that
constrained the input sizes suddenly turn into toys.

I'm only half joking; could that be part of it?

> So to answer your hypothetical question: how would programming language
> be different if the designers of Algol 60 had decided to put
> implementation convenience above mathematical simplicity
> and expressive power in the language?

I suspect that wouldn't because all that call by name stuff business is
basically just an alteration of lazy evaluation semantics into supporting
mutation.

Lazy evaluation means that when we call (f x), x isn't evaluated now; its value
isn't needed yet.  Implementation-wise, we pass down something which allows
access to x.

If x is immutable, than that something is a simple lambda that
provides read-only access.

If we don't need the laziness to be implicit in the language, we can
use (delay x) to create a promise of the value of x, and (force p)
to later force the value out of the promise object at the point
where we need it.

If we have discovered lambda as a way of obtaining lazy evaluation
(i.e. implementing delay and force) adding another lambda to also enable the
assignment of a new value to x is just a footnote. We add a second
method (stuff p) to stuff a new value into the promise.
The caller's x put into (delay x) is overwritten and so it goes.

--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

[toc] | [prev] | [next] | [standalone]

#2013

On 13/03/18 03:02, Kaz Kylheku wrote:
> That's because machines have gotten faster and memories bigger!
>
> Perversely, when memories get bigger, all the interesting stuff
> gets a lot slower, because it has exponential complexity.

Faster machines and larger memories mean that it becomes more
important to use the best algorithms. The best algorithms
are often more complex than less efficient algorithms:
which means that it is *more* important to have powerful
languages in which it is easier to define complex algorithms.

So the need for more powerful languages has only increased over time.

On 14/03/18 15:16, Anton Ertl wrote:
>> The result was an explosion of productive research and development
>> in compilers and language implementation.
>
> Is it really productive to research and develop a feature that turns
> out to be a dead end?  Even the closest thing to call-by-name these
> days, call-by-need in lazy functional languages, does not use the
> techniques developed by call-by-name.

Actually, the closest thing to call-by-name is first class functions
(technically: downward funargs). The desire for mathematical
simplicity over implementation simplicity drove the choice
of call by name over call by reference. Call by name allowed
Jenson's Device which is a method of passing a function as a parameter.
Call by name turned out to be implementable by, in effect,
passing a function as a parameter.

Of course, with hindsight we can see that defining function parameters
directly in the language would be an even better solution:
but language design was still in its early days at the time,
and Algol 60 was "not only an improvement on its predecessors,
but also on nearly all its successors" (C.A.R. Hoare).

How many modern languages can claim the same?

> Algol 60 did not have first-order functions and closures.  It did have
> lexical scoping, though, which the Lisp family only acquired with
> Scheme in 1975.
>
> Algol 60 certainly did not have abstract data types.  It did not even
> have records.
>
> So these are examples that actually contradict your theory.

My theory is that the attitude of the Algol 60 designers towards
language design is what led to these innovations appearing
over then next 20 years: this is the "explosion of productive
research and development in compilers and language implementation"
that I was referring to.

What similar innovations in compilers and language design
have appeared over the *last* 20 years? (Haskill is still considered
by some to be a scary new innovative language: it was initially
developed in the early 1990's, over 20 years ago).

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

[toc] | [prev] | [next] | [standalone]

#2014

On Mon, 19 Mar 2018 11:04:20 +0000, Martin Ward <martin@gkc.org.uk>
wrote:

[snip]

>Faster machines and larger memories mean that it becomes more
>important to use the best algorithms.

     How does that follow?

     One could argue exactly the opposite as there are resources to
waste.

[snip]

Sincerely,

Gene Wirchenko
[Depends on the algorithms.  If they're linear, things are fine,
not so fine if they're O(N^2) or O(2^N) -John]

[toc] | [prev] | [next] | [standalone]

#2018

On 2018-03-19, Gene Wirchenko <genew@telus.net> wrote:
> On Mon, 19 Mar 2018 11:04:20 +0000, Martin Ward <martin@gkc.org.uk>
> wrote:
>
> [snip]
>
>>Faster machines and larger memories mean that it becomes more
>>important to use the best algorithms.
>
>      How does that follow?
>
>      One could argue exactly the opposite as there are resources to
> waste.

Clever algorithms had to be used when machines were slow even on small
data and the data and code had to fit into small memories.

Clever algorithms have to be used when data sets are large.

In between there is a large territory where the machines are powerful,
but the problems (or sub-problems) being solved are reasonably small.
Here we use interpreted languages instead of compiled, linked lists
instead of more specific data structures, hashes instead of vectors and
N-dimensional data even when it isn't sparse and so on.

[toc] | [prev] | [next] | [standalone]

#2022

On 19/03/18 19:50, Gene Wirchenko wrote:
>> Faster machines and larger memories mean that it becomes more
>> important to use the best algorithms.
>
> How does that follow?

It follows because data expands to fill the memory available.

> One could argue exactly the opposite as there are resources to
> waste.
>
> [Depends on the algorithms.  If they're linear, things are fine, not
> so fine if they're O(N^2) or O(2^N) -John]

My first computer had 8K of RAM and a 1MHz clock speed.
If I wanted to sort 1,000 values I could use bubble sort, O(N^2),
or quicksort, O(N log N).

So, bubble sort would need of the order of 1,000,000 instructions
and take about 1 second: this might well be acceptable for an operation
you only need to do a few times an hour. Quicksort would need
of the order of 10,000 instructions and take 0.01 seconds.

My current laptop (not the latest model) has 8Gb of RAM:
literally, over a million times as much RAM, and a 1.7 GHz clock.
Even accounting for more powerful instructions, the clock is
only of the order 10,000 times faster, while the memory is 1,000,000
times larger. Now 1,000,000,000 values will fit in RAM.
Sorting these with bubble sort will need of the order 10^18 instructions
which takes 100,000,000 seconds (over 1,000 years) while quicksort
needs 300,000,000,000 instructions and takes only a few seconds.

For a linear algorithm, say a linear search, my first computer
takes 0.001 seconds to process the data, while my new laptop
takes 0.1 seconds. So if I need to execute this linear algorithm
more than 10 times a second, my old computer will be fine
but my new laptop would struggle. I would need to look hard
for a sub-linear algorithm.

Conclusion: even for linear algorithms things may not be fine
and more powerful sub-linear algorithms may be needed.

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4
[Give or take the detail that bubble sort is never the right algorithm
since insertion sort is shorter and faster, I agree. -John]

[toc] | [prev] | [next] | [standalone]

#2023 — Re: algorithm performance, was Add nested-function support in a language the based on a stack-machine

On 23/03/18 10:44, Martin Ward wrote:
[...]
> which takes 100,000,000 seconds (over 1,000 years)

	Point of order:  100,000,000 seconds is about pi years.

[...]
> For a linear algorithm, say a linear search, my first computer
> takes 0.001 seconds to process the data, while my new laptop
> takes 0.1 seconds. So if I need to execute this linear algorithm
> more than 10 times a second, my old computer will be fine
> but my new laptop would struggle.

	On the other hand, if you needed to search, say, a million
items, your new laptop would process them in around a millisecond,
while your first computer would spend however long it took you to
feed in the data bit-by-bit from a sequence of floppies.  Several
minutes?

	Somewhat more to the point, as this is "comp.compilers",
it seems unlikely that either the compiler or the source being
compiled have grown by anything like the growth in RAM, despite the
unfortunate modern [ie last 40-odd years!] tendency towards bloat.
It seems somewhat OTT to claim that we need better algorithms
*because of* faster and logically-bigger computers.  We want them
primarily because they are better!

--
Andy Walker,
Nottingham.
[Well, both.  Some compiler optimization algorithms can be quite slow,
ike optimal register assignment and constructing perfect hashes. -John]

[toc] | [prev] | [next] | [standalone]

#2024 — Re: algorithm performance, was Add nested-function support in a language the based on a stack-machine

Andy Walker <anw@cuboid.co.uk> writes:
>	Somewhat more to the point, as this is "comp.compilers",
>it seems unlikely that either the compiler or the source being
>compiled have grown by anything like the growth in RAM, despite the
>unfortunate modern [ie last 40-odd years!] tendency towards bloat.

One of the papers I saw during this recent discussion mentions that
one of Wirth's early compilers (PL/360 IIRC) self-compiled in IIRC 25s
on a machine of the time, i.e., late 1960s (which the author of the
paper found quite impressive).  In 1992, I heard a keynote address by
Wirth (at CC'92), where he contrasted Oberon with C++, and used
self-compilation time as one metric: The Oberon compiler compiled
itself in IIRC 6s, which he contrasted with IIRC 20 minutes for the
C++ compiler.

The last few times that I built a recent gcc, it took several hours to
compile itself (three stages, and it included several front-ends, but
still); interestingly, I rebuilt gcc-2.7 in 2015, and that took only a
few minutes.

Software bloats to fill the memory and run-time that is deemed
acceptable.  Whether that means more or less sophistication in the
algorithms varies from case to case.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/
[Back in the 1970s, the Dartmouth BASIC compiler was so fast that
nobody bothered to save object code.  It rarely took more than a few
clock ticks from source code to starting the executable.  -John]

[toc] | [prev] | [next] | [standalone]

#2026 — Re: algorithm performance, was Add nested-function support in a language the based on a stack-machine

At the end of a message by Anton Ertl <anton@mips.complang.tuwien.ac.at>,
our august moderator noted:
+---------------
| [Back in the 1970s, the Dartmouth BASIC compiler was so fast that
| nobody bothered to save object code.  It rarely took more than a few
| clock ticks from source code to starting the executable.  -John]
+---------------

And lest we forget:

    https://en.wikipedia.org/wiki/WATFIV

WATFOR/WATFIV [a.k.a. Univ. Waterloo FORTRAN] was a compile-and-go
system widely used to teach FORTRAN from 1965 until the late 1980s
[and in some places until >1995].

-Rob

-----
Rob Warnock		<rpw3@rpw3.org>
627 26th Avenue		<http://rpw3.org/>
San Mateo, CA 94403
[Apropos of another comment, Dartmouth BASIC was a real compiler that
generated machine code.  So was WATFOR/WATFIV. -John]

[toc] | [prev] | [next] | [standalone]

#2027 — Re: algorithm performance

> From: "Rob Warnock" <rpw3@rpw3.org>

> And lest we forget:
>
>    https://en.wikipedia.org/wiki/WATFIV
>
> WATFOR/WATFIV [a.k.a. Univ. Waterloo FORTRAN] was a compile-and-go
> system widely used to teach FORTRAN from 1965 until the late 1980s

And let's not forget Charles Hamblin's GEORGE,
which did the same thing from 1957,
namely, compile-and-go.

[toc] | [prev] | [next] | [standalone]

#2025 — Re: sorting performance, Add nested-function support in a language the based on a stack-machine

Martin Ward <martin@gkc.org.uk> wrote:

> <snip>> [Give or take the detail that bubble sort is never the right algorithm
> since insertion sort is shorter and faster, I agree. -John]

I believe that bubble sort is faster if the data is usually presorted.
The Unicode consortium describes the sorting of codepoints to forn the
normalization forms, because the initial decomposition process usually
results in an ordering that is usually in or close to the desired order.

[It's the reverse.  Insertion sort is O(N) if the list is already sorted.
See http://www.differencebetween.com/difference-between-bubble-sort-and-vs-insertion-sort/
-John]

[toc] | [prev] | [next] | [standalone]

#2015

Martin Ward <martin@gkc.org.uk> writes:
>Of course, with hindsight we can see that defining function parameters
>directly in the language would be an even better solution:
>but language design was still in its early days at the time,
>and Algol 60 was "not only an improvement on its predecessors,
>but also on nearly all its successors" (C.A.R. Hoare).
>
>How many modern languages can claim the same?

Was Hoare right in making this claim?  He made this claim in 1973, and
indeed most langauges developed between 1960 and 1973 have been
forgotten by now, and probably Algol 60 was an improvement over many
of them.

Interestingly, Hoare was in the more implementation-oriented Algol W
faction of the post-60 Algol committee rather than the more
mathematical faction that won out and eventually produced the Algol 68
report.  He probably meant especially Algol 68 as successor over which
Algol 60 was an improvement.  So this claim actually condemns the
attitude that you praise.

[Anton Ertl:]
>> Algol 60 did not have first-order functions and closures.  It did have
>> lexical scoping, though, which the Lisp family only acquired with
>> Scheme in 1975.
>>
>> Algol 60 certainly did not have abstract data types.  It did not even
>> have records.
>>
>> So these are examples that actually contradict your theory.
>
>My theory is that the attitude of the Algol 60 designers towards
>language design is what led to these innovations appearing
>over then next 20 years: this is the "explosion of productive
>research and development in compilers and language implementation"
>that I was referring to.

Higher-order functions (I somehow mixed up "higher-order" with
"first-class" in the above) were already available in IPL, before
Algol 60, which falsifies this theory for this feature.

Records were available in Cobol, contemporary with Algol 60, so again,
this theory is falsified in this case.

Concerning features that appeared after 1960, there is no way to
verify or falsify your theory.

>What similar innovations in compilers and language design
>have appeared over the *last* 20 years? (Haskell is still considered
>by some to be a scary new innovative language: it was initially
>developed in the early 1990's, over 20 years ago).

Many people that used to research programming in the 1960s thought in
the late 1960s that programming languages were a solved problem, and
refocused on software engineering.  The field certainly has matured,
and a sign of that maturity is that 1) you don't get great
breakthroughs all the time and 2) that even when there is a useful
innovation, it takes quite a while until it appears in mainstream
languages.

Actually, it even took quite a while in the early years; e.g., IPL
(1956) had higher-order functions, Algol 60 didn't, Pascal (1970) did,
Ada-83 didn't (IIRC).

And a lot of the work that has been done in the last decades are about
making various features fit together that have lived in separation in
various programming languages for a long time.  E.g., Java 5 (2004)
added generics to Java and Java 8 (2014) added lambdas.  Both feature
are much older, but needed to be integrated with the Java type system.
And of course, people also needed to be convinced that these features
are worth the complexity that they add to the language.

There are new features being developed all the time.  We will see
which of them make it into a mainstream language, but in any case that
will take it's time.

One of the more prominent recent ones is the way that Rust combines
static type checking with explicit memory management to ensure memory
safety in low-level languages.

There is also quite a bit of innovation in tools, e.g., in fuzz
testing, and in using theorem provers for software verification.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#2016

On 20 Mar 2018, Anton Ertl wrote (in article<18-03-079@comp.compilers>):

> Actually, it even took quite a while in the early years; e.g., IPL
> (1956) had higher-order functions, Algol 60 didn't, Pascal (1970) did,
> Ada-83 didn't (IIRC).

Algol 60 and Wirth Pascal had exactly the same functional-parameter
capability;
i.e. both procedural and functional parameters were included,
but neither language provided a way to specify their signatures.

This was rectified for Pascal, with Wirth's approval, by the BSI Pascal
standard and later by the bureaucratic variant of the latter known as ISO
Pascal.

(Ada 83 provided a clumsy way to do it by means of generics;
later versions of Ada do it properly.)

--
Bill Findlay

[toc] | [prev] | [next] | [standalone]

#2028 — Re: language design after Algol 60, was Add nested-function support

On 20/03/18 09:06, Anton Ertl wrote:
> Higher-order functions (I somehow mixed up "higher-order" with
> "first-class" in the above) were already available in IPL, before
> Algol 60, which falsifies this theory for this feature.

The theory is that "the attitude of the Algol 60 designers towards
language design is what led to these innovations appearing".
Clearly, this "attitude" was present before, during and after
the development of Algol 60.  In the context of the theory,
Algol 60 is just one example of the influence of attitude.

The second part of the theory is that since that time,
the attitude has changed and "language designers have become
very cautious and timid in specifying powerful new language features
and compiler research has stagnated."

> Concerning features that appeared after 1960, there is no way to
> verify or falsify your theory.

It should be easy to falsify the theory: where are the new language
features that have been invented in the last, say, twenty years?
Where are the powerful new languages which make Haskell
look like Dartmouth BASIC?

A very small example of language designers prioritising
implementation effort over power and simplicity: even today there
are very few mainstream languages which implement arbitrary precision
integers ("bignums") and rational numbers as primitive data types.
Proving that an algorithm is correct is simpler when you don't have
to worry about integer overflow, or floating point approximations.
For example, the binary search algorithm that Jon Bentley proved correct
and published in "Programming Pearls" in 1986 had a bug that
was not detected for two decades:

https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

It doesn't help that C and C++ have very lax rules for dealing
with overflow (in the sense that many cases are declared to
be undefined behaviour), leading to complex solutions for
simple problems:

http://www.di.unipi.it/~ruggieri/Papers/semisum.pdf

(I am still hoping for my theory to be proved wrong!)

A related, and more worrying, trend is the new and growing area
of research under the heading "empirical software engineering"
which aims to do away with program semantics altogether.
A program is deemed "correct" if and only if it passes its test suite.
Various automated and semi-automated ways of modifying the program
are being investigated: any modification which passes the test suite
is deemed to be "correct". For example, "empirical slicing"
may be defined as "delete random sections of code and call the result
a valid slice if it passes the regression test". Program semantics
and program analysis are considered to be "too difficult"
by these researchers, and therefore are not attempted.

Readers of comp.risks will no doubt already be wondering how
such methods avoid introducing security holes: given that
a security hole will not necessarily prevent the program
from passing its test suite (unless the tests happen
to include the carefully crafted data which triggers
the security hole!) As far as I can tell, the answer is:
they don't!

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

[toc] | [prev] | [next] | [standalone]

#2030 — Re: language design after Algol 60, was Add nested-function support

Martin Ward <martin@gkc.org.uk> writes:
>On 20/03/18 09:06, Anton Ertl wrote:
>> Higher-order functions (I somehow mixed up "higher-order" with
>> "first-class" in the above) were already available in IPL, before
>> Algol 60, which falsifies this theory for this feature.
>
>The theory is that "the attitude of the Algol 60 designers towards
>language design is what led to these innovations appearing".
>Clearly, this "attitude" was present before, during and after
>the development of Algol 60.

Ok, so this theory cannot even be verified of falsified for the
features that came before Algol 60.

In any case, I think this attitude is still present.

>The second part of the theory is that since that time,
>the attitude has changed and "language designers have become
>very cautious and timid in specifying powerful new language features
>and compiler research has stagnated."

And I think that this is not the case.  It's just that hardly any new
language features and languages achieve popularity (and those that do
take a long time).  Admittedly that feeds back to discourage some from
going there, but language design is far too fascinating to let that
discourage everyone.  E.g., Christian Heinlein is doing interesting
things with flexible syntax <http://flexipl.info/tutorial/>.

>It should be easy to falsify the theory: where are the new language
>features that have been invented in the last, say, twenty years?

I mentioned some things in the grandfather posting.  Do you want me to
repeat them?

>Where are the powerful new languages which make Haskell
>look like Dartmouth BASIC?

You mean a language that is even harder to learn and even less
practical than Haskell?-) Such languages are developed in significant
numbers: Take a look at
<https://en.wikipedia.org/wiki/Esoteric_programming_language>.

>A related, and more worrying, trend is the new and growing area
>of research under the heading "empirical software engineering"
>which aims to do away with program semantics altogether.
>A program is deemed "correct" if and only if it passes its test suite.

Sounds to me like test-driven development.  Not really new, however.
I heard about it in a talk by Kent Beck 20 years ago.

>Various automated and semi-automated ways of modifying the program
>are being investigated: any modification which passes the test suite
>is deemed to be "correct". For example, "empirical slicing"
>may be defined as "delete random sections of code and call the result
>a valid slice if it passes the regression test". Program semantics
>and program analysis are considered to be "too difficult"
>by these researchers, and therefore are not attempted.

That's an interesting idea, if it exists (the things Google gave me
when I asked for "empirical slicing" or "empirical program slicing"
did not appear to fit your description).  It may not be the direction
you favour, but it would be something new, wouldn't it?

Googling for "empirical software engineering" also does not give me
any hits that fit your description, either.

>Readers of comp.risks will no doubt already be wondering how
>such methods avoid introducing security holes: given that
>a security hole will not necessarily prevent the program
>from passing its test suite (unless the tests happen
>to include the carefully crafted data which triggers
>the security hole!) As far as I can tell, the answer is:
>they don't!

And neither did the waterfall model.  I am not a security expert, but
AFAIK the old-fashioned way to get there are to be aware of security
issues during design and coding, and then doing a code audit.
However, there have been some successes in finding vulnerabilities
with fuzz testing, and with techniques based on automated theorem
provers.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#2032 — Re: language design after Algol 60, was Add nested-function support

On 30/03/18 15:20, Anton Ertl wrote:
>> The theory is that "the attitude of the Algol 60 designers towards
>> language design is what led to these innovations appearing".
>> Clearly, this "attitude" was present before, during and after
>> the development of Algol 60.
> Ok, so this theory cannot even be verified of falsified for the
> features that came before Algol 60.

John asked us to speculate what might have happened differently,
not produce empirically verifiable theories :-)

I came across this quote the other day, which suggests that the change
in attitude had already started by 1979:

"The call-by-name mechanism is so expensive that modern languages
have mostly dropped it in favour of the semantically different,
but operationally more efficient, call-by-reference"
--"Understanding and Writing Compilers", Richard Bornat, Macmillan 1979.

Note that the

>> It should be easy to falsify the theory: where are the new language
>> features that have been invented in the last, say, twenty years?
>
> I mentioned some things in the grandfather posting.  Do you want me to
> repeat them?

You mentioned generics and lambdas, both of which you acknowledge
have been around for a long time: lambdas have been around
since the original Lisp!

You also mentioned combining static type checking with explicit
memory management: again two features which have been around
for decades.  One might ask: why earth we still need explicit memory
management in this day and age? Because it is more efficient
to implement?  Doesn't that prove what I have been saying all along?

Re "empirical software engineering", I apologise that I mis-remembered
the term used and sent you on a wild goose chase. :-(
"Search based software engineering" might be a more accurate term.
Two examples are:

"Observation Based" or "Language Independent" program slicing
involves deleting random chunks of code and then compiling
and re-testing the result (if possible) to see if it is
a "valid" slice (where a "valid" slice is defined as
"one which passes the test suite"):

http://coinse.kaist.ac.kr/publications/pdfs/Binkley2014ud.pdf

"Automated Software Transplantation" involves copying random blocks
of code from one program to another and testing if the resulting
program still "works" (ie passes its test suite) and also
contains some functionality from the other program
(eg it can now handle a new file format).

http://crest.cs.ucl.ac.uk/autotransplantation/downloads/autotransplantation.pdf

https://motherboard.vice.com/en_us/article/bmj9g4/muscalpel-is-an-algorithmic-code-transplantation

> It may not be the direction
> you favour, but it would be something new, wouldn't it?

It is like introducing alchemy into the chemistry department:
let's forget all the theory and all the maths and just smush
random chemicals together and see what happens!
Yes, it's something new, and no, it's not a direction I favour.

>> Where are the powerful new languages which make Haskell
>> look like Dartmouth BASIC?
>
> You mean a language that is even harder to learn and even less
> practical than Haskell?-)

Modern popular languages are neither powerful nor easy to learn.
The latest C standard is over 700 pages (even the Haskell Language
Report is only 329 pages!). In the pursuit of efficiency over
everything, C leaves so many operations "undefined" (there are
around 199 examples of undefined behaviour) that simply
writing a piece of code to carry out twos-complement arithmetic
(in a fully standards-complient manner) is a challenge
to tax the most experienced programmers: and probably compiles
into very inefficient object code even on a processor which has
native twos complement arithmetic operations!

https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow

For C++ there is the SafeInt class which tries to do this:
but examples of undefined behaviour were detected in that library,
which caused it to give incorrect results on some compilers:

http://www.cs.utah.edu/~regehr/papers/overflow12.pdf

One effect of the increases in memory size and CPU speed over
the decades is that it allows programmers to write much larger
programs and implement solutions to much more complex problems.
This makes mastering complexity far more important.
A language which is an order of magnitude more powerful
would mean that programmers need to write and comprehend
an order of magnitude less code: and each individual programmer
or small team could work on problems which are an order of
magnitude more complex. If this language takes an order of magnitude
longer to learn and fully understand, then it is still worth it!

Unfortunately, this flies in the face of modern business practice
where "programmers" are a cheap resource to be hired and put to work
generating lines of code.

--
			Martin

Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk
G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4

[toc] | [prev] | [next] | [standalone]

#2033 — Re: language design after Algol 60, was Add nested-function support

All,

> John asked us to speculate what might have happened differently,
> not produce empirically verifiable theories :-)

http://shape-of-code.coding-guidelines.com/2016/05/23/the-fall-of-rome-and-the-ascendancy-of-ego-and-bluster/

> You also mentioned combining static type checking with explicit

A language can contain strong typing, but these are useless unless
people actually use them:
http://shape-of-code.coding-guidelines.com/2014/04/17/c-vs-ada-which-language-is-more-strongly-typed/

Some weak evidence that stronger typing saves some time.
My view is that the benefit happens over longer timescales (too long
for it to be cost effective to run an experiment):
http://shape-of-code.coding-guidelines.com/2014/08/27/evidence-for-the-benefits-of-strong-typing-where-is-it/

> Re "empirical software engineering",

If anybody has any public data that I don't have, please let me know:
http://www.knosof.co.uk/ESEUR

> It is like introducing alchemy into the chemistry department:

I would say it's more akin to saying that chemistry papers need to
maximize the number of mathematical orgasm they contain and lets
ignore reality.

> let's forget all the theory and all the maths and just smush
> random chemicals together and see what happens!
> Yes, it's something new, and no, it's not a direction I favour.

http://shape-of-code.coding-guidelines.com/2017/11/29/vanity-project-or-real-research/

> Modern popular languages are neither powerful nor easy to learn.

What evidence do you have for this?

[toc] | [prev] | [next] | [standalone]

#2034 — Re: language design after Algol 60, was Add nested-function support

On Sun, 8 Apr 2018 14:21:48 +0100, "Derek M. Jones"
<derek@_NOSPAM_knosof.co.uk> wrote:


> Martin Ward wrote:
>> Modern popular languages are neither powerful nor easy to learn.
>
>What evidence do you have for this?

I disagree about "easy to learn" - there are plenty of languages that
are easy to learn.  But as to the question of "power" ...

Note that "powerful" and "useful" (for some definition) are not the
same thing.  There are plenty of semantically restricted languages
that can be considered useful for their intended purposes.

That said:


IMO, the evidence that many popular languages are not "powerful" is
that they are either exclusively or primarily OO, but they implement
only single inheritance objects.

Wherever you stand on OO as a programming paradigm, you can't deny
that single inheritance is the weakest variant of it.  The addition of
"interfaces" and "mix-ins" does not make up for the lack of true
multiple inheritence in those situations where it is needed.

The necessity to write "Design Patterns" was, IMO, acknowledgement
that the average programmer could not figure out how to express their
ideas under Java's limited object model.



I prefer to use languages that naturally support multiple programming
paradigms, and don't put many (or any) limits on what can be done
using them.  Some solutions are best expressed procedurally, others
are more naturally functional, and yet others are best modeled using
objects.

I relegate to the proverbial junk heap the many languages that force
solutions to be shoehorned into a model that they don't naturally fit.
There are too many "me too" languages that think a simple object model
combined with procedural code is the solution to every problem.


YMMV,
George

[toc] | [prev] | [next] | [standalone]

#2046 — Re: language design after Algol 60, was Add nested-function support

George Neuner <gneuner2@comcast.net> writes:
>The necessity to write "Design Patterns" was, IMO, acknowledgement
>that the average programmer could not figure out how to express their
>ideas under Java's limited object model.

Design Patterns was published in 1994 (based on work that started in
1990), before Java was published in 1995.  Moreover, it says at the
beginning that the design patterns are somewhat language-specific, and
that the language they have in target is C++.  It seems to me to be
more a guideline of how to make use of the vast possibilities of a
programming language to achieve certain things effectively (and with
maintainable results), rather than a guideline on how to work around
limitations.

- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

[toc] | [prev] | [next] | [standalone]

#2053 — Re: language design after Algol 60, was Add nested-function support

On Tue, 10 Apr 2018 05:48:43 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

>George Neuner <gneuner2@comcast.net> writes:
>>The necessity to write "Design Patterns" was, IMO, acknowledgement
>>that the average programmer could not figure out how to express their
>>ideas under Java's limited object model.
>
>Design Patterns was published in 1994 (based on work that started in
>1990), before Java was published in 1995.

Java began in 1991 ... as a language called "Oak".  Many people used
and/or experimented with Oak for mobile programming prior to it
becoming Java.  It was very well known.


>Moreover, [Design Patterns] says at the
>beginning that the design patterns are somewhat language-specific, and
>that the language they have in target is C++.

That is *partly* true, but read on.


On page 14, it says:
<quote>
 :
We chose Smalltalk and C++ for pragmatic reasons: Our day-to-day
experience has been in these languages, and they are increasingly
popular.

The choice of programming language is important because it influences
one's point of view. Our patterns assume Smalltalk/C++-level language
features, and that choice determines what can and cannot be
implemented easily.
 :
</quote>


Smalltalk had/has single inheritence only, and it's dynamic dispatch
mechanism is very different from that of C++.  Examples that were
meant to work in both languages had to be targeted to the lowest
common denominator ... which in most cases meant Smalltalk even if the
syntax of the example was in C++.

The largely Smalltalk centric text transferred very naturally to
Oak/Java because their object models shared many of the same
limitations.  Oak already was more popular than Smalltalk by the time
the book was finished, and the more expansive desktop Java was
starting to take off as well.

[Yes, I have ... in honesty, read parts of, skimmed others ... the
book.  And yes, I worked with Smalltalk (ParcPlace on the Macintosh)
plenty enough to be familiar with its object model.  Smalltalk was my
6th or 7th programming language - I was learning Objective-C at more
or less the same time, so I'm not quite certain of the chronology
there.  C++ (at least what it added wrt C) came next as my 8th
language.]


There is some good stuff in the book, but many of the patterns either
are trivial to implement or simply unnecessary in C++ where all code
does NOT have to be ensconced in some object.  Many others add little
value in C++ beyond some algorithmic decoupling.

Now decoupling is a three edged sword: it can make code more
maintainable, but it can also make code more complicated.  In either
case, it can (and usually does) make code slower.

C++ programmers accept that using objects exacts a small runtime cost,
but as a breed they tend to eschew things that make their programs
*unnecessarily* slower.

So C++ programmers largely ignored "Design Patterns" because many felt
it really wasn't all that useful to them.


OTOH, Java programmers embraced it and held it up as the gospel of
program design.  For quite a long while, if you weren't intimately
familiar with the gory details of <insert pattern here>, you couldn't
get a Java programming job to save your life.

Not so for C++.  Few C++ managers gave a damn whether you could
describe <insert pattern here> ... most were more interested in how
you would go about solving the problem.


>It seems to me to be
>more a guideline of how to make use of the vast possibilities of a
>programming language to achieve certain things effectively (and with
>maintainable results), rather than a guideline on how to work around
>limitations.

That's undoubtedly what it was intended to be.  Unfortunately I think
it ended up being more of a crutch for Java.


>- anton
YMMV, and certainly it will.
George

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.compilers

csiph-web