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

Groups > comp.compilers > #1995

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

Show key headers only | View raw

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

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

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

csiph-web